Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient

Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, Dimitris S. Papailiopoulos

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:

  1. 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.
  2. 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.
  3. 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

Abstract

The strong {\it lottery ticket hypothesis} (LTH) postulates that one can approximate any target neural network by only pruning the weights of a sufficiently over-parameterized random network. A recent work by Malach et al. \cite{MalachEtAl20} establishes the first theoretical analysis for the strong LTH: one can provably approximate a neural network of width $d$ and depth $l$, by pruning a random one that is a factor $O(d^4l^2)$ wider and twice as deep. This polynomial over-parameterization requirement is at odds with recent experimental research that achieves good approximation with networks that are a small factor wider than the target. In this work, we close the gap and offer an exponential improvement to the over-parameterization requirement for the existence of lottery tickets. We show that any target network of width $d$ and depth $l$ can be approximated by pruning a random network that is a factor $O(\log(dl))$ wider and twice as deep. Our analysis heavily relies on connecting pruning random ReLU networks to random instances of the \textsc{SubsetSum} problem. We then show that this logarithmic over-parameterization is essentially optimal for constant depth networks. Finally, we verify several of our theoretical insights with experiments.
BibTeX
@inproceedings{pensia2020optimal,
  author = {Ankit Pensia and Shashank Rajput and Alliot Nagle and Harit Vishwakarma and Dimitris S. Papailiopoulos},
  title = {{Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=5xgslXxFGh4},
}
Figure