Research map / Learning theory and algorithms / Sample complexity
On the Sparsity of the Strong Lottery Ticket Hypothesis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves a fixed-size variant of the Random Subset Sum problem (RFSS) with a near-tight bound and uses it to give the first Strong Lottery Ticket results that guarantee subnetwork sparsity for dense and equivariant networks.
Problem
Existing Strong Lottery Ticket Hypothesis results prove that random networks contain subnetworks approximating target networks, but give no guarantee on how sparse those subnetworks are or how overparameterization depends on sparsity.
Approach
Introduces the Random Fixed-Size Subset Sum problem (subsets of exactly k of n random samples), proves an essentially tight bound via a second-moment method for sum-bounded distributions (including Uniform[-1,1]), and plugs it into the SLTH pruning framework to bound overparameterization as a function of density.
Key results
- Proves an essentially tight bound for Random Fixed-Size Subset Sum: n >= c log2(k/eps)/H2(k/n) samples suffice to approximate any z in [-sqrt(k), sqrt(k)] with a size-k subset with constant probability.
- Shows Uniform[-1,1] is sum-bounded, and extends to a corollary giving success probability 1-eps for all targets simultaneously with n = O(log^2(1/eps)/H2(k/n)).
- Derives SLTH sparsity guarantees for dense and equivariant networks and a lower bound matching the required overparameterization up to logarithmic factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require the approximating subset to have fixed size k rather than arbitrary size | Random subset-sum guarantee · RFSS | sample-size bound | Helped |
| Use the RFSS corollary in the pruning construction | Dense neural networks · Dense neural networks | sparsity guarantee | Helped |
| Use the RFSS corollary when pruning equivariant parameters | Equivariant neural networks · Equivariant networks | sparsity guarantee | Helped |
| Replace the full squared-log condition with the simplified condition (ablation) | SSLTH for dense neural networks · Dense neural networks | overparameterization | Helped |
| Amplify the constant success probability to 1-ε | RFSS guarantee for mixture distributions · RFSS | success probability: c_{\text{thm}} -> 1-\varepsilon | Helped |
Limitations
- Only proves existence of winning tickets; no efficient algorithm to find them is provided
- Multidimensional RFSS remains open, so structured pruning sparsity is not covered
- Probability amplification adds an extra log(1/eps) factor relative to the lower bound
Experimental setup
Baselines: Pensia et al. Malach et al.
Builds on: Random Subset Sum problem Pensia et al. SLTH framework Malach et al. SLTH Lottery Ticket Hypothesis
Closest papers by meaning
- Optimal Lottery Tickets via Subset Sum: Logarithmic Over-Parameterization is Sufficient (NeurIPS 2020 · similarity 0.94)
- Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets (NeurIPS 2023 · similarity 0.92)
- Dual Lottery Ticket Hypothesis (ICLR 2022 · similarity 0.91)
- The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks (ICLR 2019 · similarity 0.91)
- Find A Winning Sign: Sign Is All We Need to Win the Lottery (ICLR 2025 · similarity 0.89)
- Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.