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

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