THE LOTTERY TICKET HYPOTHESIS: FINDING SPARSE, TRAINABLE NEURAL NETWORKS
Neural network pruning techniques can reduce the parameter counts of trained networks by over 90%, decreasing storage requirements and improving computational performance of inference without compromising accuracy. However, contemporary experience is that the sparse architectures produced by pruning are difficult to train from the start, which would similarly improve training performance.
We find that a standard pruning technique naturally uncovers subnetworks whose initializations made them capable of training effectively. Based on these results, we articulate the lottery ticket hypothesis: dense, randomly-initialized, feed-forward networks contain subnetworks (winning tickets) that-when trained in isolationreach test accuracy comparable to the original network in a similar number of iterations. The winning tickets we find have won the initialization lottery: their connections have initial weights that make training particularly effective.
We present an algorithm to identify winning tickets and a series of experiments that support the lottery ticket hypothesis and the importance of these fortuitous initializations. We consistently find winning tickets that are less than 10-20% of the size of several fully-connected and convolutional feed-forward architectures for MNIST and CIFAR10. Above this size, the winning tickets that we find learn faster than the original network and reach higher test accuracy.
(Score raised from 8 to 9 after rebuttal)
The paper examines the hypothesis that randomly initialized (feed-forward) neural networks contain sub-networks that train well in the sense that they converge equally fast or faster and reach the same or better classification accuracy. Interestingly, such sub-networks can be identified by simple, magnitude-based pruning. It is crucial that these sub-networks are initialized with their original initialization values, otherwise they typically fail to be trained, implying that it is not purely the structure of the sub-networks that matters. The paper thoroughly investigates the existence of such “winning-tickets” on MNIST and CIFAR-10 on both, fully connected but also convolutional neural networks. Winning-tickets are found across networks, various optimizers, at different pruning-levels and across various other hyper-parameters. The experiments also show that iterative pruning (with re-starts) is more effective at finding winning-tickets.
The paper adds a novel and interesting angle to the question of why neural networks apparently need to be heavily over-parameterized for training. This question is intriguing and of high importance to further the understanding of how neural networks train. Additionally, the findings might have practical relevance as they might help avoid unnecessary over-parameterization which, in turn, might save use of computational resources and energy. The main idea is simple (which is good) and can be tested with relatively simple experiments (also good). The experiments conducted in the paper are clean (averaging over multiple runs, controlling for a lot of factors) and should allow for easy reproduction but also for clean comparison against future experiments. The experimental section is well executed, the writing is clear and good and related work is taken into account to a sufficient degree. The paper touches upon a very intriguing “feature” of neural networks and, in my opinion, should be relevant to theorists and practitioners across many sub-fields of deep learning research. I therefore vote and argue for accepting the paper for presentation at the conference. The following comments are suggestions to the authors on how to further improve the paper. I do not expect all issues to be addressed in the camera-ready version.
1) The main “weakness” of the paper might be that, while the amount of experiments and controls is impressive, the generality of the lottery ticket hypothesis remains somewhat open. Even when restricting the statement to feed-forward networks only, the networks investigated in the paper are relatively “small” and MNIST and CIFAR-10 bear the risk of finding patterns that do not hold when scaling to larger-scale networks and tasks. I acknowledge and support the author’s decision to have thorough and clean experiments on these small models and tasks, rather than having half-baked results on ImageNet, etc. The downside of this is that the experiments are thus not sufficient to claim (with reasonable certainty) that the lottery ticket hypothesis holds “in general”. The paper would be stronger, if the existence of winning tickets on larger-scale experiments or tasks other than classification were shown - even if these experiments did not have a large number of control experiments/ablation studies.
2)  While the paper shows the existence of winning tickets robustly and convincingly on the networks/tasks investigated, the next important question would be how to systematically and reliably “break” the existence of lottery tickets. Can they be attributed to a few fundamental factors? Are they a consequence of batch-wise, gradient-based optimization, or an inherent feature of neural networks, or is it the loss functions commonly used, …? On page 2, second paragraph, the paper states: ”When randomly reinitialized, our winning tickets no longer match the performance of the original network, explaining the difficulty of training pruned networks from scratch”. I don’t fully agree - the paper certainly sheds some light on the issue, but an actual explanation would result in a testable hypothesis. My comment here is intended to be constructive criticism, I think that the paper has enough “juice” and novelty for being accepted - I am merely pointing out that the overall story is not yet conclusive (and I am aware that it might need several more publications to find these answers).
3) Do the winning tickets generalize across hyper-parameters or even tasks. I.e. if a winning ticket is found with one set of hyper-parameters, but then Optimizer/learning-rate/etc. are changed, does the winning-ticket still lead to improved convergence and accuracy? Same question for data-sets: do winning-tickets found on CIFAR-100 also work for CIFAR-10 and vice versa? If winning-tickets turn out to generalize well, in the extreme this could allow “shipping” each network architecture with a few good winning-tickets, thus making it unnecessary to apply expensive iterative pruning every time. I would not expect generalization across data-sets, but it would be highly interesting to see if winning tickets generalize in any way (after all I am still surprised by how well adversarial examples generalize and transfer).
4) Some things that would be interesting to try:
4a) Is there anything special about the pruned/non-pruned weights at the time of initialization? Did they start out with very small values already or are they all “behind” some (dead) downstream neuron? Is there anything that might essentially block gradient signal from updating the pruned neurons? This could perhaps be checked by recording weights’ “trajectories” during training to see if there is a correlation between the “distance weights traveled” and whether or not they end up in the winning ticket.
4b) Do ARD-style/Bayesian approaches or second-order methods to pruning identify (roughly) the same neurons for pruning?
5) Typo (should be through): “we find winning tickets though a principled search process”
6) For the standard ConvNets I assume you did not use batchnorm. Does batchnorm interfere in any way with the existence of winning tickets? (at least on ResNet they seem to exist with batchnorm as well)