# Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 57 of its 75 references that are in the map.
- First posted on arXiv 12 Oct 2021.

## Builds on (most cited first, 30 of 57)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Neural Ordinary Differential Equations](https://mlsanity.com/paper/1806.07366/) (2018)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Linear Mode Connectivity and the Lottery Ticket Hypothesis](https://mlsanity.com/paper/1912.05671/) (2019)
- [Rethinking the Value of Network Pruning](https://mlsanity.com/paper/1810.05270/) (2018)
- [Learning Structured Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1608.03665/) (2016)
- [Rigging the Lottery: Making All Tickets Winners](https://mlsanity.com/paper/1911.11134/) (2019)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [The Lottery Ticket Hypothesis for Pre-trained BERT Networks](https://mlsanity.com/paper/2007.12223/) (2020)
- [Variational Dropout Sparsifies Deep Neural Networks](https://mlsanity.com/paper/1701.05369/) (2017)
- [Comparing Rewinding and Fine-tuning in Neural Network Pruning](https://mlsanity.com/paper/2003.02389/) (2020)
- [What's Hidden in a Randomly Weighted Neural Network?](https://mlsanity.com/paper/1911.13299/) (2019)
- [Predicting Parameters in Deep Learning](https://mlsanity.com/paper/1306.0543/) (2013)
- [Network Trimming: A Data-Driven Neuron Pruning Approach towards Efficient Deep Architectures](https://mlsanity.com/paper/1607.03250/) (2016)
- [Learning to Prune Deep Neural Networks via Layer-wise Optimal Brain Surgeon](https://mlsanity.com/paper/1705.07565/) (2017)
- [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)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Drawing Early-Bird Tickets: Towards More Efficient Training of Deep Networks](https://mlsanity.com/paper/1909.11957/) (2019)
- [Designing Energy-Efficient Convolutional Neural Networks using Energy-Aware Pruning](https://mlsanity.com/paper/1611.05128/) (2016)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)

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

- [A Survey on Deep Neural Network Pruning-Taxonomy, Comparison, Analysis, and Recommendations](https://mlsanity.com/paper/2308.06767/) (2023)
- [A Survey of Lottery Ticket Hypothesis](https://mlsanity.com/paper/2403.04861/) (2024)
- [How does unlabeled data improve generalization in self-training? A one-hidden-layer theoretical analysis](https://mlsanity.com/paper/2201.08514/) (2022)
- [On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Exploration](https://mlsanity.com/paper/2310.16173/) (2023)
- [Convolutional and Residual Networks Provably Contain Lottery Tickets](https://mlsanity.com/paper/2205.02343/) (2022)
- [Machine Learning and Deep Learning -- A review for Ecologists](https://mlsanity.com/paper/2204.05023/) (2022)
- [SHRIMP: Sparser Random Feature Models via Iterative Magnitude Pruning](https://mlsanity.com/paper/2112.04002/) (2021)
- [Learning and generalization of one-hidden-layer neural networks, going beyond standard Gaussian data](https://mlsanity.com/paper/2207.03615/) (2022)
- [A Theoretical Understanding of Neural Network Compression from Sparse Linear Approximation](https://mlsanity.com/paper/2206.05604/) (2022)
- [Visualizing the Loss Landscape of Winning Lottery Tickets](https://mlsanity.com/paper/2112.08538/) (2021)
- [i-SpaSP: Structured Neural Pruning via Sparse Signal Recovery](https://mlsanity.com/paper/2112.04905/) (2021)
- [Representation and decomposition of functions in DAG-DNNs and structural network pruning](https://mlsanity.com/paper/2306.09707/) (2023)
- [Non-Convex Optimizations for Machine Learning with Theoretical Guarantee: Robust Matrix Completion and Neural Network Learning](https://mlsanity.com/paper/2306.16557/) (2023)
- [Pruning as a Game: Equilibrium-Driven Sparsification of Neural Networks](https://mlsanity.com/paper/2512.22106/) (2025)

## Abstract (arXiv)

The textitlottery ticket hypothesis (LTH) states that learning on a properly pruned network (the textitwinning ticket) improves test accuracy over the original unpruned network. Although LTH has been justified empirically in a broad range of deep neural network (DNN) involved applications like computer vision and natural language processing, the theoretical validation of the improved generalization of a winning ticket remains elusive. To the best of our knowledge, our work, for the first time, characterizes the performance of training a pruned neural network by analyzing the geometric structure of the objective function and the sample complexity to achieve zero generalization error. We show that the convex region near a desirable model with guaranteed generalization enlarges as the neural network model is pruned, indicating the structural importance of a winning ticket. Moreover, when the algorithm for training a pruned neural network is specified as an (accelerated) stochastic gradient descent algorithm, we theoretically show that the number of samples required for achieving zero generalization error is proportional to the number of the non-pruned weights in the hidden layer. With a fixed number of samples, training a pruned neural network enjoys a faster convergence rate to the desired model than training the original unpruned one, providing a formal justification of the improved generalization of the winning ticket. Our theoretical results are acquired from learning a pruned neural network of one hidden layer, while experimental results are further provided to justify the implications in pruning multi-layer neural networks.