# On the Sparsity of the Strong Lottery Ticket Hypothesis

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 29 references that are in the map.
- First posted on arXiv 18 Oct 2024.

## Builds on (most cited first, 18 of 18)

- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [What's Hidden in a Randomly Weighted Neural Network?](https://mlsanity.com/paper/1911.13299/) (2019)
- [Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask](https://mlsanity.com/paper/1905.01067/) (2019)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient](https://mlsanity.com/paper/2006.07990/) (2020)
- [Logarithmic Pruning is All You Need](https://mlsanity.com/paper/2006.12156/) (2020)
- [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)
- [Why Random Pruning Is All We Need to Start Sparse](https://mlsanity.com/paper/2210.02412/) (2022)
- [A Survey of Lottery Ticket Hypothesis](https://mlsanity.com/paper/2403.04861/) (2024)
- [Most Activation Functions Can Win the Lottery Without Excessive Depth](https://mlsanity.com/paper/2205.02321/) (2022)
- [A General Framework For Proving The Equivariant Strong Lottery Ticket Hypothesis](https://mlsanity.com/paper/2206.04270/) (2022)
- [Convolutional and Residual Networks Provably Contain Lottery Tickets](https://mlsanity.com/paper/2205.02343/) (2022)
- [Plant 'n' Seek: Can You Find the Winning Ticket?](https://mlsanity.com/paper/2111.11153/) (2021)
- [Adaptive Compression in Federated Learning via Side Information](https://mlsanity.com/paper/2306.12625/) (2023)
- [Lottery Tickets with Nonzero Biases](https://mlsanity.com/paper/2110.11150/) (2021)
- [On the Integrality Gap of Binary Integer Programs with Gaussian Data](https://mlsanity.com/paper/2012.08346/) (2020)
- [Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets](https://mlsanity.com/paper/2311.09858/) (2023)

## Built on by (most cited first, 3 of 3)

- [The Strong Lottery Ticket Hypothesis for Multi-Head Attention Mechanisms](https://mlsanity.com/paper/2511.04217/) (2025)
- [Quantization vs Pruning: Insights from the Strong Lottery Ticket Hypothesis](https://mlsanity.com/paper/2508.11020/) (2025)
- [Theoretical Compression Bounds for Wide Multilayer Perceptrons](https://mlsanity.com/paper/2512.06288/) (2025)

## Abstract (arXiv)

Considerable research efforts have recently been made to show that a random neural network N contains subnetworks capable of accurately approximating any given neural network that is sufficiently smaller than N, without any training. This line of research, known as the Strong Lottery Ticket Hypothesis (SLTH), was originally motivated by the weaker Lottery Ticket Hypothesis, which states that a sufficiently large random neural network N contains sparse subnetworks that can be trained efficiently to achieve performance comparable to that of training the entire network N. Despite its original motivation, results on the SLTH have so far not provided any guarantee on the size of subnetworks. Such limitation is due to the nature of the main technical tool leveraged by these results, the Random Subset Sum (RSS) Problem. Informally, the RSS Problem asks how large a random i.i.d. sample Omega should be so that we are able to approximate any number in [-1,1], up to an error of  ε, as the sum of a suitable subset of Omega. We provide the first proof of the SLTH in classical settings, such as dense and equivariant networks, with guarantees on the sparsity of the subnetworks. Central to our results, is the proof of an essentially tight bound on the Random Fixed-Size Subset Sum Problem (RFSS), a variant of the RSS Problem in which we only ask for subsets of a given size, which is of independent interest.