Mode Connectivity and Sparse Neural Networks
Authors: Jonathan Frankle
Gintare Karolina Dziugaite
Daniel M. Roy
Michael Carbin
Venue:  (2020)
Keywords: sparsity
mode connectivity
lottery ticket
optimization landscape

Abstract: We uncover a connection between two seemingly unrelated empirical phenomena: mode connectivity and sparsity. On the one hand, there is growing catalog of situations where, across multiple runs, SGD learns weights that fall into minima that are connected (mode connectivity). A striking example is described by Nagarajan & Kolter (2019). They observe that test error on MNIST does not change along the linear path connecting the end points of two independent SGD runs, starting from the same random initialization. On the other hand, there is the lottery ticket hypothesis of Frankle & Carbin (2019), where dense, randomly initialized networks have sparse subnetworks capable of training in isolation to full accuracy.

However, neither phenomenon scales beyond small vision networks. We start by proposing a technique to find sparse subnetworks after initialization. We observe that these subnetworks match the accuracy of the full network only when two SGD runs for the same subnetwork are connected by linear paths with the no change in test error. Our findings connect the existence of sparse subnetworks that train to high accuracy with the dynamics of optimization via mode connectivity. In doing so, we identify analogues of the phenomena uncovered by Nagarajan & Kolter and Frankle & Carbin in ImageNet-scale architectures at state-of-the-art sparsity levels.

Under review as a conference paper at ICLR 2020
MODE CONNECTIVITY AND SPARSE NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We introduce instubility analysis, framework for assessing whether the outcome of optimizing a neural network robust to SGD noise. It entails training two copies of network on different random data orders. If error does not increase along the linear path between the trained parameters, we say the network stable. Instability analysis reveals new properties of neural networks. For example, stan- dard vision models are initially unstable but become stable early in training; from then on, the outcome of optimization is determined up to linear interpolation.
We leverage instability analysis to examine iterative magnitude pruning (IMP), the procedure underlying the lottery ticket hypothesis. On small vision tasks, IMP finds sparse matching subnetworks that can train in isolation from initialization full accuracy, but it fails to do so in more challenging settings.
We find that IMP subnetworks are matching only when they are stable. In cases where IMP subnetworks are unstable at initialization, they become stable and matching early in training. We augment IMP to rewind subnetworks to their weights early in training, producing sparse subnetworks of large-scale networks, including Resnet-50 for ImageNet, that train to full accuracy.
INTRODUCTION
The lottery ticket hypothesis (Frankle & Carbin, 2019) conjectures that neural networks contain sparse subnetworks that are capable of training in isolation from initialization to full accuracy. The sole empirical evidence in support of the lottery ticket hypothesis is a series of experiments using procedure called iterative magnitude pruning (IMP). IMP returns a subnetwork of the original, randomly initialized network by training the network to completion, pruning the lowest-magnitude weights (Han et al., 2015), and resetting each remaining weight small networks for MNIST and CIFAR-10, IMP subnetworks can match the accuracy of the full network (we refer to such subnetworks as matching subnetworks) at sparsity levels far beyond those at which randomly reinitialized or randomly pruned subnetworks can do the same.
original initialization. On
The lottery ticket hypothesis offers a new perspective on the role of overparameterization and raises the tantalizing prospect that there may exist much smaller neural networks that are capable of re- placing the larger models we typically train today. Unfortunately, in more challenging settings, there is empirical evidence that the lottery ticket hypothesis holds. IMP subnetworks of VGG and Resnet-style networks on CIFAR- 10 and ImageNet perform no better than other kinds of sparse networks (Liu al., 2019; Gale al., 2019).
In this paper, we describe a new framework called instability analysis, which measures whether the outcome of optimizing a network is robust to SGD noise (in which case call it stable). Insta- bility analysis offers a range of new insights into the behavior of unpruned networks. For example, the outcome of optimization becomes stable SGD noise early in training (3% for Resnet-20 on CIFAR- 10 and 20% on Resnet-50 for ImageNet). Moreover, it distinguishes known cases where IMP succeeds and fails to find matching subnetwork; namely, IMP subnetworks are only matching when they are stable. It also allows us to identify new scenarios where sparse, matching subnet- works emerge early in training in more challenging settings, including Resnet-50 and Inception-v3 on ImageNet. In doing so, our results demonstrate that instability analysis is a valuable scientific tool for investigating the behavior of neural networks.

---

Under review as a conference paper at ICLR 2020
Instability analysis. Instability analysis is technique deter- mine whether the outcome of optimization is robust to SGD noise. Figure 1 visualizes this process. We train two copies of the same network from initialization (W)) on different data orders (which models different samples of SGD noise). We then linearly inter- polate (dashed line) between the trained weights (W7 and W?)) and examine the error along this path (blue curve). The instabil- ity of the network to SGD noise is the maximum increase in train or test error along this path (red line). We say a network is stable if error does not increase along the path, i.e., instability is O. To examine instability at later iteration k, we first train the network to iteration & (W₂) and make two copies afterwards. Instability is a property of a network with respect to an optimization procedure; we focus the standard procedure prescribed for the networks we examine.
Wo
WR
W
W
Instability
Figure 1: A diagram of instabil- ity analysis (text left).
Instability analysis assesses a linear form of mode connectivity, a phenomenon where the minima found by two networks are connected by a path of constant error. Draxler et al. (2018) and Garipov et al. (2018) show that the modes of standard vision networks trained from different initializations connected by piece-wise linear paths of constant error loss. Based this work, we expect that our networks will be connected by such paths. However, the modes found by Draxler et al. and Garipov et al. are not connected by linear paths. The only extant example of linear mode connectivity is by Nagarajan & Kolter (2019), who train MLPs from the same initialization on disjoint subsets of MNIST and find that the resulting networks are connected by linear paths of constant test error; we explore linear mode connectivity from points throughout training, we do so at a larger scale, and we focus on different samples of SGD noise rather than disjoint samples of data,
Results. We begin by examining the instability of unpruned networks for MNIST, CIFAR-10, and ImageNet. All but the smallest MNIST network we study are unstable at initialization. However, by point early in training (3% for Resnet-20 on CIFAR-10 10 and 20% for Resnet-50 on ImageNet), all networks become stable. other words, from this point forward, the outcome of optimization is determined modulo linear interpolation. In fact, the entire trajectory of stable network is so determined: when we train two copies of the network on different data orders, the states of the networks at each epoch are connected by linear paths over which test error does not increase.
In the lottery ticket context, we find that extremely sparse IMP subnetworks are matching only when they are stable, providing the first basis for understanding the mixed results in the literature. In do- ing so, we make a new connection between lottery ticket behavior and the optimization dynamics of neural networks. Inspired by full network results, modify IMP to rewind subnetwork weights to their values at iteration k rather than resetting them to initialization. For values of & that are early in training (in fact, earlier than the full networks), IMP subnetworks become stable in all cases we consider. Correspondingly. they also become matching. At these sparsity levels, randomly reinitialized and randomly pruned networks are neither stable nor matching. This connection be- tween stability and accuracy suggests that linear mode connectivity is fundamental to sparse neural networks found by IMP and, thereby, to our current knowledge of the lottery ticket hypothesis.
Contributions. We make the following contributions:
We introduce instability analysis. which measures the maximum increase in error along the linear path between minima found by training the same network on different data orders.
On a range of image classification benchmarks including Resnet-50 on ImageNet, we observe that networks become stable SGD noise early in training.
We show that stable networks are stable throughout the training process.
We use instability analysis to distinguish successes and failures of IMP (the core algorithm be- hind the lottery ticket hypothesis) as identified in previous work. Namely, extremely sparse IMP subnetworks are only matching when they are stable.
We augment IMP with rewinding to study subnetworks initialized after iteration 0. We show that IMP subnetworks become stable and matching early in training if not at initialization.
Using rewinding, we show how to find sparse, matching subnetworks in much larger settings than in previous work by setting the weights of IMP subnetworks to their values from early in training.
2

---

Under review as a conference paper at ICLR 2020
Network
Dataset
Params
Train For Batch
Accuracy
Opt
Rate
Schodule
Warmup
Donsity
Pruning
Lenet
MNIST 2668
24K Iters
60
98.3 0.1%
adam
12c-4
constant
3.5%
Iterativve
Resnei-20 (standard)
91.7 0.1%
mom.
10x drup at
16.8%
Resnet-20 (low)
CIFAR-10 274K
63K Iters
128
88.8 + 0.1%
0.01
32K, 48K
8.6%
Iterative
Resnet-20 (warmup)
89.7 1: 0.3%
mom.
0.03
30K
6.9%
VGG-16 (standard)
93.7 + 0.1% mom.
0.1
0
1.5%
10x drop at 32K, 48K
VGG-16 (low)
CIFAR-I0 63K
91.7 0.1%
mom.
5.5%
VGG-16 (warmup)
93.4 1: 0.1%
mor.
0.1
30K
1.5%
Resnet-50
ImageNet
25.5M 90
1024
76.1 +: 0.1%
0.4
10x drop at 30,60,80
Eips
30%
Oneshot
Inception- v3
ImageNet 27.1M 171 Eps 1024 78.1 1: 0.1%%
mor. 0.03
linear decay to 0.005
30%
Oneshot
Table I: Our networks and hyperparameters. Accuracies are the averages and standard deviations across three initializations. Hyperparameters for Resnet-20 (standard) are from He al. (2016). Hy- perparameters for VGG-16 (standard) are from Liu et al. (2019). Hyperparameters for low, warmup, and Lenet are adapted from Frankle & Carbin (2019). Hyperparametees for ImageNet networks are from Google's 's reference TPU code (Google, 201 8).
2 PRELIMINARIES AND METHODOLOGY
Instability analysis via linear mode connectivity. Instability analysis evaluates whether the min- ima found when training two copies of a neural network on different samples of SGD noise (i.e., the random data order used during SGD) are linearly connected by a path over which error does not increase. The neural network in question could be randomly initialized (Wo in Figure 1) or the result of & training iterations (Ws). To perform instability analysis, we make two copies of the network and train them to completion with different random data orders (W1 and W/)). We then linearly interpolate between the trained weights (dashed line) and compute the train or test error at each point (blue curve) to determine whether it increased (minima are not linearly connected) or did not increase (minima are linearly connected).
Formally, we capture training with SGD (or variant) by a function -A"- RP x U + RP, which maps weights W, at iteration s and SGD randomness u U to updated weights W, at iteration by training for - steps (for ( E {1,.., T and 8 < l). Algorithm 1 describes our procedure:
Algorithm Stability analysis from iteration k.
1: Create a neural network with randomly initialized weights Wn 12d
2: Train Wo to Wa under SGD noise u ~ U. That is, W. < A - (Wo. u).
3: Train W& Wil under SGD noise i1 U. That is, WT1 +- A (We, u1)
4: Train Wa to W under SGD noise u2 ~ U. That is, W + A k- (W2, U2).
5: Evaluate E ( (1 3)) for E [0, 1].
We describe the result of linear interpolation (step 5) with a quantity that we term instabil- it. Let ((W denote the train or test error of a network parameterized by W. Let & be the average test error of W and WZ. Let Emax = suP E(aW? + (1-))W77) be the highest test error when linearly interpolating between W and W The instabil- iry is Emax - ε (red line in Figure 1). When instability > 0, the minima are linearly connected and the network stable. In practice, we average the instability from three initializations and three data orders per initialization (nine combinations in total). We use 30 evenly-space values of E [0. 1].
(
Networks and datasets. We study image classification networks on MNIST, CIFAR-10. 10, and Ima- geNet as specified in Table 1. All hyperparameters listed are the standard values for these networks from reference implementations or prior work as cited in Table 1. The warmup and low variants of Resnet-20 and VGG-16 are adapted from hyperparameters chosen by Frankle & Carbin (2019).
Frankle & Carbin (2019) mistakenly refer to Resnet-20 "Resnet-18; which is separate network.
3

---

Under review as a conference paper at ICLR 2020
30
VCGG-16
Bomae-10
Incplimn-1
30
60
100
50
100
Eate (55)
191
Tine (55
600
50
20
20
40
20
0.2
0.6
08
0.0
0.5
1.0
Interpolation
Incepolation
Ennerpolation
Inkepotation
Decepolatoo
Teat Eire
Trin Frror
Figure 2: The train and test error when linearly interpolating between the minima found by randomly initializing a network and training it twice under different data orders. Each line is the mean and standard deviation across three initializations and three data orders (nine samples in total). The errors of the trained networks are at interpolation = 0 and 1. Inception train data is progress.
Lanet
Resser 20
VGG--6
Reanc: 50
laceptico v3
0.4
Inophityy (85)
46
Laxihtyy (6)
60
Inshilyy 880
6.2
40
20
0.0
0
25 100
100
500
2X
10k
100-000 2K 10X
20
20 24
Denations
(lnee)
Tes Ence
Trann
Figure 3: The instability when linearly interpolating between the minima found by networks that are trained on different data orders from step k. Each line is the mean and standard deviation across three initializations and three data orders (nine samples in total). Inception train data is progress.
3 NEURAL NETWORK INSTABILITY TO SGD NOISE
In this section, we study whether the outcome of optimization becomes robust to SGD noise after certain amount of training. Concretely, we perform instability analysis (Algorithm 1) on the standard networks in Table from many points during training to understand when, ever, networks become stable to SGD noise. We find that, although only Lenet is stable at initialization, every network becomes stable early in training.
Neural networks are unstable at initialization. We begin by studying the instability of neural networks at initialization. We do so by training two copies of the same, randomly-inttialized network under different samples of SGD noise (that is, Algorithm 1 with h: 0). Figure 2 shows the train error (purple) and test error (red) when linearly interpolating between the minima found by these copies. With the exception of Lenet MNIST, none of the networks we study are stable at initialization. In fact, both training and test error rise to the point of random guessing when linearly interpolating between the minima found under different data orders. Lenet's error does rise slightly, but the increase is a small fraction of a percentage point. We conclude that, in general, larger-scale image classification networks not stable initialization.
Stability improves early in training. Although nearly all networks are unstable at initialization, they will inevitably become stable at some point. In the limit, they will be stable by the end of training, and it seems reasonable to expect that the final few steps of SGD are too insignificant to cause the network enter linearly unconnected minima. In this experiment, we ask how early neural networks become stable. In other words, after what point in training is the outcome of optimization determined modulo linear interpolation regardless of the sample of SGD noise? To explore this behavior, we train a single copy of the network for & iterations or epochs before making two copies that we train to completion on different data orders (Algorithm I with k 2 0).
Figure plots the instability of the networks for various values of k. We measure instability as the maximum error during interpolation (the peaks in Figure 2) minus the mean of the errors of the two networks (the endpoints in Figure 2). In all cases, instability decreases as & increases, culminating in networks that are stable (i.e., instability ze 0). The iteration at which stability emerges is surprisingly early. For example, it occurs from approximately iteration 2000 for Resnet-20 and VGG-16 16; in other words, after 3% of training, SGD noise cannot affect the final minimum modulo linear interpolation. Stability occurs later for Resnet-50: about epoch 18 (20% into training).
4

---

Under review as a conference paper at ICLR 2020
10
laashirr (70)
Lanabiig (50
40-
20-
20-
10000
20000
10000
00000
S0000
0005
10000
20000
10000
4000
S0000
6009
Toening
k=O
50
1- 100
250
k 500
k-
1000
2006
Figure 4: Test instability throughout training. At each epoch, linearly interpolate between the states of two networks trained with different SGD noise and compute instability. Each line involves train- ing to iteration k and then training two copies on different data orders after.
Instability is essentially identical when measured in terms of train or test error (although train in- stability is slightly higher than test instability for Resnet-50), indicating that the minimum becomes determined on both the train and test surfaces around the same time. Going forward, we present all results with respect test error for simplicity.
Stable networks are linearly connected throughout training, Stable networks arrive at minima that are linearly connected, but do the trajectories they follow throughout training also have this property? In other words, when training two copies of the same network with different noise, is there linear path over which test error does not increase connecting the states of the networks at each iteration? To study this behavior, we linearly interpolate between the networks at every epoch of training and compute the test error instability. That is, we compute instability throughout training.
Figure 4 plots instability throughout training for Resnet-20 and VGG-16 from different starting iterations For as test error: the test error of cach network decreases, the maximum possible instability increases (since instability never exceeds random guessing). With larger values of k; instability increases more slowly throughout training. When i is sufficiently large that the networks are stable at the end of training, they are stable at every epoch of training (k = 2000, pink line). In other words, after iteration 2000, the networks follow identical optimization trajectories modulo linear interpolation.
(blue line), instability increases rapidly. In fact, it follows the same pattern
Discussion. Our observations implicitly divide training into two phases: an initial, unstable phase in which the final "linearly connected" minimum undetermined on account of SGD noise and subsequent, stable phase in which the final linearly connected minimum becomes determined. From this perspective, our observations contribute to a growing body of literature suggesting that training experiences a noisy initial phase and less stochastic second phase. For example, the eigenspectrum of the Hessian settles into bulk of small eigenvalues and a few large outlier eigenvalues after some amount of training (Gur-Ari et al., 2018), and networks trained with large batch sizes and high learning rates benefit from learning rate warmup during the first part of training (Goyal et al., 2017). One possible way to exploit our observations could be explore changing aspects of the optimization process (c.g., learning rate schedule or optimizer) similar to Goyal et al. (2017) once the network enters the stable phase in order to improve the performance of training; instability analysis makes possible to evaluate the consequences of doing so.
As scientific tool, also believe instability analysis provides framework for studying topics related to the scale and distribution SGD noise, e.g.. the relationship between batch size, learning rate, and generalization (Keskar al., 2017; Smith & Le, 2018; Smith et al., 2018) and the efficacy of alternative learning rate schedules (Smith, 2017: Smith & Topin, 2018; 88; Li & Arora, 2019).
INSTABILITY AND SPARSITY
We have long known that it is possible to prune neural networks after training, often removing 90% of connections more with reduction in accuracy after small amount of additional training (e.g., LeCun et al., 1990; Reed, 1993; Han et al., 2015; Gale et al., 2019; He et al., 2018). However, sparse networks more difficult to train from scratch. At the most extreme levels of sparsity
5

---

Under review as a conference paper at ICLR 2020
achievable by pruning, sparse networks trained in isolation generally reach lower test accuracy than dense networks (Han et al., 2015; Li et al., 2016; Liu et al., 2019: Frankle & Carbin, 2019).
However, there is known class of networks that remains accurate these sparsity levels: win- ning lottery tickets. On small vision networks, iterative magnitude pruming (IMP) retroactively finds sparse subnetworks that were capable of training in isolation to full accuracy (Frankle & Carbin, 2019); we refer to subnetworks with this capability as matching subnetworks. The existence of winning lottery tickets raises the possibility that we might be able to replace conventional, dense networks with sparser subnetworks, creating new opportunities to improve the performance of train- ing. However, more challenging settings, subnetworks found by IMP with at particularly high sparsities and perform no better than other subnetworks (Liu et al., 2019; Gale et al., 2019). In these contexts, there is no evidence that the lottery ticket hypothesis holds.
are not matching
Motivated by the possibility of training more efficient networks and a desire to explain the successes and failures of IMP, we study the relationship between instability and the accuracy of extremely sparse neural networks. Our central finding is that, although the accuracy of full networks in Section 3 seems unaffected by instability, the sparsest IMP subnetworks are matching only when they are stable. In other words, when SGD noise is sufficient to change the minimum that an IMP network finds (up to linear interpolation), test accuracy is lower. Randomly reinitialized and randomly pruned subnetworks are always both unstable and non-matching at all sparsity levels we consider.
4.1 METHODOLOGY
Iterative magnitude pruning. Iterative magnitude pruning (IMP) is a procedure to retroactively find a subnetwork of the state of the full network at iteration k of training. As outlined in Algorithm 2, IMP trains network completion, prunes weights with the lowest magnitudes globally, and rewinds the remaining weights back to their values at iteration k. The result a subnetwork (Wk. m) where W& Rd is the state of the full network iteration & and m {0, 1]d is a fixed binary vector that, when multiplied element-wise with WR. produces the pruned network m O WR. We can either run IMP iteratively (training, pruning 20% of weights (Han et al., 2015; Frankle Carbin, 2019), rewinding, and repeating until we reach a target sparsity) or in one-shot (pruning to the target sparsity in single step). We use one-shot pruning on ImageNet networks for efficiency and iterative pruning in all other cases (Table 1). Frankle & Carbin (2019) only study rewinding to iteration O; one of our contributions is to generalize IMP to any rewinding iteration When training a subnetwork from iteration k we also rewind the learning rate schedule to its state at iteration k.
Algorithm 2 Iterative Magnitude Pruning (IMP) with rewinding iteration i and N iterations.
1: Create neural network with randomly initialized weights Wo E Rdd and initial pruning mask m 1d.
2: Train Wo to W. under SGD noise U. That is, We - (Wo, u).
3: for v E [L.....N] N do
4: Train m @ We to @ Wr under SGD noise n' ~ U. That is, Wr < A (m @ Wr,
5: Prune the remaining entries with the lowest magnitudes from Wr. Let mlj] if Wrli is pruned.
6:
Return m, We
Sparsity levels. Although we are interested in the behavior of networks at all sparsities, computa- tional limits force to focus specific sparsity level.2 In light of these restrictions, we focus on the highest sparsities for which IMP returns a matching network at any rewinding iteration k. The densities examine are in Table 1, and Appendix A explains these choices. Doing so provides the best contrast between sparse networks that are matching and (1) the full, overparameterized neural networks and (2) other classes of sparse networks.
Experimental approach. We study the relationship between stability and accuracy in extremely sparse subnetworks uncovered by IMP. IMP produces particularly sparse matching subnetworks and is the algorithm behind current lottery ticket results, so it merits close examination for both better scientific understanding and potential practical lessons for training sparse networks. As a basis
2 IMP entails training a network at least dozen times to reach high levels of sparsity, and instability analysis requires training each of these networks further nine times (three data orders and three kinds of sparsity) for many rewinding iterations. For rigor, we replicate each experiment three times with different initializations.

---

Under review as a conference paper at ICLR 2020
Roaci-30
Inception-3
96-
76
96-
84
68
92
110.03
252
134
188
69
0.3
1AJ0
100
343
34.1
16.8
11.7
(ALU/00 490 34.3 240 1h.
Porcet of Wastes Resrazing
Poveet Weighta Rensazing
Paice: of Waggts Beesaning
4.3
00.5
Reasa 20
90.5
Reana 20 Wartep
-0-
900
900
87.5
67.5
410 26.2
S4. 410
Percent Winghas Remouning
Porter of Weight Rersatinng
Perter Weights Rerransing
V0G-16 Lew
V80--6 WazzRO
21
1000 262
0.3
1.0
10L0 20 135
30
1.0
Poscest Wiiglas Renaahing
Peoce Whigles Reasning
PoIcE of Weights Rezanning
DMP
Priting
+ Randons Reint
Figure 5: Test accuracy of IMP subnetworks, randomly pruned subnetworks, and randomly reini- tialized IMP subnetworks at all levels of sparsity. The black line is the accuracy of the unpruned network. Each line is the mean and standard deviation across three initializations.
for comparison, we also examine two kinds of subnetworks that are not matching at the sparsities we consider: (1) IMP subnetworks that are randomly reinitialized and (2) subnetworks found by randomly pruning weights rather than pruning those with the lowest magnitudes. We exploit the fact that not all IMP subnetworks are matching: contrast settings where IMP succeeds and fails to further understand the conditions under which IMP subnetworks are matching.
4.2 EXPERIMENTS
IMP subnetworks are matching at initialization only when stable. We begin by studying sparse subnetworks trained in isolation from initialization (k = 0). As noted previously, not all IMP subnetworks are matching at the sparsity levels we consider for 0. Figure 5 shows the accuracy of the IMP subnetworks (blue) across all levels of sparsity for each of the hyperparameters in Table (alongside randomly pruned subnetworks orange and randomly reinitialized subnetworks in green for comparison). On Lenet, IMP subnetworks are matching at sparsities well beyond those which other subnetworks are matching. The same is true for variants Resnet-20 and VGG-16 16 with lower learning rates or learning make it possible for IMP to find matching subnetworks. In contrast, IMP subnetworks Resnet-50, Inception-v3, and standard configurations of Resnet-20 and VGG-16 perform similarly to randomly reinitialized and randomly pruned subnetworks.
warmup, changes proposed by Frankle & Carbin (2019) specifically to
In Figure 6, we analyze the instability of these subnetworks. At the sparsity levels we consider, IMP subnetworks are matching only when they are stable. The IMP subnetworks of Lenet, Resnet-20 (low, warmup), and VGG-16 (low, warmup) are stable and matching, while no other IMP subnet- works have either property. The low and warmup experiments are notable because these hyperpa- rameters were selected by Frankle & Carbin (2019) make it possible for IMP to find matching subnetworks without awareness that they also improve stability. This inadvertent causal experiment adds further evidence of a connection between instability and accuracy IMP subnetworks.
With the exception of Lenet, no randomly reinitialized or randomly pruned subnetworks are stable or matching at these levels of sparsity. On Lenet, these subnetworks are not matching but test error only rises slightly when interpolating. For all other networks consider, the error of these subnetworks approaches or reaches that of random guessing when interpolating.
IMP subnetworks become stable and matching early in training, In the previous experiment, we saw that the IMP subnetworks are matching only when they are stable to SGD noise. In Section 3, observed that unpruned networks become stable to SGD noise only after a certain amount of training. In this experiment, we combine these observations: we study whether IMP subnetworks become stable during training and, if so, whether improved accuracy follows. To do so, we examine

---

Under review as a conference paper at ICLR 2020
Resest 50 (3000))
(16.88)
Warmap
Leact (3.53)
50
3.5
The Creee5
-00
60
3.0
60
90
40
40-
20-
60
0.5
0.0
1.0
000
00
0.0
0.5
interpdattios
Intorpolation
Interpolaton
Insepolttion
Interpdation
hocppione33 (3608)
VGG (1
Low
VGG
100
Tou Dmerr
80
Tout Einer
60
60
60-
20
12
Random Reinir
Random Pruning
60
0.5 Integedatiinn
1.0
010
0.1
0.5
3.0
IMP
Lmsepelation
Interolltoon
Emsepeatiinn
Figure 6: The test when linearly interpolating between the minima found by training sparse subnetworks twice from initialization under different data orders. Each line is the mean and standard deviation across three initializations and three data orders (nine samples in total). The errors of the trained networks are at 0 and 1. Percents are percents of weights remaining.
Resest (30.0))
(863)
Lese: (3.53)
1.0
lusabatty (8)
-0
60
Insahilly
40
V S
0.S
20
0.0
0
100
500
2K
10k
100
500 2K TOK
100
500
2X
108
0
25
100
100 IK
Rewindnn Epech (inea)
Rewinding Deration dog)
Rewindina Deration loo))
Rewirdine hessioa (lox)
Revindiss laasiio Oog)
27
s.s
Tex Enee (3)
20
Bine (8)
Tea Umeers (S)
26-
(imerr
so-
10
14
2.5
2.0
10
500
1000
10k
1K Oog)
Revilidi Eooch
Rewadding Doration
Rewinding Deraion (log)
Rewarding
Incepion-8 (30.0%)
VGr--621 1621.99 (19999)
vacc-16 Low c5 (35%
vocc to Wormap 45)
30
Eanabilty (R)
50
Intaaity
betellrry
10
40-
20
0-
0
200
EorEnne (3)
24-
Yos Eaioe
Teal Eiser (5)
9.5
IMP
Random Priming
Randum
Revisding Epoch lineet)
Rewanding Doration dog)
25 100 500 2K 10K Rewttsing Tepatte
Rewasding Deratio
Urpeined Newwork
Figure 7: The instability of subnetworks that are created from the state of the full network at iteration l and trained on different data orders from there. Each line is the mean and standard deviation across three initializations and three data orders (nine samples in total). The gray lines are the accuracies of the full networks to one standard deviation. Percents are percents of weights remaining.
the sparse subnetworks that result from training unpruned networks for steps and subsequently applying pruning masks (and possibly reinitializing). We find these masks by running IMP with rewinding: we train the full network to completion, prune, and rewind each remaining weight to its value step k. We then standard instability analysis these sparse networks from iteration k.
The blue dots in Figure 7 show the instability (rows and 3) and test accuracy (rows 2 and 4) when rewinding IMP subnetworks to various points early in training. Those subnetworks that are unstable when rewound to iteration 0 (Resnet-20, VGG-16 16. Resnet-50, Inception-v3) become stable when rewound points slightly later in training. IMP subnetworks of Resnet-20, VGG-16, and Resnet-50
8

---

Under review as a conference paper at ICLR 2020
become stable about iteration 500 (0.8% into training), iteration 1000 (1.6%), and epoch 4 (4.4%) Stability and accuracy of these sparse IMP subnetworks continue to correlate. Test error decreases alongside instability, with IMP subnetworks reaching the performance of the unpruned networks (gray lines) approximately when they become stable. IMP subnetworks that were matching and stable iteration 0 generally remain VGG-16 low experience increased test error at the latest rewinding points we consider.
other rewinding points, although Resnet-20 low and
IMP subnetworks become stable at least as early as the unpruned networks (red) and much earlier for Resnet-50 (epoch 4 vs. 18). In contrast, randomly pruned subnetworks (orange) and randomly reinitialized IMP subnetworks (green) are unstable and non non-matching every rewinding iteration (with Lenet again the sole exception). We believe these subnetworks will eventually become stable later on; in some cases, instability of randomly pruned subnetworks decreases the latest rewinding points we consider. This behavior suggests potential broader link between subnetwork stability and aceuracy: IMP subnetworks are matching and maintain or improve upon the stability behavior of the full networks, while other subnetworks are less accurate and become stable later if at all.
4.3 DISCUSSION
The "lottery ticket hypothesis." The lottery ticket hypothesis (Frankle & Carbin, 2019) conjectures that any "randomly initialized, dense neural network contains subnetwork that-wher trained in isolation-matches the accuracy of the original network." " The authors support this hypothesis by using IMP to find matching subnetworks at initialization in small vision networks. However, follow- up studies show (Liu et al., 2019; Gale et al., 2019) and we confirm that IMP does not find matching subnetworks in more challenging settings. We use instability analysis to distinguish the successes and failures of IMP as identified in previous work. In doing so, we make new connection between the lottery ticket hypothesis and the optimization dynamics of neural networks.
Moreover, by augmenting IMP with rewinding, we show how to find sparse, matching subnetworks in much larger settings than in previous work, albeit with subnetworks from early in training rather than at initialization. Our technique has already been adopted to create trainable subnetworks that transfer to new settings (Morcos et al., 2019), as a pruning method in its own right (Anonymous, 2020a), and to further study the lottery ticket hypothesis (Anonymous, 2020e:c:g:f.b).
Pruning. On larger-scale networks and tasks, we find that IMP subnetworks at extreme sparsities only become stable and matching after the full network has been trained for small number of iterations or epochs. Recent methods have explored pruning neural networks at initialization (Lee al., 2019; Anonymous, 2020d), but our results suggest that the best time to prune may be slightly later in training. By that same token, most modern pruning methods only begin to sparsify networks late in training or after training (Han et al., 2015; Gale et al., 2019; He al., 2018). In these cases, the fact that there are matching subnetworks early in training suggests that there is potentially a substantial unexploited opportunity to prune neural networks much carlier than current methods.
SGD noise and overparameterization. While dense neural networks train to full accuracy regard- less of their stability, sparse networks in our experiments are only matching when they are stable. Although our results speak only to specific kinds of sparse networks (IMP subnetworks and our randomly reinitialized and randomly pruned baselines) at particularly extreme sparsity levels, they suggest possible broader relationship between instability and accuracy of sparse networks. It is possible that sparse networks, which have fewer parameters than their dense counterparts, are less robust instability during the carly part of training.
REFERENCES
Anonymous. Comparing fine-tuning and rewinding in neural network pruning. In Submitted In- ternational Conference on Learning Representations, 2020a. URL httt:::///ppeevieew... net/ forum?id=S1gSSeNNkva under review.
Anonymous. The early phase of neural network training. In Submitted to International Conference on Learning Representations, 2020b. URL http:p::////eeeeiiieeeeeeette wtw.://wweettoorrrm////..... iRNFWS. under review.

---

Under review as a conference paper at ICLR 2020
Anonymous. Finding winning tickets with limited (or no) supervision. In Submitted International Conference on Learning Representations, 2020c. URL SJx QJHYDB. under review.
Anonymous. Picking winning tickets before training by preserving gradient flow. In Submitted to International Conference Learning Representations, 2020d. URL https://openrevien het/foorumiid=SkkgAccvke under review.
Anonymous. Playing the lottery with rewards and multiple languages: lottery tickets in rl and nip- In Submitted to International Conference on Learning Representations, 2020e. URL https: wtwprreiwweeeeeeooummiiieeeee XnXRVFWH.. under review.
Anonymous. The sooner the better: Investigating structure of early winning lottery tickets. In Submitted to International Conference Learning Representations, 2020f. URL https:
// wew.iewwwee/fooro www.:neee/orrumnntteBnasssvvee under review.
Anonymous. Winning the lottery with continuous sparsification. In Submitted to International Conference on Learning Representations, 2020g. URL BJe4oxHYPB. under review.
Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred A Hamprecht. Essentially no bar- riers in neural network energy landscape. In International Conference on Machine Learning, 2018.
Jonathan Frankle and Michael Carbin. The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks. In Int. Conf. Represent. Learn., 2019.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks, 2019. arXiv:1902.09574.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. In Advances in Neural Information Processing Systems, pp. 8789-8798, 879998779.220 2018.
Google. Networks for Imagenet on TPUs, 2018. URL https: http:/twww..cmm/etessso////////a tree/mmatter/oodels//
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate large minibatch SGD: training Imagenet in 1 hour, 2017.
Guy Gur-Ari, Daniel A Roberts, and Ethan Dyer. Gradient descent happens in a tiny subspace. arXiv preprint arXiv: (xXXv:8812..477:: 2018.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances in Neural Information Processing Systems, pp. 1135-1143, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp- 770-778, 2016.
Yihui He, Lin, Zhijian Liu, Hanrui Wang, Li-Jia Li, and Song Han. Ame: Automl for model compression and acceleration mobile devices. In Proceedings of the European Conference Computer Vision (ECCV), pp. 784-800, 2018
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batcl batch training for deep learning: Generalization gap and sharp minima. In International Conference Learning Representations, 2017.
Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In Advances in Neural Information Processing Systems, pp. 598-605, 1990.
10

---

Under review as a conference paper at ICLR 2020
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. Tomr. SNIP: Single-shot Network Pruning based on Connection Sensitivity. In International Conference on Learning Representations, 2019.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. arXiv preprint arXiv: 2016.
Zhiyuan Li and Sanjeev Arora. An exponential learning rate schedule for deep learning. arXiv preprint arXiv:1910.07454, 2019.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the Value of Network Pruning. In International Conference on Learning Representations, 2019.
Ari S Morcos, Haonan Yu, Michela Paganini, and Yuandong Tian. One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers. 2019.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable explain general- ization in deep learning. 2019. 1rXiv:1902.04742V2 To appear in NeurlPS 2019.
Russell Reed. Pruning algorithms-a survey. IEEE transactions on Neural Networks, 4(5):740-747, 1993.
Leslie N Smith. Cyclical learning rates for training neural networks. In 2017 IEEE Winter Confer- on Applications of Computer Vision (WACV), pp. 464-472. IEEE, 2017.
Leslie N. Smith and Nicholay Topin. Super-convergence: Very fast training of residual networks wtwpeerrwiieee.e/foormmmmddoo Aet/forrm22d::1115tt]333
using large learning rates, 2018. URL
Samuel L. Smith and Quoe V. Le. A bayesian perspective generalization and stochastic gra- dient descent. International Conference on Learning Representations, 2018. URL https:
Samuel L. Smith, Pieter-Jan Kindermans, and Quoc V. Le. Don't decay the learning rate, increase the batch size. In International Conference on Learning Representations, 2018. URL https:

---

Under review as a conference paper at ICLR 2020
(anagehe))
50
96
1060 512
262
1M 65
35
1.8
09
0.5
1060
3000
800
34.1
340
168
11.7
1000
70.0 000 313
360 168 82 57
Perent of Weighto Reanining
Pricté Weiggto Ronainit
Procat of Weight Remnining
(CIAAR11))
Razzi- Low
Wazzap (CIFAR-1))
800
Tol
100.
640
4111
262
16.1
10.7
6-3
4.4
1000
64.0
4.11
20.2
16.
10.7
6M
4.4
1100
660
4.0
26.2
16.8
1017
6.9
4.4
Pertent of
Remminnz
Peieen
Kenaineu
Pooim Weigh
VGGG-16 (UIFARR-1))
LowG (CHAR-IC))
VGGG-L Wormey (CWVAR-155
95
95
05
83
Tox TocAAoKKA
91
91
89
1000 512 262
155
5.0 16
1.0
0.5
1000 512 262
135
69
16
18
1.0
D5
1000 112
26.2
155
14
18 10 0.5
Remoinin
Prinuce Weight Remotnin
Prinee Waggh
Original
Peating
+
Under Revinding
Figure 8: At all sparsity levels, the maximum test accuracy achieved by IMP subnetworks for any rewinding iteration (red). Also includes the test accuracy of IMP subnetworks with A: = 0, randomly pruned subnetworks, and randomly reinitialized IMP subnetworks with l 0 at all levels of sparsity. The black line is the accuracy of the unpruned network. Each line the mean and standard deviation across three initializations.
A SELECTING EXTREME SPARSITY LEVELS FOR IMP SUBNETWORKS
In this appendix, we describe how we select the sparsity level that we examine for each IMP sub- network. For each network and hyperparameter configuration, our goal study the most extreme sparsity level at which matching subnetworks are known to exist early in training. To do so, we use IMP generate subnetworks many different sparsities for many different rewinding iterations (specifically, all of the rewinding iterations Figure 7). We then select the most extreme sparsity level at which any rewinding iteration produces a matching subnetwork.
Figure 8 plots the maximum accuracy found by any rewinding iteration in red. The black line is the accuracy of the unprumed network to one standard deviation. For each network, we select the most extreme sparsity for which the red and black lines overlap. As basis for comparison, Figure 8 also includes all of the other lines from Figure 5: the result of performing IMP with A: = 0 (blue line), random pruning (orange line), and random reinitialization of the IMP subnetworks with (green line).
Note that, for computational reasons, Resnet-50 and Inception-v3 pruned using one-shot prun- ing, meaning the networks are pruned to the target sparsity all at once. All other networks are pruned using iterative pruning, meaning the networks pruned by 20% after each iteration of IMP until they reach the target sparsity.
B INTERPOLATION DATA FOR UNPRUNED NETWORKS
In this appendix, we present the interpolation data for the instability analysis on the unpruned net- works in Section 3.
12

---

Under review as a conference paper at ICLR 2020
B.1
TEST ERROR
These graphs plot the test error when linearly interpolating for select values of for the networks in Figure 3.
Lenet Prll Nerwork
Resect 20 (100.0%)
Pall Network
VGG 16 (100.03)
Full Network
60
80
60
Ton Emtr
2.0
16
20
0.75
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.25
1.00
Inerpotation
Interpobation
Interpobiton
k=0
500
k-0
500
k-
k- 500
k- 50
- 250
2K
1 250
1-2X
k 250
1 2K
Mennet- 50 (10IL)55)
Pull Network
100
80
60
40
20
0.000
0.25
0.50
0.75
1.00
k-d
B.2 TRAIN ERROR
These graphs plot the train error when linearly interpolating for select values of for the networks in Figure 3.
Resnat-20 (100,05) Full Network
VGG-16(10800)) Full Netwekk
0.6
50
80
Tell Banu
0.4
Toa
Tee
40
60
20
20
0.0
0.25
Intop-aatimm
Interpolation
Interpoution
k
1- 500
1=0
1- 500
k-0
k 500
250
3K
1- 250
1x
k 250
2K
13

---

Under review as a conference paper at ICLR 2020
Re-me-50 (100085) - Full Newwrrk
60
40
0.25
Interpolation
k-4
k
C INTERPOLATION DATA FOR SPARSE NETWORKS
In this appendix, present the interpolation data for the instability analysis the sparse networks in Section 4.
C. TEST ERROR OF IMP SUBNETWORKS
These graphs plot the test error when linearly interpolating for select values of l for the IMP sub- networks Figure 7. Percents in all figures are densities the percent of weights remaining after pruning.
Inceptina-v3 (3ILDS)) IMP
Leset (3.5%) IMP
Recact-90 (90.05)-M44
2.0
Tai Emor
Tia Fans
Tal
188
0.00
0.30 Interpolation
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.90
1.00
Interolation
Interpstatin
O
10
IK
250
Revusi20 (16.85) IMP
(6-9%)
60
Tod Emmor
Tea Lamer
110
Tca
40
11.0
0.50
0.00
0.25
0.50 Intepulation
0.75
1.00
0.00
0.25
0.50
0.55
1.00
Interodaiion
Intorpeattinn
k
500 500
k 500
k 100
k- IK
- 100
k- 1K
- 250
-K
k-
14

---

Under review as a conference paper at ICLR 2020
VGG (8 IMP
VO0-16 Low (5 (5.55-IMM -MP
VCD-16 W Wemup (1 (8)
80
60
Tent
8..00
Test Uamorr
6.50
40
8.25
20
6.25
6.00
0.00
0.25
0.50
0.00
0.25
0.50
0.75
1.00
0.00
0125
0.30
0.75
Interpodtiinn
Interpllaiion
laterpdution
k-0 0
500
K 500
50
IK
1K
k 250
k- 28
1
230
k- 2X
250
k 2K
C.2 TEST ERROR OF RANDOMLY PRUNED SUBNETWORKS
These graphs plot the test error when linearly interpolating for select values of k for the randomly pruned subnetworks in Figure 7. Percents in all figures are densities the percent of weights re- maining after pruning.
Inceptionn69 Random Proning
(3.5%)
Prusing
Reseat-50 (30.0)) Randum Prixingg
100
4.5
3X2
Tall Enoo
Toa
Tou
60
3,5
3.0
0.00
0.25
0,50
1.00
Interpolation
Intorplation
Interpolatinn
k=0
500
IK
250
2K
k=6
20soci-20(16.855) Prining
Resoet-20 (8.6)) Praning
Roact-20 Warmup (6.95) Rundom Prusing
80
50
60
10
Tol Enno
60
40
20
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0150 Interpolation
0.55
1.00
Interpaattion
Interpolation
100
1K
1- 100
1-
IK
100
k
1K
250
2X
VGG-16 (1.5S) Romdon Priting
VGG-16 Low (5.5%) Random Pruning
VGG-16 Wamnup (1.5%)
(1.55) Random Pruning
80
60
Tel Bmur
Tcd
Tea
40
40
20
20
20
0.25
0.50
0.75
0.25
0.25
Interpaaiion
Interpolation
Interpaution
k 0
500 500
1=0
1- 500
k=0
k 500
1 250
4K
1- 250
1x
k 250
2K
15

---

Under review as a conference paper at ICLR 2020
C.3
TEST ERROR OF RANDOMLY REINITIALIZED IMP SUBNETWORKS
These graphs plot the test error when linearly interpolating for select values of & for the randomly reinitialized IMP subnetworks in Figure 7. Percents in all figures are densities the percent of weights remaining after pruning.
Lenet (3.5%) Random Seinit
Reanct-90
28
Tiat Fanse
2.6
2.4
80
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.90
0.75
1.00
Imsopdatioon
Interptation
500
k=O 0
90
IK
250
Resnet-20 (16.85) Randum Reina
Roadt-20 Low (866)) Ranlum Reina
Reand-20 Wamnpp (6.5)) Romdom Rdnit
80
50
Toll EEmur
Tea
40
40
20
20
20
0.25
0.50
0.75
0.25
0.25
Interpaatioon
Interpolation
Interpolttion
k 0
k-500 500
1-0
1- 500
k=0
1 500
1K
250
2K
1- 250
k-
km 250
VGG-16(1.59) Rondom
VGG-I6 (5.55) 58) Randem
VOG-16 Wemmpp (1 (1-5%)-Ranieee -Rondom
80
50
80
60
Eaoor
100
6
Tol
40
20
0.00
0.25
0.50
0.55
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50 Interpaatiin
075
1.0
Intepodtionn
500
50
1-1K 1K
1- 50
1- IK
k- 50
k IK
kK
2X
D L2 DISTANCES FOR UNPRUNED NETWORKS
In this appendix, we present the Lg distances between pairs of full networks trained on different data orders from iteration k the experiment in Section 3. This data parallels Figure 3. We do not yet have L2 distance data for the ImageNet networks, although we plan to add it to the next version of the paper.
16

---

Under review as a conference paper at ICLR 2020
Lenet
Resnet-20
VGG-16
80
60
L22 Distannc
L2 Distance
Distance
60
40
40
40
20
20
20
0 25 500 2K 10K
0
100 500 2K 10K
100 2K 10K
Rewinding Iteration (log)
Rewinding Iteration (log)
Rewinding Iteration (log)
The Le distance between the networks decreases linearly as k increases. Interestingly, observe no clear relationship between the I.2 distance and the network instability. For example, there does not appear be critical I22 distance threshold that is crossed when the networks become stable. This is in contrast to our observations in Appendix E, where L2 distance between IMP networks correlates with instability, dropping a lower value when the subnetworks become stable.
E L2 DISTANCES FOR SPARSE NETWORKS
In this appendix, we present the L2 distances between pairs of sparse networks trained on different data orders from iteration k, the experiment in Section 4. This data parallels Figure 7. We do not yet have L2 distance data for the ImageNet networks, although we plan to add it to the next version of the paper.
Lenet (3.5%)
L2 Distance
10
25
100
500
2K
Rewinding Iteration (log)
Resnet-20 (16.8%)
Resnet-20 Low (8.6%)
Resnet-20 Warmup (6.9%
40
60
30
1.2 Distance
L2 Distance
L2 Distance
30
20
20
10
10
0
100
500
2K
10K
0
100
500
2K 10K
100
500
2K 10K
Rewinding Iteration (log)
Rewinding Iteration (log)
Rewinding Iteration (log)
17

---

Under review as a conference paper at ICLR 2020
VGG-16 Low (5.5%)
16 Warmup (1.5%)
VGG-16 (1.5%)
40
60
L. Distance
100
1.2 Distance
Distance
40
20
20
100 500 2K 10K
0
25 100 500 2K 10K
0
25 100 500 2K 10K
Rewinding Iteration (log)
Rewinding Tteration (Ing)
Rewinding Iteration (log)
The Le distance between IMP subnetworks follows the same pattern instability. When the net- work is unstable, the L2 distance plateaus at a higher level, the same level as randomly reinitialized and randomly pruned networks. As instability decreases, Le distance also decreases. When the subnetwork becomes stable, L2 distance platcaus at lower level than the randomly reinitialized and randomly pruned networks. Importantly, this lower level is still non-zero. These results trast with thise in Appendix D, where we do not observe a relationship between instability and L2 distance between the full networks.
18


Reviews:
[{"review_id": "rJlhQU77jr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis paper empirically examines an interesting relationship between mode connectivity and matching sparse subnetworks (lottery ticket hypothesis). \n\nBy mode connectivity, the paper refers to a specific instance where the final trained SGD solutions are connected by a linear interpolation path without loss in test accuracy. When networks trained with SGD reliably find solutions which can be linearly interpolated without loss in test accuracy despite different data ordering,  the paper refers to these networks as ‘stable.’ \n\nMatching sparse subnetworks refer to subnetworks within a full dense network that matches the test accuracy of the full network when trained in isolation.  \n\nThe paper introduces a novel improvement on the existing iterative magnitude pruning (IMP) technique that is able to find matching subnetworks even after initialization by rewinding the weights. This allowed the authors to find matching subnetworks for deeper networks and in cases where it could not be done without some intervention in learning schedule. \n\nThe paper then finds a relationship that only when the subnetworks become stable, the subnetworks become matching subnetworks.\n———\n\nAlthough finding a connection between two seemingly distinct phenomena is novel and interesting, I would recommend a weak reject for the following two reasons: \n1) The scope of the experiment is limited to a quite specific setting, \n2) there are unsupported strong claims which need to be clarified.\n———\n\n1)\nIn the abstract the paper claims that sparse subnetworks are matching subnetworks only when they are stable, but the results are shown in a limited setting only at a very high sparsity. \nThey tested stability on the highest sparsity level at which there was evidence that matching subnetworks existed, but how would the result generalize to other sparsity levels?\nWith lower sparsity level (if weights are pruned less), is stability easier to achieve? \n\nThe paper also focused on cases where matching subnetworks were found by IMP, but matching subnetworks can also be found by other pruning methods. \nAs acknowledged in the limitations section, other relationships may exist between stability and matching subnetworks found by other pruning methods, or in different sparsity levels,\nwhich could be quite different from this paper’s claim.\n\nIn order to address this concern, I think the paper needs to show how the same relationship might generalize to different sparsity levels, \nor alternatively modify the claim (to what it actually shows) and highlight the significance of the connection between matching subnetworks and stability in this highly sparse subnetwork regime.\n\n2) \nAs addressed above, in the Abstract and Introduction, the paper’s claims are very general about mode connectivity and sparsity, claiming in the sparse regime, “a subnetwork is matching if and only if it is stable.” However, the experiments only show it is true in a limited setting, focusing on specific pruning method and at a specific sparsity level.\nFurthermore, the statement is contradicted in Footnote 7: “for the sparsity levels we studied on VGG (low), the IMP subnetwork is stable but does not quite qualify as matching“\n\nThere are also a few other areas where there are unsupported claims.\n\n“Namely, whenever IMP finds a matching subnetwork, test error does not increase when linearly interpolating between duplicates, meaning the subnetwork is stable.” \n-> Stability was tested only at one specific sparsity level, and it is not obvious it would be stable at all lower sparsity levels where IMP found matching subnetworks.\n\n“This result extends Nagarajan & Kolter’s observation about linear interpolation beyond MNIST to matching subnetworks found by IMP at initialization on our CIFAR10 networks” \n-> Nagarajan & Kolter’s observation about linear interpolation was on a completely different setup: using same duplicate network but training on disjoint subset of data, whereas in this paper it uses different subnetworks and trains it on full dataset with different data order. \n\nRelated to the first issue, I think some of these stronger claims can be modified to describe what the experiments actually show. \nThe relationship found between stability and matching subnetworks in the high sparsity regime is a valuable insight that I believe should be conveyed correctly in this paper.\n\n———\n\nI also have some minor clarification question and suggestions for improvement. \n\nHow was the sparsity level (30%) of Resnet-50 and Inception-v3 chosen in Table 1? (which was later used in Figure 5)\n\n— In Figure 3 and 5, the y-axis “Stability(%)” is unclear and not explained how this is computed. I first thought higher amount of stability(%) was good but it doesn't seem to be true.\n\n— The ordering of methods for plots could be more consistent. In some figures VGG-19 come first and then Resnet-20 while for others it was the other way around, which was confusing to read. (Also same for Resnet-50 and Inception-v3)\n\n— There are same lines in multiple graphs, but the labeling is inconsistent, potentially confusing readers:\nFigure 1: (Original Init, Standard) is the same as Figure 4: (Reset), \nand Figure 1: (Random Reinit, Standard) is the same as Figure 4: (Reset, Random Reinit)", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "HyxwWTFAOS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper works on empirically demonstrating the connection between model connectivity and the lottery ticket hypothesis, which are individually explored in the literature. Here the model connectivity refers to the fact that SGD produces different solutions (from the randomness, such as data ordering) that are connected through model parameter transition paths of approximately equal loss/accuracy. The lottery ticket hypothesis tells that there exist sparse subnetworks of the corresponding full dense network which can attain as strong loss / accuracy as the full dense network. \n\nAs the primary contribution, the authors demonstrated that the following two observations often emerge together: 1) A sparse subnetwork can match the performance of the corresponding full dense network;  2) Running SGD on this sparse subnetwork produces solutions which are connected via a linear model parameter transition path of similar loss/accuracy; this is observed across both small tasks (using CIFAR10) and ImageNet-level tasks. Another contribution I can see besides the primary one is that the lottery ticket hypothesis still holds on large tasks, which is against the conventional wisdom demonstrated in recent papers (e.g. Gale et al., 2019); the authors show that it needs to rewind to weights after a short period of training instead of rewinding to the initialized weight in Iterative Magnitude Pruning to produce the \"lottery ticket\" in large tasks (such as CNN for ImageNet). \n\nI think the primary contribution on the connection between model connectivity and lottery ticket hypothesis is an interesting observation, but the content are poorly presented for me fully appreciate the importance and practical implications of this work. Thus I give weak reject. The major concerns and questions are as the following:\n\n1. From the paper, I don't understand why the connection between model connectivity and lottery ticket hypothesis is an important one to reveal. Is it important because it implies some practical approaches / heuristics to figure out performant sparse subnetworks? Is it intrinsically interesting because it validates some hypothesis in the training dynamics of SGD? These are not clear to me.\n\n2. I think the current presentation of the content is only limited to the empirical demonstration. And I can not extract useful intuitions/messages from the demonstration here on why this happens. These message should provide intuitions on why this connection exists. E.g. These message can be extracted from some SGD on some simple (toy) non-convex models with multiple local minimum regions.  \n\nMinor comments for improving the paper:\n\n1. At the end of line 1 in algorithm one, it is not clear what 1^|W0| means.\n\n2. The terms in figure legend needs to be properly defined to enable clear reading. Currently words such as \"reset\" is not mentioned in the text but appears in the legend of figure 4 and etc. \n\n\n\n\n\n\n\n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HygFbYdatS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper empirically presents a very interesting connection between two also very interesting phenomena (mode connectivity and lottery ticket hypothesis), while removing a previous limitation of the lottery ticket hypothesis on larger networks. through a good amount of experiments, the authors empirically showed these two phenomena co-occur together (i.e. matching networks are stable) and have positive correlation (i.e. the more “matching” the network the more “stable”), under different network architectures and datasets.\n\nThough it is unclear from the paper what are the immediate / straightforward applications, the findings do present interesting contributions. Several things I found that can further improve this paper.\n\nFirst, this paper lacks a structured literature review. It is suggested that the findings may provide insights to our understanding of how SGD works in neural network. Laying some proper background knowledge on this area is needed in the literature review. \n\nThere are several experiments that I’m curious to see. Though I must say the existing amount of experiments sufficiently validates the existence of the connection authors put forth and hence not required.\n\na) Provide some metrics on how “far” are the two final weights upon which mode connectivity (or stability) is explored. For the sake of comparison, distance between the initial weights and final weights can be added. \n\nb) First off, the introduction mentions connectivity was previously observed using “disjoint subsets” of data, whereas later in the paper only different orders of the same data are explored. I wonder if this is a typo. Regardless, exploring if the findings still apply on disjoint data and/or varying amount of data, besides different data orders, is helpful. \n\nc) Does the full network have the property of mode connectivity (when trained using different data orders), or this only occurs under sparsity.\n\nLastly, the writing of the paper doesn’t interfere with understanding, but can definitely use more work. Abstract can be tightened. Several typos throughout the paper:\n- in the abstract, \"with the no change\" -> remove \"the\"\n- bottom of page 1, subt -> sub\n- second bullet point under \"contributions\": remove \":\"?\n- page 3, paragraph starting with \"stability\": \"the increase in worst-case increase\" -> \"the worst-case increase\"?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates theories related to networks sparsification, related to mode connectivity and the so-called lottery ticket hypothesis.  The paper is interesting and has merit, but on balance I find the contributions not sufficiently clear to warrant acceptance.  The authors made substantial changes to the paper which are admirable and which bring it to borderline status. 

Decision: Reject