The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks — part 1/6
Cleaned-text code points [0, 15390). Bibliography omitted here; source.md includes it.
# The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
###### Abstract
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.
## 1 Introduction
Techniques for eliminating unnecessary weights from neural networks ( pruning ) ( LeCun et al., 1990 ; Hassibi & Stork, 1993 ; Han et al., 2015 ; Li et al., 2016 ) can reduce parameter-counts by more than 90% without harming accuracy. Doing so decreases the size ( Han et al., 2015 ; 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. 1 1 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.” ( Han et al., 2015 )
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 Han et al. (2015) . Across various levels of sparsity, dashed lines trace the iteration of minimum validation loss 2 2 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. and the test accuracy at that iteration. The sparser the network, the slower the learning and the lower the eventual test accuracy.
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 , θ ) f(x;\theta) with initial parameters θ = θ 0 ∼ 𝒟 θ \theta=\theta_{0}\sim\mathcal{D}_{\theta} . When optimizing with stochastic gradient descent (SGD) on a training set, f f reaches minimum validation loss l l at iteration j j with test accuracy a a . In addition, consider training f ( x , m ⊙ θ ) f(x;m\odot\theta) with a mask m ∈ { 0 , 1 } | θ | m\in\{0,1\}^{|\theta|} on its parameters such that its initialization is m ⊙ θ 0 m\odot\theta_{0} . When optimizing with SGD on the same training set (with m m fixed), f f reaches minimum validation loss l ′ l^{\prime} at iteration j ′ j^{\prime} with test accuracy a ′ a^{\prime} . The lottery ticket hypothesis predicts that ∃ m \exists~m for which j ′ ≤ j j^{\prime}\leq j ( commensurate training time ), a ′ ≥ a a^{\prime}\geq a ( commensurate accuracy ), and ∥ m ∥ 0 ≪ | θ | \lVert m\rVert_{0}\ll|\theta| ( 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 ) f(x;m\odot\theta_{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 ′ ) f(x;m\odot\theta^{\prime}_{0}) where θ 0 ′ ∼ 𝒟 θ \theta^{\prime}_{0}\sim\mathcal{D}_{\theta} ), 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: 1. Randomly initialize a neural network f ( x , θ 0 ) f(x;\theta_{0}) (where θ 0 ∼ 𝒟 θ \theta_{0}\sim\mathcal{D}_{\theta} ).
2. Train the network for j j iterations, arriving at parameters θ j \theta_{j} .
3. Prune p % p\% of the parameters in θ j \theta_{j} , creating a mask m m .
4. Reset the remaining parameters to their values in θ 0 \theta_{0} , creating the winning ticket f ( x , m ⊙ θ 0 ) f(x;m\odot\theta_{0}) .
As described, this pruning approach is one-shot : the network is trained once, p % p\% of weights are pruned, and the surviving weights are reset. However, in this paper, we focus on iterative pruning , which repeatedly trains, prunes, and resets the network over n n rounds; each round prunes p 1 n % p^{\frac{1}{n}}\% of the weights that survive the previous round. Our results show that iterative pruning finds winning tickets that match the accuracy of the original network at smaller sizes than does one-shot pruning.
Results. We identify winning tickets in a fully-connected architecture for MNIST and convolutional architectures for CIFAR10 across several optimization strategies (SGD, momentum, and Adam) with techniques like dropout, weight decay, batchnorm, and residual connections. We use an unstructured pruning technique, so these winning tickets are sparse. In deeper networks, our pruning-based strategy for finding winning tickets is sensitive to the learning rate: it requires warmup to find winning tickets at higher learning rates. The winning tickets we find are 10-20% (or less) of the size of the original 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 cannot 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 ( Du et al., 2019 ) and generalization ( Zhou et al., 2018 ; Arora et al., 2018 ) .
## 2 Winning Tickets in Fully-Connected Networks
In this Section, we assess the lottery ticket hypothesis as applied to fully-connected networks trained on MNIST. We use the Lenet-300-100 architecture ( LeCun et al., 1998 ) as described in Figure 2 . We follow the outline from Section 1: after randomly initializing and training a network, we prune the network and reset the remaining connections to their original initializations. We use a simple layer-wise pruning heuristic: remove a percentage of the weights with the lowest magnitudes within each layer (as in Han et al. (2015) ). Connections to outputs are pruned at half of the rate of the rest of the network. We explore other hyperparameters in Appendix G , including learning rates, optimization strategies (SGD, momentum), initialization schemes, and network sizes.
Notation. P m = ∥ m ∥ 0 | θ | P_{m}=\frac{\lVert m\rVert_{0}}{|\theta|} is the sparsity of mask m m , e.g., P m = 25 % P_{m}=25\% when 75% of weights are pruned.
Iterative pruning. The winning tickets we find learn faster than the original network. Figure 3 plots the average test accuracy when training winning tickets iteratively pruned to various extents. Error bars are the minimum and maximum of five runs. For the first pruning rounds, networks learn faster and reach higher test accuracy the more they are pruned (left graph in Figure 3 ). A winning ticket comprising 51.3% of the weights from the original network (i.e., P m = 51.3 % P_{m}=51.3\% ) reaches higher test accuracy faster than the original network but slower than when P m = 21.1 % P_{m}=21.1\% . When P m < 21.1 % P_{m}<21.1\% , learning slows (middle graph). When P m = 3.6 % P_{m}=3.6\% , a winning ticket regresses to the performance of the original network. A similar pattern repeats throughout this paper.
Figure 4 a summarizes this behavior for all pruning levels when iteratively pruning by 20% per iteration (blue). On the left is the iteration at which each network reaches minimum validation loss (i.e., when the early-stopping criterion would halt training) in relation to the percent of weights remaining after pruning; in the middle is test accuracy at that iteration. We use the iteration at which the early-stopping criterion is met as a proxy for how quickly the network learns.
The winning tickets learn faster as P m P_{m} decreases from 100% to 21%, at which point early-stopping occurs 38 % 38\% earlier than for the original network. Further pruning causes learning to slow, returning to the early-stopping performance of the original network when P m = 3.6 % P_{m}=3.6\% . Test accuracy increases with pruning, improving by more than 0.3 percentage points when P m = 13.5 % P_{m}=13.5\% ; after this point, accuracy decreases, returning to the level of the original network when P m = 3.6 % P_{m}=3.6\% .
At early stopping, training accuracy (Figure 4 a, right) increases with pruning in a similar pattern to test accuracy, seemingly implying that winning tickets optimize more effectively but do not generalize better. However, at iteration 50,000 (Figure 4 b), iteratively-pruned winning tickets still see a test accuracy improvement of up to 0.35 percentage points in spite of the fact that training accuracy reaches 100% for nearly all networks (Appendix D , Figure 12 ). This means that the gap between training accuracy and test accuracy is smaller for winning tickets, pointing to improved generalization.
Random reinitialization. To measure the importance of a winning ticket’s initialization, we retain the structure of a winning ticket (i.e., the mask m m ) but randomly sample a new initialization θ 0 ′ ∼ 𝒟 θ \theta^{\prime}_{0}\sim\mathcal{D}_{\theta} . We randomly reinitialize each winning ticket three times, making 15 total per point in Figure 4 . We find that initialization is crucial for the efficacy of a winning ticket. The right graph in Figure 3 shows this experiment for iterative pruning. In addition to the original network and winning tickets at P m = 51 % P_{m}=51\% and 21 % 21\% are the random reinitialization experiments. Where the winning tickets learn faster as they are pruned, they learn progressively slower when randomly reinitialized.
The broader results of this experiment are orange line in Figure 4 a. Unlike winning tickets, the reinitialized networks learn increasingly slower than the original network and lose test accuracy after little pruning. The average reinitialized iterative winning ticket’s test accuracy drops off from the original accuracy when P m = 21.1 % P_{m}=21.1\% , compared to 2.9% for the winning ticket. When P m = 21 % P_{m}=21\% , the winning ticket reaches minimum validation loss 2.51x faster than when reinitialized and is half a percentage point more accurate. All networks reach 100% training accuracy for P m ≥ 5 % P_{m}\geq 5\% ; Figure 4 b therefore shows that the winning tickets generalize substantially better than when randomly reinitialized. This experiment supports the lottery ticket hypothesis’ emphasis on initialization: the original initialization withstands and benefits from pruning, while the random reinitialization’s performance immediately suffers and diminishes steadily.