The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
By Jonathan Frankle and Michael Carbin (MIT CSAIL)
"Dense, randomly-initialized, feed-forward networks contain subnetworks (winning tickets) that—when trained in isolation—reach test accuracy comparable to the original network in a similar number of iterations."
Why This Matters
Modern deep learning relies on massive, overparameterized networks. We know we can prune these networks after training—often discarding over 90% of the parameters—without losing accuracy.
But this raises a frustrating paradox: If a tiny subnetwork is sufficient for inference, why can't we just train that smaller network from the start?
Historically, trying to train sparse architectures from scratch failed. They learned slower and reached lower accuracy than their dense counterparts. Frankle and Carbin solve this mystery by showing that the architecture itself isn't the problem; it's the initialization.
The Big Idea
Think of initializing a dense neural network as buying millions of lottery tickets. Each ticket is a randomly initialized subnetwork. Because we bought so many, we are virtually guaranteed that at least one subnetwork—the "winning ticket"—is initialized with the perfect combination of weights and connections to learn the task rapidly and effectively.
When we prune a trained network, we are uncovering this winning ticket. If we reset its weights to exactly their original initial values, it trains beautifully in isolation. If we reinitialize it randomly, it fails.
How It Works: Finding the Winning Ticket
To find these elusive winning tickets, the authors use a technique called Iterative Magnitude Pruning (IMP). The steps are mathematically defined as follows:
Interactive Algorithm: Iterative Magnitude Pruning (IMP) Step 1 / 5
1. Random Initialization
Initialize a dense neural network $f(x; \theta_0)$ with random parameters $\theta_0 \sim \mathcal{D}_\theta$. We also create an initial mask $m = 1^{|\theta|}$.
Simulating the "Occam's Hill"
Adjust the percentage of weights remaining to see how a Winning Ticket (original initialization) compares to a Reinitialized Ticket (same structure, random weights).
Key Empirical Findings
The paper tests this hypothesis across various architectures (Lenet, Conv-2/4/6, Resnet-18, VGG-19) on MNIST and CIFAR10.
- The 10-20% Sweet Spot: Winning tickets consistently appear at 10% to 20% of the original network size.
- Faster Learning: Above this size, winning tickets actually learn *faster* and achieve *higher* test accuracy than the original dense network.
- Asymmetry in Weights: Surviving weights tend to develop a distinct bimodal distribution.
Weight Distribution Morphing
As the network is pruned iteratively, the distribution of the surviving initial weights morphs from a standard Gaussian to a bimodal distribution. Drag the slider to see this transition.
Limitations & Open Questions
While groundbreaking, the Lottery Ticket Hypothesis left several open challenges that remain active areas of research:
High Computational Cost
Finding winning tickets requires training, pruning, resetting, and retraining multiple times. This is far more expensive than just training the dense network once.
Scale to Large Datasets
On massive datasets like ImageNet, standard IMP fails unless combined with learning rate warmup or late-resetting (resetting weights to step $k$ instead of step 0).
Glossary
Winning Ticket
A sparse subnetwork that is initialized with weights that allow it to train as fast and effectively as the dense network from which it was derived.
Iterative Magnitude Pruning (IMP)
The algorithm used to find winning tickets by training a network, pruning the smallest weights, resetting the rest, and repeating.
Overparameterization
The practice of training neural networks with far more parameters than necessary to represent the target function, making optimization easier.
Cite this work
@inproceedings{frankle2018lottery,
title={The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks},
author={Jonathan Frankle and Michael Carbin},
booktitle={International Conference on Learning Representations (ICLR)},
year={2019}
}