The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks — part 3/6

Cleaned-text code points [31378, 47230). Bibliography omitted here; source.md includes it.

We only consider vision-centric classification tasks on smaller datasets (MNIST, CIFAR10). We do not investigate larger datasets (namely Imagenet ( Russakovsky et al., 2015 ) ): iterative pruning is computationally intensive, requiring training a network 15 or more times consecutively for multiple trials. In future work, we intend to explore more efficient methods for finding winning tickets that will make it possible to study the lottery ticket hypothesis in more resource-intensive settings.

Sparse pruning is our only method for finding winning tickets. Although we reduce parameter-counts, the resulting architectures are not optimized for modern libraries or hardware. In future work, we intend to study other pruning methods from the extensive contemporary literature, such as structured pruning (which would produce networks optimized for contemporary hardware) and non-magnitude pruning methods (which could produce smaller winning tickets or find them earlier).

The winning tickets we find have initializations that allow them to match the performance of the unpruned networks at sizes too small for randomly-initialized networks to do the same. In future work, we intend to study the properties of these initializations that, in concert with the inductive biases of the pruned network architectures, make these networks particularly adept at learning.

On deeper networks (Resnet-18 and VGG-19), iterative pruning is unable to find winning tickets unless we train the networks with learning rate warmup. In future work, we plan to explore why warmup is necessary and whether other improvements to our scheme for identifying winning tickets could obviate the need for these hyperparameter modifications.

## 7 Related Work

In practice, neural networks tend to be dramatically overparameterized. Distillation ( Ba & Caruana, 2014 ; Hinton et al., 2015 ) and pruning ( LeCun et al., 1990 ; Han et al., 2015 ) rely on the fact that parameters can be reduced while preserving accuracy. Even with sufficient capacity to memorize training data, networks naturally learn simpler functions ( Zhang et al., 2016 ; Neyshabur et al., 2014 ; Arpit et al., 2017 ) . Contemporary experience ( Bengio et al., 2006 ; Hinton et al., 2015 ; Zhang et al., 2016 ) and Figure 1 suggest that overparameterized networks are easier to train. We show that dense networks contain sparse subnetworks capable of learning on their own starting from their original initializations. Several other research directions aim to train small or sparse networks.

Prior to training. Squeezenet ( Iandola et al., 2016 ) and MobileNets ( Howard et al., 2017 ) are specifically engineered image-recognition networks that are an order of magnitude smaller than standard architectures. Denil et al. (2013) represent weight matrices as products of lower-rank factors. Li et al. (2018) restrict optimization to a small, randomly-sampled subspace of the parameter space (meaning all parameters can still be updated); they successfully train networks under this restriction. We show that one need not even update all parameters to optimize a network, and we find winning tickets through a principled search process involving pruning. Our contribution to this class of approaches is to demonstrate that sparse, trainable networks exist within larger networks.

After training. Distillation ( Ba & Caruana, 2014 ; Hinton et al., 2015 ) trains small networks to mimic the behavior of large networks; small networks are easier to train in this paradigm. Recent pruning work compresses large models to run with limited resources (e.g., on mobile devices). Although pruning is central to our experiments, we study why training needs the overparameterized networks that make pruning possible. LeCun et al. (1990) and Hassibi & Stork (1993) first explored pruning based on second derivatives. More recently, Han et al. (2015) showed per-weight magnitude-based pruning substantially reduces the size of image-recognition networks. Guo et al. (2016) restore pruned connections as they become relevant again. Han et al. (2017) and Jin et al. (2016) restore pruned connections to increase network capacity after small weights have been pruned and surviving weights fine-tuned. Other proposed pruning heuristics include pruning based on activations ( Hu et al., 2016 ) , redundancy ( Mariet & Sra, 2016 ; Srinivas & Babu, 2015a ) , per-layer second derivatives ( Dong et al., 2017 ) , and energy/computation efficiency ( Yang et al., 2017 ) (e.g., pruning convolutional filters ( Li et al., 2016 ; Molchanov et al., 2016 ; Luo et al., 2017 ) or channels ( He et al., 2017 ) ). Cohen et al. (2016) observe that convolutional filters are sensitive to initialization (“The Filter Lottery”); throughout training, they randomly reinitialize unimportant filters.

During training. Bellec et al. (2018) train with sparse networks and replace weights that reach zero with new random connections. Srinivas et al. (2017) and Louizos et al. (2018) learn gating variables that minimize the number of nonzero parameters. Narang et al. (2017) integrate magnitude-based pruning into training. Gal & Ghahramani (2016) show that dropout approximates Bayesian inference in Gaussian processes. Bayesian perspectives on dropout learn dropout probabilities during training ( Gal et al., 2017 ; Kingma et al., 2015 ; Srinivas & Babu, 2016 ) . Techniques that learn per-weight, per-unit ( Srinivas & Babu, 2016 ) , or structured dropout probabilities naturally ( Molchanov et al., 2017 ; Neklyudov et al., 2017 ) or explicitly ( Louizos et al., 2017 ; Srinivas & Babu, 2015b ) prune and sparsify networks during training as dropout probabilities for some weights reach 1. In contrast, we train networks at least once to find winning tickets. These techniques might also find winning tickets, or, by inducing sparsity, might beneficially interact with our methods.

## Appendix A Acknowledgments

We gratefully acknowledge IBM, which—through the MIT-IBM Watson AI Lab—contributed the computational resources necessary to conduct the experiments in this paper. We particularly thank IBM researchers German Goldszmidt, David Cox, Ian Molloy, and Benjamin Edwards for their generous contributions of infrastructure, technical support, and feedback. We also wish to thank Aleksander Madry, Shafi Goldwasser, Ed Felten, David Bieber, Karolina Dziugaite, Daniel Weitzner, and R. David Edelman for support, feedback, and helpful discussions over the course of this project. This work was supported in part by the Office of Naval Research (ONR N00014-17-1-2699).

## Appendix B Iterative Pruning Strategies

In this Appendix, we examine two different ways of structuring the iterative pruning strategy that we use throughout the main body of the paper to find winning tickets.

##### Strategy 1: Iterative pruning with resetting.

1. Randomly initialize a neural network f ⁡ ( x , m ⊙ θ ) f(x;m\odot\theta) where θ = θ 0 \theta=\theta_{0} and m = 1 | θ | m=1^{|\theta|} is a mask.

2. Train the network for j j iterations, reaching parameters m ⊙ θ j m\odot\theta_{j} .

3. Prune s % s\% of the parameters, creating an updated mask m ′ m^{\prime} where P m ′ = ( P m − s ) % P_{m^{\prime}}=(P_{m}-s)\% .

4. Reset the weights of the remaining portion of the network to their values in θ 0 \theta_{0} . That is, let θ = θ 0 \theta=\theta_{0} .

5. Let m = m ′ m=m^{\prime} and repeat steps 2 through 4 until a sufficiently pruned network has been obtained.

##### Strategy 2: Iterative pruning with continued training.

1. Randomly initialize a neural network f ⁡ ( x , m ⊙ θ ) f(x;m\odot\theta) where θ = θ 0 \theta=\theta_{0} and m = 1 | θ | m=1^{|\theta|} is a mask.

2. Train the network for j j iterations.

3. Prune s % s\% of the parameters, creating an updated mask m ′ m^{\prime} where P m ′ = ( P m − s ) % P_{m^{\prime}}=(P_{m}-s)\% .

4. Let m = m ′ m=m^{\prime} and repeat steps 2 and 3 until a sufficiently pruned network has been obtained.

5. Reset the weights of the remaining portion of the network to their values in θ 0 \theta_{0} . That is, let θ = θ 0 \theta=\theta_{0} .

The difference between these two strategies is that, after each round of pruning, Strategy 2 retrains using the already-trained weights, whereas Strategy 1 resets the network weights back to their initial values before retraining. In both cases, after the network has been sufficiently pruned, its weights are reset back to the original initializations.

Figures 9 and 10 compare the two strategies on the Lenet and Conv-2/4/6 architectures on the hyperparameters we select in Appendices G and H . In all cases, the Strategy 1 maintains higher validation accuracy and faster early-stopping times to smaller network sizes.

## Appendix C Early Stopping Criterion

Throughout this paper, we are interested in measuring the speed at which networks learn. As a proxy for this quantity, we measure the iteration at which an early-stopping criterion would end training. The specific criterion we employ is the iteration of minimum validation loss. In this Subsection, we further explain that criterion.

Validation and test loss follow a pattern where they decrease early in the training process, reach a minimum, and then begin to increase as the model overfits to the training data. Figure 11 shows an example of the validation loss as training progresses; these graphs use Lenet, iterative pruning, and Adam with a learning rate of 0.0012 (the learning rate we will select in the following subsection). This Figure shows the validation loss corresponding to the test accuracies in Figure 3 .

In all cases, validation loss initially drops, after which it forms a clear bottom and then begins increasing again. Our early-stopping criterion identifies this bottom. We consider networks that reach this moment sooner to have learned “faster.” In support of this notion, the ordering in which each experiment meets our early-stopping criterion in Figure 3 is the same order in which each experiment reaches a particular test accuracy threshold in Figure 3 .

Throughout this paper, in order to contextualize this learning speed, we also present the test accuracy of the network at the iteration of minimum validation loss. In the main body of the paper, we find that winning tickets both arrive at early-stopping sooner and reach higher test accuracy at this point.

## Appendix D Training Accuracy for Lottery Ticket Experiments

This Appendix accompanies Figure 4 (the accuracy and early-stopping iterations of Lenet on MNIST from Section 2 ) and Figure 5 (the accuracy and early-stopping iterations of Conv-2, Conv-4, and Conv-6 in Section Section 3 ) in the main body of the paper. Those figures show the iteration of early-stopping, the test accuracy at early-stopping, the training accuracy at early-stopping, and the test accuracy at the end of the training process. However, we did not have space to include a graph of the training accuracy at the end of the training process, which we assert in the main body of the paper to be 100% for all but the most heavily pruned networks. In this Appendix, we include those additional graphs in Figure 12 (corresponding to Figure 4 ) and Figure 13 (corresponding to Figure 5 ). As we describe in the main body of the paper, training accuracy reaches 100% in all cases for all but the most heavily pruned networks. However, training accuracy remains at 100% longer for winning tickets than for randomly reinitialized networks.

## Appendix E Comparing Random Reinitialization and Random Sparsity

In this Appendix, we aim to understand the relative performance of randomly reinitialized winning tickets and randomly sparse networks. 1. Networks found via iterative pruning with the original initializations (blue in Figure 14 ).

2. Networks found via iterative pruning that are randomly reinitialized (orange in Figure 14 ).

3. Random sparse subnetworks with the same number of parameters as those found via iterative pruning (green in Figure 14 ).

Figure 14 shows this comparison for all of the major experiments in this paper. For the fully-connected Lenet architecture for MNIST, we find that the randomly reinitialized networks outperform random sparsity. However, for all of the other, convolutional networks studied in this paper, there is no significant difference in performance between the two. We hypothesize that the fully-connected network for MNIST sees these benefits because only certain parts of the MNIST images contain useful information for classification, meaning connections in some parts of the network will be more valuable than others. This is less true with convolutions, which are not constrained to any one part of the input image.

## Appendix F Examining Winning Tickets

In this Appendix, we examine the structure of winning tickets to gain insight into why winning tickets are able to learn effectively even when so heavily pruned. Throughout this Appendix, we study the winning tickets from the Lenet architecture trained on MNIST. Unless otherwise stated, we use the same hyperparameters as in Section 2 : glorot initialization and adam optimization.

### F.1 Winning Ticket Initialization (Adam)

Figure 15 shows the distributions of winning ticket initializations for four different levels of P m P_{m} . To clarify, these are the distributions of the initial weights of the connections that have survived the pruning process. The blue, orange, and green lines show the distribution of weights for the first hidden layer, second hidden layer, and output layer, respectively. The weights are collected from five different trials of the lottery ticket experiment, but the distributions for each individual trial closely mirror those aggregated from across all of the trials. The histograms have been normalized so that the area under each curve is 1.

The left-most graph in Figure 15 shows the initialization distributions for the unpruned networks. We use glorot initialization, so each of the layers has a different standard deviation. As the network is pruned, the first hidden layer maintains its distribution. However, the second hidden layer and the output layer become increasingly bimodal, with peaks on either side of 0. Interestingly, the peaks are asymmetric: the second hidden layer has more positive initializations remaining than negative initializations, and the reverse is true for the output layer.

The connections in the second hidden layer and output layer that survive the pruning process tend to have higher magnitude-initializations. Since we find winning tickets by pruning the connections with the lowest magnitudes in each layer at the end , the connections with the lowest-magnitude initializations must still have the lowest-magnitude weights at the end of training. A different trend holds for the input layer: it maintains its distribution, meaning a connection’s initialization has less relation to its final weight.

### F.2 Winning Ticket Initializations (SGD)

We also consider the winning tickets obtained when training the network with SGD learning rate 0.8 (selected as described in Appendix G ). The bimodal distributions from Figure 15 are present across all layers (see Figure 16 . The connections with the highest-magnitude initializations are more likely to survive the pruning process, meaning winning ticket initializations have a bimodal distribution with peaks on opposite sides of 0. Just as with the adam-optimized winning tickets, these peaks are of different sizes, with the first hidden layer favoring negative initializations and the second hidden layer and output layer favoring positive initializations. Just as with the adam results, we confirm that each individual trial evidences the same asymmetry as the aggregate graphs in Figure 16 .

### F.3 Reinitializing from Winning Ticket Initializations