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:
- 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.
- The Planting Algorithm: To create a benchmark, they "plant" a known, hand-crafted sparse subnetwork into a large, 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.
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