The lottery ticket hypothesis is usually told as a story about training. This piece tells the mathematical version. There is a stronger, more surprising claim hiding underneath: a large enough randomly initialized network already contains a subnetwork that computes the function you want — no gradient steps required — and you can reach it by pruning alone. That is the strong lottery ticket hypothesis, and unlike the original it has been proved. We build it from first principles: what a subnetwork is formally (a binary mask over the weights), the Malach et al. approximation theorem and its single-weight gadget, the subset-sum lemma that makes the overparameterization only logarithmic, why pruning is best read as a discrete optimization problem, how magnitude pruning falls out as a first-order saliency criterion, and the characteristic shape of the sparsity–accuracy curve. Rigor and intuition, aimed at anyone shipping a sparse small model on a CPU.
Weak ticket, strong ticket
The original (weak) lottery ticket hypothesis says: inside a dense randomly initialized network there is a sparse subnetwork — a winning ticket — that, trained in isolation from the same initialization, matches the dense network’s accuracy in comparable steps. The load-bearing phrase is ‘trained in isolation.’ The ticket still has to learn; the claim is only that the sparse mask plus its lucky initial values is a viable starting point.
The strong lottery ticket hypothesis (strong LTH) removes the training entirely. It claims that a sufficiently over-parameterized random network already contains a subnetwork that approximates the target function at initialization, so pruning — deciding which weights to keep — is the only operation you perform. No weight is ever updated. This is a far bolder statement: it turns ‘training’ into ‘search over masks,’ and it is the version that admits a clean proof. The rest of this article is about that proof and its consequences.
A subnetwork is a mask
To reason formally, fix the vocabulary. Let a network with weights w ∈ ℝ^d compute a function F(x; w). A subnetwork is not a smaller architecture — it is the same architecture with some weights forced to zero. Encode that as a binary mask m ∈ {0,1}^d, and the pruned network computes F(x; m ⊙ w), where ⊙ is the elementwise (Hadamard) product.
This reframing is the whole game. The weights w are drawn once, at random, and frozen. The only free variable is the mask m — one of 2^d possible binary vectors. Sparsity is just the fraction of zeros, s = 1 − (∑_i m_i)/d. Strong LTH then reads as an existence claim about masks: for a random w, there exists an m making F(·; m ⊙ w) close to the target. ‘Learning by pruning’ is exactly the search for that m.
The Malach approximation theorem
Malach, Yehudai, Shalev-Shwartz and Shamir (2020), in ‘Proving the Lottery Ticket Hypothesis: Pruning is All You Need,’ made the strong form a theorem. Informally: let the target be any ReLU network F of depth ℓ and width n with weights bounded by 1. Take a randomly initialized network G of depth 2ℓ and width polynomial in (n, ℓ, 1/ε, log(1/δ)). Then with probability at least 1 − δ there is a mask m such that
sup_x | G(x; m ⊙ w) − F(x) | ≤ ε.Read that carefully: no entry of w is ever trained. The random network is roughly twice as deep and polynomially wider than the target, and pruning alone recovers the target to arbitrary accuracy. So over-parameterization is not merely helpful for optimization — it is sufficient for expressivity by masking. The proof reduces the whole theorem to one primitive: approximating a single weighted connection.
The single-weight gadget
Everything rests on approximating one scalar operation, x → w* · x for a target weight w* ∈ [−1, 1], using only frozen random weights and a mask. The ReLU identity does the structural work: any linear map splits as w*·x = w*·ReLU(x) − w*·ReLU(−x), which is why the construction needs to double the depth — one extra ReLU layer to realize each target layer as a difference of rectified parts.
Now the magnitude. Give the gadget k parallel random neurons whose weights X_1, …, X_k are i.i.d. Instead of tuning any weight to equal w*, we select a subset of these neurons — keep some, mask the rest — so that the kept weights sum to approximately w*. Choosing the subset is choosing the mask. The target weight is thus synthesized, not stored: a value the random draw never produced emerges from adding up a hand-picked handful of the values it did produce. All that remains is to show such a subset almost always exists.
The subset-sum lemma, and why width is only logarithmic
That existence question is exactly the random subset-sum problem, and it is what Pensia et al. (2020) used to sharpen Malach’s result. The lemma: if X_1, …, X_k are i.i.d. uniform on [−1, 1], then for any target w* ∈ [−1, 1] there exists a subset S with |∑_{i∈S} X_i − w*| ≤ ε, with high probability, once k = O(log(1/ε)).
The intuition is a counting argument: k weights generate 2^k distinct subset sums, and those sums scatter densely across their range. To place one within ε of every target you need roughly 2^k ≳ 1/ε, i.e. k ≈ log_2(1/ε). Worked example: draw {0.31, −0.12, 0.44, 0.08, −0.27} and target w* = 0.60. The subset {0.31, 0.44, −0.12, 0.08} sums to 0.71; dropping 0.08 gives 0.63; swapping in −0.27 to get {0.44, 0.31, −0.12} = 0.63 is already within 0.03. This log(1/ε) cost per weight is why the network need only be logarithmically, not polynomially, wider.
Pruning is optimization
Once weights are frozen, learning is a search over the discrete cube {0,1}^d. Formally you are solving
minimize_over_m L( F(·; m ⊙ w) )
subject to ∑_i m_i ≤ (1 − s) · d (a sparsity budget)This is a genuine combinatorial optimization problem, and a hard one — 2^d candidates, and the loss is not a nice function of the discrete mask. The strong-LTH theorems prove the feasible set is non-empty (a good mask exists); they do not hand you an efficient algorithm to find it. In practice you relax the discreteness: attach a real-valued score s_i to each weight and keep the top fraction by score. The edge-popup algorithm learns those scores by straight-through gradients while the weights stay fixed — gradient descent on what to keep rather than on the weights themselves. Magnitude pruning is the same idea with a fixed, hand-chosen score.
Magnitude pruning as a saliency criterion
Why is ‘delete the smallest weights’ a principled score rather than folklore? Define a weight’s saliency as the loss increase from zeroing it. A second-order Taylor expansion around the current weights gives
ΔL_i ≈ −(∂L/∂w_i)·w_i + ½ H_ii · w_i^2 + …where H_ii is a diagonal entry of the Hessian. At a converged minimum the gradient ∂L/∂w_i ≈ 0, so the first-order term vanishes and the leading cost of removing weight i is ½ H_ii w_i^2. That is the Optimal Brain Damage criterion. Magnitude pruning is its cheap approximation: assume the curvature H_ii is roughly uniform across weights, and saliency reduces to w_i^2 — so ranking by |w_i| and dropping the smallest removes the least-costly connections first. The approximation is crude (curvature is not uniform) but astonishingly effective, which is why |w| remains the default saliency signal.
The sparsity–accuracy tradeoff curve
Plot accuracy against sparsity s and a robust shape appears: a long flat plateau followed by a sharp cliff. Up to surprisingly high sparsity the pruned network holds its accuracy; past a critical point it collapses. It is often cleaner to plot against the compression ratio C = 1/(1 − s): 90% sparsity is C = 10×, 99% is 100×.
Illustrative numbers: a dense model at 92.0% might sit at 91.6% after pruning to 90% sparsity, 90.3% at 95%, then knee downward — 86% at 98% and near-random by 99.5%. The plateau is the region where a winning ticket still lives inside the surviving weights; the cliff is where the mask has removed capacity the function genuinely needs. Iterative pruning (prune a little, recover, repeat) pushes the cliff rightward compared to one-shot pruning, because each round re-ranks saliencies on the already-sparse network instead of trusting a single dense snapshot.
What this buys a CPU small model
On a CPU the payoff is concrete but conditional. Unstructured magnitude pruning — the kind the theory is about — scatters zeros arbitrarily, and a generic dense GEMM kernel still touches every entry, so a 90%-sparse weight matrix does not automatically run 10× faster. You need a sparse kernel (CSR/CSC formats, or blocked storage) that skips zeros, and those pay off reliably only above roughly 80–90% sparsity, where the bookkeeping overhead is finally outweighed.
The unconditional win is memory: a sparse format stores only nonzeros plus indices, shrinking the model’s footprint and its bandwidth demand — and for the memory-bound matrix-vector products of single-stream CPU inference, bandwidth is latency. This is also why structured sparsity (dropping whole rows, heads, or channels) is often preferred in deployment: it yields smaller dense tensors that existing kernels accelerate directly, trading some of the theory’s reach for hardware-friendliness.
What the theory does and does not promise
Keep the guarantees honest. First, the strong-LTH theorems are existence results: they prove a good mask exists in a wide enough random net, not that magnitude pruning or edge-popup will find it. The search is NP-hard in general; practice relies on greedy heuristics that usually, not always, land near a winning ticket.
Second, mind the overparameterization. ‘Logarithmically wider’ still means the random host must be meaningfully larger than the target — you cannot prune a network down past the capacity its task actually requires and expect the plateau to hold. Third, the clean theorems assume ReLU nets with bounded weights; transformer blocks add attention, softmax, and normalization, so treat the results as guiding intuition, not a literal recipe. Finally, magnitude as saliency inherits the uniform-curvature assumption: it can prune a small-magnitude weight that nonetheless sits on a high-curvature direction and hurts more than its size suggests. The theory tells you a ticket is there; finding and exploiting it stays an engineering problem.
½ H_ii w_i^2 collapsed to w_i^2 under uniform-curvature assumptions. The sparsity–accuracy curve rewards this with a long plateau before a cliff. But the proofs are existence results on ReLU nets, not algorithms — and on a CPU the guaranteed win is memory and bandwidth, with speed arriving only through sparse or structured kernels.