Rigging the Lottery: Making All Tickets Winners
Authors: Utku Evci
Erich Elsen
Pablo Castro
Trevor Gale
Venue:  (2020)
Keywords: sparse training
sparsity
pruning
lottery tickets
imagenet
resnet
mobilenet
efficiency
optimization
local minima

Abstract: Sparse neural networks have been shown to yield computationally efficient networks with improved inference times.  There is a large body of work on training dense networks to yield sparse networks for inference (Molchanov et al., 2017;Zhu & Gupta, 2018; Louizos et al., 2017; Li et al., 2016; Guo et al., 2016).  This limits the size of the largest trainable sparse model to that of the largest trainable dense model. In this paper we introduce a method to train sparse neural networks with a fixed parameter count and a fixed computational cost throughout training, without sacrificing accuracy relative to existing dense-to-sparse training methods. Our method updates the topology of the network during training by using parameter magnitudes and infrequent gradient calculations. We show that this approach requires less floating-point operations (FLOPs) to achieve a given level of accuracy compared to prior techniques. We demonstrate state-of-the-art sparse training results with ResNet-50, MobileNet v1 and MobileNet v2 on the ImageNet-2012 dataset. Finally,  we  provide  some  insights  into  why  allowing  the  topology  to change during the optimization can overcome local minima encountered when the topology remains static.

Under review as a conference paper at ICLR 2020
RIGGING THE LOTTERY: MAKING ALL TICKETS WINNERS
Anonymous authors Paper under double-blind review
ABSTRACT
Sparse neural networks have been shown to be more parameter and compute ef- ficient compared to dense networks and some cases they are even successfully used to decrease wall clock inference times. There is a large body of work on training dense networks to yield sparse networks for inference (Molchanov et al., Zhu & Gupta 2018 Louizos al. 2017 Li ct al. 2016 Guo et al. (016)) This limits the size of the largest trainable sparse model to that of the largest train- able dense model. In this paper introduce method to train sparse neural networks with a fixed parameter count and a fixed computational cost throughout training, without sacrificing accuracy relative to existing dense-to-sppe -t---pssss training methods. Our method updates the topology of the network during training by using parameter magnitudes and infrequent gradient calculations. We show that this approach requires fewer floating-poit -ponnt operations (FLOPs) to achieve given level of accuracy compared to prior techniques. We demonstrate state-of-the-art sparse training results with ResNet-50, MobileNet v1 and MobileNet v2 on the ImageNett2212 dataset, WideResNets on the CIFAR-10 10 dataset and RNNs on the WikiTexxt 103 dataset. Finally, we provide some insights into why allowing the topology to change during the optimization can overcome local minima encoun- tered when the topology remains static.
2017
INTRODUCTION
The parameter and floating point operation (FLOP) efficiency of sparse neural networks is now well demonstrated on a variety of problems (Han et al. 2015 Srinivas et al. 2017). Some work has even shown inference time speedups are possible Recurrent Neural Networks (RNNs) (Kalchbrenner eet al., 2018) and Convolutional Neural Networks (ConyNets) (Park et al. 2016). Currently, the accurate sparse models are obtained with techniques that require,
minimum, the cost of training a dense model in terms of memory and FLOPs (Zhu & Gupta 2018) Guo et al. 2016). and sometimes significantly more (Molchanov et al. 2017). This paradigm has two main limitations:
The maximum size of sparse models is limited to the largest dense model that can be trained. Even if sparse models more parameter efficient, we can't use pruning to train models that are larger and more accurate than the largest possible dense models.
2. It is inefficient. Large amounts computation must be performed for parameters that are zero valued or that will be zero during inference.
Additionally, it remains unknown if the performance the current best pruning algorithms are an upper bound on the quality of sparse models. Gale et al. (2019) found that three different dense-to- sparse training algorithms all achieve about same sparsity accuracy trade-off. However, this far from conclusive proof that no better performance is possible. In this work we show the surprising result that dynamic sparse training, which includes the method we introduce below, can find more accurate models than the current best approaches pruning initially dense networks. Importantly, our method does not change the FLOPs required to execute the model during training, allowing one to decide specific inference cost prior to training.
The Lottery Ticket Hypothesis (Frankle & Carbin 2019) hypothesized that if we can find a sparse neural network with iterative pruning, then we train that sparse network from scratch, to the

---

Under review as a conference paper at ICLR 2020
same level of accuracy, by starting from the original initial conditions. In this paper introduce new method for training sparse models without the need of "lucky" initialization; for this reason, call our method "The Rigged Lottery" Rig4
We show that this method is:
Memory efficient: requires memory only proportional to the size of the sparse model. It never requires storing quantities that are the size of the dense model. This is in contrast tetDemrerss & Zettlemoyer (2019) which requires storing the momentum for all parameters, even those that are zero valued.
Computationally efficient: The amount of computation required to train the model is pro-
portional to the number of nonzero parameters in the model.
Accurate: The performance achieved by the method matches and sometimes exceeds the performance of pruning based approaches.
Our method works by infrequently using instantaneous gradient information to inform re-wiring of the network. We show that this allows the optimization to escape local minima where would otherwise become trapped if the sparsity pattern were remain static. Crucially, as long as the full gradient information is needed less than every T-sparsity iterations, then the overall work remains proportional to the model sparsity.
2 RELATED WORK
Research finding sparse neural networks dates back decades; for example, at least to Thimm & Fiesler (1955) who concluded that pruning weights based on magnitude was a simple and powerful technique. [Strmm] (197)) later introduced the idea of retraining the previously pruned network to increase accuracy. Han et al. (2016b) went further and introduced multiple rounds of magnitude pruning and retraining. This is, however, relatively inefficient, requiring ten rounds of retraining when removing 20% of the connections to reach a final sparsity of 90%. To overcome this problem, Narang et al. (2017) introduced gradual pruning, where connections are slowly removed over the course of single round of training. Zhu & Gupta (2018) refined the technique to minimize the amount of tlyerr-paamees selection required.
A diversity of approaches not based on magnitude based pruning have also been proposed. LeCun al.] (1990) Hassibbi Stork (1993) are some early examples, but impractical for modern neural networks they use information from the Hessian to prune trained network. More recent work includes Lo Regularization (Christos Louizos 2018). Variational Dropout (Molchanov al. (017). Dynamic Network Surgery (Guo et al. (016) and Sensitivity Driven Regularization (Tartaglione ctt al. 2018). [ale et al. (2019) examined magnitude pruning, Lo Regularization and Variational Dropout and concluded that they all achieve about the same accuracy versus sparsity trade-off on ResNet-50 and Transformer architectures.
knowl- Training techniques that allow for sparsity throughout the entire training process were, edge, first introduced in Deep Rewiring (DeepR) (Bellec et al.] 2017). In DeepR, the standard Stochastic Gradient Descent (SGD) optimizer is augmented with random walk in parameter space. Additionally, connections have a pre-defined sign assigned at random; when the optimizer would normally flip the sign, the weight is set instead and new weights are activated random.
Sparse Evolutionary Training (SET) (Mocanu et al. 2018 proposed a simpler scheme where weights are pruned according to the standard magnitude criterion used in pruning and are added back at random. The method is simple and achieves reasonable performance in practice. Dynamic Sparse Reparameterizatioo (DSR) (Mostafa Wang 2019) introduced the idea of allowing the parameter budget to shift between different layers of the model, allowing for non-unifone sparsity. This allows the model to distribute parameters where they are most effective. Unfortunately, the models under consideration are mostly convolutional networks, so the result of this parameter reallocation (which is to decrease the sparsity of carly layers and increase the sparsity of later layers) has the overall effect of increasing the FLOP count because the spatial size is largest the beginning. Sparse Networks from Scratch (SNFS) (Dettmers & Zettlemoyer 2019) introduces the idea of using the momentum of each parameter as the criterion to be used for growing weights and demonstrates it
"Pronounced "wriggle".
2

---

Under review as a conference paper at ICLR 2020
Method
Drop
Grow none
Selectable FLOPs
Space & FLOPs
SNIP
min( ( (oL(
yes
sparse
DeepR
stochastic
random
yes
sparse sparse sparse dense
SET
min(10)
random
yes
DSR
min (8)
random
no
SNFS (ours)
min [0)
momentum
min((0)
gradient
yes
sparse
Table Comparison different sparse training techniques. Drop and Grow columns correspond to the strategies used during the mask update. Selectable FLOPs is possible if the cost of training the model fixed at the beginning of training.
leads to improvement in test accuracy. Like DSR, they allow the sparsity of each layer to change and focus on a constant parameter, not FLOP, budget. Importantly, the method requires computing those that zero,
gradients and updating the momentum for every parameter in the model, at every iteration. This can result in a significant amount of overall computation. Additionally, depending the model and training setup, the required storage for the full momentum tensor could be prohibitive. Single-Shot Network Pruning (SNIP) (Lee et al. 2019) attempts to find an initial mask with one-shot pruning and uses the saliency score of parameters to decide which parameters to keep. After pruning training proceeds with this static sparse network. Properties of the different sparse training techniques are summarized in Table
There has also been a line of work investigating the Lottery Ticket Hypothesis (Frankle & Carbin 2019). Frankle
(2019) showed that the formulation must be weakened to apply larger networks such as 50 (He et al.) (015). In large networks, instead of the original initial- ization, the values after thousands of optimization steps must be used for initialization. Zhou et al.) (2019) showed that lottery tickets obtain non-random accuracies even before the training has started. Though the possibility of training sparse neural networks with a fixed sparsity mask using lottery tickets is intriguing, remains unclear whether it is possible to generate such initializations for both masks and parameters de novo.
RIGGING THE LOTTERY
Our method, Rigl, is illustrated in Figure [] At regularly spaced intervals our method removes a fraction of connections based on weight magnitudes and activates new ones using instantancous gradient information. After updating the connectivity, training continues with the updated network until the next update. The main parts our algorithm, Sparsity Distribution, Update Schedule, Drop Criterion, Grow Criterion, and the various options considered for each, explained below. The improved performance of RigL is due to two reasons: the use of new method for activating connections that is efficient and more effective than choosing random, and the of a natural extension to an existing method for distributing parameters statically among convolutional layers.
(0) Notation. Given dataset D with individual inputs and targets one can train neural network minimize the loss function Σ; ((fo( 21), where fo(x) the neural network with
(3) Drop
(4) Grow
(2) Updete Schedule
Sparsity Distribution
Update iteration?
yes
Sperse Training
Figure 1: Dynamic sparse training aims change connectivity during training help out optimza- tion.

---

Under review as a conference paper at ICLR 2020
parameters A of length N. The vector 0 can be decomposed into parameters 8', of length N for each layer 1. A sparse network keeps only a fraction D E (0, 1) of all connections, resulting in a sparsity of S = 1 - D. More precisely, denoting the sparsity of individual layers with s', the total parameter count of the sparse neural network satisfies (1 - =') = =(1 S) 5)* N.
(1) Sparsity Distribution. There are many ways of distributing the non-zero weights across the layers while satisfying the equality above. We avoid re-allocating parameters between layers during the training process it makes it difficult to target a specific final FLOP budget, which is important for many inference applications. We consider the following three strategies:
1. Uniform: The sparsity of each individual layer is the same as the total sparsity S. We keep the first layer dense (s" 0), since it has negligible number of parameters.
2. Erdös-Rényi: As introduced in Mocanu et al. 2018), s scales with 1 -'='+n' denotes number of neurons layer This enables the number of connections in sparse layer to scale with the sum of the number of output and input channels.
Tant where n'
3. Erdös-Rényi- Kereell (ERK): This method modifies the original Erdös-Réng Rényi formulation by including the kernel dimensions in the scaling factors. In other words, the number of 2''1+n'' + +h! parameters of the sparse convolutional layers are scaled proportional to -n- wh" where w/ and / are the width and the height of the I'th convolutional kernel. Sparsity of the fully connected layers scale as in the original Erdös-Rényi formulation. Similar Erdōs- Rényi, ERK allocates higher sparsities to the layers with more parameters while allocating lower sparsities to the smaller ones.
In all methods, the bias and batch-norm parameters are kept dense.
(2) Update Schedule. The update schedule is defined by the following parameters: (1) the number of iterations between sparse connectivity updates (AT), (2) the iteration which to stop updating the sparse connectivity (Tend), (3) the initial fraction of connections updated (a) and (4) a function Sdecay: invoked every AT' iterations until Tend, possibly decaying the fraction of updated connec- tions over time. For the latter we choose to use cosine annealing, as we find it slightly outperforms the other methods considered.
ta Tend
fdecay (t)
1 cos
Alternatives to cosine annealing like constant schedule and inverse power annealing are studied in the Appendix F
(3) Drop criterion. Over the course of training, we drop the lowest magnitude weights according to the update schedule since they are expected to effect the training loss least. Specifically, we drop the connections given by T T- (decca
st >
(4) Grow criterion. The novelty of our method lies in how we grow new connections. We grow the connections with highest magnitude gradients, TopK actioe (Igrad(f'), (1ccs)())11ss)))))
where P is the set of active connections after the drop step. Newly activated connections are initialized
and therefore don't effect the output of the network. However they are expected to receive gradients with high magnitudes in the next iteration and therefore reduce the loss fastest. This procedure can be applied to each layer in sequence and the dense gradients can be discarded immediately after selecting the top connections. If a layer is too large to materialize the full gradient with respect to the weights, then we can further reduce the memory requirements by performing an iterative calculation:
1. Initialize the set TK = O--
2. Materialize subset of size M of the full gradient, which we denote GBs4M
3. Update TK to contain the Top-K elements of Ges+ concatenated with TK.
4. Repeat steps through 3 until all of the gradients have been materialized. The final set TK contains the connections wish to grow.
TTopK(p, k) returns the indices and values of the top-k elements of vector u.
4

---

Under review as a conference paper at ICLR 2020
Performance on ImageNet-2012
Sparsity Sweep
0.7
Test Accuracy
0.76
Test Accuracy
075
Pruning
0.74
RigL
0.20
Pruningu
0.73
SET
Righiv
0.22
SNFS
Righi (ERI)....
Smaal--Dense
Small-Denses,
Static
Statice
0.70
10
0.0
0Bs
050
095
Training Flops
Sparsity
Figure 2: (left) Performance of various dynamic sparse training methods ImageNet-2012 classi- fication task. We use 80% sparse ResNet-50 architecture with uniform sparsity distribution. Points at each curve correspond to the individual training runs with training multipliers from 1 to 5 (except pruning which is scaled between 0.5 and 2). We repeat training 3 times at every multiplier and report the mean accuracies. The number of FLOPss required train standard dense Resnet-50 along with its performance is indicated with dashed red line. (right) Performance of Rigl. at different sparsity levels with extended training. Results are averaged over 3 runs.
As long as AT I-s the total work in calculating dense gradients amortized and still propor- tional to S. This is in contrast to the method of Dettmers & Zettlemoyer (2019), which requires calculating and storing the full gradients at each optimization step.
4 EMPIRICAL EVALUATION
Our experiments include image classification using CNNs on the ImageNet-2012 (Russakovsky ct al, 2015) and CIFAR-10 (Krizhevsky et al.) datasets and character based language modelling using RNNs with the WikiText- dataset (Merity al.] 2016). We use the TensorFlow Model Pruning library (Zhu & Gupta 2018) for our pruning baselines. A Tensorflow (Abadi et al. 2015) implementation of our method along with three other baselines (SET, SNFS, SNIP) will open sourced. When we increase the training steps by factor M, the anchor epochs of the learning rate schedule and the end iteration of the mask update schedule are also scaled by the same factor; we indicate this scaling with a subscript (e.g. RigLaxx).
4.1 IMAGENET-2012 DATASET
In all experiments in this section, we use SGD with momentum as our optimizer. We set the momen- tum coefficient of the optimizer to 0.9, L2 regularization coefficient to 0.0001, and label smoothing (Szegedy al.) 2016) to 0.1. The learning rate schedule starts with linear warm up reaching its maximum value of 1.6 at epoch 5 which is then dropped by a factor of 10 at epochs 30, 70 and 90. We train networks with batch size of 4096 for 32000 steps which roughly corresponds 100 epochs of training. Our training pipeline uses standard data augmentation, which includes random flips and crops.
4.1.1 RESNET-50
Figure Tigure2left left summarizes the performance of various methods on training an 80% sparse ResNet-50.
We also train small dense networks with equivalent parameter count. All sparse networks use the constant sparsity distribution and a cosine update schedule (a: = 0.3, AT 100). Overall, we observe that the performance of all methods improves with training time; thus, for each method run extended training with up to 5x the training steps of the original.
As noted by Gale et al. (2019). Evci et al. (2019), Frankle et al. (2019). and Mostafa & Wang 2019) training a network with fixed sparsity from scratch (Static) leads to inferior performance. Training small dense network with the same number of parameters gets better results than Static, but fails to match the performance of dynamic sparse models. Similarly SET improves the performance over Small-Denee however saturates around 75% accuracy indicating the limits of growing new connec-
5

---

Under review as a conference paper at ICLR 2020
Method
Top-1 Accuracy
FLOPs (Train)
FLOPs (Test)
Top-1 Accuracy
FLOPs (Train)
FLOPs
(Test)
Dense
76.8+0.09
1x (3.2e18)
(8.2e9)
$=0.8
S=0.9
Static
70.611.006
0.23x
0.23x
65.810.04
0.10x
0.10x
SNIP
72.0+0.10
0.23x
0.23x
67.2
0.10x
0.10x
Small-Dense
72.1+0012
0.20x
0.20x
68.9+0.10
0.12x
0.12x
SET
72.9=0.39
0,23x
0.23x
69.61t023
0.10x
0.10x
RigL
74.6=:0.06
0.23x
0.23x
72.0=0.05
0.10x
0.10x
Small-Densesx
73.9=0.07
1.01x
0.20x
71.3
0.60x
0.12x
RigLax
76.6.10.06
1.14x
0.23x
75.71.0.06
0.52x
0.10x
Static (ERK)
72.140.04
0,42x
0.42x
67.7+0.12
0.24x
0.24x
DSR*
73.3
0,40x
0.40x
71.6
0.30x
0.30x
RigL (ERK)
75.1
0.42x
0.42x
73.011.00
0.25x
0.24x
Rigl.sx (ERK)
07.1
2.09x
0.42x
76.4+
1.23x
0.24x
SNFS*
74.2
n/a
n/a
72.3
n/a
n/a
SNFS (ERK)
75.2:10.11
0.61x
0.42x
72.910.06
0.50x
0.24x
Pruning* (Zhu)
73.2
1.00x
0.23x
70.3
1.00x
0.10x
Pruning* (Gale)
75.6
1.00x
0.23x
73.9
1.00x
0.10x
Pruning1.5x (Gale) 76.5
1.50x
0.23x
75.2
1.50x
0.10x
Table 2: Performance and cost of sparse training methods on training 80% and 90% sparse ResNet- 50s. FLOPs needed for training and test are normalized with the FLOPs a dense model (see Appendix for details how FLOPS calculated). Methods with subscript indicate rescaled training time, whereas *** indicates reported results. (ERK) corresponds to the sparse networks with Erdös-Red Erdös-Renyi-Kenn Renyi-Kennell sparsity distribution. RigLox (ERK) achieves 77.1% Top-1 Accuracy using only 20% of the parameters of a dense model and 42% of its FLOPs.
tions randomly. Methods that use gradient information to grow new connections (RigL and SNFS) obtain higher accuracies, but RigL. achieves the highest accuracy and does so while consistently requiring fewer FLOPs than the other methods.
Given that different applications scenarios might require a limit on the number of FLOPs for inference, we investigate the performance our method at various sparsity levels. As mentioned previously, one strength of our method is that its resource requirements are constant throughout training and we can choose the level of sparsity that fits our training and/or inference constraints. In Figure right we show the performance of our method at different sparsities and compare them with the pruning results of Gale et al.] (2019), which uses 1.5x training steps, relative to the original 32k iterations. To make fair comparison with regards to FLOPs, of all other methods by 5x. Note that even after extending the training, it takes less FLOPs to train sparse networks using rigL (except for the 80% sparse RigL-ERK) compared the pruning method.
scale the learning schedule
Rigl., our method with constant sparsity distribution, exceeds the performance of magnitude based iterative pruning in all sparsity levels while requiring less FLOPs to train. Sparse networks that use Erdös-Renyi-Kene Kernel (ERK) sparsity distribution obtains even greater performance. For exam- ple ResNet-50 with 96.5% sparsity achieves remarkable 72.75% Top-1 Accuracy, around 3.5% higher than the extended magnitude pruning results reported by Gale et al.] (2019). As observed earlier, smaller dense models (with the same number parameters) or sparse models with a static connectivity can not perform at comparable level.
more fine grained comparison of sparse training methods is presented Table Methods us- ing uniform sparsity distribution and whose FI.OP/mmorry footprint scales directly with (1-S) are placed in the first sub-group the table. The second sub-group includes DSR and networks with ERK sparsity distribution which require higher number of FLOPs for inference with same param- eter count. The final sub-group includes methods that require the space and the work proportional to training dense model.
"approximated

---

Under review as a conference paper at ICLR 2020
Method
Top-1
FLOPs
Sparse MobileNets
Small-Dense6x
66.0+0.11
0.23x
0.75
Pruning (Zhu)
67.7
0.27x
Test Accuracy
RigLsx
71.5110.06
0.27x
065
RigLsx (ERK)
71.910001
0.52x
Small-Dense5x
57.740.34
0.09x
060
Pruhing
0.90
Rigis (ERK)
Pruning (Zhu)
61.8
0.12x
OS5-
Small Dense
Rigl-sx
67.0+t0.17
0.12x
Static,, (ERK)
RigLsx (ERK)
68.11.0.11
0.27x
050
mobilenet_v2...
Dense
72.1
1x (I.1c9)
0.75
08o
0.5
Big- Sig-Sparsexx
76.4
0.98x
Sparsity
0.75
Big-Sparsesx (ERK)
77.0=0.08
1.91x
Figure 3: (left) RigL significantly improves the performance of Sparse MobileNets on ImageNet- 2012 dataset and exceeds the praming results reported by Zhuu & Gupta (2018). Performance of the dense MobileNets are indicated with red lines. (right) Performance architectures presented with their inference FLOPs. Networks with ERK distribution get better performance with the same number of parameters but take more FLOPs to run. Training wider sparse models with Rigl. (Big-Sparse) yields significant performance improvement over the dense model.
sparse MobileNet-vi
4.1.2 MOBILENET
MobileNet is a compact architecture that performs remarkably well resource constrained settings. Due to its compact nature with separable convolutions it is known to be difficult to sparsify (Zhu & Gupta 2018). In this section we apply our method to MobileNet-vl (Howard et al., 2017) and MobileNet-v2 v2 (Sandler et al. 2018). Due to its low parameter count we keep the first layer dense, and use ERK and Uniform sparsity distributions to sparsify the remaining layers.
The performance of sparse MobileNets trained with RigL well the baselines are shown in Figure B3] We do extended training (5x of the original number of steps) for all runs in this section. Although MobileNets are more sensitive sparsity compared the ResNet-50 architecture, RigL successfully trains sparse MobileNets at high sparsities and exceeds the performance of previously reported pruning results.
To demonstrate the advantages of sparse models, next, we train wider MobileNets while keeping the FLOPs and total number of parameters the same the dense baseline using sparsity. A sparse MobileNet-vl I with width multiplier 1.98 and constant 75% sparsity has the same FLOPs and pa- rameter count as the dense baseline. Training this network with RigL yields an impressive 4.3% absolute improvement in Top-1 I Accuracy.
4.2 CHARACTER LEVEL LANGUAGE MODELLING
Most prior work has only examined sparse training on vision networks [the exception the earliest work Deep Rewiring (Bellec al. 2017) which trained LSTM (Hochreiter & Schmidhuber 1997) on the TIMIT (Garofolo et al. 1993) dataset]. To fully understand these techniques it is im- portant to examine different architectures
different datasets. Kalchbrenner al. (2018) found sparse GRUs (Cho et al., 2014) to be very effective at modeling speech, however the dataset they used is not available. We choose a proxy task with similar characteristics (dataset size and vocabu- lary size are approximately the same) character level language modeling on the publicly available WikiText- (Merity et al. (016) dataset.
Our network consists of shared embedding with dimensionality 128, vocabulary size of 256, GRU with a state size of 512, a readout from the GRU state consisting of two linear layers with 256 units and 128 units respectively. We train the next step prediction task with the standard cross entropy loss, the Adam optimizer, a learning rate of 7e 4, an L2 regularization coefficient of 5e -4, sequence length of 512, batch size of 32 and gradient absolute value clipping of values larger (in magnitude) than 10. Baseline training length is 200,000 iterations. When inducing sparsity with magnitude pruning (Zhu & Gupta 2018), perform pruning between iterations 50,000 and
7

---

Under review as a conference paper at ICLR 2020
Performance on WikiText-
Sparsity Sweep on CIFAR-10
0.95
0.94
Bits Per Step
1.65
Test Accuracy
0.93
0.92
1.50
Pruning
Pruning (ERK]
RigL
Rig. (ERI)
0.90
Rig.ax (ERK)
1.55
SNFS
Static (ERK)
0.89
Static
Stalikzx (ERK)
1.50
0.88
0.6
0.8
0.3
Training Flops
Sparsity
Figure 4: (left) Final validation loss of various sparse training methods on character level language modelling task. Cross entropy loss is converted bits (from nats). Performance and the training cost of a dense model is indicated with dashed red lines. (right) Test accuracies of sparse WideResNet- 22-2's on CIFAR-10 10 task.
150,000 with pruning frequency of 1,000. We initialize sparse networks with uniform sparsity distribution and use a cosine update schedule with 0.1 and AT 100. Unlike the previous experiments we keep updating the mask until the end of the training; we observed this performed slightly better than stopping iteration 150,000.
In Figure Ieft we report the validation loss of various solutions at the end of the training. For each method we perform extended runs to see how they scale with increasing training time. As observed before, SET performs worst than the other dynamic training methods and its performance improves only slightly with increased training time. On the other hand the performance of RigL and SNFS improves constantly with more training steps. Both of these methods falls short of matching the pruning performance.
4.3 WIDERESNET-22-- ON CIFAR-10
In this section, evaluate the performance of RigL on CIFAR- 10 image classification benchmark. We train Wide Residual Network's 's (Zagoruyko & Komodakis 2016) with 22 layers using width multiplier of 2 for 250 epochs (97656 steps). Learning rate starts at 0.1 and scaled down by factor 5 every 30,000 iterations. We use an L2 regularization coefficient 5e-4, a batch size of 128 and a momentum coefficient of 0.9. We keep the hyper-parameters specific to RigL same as the ImageNet experiments, except the final iteration for mask updates; which is adjusted to 75000. Results with different mask update intervals can be found in Appendix
Performance of RigL across different sparsity levels is presented in Figure rright Corresponding final training losses of the trained networks can be found in Appendix H The dense baseline ob- tains 94.1% test accuracy. Networks with half of the connections removed (50% sparsity) achieves roughly the same accuracy as the dense baseline. Surprisingly. some of the networks this spar- sity level generalize better than the dense baseline demonstrating the regularization aspect of using sparsity. With increased sparsity, we start to see performance gap between the Static and Pruning solutions. Training static RigL networks longer seems to have limited effect on the final perfor- mance. On the other hand, RigL, matches the performance of pruning using only a fraction of resources needed for training dense network.
4.4 ANALYZING THE PERFORMANCE OF Rigl.
In this section we study the effect of sparsity distributions, update schedules, and dynamic connec- tions the performance of our method. The results for SET and SNES are similar and are discussed in Appendices and
Effect of Mask Initializatin:: Figure left shows how the sparsity distribution affects the final test accuracy of sparse ResNet-50s trained with RigL. Erdös- Erdōs-Rényi- Rényi-Kernde (ERK) performs consis- tently better than the other distributions. ERK automatically allocates parameters to the
8

---

Under review as a conference paper at ICLR 2020
Sparsity Distributions
Cosine Update Schedule
Erdös Rerys--rr--eeo Erdés-Rérii
0.80
0746
Test Accuracy
Test Accuracy
Uniform
0740
0.70
0.75
0.69
0.700
0.1
0.60
0725
0.3
05
0.55
63
0.9
0.95
0.965
0.20
10
13
Sparsity
Update Interval
Figure 5: (left) Performance of RigL at different sparsities using different sparsity masks (right)
Ablation study on cosine schedule. Other methods are in the appendix.
layers with few parameters by decreasing their sparsities This reallocation seems to be crucial for preserving the capacity of the network high sparsity levels where ERK outperforms other distri- butions by greater margin. Though it performs better, the ERK distribution requires approximately twice many FLOPs compared to uniform distribution. This highlights an interesting trade-off between accuracy and computational efficiency even though both models have the same number of parameters.
Effeet of Update Schedule and Frequency: In Figure Stright, we evaluate the performance of our method on update intervals AT [50, 100, 500, 1000) and initial drop fractions [0.1, 0.3, 0.5). The best accuracies are obtained when the mask is updated every 100 iterations with an initial drop fraction 0.3 or 0.5. Notably, even with frequent update intervals (e.g. every 1000 iterations), RigL performs above 73.5%.
Effect of Dynamic connections: Frankle et al. (2019) and Mostafa & Wang 2019) observed that static sparse training converges to a solution with higher loss than dynamic sparse training. In Figurc/o-left we examine the loss landscape lying between a solution found via static sparse training and a solution found via pruning to understand whether former lies in a basin isolated from the latter. Performing linear interpolation between the two reveals the expected result high-loss barrier demonstrating that the loss landscape is not trivially connected. However, this is only one of infinitely many paths between the two points optimization can be used to find parametric curves that connects solutions (Garipov al., 2018 Draxler et al.! 2018) subject constraints. For example Garipov et al. (2018) showed different dense solutions lie in the same basin by finding 2nd order Bézier curves with low energy between the two solutions. Following their method, we attempt
see Appendix ffor exact layer-wise sparsities given by ERK for 80% and 90% sparse ResNet-50's.
Path Between Two Solutions
76.0
Fruning
Static
Rigl
Static
Training Loss
Training Loss
73.0
2.0
Biz Derse
1.5
Accuracy
262
0.6
Iteration
1 e4
Interpolation Coefficient
Figure 6: (left) Training loss evaluated at various points on interpolation curves between magnitude pruning model (0.0) and model trained with static sparsity (1.0). (right) Training loss of Rigl. and Static methods starting from the static sparse solution, and their final accuracies.

---

Under review as a conference paper at ICLR 2020
to find quadratic and cubic Bézier curves between the two sparse solutions. Surprisingly, even with cubic curve, we fail to find a path without a high-loss barrier. These results suggest that static sparse training can get stuck at local minima that are isolated from improved solutions. On the other hand, when we optimize the quadratic Bézier curve across the full dense space we find near-monotonic path the improved solution, suggesting that allowing sparse training greater flexibility in navigating the loss landscape.
connections grow lends dynamic
In Figure (tright we train RigL starting from the sub-optimal solution found by static sparse train- ing, demonstrating that it is able to escape the local minimum, whereas re-training with static sparse training cannot. RigL first removes connections with the smallest magnitudes since removing these connections have been shown to have minimal effect on the loss (Han et al. 2015 Evci 2018). Next, activates connections with the high gradients, since these connections are expected to de- crease the loss fastest. We hypothesize in Appendix [ that Rigl. escapes bad critical points by replacing saddle directions with high gradient dimensions.
5 DISCUSSION & CONCLUSION
In this work we introduced 'Rigged Lottery' or RigL, an algorithm for training sparse neural net- works efficiently. For given computational budget RigL. achieves higher accuracies than existing dense-to-sparse and sparse-to-sparse training algorithms. RigL. is useful in three different scenarios: (1) To improve the accuracy of sparse models intended for deployment; (2) To improve the accuracy of large sparse models which can only be trained for a limited number of iterations; and (3) Com- bined with sparse primitives enable training of extremely large sparse models which otherwise would not be possible.
The third scenario is unexplored due to the lack of hardware and software support for sparsity. Nonetheless, work continues to improve the performance of sparse networks on current hard- ware (Hong et al.) 2019;; Merrill Garland, (2066), and new types hardware accelerators will have better support for parameter sparsity (Wang et al., 2018 Mike Ashby 2019 Liu et al.) 20118] Han et al., 2016a Chen et al., 2019). RigL provides the tools to take advantage of, and motivation for, such advances.
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving. Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dan Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vin- cent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Watten- berg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogencous systems, 2015. URL
org/
Guillaume Bellec, David Kappel, Wolfgang Maass, and Robert A. Legenstein. Deep rewiring: Training very sparse deep networks. CoRR, abs/1711.05136, 2017. URL httt:://axxxiv
org/ bogg/bb//7711.000 05136
Y. Chen, T. Yang, J. Emer, and V. Sze. Eyeriss v2: A flexible accelerator for emerging deep neural networks on mobile devices. IEEE Journal on Emerging and Selected Topics Circuits and Systems, 9(2):292-308 June 2019. doi: 10. 10.1109/JTCAAS.200 201...99299922222....
Kyunghyun Cho, van Merrienboer, Caglar Gulcehre, F Bougares, Schwenk, and Yoshua Ben- gio. Learning phrase representations using mnn encoder-decoder for statistical machine translation. In Conference on Empirical Methods Natural Language Processing (EMNLP 2014), 2014.
Diederik P. Kingma Christos Louizos, Max Welling. Learning sparse neural networks through lo regularization. In International Conference on Learning Representations, 2018
Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing 04840
performance. ArXiv, 2019. wtt.ht.p:://xxxv..rrg////
10

---

Under review as a conference paper at ICLR 2020
Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred A Hamprecht. Essentially No Bar- riers in Neural Network Energy Landscape, In International Conference on Machine Learning, 2018.
Utku Evci. Detecting dead weights and units in neural networks. CoRR, 2018. / //axxiv.org/abb/18006 66068
URL http:
Utku Evci, Fabian Pedregosa, Aidan N. Gomez, and Erich Elsen. The difficulty of training sparse neural networks. ArXiv, 2019. URL httppp//aaax....rrra/a//////////
10732
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neu- ral networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019. URL https:/ htttss://openreview..o net. foret/foormmid
FJl FJ1-b3ReF7]
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, and Michael Carbin. The lottery 0166]
ticket hypothesis at scale, ArXiv, 2019. htt.http://axxe wwt.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity deep neural networks. CoRR, abs/1902.09574, 2019.
09574
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew Gordon Wilson. Loss surfaces, mode connectivity, and fast ensembling of dons. Advances in Neural Information Processing Systems, 2018.
J. S. Garofolo, L. F. Lamel, W. M. Fisher, J. G. Fiscus, D. S. Pallett, and N. L. Dahlgren. Darpa timit acoustic phonetic continuous speech corpus edrom, 1993.
Yiwen Guo, Anbang Yao, and Yurong Chen. Dynamic network surgery for efficient DNNs. CoRR, abs/1608.04493 04493, 2016. http:://a/r
org/ abs/a/as//111//// 04493
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances in neural information processing systems, 2015.
Song Han, Xingyu Liu, Huizi Mao, Jing Pu, Ardavan Pedram, Mark A. Horowitz, and William J. Dally. EIE: Efficient Inference Engine on compressed deep neural network. Proceedings of the 43rd International Symposium on Computer Architecture, 2016a.
Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural net- work with pruning, trained quantization and huffman coding. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016b. URL http:/ arxii,ivvvv./.... orq/ abs 11111111111 00149
B. Hassibi and D. Stork. Second order derivatives for network pruning: Optimal Brain Surgeon. 1993.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the 2015 IEEE Interna- tional Conference on Computer Vision (ICCV), 2015.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Comput., 98): doi: 10.1 19t5//eco.1997.98.. URL http://xx
1780, November 1997. ISSN 0899-7667,
doi.org/ 110.01112200 1ww.:.11122neeeee 1997. 9. 1735
Changwan Hong. Aravind Sukumaran Rajam,, Israt Nisa, Kunal Singh, and P. Sadayappan. Adaptive sparse tiling for sparse matrix multiplication. In Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming, PPoPP '19, pp. 300-314, New York, NY, USA, 2019. http:tt:://
ACM. ISBN 978- 1 100-----503-2225555 doi: 01114/3223388.32957777 org/10.1145/322 1tl.:115/3229385
acc.
3295712
Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Mareo Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. CoRR, Abs/1704404861, 2017. URL http: org/ org/abs/
T704 04861
11

---

Under review as a conference paper at ICLR 2020
Nal Kalchbrenner, Erich Elsen, Karen Simonyan, Seb Noury, Norman Casagrande, Edward Lock- hart, Florian Stimberg. Aaron Oord, Sander Dieleman, and Koray Kavukcuoglu. Efficient neural audio synthesis. In International Conference on Machine Learning (ICML), 2018.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced search). URL http:h/tpw//// http://wwwccom cs toronto......o......... www/ekriz////eeeeeeeee sariz/cifate cat./aamfa
Yann LeCun, John S. Denker, and Sara A. Solla. Optimal Brain Damage. In Advances in Neural Information Processing Systems, 1990.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. S. Tomr. SNIP: Single-shot Network Prun- ing based on Connection Sensitivity. In International Conference on Learning Representations (ICLR), 2019, 2019.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. In International Conference on Learning Representations, 2016.
Chen Liu, Guillaume Bellec, Bernhard Vogginger, David Kappel, Johannes Partzsch, Felix Neu- maerker, Sebastian Höppner, Wolfgang Maass, Stephen B. Furber, Robert A. Legenstein, and Christian Mayr. Memory-efficient deep learning on spinnaker 2 prototype. Front. Neurosci., 2018.
Christos Louizos, Karen Ulirich, and Max Welling. |Bayssian compression for deep learning In Advances in Neural Information Processing Systems, 2017.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. ArXiv, 2016. Utt.httt:///rrxiv.oo
http:/aas.11.0000 07843
Duane Merrill and Michael Garland. Merge- based sparse matrix-vector multiplication (spmv) using the csr storage format. In Proceedings of the 2 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 16, pp. 43:1-43:2, New York, NY, USA, 2016. ACM. doi: 00.1145/2551441228511 10. 10.1145/2851141 118.511111.28519900
ISBN 978 4-023-4092-2
URL http: //do: acm. org/
Peter Baldwin Martijn Bastiaan Oliver Bunting Aiken Cairneross Christopher Chalmers Liz Cor- rigan Sam Davis Nathan van Doomn Jon Fowler Graham Hazel Basile Henry David Page Jonny Shipton Shaun Steenkamp Mike Ashby, Christiaan Baaij. Exploiting unstructured sparsity on next-generation datacenter hardware. 2019. URL ht tps: //t//t/ylle/e////e//..o//e///mme le. a /opttnnntttt// MorEeoorrtMMttlle. ai 21. 06.006.6 99b.._p..f...
upllaads/219//
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong Nguyen, Madeleine Gibescu, and Antonio Liotta. (Scalable training of artificial neural networks with adaptive sparse connec- tivity inspired by network science Nature Communications, 2018
Dmitry Molchanov, Arsenii Ashukha, and Dmitry P. Vetrov. Variational Dropout Sparsifies Deep
Neural Networks. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pp. 2498-2507, 2017.
Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz. Pruning Convolutional Neural Networks for Resource Efficient Transfer Learning. CoRR, abs//611.0644// 2016.
Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 4646-4655, 2019.
mlr press 99 httppppess///mmmmsstteesessee htt////ostaaaaaaa.mmmmam html
Sharan Narang, Greg Diamos, Shubho Sengupta, and Erich Elsen. Exploring sparsity in re- current neural networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017. URL https: / //openreview. nww. fttt:/foummm// d=Bylsyyyyyyyyy
Jongsoo Park, Sheng R. Li, Wei Wen. Hai Li, Yiran Chen, and Pradeep Dubey. Holistic SparseCNN: Forging the trident of accuracy, speed, and size. CoRR, abs/1660801 0148,, 2016. URL http:
wlaaxiivrrg/aee (008. 01409
12

---

Under review as a conference paper at ICLR 2020
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Fei- Fei. Imagenet large scale visual recognition challenge. International Journal of Computer Viston (IJV), 2015.
M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L. Chen. Mobilenetv2: Inverted residuals and linear bottlenecks. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4510-4520, June 2018. doi: 10.11099CVR..2088..000
S. Srinivas, A. Subramanya, and R. V. Babu. Training sparse neural networks. In 2017 IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pp. 455-462, July 2017. doi: 11110//VVR..201..00
Nikko Ström. Sparse Connection and Pruning in Large Dynamic Artificial Neural Networks. In EUROSPEECH, 1997.
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jonathon Shlens, and Zbigniew Wojna. Re- thinking the inception architecture for computer vision. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition,, 2016. URL http::/aawxi...rrgaabbaee
00567
Enzo Tartaglione, Skjalg Lepsøy, Attilio Fiandrotti, and Gianluca Francini. Learning sparse neural networks via sensitivity-driven regularization. In Proceedings of the 32nd International Confer- ence Neural Information Processing Systems, NIPS' 18, pp. 3882-3892, USA, 2018. Curran 3327303
wtt.:aaa......aa.iiio... Associates Inc. htLL://: acm. wwtp/o/gggt/too.ooooo.oo//t..
Georg Thimm and Emile Fiesler. Evaluating pruning methods. In National Chiao-Tung University, pp. 1995.
Peiqi Wang, Jú, Chi Hong, Yongqiang Lyu, Dongsheng Wang, and Yuan Xie. Snrram: An efficient sparse neural network computation architecture based resistive random-access memory. In Proceedings of the 55th Annual Design Automation Conference, DAC '18 pp. 106:1-106:6, New
York, NY, USA, 2018. ACM. ISBN 978-1-4503-57005. doi: 10. 10.1145/19599703116111 URL
http:://dii acm.
3196116
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In BMVC, 2016.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask| ArXiv, 2019.
Michael Zhu and Suyog Gupta. To Prune, or Not to Prune: Exploring the Efficacy of Pruning for Model Compression In International Conference Learning Representations Workshop, 2018.
A EFFECT OF MASK UPDATES ON THE ENERGY LANDSCAPE
To update the connectivity of our sparse network, we first need to drop fraction d of the existing connections for each layer independently create a budget for growing new connections. Following the recipe of magnitude based pruning(Han et al. 2015), order parameters at layer i by magnitude [0:] and drop the N (1 S) d parameters with lowest magnitude. The effectiveness of this simple criteria can be explained through the first order Taylor approximation of the loss L around the current set of parameters
AL = L(0 + 20) L(0) = VoL + R(]A0))))
The main goal of dropping connections is to remove parameters with minimal impact on the neu- ral network and therefore on its performance. Since removing the connection 0, corresponds to setting it to zero, it incurs a change of A = -8; in that direction and change of AL; = L()) R((?) in the loss, where the first term is usually defined the saliency of connec- tion. Though using saliency to remove connections has been used as a criteria for removing connec- tions MMochanov et al. 2016), it has been shown produce inferior results compared to magnitude
13

---

Under review as a conference paper at ICLR 2020
based removal, especially when used to remove multiple connections at once (Evci 2018 In trast, picking the lowest magnitude connections ensures a small remainder term in addition to a low note that
saliency, limiting the damage we make when drop connections. Additionally, nections with small magnitude can only remain small if the gradient is also small, meaning that the saliency is likely small when the parameter itself is small. Therefore argue that the connections removed by RigL are likely to be saddle directions of the energy landscape.
After the removal of insignificant connections, enable connections that have the highest expected gradients. Since we initialize these new connections to zero, they are guaranteed to have high gradients in the proceeding iteration and therefore reduce the loss quickly. By definition direction with high magnitude gradient is not a saddle direction. Combining this observation with the previous (Rigl. likely to remove saddle directions) and the results in Section [4.4 we suggest that Rigl. improves the energy landscape of the optimization by replacing saddle directions with the ones with high gradient. This helps the optimization procedure to escape bad critical points and find solutions with higher quality.
B EFFECT OF SPARSITY DISTRIBUTION ON OTHER METHODS
In Figure left we show the effect of sparsity distribution choice on different sparse training methods. ERK distribution performs better than other distributions for each training method.
C EFFECT OF MOMENTUM COEFFICIENT FOR SNFS
In Figure right we show the effect the momentum coefficient on the performance of SNFS. Our results shows that using coefficient of 0.99 brings the best performance. On the other hand using the most recent gradient only (coefficient of 0) performs as good as using a coefficient 0.9. This result might be due the large batch size we using (4096), but it still motivates using Rigl. and instantaneous gradient information only when needed, instead of accumulating them.
D EXISTENCE OF LOTTERY TICKETS
We perform the following experiment to whether Lottery Tickets exist in setting. We take the sparse network found by RigL and restart training using original initialization, both with RigL and with fixed topology as the original Lottery Ticket Hypothesis. Results in (able(ddemosstraee that training with fixed topology is significantly worse than training with RigL and that RigL does benefit from starting again with the final topology and the original initialization training for twice as long instead of rewiring is more effective. In short, there are no special tickets, with Rigl. all tickets seems win.
Effect of Sparsity Distributions
Effect of Momentum Coefficient
0.78
Frdös-Réryy-Kernel
0.77
Test Accuracy
0.76
Erdös-Rény!
Test Accuracy
0.748
Uniform
0.75
0.74
0.73
0.744
0.72
6.71
0.70
SET
SAFSS
Static
0740
0.9
Sparsity
Sparsity
Figure 7: (left) Effect of sparsity distribution choice sparse training methods different sparsity levels. We average over 3 runs and report the standard deviations for each. (right) Effect of momen- tum value the performance of SNFS algorithm. Setting the momentum coefficient of the SNES algorithm to 0 seems to perform best, suggesting the accumulated values are not important.
14

---

Under review as a conference paper at ICLR 2020
Initialization
Training Method
Test Accuracy
Training FLOPs
Lottery
Static
70.82:00077
0,46x
Lottery
RigL
73.93++0.09
0.46x
Random
RigL
74.55.10.06
0.23x
Random
RigLex
76.06.10.09
0.46x
Table 3: Effect of lottery ticket initialization on the final performance. There are no special tickets and dynamic connectivity provided by Rigl. is critical for good performance.
E EFFECT OF UPDATE SCHEDULES ON OTHER DYNAMIC SPARSE METHODS
In Figure we repeat the hyper-parameter sweep done for Rigl. in Figure riight, using SET and SNFS. Cosine schedule with AT = 50 and a = 0.1 seems to work best across all methods. An interesting observation is that higher drop fractions (a) seem to work better with longer intervals AT. For example, SET with AT 1000 seems to work best with 0.5.
F ALTERNATIVE UPDATE SCHEDULES
In Figure 9
we share the performance of two alternative annealing functions:
Constant:
fdecay = a.
2. Inverse Power: The fraction of weights updated decreases similarly to the schedule used in Zhu & Gupta 2018 8) for iterative pruning: fdecay (t) a Tend )h_ In our experiments we tried &
which is the linear decay and their default k = 3.
Constant seems to perform well with low initial drop fractions like a = 0.1, but starts to perform worse with increasing Inverse Power for k=3 and k=1 (Linear) seems to perform similarly for low a values. However the performance drops noticeably for k=3 when we increase the update interval. As reported by Dettmers Zettlemoyer (2019) linear (k=1) seems to provide similar results as the cosine schedule.
G CALCULATING FLOPS OF MODELS AND METHODS
In order to calculate FLOPs needed for a single forward pass of a sparse model, we count the total number of multiplications and additions layer by layer for given layer sparsity s'. The total FLOPs is then obtained by summing up all of these multiply and adds.
Different sparsity distributions require different number FLOPs to compute a single prediction. For example Erdōs-Renyi- -ea--Renii--eeeeee Kernel distributions usually cause earlier layers to be less sparse than the later layers (see Appendix D. The inputs of earlier layers have greater spatial dimensions, so
Cosine-SET
Cosine-SNFS
0.75
Test Accuracy
Test Accuracy
0.730
0.725
C
01
0.715
03
05
0.5
0.100
Update Interval
Update Interval
Figure 8: Cosine update schedule hyper-parameter sweep done using dynamic sparse training meth- ods SET (left) and SNES (right).
15

---

Under review as a conference paper at ICLR 2020
convolutional kernel that works such imputs will require more FLOPs to compute the output features compared to later layers. Thus, having earlier layers which are less sparse results a higher total number of FLOPs required by model.
Training a neural network consists of 2 main steps:
forward pass: Calculating the loss of the current set of parameters on given batch of data. During this process layer activations are calculated in sequence using the previous activations and the parameters of the layer. Activation of layers are stored in memory for the backward pass.
2. backward pass: Using the loss value as the initial error signal, we back-propagate the error signal while calculating the gradient of parameters. During the backward pass each layer calculates 2 quantities: the gradient of the activations of the previous layer and the gradient of its parameters. Therefore in our calculations we count backward passes as two times the computational expense of the forward pass. We omit the FLOOPs needed for batch normalization and cross entropy.
Dynamic sparse training methods require some extra FLOPs to update the connectivity of the neural network. We omit FLOPss needed for dropping the lowest magnitude connections in our calculations. For given dense architecture with FLOPs I' and sparse version with FLOPs fs, the total FLOPs required to calculate the gradient on single sample computed as follows:
Static Sparse and Dense. Scales with 3 fs and * fo FLOPs, respectively.
Snip. We omit the initial dense gradient calculation since it is negligible, which means Snip scales in the same way Static methods: 3 fs FLOPs.
SET. We omit the extra FLOPs needed for growing random connections, since this op- eration can be done on chip efficiently. Therefore, the total FLOPs for SET scales with 3 fs-
SNFS. Forward pass and back-propagating the error signal needs 2 fs FLOPs. However, the dense gradient needs to be calculated at every iteration. Thus, the total number of FLOPs scales with 2 fs + fD.
RigL. Iterations with no connection updates need * fs FLOPs. However, at every AT iteration need to calculate the dense gradients. This results in the average FLOPs for RigL given by (3<f==AT+2=fs+ff)
(AT+1)
H ADDITIONAL PLOTS AND EXPERIMENTS FOR CIFAR-10
In Figure left, we plot the final training loss of experiments presented in Section to investigate the generalization properties of the algorithms considered. Poor performance of Static reflects itself in training loss clearly across all sparsity levels. Rigl. achieves similar final loss as the pruning, despite having around half percent less accuracy. Training longer with Rigl. decreases the final loss further and the test accuracies start matching pruning (see Figure A performance. These results show that RigL improves the optimization as promised, however generalizes slightly worse than pruning.
Constant
Inverse Power (k=3)
Linear
2440
Test Arcuracy
Test Accuracy
Accuracy
0332
D1
578
Update Interval
Upcate Interval
Update Interval
Figure 9: Using other update schedules with Rigl: (left) Constant (middle) Exponential (k=3) and (right) Linear
16

---

Under review as a conference paper at ICLR 2020
Sparsity Sweep on CIFAR-10
Performance of RigL on CIFAR 10
0.50
Pruning (ERK]
0.42
Training Loss
RigL (ERK)
Test Accuracy
Riglax (ERK)
0.36
0.35
Stitic (ERK)
0.30
Stalic (ER()
022
0.32
015
0.28
Frdōs-Rény--Kere
0.1
Uniform
000 55
0.
0.3
Sparsity
Update Interval
Figure 10: Final training loss of sparse models (left) and performance of RigL at different mask update intervals (right).
In Figure right, we sweep mask update interval AT and plot the final test accuracies. We fix initial drop fraction a 0.3 and evaluate two different sparsity distributions: Uniform and ERK. Both curves follow similar pattern as in Imagenet-2012 2012 sweeps (see Figure 8 and best results are obtained when AT 100.
SPARSITY OF INDIVIDUAL LAYERS FOR SPARSE RESNET-50
Sparsity of ResNet-50 layers given by the Frdōs-Rényi-Kernel sparsity distribution plotted in Figure
J BUGS DISCOVERED DURING EXPERIMENTS
Our initial implementations contained some subtle bugs, which while not affecting the general con- clusion that RigL more effective than other techniques, did result in lower accuracy for all sparse training techniques. We detail these issues here with the hope that others may learn from our mis- takes.
1. Random operations on multiple replicas. We data parallelism split mini-batch among multiple replicas. Each replica independently calculates the gradients using a dif- ferent sub-mini-batch of data. The gradients are aggregated using an ALL-REDUCE oper- ation before the optimizer update. Our implementation of SET, SNFS and Rig/. depended on each replica independently choosing to drop and grow the same connections. However, due to the nature of random operations in Tensorflow, this did not happen. Instead, different replicas diverged after the first drop/grow step. This was most pronounced SET where each replica chose at random and much less so for SNFS and RigL where randomness is only needed to break ties. If left unchecked this might be expected to be catastrophic, but due to the behavior of Estimators and/or TF-replicator, the values on the first replica broadcast to the others periodically (every approximately 1000 steps in our case).
We fixed this bug by using stateless random operations improved slightly (0.1-0.3 % higher on Table
As result the performance of SET
2. Synchronization between replicas. RigL and SNFS depend calculating dense gradients with respect to the masked parameters. However, as explained above, in the multiple replica setting these gradients need be aggregated. Normally this aggregation is automatically done by the optimizer, but in our case, this does not happen (only the gradients with respect the unmasked parameters are aggregated automatically). This bug affected SNFS and RigL. but not SET since SET does not rely on the gradients to grow connections. Again, the synchronization of the parameters from the first replica every approximately 1000 steps masked this bug.
We fixed this bug by explicitly calling ALL-REDUCE the gradients with respect to the masked parameters. With this fix, the performance of RigL and SNFS improved signifi- cantly, particularly for default training lengths (around 0.5-1% improvement).
17

---

Under review as a conference paper at ICLR 2020
80 % Sparse ERK
90 % Sparse ERK
branchh 2000
resto oranon2o
0.588
00523
rests brarchze
2000
00
re22b branch2a
6000
000 041
ns2ooprandhae
00.38
10.923
100
rest: hnerch2w 2.10
p.11
0.538
00923
800
branch2e
2010
00923
2013
301 g2.025
01522
restbbbroce brobbbronnno
g0,025
0.522
resóo oranehdh
0.923
2913
rosacbrorch2e
go,025
10.22
resSc branenbb
0,523
2913
restcbanchhc
redtd hranch2e g1.025
00223
2913
branch2e
2013
0952
rests hneehhe
brothbbondh2
p.312
0.751
resto oeanehdt
0913
0.97
reskk_barch22
p.513
0.751
reste oranehde
0913
0.57
restcbranchic
0.312
restd branch2e
P.513
2013
0057
resed
p.312
branch2e
neve, beb
2013
0057
reseu
p.512
roset oranch2e
0313
3857
restt branchée
p.513
3751
0357
0.979
resso branchée
0257
7881
resi branchee
84057
0.999
branchte
resfe resfe.ceantie cearehob
DV057
979
resictrancia
1e1000
10852
Sparsity
Sparsity
Figure 11: Sparsities of individual layers of the ResNet-50.
18

---

Under review as a conference paper at ICLR 2020
3. SNIP Experiments. Our first implementation of SNIP used the gradient magnitudes to decide which connections to keep causing its performance to be worse than static. Upon discussions with the authors of SNIP, realized that the correct metric is the saliency (gradient times parameter magnitude). With this correction SNIP performance improved dramatically to better than random (Static) even Resnet-500/lmaee ing that picking connections with the highest gradient magnitudes can be so detrimental to training (it resulted in much worse than random performance).
scale. It surpris-
19


Reviews:
[{"review_id": "Skg97KzhKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overview:\n\nThe paper is dedicated to developing a more efficient and powerful dense-to-sparse training method. In order to break the limits of the size of the largest trainable sparse model to that of the largest trainable dense model, the author proposes a dynamic method that updates the network topology via parameter magnitudes and infrequent gradient calculation. In the experiments parts, they conduct extensive studies to show the proposed approach can surpass the previous sota with ResNet-50, MobileNet v1 and v2 on the imagenet 2012. What's more, the author also provides some intuitive explanation about why allowing topology change during the optimization is beneficial. \n\nStrength Bullets:\n\n1. Due to the dynamic network topology, the paper's methods exactly achieve the memory and computation efficient. i) Required memory is only proportional to the size of the sparse model. ii) The amount of computation is proportional to the number of nonzero parameters in the model.\n2. The author performs detailed comparison experiments among different sparsity distribution and different pruning methods. And the results overcome the previous state-of-the-art results.\n3. Fig 5 shows some interesting insight. It suggests that static sparse training may be stuck at some local minima which are isolated from improved solutions. However, the dynamic update has a big chance to avoid this problem.\n\nWeakness Bullets:\n\n1. The author claims that the ticket in the paper does not rely on a \"lucky\" initialization. But it doesn't exclude the possibility that starting from the original initial conditions may give a better performance. Even if the connection is dynamic, we can still record the initial point for each weight. It will be better the author can provide related analysis.\n2. In my opinion, in order to prove dynamic pruning is better than static methods, the author needs to provide a comparison with the previous sota method in it's own setting. i.e. The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks\n\nRecommendation:\n\nI think this paper is a novel work. Although it has some flaws in the experiment design, the motivation and experiment results are conniving enough. So, this is a weak accept.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1gDIdo2FS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method for training sparse network without first training a dense network (e.g. the lottery ticket hypothesis or distillation). The method involves a combination of dynamic pruning of weights coupled with a dynamic \"growing\" of new weights given a novel criterion based on the magnitude of the gradient of the loss. As a result, networks can stay sparse throughout training and testing, leading to a large reduction in computational cost.\n\nThe paper's approach of dynamically changing the topology of networks is an interesting and motivated idea that seems to work rather well. I also appreciate the experiments on MobileNet, a setting where one expects investigations into sparse network architectures to have significant application. Relatedly, I appreciate the importance of the fact that the computational cost of training and evaluating the network is proportional to the sparse model size, which is not normally true for masked dense models. Overall, I found the paper to be very clear and of high quality, and thus I find this to be an interest addition to investigations into the lottery ticket hypothesis.\n\nAs the authors state, the novelty of their method is that they use the gradients with the highest magnitudes to grow connections. This is somewhat intuitive given the role gradients play in gradient descent based optimization, but I was wondering if they had any further intuition as to why this is the right criterion?\n\nIn section 4.3, I was a bit confused by Figure 5. My understanding is that many paths between loss landscape minima follow nonlinear paths -- why is it at all significant that there's a linear barrier? Why are only quadric and cubic Bezier curves used, rather than a more general path finding algorithm?\n\nOverall, this is a nice paper that should be accepted to ICLR.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bye-WT3W9S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a pruning technique called RigL, which performs sparse initialization of the network weights, and allows the network to grow weights during training. The sparse initialization makes the pruning algorithm to be memory- and computation- efficient, unlike existing models that starts with dense network weights. The authors train RigL with three different sparsity distributions that considers the number of input and output nodes, and validate them on various deep convnets for training on ImageNet, on which the model outperforms several existing sparsification methods and even dense counterparts. \n\nPros\n- The proposed model, RigL, is memory- and computation- efficient, and thus allows to train a large network in an efficient manner.\n \n- RigL obtains impressive sparsification performance, even yielding sparse networks that outperform their dense counterparts.\n\nCons\n- The idea of starting from a small, sparse network and expanding it is not novel. DEN [Yoon et al. 18] proposed the same bottom-up approach with sparsely initialized networks, while they allowed to increase the number of neurons at each layer and focused more on continual learning. The authors should compare the two methods both conceptually and experimentally. \n\n- The method is more like a set of heuristics rather than a principled approach, which makes it less appealing. This is not really an issue if the paper includes extensive experimental validation and in-depth analysis, but this is not the case. \n \n- The experimental validation is largely lacking, as the authors only perform experiments on ImageNet and do not compare against recent state-of-the-art Bayesian sparsification methods (SBP, VIB, L0-regularization). Without such extensive experimental validation, it is uncertain whether the result will generalize, given the highly empirical nature of the work. \n\nIn sum, although I believe that the paper proposes a very practical method that is easy to implement and is promising, due to lack of experimental validation against a similar approach, state-of-the-art sparsification methods, and results on more datasets, I temporarily provide the rating of weak reject. I may change my opinion if the authors provide those results during the rebuttal period.\n\n[Yoon et al. 18] Lifelong learning with dynamically expandable networks, ICLR 2018", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: A somewhat new approach to growing sparse networks.  Experimental validation is good, focussing on ImageNet and CIFAR-10, plus experiments on language modelling.  Though efficient in computation and storage size, the approach does not have a theoretical foundation.  That does not agree with the intended scope of ICLR.  I strongly suggest the authors submit elsewhere.
Decision: Reject