# Efficient Lottery Ticket Finding: Less Data is More

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 56 references that are in the map.
- First posted on arXiv 6 Jun 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [An Empirical Study of Example Forgetting during Deep Neural Network Learning](https://mlsanity.com/paper/1812.05159/) (2018)
- [Linear Mode Connectivity and the Lottery Ticket Hypothesis](https://mlsanity.com/paper/1912.05671/) (2019)
- [Rigging the Lottery: Making All Tickets Winners](https://mlsanity.com/paper/1911.11134/) (2019)
- [Pruning neural networks without any data by iteratively conserving synaptic flow](https://mlsanity.com/paper/2006.05467/) (2020)
- [The State of Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1902.09574/) (2019)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [Selection via Proxy: Efficient Data Selection for Deep Learning](https://mlsanity.com/paper/1906.11829/) (2019)
- [Scalable Training of Artificial Neural Networks with Adaptive Sparse Connectivity inspired by Network Science](https://mlsanity.com/paper/1707.04780/) (2017)
- [Not All Samples Are Created Equal: Deep Learning with Importance Sampling](https://mlsanity.com/paper/1803.00942/) (2018)
- [The Lottery Ticket Hypothesis for Pre-trained BERT Networks](https://mlsanity.com/paper/2007.12223/) (2020)
- [Comparing Rewinding and Fine-tuning in Neural Network Pruning](https://mlsanity.com/paper/2003.02389/) (2020)
- [Dataset Distillation](https://mlsanity.com/paper/1811.10959/) (2018)
- [Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask](https://mlsanity.com/paper/1905.01067/) (2019)
- [Parameter Efficient Training of Deep Convolutional Neural Networks by Dynamic Sparse Reparameterization](https://mlsanity.com/paper/1902.05967/) (2019)
- [Pruning Neural Networks at Initialization: Why are We Missing the Mark?](https://mlsanity.com/paper/2009.08576/) (2020)
- [What Do Compressed Deep Neural Networks Forget?](https://mlsanity.com/paper/1911.05248/) (2019)
- [Characterising Bias in Compressed Models](https://mlsanity.com/paper/2010.03058/) (2020)
- [Drawing Early-Bird Tickets: Towards More Efficient Training of Deep Networks](https://mlsanity.com/paper/1909.11957/) (2019)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers](https://mlsanity.com/paper/1906.02773/) (2019)
- [SCOP: Scientific Control for Reliable Neural Network Pruning](https://mlsanity.com/paper/2010.10732/) (2020)
- [Stochastic Optimization with Importance Sampling](https://mlsanity.com/paper/1401.2753/) (2014)
- [The Lottery Tickets Hypothesis for Supervised and Self-supervised Pre-training in Computer Vision Models](https://mlsanity.com/paper/2012.06908/) (2020)
- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [Playing the lottery with rewards and multiple languages: lottery tickets in RL and NLP](https://mlsanity.com/paper/1906.02768/) (2019)

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

- [Chasing Sparsity in Vision Transformers: An End-to-End Exploration](https://mlsanity.com/paper/2106.04533/) (2021)
- [Advancing Model Pruning via Bi-level Optimization](https://mlsanity.com/paper/2210.04092/) (2022)
- [Sanity Checks for Lottery Tickets: Does Your Winning Ticket Really Win the Jackpot?](https://mlsanity.com/paper/2107.00166/) (2021)
- [Sparsity Winning Twice: Better Robust Generalization from More Efficient Training](https://mlsanity.com/paper/2202.09844/) (2022)
- [The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networks](https://mlsanity.com/paper/2203.04466/) (2022)
- [Compute-Efficient Deep Learning: Algorithmic Trends and Opportunities](https://mlsanity.com/paper/2210.06640/) (2022)
- [Coarsening the Granularity: Towards Structurally Sparse Lottery Tickets](https://mlsanity.com/paper/2202.04736/) (2022)
- [Exploring Lottery Ticket Hypothesis in Spiking Neural Networks](https://mlsanity.com/paper/2207.01382/) (2022)
- [A Survey of Lottery Ticket Hypothesis](https://mlsanity.com/paper/2403.04861/) (2024)
- [Rethinking Graph Lottery Tickets: Graph Sparsity Matters](https://mlsanity.com/paper/2305.02190/) (2023)
- [Dynamic Sparse Network for Time Series Classification: Learning What to "see''](https://mlsanity.com/paper/2212.09840/) (2022)
- [Most Activation Functions Can Win the Lottery Without Excessive Depth](https://mlsanity.com/paper/2205.02321/) (2022)
- [A Comprehensive Survey on Data-Efficient GANs in Image Generation](https://mlsanity.com/paper/2204.08329/) (2022)
- [Knowledge Condensation Distillation](https://mlsanity.com/paper/2207.05409/) (2022)
- [EXGC: Bridging Efficiency and Explainability in Graph Condensation](https://mlsanity.com/paper/2402.05962/) (2024)
- [You are caught stealing my winning lottery ticket! Making a lottery ticket claim its ownership](https://mlsanity.com/paper/2111.00162/) (2021)
- [Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks](https://mlsanity.com/paper/2207.08629/) (2022)
- [FakeCLR: Exploring Contrastive Learning for Solving Latent Discontinuity in Data-Efficient GANs](https://mlsanity.com/paper/2207.08630/) (2022)
- [Convolutional and Residual Networks Provably Contain Lottery Tickets](https://mlsanity.com/paper/2205.02343/) (2022)
- [Trainability Preserving Neural Pruning](https://mlsanity.com/paper/2207.12534/) (2022)
- [Quarantine: Sparsity Can Uncover the Trojan Attack Trigger for Free](https://mlsanity.com/paper/2205.11819/) (2022)
- [PERP: Rethinking the Prune-Retrain Paradigm in the Era of LLMs](https://mlsanity.com/paper/2312.15230/) (2023)
- [To update or not to update? Neurons at equilibrium in deep models](https://mlsanity.com/paper/2207.09455/) (2022)
- [Dimensionality Reduced Training by Pruning and Freezing Parts of a Deep Neural Network, a Survey](https://mlsanity.com/paper/2205.08099/) (2022)
- [SuperTickets: Drawing Task-Agnostic Lottery Tickets from Supernets via Jointly Architecture Searching and Parameter Pruning](https://mlsanity.com/paper/2207.03677/) (2022)
- [SHRIMP: Sparser Random Feature Models via Iterative Magnitude Pruning](https://mlsanity.com/paper/2112.04002/) (2021)
- [On the Neural Tangent Kernel Analysis of Randomly Pruned Neural Networks](https://mlsanity.com/paper/2203.14328/) (2022)
- [The rise of the lottery heroes: why zero-shot pruning is hard](https://mlsanity.com/paper/2202.12400/) (2022)
- [Speeding up NAS with Adaptive Subset Selection](https://mlsanity.com/paper/2211.01454/) (2022)
- [DSD2: Can We Dodge Sparse Double Descent and Compress the Neural Network Worry-Free?](https://mlsanity.com/paper/2303.01213/) (2023)

## Abstract (arXiv)

The lottery ticket hypothesis (LTH) reveals the existence of winning tickets (sparse but critical subnetworks) for dense networks, that can be trained in isolation from random initialization to match the latter's accuracies. However, finding winning tickets requires burdensome computations in the train-prune-retrain process, especially on large-scale datasets (e.g., ImageNet), restricting their practical benefits. This paper explores a new perspective on finding lottery tickets more efficiently, by doing so only with a specially selected subset of data, called Pruning-Aware Critical set (PrAC set), rather than using the full training set. The concept of PrAC set was inspired by the recent observation, that deep networks have samples that are either hard to memorize during training, or easy to forget during pruning. A PrAC set is thus hypothesized to capture those most challenging and informative examples for the dense model. We observe that a high-quality winning ticket can be found with training and pruning the dense network on the very compact PrAC set, which can substantially save training iterations for the ticket finding process. Extensive experiments validate our proposal across diverse datasets and network architectures. Specifically, on CIFAR-10, CIFAR-100, and Tiny ImageNet, we locate effective PrAC sets at 35.32%~78.19% of their training set sizes. On top of them, we can obtain the same competitive winning tickets for the corresponding dense networks, yet saving up to 82.85%~92.77%, 63.54%~74.92%, and 76.14%~86.56% training iterations, respectively. Crucially, we show that a PrAC set found is reusable across different network architectures, which can amortize the extra cost of finding PrAC sets, yielding a practical regime for efficient lottery ticket finding.