Gradient Flow in Sparse Neural Networks and How Lottery Tickets Win
Authors: Utku Evci
Yani Ioannou
Cem Keskin
Yann Dauphin
Venue:  (2021)
Keywords: sparse training
sparsity
pruning
lottery ticket hypothesis
lottery tickets
sparse initialization
initialization
deep learning
gradient flow

Abstract: Sparse Neural Networks (NNs) can match the generalization of dense NNs using a fraction of the compute/storage for inference, and also have the potential to enable efficient training. However, naively training unstructured sparse NNs from random initialization results in significantly worse generalization, with the notable exception of Lottery Tickets (LTs) and Dynamic Sparse Training (DST). In this work, we attempt to answer: (1) why training unstructured sparse networks from random initialization performs poorly and; and (2) what makes LTs and DST the exceptions? We show that sparse NNs have poor gradient flow at initialization and propose a modified initialization for unstructured connectivity. Furthermore, we find that DST methods significantly improve gradient flow during training over traditional sparse training methods. Finally, we show that LTs do not improve gradient flow, rather their success lies in re-learning the pruning solution they are derived from — however, this comes at the cost of learning novel solutions.

Under review as a conference paper at ICLR 2020
GRADIENT FLOW IN SPARSE NEURAL NETWORKS AND HOW LOTTERY TICKETS WIN
Anonymous authors Paper under double-blind review
ABSTRACT
Sparse Neural Networks (NNs) can match the generalization of dense NNs using a fraction of the compute/storage for inference, and have the potential to enable efficient training. However, naively training unstructured sparse NNs from random initialization results in significantly worse generalization, with the notable exceptions of Lottery Tick- ets (LTs) and Dynamic Sparse Training (DST). In this work, we attempt to answer: (1) why training unstructured sparse networks from random initialization performs poorly and; and (2) what makes L.T's and DST the exceptions? We show that sparse NNs have poor gradient flow at initialization and propose modified initialization for unstructured connectivity. Furthermore, we find that DST methods significantly improve gradient flow during training over traditional sparse training methods. Finally, show that LT's do not improve gradient flow, rather their success lies in re-learning the pruning solution they are derived from however, this comes at the cost of learning novel solutions.
Introduction
Deep Neural Networks (DNNs) are the state-of-the-arr method for solving problems in computer vision, speech recognition, and many other fields. While early research in deep learning focused on application to new problems, or pushing sate-of-theeaae art performance with ever larger/more computationally expensive models, broader focus has emerged towards their efficient real-world application. One such focus is on the observation that only a sparse subset this dense connectivity required for inference, as apparent in the success of pruning (Han et al., 2015; Mozer et al., 1989b).
Pruning has a long history in Neural Network (NN) literature, and remains the most popular approach for finding sparse NNs. Sparse NNs found by pruning algorithms (Han al., 2015: Louizos et al., 2017; Molchanov et al., 2017: Zhu et al., 2018) (i.e. pruning solutions) can match dense NN generalization with much better efficiency inference time. However, naively training (unstructured) sparse NN from a random initialization from scratchi. typically leads to significantly worse generalization.
Two methods in particular have shown some success at addressing this problem - Lottery Tickets (LT's) and Dynamic Sparse Training (DST). The mechanism behind the success of both of these methods is not well understood however, e.g. we don't know how find Lottery Tickets (L.Ts) efficiently; while Rigl. (Evei et al., 2020), a recent DST method, requires 5x the training steps to match dense NN generalization. Only in understanding how these methods overcome the difficulty of sparse training can we improve upon them.
A significant breakthrough in training DNNs - addressing vanishing and exploding gradients- - arose from understanding gradient flow both initialization, and during training. In this work we investigate the role of gradient flow in the difficulty of training unstructured sparse NNs from random initializations and from LT initializations. Our experimental investigation results in the following insights:
1. Sparse NNs have poor gradient flow at initialization. In $3.1, $4.1 we show that existing methods for initializing sparse NNs are incorrect in not considering heterogeneous connectivity. We believe we are the first to show that sparsity- aware initialization methods improve gradient flow and training.
Sparse NNs have poor gradient flow during training. In $3.2, $4.2, we observe that even in sparse NN architectures less sensitive to incorrect initialization, the gradient flow during training is poor. We show that DST methods achieving the best generalization have improved gradient flow.
3. Lottery Tickets don't 't improve upon (1) or (2), instead they re-learn the pruning solution. In $3.3, $4.3 we show that a LT initialization resides within the same basin of attraction as the original pruning solution it is derived of, and LT solution is highly similar the pruning solution in function space.

---

Under review as a conference paper at ICLR 2020
2 Related Work
Pruning Pruning used commonly in Neural Network (NN) literature to obtain sparse networks (Castel- lano et al., 1997; Hanson et al.. 1988; Kusupati et al., 2020: Mozer et al., 1989a,;; Setiono, 1997; Sietsma et al., 1988: Wortsman al., 2019). Pruning algorithms remove connections of a trained dense network using various criteria including weight magnitude (Han et al., 2016, 2015; Zhu et al., 2018), gradient-based measures (Molchanov et al., 2016), and 2rddrrder terms based on the Hessian (Hassibi et al., 1993; LeCun et al., 1990). While the majority of pruning algorithms focus on pruning after training, a subset focuses on pruning NNs before training (Lee et al., 2019; Tanaka et al., 2020; Wang et al., 2020). Gradient Signal Preservation (GRaSP) (Wang et al., 2020) is particularly relevant aims to preserve gradient flow, and they observe a positive correlation between initial gradient flow and final generalization. However, recent work of Frankle al., 2020b suggests that the reported gains due to sparsity distributions discovered rather than the particular sub-network. Another limitation of these algorithms is that they don't scale to large scale tasks like Resnet-50 training on ImageNet-2012.
study, since their pruning criteria
Lottery Tickets Frankle et al. (2019a) showed the existence of sparse sub-networks at initialization known as Lottery Tickets - which can be trained to match the generalization of the corresponding dense Deep Neural Network (DNN). The initial work of Frankle et al. (2019a) inspired much follow-up up work. Gale et al. (2019) and Liu et al. (2019) observed that the initial formulation was not applicable to larger networks with higher learning rates. Frankle et al. (2019b, 2020a) proposed late rewinding as solution. Morcos et al. (2019) and Sabatelli et al. (2020) showed that Lottery Tickets (LTs) trained on large datasets transfer to smaller ones, but not vice versa. Frankle al. (2020c), Ramanujan al. (2019), and Zhou et al. (2019) focused on further understanding LTs, and finding sparse sub-networks at initialization. As one might expect, sufficiently large networks would have smaller solutions hidden them. Malach et (2020) studied this and proved the existence of solutions in sufficiently large networks. However, it is an open question whether finding such networks at initialization could be done more efficiently than with existing pruning algorithms.
Dynamic Sparse Training Most training algorithms work on rreedetermnned architectures and optimize parameters using fixed learning schedules. Dynamic Sparse Training (DST), on the other hand, aims to optimize the sparse NN connectivity jointly with model parameters. Mocanu et al. (2018) and Mostafa et al. (2019) propose replacing low magnitude parameters with random connections and report improved general- ization. Dettmers et al. (2019) proposed using momentum values, whereas Evci et al. (2020) used gradient estimates directly to guide the selection of new connections, reporting results that are on par with pruning algorithms. In $4.2 we study these algorithms and try to understand the role of gradient flow in their success.
Random Initialization of Sparse NN In training sparse NN from scratch, the vast majority of pre-exisiting work on training sparse NN has used the common initialization methods (Glorot et al., 2010; He et al., 2015) derived for dense NNs, with only a few notable exceptions. Gale et al. (2019), Liu et al. (2019), and Ramanujan al. (2019) scaled the variance (fan-in/fan-out) of a sparse NN layer according to the layer's ' sparsity, effectively using the standard initialization for a small dense layer of equivalent number of weights as in the sparse model.
3 Analyzing Gradient Flow in Sparse Neural Networks
A significant breakthrough in training very deep NNs arose in addressing the vanishing and exploding gradient problem, both at initialization, and during training. This problem was understood by analyzing the signal propagation within a DNN, and addressed in improved initialization methods (Glorot et al., 2010; He et al., 2015; Xiao et al., 2018) alongside normalization methods, such as Batch Normalization (BatchNorm) (loffe et al., 2015). In our work, following Wang al. (2020), we study these problems using the gradient flow, ( (()) which is the first order approximation" of the decrease in the loss expected after a gradient step. We observe poor gradient flow for the predominant sparse NN initialization strategy and propose solution in $3.1. Then in $3.2 and $3.3 we summarize Dynamic Sparse Training (DST) methods and LT hypothesis respectively.
"We omit leaming rate for simplicity.
2

---

Under review as a conference paper at ICLR 2020
12
by
o(f(a))
19
we
wf
ton,-2
Donse Lisat
9
weight matrix
weight mask
=
fan in
05
Sparsity
(a) Dense Layer
(b) Sparse Layer
(c) Signal Propagation Init.
Figure 1: Glorot/He Initialization for Sparse NN. All neurons in dense NN layer (a) have the same fan-in, whereas a sparse NN (b) the fan-in can differ for every neuron, potentially requiring sampling from a different distribution for every neuron. The initialization derivation/fan-on variant are explained further in Appendix A.I. (c) Std. dev. of the pre-softmax output of LeNet5 with input sampled from a normal distribution, over 5 different randomly-inttilized sparse NN for a range of sparsities.
3.1 The Initialization Problem in Sparse Networks
Here analyze the gradient flow initialization for random sparse NNs, motivating the derivation of a more general initialization for NN with heterogeneous connectivity, such as in sparse NNs. In practice, without a method such as BatchNorm (Ioffe et al., 2015), using the correct initialization can be the difference between being able to train a DNN, or not Table 1). The initializations proposed by Glorot al. (2010) and He et al. (2015) ensure that the output distribution of every neuron in layer is of zero-mean and unit variance, and do this by sampling a Gaussian distribution with variance based on the number inconing/outgoing connections for the neurons in dense layer, as illustrated in Fig. la, which is assumed be identical for all neurons in the layer.
observed for VGG16 in our results (64.1,
In an unstructured sparse NN however, the number of incoming/outgoing connections is not identical for all neurons in layer, as illustrated in Fig. lb. In Appendix A.2 we derive the initialization for this more general case. In Appendix A. we explain in full the generalized Glorot et al. (2010) and He et al. (2015) initialization, in the forward, backward and average the generalized He et al. (2015) initialization for forward propagation, which we used in our experiments.
cases. Here will focus only explaining
For every weight wly xpll in a layer E with nl neurons, and mask (m!)) M E 10.1pal9 1x1pp/xxn'' xn!
19 NN
2
w
fan-inn
m
fan-in 1
the number of incoming connections neuron in layer l.
In the special case of a dense layer where m!) = 1,jij. Eq. (1) reduces to the initialization proposed by (He et al., 2015) since fan-in -nnr-in"""n((-- (1-1) Vi. Using the dense initialization in a sparse DNN causes signal vanish, as empirically observed in Fig. lc), whereas our initialization keeps the variance the signal constant. The initialization proposed by Liu et al. (2019) is special case of ours where it is assumed fan-in; 16 Ef Vi, i.e. all neurons have the same number of unmasked incoming connections in a layer. Surprisingly the initialization of Liu et al. (2019) also preserves the signal in Fig. Ic (discussed in $4.1).
3.2 Gradient Flow during Training and Dynamic Sparse Training
While initialization is important for the first training step, the gradient flow during the early stages of training is not well addressed by initialization alone, shown by normalization methods (loffe al., 2015). Our find- ings show that even with BatchNorm, the gradient flow during training in unstructured sparse NNs is poor.
Recently, promising new approach to training sparse NNs has emerged Dynamic Sparse Training (DST) - that learns connectivity adaptively during training, showing significant improvements over baseline methods that use fixed mask. These methods perform periodic updates the sparse connectivity of each layer: commonly replacing least magnitude connections with new connections selected using various criteria. We consider two of these methods: Sparse Evolutionary Training (SET) (Mocanu et al.,

---

Under review as a conference paper at ICLR 2020
2018), which chooses new connections randomly and Rigged Lottery (RigL) (Evci al., 2019), which chooses connections with high gradient magnitude. RigL improves over SET and matches pruning performance with sufficient training time. Since these methods have only recently been proposed, there a lack of understanding of why and how these methods achieve better results.
3.3 Lottery Ticket Hypothesis
recent approach for training unstructured sparse NNs while achieving similar generalization to the original dense solution is the Lottery Ticket Hypothesis (LTH) (Frankle et al., 2019a). Notably, rather than training a pruned NN structure from random initialization, the LTH uses the dense initialization from which the pruning solution was trained/derived from.
Definition [Lottery Ticket Hypothesis]: Given a NN f with parameter vector @ and an optimization
function ON (J.00) = ON, which gives the optimized parameters of f after N training steps, there exists sparse sub-network characterized by the binary mask M such that for some iteration K, O (J (J.0k M) performs as well as O (f.0)* + M, whereas the model trained from another random initialization 0g. using the same mask O ff..+MM). typically does not". Frankle et al. (2019a) initially claimed the LTH held for K 0, but later revised this to N > K 20 (Frankle et al., 2019;; Liu et al., 2019).
LT' enjoy significantly faster convergence compared to regular NN training but require the connectivity mask as found by the pruning solution (Frankle et al., 2019a) along with values from early training (Frankle et al., 2019b). Given the importance of the early phase of training (Frankle et al., 2020c; Lewkowyez et al., n.d.). it is natural to ask about the difference hetween lottery tickets and the solution they are derived from (i.e. pruning solutions). Answering this question can help understand if the success of LTss is primarily due to its relation to the solution, or if we can identify generalizable characteristics that help with sparse NNs training.
4 Experiments
Here we show empirically that (I) sparsity- initialization improves gradient flow at initialization for all methods, and achieves higher generalization for networks without BatchNorm, (2) the mask updates of DST methods increase gradient flow and create new negative eigenvalues in the Hessian; which we believe to be the main factor for improved generalization, (3) lottery tickets have poor gradient flow, however they achieve good performance by effectively re-learning the pruning solution, meaning they do not address the problem of training sparse NNs in general. Our experiments include the following settings: LeNet5 on MNIST, VGG16 on ImageNet-2012 and ResNet-50 on ImageNet-2012. Experimental details can be found in Appendix B'.
4.1 Gradient Flow at Initialization
In this section, we measure the gradient flow over the course of the training (Fig. 2) and evaluate the performance of our generalized He initialization method (Table 1), and that proposed by Liu al. (2019), over the commonly used masked dense initialization. Additional gradient flow plots for the remaining methods are shared in Appendix C. Sparse NN initialized using the initialization distribution of a dense model (Scratch in Fig. 2) start in a flat region where gradient flow is very small and don't make any early progress. I Learning starts after 1000 iterations for LeNet5 and 5000 for VGG-16, however, their generalization is sub-optimal. Liu et al. (2019) claim their proposed initialization has no empirical effect as compared to the masked dense initialization'. Although technically incorrect (see $3.1), our results show their method to be largely effective our proposed initialization. This indicates that the assumption of a mask having roughly uniform mask sparsity is sufficient for the masks we considered. Both of these initializations remedy the vanishing gradient problem at initialization (Scratch+ in Fig. 2) and result in better generalization for all methods. For instance, improved initialization results in an 11 11% improvement Top-1 accuracy for VGG16 (62.52 51.81). While initialization is extremely important
*See Frankle et al. (2019b) for details. indicates element-wiss multiplication, respecting the mask. 'Implementation of sparse initialization, Hessian calculation and code for reproducing our experiments will be open sourced with the final version. Additionally we provide videos that shows the evolution of Hessian during training under different algorithms in the supplementary material.
Models with BatchNorm and skip connections are less affected by initialization, and this is likely why the authors did observe this effect.
4

---

Under review as a conference paper at ICLR 2020
Table 1:
Results of Trained Sparse/Dense Models from Different Initializations. The initializations proposed Eq. (1) (Ours) and Liu ot al. (2019) improve gencralization consistently over masked dense (Original) except for RosNer50. Note that VGG16 trained without a sparsity-awar: initialization fails to converge in some instances. Baseline corresponds to the original dense architecture, whereas Small Dense comesponds smaller dense model approximately the same parameter count as the sparse models.
MNIST
ImageNet-2012
LeNet5 spanse)
VGGI6 (80% spanse
ResNet50 spans))
Bascline
99.21=00.07
19.25=00.13
76.75=0.12
Lottery Small Dense
98 26:10.27
0.10:10.01
75.75=0.12
98.21.10..6
61.75.10.09
71.95
Original
Original
Liu
Original
Scratch 62 22.99442.116
96 06.64-0.83
97.70=0.099
51,81++3.02
62.71+00.5
62.52:0.100
70.58:00118
10.72=0.16
70.63+0022
SET
63 33:242.444
97.77=0.31
98.16::0.06
53.55:21.03
63.19:10.26
63. 13:10.15
72.93:20.27
72.77=0.27
72.56:0. 14
RigL.
80.82:1:4474
98.14.00.17
98.13:10.09
37.15:126.00
63.56.10.06
74,41:0005
74.3810.10
74.38.0001
Used late-roindinng
K 5000))
Lobory
18.
Gradient Norm
Smithh
Gradient Norm
Gradient Norm
Riglt
2-
Scrithh
Scratch
Scratch+
Small Denoe
Small
2..
Iteration
Iteration
Iteration
(a) LeNet5
(b) VGG-16
(c) ResNet-50
Figure 2: Gradient Flow of Sparse Models during Training, Gradient flow during training averaged over multiple runs, '+' indicates training runs with proposed sparse initialization and Small Dense corresponds to training of a dense network with same number parameters as the sparse networks. Lottery ticket runs for ResNet-50 include late-rewinding.
0.5
Rigl
RigL+
Grad Grad Norm
0.4
Rigl
Inverted
Graa Norm
RigL+ Inverted
0.3
SET
0.2
10
16a
tteration
Iteration
(a) ResNet-50
(b) LeNet5
Figure 3: Effect of Mask Updates in Dynamic Sparse Training. Effect of mask updates on the gradient norm. RigL Inverted chooses connections with least magnitude. We measure the gradient norm before and after the mask updates and plot the A. '+' indicates proposed initialization and used in MNIST experiments.
for NNs without BatchNorm and skip connections, its effect on modern architectures, such as Resnet-50, is limited (Evci et al., 2019; Frankle et al., 2020b; Zhang et al., 2019). We confirm these observations in our ResNet-50 experiments in which, despite some initial improvement in gradient flow, our initialization seems to have effect on final generalization. We observe significant increases in gradient norm after each learning rate drop (due to increased variance in gradients), which suggests studying gradient norm in the later part of the training might not be helpful. On the other hand, observe significant difference in gradient flow during training between sparse networks and small dense models of similar parameter count. Can the performance gap between static-sparse and dense models be explained by this difference?

---

Under review as a conference paper at ICLR 2020
Rendon (Sawich)
Intielaationa
(Sparie) Infisiization
Scretch
Pruning
Basin
Solatnn
Lattery
Pruning Bosin
Solution
Figure 4: Lottery Tickets Are Biased Towards the Pruning Solution, Unlike Random Initialization. cartoon illustration of the loss landscape sparse model, after it is pruned from a dense solution to create LT net-net A lottery ticket initialization is within the basin of attraction of the pruned model's solution. In contrast a random initialization is unlikely to be close to the dense solution's 's basin.
4.2 Gradient Flow during Training and Dynamic Sparse Training
In Fig. 2 we observed improved gradient flow for RigL. In this section we focus on those iterations in which the sparse connectivity is updated, and measure the change in gradient flow along with the Hessian spectrum. We also run the inverted baseline for RigL (RigL Inverted), in which the growing criteria is reversed and connections with least gradient magnitudes are activated.
DST methods such RigL replace low saliency connections during training. Assuming the pruned connec- tions indeed have a low impact on the loss, we might expect to see increased gradient norm after new con- nections are activated, especially in the dients. In Fig. 3 we confirm that Rigl. updates increase the norm of the gradient significantly, especially in the first half of training, whereas SET, which picks new connections randomly, seems be less effective at this. Using the inverted RigL criteria doesn't It improve the gradient flow, as expected, and without this RigL's performance degrades (73.83+0.112 12 for ResNet-50 and 77.67 for LeNet5). These results suggest that improving gradient flow early in training might be the key for training sparse networks and that is what RigL appears to be doing. Additional plots for different initialization methods are shared in Appendix C.
of Rigl., which picks new connections with high magnitude gra-
RigL. falls short of matching Small-Dense performance while constantly having higher gradient flow during the training, which highlights limitation of looking solely at gradient flow. When the gradient is zero, or uninformative due to the error term of the approximation, analyzing the Hessian could provide additional insights (Ghorbani et al., 2019; Papyan, 2019; Sagun et al., 2017). In Appendix E, we show the Hessian spectrum before and after sparse connectivity updates. After RigL updates we observe more negative eigenvalues with significantly larger magnitudes as compared to SET. On the other hand, small dense models have smaller positive outlier eigenvalues while having significantly larger negative ones; which is again a sign of better conditioned optimization. We leave investigating the relationship between gradient flow and the Hessian further future work.
4.3
Why Lottery Tickets are Successful
We found that LTTs do not improve gradient flow, either at initialization, or early in training, as shown in Fig. 2. This may be surprising given the apparent success of LTs, however the questions posed in $3.3 present an alternative hypothesis for the ease of training from a LT initialization. Here we present results showing that indeed (1) LTs initializations are consistently closer to the pruning solution than a random initialization, (2) trained LTs (i.e. LT solutions) consistently end up in the same basin as the pruning solution and (3), LT solutions are highly similar to pruning solutions under various function similarity measures. Our resulting understanding of L.T's in the context of the pruning solution and the loss landscape is illustrated in Fig. 4.
Experimental Setup
To investigate the relationship between the pruned and LT solutions we perform experiments on two models/datasets: 95% sparse LcNet5 architecture (LeCun et al., 1989) trained on MNIST (where the original LT formulation works, i.c. K 0), and an 80% sparse ResNet-50 (Wu et al., 2018) on ImageNet-209 2012 (Russakovsky et al., 2015) (where K =0 doesn't 't work (Frankle et al., 2019b)), for which use values from K = 2000 6==6th epoch). In both cases, find a LT initialization by pruning each layer of a dense NN separately using magnitude-based iterative pruning (Zhu et al., 2018). Further details about our experiments can be found in Appendix B.
We train 5 different models using different seeds from both scratch (random) and LT initializations, the results of which are in Figs. 5b and 5e. These
Lottery Tickets Are Close to the Pruning Solution
Note: We Rel. activation functions, unlike the original architecture (I.eCun al., 1989).

---

Under review as a conference paper at ICLR 2020
aaay
May End
20-
MNIST/LeNet5
Training Loss
Ind
10
LT
Scratch
AcCtest
98.52
97.19
dinse
13.61
17.46
-10
d dyinal
8.03
25.64
Lockary
-20
Lotaayy
20
20
06
Interpolation Coefficient (a)
(a) MDS Projection
(b) L.2 Distances
(c) Loss Interpolation
Luilery
200
Lonary End
ImageNNe-2011 /ResNet-50
Senalin
100
Training Loss
Screten
0
Method LT
Scratch
Accrest
75.74
71.16
donst
147.12
200.44
d
39.35
215.98
167
-200
200
150
250
Interpolation Coeffidint (o)
(d) MDS Projection
(e) L2 Distances
(I) Loss Interpolation
Figure 5: MDS Embeddings/L.2 Distances: (a, d): 2D Multi-dimensional Scaling (MDS) embedding of sparse NNs with the same connectivity/mask: (b, e): the average 1.2-distance between pruning solution and other derived sparse networks; (c, f): linear path between the pruning solution (a = 1.0) and LT/scratch at both initialization, and solution (end of training). Top and bottom rows are for MNIST/LeNet5 and ImageNet-201 20e respectively.
networks share the same pruning mask and therefore lie in the same solution space. We visualize distances between initial and final points of these experiments in Figs. 5a and 5d using 2D Multi-dimenssoonl Scaling (MDS) (Kruskal, 1964) embeddings. LeNet5/MNIST: In Fig. 5b, provide the average 1.2 distance to the pruning solution at initialization (dsnst), and after training (dat))) We observe that LT initializations start significantly closer to the pruning solution on average (dinst 13.61 v.s. 17.46). After training, LTs end up more than 3x closer to the pruning solution compared to scratch. Resnet- Siaieee-55/mmme/eeee20000 We observe similar results for Gesnnet-50/mageNeeer 201- LT's again, start closer the pruning solution, and solutions are 5x closer fdii = 39.35 v.s. 215.98). With these observations, non-random initial loss values for LT initialization reported first by (Zhou et al., 2019) seem reasonable. LT's are biased towards the pruning solution they are derived from, but are they in the same basin?
Lottery Tickets are in the Pruning Solution Basin Investigating paths between different solutions is a popular tool for understanding how various points parameter space relate to each other in the loss landscape (Draxler et al., 2018; Evei et al., 2019; Fort et al., 2020; Frankle et al., 2020a; Garipov et al., 2018; Goodfellow et al., 2015). For example, Frankle et al. (2019b) use linear interpolations to show that LTs always go the same basin" when trained in different data orders. In Figs. 5c and 5f we look at the linear paths between pruning solution and other points: LT inttialization/sslutiin and random (scratch) initialization/solution Each experiment is repeated 5 times with different random seeds, and mean values are provided with 80% confidence intervals. both experiments we observe that the linear path between LT initialization and the pruning solution decreases faster compared the path that originates from scratch initialization. After training, the linear paths towards the pruning solution change drastically. The path from the scratch solution depicts loss barrier; the scratch solution seems be in a different basin than the pruning solution'. In contrast, LTs are linearly connected to the pruning solution in both small and large-scale experiments indicating that LT' have the same basin of attraction as the pruning solutions
We define a basin as a set of points, each of which is linearly connected at least one other point in the set. 'This is not always true, it is possible that non-linear low energy paths exist between two solutions (Draxler et al., 2018; 8; Garipov et al., 2018), but searching for such paths outside the scope of this work.
7

---

Under review as a conference paper at ICLR 2020
Table 2: Ensemble & Prediction Disagreement. We compare the function similarity (Fort et al.. 2020) with the original pruning solution and ensemble generalization over sparse models, trained from random initializations and LTs. As baseline, we also show results for 5 pruned models trained from different random initializations. See Appendix F for the complete results.
Initialization
(Top-1) Test Acc.
Ensemble
Disagree.
Disagree. w/ Pruned
LT
98.52-+0.02
98.58
0.0013=000006
0.0089=0.000
Scratch
97.04+0.115
98.00
0.0316=0.0023
0.0278=0.0020
LeNe15 MNIST
Scratch (Diff. Init.)
97.19-+0.33
98.43
0.0352-0.0037
0.0278=0.0032
Prune Restart
98.60:10.01
98.63
0.0027=0.0003
0.0077=0.0003
Pruned Soln.
98.53
5 Diff. Pruned
98.30++0.23
99.07
0.0214=0.0023
0.0197=0.0019'
LT Scratch
75.73++0.08
76.27
0.0894000000
0.0941=0.0009
ResNet50
71.1610.13
74.05
0.2039-0.0013
0.2033-0.0012
ImageNet
Pruned Soln. 5 DifT. Pruned
75.60
75.65.10.13
77.80
0.1620-0.0008
0.1623-0.0011
Herr we compare 4 diffferent pruned models with the pruning solution LT/Seratch are derived from.
they are derived from. While it seems likely, these results do not however explicitly show that the LT and pruning solutions have learned similar functions.
Lottery Tickets Learn Similar Functions to the Pruning Solution Fort et al. (2020) motivate deep ensembles by empirically showing that models starting from different random initializations typically learn different solutions, as compared to models trained from similar initializations. Here we adopt the analysis of (Fort et al., 2020), but in comparing LT initializations and random initializations using fractional disagreement. The fractional disagreement with the pruning solution is the fraction of class predictions over which the LT and scratch models disagree with the pruming solution they were derived from. In Table we show the mean fractional disagreement over all pairs of models. We rum two versions of scratch training: (1) Scratch (Diff. Ini.. different weight initialization and different data order (2) Scratch same weight initialization and different data order for 5 different seeds the experiments are ran. Finally, we restart training starting from the pruning solution (Prune Restart) using, again, 5 different data orders.
The results presented in Table 2 suggest that all 5 LTs models converge on solution almost identical to the pruning solution. Interestingly, the LT models even more similar each other (Disagree. column) than the pruning solution, possibly because they share an initialization and training is stable (Frankle et al., 2019b). The disagreement of Prune Restart solutions with the original pruning solution matches the disagreement of lottery solutions; showing the extent of similarity between LTT and pruning solutions.
Our results show that having a fixed initialization alone can not explain the low disagreement observed for LT experiments as Scratch solutions obtain an average disagreement of 0.0316 despite using the same initialization, which is almost 10 times more than the LT solutions (0.0043). Finding different LT initialization is costly, however using different initialization in Scratch (Diff. Init.) training is free as the initializations are random. Using different initializations we can obtain more diverse solutions and thus achieve higher ensemble accuracy. As suggested by the analysis of Fort et al. (2020), ensembles of different solutions are more robust, and generalize better, than ensembles of similar solutions. An ensemble of 5 LT models with low disagreement doesn't significantly improve generalization as compared to an ensemble of 5 different pruning solutions with similar individual test accuracy. We further demonstrate these results by comparing the output probability distributions using the Kullback-Leibler Divergence (KL), and Sensen-Shannoe Divergence (JSD) in Appendix F.
Implications: (a) Rewinding of LTs. Frankle al. (2019b, 2020a) argued that LTs work when the training is stable, and thus converges to the same basin when trained with different data sampling orders. In $4.3, we show that this basin is the same one found by pruning. and since the training converges to the same basin as before, we expect to see limited gains from rewinding if any. This is partially confirmed by Renda et (2020) which shows that restarting the learning rate schedule from the pruning solution performs better than rewinding the weights. (b) Transfer of LTs. Given the close relationship between LT' and pruning solutions, the observation that LTs trained on large datasets transfer to smaller ones, but not vice versa (Morcos al., 2019; Sabatelli al., 2020) can be explained by common observation in transfer leaming: networks trained in large datasets transfer to smaller ones. (c) LT's Robustness to Perturbations, Frankle al. (2020e) and Zhou et al. (2019) found that certain perturbations, like only using the signs of weights
8

---

Under review as a conference paper at ICLR 2020
at initialization, do not impact LT generalization, while others, like shuffling the weights, do. Our results bring further insights to these observations: As long as the perturbation is small enough such that a LT stays in the same basin of attraction, results will be good as the pruning solution. (d) Success of LTs. While it is exciting to see widespread applicability of L.T's in different domains (Brix et al., 2020; Li et al., 2020; Venkatesh al., 2020), the results presented in this paper suggest this success may he due to the underlying pruning algorithm (and transfer learning) rather than LT initializations themselves.
5
Conclusion
We attempted to answer the questions of (1) why training unstructured sparse networks from random initialization performs poorly and; (2) what makes Lottery Tickets (LTs) and Dynamic Sparse Training (DST) the exceptions? We identified that randomly initialized unstructured sparse Neural Networks (NNs) exhibit poor gradient flow when initialized naively and proposed an alternative initialization that scales the initial variance for each neuron separately. Furthermore we showed that modern sparse NN architectures are more sensitive to poor gradient flow during early training rather than initialization alone. We observed that this is somewhat addressed by ofth-offthee-at DST methods, such as Rigged Lottery (Rigl.), which significantly improves gradient flow during early training over traditional sparse training methods. Finally, we show that LTs do not improve gradient flow at either initialization or during training. but rather their success lies in effectively re-learning the original pruning solution they are derived from. We showed that a LT' initialization resides within the same basin of attraction the pruning solution and, furthermore, when trained the LT solution learns a highly similar solution to the pruning solution. These findings suggest that LTs are fundamentally limited in their potential for improving the training of sparse NNs more generally.
References
Brix, Christopher, Parnia Bahar, and Hermann Ney (2020). ''Suceesfullyy Applying the Stabilized Lottery Ticket Hypothesis to the Transformer Architecture". In: ArXiv. URL: https::t/////ttte arg/abs/ 2005. , 03454.
Castellano, Giovanna. Anna Maria Fanelli, and Marcello Pelillo (1997). "An iterative pruning algorithm for feedforward neural networks". In: IEEE Transactions on Neural Networks. ISSN: 1045-9227. DOI:
10. 1.0.1199/70 72. 000100977.7779999 572092.
Dettmers, Tim and Luke Zettlemoyer (2019). "Sparse Networks from Scratch: Faster Training without
Losing Performance". In: ArXiv. URL: http: / /arxiv. org/ abs /1907 04 04.0
Draxler, Felix, Kambis Veschgini, Manfred Salmhofer, and Fred A Hamprecht (2018). "Essentially No
Barriers in Neural Network Energy Landscape". In: International Conference Machine Learning.
Evci, Utku, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen (2020). "Rigging the Lottery:
Making All Tickets Winners". In: Proceedings of Machine Learning and Systems 2020.
Evei, Utku, Fabian Pedregosa, Aidan N. Gomez, and Erich Flsen (2019). 'The Difficulty of Training
Sparse Neural Networks". In: ArXiv, URL: http: / arxiv org/ abs / 111999966... 10732.
Fort, Stanislav, Huiyi Hu, and Balaji Lakshminarayanan (2020). "Deep Ensembles: A Loss Landscape Perspective" In: International Conference on Learning Representations.
Frankle, Jonathan and Michael Carbin (2019a). "The Lottery Ticket Hypothesis: Finding Sparse, Trainable
Neural Networks". In: 7th International Conference on Learning Representations (ICLR).
Frankle, Jonathan, Gintare Karolina Dziugaite, Daniel M. Roy, and Michael Carbin (2019b). "Stabilizing
the Lottery Ticket Hypothesis". In: ArXiv. URL: ht attps: / /aaxiivvvvv.////////a////aaaavva org/ abs/1903 01 611. (2020a). "Linear Mode Connectivity and the Lottery Ticket Hypothesis". In: Proceedings of the Interna- tional Conference on Machine Learning.
(2020b). "Pruning Neural Networks Initialization: Why are We Missing the Mark?" In: ArXiv. URL:
https: //rxiv org/ alos/ 2009. 08576.
Frankle, Jonathan, David Schwab, and Ari S. Morcos (2020c). "The Early Phase of Neural Network Training". In: International Conference on Learning Representations.
Gale, Trevor, Erich Elsen, and Sara Hooker (2019). "The State of Sparsity Deep Neural Networks". In: abg/abs/// ArXiv. URL: http: /ttp:///aaiiv..// /rg/ abs/ / 1 1902. 09574.
Garipov, Timur, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew Gordon Wilson (2018).
"Loss Surfaces, M Connectivity, and Fast Ensembling of DNNs". In: Advances in Neural Information Processing Systems.
Ghorbani, Behrooz, Shankar Krishnan, and Ying Xiao (2019). "An Investigation into Neural Net Optimiza- tion via Hessian Eigenvalue Density". In: Proceedings of the 36th International Conference on Machine

---

Under review as a conference paper at ICLR 2020
Learning. URL: http:/ htttt:://prcceeinnnoe ngg. mllr. ptress/v97/ghoraaiii htmll.
Glorot, Xavier and Yoshua Bengio (2010). "Understanding the difficulty of training deep feedforward neural networks". In: Proceedings of the 13th International Conference Artificial Intelligence and Statistics (AISTATS).
Goodfellow, Ian J., Oriol Vinyals, and Andrew M. Saxe (2015). "Qualitatively characterizing neural network optimization problems". In: International Conference on Learning Representations.
Han, Song, Xingyu Liu, Huizi Mao, Jing Pu, Ardavan Pedram, Mark A. Horowitz, and William J. Dally (2016). "EIE: Efficient Inference Engine on Compressed Deep Neural Network". In: Proceedings of the 43rd International Symposium on Computer Architecture.
Han, Song, Jeff Pool, John Tran, and William Dally (2015). "Learning both weights and connections for efficient neural network". In: Advances in neural information processing systems.
Hanson, Stephen José and I Lorien Y. Pratt (1988). "Comparing biases for minimal network construction with back- propagatiin""" In: Proceedings of the 1st International Conference on Neural Information Processing Systems (NIPS). Morgan Kaufimann.
Hassibi, B. and D. Stork (1993). "Second order derivatives for network pruning: Optimal Brain Surgeon".
In: Advances in Neural Information Processing Systems. He, Kaiming, Xiangyu Zhang. Shacqjig Ren, and Jian Sun (2015). "Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification". In: IEEE International Conference on Computer Vision (ICCV).
loffe, Sergey and Christian Szegedy (2015). "Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift". In: Proceedings of the 32Nd International Conference on International Conference on Machine Learning.
Kruskal, J. (1964). "Multidimensionall scaling by optimizing goodness of fit to nonmetric hypothesis". In: Psychometrika. DOE: 10. BE 020228 89665.
Kusupati, Aditya, Vivek Ramanujan, Ragha Somani, Mitchell Wortsman, Prateek Jain, Sham Kakade, and
Ali Farhadi (2020). "Soft Threshold Weight Reparameterization for Leamable Sparsity". In: Proceedings of the International Conference Machine Learning.
LeCun, Yann, Bernhard Boser, John S. Denker, Donnie Henderson, Richard E. Howard, Wayne Hubbard, and Lawrence D. Jackel (1989). "Backpropagation applied to handwritten zip code recognition".. In: Neural Computation. ISSN: 0899-7667. DOI: 10. 1 1 62/neco. 1 1899.1. 1.4.............. 4.541. LeCun, Yann, John S. Denker, and Sara A. Solla (1990). "Optimal Brain Damage". In: Advances in Neural Information Processing Systems.
Lee, Namhoon, Thalaiyasingam Ajanthan, and Philip H. S. Torr (2019). "SNIP: Single-shot Network Pruning based on Connection Sensitivity". In: International Conference on Learning Representations
(ICLR), 2019.
Lewkowyez, Aitor, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari (n.d.). "The large learning rate phase of deep learning: the catapult mechanism". In: Arxiv O. URL: https:
// //arxivvoon org http//d////0/ 02218.
Li, Bai, Shiqi Wang, Yunhan Jia, Yantao Lu, Zhenyu Zhong, Lawrence Carin, and Suman Jana (2020).
"Towards Practical Lottery Ticket Hypothesis for Adversarial Training". In: ArXiv. URL: https:
/ //arxiv. orgg / abs/ 2003. 05733.
Liu, Zhuang, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell (2019). "Rethinking the Value of Network Pruning". In: International Conference on Learning Representations.
Louizos, Christos, Karen Ullrich, and Max Welling (2017). "Bayesian compression for deep learning.. In: Advances in Neural Information Processing Systems.
Malach, Eran, Gilad Ychudai, Shai Shalev-Shwartz, and Ohad Shamir (2020). "Proving the Lottery Ticket Hypothesis: Pruning is All You Need". In: ArXiv. URL:: http:/ /arxiiiv ixxvvv v. org/ abs 220/2000220 2200200055 00585. Mocanu, Decebal Constantin, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta (2018). "Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science".. In: Nature Communications.
Molchanov, Dmitry, Arsenii Ashukha, and Dmitry Vetrov (2017). "Variational Dropout Sparsifies Deep Neural Networks". In: Proceedings of the 34th International Conference on Machine Leamiing Proceed- ings of Machine Learning Research. International Convention Centre, Sydney, Australia: PMLR. URL: http:/ / /twp/eeoieeeeooeooooooooo ngs . ml r. .press/ v /mo 1 chanovl 7a .htmml
Molchanow, Pavlo, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz (2016). "Pruning Convolutional Neural Networks for Resource Efficient Inference". In: ArXiv. URL: http: / /aaxivvvvv/..////// .rg/ abs/
1611. 06440.
Morcos, Ari, Haonan Yu, Michela Pagannii, and Yuandong Tian (2019). "One ticket to win them all: gener- alizing lottery ticket initializations across datasets and optimizers". In: Advances in Neural Information
10

---

Under review as a conference paper at ICLR 2020
Processing Systems 32.
Mostafa, Hesham and Xin Wang (2019). "Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization.. In: Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA. URL: http:
/ /pproceddiggs ml presss / /v9 fm 9a. .tml.
Mozer, Michael C. and Paul Smolensky (1989a). "Using Relevance to Reduce Network Size Automatically".
In: Connection Science. DOI: 10. 1080/10000000 095400044000 98 909915 1266..6...
(1989b). "Skeletonization: A Technique for Trimming the Fat from a Network via Relevance Assess- ment". In: Advances in Neural Information Processing Systems 1.
Papyan, Vardan (2019). "Measurements of Three-Level Hierarchical Structure in the Outliers in the Spectrum of Deepnet Hessians". In: ArXiv. URL: https: : / /arxivi www.v.org/aaa....e...... abs / 901. 08244. Ramanujan, Vivek, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari (2019). "What's Hidden in a Randomly Weighted Neural Network?" In: ArXiv. URL: ht http:://ara
org/abs /191s 13299.
Renda, Alex, Jonathan Frankle, and Michael Carbin (2020). "Comparing Rewinding and Fine-tuning in
Neural Network Pruning". In: International Conference on Learning Representations. URL: https: //openreeveww. www.:/ee//ea.... forum? iid gS JONKBB.
/
Russakovsky, Olga, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, An-
drej Karpathy, Aditya Khosla, Michael Bernstcin, Alexander C. Berg, and Li Fei-Fei (2015). "ImageNet
Large Scale Visual Recognition Challenge". In: International Journal of Computer Vision (IJCV).
Sabatelli, Matthia, Mike Kestemont, and Pierre Geurts (2020). "On the Transferability of Winning Tickets /arg//bb//// in Non-Natural Image Datasets". In: ArXiv. URL:: https: : / //aaxiiv.orrg orr.v..rr/aae.. abs 22005 05232.
Sagun, Levent, Utku Evci, V. Ugur Güney, Yann Dauphin, and Léon Bottou (2017). "Empirical Analysis of the Hessian of Over-Parametrizee Neural Networks". In: International Conference on Learning Representations.
Setiono, Rudy (1997). "A Penalty- Function Approach for Pruning Feedforward Neural Networks". In: Neural Computationn DOI: 10. 11 62 /ew... 1997. 9. 1. 185.
Sietsma, Jocelyn and Robert J.F. Dow (1988). "Neural net pruning-why and how". In: IEEE International 988 23864.
Conference on Neural Networks. DOI: 1 0 1 101/
Tanaka, Hidenori, Daniel Kunin, Daniel I.. K. Yamins, and Surya Ganguli (2020). "Pruning neural networks
without any data by iteratively conserving synaptic flow". In: ArXiv. URL: https: /ttss///axxta /arxiv. org/ abs/2005 05467.
van der Walt, S., S. C. Colbert, and G. Varoquaux (2011). "The NumPy Arra: Structure for Efficient Numerical Computation". In: Computing in Science Engineering.
Venkatesh, Bindya, Jayaraman J. Thiagarajan, Kowshik Thopalli, and Prasanna Sattigeri (2020). "Calibrate and Prune: Improving Reliability of Lottery Tickets Through Prediction Calibration". In: ArXiv. URL: /tgg/as/////.oooo..///..//aea / 202 03875.
Wang. Chaoqi. Guodong Zhang, and Roger Grosse (2020). "Picking Winning Tickets Before Training by Preserving Gradient Flow". In: International Conference on Learning Representations. URL: https:
/ //openreview net forum? SerrrmmiddSsssaaa d=SkgsACVKH..
Wortsman, Mitchell, Ali Farhadi, and Mohammad Rastegari (2019). "Discovering Neural Wirings". In:
Advances in Neural Information Processing Systems.
Wu, Songtao. Shenghua Zhong, and Yan Liu (2018). "Deep residual learning for image steganalysis". In:
Multimedia Tools and Applications.
Xiao, Lechao, Yasaman Bahri, Jascha Sohl- -ick-iiks,,,n, Samuel S Schoenholz, and Jeffrey Pennington (2018).
"Dynamical isometry and mean field theory of cnns: How train 10,000-layer vanilla convolutional neural networks". In: International Conference on Machine Learning (ICMI).
Zhang, Hongyi, Yann N. Dauphin, and Tengyu Ma (2019). "Fixup Initialization: Residual Learning Without Normalization". In: International Conference on Learning Representations.
Zhou, Hattie, Janice Lan, Rosanne Liu, and Jason Yosinski (2019). "Deconstructing lottery tickets: Zeros, signs, and the supermask". In: Advances in Neural Information Processing Systems.
Zhu, Michael and Suyog Gupta (2018). "To Prune, or Not to Prune: Exploring the Efficacy of Pruning for Model Compression". In: International Conference Learning Representations Workshop.
11

---

fan out Under review as a conference paper at ICLR 2020
wa
We 12
wf
tang=2
weight mask
weight matrix
=
fan in
(a) Dense Layer
(b) Sparse Layer
Figure 6: Glorot/He Initialization for Sparse NN. (Glorot et al., 2010; He et al., 2015) restrict the outputs of all neurons to be zero-mean and of unit variance. All neurons in dense NN layer (a) have the same fan-in/fan-out, whereas in a sparse NN (b) the fan-in/fan-out can differ for every neuron, potentially requiring sampling from different distribution for every neuron. The fan-in matrix contains the values used in Eq. (I) for each neuron.
A Glorot/He Initialization Generalized to Neural Networks with Heterogeneous Connectivity: Full Explanation/Derrvation
Here we derive the full generalized initialization for both the forwards/backwards cases (i.e. fan-in/fan-out), refer Fig. 6 for an illustration of how the connectivity for the fan-in/fan-out cases are determined for each neuron.
A.1 Generalized Glorot/He Initialization: Backwards, Forwards and Average Cases
For every weight w/f Wnllxxul-- in a layer & with nl4 neurons, connecting neuron in layer to neuron j in layer (6-1) with (!e-1) neurons, and weight mask [m]]] =M] E [0.1] xnle-1)
10 ~N (0.
fan-in,,
(forward)
Glorot et al. (2010):
where fan-out 1n (fan-in! +fan-ou!") (average)
(backward)
He et al. (2015):
wif (0)
where,
n!
x2
fan-inn
Σ mi
fan-oud
18]
> m
are the number of incoming and outgoing connections respectively. In the special case of dense layer where m!y 1, 1.vij. Eq. (1) reduces to the initializations proposed by (Glorot et al., 2010; He al., 2015)
since fan-in 19] Vi, fan-out - yl.
A.2 Derivation: Fixed Mask, Forward Propagation
Given sparse NN, where the output of a neuron as is given by, a!" f (4!*). where 10
Σ le my w aj [t-1] where ml e Ml and w/ will are the mask and weights re- [6-1] the output of the previous layer. Assume the mask M x
spectively for layer l, and a constant, where 1 19 xn is indicator matrix.
12

---

Under review as a conference paper at ICLR 2020
As in Glorot et al. (2010)
ensure Var(a;)) Var(a, and mean(a. - Assume that f(r) z for x close to 0, e.g. in the case of f(x) (a)) and that wij and ag [t-1] are independent,
Var(a (1
Var(2 (
a- 1
(
16 [e-1)
Var
m kj
ij ag
(4)
n [f-1]
[6] 16 Var mij Wij
a (1-11)
(independent sum) (5)
xlc-1]
mij (ml/) Var 20l (6-11)
[00) 2
mm 18]
constant, Var(cc))c22V (6)
1=1
n|t-1]
Σ
[6] Var
wij 11/1//11111
m E10011, (m..) =m
(m))))
mij
1e-11
Σ
mij
[e]
Var(w Varla, 1)
(independent product)
Assume Var(w: [0] and (ar(ak--))) = Var(an [f--- i.c. the variance of any of the outputs of the previous layer are the same. Therefore we can simplify Eq. (8).
Var (w) ( Vn.m, ie. the variance of all weights for given neuron are the same,
n n/
Var(a/-11) 1)
Σ
my Var(w! Var(a,_1)
(9)
j=1
12te
=Var(w,)) Var(a (e 11-11|
mij
(10)
Let neuron i's number of non-masked weights be fan- where fan-in, 19
= Σ 5== mij- then
[--1]
[4]
Var(a, (e-11] " ffan-in! 18 Var(w: Var(a)--1)
(11)
Recall, Var(a, 1 ) Var(a (
+ >Va((w!))= fan-int
(12)
[d] Therefore, in order to have the output of each neuron a; in layer l to have unit variance, and mean 0, we need sample the weights for each neuron from the normal distribution,
(13)
fan-in
where of is the sparsity of weights of the neuron with output a,, For the ReLU activation function. following the derivation in He et al. (2015),
(w) [w]]])~ ~N
(14)
san-in!!)
A.3 Fixed Mask: Backward Pass
Given sparse NN, where the output of a neuron ag is given by, a f (24 where 19 18 [6-1] where m Ml and w/f wid are the mask and weights respectively m.j w dz
13

---

Under review as a conference paper at ICLR 2020
for layer E, and 03 [e-1] the output of the previous layer. Assume the mask M E 1nn/0xn" is constant, where 1 xnl an indicator matrix, and let L(0- (Wit) ( be the loss we are optimizing.
As in Glorot et al. (2010), from the Backward-propagation standpoint, we want to ensure
Var( OL ) -Var 82
)), and mean( ot ) Assume that (0( 10,
0z;
az.
OT. Var(
OL Var(
(15)
10
dag
dal!-1
19
AL [9
Var
miy by
(16)
Oz
Var
mi wi
[4]
ØL 22p 16
(independent sum)
(17)
maas
Var
OL Wis 02,
mm is constant, Var(eX)=
[4]
(18)
mig
181 Var
[e] ØL Wis
mm 18
E(0.1), (m))) m
(19)
Oz!11
Σ
18) mij
Var(w!g) 101 Varl
0L
(independent product)
(20)
Assume Var(w!g) = Var(u (8) Vn,m i.e. the variance of all weights for given neuron are the same, and Varl aL
0zl )= Var( aL ). i.e. the variance of the output gradients of each neuron at layer 7 are the same.
a=!! Then we can simplify Eq. (20).
Var
OL
mi
Var(w
10)
Var(
OL
(21)
Ozy
0z1
1=1
aL
=Va((w?))
10 Var(
2z1
10
mij
(22)
Let neuron i's number of non- masked weights be denoted fon-todfan-out fan-out! where fan-ou,) = ml
-i= then
Var( 0zm
ØL.
= fan--out Var(w 16
Var( O2.
ØT.
(23)
ØT.
= Var( ØT.
Recall, Var(
0x 02!!
1
+ VVa(wu!))
(24)
fan-out
[0]
Therefore, in order to have the output of each neuron a; in layer l to have unit variance, and mean we need to sample the weights for each neuron from the normal distribution,
(w ~~ > fan-in!!)
(25)
where of is the sparsity of weights of the neuron with output 0, For the ReLU activation function, following the derivation He et al. (2015).
(u ~N N/1. fan-in!!"
(26)
14

---

Under review as a conference paper at ICLR 2020
Table 3: $4.3: Experiment Details/Hypeppaameete Initial Learning Rate (LR), LR Schedule (Sched.), Batchsize (Batch.), Momentum (m), Weight Decay (WD), tuant fend and are the pruning starting iteration, end iteration, and mask update frequency respectively.
Dataset
Model
looi
Epochs
Batch.
LR
Sched.
WD
Sparsity
Pruning
Laan
Lnnd
f
MNIST
LeNet5
11719
30
128
0.05
Cosine 0.9
0
95%
3000
7000
100
ImageNet ResNet50
32000
=102
4096
1.6
Step'
0.9
x 44
80%
5000
8000
2000
Step schedule has a linear warm-up in first 5 epochs and decreases the learning rate by a factor of 10 at epochs 30,70 and 90.
Table 4: $4.1: Experiment Detaals/Hyprppaametters Initial Learning Rate (LR), LR Schedule (Sched.), Batchsize (Batch.), Momentum (m²) Weight Decay (WD), Initial Drop Fraction (Drop.), feed and f are the pruning mask update frequency and end iteration respectively. LeNer5+ row corresponds the LeNet5 experiments with our sparse initialization, whereas LeNet5 is the regular masked initialization.
Dataset
Model
tooi
Epochs
Batch.
LR
Sched.
m
WD
Sparsity
DST
Drop.
f
fead
MNIST
LeNet5
11719
30
128
0.05
Cosine
0.9
1x
95%
0.3
500
11719
ResNe150
32000
4096
1.6
0.3
100
ImageNet
VGG16
128000
102
1024
0.04
Step"
0.9
1
80%
0.1
500
25000
Step schedule has a linear warm-up in first 5 epochs and decreases the learning rate by a factor of 10 at epochs 30,70 and 90.
B Experimental Details
B.1 Details of Experiments in Section 4.3
The training hyper-parameters used in $4.3 are shared in Table 3. All experiments in this section start with pruning experiment, after which the sparsity masks found by pruning used perform LT experiments. We use iterative magnitude pruning (Zhu et al., 2018) in our experiments, which is well studied and more efficient pruning method as compared to the one used by Frankle et al. (2019a). Our pruning algorithm per- forms iterative pruning without rewinding the weights between intermediate steps and requires significantly less iterations. We expect our results would even more pronounced with additional rewinding steps.
We use SGD with momentum in all of our experiments. Scratch and Lottery experiments use the same paper-parameters. Additional specific details of our experiments are shared below.
LeNet5 We prune all layers of LeNet5, so that they reach 95% final sparsity (i.c. 95% of the parameters zeros). We choose this sparsity, since at this sparsity, start observing stark differences between Lottery and Scratch terms of performance. We set the weight decay to zero, similar to the MNIST experiments done in the original LT paper (Frankle et al., 2019a) and do grid search learningrrates-(0. (0.000s=0001,,,,0.000. 1,0.2,0.05,0002.000. }. Loss values for the linear interpolation experiments are calculated on the entire training set.
ResNet50 We prune all layers of ResNet50, except the first layer, so that they reach 80% final sparsity, In this setting rewinding to the original initialization doesn't 't work. hence we use values from 6th epoch. Loss values for the linear interpolation experiments are calculated using 500,000 images from the ImageNet-2012 training set.
B.2 Details of Experiments in Section 4.1 and 4.2
Training hyper-parameters used for these experiments are shared in Table 4.
MNIST In this setting. the hyper-parameters almost same in $4.3, except able weight decay as it brings better generalization. We do a grid search over weight- 1.0000,,.00005.5
0000000000.000001100000000.....0
and Gemming-atsss0000020050000000000 and
15

---

Under review as a conference paper at ICLR 2020
Gredient Norm
Gradient Norm
Soothh Somothe
Gradient Norm
Sconom-de Groncme Scaazitt the
"
Iteration
lteration
lteration
(a)
(b)
(c)
Figure Gradient Flow of Sparse LeNet-5s during Training. Gradient flow during training averaged
over multiple runs, '+' indicates training runs with our proposed sparse initialization. '+Iiu"' indicates initialization proposed by Liu et al., 2019. 'He" suffix refers to He initilization where 'scale=2" and 'fanin options are used for the variance scaling initialization.
pick the values with top test accuracy. We the masks found by pruning experiments in all of our MNIST experiments in this section to isolate the effect of the initialization. We simplify the update schedule of Dynamic Sparse Training (DST) methods such that they decay with learning rate. This approach fits well, since the original decay function used in these experiments is the cosine decay which is the same as our learning rate schedule. We scale learning rate such that it matches the initial drop fraction provided. Mask update frequency and initial drop fraction are chosen from a grid search of (50, 100, 500} (od00.0,0.110.33. respectively. To allow fair comparison, we use Glorot scaling all of our initializations (i.e. scale=1 and we average fan-in fan-out values) as it is the default initialization for Tensorflow layers and our results shows that it out-performs He initialization by a small margin with the hyper-parameters used. Using He initialization brings similar results.
Hessian calculation The Hessian is calculated on full training set using Hessian-vector products. We mask our network after each gradient call and calculate only non-zero rows. After calculating the full Hessian, use numpy eigh (van der Walt et al., 201 to calculate eigenvalues of the Hessian.
ImageNet-20012 In this setting, hyper-parametens are almost the same as in $4.3 except for VGGI6 ar- chitecture, where we use smaller batch size and learning rate. For all DST methods, we use a cosine drop schedule Detimers et al., 2019 and hyper-parameto parameters proposed by Evci et al. (2019). For VGG, we reduce the mask update frequency and the initial drop fraction, as we observe better performance after doing a grid search (50, 100, 500) and 1,030.0, respectively. We also use non-uniform (ERK) sparsity distri- bution among layers as described Evci et al. (2020), since we observed that brings better performance.
C Additional Gradient Flow Plots
Here we share additional gradient flow figures for method/inittalizztion combinations presented in 3 and 2.
In Fig. 7b, we show the gradient flow for DST methods and scratch training. Using RigL helps improves gradient flow with both initialization; helping learning to start earlier than regular Scratch training. Sparse Evolutionary Training (SET) seem have limited effect on the gradient flow.
In Fig. 7b, we share gradient flow when the scaled initialization of Liu et al., 2019 is used. Similar to the proposed initialization, we observe improved gradient flow for cases. Different than our initialization however, RigL. doesn't improve gradient flow in this setting: highlighting an interesting future research direction on the relationship between initialization and the DST methods.
In Fig. 7c, share gradient flow when He initialization is used instead of Glorot initialization. We observe that Scratch training starts learning faster in this case. Gradient flow seems to be similar for other sparse initialization methods.
In Fig. 8, we share gradient flow improvements after DST updates on connectivity for different initialization methods. ResNet-50 curves match the results in Fig. 3. LeNet5 curves however to be adversely affected by poor initialization at the beginning of the training. We start observing improvements with Rigl. when the learning starts (around the 400 iteration).
16

---

Under review as a conference paper at ICLR 2020
A Grad Norm
0.25
RigL- SET+
4 Grad Norm
0.50
Rigl
SET
0.25
0.00
0.00
10
Iteration
Iteration
(a) ResNet-50
(b) LeNet5
Figure 8: Effect of Mask Updates in Dynamic Sparse Training. Effect of mask updates on the gradient norm. We measure the gradient norm before and after the mask updates and plot the A. '+' indicates proposed initialization and used in MNIST experiments.
Table 5: Results of Trained Fully-Connected MNIST Model from Different Initializations.
MNIST
Fully-Coneccted NN (98% sparse)
Baseline
98.55:10.04
Lottery
97.73:+0.11
Small Dense
91.69:+1.85
Original
Liu et al.
Ours
Scratch
94,40+14.00
96.66:10.18
96.70-+0.12
SET
96.4910.36
96.56:10.22 96.76:10.19
96.48=10.10
RigL
96.82.+0.25
96.94=0.12
D Fully Connected Neural Network Experiments on MNIST
this section we repeat our experiments from $4.1 using different sparse initialization methods, and analyz- ing gradient flow, for standard 2-layer fully-connected NN with 2 hidden layers of size 300 and 100 units. We use the same grid used in LeNet5 experiments for hyper-parameter selection. Best results were obtained with leamning rate of 0.2, weight decay coefficient of 0.0001 and an mask update frequency of 500 (used in DST methods). The rest of the hyperparameters remained unchanged from the LeNet5 experiments.
The results of training with various initialization methods is shown in Table 5. Although the results not as drastic as with LeNet5, we see that here too sparsity aware initialization (the proposed initialization, and that of Liu (Liu al., 2019)) shows a significant improvement in the test accuracy of Scratch, and RigL or our proposed initialization, although not quite reaching lottery or RigL accuracy. Finally, we see no significant effect on SET training, with none of the initialization variants having significant increase over any of the others, although the Liu (Liu et al., 2019) initialization does marginally better.
The gradient flow of this model shown Fig. 9, While we see moderate improvements to Scratch gradient flow early on in training with our proposed initialization (a). Rigl. shows significantly higher gradient flow throughout training, in particular after mask updates (b), mirroring the results of LeNet5. The interpolation graphs in (c) only differ slightly from that of LeNet5, again showing that our results for LeNet5 broadly hold for the fully-connected model.
E Hessian Spectrum of LeNet5
Given a loss function L and parameters f, we can write the first order Taylor approximation of the change in loss AL= AL=L(0++)) L( 10- _(0 after single training step with the learning rate <>> as
AL ~
(27)
Note that as long the error is small, gradient descent is guaranteed to decrease the loss by amount proportional to VL which we refer as the gradient flow. practice large learning rates are used, and the first order approximation might not be accurate. Instead can look at the second order
17

---

Under review as a conference paper at ICLR 2020
Gredient Norm
9gl SET
Scorm Scoren
Soroch
Training Loss
Gradd
Iteration
Iteration
(b) Gradient Flow improvements after
do
us Interpolation Coefficient (al
connectivity updates
(a) Gradient Flow during training
(c) Interpolation
Figure 9: Sparse 300-100 MLP experiments. Gradient flow during training averaged over multiple runs, '+' indicates training runs with our proposed sparse initialization.
approximation of AL:
o AL*-aVLO0) H(OVLI))))
(28)
where (0) is the Hessian of the loss function. The eigenvalue spectrum of Hessian can help us understand the local landscape (Sagun et al., 2017), and help identify optimization difficulties (Ghorbani et al., 2019). For example. if and when the gradient is aligned with large magnitude eigenvalues, the second term of Eq. (28) can have significant effect the optimization L. If the gradient is aligned with large positive eigenvalues, it can prevent gradient descent from decreasing the loss and harm the optimization. Similarly, if is aligned with negative eigenvalues can help to accelerate optimization.
We show the Hessian spectrum before and after the topology updates in Fig. 10. After RigL. updates we observe new negative eigenvalues with significantly larger magnitudes. We also see larger positive eigenvalues, which disappear after few iterations" In comparison, the effect of SET updates on the Hessian spectrum seems limited.
We also evaluate the Hessian spectrum of LeNet5 during the training. In Fig. 11b, we observe similar shapes for each method on the positive side of the spectrum, however, on the negative side dense models seem to have more mass. We plot the magnitude of the largest negative eigenvalue to characterize this behaviour Fig. 1aa. We observe a significant difference between sparse and dense models and observe that sparse networks trained with RigL have larger negative eigenvalues.
Comparing Function Similarity
Table 6 gives full list of comparison metrics of the predictions the test set for LeNet5 MNIST and ResNet50 on ImageNet-2012, in particular here we also compare the output probability distributions using relevant metrics.
"We share videos of these transitions in supplementary material.
18

---

Under review as a conference paper at ICLR 2020
Table Cnsemble/Predicttinn Disagreement order to show the function similarity of LTT the pruning solution, we follow the analysis of (Fort al., 2020), and compare the function similarity and ensemble generalization over 5 sparse models trained using random initializations and LT's with the original pruning solution they are derived from. The fractional disagreement is the puirwise disagreement of class predictions over the test set, as compared within the group of sparse models. and as compared to the pruned model whose mask they were derived from. Kullback-Leee Leibler Divergence (KL) and Jensen- Shannon Divergence (JSD) compare the prediction distributions over all the test samples.
JSD w/ Pruncdd
0.0159+000000
0.0157 1..002
0.002710.000
0.0103++0.000
JSD Pruned
553.70133.5 3355
3847.0 #26.0
2755. (05-000++4400 1.96
0.0033+
0.0140 +0,0004
0.1506 +0.0100
0.1468 #0,0295
0.0105 10.0001
0.0752 #0.0133 13
787.20
3316.0 #13.2
2760.0 +16.8
5-model JSD
S-model JSD
KL Pruned
0002
0.0506+0.0228
0.06501000000
0.00191100011
0.0438$0.02411
KL w/ Pruned
3605.0.113 011114
20442 #178
00:5.99
0.0030++0 0004 0.0039++0
13087.0:+550
13087
Pairwise KL
0.0917+0.0122
0.135810.0200
0.001410.0001
0.0741+0.0107
Pairwise KL.
3325.011.64
15787 1005
143
13158
5 pruning solutions found with different random initialization. one of which is the pruning solution above. Here we compare different pruned models with the pruning solution the LT/Seratch are derived from.
Disagree. w/ Pruned
Disagree. w/ Pruned
0.1623+:0.0111 "M
0.0089++0.000 1.0278+0.0022
0.002
0.027810.0002
0.007710.0003
00000000999
0.08411000009 0. 0.2033310.0012
0.0197
Pairwise Disagree.
0.0043++000000 0000
0.0316++0.000 0023
0.0352-10.000 0.0377
0.0027 10.0003
0.021 10:14::00000 0023
Pairwise Disagree.
0.089410.00088
0. 0.2089 0013
0.1 0.1620=0.00M 0.0088
00088
This is the pruning solution that the LT and scratch models are derived from.
Ensemble
Ensemble
98 58.58
98. 43
98. 63
99.00 07
76.27
74.05
77.78
98.00
Test Acc. (Top-1)
Test Acc. (Top-1)
+0002
+0.15
+:033
10.01
98. 30 #0.23
75. 7..700000000
71.16 #0.13
75.65 +0.13
0.7554
98. 53
98.55 58.52
97.04
97.19 19
98. 60
ImageNer- ImageNez-012/RsssWert 201222/eee/e 50
Pruned Diff. Init."
Pruned w/ Diff. Init."
Scratch (DifT. Init.)
MNIST/LeNNeS
Init. Method
Pruned Soln."
Prune Restart
Init. Method
Pruned Soln.'
Scratch
Scratch
LT
LT
19

---

Under review as a conference paper at ICLR 2020
(SET) Iteration: 200
(RigL) Iteration: 200
10a
After Before
13a-
After
Before
135-
Density
10a3
10-3
10
10"
10
10
20
30
10
Iteration: 1000
Iteration: 1000
10a
After
After
Before
Before
105
105
Density
10-2
10-2
10
10
10
10
10
Figure 10: Hessian spectrum before and after mask updates: (left) SET (right) RigL. Similar to Ghorbani
et al., 2019, we estimate the spectral density of Hessian using Gaussian kemels.
20

---

Under review as a conference paper at ICLR 2020
100
minl
10
RigLt
SET+
10-2
Scratch
Scratch+
Small Dense
5000
10000
Iteration
Iteration:200
Iteration:500
10
Righ-
RgL-
Scratche
Scranche
Small Denoe
Small Dense
10
10"
Density
Density
10
10
10a
10-1
10
10
20
Iteration:2000
Iteration: 1000
10"
10a
Right Scratch
Screthh
Small Denie
10"
10"
Density
Density
10"
10"1
10
10"4
25
50
(b)
Figure 11: MNIST Hessian spectrum experiments.
21


Reviews:
[{"review_id": "mqlycatelq5", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "Summary:\n\nThe paper is clear and very well written. It makes important steps towards understanding if sparse convolutional neural networks can represent a substitute for their dense counterparts. Moreover, it unveils the relation between the performance of sparse neural networks and gradient flow. Based on this relation, it explains also why the dynamic sparse training approach has higher potential of improving sparse neural networks in the future, while lottery tickets are limited by the performance of the pruning solutions from which they are derived. The last but not the least, the paper introduces a simple and practical method specially designed to initialise sparse networks weights.\n\nStrong points:\n\n•\tThe paper brings novel basic knowledge and understanding of sparse neural networks.\n\n•\tThe extensive set of experiments is well-designed, very informative, and support the paper claims.\n\n•\tThe fundamental study performed in this paper is timely and has the potential of advancing seriously the field.  \n\n\nWeak Points:\n\n•\tWhile the abstract and some other parts of the paper discuss about deep neural networks in general, the experiments are solely focused on convolutional neural networks. I believe that extending them also to other types of networks would improve the overall quality of the paper.\n\nFor the discussion phase, I suggest to the authors to consider the weak point and the following minor comments:\n\n1) I find very interesting that any sparse training method cope much better with the ResNet architecture than with the VGG architecture. It is easy to observe this in Table 1. Do you have any idea why is this happening? Is this the effect of skip connections?\n\n2) Can you add in figure 3 the “+” version of the training algorithms for ResNet-50 and the version without “+” for LeNet5?\n\n3) The relation between Hessian, gradient flow, and sparse training raised my curiosity, but I agree with the authors that this investigation can be let for future work.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ehP_ZwJZuMU", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "##########################################################################\n\nPaper Summary:\n\nThis paper presents an empirical study of sparse deep nets, either obtained by sparsification methods such as “dynamic sparse training” or by pruning according to the lottery ticket hypothesis.\nThe main contribution of this work is to study gradient flow both at initialisation and during training, and to propose an extension of known initialisation methods that works for sparse networks.\nIn addition, this work also attempts at explaining why lottery tickets are successful, despite sharing similar problems related to the gradient flow, when compared to other sparsification methods.\n\n##########################################################################\n\nReasons for score: \n\nOverall, I like this kind of empirical study, where authors set the stage for important questions and attempt at answering them with a thorough empirical study. My major concern for accepting this work relates to the depth of contributions. In my humble opinion, the proposed generalisation of “He’s initialisation” could have have been the main (only?) focus of this work, with additional experiments and considerations: relation to other sparsity inducing methods (not only DST), a better understanding of the interaction between initialisation, Batch normalisation and skip connections, …\nInstead, the presentation strategy in this paper is to illustrate several findings but, due to space constraints, in a more shallow manner. This choice dilutes the contributions too much. \n\n##########################################################################\n\nPositive points: \n\n1) Empirical work that addresses an important topic, that of sparse NN. Questions are well motivated, and sufficiently well described, although they have the slightly negative effect of diluting the overall take home message from reading this paper.\n\n2) The proposed extension to a known initialisation method to cope with issues related to gradient flow during the early stages of training is reasonable, and effective as shown by the experiments.\n\n3) The experiments on gradient flow during training and the ones on lottery tickets confirm either known results or intuition. They can be viewed as a reproducibility study, which is commendable. Some by products of the study indicate important properties of LT, which are of direct practical relevance, e.g. rewinding strategies.\n\n\n##########################################################################\n\nNegative points:\n\n1) The proposed generalisation of He’s method is not sufficiently exploited. Focusing on the forward pass, the idea is to initialise weights on a per neuron basis, using the mask computed by the sparsification method. As the authors notice, the work by Lui et al. achieves similar performance (Fig 1.c) and in many cases it outperforms the proposed method (Tab.1, bold results). This calls for a better understanding of the advantages of the proposed method. Furthermore, the interaction of “sparse initialisation” with batch normalisation and skip connections is not sufficiently studied: in Fig.2 all methods appear similar. Finally, the fact that a “small but dense” network achieves better results (LeNet on MNIST, Tab1), and does not suffer from gradient flow problems (Fig.2 c) is interesting and calls again for further study.\n\n2) The results on gradient flow during training are only superficially commented, although the authors hint at additional ideas based on second order approximations of the loss, i.e. considering the Hessian and its eigen-spectrum. Overall, the take home message from Fig.3 confirms the known behaviour of DST methods such as RigL. Albeit interesting, in my humble opinion this results seem to be given more “real estate” on the paper than it deserves, subtracting space for the main contribution on a new initialisation scheme.\n\n3) The results on lottery ticket could enjoy some improvements on the terminology, which is a minor remark. Indeed, it would be easier to refer to: 1) IMP solution <-> pruning solution; 2) Random init/final <-> start/end; 3) LT init/final <-> start/end. My main concern with this set of results is that on the one hand, they are somehow expected, especially with respect to the large literature available on the topic. It is not bad per se to collect in one coherent piece of work previous observations and place them in a thorough experimental framework. However, I have problems with the following.\na) The notion of “closeness” as shown in Fig 5 a,d and reported in fig 5 b,e is the result of a dramatic dimensionality reduction. Similar techniques have been used in other contexts (e.g. Hao Li, et al. “Visualizing the Loss Landscape of Neural Nets.” NIPS, 2018) and the warnings are to take results with a grain of salt. That said, it is expected — by construction — to find that LT final networks are close to the IMP solution.\nb) The argument used to confirm that LT are in the basin of the IMP solution is based on path connectivity and, as the author also note in a foot note in page 7, studying in detail this path is outside the scope of the paper. The geometry of the loss landscapes is in general very complex (especially when there is no Batch normalisation nor skip connections, which have the effect of smoothing it): I am not sure it is correct to claim that if two solutions (that is the params of a neural net) have the same loss and they are connected by a linear path, then it is necessary true that they lie in the same basin. Even if results in Tab.2 on the disagreement are compelling, it might still not be necessarily true that the two compared models are the same instance of function approximation.\nc) As a minor remark, the implications of the results in Sec 4.3 are interesting and valuable, but I failed to understand properly the connection to the empirical study on the “distance” between IMP solutions and LT final solutions.\n \n\n#########################################################################\n\nAdditional comments:\n\nI found this paper well written in most parts (just a minor comment on the terminology used in one sub-section). I liked this work and I think it has plenty of potential. \nAs an humble suggestion, would it make sense to attempt at focussing more the message, and insist on the main contribution of the paper as per a new initialisation scheme, or was this not seen as sufficient in light of the results from Liu et al. (2019).", "extra_scores": {}, "extra_text": {}}, {"review_id": "Iynm0T7BFVZ", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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\nSummary:\nThis paper tries to answer the following two questions: i) why training unstructured sparse networks from random initiation perform poorly? 2) what makes LTs and DST the exception? The authors show the following findings:\n1. Sparse NNs have poor gradient flow at initialization. They show that existing methods for initializing sparse NNs are incorrect in not considering heterogeneous connectivity. Improved methods are sample initialization from a dynamic gaussian whose variance is related to the fan-in numbers. fan-in = fan-out rule plays an important role here and improves the gradient flow.\n2. Sparse NNs have poor gradient flow during training. They show that DST based methods achieving the best generalization have improved gradient flow.\n3. They find the LTs do not improve gradient flow, rather their success lies in re-learning the pruning solution they are derived from.\n\n\nStrength bullets:\n1. The idea is very interesting. I appreciate the novel analysis. The proposed methods are well-motivated.\n2. The paper is well written and easy to understand.\n3. The finding is surprising but the experiment design is poor which I will list more detailed limitations in the weakness sections. I like the idea, I will raise my score if the authors can completely address my confusion and concerns.\n\n\nWeakness bullets:\n1. For Table 1, a Strong baseline is missing. Why not compare with the performance of the lottery ticket setting? I think it is a more natural baseline than SET and RigL.\n2. In my opinion, there is a must-do experiment: Lottery ticket mask + proposed initialization and compare it to LT and random tickets. Because the LT mask + random reinitialization = random tickets fail in the previous literature. According to the explanation in the paper, it can also be the problem of random reinitialization. Thus, strong supportive evidence is that show proposed modified random reinitialization + LT mask can surpass random ticket performance.\n3. Missing details what is the pruning ratio of each stage in iterative magnitude pruning? The appendix only tells me the author using 95% and 80% sparsity, why pick these two sparsity? Because this sparsity gives the extreme matching subnetworks? And the author uses iterative magnitude pruning, if they follow the original LTH setting, pruning 20% for each time. Then the sparsity should be 1-0.8^i, how to achieve 95% and 80%?\n4. What is the definition of \"pruning solution\"? Is it the obtained mask or initialization or subnetworks contains both mask and initialization? Super confused\n5. Conflicted experiments results with Linear Mode Connectivity and the Lottery Ticket Hypothesis paper, ResNet 50 IMP LT on ImageNet without Early weight rewinding can not have good linear mode connectivity. However, the pruning solution and LT solution have good linear mode connectivity. It is wired, even for two LTs (ResNet 50 IMP LT on ImageNet) trained with the same initialization in different data orders, they do not have a linear path where interpolated training loss is flat, as evidenced in figure 5 in the paper \"Linear Mode Connectivity and the Lottery Ticket Hypothesis\". Early weight rewinding is needed for the presented results while I think the author did not use it. \n6. The comparison in Table 2 is unfair. Scratch settings are trained from five different random initialization, while LT settings are trained from the same initialization with different data orders. LT setting results should also be from different initialization, otherwise can not achieve the conclusion that \"Lottery Tickets Learn Similar Functions to the Pruning Solution\".\n\nMinor:\n1. The definition of LTH in 3.3 \"perform as well as O^N(f,\\theta)*M\", why there is M? It should be the full dense model without the mask, right?\n\n------ Post Rebuttal------\n\nThanks to the authors for the extra experiments and feedback!\n\n[Lottery baseline for Table-1] Although RigL does not need dense network training, it cost more to find the mask (Table 2 of the RigL paper).\n\n[Random tickets] Random Ticket = LT mask + random re-initialization rather than random pruning + random init. The front one will be much more interesting. \"Because the LT mask + random reinitialization = random tickets fail in the previous literature. According to the explanation in the paper, it can also be the problem of random reinitialization. Thus, strong supportive evidence is that show proposed modified random reinitialization + LT mask can surpass random ticket performance.\" I personally do the experiment that performing proposed initialization on random tickets and the performance is unchanged. Of course, there may exist lots of reasons for the results. I will not degrade the paper according to my experiments.\n\nOther concerns are will-addressed. Thanks!\n\nAlthough I do like the idea of this paper, I think it might need to be revised and resubmitted, incorporating the extensive discussion presented by all the reviewers. I tend to keep my scores unchanged. But I don’t think this is 100% a clear reject and depending on the opinions of the other reviewers I would not feel that accepting this paper was completely out of bounds.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-pZuChbkVqt", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 presents three key hypotheses for sparse NN training dynamics and provides empirical studies and observations to verify them. This review will first provide general comments and then specific ones on each hypothesis. \n\nMain comments:\n\nPros: Three messages that the authors try to convey are important and interesting to the audiences in pruning. It is an observational paper which provides insights on 1) what is a good initialization of the for sparse NN training 2) why DST can achieve good generalization, and 3) is LTH really different from pruning. \n\nCons: The presentation of the paper needs work. The high-level structure is good and clear but for each paragraph, the logic flow is hard to follow. For example, in a very key paragraph on P7: “Lottery Tickets Learn Similar Functions to the Pruning Solution”, I have to read repeatedly and infer inner logics of each sentence to see the conclusion. \n\nHypotheses:\nI appreciate identifying the problem of naive initialization of sparse NN and connecting it with gradient flow. However, a new proposal for initialization here (as the major contribution) is unnecessary and actually negatively affects the credits of the true contribution. The results presented in table 1 are not very impressive. It is ok to just compare original and liu et al, and provide insights in an observational paper.\nThe observations provide one possible explanation on why DST might work. The authors could try to test this in different architectures (even beyond CNNs) to see if they are widely held. If so, it is potentially a good metric or analysis tool for sparse NN training.\nI am not fully convinced by the third hypothesis. First, the models and datasets for ensemble and prediction disagreement are too limited while the conclusion is very strong. Also I think a more appropriate statement could be Lottery Tickets Learn Similar Functions to the Pruning Solution than random /scratch since that is the only thing you are comparing with.\n\nMinor comment:\n\nIt would be interesting to see if all the conclusions hold in other models besides CNNs.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows empirically that training unstructured sparse networks from random initialization performs poorly as sparse NNs have poor gradient flow at initialization. Besides, the authors argue that sparse NNs have poor gradient flow during training. They show that DST based methods achieving the best generalization have improved gradient flow. Moreover, they find the LTs do not improve gradient flow, rather their success lies in re-learning the pruning solution they are derived from. I read the paper and the reviewers discussed the rebuttal. Although all the reviewers found the rebuttal helpful and they all agree that the paper is decently well written and has some clear value, the majority believes that further observations are required for making the paper and its hypothesis convincing. There are also some recent related work on initialization of pruned networks, e.g. by rescaling their weights at initialization. I believe, adding the discussion of such related techniques and making the connection to existing work will greatly strengthen the paper and provides more evidence to support its claims.



Decision: Reject