# Multi-Prize Lottery Ticket Hypothesis: Finding Accurate Binary Neural Networks by Pruning A Randomly Weighted Network

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

## Key facts

- Cited by 55 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 55 references that are in the map.
- First posted on arXiv 17 Mar 2021.

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

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [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)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [Energy and Policy Considerations for Deep Learning in NLP](https://mlsanity.com/paper/1906.02243/) (2019)
- [XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks](https://mlsanity.com/paper/1603.05279/) (2016)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Rethinking the Value of Network Pruning](https://mlsanity.com/paper/1810.05270/) (2018)
- [BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://mlsanity.com/paper/1511.00363/) (2015)
- [DoReFa-Net: Training Low Bitwidth Convolutional Neural Networks with Low Bitwidth Gradients](https://mlsanity.com/paper/1606.06160/) (2016)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [LQ-Nets: Learned Quantization for Highly Accurate and Compact Deep Neural Networks](https://mlsanity.com/paper/1807.10029/) (2018)
- [Differentiable Soft Quantization: Bridging Full-Precision and Low-Bit Neural Networks](https://mlsanity.com/paper/1908.05033/) (2019)
- [What's Hidden in a Randomly Weighted Neural Network?](https://mlsanity.com/paper/1911.13299/) (2019)
- [Bi-Real Net: Enhancing the Performance of 1-bit CNNs With Improved Representational Capability and Advanced Training Algorithm](https://mlsanity.com/paper/1808.00278/) (2018)
- [Incremental Network Quantization: Towards Lossless CNNs with Low-Precision Weights](https://mlsanity.com/paper/1702.03044/) (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)
- [Binary Neural Networks: A Survey](https://mlsanity.com/paper/2004.03333/) (2020)
- [Forward and Backward Information Retention for Accurate Binary Neural Networks](https://mlsanity.com/paper/1909.10788/) (2019)
- [Drawing Early-Bird Tickets: Towards More Efficient Training of Deep Networks](https://mlsanity.com/paper/1909.11957/) (2019)
- [Towards Accurate Binary Convolutional Neural Network](https://mlsanity.com/paper/1711.11294/) (2017)
- [Training Binary Neural Networks with Real-to-Binary Convolutions](https://mlsanity.com/paper/2003.11535/) (2020)
- [Training BatchNorm and Only BatchNorm: On the Expressive Power of Random Features in CNNs](https://mlsanity.com/paper/2003.00152/) (2020)
- [Exploring Randomly Wired Neural Networks for Image Recognition](https://mlsanity.com/paper/1904.01569/) (2019)
- [XNOR-Net++: Improved Binary Neural Networks](https://mlsanity.com/paper/1909.13863/) (2019)
- [Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient](https://mlsanity.com/paper/2006.07990/) (2020)
- [Rotated Binary Neural Network](https://mlsanity.com/paper/2009.13055/) (2020)

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

- [A Survey of Quantization Methods for Efficient Neural Network Inference](https://mlsanity.com/paper/2103.13630/) (2021)
- [A Survey on Deep Neural Network Pruning-Taxonomy, Comparison, Analysis, and Recommendations](https://mlsanity.com/paper/2308.06767/) (2023)
- [DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Training](https://mlsanity.com/paper/2310.02025/) (2023)
- [A Winning Hand: Compressing Deep Networks Can Improve Out-Of-Distribution Robustness](https://mlsanity.com/paper/2106.09129/) (2021)
- [Decoding Compressed Trust: Scrutinizing the Trustworthiness of Efficient LLMs Under Compression](https://mlsanity.com/paper/2403.15447/) (2024)
- [Patch-Fool: Are Vision Transformers Always Robust Against Adversarial Perturbations?](https://mlsanity.com/paper/2203.08392/) (2022)
- [A comprehensive review of Binary Neural Network](https://mlsanity.com/paper/2110.06804/) (2021)
- [Rare Gems: Finding Lottery Tickets at Initialization](https://mlsanity.com/paper/2202.12002/) (2022)
- [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)
- [Drawing Robust Scratch Tickets: Subnetworks with Inborn Robustness Are Found within Randomly Initialized Networks](https://mlsanity.com/paper/2110.14068/) (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)
- [Rethinking Graph Lottery Tickets: Graph Sparsity Matters](https://mlsanity.com/paper/2305.02190/) (2023)
- [BiBench: Benchmarking and Analyzing Network Binarization](https://mlsanity.com/paper/2301.11233/) (2023)
- [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)
- [Train Flat, Then Compress: Sharpness-Aware Minimization Learns More Compressible Models](https://mlsanity.com/paper/2205.12694/) (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)
- [Deep learning via message passing algorithms based on belief propagation](https://mlsanity.com/paper/2110.14583/) (2021)
- [Dimensionality Reduced Training by Pruning and Freezing Parts of a Deep Neural Network, a Survey](https://mlsanity.com/paper/2205.08099/) (2022)
- [Successfully Applying Lottery Ticket Hypothesis to Diffusion Model](https://mlsanity.com/paper/2310.18823/) (2023)
- [Equal Bits: Enforcing Equally Distributed Binary Network Weights](https://mlsanity.com/paper/2112.03406/) (2021)
- [Sparse Binary Transformers for Multivariate Time Series Modeling](https://mlsanity.com/paper/2308.04637/) (2023)
- [Signing the Supermask: Keep, Hide, Invert](https://mlsanity.com/paper/2201.13361/) (2022)
- [Survival of the Fittest Representation: A Case Study with Modular Addition](https://mlsanity.com/paper/2405.17420/) (2024)
- [Robust Binary Models by Pruning Randomly-initialized Networks](https://mlsanity.com/paper/2202.01341/) (2022)
- [Finding Everything within Random Binary Networks](https://mlsanity.com/paper/2110.08996/) (2021)
- [Hoyer regularizer is all you need for ultra low-latency spiking neural networks](https://mlsanity.com/paper/2212.10170/) (2022)

## Abstract (arXiv)

Recently, Frankle & Carbin (2019) demonstrated that randomly-initialized dense networks contain subnetworks that once found can be trained to reach test accuracy comparable to the trained dense network. However, finding these high performing trainable subnetworks is expensive, requiring iterative process of training and pruning weights. In this paper, we propose (and prove) a stronger Multi-Prize Lottery Ticket Hypothesis: A sufficiently over-parameterized neural network with random weights contains several subnetworks (winning tickets) that (a) have comparable accuracy to a dense target network with learned weights (prize 1), (b) do not require any further training to achieve prize 1 (prize 2), and (c) is robust to extreme forms of quantization (i.e., binary weights and/or activation) (prize 3). This provides a new paradigm for learning compact yet highly accurate binary neural networks simply by pruning and quantizing randomly weighted full precision neural networks. We also propose an algorithm for finding multi-prize tickets (MPTs) and test it by performing a series of experiments on CIFAR-10 and ImageNet datasets. Empirical results indicate that as models grow deeper and wider, multi-prize tickets start to reach similar (and sometimes even higher) test accuracy compared to their significantly larger and full-precision counterparts that have been weight-trained. Without ever updating the weight values, our MPTs-1/32 not only set new binary weight network state-of-the-art (SOTA) Top-1 accuracy -- 94.8% on CIFAR-10 and 74.03% on ImageNet -- but also outperform their full-precision counterparts by 1.78% and 0.76%, respectively. Further, our MPT-1/1 achieves SOTA Top-1 accuracy (91.9%) for binary neural networks on CIFAR-10. Code and pre-trained models are available at: https://github.com/chrundle/biprop.