Plant 'n' Seek: Can You Find the Winning Ticket?

Jonas Fischer, Rebekka Burkholz

Introduction

The "Lottery Ticket Hypothesis" (LTH) suggests that large, over-parameterized neural networks contain tiny, sparse subnetworks that can perform just as well as the full model. However, finding these "winning tickets" at extreme sparsity levels has proven incredibly difficult.

This paper introduces Plant 'n' Seek, a novel framework that hides hand-crafted, optimal sparse networks inside larger ones. By doing so, the authors test whether current pruning algorithms can actually find these tickets, ultimately revealing that our current "seekers" (the algorithms) are the primary bottleneck, not the existence of the tickets themselves.

The "Missing Baseline" Problem

In deep learning, models are often over-parameterized to make them easier to train, then "pruned" (connections removed) to make them efficient for deployment. The LTH claims these efficient subnetworks exist from the very start. There are two flavors of these tickets:

  • Weak LTs: Subnetworks that can be trained to high accuracy.
  • Strong LTs: Subnetworks that work well at initialization without any training.

While theory dictates these tickets exist, current algorithms struggle to find them at high sparsity levels (e.g., 99% pruned). This creates a "missing baseline" problem: when an algorithm fails to find a sparse ticket, is it because the ticket doesn't exist, or because the algorithm is simply bad at finding it? This paper aims to settle the debate by creating a verifiable "ground truth" benchmark.

The Plant 'n' Seek Framework

To establish this ground truth, the authors propose a two-part approach:

  1. Theoretical Proof: They derive a new lower bound on the probability that a target sparse architecture exists within a larger, randomly initialized network of the same depth.
  2. The Planting Algorithm: To create a benchmark, they "plant" a known, hand-crafted sparse subnetwork into a large, dense "mother" network.
A sparse subnetwork planted within a dense mother network.

The primary challenge in planting is that you cannot simply copy weights; the planted ticket must be "hidden" so it doesn't stand out statistically (e.g., by having unusually large weights). The authors solve this using a clever scaling framework. Because a sparse network has fewer paths to the output, its weights must be scaled up to match the output range of the dense network. Their algorithm matches target neurons to mother network neurons and adjusts scaling factors to ensure the planted ticket is functionally identical to the target but seamlessly blended in.

Custom Datasets for Ground Truth

Instead of relying solely on standard image datasets where the "optimal" subnetwork is unknown, the authors designed specific "toy" tasks with known, hand-crafted sparse solutions:

  • ReLU Regression: A simple path-based task.
  • Circle (Classification of Rings): A 2D classification task requiring the calculation of $x^2 + y^2$, utilizing a sparse architecture based on mirroring symmetry.
  • Helix (Manifold Learning): A 1D-to-3D regression task that tests an algorithm's ability to handle complex coordinate mappings.
The Circle and Helix datasets designed with known optimal sparse solutions.

To bridge the gap to real-world settings, they also "planted" a trained weak ticket back into a random VGG16 architecture on CIFAR-10 to see if it could be recovered.

Key Findings

  • Algorithmic Failure, Not Existence Failure: The most significant insight is that even when a perfect, extremely sparse subnetwork is known to exist (because it was planted), state-of-the-art pruning algorithms like SNIP, GraSP, and SynFlow fail to find it. This proves the LTH bottleneck is currently algorithmic.
  • The Scaling Secret: "Strong" lottery tickets require specific weight scales. If a pruning algorithm doesn't account for how weights must grow as the network gets sparser, it will likely fail.
  • Layer Collapse: A common failure mode is "layer collapse," where algorithms accidentally prune every single connection in one layer, killing the gradient flow. Even advanced algorithms like SynFlow suffer from this at the extreme sparsities required to find the planted tickets.
  • Singleshot vs. Multishot: Most "singleshot" methods (pruning in one go before training) failed to find any functional tickets at the sparsity levels of the planted ground truth.
  • The VGG16 Test: In the VGG16 experiment, even after planting a known-good subnetwork with only 1% of the weights, the "seekers" could not retrieve it, instead finding much denser, less accurate subnetworks.

Conclusion and Future Work

While the hand-crafted tasks are low-dimensional and don't fully replicate the high-dimensional noise of tasks like ImageNet, they capture fundamental mathematical challenges that current algorithms fail to overcome. The planting algorithm currently focuses on matching architectures of the same depth, leaving room for future work to explore planting tickets across different depths or more complex convolutional structures.

Ultimately, the paper concludes that the field needs better "seekers." By providing the Plant 'n' Seek code and benchmarks, the authors have given the community a vital tool to measure whether new pruning algorithms are actually getting closer to the theoretical limits of network compression.

Summary updated

Abstract

The lottery ticket hypothesis has sparked the rapid development of pruning algorithms that aim to reduce the computational costs associated with deep learning during training and model deployment. Currently, such algorithms are primarily evaluated on imaging data, for which we lack ground truth information and thus the understanding of how sparse lottery tickets could be. To fill this gap, we develop a framework that allows us to plant and hide winning tickets with desirable properties in randomly initialized neural networks. To analyze the ability of state-of-the-art pruning to identify tickets of extreme sparsity, we design and hide such tickets solving four challenging tasks. In extensive experiments, we observe similar trends as in imaging studies, indicating that our framework can provide transferable insights into realistic problems. Additionally, we can now see beyond such relative trends and highlight limitations of current pruning methods. Based on our results, we conclude that the current limitations in ticket sparsity are likely of algorithmic rather than fundamental nature. We anticipate that comparisons to planted tickets will facilitate future developments of efficient pruning algorithms.
BibTeX
@inproceedings{fischer2022plant,
  author = {Jonas Fischer and Rebekka Burkholz},
  title = {{Plant 'n' Seek: Can You Find the Winning Ticket?}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=9n9c8sf0xm},
}
Figure