The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks

By 2018, deep networks were routinely over-parameterized. Research by Han et al. (2015) showed that 90% or more of trained weights could be pruned away using magnitude-based pruning without hurting accuracy. The remaining 10% was enough to represent everything the network had learned.

But there was a catch. If you took that pruned architecture and tried to retrain it from scratch with new random weights, performance collapsed. The pruned structure alone was not enough — it apparently needed the specific weight values that emerged from training the full, unpruned network. Pruning was therefore only a post-training compression trick, not a way to reduce the cost of training itself.

This created a frustrating paradox: we know 90% of parameters are unnecessary after training, but we seem to need them during training. The expensive training run appears to be essential for figuring out which 10% to keep — and then those parameters cannot even be reused from scratch.

Frankle and Carlin asked a different question: what if the pruned network can train from scratch — but only if we give it back its original initial weights, not new random ones?

Their answer is the Lottery Ticket Hypothesis:

A randomly-initialized, dense neural network contains a subnetwork that is initialized such that — when trained in isolation — it can match the test accuracy of the original network after training for at most the same number of iterations.

The intuition comes from lottery tickets. A large network is like buying thousands of tickets: most connections are losers, but some are winners. The winners are connections whose initial weights happen to be positioned in the loss landscape such that gradient descent can carry them to a good solution. The full network succeeds because it contains enough winning tickets. The winning subnetwork, when retrained with those same lucky initial values, still wins.

How do we find winning tickets? The authors propose a four-step process. Start with a dense network $f(x; \theta_0)$ with random initial weights $\theta_0$. First, train it to completion, arriving at final weights $\theta_j$. Second, prune the $p\%$ of weights with the smallest magnitudes — these are the least important connections. Third, create a binary mask $m$ that marks which weights survived. Fourth, and this is the critical step, reset the surviving weights to their original values $\theta_0$, not the trained values. The result is the winning ticket: $f(x; m \odot \theta_0)$.

For one-shot pruning, this is done once. But the authors found better results with iterative pruning: instead of pruning $p\%$ all at once, prune a small fraction (e.g. 20%) per round, retrain, prune again, retrain, and repeat. Each round removes the lowest-magnitude weights from what remains. This gradual approach finds sparser winning tickets than one-shot pruning.

The critical experiment is the comparison between three conditions. First, the winning ticket: the pruned structure retrained with its original initialization $\theta_0$. Second, a random ticket: the same pruned structure but with new random weights. Third, the full unpruned network as a baseline.

The results are striking. Winning tickets at 10–20% of original size match or exceed the full network's accuracy. They also often converge faster — needing fewer training iterations. Random tickets, by contrast, perform substantially worse, especially at higher sparsity levels. This proves that the structure alone is insufficient — the original initialization is essential.

Think of it like a jigsaw puzzle. The pruned structure tells you which pieces you need, but the original initialization tells you which orientation each piece starts in. Without the right starting orientation, even the right pieces cannot be assembled into the correct picture through gradient descent.

One-shot pruning trains the full network once, prunes $p\%$ of weights, and resets. Iterative pruning repeats the cycle in small steps: for example, to reach 90% sparsity with 20% pruning per round, it runs about 10 rounds of train-prune-reset.

Iterative pruning is far more expensive computationally — it requires training the full network many times. But it consistently finds better winning tickets: sparser subnetworks that still match or exceed the original's accuracy. The reason is that each round makes finer-grained decisions about which weights to keep, informed by how the remaining weights interact during training.

This is like sculpting in layers: removing thin shavings each time produces a finer result than hacking away large chunks in a single cut. The sculptor can see the emerging form and adjust each stroke accordingly.

The experiments span fully-connected networks (LeNet on MNIST) and convolutional networks (Conv-2, Conv-4, Conv-6 on CIFAR-10), as well as deeper architectures like VGG-19 and ResNet-18.

On LeNet/MNIST, winning tickets at 21% of original size (79% pruned) matched the full network's 98.5% test accuracy. Even at 3.6% of original size (96.4% pruned), winning tickets reached 98.2% accuracy. The full network converged in about 24,000 iterations; the 21% winning ticket converged in about 17,000 — 30% faster.

On the convolutional architectures for CIFAR-10, winning tickets at 10-20% of original size matched the full network. Deeper networks like Conv-6 showed even more room for pruning, with winning tickets at just 5% of the original size still performing well.

A consistent pattern emerged: winning tickets not only match the full network's final accuracy but often converge in fewer iterations, suggesting they sit on a more favorable region of the loss landscape from the start.

The authors provide an intuitive explanation: winning tickets start in a favorable region of the loss landscape. Their initial weights happen to point in a direction where gradient descent can make rapid progress. Random reinitialization places the weights in an arbitrary position — far from the favorable region — and the sparse network does not have enough redundancy to "find its way" from a poor starting position.

Think of it as navigating a mountain range. The full network (1,000 hikers spread across the mountains) is almost guaranteed to have at least a few hikers near a good path. The winning ticket is those specific hikers starting from their lucky positions. If you moved those same hikers to random new positions, they would likely end up on the wrong side of a ridge with no way across.

The dense network's redundancy serves as an insurance policy during training: even though most parameters end up contributing little, their presence during training helps gradient flow and provides alternative paths through the loss landscape.

The lottery ticket hypothesis reframes over-parameterization as a feature, not a bug. Large networks are not successful despite being over-parameterized — they are successful because they are over-parameterized. More parameters mean more lottery tickets, and more lottery tickets mean a higher chance of containing a winning one.

This also explains why small networks are hard to train from scratch: they have fewer lottery tickets, so the chance of a winning initialization is lower. It is not that small networks cannot learn — it is that they rarely start in a position where gradient descent can find a good solution.

The practical implication is a paradigm shift in how we think about efficiency. Instead of training a big network and then compressing it (train big, prune later), the vision is to identify winning tickets early and train only the sparse subnetwork. The paper shows this is possible in principle, though finding the tickets still requires training the full network first — a limitation that sparked a wave of follow-up research.

The original paper has important limitations. The experiments were limited to small-scale benchmarks — MNIST and CIFAR-10 — with relatively shallow architectures. Later work by Frankle et al. (2019) showed that the hypothesis does not hold as cleanly for deeper networks on ImageNet: winning tickets require "rewinding" to early training weights (not initialization) to succeed, which weakened the original claim.

The cost of finding winning tickets is also a practical barrier. Iterative pruning requires training the full network many times, making it far more expensive than a single training run. The hypothesis tells us winning tickets exist but does not give us an efficient way to find them without the expensive search.

Finally, the paper uses unstructured pruning, which removes individual weights scattered throughout the network. While this achieves high sparsity ratios, unstructured sparsity is difficult to exploit for actual speedups on modern hardware, which prefers regular, structured memory access patterns.