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.
Introduction
Deep learning is notoriously resource-intensive, prompting interest in the Lottery Ticket Hypothesis (LTH). The LTH posits that large neural networks contain small, trainable subnetworks—"winning tickets"—capable of matching the performance of the full model. A "strong" version suggests these tickets exist at initialization, requiring only the correct binary mask to be identified.
However, evaluating pruning algorithms is hindered by a lack of "ground truth" in complex datasets like images. If an algorithm identifies a subnetwork at 10% sparsity, it remains unclear if a 0.1% subnetwork exists but was missed. Without a baseline, researchers cannot distinguish between the limitations of a network's initialization and the failures of the pruning algorithm itself.
The Plant 'n' Seek Framework
The authors introduce a framework to plant winning tickets with known properties into a larger "mother" network.
The Planting Algorithm
To avoid making the ticket trivial to find (e.g., by simply overwriting weights), the algorithm identifies neurons in the large network that already approximate the target "winning" neurons. It minimizes the $L_2$ distance between them and applies an optimal scaling factor ($\lambda$) to embed the ticket within the random noise of the surrounding weights.
Target Construction and Datasets
The study utilizes hand-crafted sparse target networks representing distinct mathematical challenges:
- ReLU Unit: A simple path-based regression task.
- Circle Task: A 4-class classification task based on radial symmetry ($x^2 + y^2$).
- Helix Task: A complex regression task mapping a 1D input to a 3D manifold.
By moving away from standard image datasets, the paper focuses on synthetic benchmarks where the optimal solution is mathematically defined. For instance, the Helix task provides a rigorous test for regression capabilities.
Benchmarking Pruning Algorithms
The authors tested several "singleshot" (pruning once at initialization) and "multishot" (iterative pruning and training) algorithms, including SNIP, GraSP, SynFlow, Magnitude pruning, and Edge-Popup.
Key Insights
- The Algorithmic Gap: Since the authors know a 0.01% sparsity ticket exists, the failure of current algorithms to find it demonstrates that the bottleneck is algorithmic. We are limited by search tools, not the "luck of the draw" at initialization.
- Layer Collapse: Pruning often fails at high sparsity due to "layer collapse," where an algorithm prunes all connections in a specific layer, severing information flow.
- Regression Difficulty: Algorithms that succeed on classification (e.g., the Circle task) often fail on regression (e.g., the Helix task), suggesting a bias in current pruning heuristics toward classification boundaries.
- Scaling Importance: "Strong" tickets often require specific weight scaling. Algorithms that ignore this struggle to identify the underlying winning architecture.
Results
- Sub-optimal Sparsity: Most state-of-the-art methods fail to recover effective tickets once sparsity drops below 1% ($10^{-2}$), despite the existence of much sparser planted tickets.
- SynFlow Performance: Among singleshot methods, SynFlow was most effective at avoiding layer collapse, though it still fell short of the planted ticket's performance.
- Edge-Popup Limitations: Edge-Popup, designed for finding strong tickets, showed a performance "spike" and subsequent failure at the extreme sparsities where planted tickets reside. An "annealing" schedule improved its performance but did not reach the optimal baseline.
Conclusion and Future Work
The "Plant 'n' Seek" framework provides a clear yardstick for the pruning community. While current benchmarks are lower-dimensional than modern vision tasks, the observed trends—such as layer collapse—align with image-based studies.
Future research should focus on:
- Developing "flow-preserving" pruning algorithms to prevent layer collapse.
- Investigating the specific challenges regression tasks pose for pruners.
- Expanding the framework to complex architectures like Transformers.
By providing a hidden ground truth, this work enables a more rigorous evaluation of whether new pruning methods represent genuine breakthroughs.
Summary updated