Unmasking the Lottery Ticket Hypothesis: What's Encoded in a Winning Ticket's Mask?

Mansheej Paul, Feng Chen, Brett W. Larsen, Jonathan Frankle, Surya Ganguli, Gintare Karolina Dziugaite

The "Lottery Ticket Hypothesis" (LTH) has fascinated deep learning researchers since 2018. It suggests that inside large, overparameterized neural networks, there exist tiny "winning tickets"—sparse subnetworks that, when trained from their original initializations, can match the performance of the full model.

While the algorithm used to find these tickets—Iterative Magnitude Pruning (IMP)—is well-known, why it works has remained a geometric mystery. In this paper, researchers from Stanford, Meta AI, and Google Research "unmask" the mechanics of IMP through the lens of error landscape geometry.

TL;DR

The paper reveals that winning ticket masks work by identifying specific subspaces that intersect "linearly connected" regions of the error landscape. By leveraging the robustness of SGD and the flatness of the loss landscape (quantified by the Hessian), the authors explain why pruning must be iterative and how retraining "resets" the network to allow for even deeper cuts.

What Problem Does This Paper Address?

Finding sparse, efficient networks is crucial for deploying AI on edge devices. IMP is the gold standard for finding these networks, but it is computationally expensive and poorly understood. Specifically, the authors tackle four "foundational puzzles":

  1. Information: What does a mask found at the end of training tell a network at the beginning (the rewind point)?
  2. Extraction: How does Stochastic Gradient Descent (SGD) actually use that mask information?
  3. Iteration: Why can’t we just prune 90% of the weights in one shot? Why must we do it in smaller increments?
  4. Retraining: What is the actual role of the retraining phase between pruning steps?

Methods

The authors investigate these questions by analyzing the geometry of the error landscape. Key techniques include:

  • Linear Mode Connectivity (LMC): Checking if two sets of weights can be connected by a straight line in weight space without the error increasing.
  • LCS-sets (Linearly Connected Sublevel Sets): Defining the "neighborhood" of weights that achieve similar accuracy and are linearly connected.
  • Hessian Analysis: Using the Lanczos algorithm to estimate the "flatness" (eigenvalues) of the error landscape.
  • Subspace Intersection Theory: Applying mathematical frameworks to predict how much a network can be pruned before it "misses" the target region of the landscape.

The study uses standard computer vision benchmarks (CIFAR-10, CIFAR-100, and ImageNet) and modern architectures (ResNet-20, ResNet-18, and ResNet-50) to ensure the findings are robust.

Key Insights and Ideas

  • The Mask as a Subspace Locator: The mask isn't just a list of "important weights." It defines an axial subspace (a slice of the high-dimensional weight space) that is guaranteed to intersect the "mode" (the basin) where the previous, less-sparse solution lived.
Nested subspaces of increasing sparsity intersecting the matching error sublevel set.
  • SGD is Robust to "Kicks": The authors found that at the "rewind point," SGD is remarkably robust. Even if you perturb the weights significantly, as long as you stay within the subspace defined by the mask, SGD will navigate back to the same high-performing region.
  • Flatness Equals Prunability: Magnitude pruning is successful because it implicitly chooses to prune weights along "flat" directions of the error landscape. If you prune along "sharp" directions, the error spikes immediately.
  • The "Re-equilibration" of Weights: Retraining isn't just about recovering accuracy; it's about shifting the weight distribution. It creates a new set of "small weights" that are safe to prune in the next iteration. Without this, the network "runs out" of safe weights to cut.

Key Results

  • Linear Connectivity of Tickets: The researchers show that successive winning tickets (e.g., a ticket at 80% sparsity and one at 64% sparsity) are linearly mode connected. This confirms that IMP is essentially "tunneling" through the same high-performance region of the landscape.
Test error and linear mode connectivity heatmaps across different sparsity levels.
  • Predicting Pruning Limits: Using Hessian eigenvalues, the authors developed a theoretical bound that predicts when pruning will fail. They showed that as a network gets sparser, the landscape gets "sharper," explaining why we must prune more cautiously at high sparsities.
  • Adaptive Pruning Heuristic: Based on their geometric insights, they proposed a simple adaptive rule: prune more aggressively when the landscape is flat (low sparsity) and more gently when it gets sharp (high sparsity). This heuristic reduced the training compute for IMP by roughly 33% on CIFAR-100 without losing accuracy.

Limitations and Future Work

While the paper provides a much-needed theoretical foundation, some gaps remain:

  • Quadratic Assumption: The theory relies on a quadratic approximation of the loss landscape. While this works well in practice, the true landscape of a deep neural network is much more complex.
  • The "Why" of Magnitude Pruning: While they show that magnitude pruning correlates with flat directions, they don't fully explain why the smallest weights happen to live in those flat directions.
  • Algorithmic Efficiency: The adaptive heuristic is a great proof-of-concept, but the authors suggest that even more efficient pruning strategies could be designed by directly exploring these linearly connected subspaces.

By moving the conversation from "which weights to keep" to "which subspaces to navigate," this work provides a clearer map for researchers trying to build the next generation of efficient AI.

Summary updated

Abstract

As neural networks get larger and costlier, it is important to find sparse networks that require less compute and memory but can be trained to the same accuracy as the full network (i.e. matching). Iterative magnitude pruning (IMP) is a state of the art algorithm that can find such highly sparse matching subnetworks, known as winning tickets. IMP iterates through cycles of training, pruning a fraction of smallest magnitude weights, rewinding unpruned weights back to an early training point, and repeating. Despite its simplicity, the principles underlying when and how IMP finds winning tickets remain elusive. In particular, what useful information does an IMP mask found at the end of training convey to a rewound network near the beginning of training? How does SGD allow the network to extract this information? And why is iterative pruning needed, i.e. why can't we prune to very high sparsities in one shot? We investigate these questions through the lens of the geometry of the error landscape. First, we find that—at higher sparsities—pairs of pruned networks at successive pruning iterations are connected by a linear path with zero error barrier if and only if they are matching. This indicates that masks found at the end of training convey to the rewind point the identity of an axial subspace that intersects a desired linearly connected mode of a matching sublevel set. Second, we show SGD can exploit this information due to a strong form of robustness: it can return to this mode despite strong perturbations early in training. Third, we show how the flatness of the error landscape at the end of training limits the fraction of weights that can be pruned at each iteration of IMP. This analysis yields a new quantitative link between IMP performance and the Hessian eigenspectrum. Finally, we show that the role of retraining in IMP is to find a network with new small weights to prune. Overall, these results make progress toward demystifying the existence of winning tickets by revealing the fundamental role of error landscape geometry in the algorithms used to find them.
BibTeX
@inproceedings{paul2023unmasking,
  author = {Mansheej Paul and Feng Chen and Brett W. Larsen and Jonathan Frankle and Surya Ganguli and Gintare Karolina Dziugaite},
  title = {{Unmasking the Lottery Ticket Hypothesis: What's Encoded in a Winning Ticket's Mask?}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=xSsW2Am-ukZ},
}
Figure