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

arXiv: https://arxiv.org/abs/2006.07990 · HTML: https://mlsanity.com/paper/2006.07990/

## Key facts

- Cited by 81 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jun 2020.

## Built on by (most cited first, 30 of 81)

- [Monarch: Expressive Structured Matrices for Efficient and Accurate Training](https://mlsanity.com/paper/2204.00595/) (2022)
- [Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models](https://mlsanity.com/paper/2112.00029/) (2021)
- [A Winning Hand: Compressing Deep Networks Can Improve Out-Of-Distribution Robustness](https://mlsanity.com/paper/2106.09129/) (2021)
- [Multi-Prize Lottery Ticket Hypothesis: Finding Accurate Binary Neural Networks by Pruning A Randomly Weighted Network](https://mlsanity.com/paper/2103.09377/) (2021)
- [Playing Lottery Tickets with Vision and Language](https://mlsanity.com/paper/2104.11832/) (2021)
- [Recent Advances on Neural Network Pruning at Initialization](https://mlsanity.com/paper/2103.06460/) (2021)
- [The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networks](https://mlsanity.com/paper/2203.04466/) (2022)
- [Rare Gems: Finding Lottery Tickets at Initialization](https://mlsanity.com/paper/2202.12002/) (2022)
- [MixMo: Mixing Multiple Inputs for Multiple Outputs via Deep Subnetworks](https://mlsanity.com/paper/2103.06132/) (2021)
- [GANs Can Play Lottery Tickets Too](https://mlsanity.com/paper/2106.00134/) (2021)
- [Sparse Random Networks for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2209.15328/) (2022)
- [On the Existence of Universal Lottery Tickets](https://mlsanity.com/paper/2111.11146/) (2021)
- [Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammars](https://mlsanity.com/paper/2312.01429/) (2023)
- [Why Random Pruning Is All We Need to Start Sparse](https://mlsanity.com/paper/2210.02412/) (2022)
- [Proving Linear Mode Connectivity of Neural Networks via Optimal Transport](https://mlsanity.com/paper/2310.19103/) (2023)
- [A Survey of Lottery Ticket Hypothesis](https://mlsanity.com/paper/2403.04861/) (2024)
- [Sparse Progressive Distillation: Resolving Overfitting under Pretrain-and-Finetune Paradigm](https://mlsanity.com/paper/2110.08190/) (2021)
- [Most Activation Functions Can Win the Lottery Without Excessive Depth](https://mlsanity.com/paper/2205.02321/) (2022)
- [Pruning Randomly Initialized Neural Networks with Iterative Randomization](https://mlsanity.com/paper/2106.09269/) (2021)
- [A General Framework For Proving The Equivariant Strong Lottery Ticket Hypothesis](https://mlsanity.com/paper/2206.04270/) (2022)
- [On the Surprising Effectiveness of Attention Transfer for Vision Transformers](https://mlsanity.com/paper/2411.09702/) (2024)
- [Convolutional and Residual Networks Provably Contain Lottery Tickets](https://mlsanity.com/paper/2205.02343/) (2022)
- [A Probabilistic Approach to Neural Network Pruning](https://mlsanity.com/paper/2105.10065/) (2021)
- [Masks, Signs, And Learning Rate Rewinding](https://mlsanity.com/paper/2402.19262/) (2024)
- [Provable and Efficient Continual Representation Learning](https://mlsanity.com/paper/2203.02026/) (2022)
- [Mask in the Mirror: Implicit Sparsification](https://mlsanity.com/paper/2408.09966/) (2024)
- [Plant 'n' Seek: Can You Find the Winning Ticket?](https://mlsanity.com/paper/2111.11153/) (2021)
- [Dimensionality Reduced Training by Pruning and Freezing Parts of a Deep Neural Network, a Survey](https://mlsanity.com/paper/2205.08099/) (2022)
- [Why Larger Models Learn More: Effects of Capacity, Interference, and Rare-Task Retention](https://mlsanity.com/paper/2605.29548/) (2026)
- [SHRIMP: Sparser Random Feature Models via Iterative Magnitude Pruning](https://mlsanity.com/paper/2112.04002/) (2021)

## Abstract (arXiv)

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. citeMalachEtAl20 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(d4l2) 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 textscSubsetSum 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.