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 isolation - reach 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. Techniques for eliminating unnecessary weights from neural networks (pruning) (LeCun et al., 1990; BID17 BID15 Li et al., 2016) can reduce parameter-counts by more than 90% without harming accuracy. Doing so decreases the size BID15 Hinton et al., 2015) or energy consumption (Yang et al., 2017; Molchanov et al., 2016; Luo et al., 2017) of the trained networks, making inference more efficient. However, if a network can be reduced in size, why do we not train this smaller architecture instead in the interest of making training more efficient as well? Contemporary experience is that the architectures uncovered by pruning are harder to train from the start, reaching lower accuracy than the original networks. Consider an example. In Figure 1 , we randomly sample and train subnetworks from a fully-connected network for MNIST and convolutional networks for CIFAR10. Random sampling models the effect of the unstructured pruning used by LeCun et al. (1990) and BID15 . Across various levels of sparsity, dashed lines trace the iteration of minimum validation loss 2 and the test accuracy at that iteration. The sparser the network, the slower the learning and the lower the eventual test accuracy.1 "Training a pruned model from scratch performs worse than retraining a pruned model, which may indicate the difficulty of training a network with a small capacity." (Li et al., 2016 ) "During retraining, it is better to retain the weights from the initial training phase for the connections that survived pruning than it is to re-initialize the pruned layers...gradient descent is able to find a good solution when the network is initially trained, but not after re-initializing some layers and retraining them." BID15 2 As a proxy for the speed at which a network learns, we use the iteration at which an early-stopping criterion would end training. The particular early-stopping criterion we employ throughout this paper is the iteration of minimum validation loss during training. See Appendix C for more details on this choice. Figure 1: The iteration at which early-stopping would occur (left) and the test accuracy at that iteration (right) of the Lenet architecture for MNIST and the Conv-2, Conv-4, and Conv-6 architectures for CIFAR10 (see Figure 2 ) when trained starting at various sizes. Dashed lines are randomly sampled sparse networks (average of ten trials). Solid lines are winning tickets (average of five trials).In this paper, we show that there consistently exist smaller subnetworks that train from the start and learn at least as fast as their larger counterparts while reaching similar test accuracy. Solid lines in Figure 1 show networks that we find. Based on these results, we state the lottery ticket hypothesis. The Lottery Ticket Hypothesis. A randomly-initialized , dense neural network contains a subnetwork that is initialized such that-when trained in isolation-it can match the test accuracy of the original network after training for at most the same number of iterations.More formally, consider a dense feed-forward neural network f (x; θ) with initial parameters θ = θ 0 ∼ D θ . When optimizing with stochastic gradient descent (SGD) on a training set, f reaches minimum validation loss l at iteration j with test accuracy a . In addition, consider training f (x; m θ) with a mask m ∈ {0, 1} |θ| on its parameters such that its initialization is m θ 0 . When optimizing with SGD on the same training set (with m fixed), f reaches minimum validation loss l at iteration j with test accuracy a . The lottery ticket hypothesis predicts that ∃ m for which j ≤ j (commensurate training time), a ≥ a (commensurate accuracy), and m 0 |θ| (fewer parameters).We find that a standard pruning technique automatically uncovers such trainable subnetworks from fully-connected and convolutional feed-forward networks. We designate these trainable subnetworks , f (x; m θ 0 ), winning tickets, since those that we find have won the initialization lottery with a combination of weights and connections capable of learning. When their parameters are randomly reinitialized (f (x; m θ 0 ) where θ 0 ∼ D θ ), our winning tickets no longer match the performance of the original network, offering evidence that these smaller networks do not train effectively unless they are appropriately initialized.Identifying winning tickets. We identify a winning ticket by training a network and pruning its smallest-magnitude weights. The remaining, unpruned connections constitute the architecture of the winning ticket. Unique to our work, each unpruned connection's value is then reset to its initialization from original network before it was trained. This forms our central experiment: Conv-2 Conv-4 Conv-6 Resnet-18 VGG-19 Convolutions 64, 64, pool 64, 64, pool 128, 128, pool 64, 64, pool 128, 128, pool 256, 256, pool 16, 3x[16, 16] 3x [32, 32] 3x [64, 64] 2x64 pool 2x128 pool, 4x256, pool 4x512, pool, 4x512 Pruning Rate fc20% conv10% fc20% conv10% fc20% conv15% fc20% conv20% fc0% conv20% fc0% DISPLAYFORM0 Figure 2: Architectures tested in this paper. Convolutions are 3x3. Lenet is from LeCun et al. (1998) . Conv-2/4/6 are variants of VGG (Simonyan & Zisserman, 2014) . Resnet-18 is from He et al. (2016) . VGG-19 for CIFAR10 is adapted from Liu et al. (2019) . Initializations are Gaussian Glorot BID13 . Brackets denote residual connections around layers.network (smaller size). Down to that size, they meet or exceed the original network's test accuracy (commensurate accuracy) in at most the same number of iterations (commensurate training time).When randomly reinitialized, winning tickets perform far worse, meaning structure alone can not explain a winning ticket's success.The Lottery Ticket Conjecture. Returning to our motivating question, we extend our hypothesis into an untested conjecture that SGD seeks out and trains a subset of well-initialized weights. Dense, randomly-initialized networks are easier to train than the sparse networks that result from pruning because there are more possible subnetworks from which training might recover a winning ticket.Contributions.• We demonstrate that pruning uncovers trainable subnetworks that reach test accuracy comparable to the original networks from which they derived in a comparable number of iterations.• We show that pruning finds winning tickets that learn faster than the original network while reaching higher test accuracy and generalizing better.• We propose the lottery ticket hypothesis as a new perspective on the composition of neural networks to explain these findings.Implications. In this paper, we empirically study the lottery ticket hypothesis. Now that we have demonstrated the existence of winning tickets, we hope to exploit this knowledge to:Improve training performance. Since winning tickets can be trained from the start in isolation, a hope is that we can design training schemes that search for winning tickets and prune as early as possible.Design better networks. Winning tickets reveal combinations of sparse architectures and initializations that are particularly adept at learning . We can take inspiration from winning tickets to design new architectures and initialization schemes with the same properties that are conducive to learning. We may even be able to transfer winning tickets discovered for one task to many others.Improve our theoretical understanding of neural networks. We can study why randomly-initialized feed-forward networks seem to contain winning tickets and potential implications for theoretical study of optimization BID10 and generalization (Zhou et al., 2018; BID0 . Existing work on neural network pruning (e.g., BID15 ) demonstrates that the function learned by a neural network can often be represented with fewer parameters. Pruning typically proceeds by training the original network, removing connections, and further fine-tuning. In effect, the initial training initializes the weights of the pruned network so that it can learn in isolation during fine-tuning. We seek to determine if similarly sparse networks can learn from the start. We find that the architectures studied in this paper reliably contain such trainable subnetworks, and the lottery ticket hypothesis proposes that this property applies in general. Our empirical study of the existence and nature of winning tickets invites a number of follow-up questions.The importance of winning ticket initialization. When randomly reinitialized, a winning ticket learns more slowly and achieves lower test accuracy, suggesting that initialization is important to its success. One possible explanation for this behavior is these initial weights are close to their final values after training-that in the most extreme case, they are already trained. However, experiments in Appendix F show the opposite-that the winning ticket weights move further than other weights. This suggests that the benefit of the initialization is connected to the optimization algorithm, dataset, and model. For example, the winning ticket initialization might land in a region of the loss landscape that is particularly amenable to optimization by the chosen optimization algorithm. Liu et al. (2019) find that pruned networks are indeed trainable when randomly reinitialized, seemingly contradicting conventional wisdom and our random reinitialization experiments. For example, on VGG-19 (for which we share the same setup), they find that networks pruned by up to 80% and randomly reinitialized match the accuracy of the original network. Our experiments in FIG3 confirm these findings at this level of sparsity (below which Liu et al. do not present data). However, after further pruning, initialization matters: we find winning tickets when VGG-19 is pruned by up to 98.5%; when reinitialized, these tickets reach much lower accuracy. We hypothesize that-up to a certain level of sparsity-highly overparameterized networks can be pruned, reinitialized, and retrained successfully; however, beyond this point, extremely pruned, less severely overparamterized networks only maintain accuracy with fortuitous initialization.The importance of winning ticket structure. The initialization that gives rise to a winning ticket is arranged in a particular sparse architecture. Since we uncover winning tickets through heavy use of training data, we hypothesize that the structure of our winning tickets encodes an inductive bias customized to the learning task at hand. BID7 show that the inductive bias embedded in the structure of a deep network determines the kinds of data that it can separate more parameter-efficiently than can a shallow network; although BID7 focus on the pooling geometry of convolutional networks, a similar effect may be at play with the structure of winning tickets, allowing them to learn even when heavily pruned.The improved generalization of winning tickets. We reliably find winning tickets that generalize better, exceeding the test accuracy of the original network while matching its training accuracy. Test accuracy increases and then decreases as we prune, forming an Occam's Hill (Rasmussen & Ghahramani, 2001) where the original, overparameterized model has too much complexity (perhaps overfitting) and the extremely pruned model has too little. The conventional view of the relationship between compression and generalization is that compact hypotheses can better generalize (Rissanen, 1986 ). Recent theoretical work shows a similar link for neural networks, proving tighter generalization bounds for networks that can be compressed further (Zhou et al. (2018) for pruning/quantization and BID0 for noise robustness). The lottery ticket hypothesis offers a complementary perspective on this relationship-that larger networks might explicitly contain simpler representations.Implications for neural network optimization. Winning tickets can reach accuracy equivalent to that of the original, unpruned network, but with significantly fewer parameters. This observation connects to recent work on the role of overparameterization in neural network training. For example, BID10 prove that sufficiently overparameterized two-layer relu networks (with fixed-size second layers) trained with SGD converge to global optima. A key question, then, is whether the presence of a winning ticket is necessary or sufficient for SGD to optimize a neural network to a particular test accuracy. We conjecture (but do not empirically show) that SGD seeks out and trains a well-initialized subnetwork. By this logic, overparameterized networks are easier to train because they have more combinations of subnetworks that are potential winning tickets.
Feedforward neural networks that can have weights pruned after training could have had the same weights pruned before training Shows that there exists sparse subnetworks that can be trained from scratch with good generalization performance and proposes a unpruned, randomly initialized NNs contain subnetworks that can be trained from scratch with similar generalization accuracy. The paper examines the hypothesis that randomly initialized neural networks contain sub-networks that converge equally fast or faster and can reach the same or better classification accuracy