ICLR 2019 • Outstanding Paper Award

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."

Neural Network Pruning Weight Initialization Parameter Efficiency

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|}$.

Weight Matrix Representation

Initialized with random positive and negative weights.

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).

Weights Remaining ($P_m$): 21.1%

1% (Highly Sparse) 100% (Dense)

Notice the performance gap at extreme sparsity:

Winning Ticket

Random Reinit

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.

Pruning Stage: Unpruned (100% Remaining)

100% Remaining 41.1% Remaining 16.8% Remaining 6.9% Remaining

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}
}

Share this Flash Paper