Can We Prove the Lottery Ticket Hypothesis for Two-Layer Networks?
1. What LTH says, what is known, and what is missing
The Lottery Ticket Hypothesis (LTH), introduced by Frankle and Carbin in 2019, observes that a large trained network contains a much smaller subnetwork — a winning ticket — which, when trained again from the same initialization, reaches comparable accuracy with far fewer parameters. Three ingredients must be kept separate: the mask defining the subnetwork structure, the initialization (kept or rewound), and the pruning procedure (one-shot or iterative). Later work by Frankle et al. (2020) explained the mechanism through stability to SGD noise: large networks contain many stable solutions, and pruning retains those.
What has been proved is narrow. For linear networks, one-layer networks, or random features, some theoretical results exist under restrictive conditions. Sparsity bounds typically state existence without being constructive. There is no proof for general nonlinear two-layer networks. Pruning in practice remains heuristic: neurons are removed by weight magnitude or movement, with no certificate that the optimum is preserved. Moreover, the cleanest theory for two-layer networks assumes the number of neurons tends to infinity, while real networks are finite, and no quantitative bridge connects the two regimes. Finally, there is no usable notion of “same network”: two networks computing the same function may have completely different weights, so the question “does pruning return the same network” is not even well posed without a strong equivalence concept.
This post does not prove LTH. It asks: if LTH holds for two-layer networks in a certified sense, which steps must the argument go through, which pieces does it use, and what is still missing at each step?
2. Five pieces and their papers
The first piece is mean-field and measure theory, from Mei, Montanari, Nguyen (2018) and Chizat, Bach (2018). As the number of neurons tends to infinity, a two-layer network is described as a probability distribution over neuron parameters, and training converges globally in a suitable sense. This gives the argument an ideal world where the corresponding problem is convex with a global solution, at the price of requiring infinitely many neurons and a global optimum.
The second piece is group lasso and combinatorial blow-up, from Bach (2017) and Bengio et al. (2006). A two-layer network penalized by the variation norm is equivalent to a convex problem over measures. Discretizing over the data samples turns it into a group lasso whose number of groups can grow exponentially. This gives the argument a finite problem where screening applies, at the price of accepting an enormous number of groups or finding a way to avoid enumerating them.
The third piece is safe screening for Beurling-LASSO, developed in the PhD thesis of Tran Thu Le (full title, year, and institution still need to be confirmed). On the space of measures, one can identify in advance regions of neurons whose coefficients are guaranteed to vanish at the optimum, and remove them without changing the solution. This gives the argument certified pruning, at the price of checking a condition over a continuous parameter space or having a sufficiently tight approximate bound.
The fourth piece is connected sublevel sets, from Nguyen (2019) and Freeman, Bruna (2017). For sufficiently wide networks — specifically when the first hidden layer has at least twice as many neurons as samples — the set of weights with loss below a threshold forms a single connected component. This gives the argument a continuous path between representations of the same function, at the price of an extremely strong width condition.
The fifth piece is local to global confluence, from Newman (1942) and Huet (1980). In rewriting theory, a relation that is locally confluent and terminating is globally confluent: every order of application leads to the same final result. This gives the argument order-independence of pruning, at the price of requiring a decreasing quantity that guarantees termination.
The LTH result itself (Frankle and Carbin) is not in this list because it is the destination, not a tool.
3. A possible route and the open questions
3.1 The chain of reasoning
A proof of certified LTH for two-layer networks could proceed in five steps. Step A moves to the convex problem: pieces 1 and 2 let us view the network as a measure over neuron space, whose training problem is convex, and discretization over samples yields a finite problem. Step B identifies which neurons are certainly removed: piece 3 tells us where the support of the optimal measure lies, and neurons outside the support have zero coefficient. Step C shows order-independence: piece 5 says that if pruning is terminating and locally confluent, every order leads to the same final set, so a canonical form exists. Step D connects the original and pruned networks: piece 4 says that two networks with the same function and the same complexity lie in the same connected region, so a continuous path exists between them. Step E concludes: a smaller subnetwork with the same function exists, every pruning order leads to it, and it is a certified winning ticket.
In compact form, the core logic is the following implication. If (i) the convex problem has a global solution, (ii) finite discretization preserves its support, (iii) screening identifies that support, (iv) pruning is terminating and locally confluent, and (v) sublevel sets are connected at the function level, then a certified winning ticket exists, unique up to permutation of neurons.
This is not a theorem. It is a map of the argument: any proof must have this shape, and each hypothesis (i)–(v) is a gap to be closed.
3.2 Open questions at each step
The first open question is how to pass from infinite to finite. Piece 1 holds only as the number of neurons tends to infinity, while real networks are finite. A quantitative bound is needed: how close is the finite-network solution to the ideal one, and how close must it be for the support to be preserved. No such result currently exists for pruning.
The second open question is whether discretization loses neurons. Piece 2 gives a finite problem, but the number of groups can grow exponentially. Is there a discretization that preserves the relevant neurons without enumerating all groups? This is both a theoretical and a computational question.
The third open question is whether screening on the convex solution transfers to the trained network. Piece 3 certifies the support of the convex optimum, but the real network is trained by gradient descent, not by solving that convex problem. How far apart are the two solutions, and does the screening criterion computed from the convex solution still hold for the trained one? A quantitative comparison is needed.
The fourth open question is how to guarantee that pruning terminates. Piece 5 requires a decreasing quantity, but removing a neuron with zero coefficient decreases nothing, since that neuron contributes nothing. A suitable decreasing quantity for certified pruning must be constructed; none exists today.
The fifth open question is whether connectedness at the function level descends to the weight level. Piece 4 concerns connectedness of the low-loss weight set, but two networks computing the same function may lie in different branches of weight space, unreachable without crossing a high-loss region. A sufficiently strong equivalence notion is needed so that same function implies same connected region, or one must accept that LTH holds at the function level but not at the mask level.
3.3 What is missing, and what must be checked first
From the five questions, three major gaps emerge. The first is a bridge from the infinite-neuron theory to finite networks, strong enough to preserve support; this is the hardest gap and lies at the center of the whole program. The second is a decreasing quantity for certified pruning; without it, the confluence piece does not apply. The third is a sufficiently strong equivalence notion, invariant under pruning, not requiring identical weights, and strong enough to imply uniqueness of the canonical form.
Beyond these three gaps, one thing must be checked before any gluing attempt: whether the screening in Tran Thu Le’s thesis actually provides a checkable bound over the continuous parameter space, and whether it transfers to a pruning criterion for trained networks. If yes, piece 3 is stronger than assumed here; if not, it remains a theoretical screening result.
3.4 Conclusion
The five pieces match in form: they speak about the same object and use the same language. But whether they glue together is unknown, because the five open questions above have no answers yet. This post does not promise a proof of LTH. It only draws a map: anyone who wants to prove it must go through these five steps, and must resolve these five questions first.
