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.

Advertisement

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.

Advertisement

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.