The Lottery Ticket Hypothesis

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 Lottery Ticket Hypothesis (LTH) asserts that a dense, randomly-initialized feed-forward network of $n$ parameters contains a subnetwork — identified by a binary pruning mask $m \in {0, 1}^{n}$ applied to the original weights $θ_{0}$ — that can be trained in isolation to reach test accuracy at least as high as the full network, using at most the same number of iterations. The hypothesis matters because it decouples the question of whether a small model can perform a task (long known: yes, via post-hoc pruning) from the question of whether such a small model can be trained from scratch (long believed: no). The surprising empirical fact is that the reset to original initialization is essential: the same sparse connectivity pattern, re-initialized randomly, trains poorly — implying that the mask and the initial values jointly form a privileged "winning ticket." LTH reframes overparameterization as a mechanism that buys many lottery tickets at once, dramatically increasing the chance that gradient descent finds a trainable sparse configuration.

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})$ — 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

Winning Ticket

Let $f (x; θ)$ be a network with parameters $θ \in R^{n}$ , trained from initialization $θ_{0} \sim D_{θ}$ by an optimization algorithm $A$ for $j$ iterations, reaching commensurate test accuracy $a$ at iteration $j$ . A winning ticket is a subnetwork $f (x; m ⊙ θ_{0})$ , where $m \in {0, 1}^{n}$ is a binary mask and $⊙$ is the elementwise (Hadamard) product, satisfying:

a^{'} \geq a and j^{'} \leq j at sparsity ∥ m ∥_{0} ≪ n,

where $a^{'}$ is the test accuracy reached by training the masked, reinitialized-to- $θ_{0}$ subnetwork for $j^{'}$ iterations.

⟳This is a definition, not a derived result —

a

and

j

are measured for the dense net;

a^{'}

and

j^{'}

are measured for the masked net trained in isolation; the inequalities encode "at least as good, at least as fast."

Iterative Magnitude Pruning (IMP)

The canonical procedure for finding winning tickets. Given a pruning rate $p \in (0, 1)$ per round and $N$ rounds:

Initialize $θ_{0}$ , store it. Set mask $m = 1$ .
Train $f (x; m ⊙ θ)$ to convergence, obtaining $θ_{T}$ .
Prune the $p$ -fraction of currently unpruned weights with smallest magnitude: update $m$ to zero them out.
Reset surviving weights to their values in $θ_{0}$ (LTH) or in $θ_{k}$ for small $k > 0$ (rewinding).
Repeat from step 2 for $N$ rounds.

After $N$ rounds the surviving fraction is

s_{N} = (1 - p)^{N},

the unpruned weight density.

⟳Each round multiplies the density by

(1 - p)

; compounding

N

rounds gives the geometric product

(1 - p)^{N}

Lottery 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,

a^{'} (s) \geq a_{dense} for s ≳ s^{*},

where $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:

a_{reinit}^{'} (s) < a_{θ_{0}}^{'} (s) for s ≲ 0.2.

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

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.

Strong 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 $ϵ$ -approximate a target network with $ℓ$ layers and width $d$ , it suffices to randomly initialize a network whose width is polylogarithmic in the approximation parameters:

width_{random} = O (d lo g \frac{d ℓ}{ϵδ})

with probability $\geq 1 - δ$ .

⟳Reduce to approximating a single target weight

w

by a subset-sum of random weights; the SUBSET-SUM approximation lemma shows

O (lo g (1/ ϵ))

random values suffice to hit any target in

[- 1, 1]

to error

ϵ

. Pensia et al. tightened Malach's polynomial overhead to logarithmic via this subset-sum argument.

Sketch of the Subset-Sum Construction (Strong LTH)

Target. Fix a target weight $w^{*} \in [- 1/2, 1/2]$ to be realized by pruning.
Random pool. Draw $k$ i.i.d. weights $X_{1}, \dots, X_{k} \sim Unif [- 1, 1]$ .
Subset-sum lemma. With probability $\geq 1 - δ$ , there exists a subset $S \subseteq {1, \dots, k}$ with

w^{*} - i \in S \sum X_{i} \leq ϵ whenever k = Ω (lo g \frac{1}{ϵδ}) .

⟳This is the random-subset-sum theorem of Lueker (1998);

k

i.i.d. uniform draws make every target in an interval reachable up to

ϵ

with high probability, with logarithmic sample complexity.

Mask = subset selector. Choosing the mask to keep exactly the weights in $S$ realizes $w^{*}$ approximately, with the kept weights at their random values — no gradient training needed.
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. $□$

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}$ fails. Carbin's broader research program concerns the verifiable and resource-efficient deployment of learned systems.

Building Intuition

Think of the dense network's $n$ weights as $n$ 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.

Accuracy vs. sparsity: winning tickets (reset to θ₀) vs. random reinitialization controls

Worked Examples

IMP Schedule: How Many Rounds to 5% Density?

Given: Per-round pruning rate

p = 0.20

(prune 20% of surviving weights each round). Target density

s_{N} = 0.05

. Steps:

From [2], $s_{N} = (1 - p)^{N} = 0. 8^{N}$ .
Solve $0. 8^{N} = 0.05$ :

N = \frac{ln 0.05}{ln 0.8} = \frac{- 2.9957}{- 0.2231} = 13.43.

Round up (you cannot do a fractional round): $N = 14$ .
Resulting density: $0. 8^{14} = 0.0440$ , i.e. 4.40% remaining.

Boxed answer:

N = 14 rounds \Rightarrow 4.40% of weights remain (parameters, dimensionless)

Cost of IMP vs. One-Shot Pruning

Given: A network with

n = 1 0^{7}

parameters; one full training run =

T = 50

epochs. One-shot pruning prunes to target density in a single train-prune-retrain pass. IMP uses

N = 14

rounds, each requiring a full retraining of

T

epochs. Steps:

One-shot total training cost: train once + retrain once $= 2 T = 100$ epochs.
IMP total cost: initial training is round 1, plus 13 further retrains $= 14 \times 50 = 700$ epochs.
Overhead ratio:

\frac{700}{100} = 7.0.

Surviving parameters at 4.40% density: $0.0440 \times 1 0^{7} = 4.40 \times 1 0^{5}$ weights.

Boxed answer:

IMP costs 7.0 \times the compute of one-shot, yielding 4.4 \times 1 0^{5} 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

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. Resetting to $θ_{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

k

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

in large regimes.

Random Reinitialization Breaks the Ticket

Take a winning ticket mask $m$ found by IMP at 5% density on Conv-6/CIFAR-10. Keep the mask but draw fresh weights $\tilde{θ}_{0} \sim D_{θ}$ for the surviving connections. Training $f (x; m ⊙ \tilde{θ}_{0})$ yields markedly lower accuracy and slower convergence than $f (x; m ⊙ θ_{0})$ . This is the decisive control in Frankle–Carbin (2019): it proves the topology alone is insufficient; the privileged initialization carried by $θ_{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

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

Model compression for edge deployment. Winning tickets motivate sparse models for mobile/IoT inference; though IMP itself is expensive, the discovered sparse patterns inform efficient deployment (TensorFlow Model Optimization, NVIDIA's 2:4 structured sparsity).
Pruning research benchmarks. LTH provided the standard rewinding baseline against which all modern pruning methods (SNIP, GraSP, SynFlow, magnitude-after-training) are now compared.
Pretrained transformer pruning. BERT and GPT-family "lottery tickets" have been identified; the matching subnetworks of pretrained language models transfer across downstream tasks (the "task-agnostic ticket"), enabling cheaper fine-tuning.
Sparse training algorithms. Insights from LTH spurred dynamic sparse training (RigL, SET) that aims to train sparse from scratch without the dense-training overhead — directly targeting LTH's compute limitation.
Reinforcement learning and NLP transfer. Winning tickets found on one RL environment or one NLP task have been shown to transfer to related tasks, suggesting tickets capture reusable inductive structure.
Neuroscience-inspired efficiency studies. LTH supports the view that biological-scale sparsity is compatible with high performance, informing analog/neuromorphic hardware co-design where sparse connectivity is native.
Hardware-aware structured sparsity. Block- and channel-level lottery tickets (structured pruning variants) are deployed where unstructured sparsity gives no speedup on dense matrix hardware (GPUs/TPUs).

Historical Development

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

Why does rewinding work where reset-to- $θ_{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

k

places the weights past this commitment. A predictive theory of

k

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

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^{*}

in [3].