The Lottery Ticket Hypothesis

⚡ Key Takeaways

One-line statement: A randomly-initialized dense neural network contains a sparse subnetwork ("winning ticket") that — when trained in isolation from its original initialization — can match the full network's accuracy in comparable training time. Key result in words: Trainability is not solely a property of architecture; specific initializations of sparse subnetworks are crucial, and they can be discovered by iterative magnitude pruning. Where it applies: Overparameterized deep networks (CNNs, MLPs, transformers), pruning, neural architecture search, sparse training. Who/when: Jonathan Frankle & Michael Carbin (MIT), ICLR 2019; later refined with "rewinding" by Frankle, Dziugaite, Roy & Carbin (2020).

💡 The Core Insight

Dense overparameterized training is, in effect, a parallel search over an astronomically large number of sparse subnetworks, each with its own lucky initialization. Pruning by weight magnitude after training is a cheap way to read off which subnetwork "won the lottery." The winning ticket is the pair (m,θ0)(m, \theta_0) — mask AND initialization — not merely the sparse topology. Resetting the surviving weights to their original random values (or, in deep nets, to values from a slightly later "rewind" point) is what makes the subnetwork trainable; randomly re-rolling those weights destroys it.

Formal Statement

DefinitionWinning Ticket

Let f(x;θ)f(x; \theta) be a network with parameters θ∈Rn\theta \in \mathbb{R}^n, trained from initialization θ0∼Dθ\theta_0 \sim \mathcal{D}_\theta by an optimization algorithm A\mathcal{A} for jj iterations, reaching commensurate test accuracy aa at iteration jj. A winning ticket is a subnetwork f(x;m⊙θ0)f(x; m \odot \theta_0), where m∈{0,1}nm \in \{0,1\}^n is a binary mask and ⊙\odot is the elementwise (Hadamard) product, satisfying:

1
a′≥aandj′≤jat sparsity ∥m∥0≪n,\quad a' \ge a \quad\text{and}\quad j' \le j \quad\text{at sparsity } \|m\|_0 \ll n,

where a′a' is the test accuracy reached by training the masked, reinitialized-to-θ0\theta_0 subnetwork for j′j' iterations.

Derivation hint: This is a definition, not a derived result — aa and jj are measured for the dense net; a′a' and j′j' are measured for the masked net trained in isolation; the inequalities encode "at least as good, at least as fast."

DefinitionIterative Magnitude Pruning (IMP)

The canonical procedure for finding winning tickets. Given a pruning rate p∈(0,1)p \in (0,1) per round and NN rounds: 1. Initialize θ0\theta_0, store it. Set mask m=1m = \mathbf{1}. 2. Train f(x;m⊙θ)f(x; m \odot \theta) to convergence, obtaining θT\theta_T. 3. Prune the pp-fraction of currently unpruned weights with smallest magnitude: update mm to zero them out. 4. Reset surviving weights to their values in θ0\theta_0 (LTH) or in θk\theta_k for small k>0k>0 (rewinding). 5. Repeat from step 2 for NN rounds. After NN rounds the surviving fraction is

2
sN=(1−p)N,\quad s_N = (1-p)^N,

the unpruned weight density.

Derivation hint: Each round multiplies the density by (1−p)(1-p); compounding NN rounds gives the geometric product (1−p)N(1-p)^N.

TheoremLottery Ticket Hypothesis (Frankle–Carbin, 2019)

For dense, randomly-initialized networks trained with SGD on standard vision benchmarks, there exist sparse subnetworks (winning tickets) found by IMP such that, for sparsity levels up to roughly 10–20% of original weights remaining,

3
a′(s)≥adensefor s≳s∗,\quad a'(s) \ge a_{\text{dense}} \quad\text{for } s \gtrsim s^*,

where s∗s^* is a task- and architecture-dependent threshold below which accuracy degrades. The matching subnetwork must use the original initialization; the random-reinitialization control fails:

4
areinit′(s)<aθ0′(s)for s≲0.2.\quad a'_{\text{reinit}}(s) < a'_{\theta_0}(s) \quad\text{for } s \lesssim 0.2.

Derivation hint: This is an empirical theorem (a strongly supported regularity, not a proven mathematical theorem). The inequalities summarize the accuracy-vs-sparsity curves measured across LeNet, Conv-2/4/6, VGG, ResNet; the reinit control isolates the role of θ0\theta_0.

Why It Holds / Derivation

There is no closed-form proof; LTH is an empirical phenomenon with partial theoretical backing. The strongest theoretical result is the Strong Lottery Ticket Hypothesis, which is provable.

TheoremStrong Lottery Ticket Hypothesis — provable form (Malach et al., 2020; Pensia et al., 2020)

A sufficiently overparameterized, randomly-initialized network contains a subnetwork that approximates any target network of bounded width and depth without any training of the surviving weights — pruning alone suffices. Formally, to ϵ\epsilon-approximate a target network with ℓ\ell layers and width dd, it suffices to randomly initialize a network whose width is polylogarithmic in the approximation parameters:

5
widthrandom=O ⁣(dlog⁡dℓϵδ)\quad \text{width}_{\text{random}} = O\!\left(d \log\frac{d\ell}{\epsilon\delta}\right)

with probability ≥1−δ\ge 1-\delta.

Derivation hint: Reduce to approximating a single target weight ww by a subset-sum of random weights; the SUBSET-SUM approximation lemma shows O(log⁡(1/ϵ))O(\log(1/\epsilon)) random values suffice to hit any target in [−1,1][-1,1] to error ϵ\epsilon. Pensia et al. tightened Malach's polynomial overhead to logarithmic via this subset-sum argument.

ProofSketch of the Subset-Sum Construction (Strong LTH)

1. Target. Fix a target weight w∗∈[−1/2,1/2]w^* \in [-1/2, 1/2] to be realized by pruning. 2. Random pool. Draw kk i.i.d. weights X1,…,Xk∼Unif[−1,1]X_1, \dots, X_k \sim \mathrm{Unif}[-1,1]. 3. Subset-sum lemma. With probability ≥1−δ\ge 1-\delta, there exists a subset S⊆{1,…,k}S \subseteq \{1,\dots,k\} with

6
∣w∗−∑i∈SXi∣≤ϵwhenever k=Ω ⁣(log⁡1ϵδ).\quad \left| w^* - \sum_{i\in S} X_i \right| \le \epsilon \quad\text{whenever } k = \Omega\!\left(\log\tfrac{1}{\epsilon\delta}\right).

Derivation hint: This is the random-subset-sum theorem of Lueker (1998); kk i.i.d. uniform draws make every target in an interval reachable up to ϵ\epsilon with high probability, with logarithmic sample complexity. 4. Mask = subset selector. Choosing the mask to keep exactly the weights in SS realizes w∗w^* approximately, with the kept weights at their random values — no gradient training needed. 5. Compose across the network. Apply the construction to each weight of the target network; a two-layer random block simulates one target weight, so doubling depth and inflating width by the logarithmic factor in [5] yields the approximation. □\square

∎
JF
Jonathan Frankle & Michael Carbin
2018–2020

Frankle (then a PhD student) and Carbin (his advisor) at MIT CSAIL noticed that the prevailing wisdom — "you can prune a trained network, but you can't train the pruned network from scratch" — had never been tested with the original initialization restored. Their 2019 ICLR paper "The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks" won a Best Paper award and launched an entire subfield. Frankle's 2020 follow-up introduced rewinding to make the hypothesis hold for large networks (ResNet-50, ImageNet), where resetting all the way to θ0\theta_0 fails. Carbin's broader research program concerns the verifiable and resource-efficient deployment of learned systems.

Building Intuition

🧠 Intuition

Think of the dense network's nn weights as nn scratch-off lottery tickets, each with a random "number" (its initialization). Gradient descent on the dense net is like buying every ticket and seeing which ones grow large (win). The winners — large-magnitude weights — are exactly the ones IMP keeps. Crucially, a winning ticket is the printed number plus the position on the card; if you keep the position (mask) but reprint a new random number (reinitialize), it no longer wins. Overparameterization is buying a huge bundle of tickets: the more you buy, the more likely some sparse subset already sits in a "good basin" of the loss landscape that SGD can ride to high accuracy. The lottery metaphor explains why bigger nets are easier to train: not because the extra capacity is used, but because it raises the probability that a trainable sparse subnetwork is present at initialization.

Figure
Accuracy vs. sparsity: winning tickets (reset to θ₀) vs. random reinitialization controls
Weights remaining (%) — log scale, decreasing → Test accuracy 100 40 10 3 1 dense baseline accuracy winning ticket (reset to θ₀) random reinit control s*

Worked Examples

ExampleIMP Schedule: How Many Rounds to 5% Density?

Given: Per-round pruning rate p=0.20p = 0.20 (prune 20% of surviving weights each round). Target density sN=0.05s_N = 0.05.

Steps:

  • From [2], sN=(1−p)N=0.8Ns_N = (1-p)^N = 0.8^N.
  • Solve 0.8N=0.050.8^N = 0.05:
N=ln⁡0.05ln⁡0.8=−2.9957−0.2231=13.43.N = \frac{\ln 0.05}{\ln 0.8} = \frac{-2.9957}{-0.2231} = 13.43.
  • Round up (you cannot do a fractional round): N=14N = 14.
  • Resulting density: 0.814=0.04400.8^{14} = 0.0440, i.e. 4.40% remaining.

Boxed answer:

N=14 rounds⇒4.40% of weights remain (parameters, dimensionless)\boxed{N = 14 \text{ rounds} \Rightarrow 4.40\% \text{ of weights remain (parameters, dimensionless)}}
ExampleCost of IMP vs. One-Shot Pruning

Given: A network with n=107n = 10^7 parameters; one full training run = T=50T = 50 epochs. One-shot pruning prunes to target density in a single train-prune-retrain pass. IMP uses N=14N = 14 rounds, each requiring a full retraining of TT epochs.

Steps:

  • One-shot total training cost: train once + retrain once =2T=100= 2T = 100 epochs.
  • IMP total cost: initial training is round 1, plus 13 further retrains =14×50=700= 14 \times 50 = 700 epochs.
  • Overhead ratio:
700100=7.0.\frac{700}{100} = 7.0.
  • Surviving parameters at 4.40% density: 0.0440×107=4.40×1050.0440 \times 10^7 = 4.40 \times 10^5 weights.

Boxed answer:

IMP costs 7.0× the compute of one-shot, yielding 4.4×105 surviving parameters\boxed{\text{IMP costs } 7.0\times \text{ the compute of one-shot, yielding } 4.4\times 10^5 \text{ surviving parameters}}

(This compute overhead is why IMP is a research tool, not a deployment-time efficiency method — finding the ticket is expensive even though the ticket itself is cheap.)

Common Misconceptions

⚠️ Common mistake

LTH is not a free lunch for compute. Finding a winning ticket via IMP requires training the dense network multiple times. The sparse network is cheap to deploy but expensive to discover. LTH is a statement about the existence and trainability of sparse subnetworks, not a recipe for cheaper training. "Training a small network from scratch" only works once you already know the mask and initialization — and obtaining those required the full dense training.

⚠️ Common mistake

Resetting to θ0\theta_0 does NOT scale to large networks. The original LTH (reset to the very first initialization) fails for ResNet-50 on ImageNet and other large/SGD-noisy settings. Rewinding to weights at a small iteration kk (e.g., 0.1%–7% into training) is required. This subtlety is essential: the "winning ticket" is robust to a little early training but not to the full randomness of θ0\theta_0 in large regimes.

CounterexampleRandom Reinitialization Breaks the Ticket

Take a winning ticket mask mm found by IMP at 5% density on Conv-6/CIFAR-10. Keep the mask but draw fresh weights θ~0∼Dθ\tilde\theta_0 \sim \mathcal{D}_\theta for the surviving connections. Training f(x;m⊙θ~0)f(x; m \odot \tilde\theta_0) yields markedly lower accuracy and slower convergence than f(x;m⊙θ0)f(x; m \odot \theta_0). This is the decisive control in Frankle–Carbin (2019): it proves the topology alone is insufficient; the privileged initialization carried by θ0\theta_0 is doing real work. A further control — randomly permuting the mask within each layer (preserving per-layer sparsity but destroying the specific connectivity) — also breaks the ticket, showing structure matters too.

Connections

connection

LTH sits at the crossroads of several themes. It refines Neural Network Pruning by adding the rewind/reset step that distinguishes a trainable subnetwork from a merely accurate one. It connects to The Loss Landscape of Neural Networks: winning tickets appear to lie in a connected, low-loss basin (linear mode connectivity), and the "instability analysis" of rewinding measures whether SGD noise keeps the trajectory in one basin. It relates to Overparameterization and the Neural Tangent Kernel, since extreme width is what makes good sparse subnetworks abundant at initialization — though winning tickets operate outside the lazy/NTK regime where weights barely move. The Strong LTH connects to Universal Approximation Theorems via the subset-sum construction, recasting approximation as a selection (masking) problem rather than a weight-fitting problem. Finally it informs Neural Architecture Search, suggesting that search over masks of a fixed dense net is a viable substitute for search over architectures.

Real-World Applications

🔬 Where this appears

Historical Development

⏳ History
- 1989–1993 — Optimal Brain Damage / Surgeon (LeCun; Hassibi & Stork). Foundational pruning: remove low-saliency weights from a trained network. Establishes that small accurate networks exist, but assumes you train dense first.
- 2015 — Han, Mao & Dally, "Deep Compression." Magnitude-based iterative pruning + quantization achieves large compression; cements the belief that pruned nets must be retrained from the trained weights, not from scratch.
- 2018 — Liu et al., "Rethinking the Value of Network Pruning." Argues pruned architectures retrained from scratch can match fine-tuning — foreshadowing the trainability question LTH would sharpen.
- March 2019 — Frankle & Carbin, ICLR. The Lottery Ticket Hypothesis is stated; IMP + reset-to-θ0\theta_0 + the reinit control demonstrated on MNIST/CIFAR. Best Paper award.
- 2019 — Zhou et al., "Deconstructing Lottery Tickets." Introduces supermasks — masks that yield good accuracy with weights at (or near) their random init, without training — precursor to Strong LTH.
- March 2020 — Frankle, Dziugaite, Roy & Carbin, "Linear Mode Connectivity and the Lottery Ticket Hypothesis." Introduces rewinding and instability analysis; makes LTH hold for ResNet-50/ImageNet.
- 2020 — Malach, Yehudai, Shalev-Shwartz & Shamir. Proves the Strong LTH: pruning a random net can approximate any target, no weight training needed.
- 2020 — Pensia et al., "Optimal Lottery Tickets via Subset Sum." Tightens Strong LTH overhead from polynomial to logarithmic via the random subset-sum lemma.
- 2020–2021 — Chen et al., "The Lottery Ticket Hypothesis for Pre-trained BERT" / Renda, Frankle, Carbin "Comparing Rewinding and Fine-tuning." Extends tickets to transformers and shows learning-rate rewinding rivals fine-tuning for pruning.

Subtleties & Limits

open-problem

Why does rewinding work where reset-to-θ0\theta_0 fails? The "instability" hypothesis says a subnetwork becomes a stable ticket once SGD's trajectory commits to a single linearly-connected loss basin; rewinding to iteration kk places the weights past this commitment. A predictive theory of kk (how far to rewind, as a function of architecture, data, and noise) is still missing. Can winning tickets be found without dense training? Pruning-at-initialization methods (SNIP, GraSP, SynFlow) attempt this but generally underperform IMP; SynFlow's "layer-collapse" analysis is partial progress, yet no method reliably matches IMP at high sparsity. Do tickets transfer universally? Cross-task and cross-dataset transfer is real but uneven; the boundary of transferability is uncharted. Is there a generative model of tickets? Whether one can predict the mask from θ0\theta_0 alone, bypassing IMP, is open. Structured vs. unstructured gap: Strong LTH guarantees exist for unstructured masks but theory for hardware-friendly structured tickets is thin. Sample-complexity theory: Beyond the subset-sum bound [5] for the strong version, there is no comparable theory for the original (train-the-ticket) hypothesis explaining the threshold s∗s^* in [3].

See Also

Neural Network Pruning · Strong Lottery Ticket Hypothesis · Overparameterization and the Neural Tangent Kernel · Linear Mode Connectivity · Dynamic Sparse Training · Pruning at Initialization · The Loss Landscape of Neural Networks · Neural Architecture Search