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

Abstract

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.

References in corpus (10)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• Binarized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1
• Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation
• DoReFa-Net: Training Low Bitwidth Convolutional Neural Networks with Low Bitwidth Gradients
• Binary Neural Networks: A Survey
• Incremental Network Quantization: Towards Lossless CNNs with Low-Precision Weights
• Picking Winning Tickets Before Training by Preserving Gradient Flow
• Proving the Lottery Ticket Hypothesis: Pruning is All You Need
• Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection
• Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient

Cited by in corpus (5)

• Pruning Randomly Initialized Neural Networks with Iterative Randomization
• A Winning Hand: Compressing Deep Networks Can Improve Out-Of-Distribution Robustness
• Exact Backpropagation in Binary Weighted Networks with Group Weight Transformations
• Plant 'n' Seek: Can You Find the Winning Ticket?
• On the Existence of Universal Lottery Tickets