Optimal Lottery Tickets via Subset Sum: Logarithmic Over-Parameterization is Sufficient

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

Introduction

The "Strong Lottery Ticket Hypothesis" (LTH) posits that within a large, randomly initialized neural network, there exists a sparse subnetwork that can perform as well as a fully trained model—without any weight updates. This paper provides a groundbreaking theoretical proof that the random source network only needs to be logarithmically wider than the target network to guarantee the existence of such a "winning ticket." This is a massive improvement over previous polynomial bounds and brings theory much closer to empirical observations.

The Problem: Over-Parameterization Gap

Standard deep learning relies on gradient descent to train weights. The LTH, however, suggests that dense, randomly initialized networks contain "winning tickets"—sparse subnetworks that reach the original network's accuracy when trained in isolation. The Strong LTH takes this a step further: it claims no weight training is needed at all. You simply need to find the right weights to keep and prune the rest.

Previous theoretical work proved the Strong LTH but required the random network to be polynomially larger ($O(d^4 l^2)$ wider) than the target. This starkly contrasted with experimental reality, where good subnetworks are found in much smaller models. This paper addresses this gap, asking: How much over-parameterization is actually necessary for these untrained winning tickets to exist?

Methodology: The Subset Sum Insight

The authors bridge the theoretical-empirical gap by connecting neural network pruning to a classic computer science problem: the Subset Sum problem.

Approximating a specific target weight $w^*$ with a single random number requires many samples to get lucky. However, if you can pick a subset of $n$ random numbers and sum them, you can approximate $w^*$ much faster. Using a result from Lueker (1998), the authors show that with only $n = O(\log(1/\epsilon))$ random samples, there exists a subset whose sum is within $\epsilon$ of the target.

Approximating a target weight using Subset Sum in linear and ReLU networks.

To approximate a target network of width $d$ and depth $l$, the authors construct a random network that is twice as deep ($2l$). They use pairs of layers to simulate a single layer of the target:

  1. Expansion: The first layer expands the input into many random values.
  2. Pruning (Subset Selection): The second layer selects a subset of these values to sum up, effectively creating the desired weight.

Because ReLU activations only pass positive values, the authors use the mathematical identity $wx = \sigma(wx) - \sigma(-wx)$ to handle both positive and negative weights, splitting the approximation into two parallel paths.

Key Insights and Results

  • Logarithmic is Sufficient: The jump from polynomial ($d^4$) to logarithmic ($\log d$) over-parameterization reveals that the search space within a random network is exponentially richer than previously thought. The theoretical bound shows a random network of width $O(d \log(dl/\epsilon))$ and depth $2l$ can approximate any target network of width $d$ and depth $l$ within error $\epsilon$.
  • Pruning as Approximation: This work shifts the perspective of pruning from "removing noise" to "active function approximation." Choosing which random weights to keep is akin to digital-to-analog conversion using random weights as bits.
  • Optimality (Lower Bound): The authors prove that a 2-layer network requires at least $\Omega(d \log(1/\epsilon))$ width to approximate certain functions, matching their upper bound's scaling. This means their logarithmic requirement is essentially optimal for constant-depth networks.
  • Empirical Validation: On the MNIST dataset, the authors approximated a 500-hidden-node target network (97.19% accuracy) by selecting subsets from a random network. With only ~21 random coefficients available per target weight, the pruned "untrained" network maintained the full 97.19% accuracy.

Limitations and Future Work

While the theoretical results are strong, practical challenges remain:

  • Computational Complexity: While the existence of the subnetwork is guaranteed, finding it is NP-hard (due to the Subset Sum problem). Experiments required a Mixed Integer Program (MIP) solver, which is computationally expensive for large models.
  • Architecture Scope: The proof focuses on fully connected layers. Extending this formally to Convolutional Neural Networks (CNNs) and Transformers remains for future work.
  • Depth Trade-off: The construction requires the random network to be twice as deep as the target. Whether this depth increase is strictly necessary is an open question.

Summary updated

Abstract

The strong 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. [MYSS20] 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^4 l^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 Subset Sum 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 Subset Sum: Logarithmic Over-Parameterization is Sufficient}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=5xgslXxFGh4},
}
Figure