This paper, presented at NeurIPS 2020, provides a major theoretical leap in our understanding of why neural network pruning works so well. By drawing a clever connection to a classic problem in computer science—the Subset Sum problem—the authors prove that we can find "winning tickets" in random networks that are only slightly larger than the target model.
TL;DR
The authors prove a "strong" version of the Lottery Ticket Hypothesis: you can approximate any target neural network simply by pruning a random one that is only logarithmically wider. This replaces previous theories requiring massive polynomial over-parameterization and provides a near-optimal theoretical bound for network pruning.
What Problem Does This Paper Address?
The Lottery Ticket Hypothesis (LTH) suggests that dense, randomly initialized networks contain sparse subnetworks (winning tickets) that, when trained in isolation, can match the performance of the original dense network. A "stronger" version of this hypothesis claims you don't even need to train the weights—you can just prune a large enough random network to find a subnetwork that already approximates the target function.
Prior to this paper, the best theoretical proof for the "strong LTH" required the random network to be polynomially wider than the target (e.g., $O(d^4)$ or $O(d^2)$ wider). This was a problem because it didn't match reality: in practice, researchers find winning tickets in networks that are only a small factor wider than the target. This paper closes that gap, proving that a logarithmic factor $O(\log(dl))$ is sufficient.
Methods
The core innovation is re-framing pruning as a Subset Sum problem.
In the Subset Sum problem, given a set of random numbers, you want to find a subset that sums up to a specific target value. A known result by Lueker (1998) shows that if you have $n = O(\log(1/\epsilon))$ random samples, you can find a subset that sums to a target value within an error of $\epsilon$ with high probability.
The authors apply this logic to neural network weights:
- Weight Approximation: Instead of trying to find a single random weight that matches a target weight (which is hard), they look for a subset of random weights that sum up to the target weight.
- ReLU Construction: Since standard pruning just turns weights on or off (1 or 0), they use a two-layer ReLU structure to mimic this summation. They use the identity $wx = \sigma(wx) - \sigma(-wx)$ to handle both positive and negative target weights.
- Layer-wise Approximation: They show that if you can approximate every weight in a layer using this subset-sum approach, you can approximate the entire layer, and eventually the entire network, while keeping the error propagation under control.
Datasets
The authors primarily focus on theoretical proofs, but they verify their insights using:
- MNIST: Used to benchmark the performance of their Subset Sum approximation and pruning structures (like the "edge-popup" algorithm).
Key Insights and Ideas
- Logarithmic is Enough: The jump from polynomial ($d^4$) to logarithmic ($\log d$) over-parameterization is an exponential improvement. It explains why we find good subnetworks in relatively small models.
- The Power of Sums: Pruning isn't just about "selecting the best weights"; it's about the combinatorial power of selecting groups of weights. This is why a wider network offers so many more "functional" possibilities.
- Theoretical Optimality: The authors don't just provide an upper bound; they provide a lower bound (Theorem 2). They show that for constant-depth networks, you must have at least $\Omega(d \log(1/\epsilon))$ width to guarantee an approximation. This means their result is essentially as good as it can get.
- Pruning as Training: This reinforces the idea that for very wide networks, the "training" process could theoretically be replaced by a "searching" process (pruning).
Key Results
- The Main Theorem: A random network with width $O(d \log(dl/\epsilon))$ and depth $2l$ can approximate any target network of width $d$ and depth $l$ within error $\epsilon$.
- Empirical Validation: On MNIST, they approximated a 500-hidden-node target network (97.19% accuracy) by solving the Subset Sum problem for every weight. Using only $n \approx 21$ random coefficients per target weight, the pruned network maintained the exact same 97.19% accuracy without any weight training.
- Lower Bound: They proved that any random network must have at least $\Omega(d^2 \log(1/\epsilon))$ total parameters to approximate a linear mapping, which translates to the logarithmic width requirement.
Limitations and Future Work
- Computational Complexity: While the existence of these tickets is proven, finding them is still hard. The Subset Sum problem is NP-hard. While the authors used a Mixed Integer Program (MIP) solver for their experiments, this doesn't scale easily to billion-parameter models like GPT or ResNet-101.
- Architecture Scope: The proof is currently tailored to fully connected ReLU networks. Extending this to convolutional layers or attention mechanisms is a logical next step.
- Initialization Distributions: While the proof works for a broad class of distributions, it relies on the distribution having a uniform component. Exploring how different initialization schemes (like Xavier or Kaiming) affect these bounds in practice remains an open area.
Summary updated