Winning the Lottery with Continuous Sparsification
Authors: Pedro Savarese
Hugo Silva
Michael Maire
Venue:  (2020)

Abstract: The Lottery Ticket Hypothesis from Frankle & Carbin (2019) conjectures that, for typically-sized neural networks, it is possible to find small sub-networks which train faster and yield superior performance than their original counterparts. The proposed algorithm to search for such sub-networks (winning tickets), Iterative Magnitude Pruning (IMP), consistently finds sub-networks with 90-95% less parameters which indeed train faster and better than the overparameterized models they were extracted from, creating potential applications to problems such as transfer learning.

In this paper, we propose a new algorithm to search for winning tickets, Continuous Sparsification, which continuously removes parameters from a network during training, and learns the sub-network's structure with gradient-based methods instead of relying on pruning strategies. We show empirically that our method is capable of finding tickets that outperforms the ones learned by Iterative Magnitude Pruning, and at the same time providing up to 5 times faster search, when measured in number of training epochs.

Under review as a conference paper at ICLR 2020
WINNING THE LOTTERY WITH CONTINUOUS SPARSIFICATION
Anonymous authors
Paper under double-blind review
ABSTRACT
The Lottery Ticket Hypothesis from Frankle & Carbin (2019) conjectures that, for typically-sized neural networks, it is possible to find small sub-networks which train faster and yield superior performance than their original counterparts. The proposed algorithm search for "winning tickets", Iterative Magnitude Pruning, consistently finds sub-networks with 90 95% less parameters which train faster and better than the overparameterrize models they were extracted from, creating potential applications to problems such as transfer learning.
In this paper, we propose Continuous Sparsification, a new algorithm to search for winning tickets which continuously removes parameters from a network dur- ing training, and learns the sub-network' 's structure with gradient- madientt-baedd methods instead of relying on pruning strategies. We show empirically that our method is capable of finding tickets that outperforms the ones learned by Iterative Magnitude Pruning, and at the same time providing faster search, when measured in number of training epochs wall-clock time.
INTRODUCTION
Although deep neural networks have become ubiquitous in fields such as computer vision and natural language processing, extreme overparameterization is typically required to achieve state-of- the-art results (Xie al., 2017; Devlin et al., 2018)), causing higher training costs and hindering applications where memory inference time are constrained. Recent theoretical work suggest that overparameterization plays a key role both the capacity and generalization of network (Neyshabur et al., 2018), and in training dynamics (Allen-Zhu et al. 2019). However, it remains unclear whether overparameteriiztion truly necessary to train networks to state-of-the-ar performance.
At the same time, empirical approaches have been successful in finding less overparameterizee neural networks, either by reducing the network after training (Han et al.) [2115] 2016) or through
more efficient architectures that can be trained from seratch (landola et | 2016). Recently, the
combination of these two approaches lead to new methods which discover efficient architectures through optimization instead of design (Liu al.. 2019: Savarese & Maire 2019). Nonetheless,
parameter efficiency is typically maximized by pruning an already trained network.
The fact that pruned networks are hard to train from scratch (Han al. 2015 2016) suggests that, while overparameterization is not necessary for model's 's capacity, it might be required for successful network training. Recently, this idea has been put into question by Frankle Carbin (2019), where heavily pruned networks are trained faster than their original counterparts, often yielding superior performance.
A key finding is that the same parameter initialization should be used when re- re-training the pruned network. A winning ticket, defined by sub-network and setting of is quickly trainable and has already found applications in, for example, transfer learning (Morcos) al. 2019 Mehta 2019 Soelen & Sheppard 2019) making the search for winning tickets problem of independent interest.
initializi parameters.
Currently, the standard algorithm to find winning tickets is Iterative Magnitude Pruning (IMP) (Frankle & Carbin 2019 Frankle et al. 2019), which consists of a repeating 2-stage procedure that alternates between parameter optimization and pruning. As a result, IMP relies on a sensible finding a winning ticket with 1% of the original parameters a 6-layer CNN requires over 20 rounds of training followed by pruming, totalling over 1000 epochs (Frankle & Carbin 2019). Choosing parameter's magnitude pruning criterion
choice for pruning strategy, and is

---

Under review as a conference paper at ICLR 2020
has also shown to be sub-optimal in some settings (Zhou et al. 2019), leading to the question of whether better winning tickets can be found by different pruning methods. Moreover, at each iteration, IMP resets the parameters of the network back to initialization, hence considerable time is spent re-training similar networks with different sparsities.
With the goal of speeding up the search for winning tickets in deep neural networks, we design a novel method, Continuous Sparsification, which continuously removes weights from a network during training, instead of following strategy to prune parameters at discrete time intervals. Unlike IMP, our method approaches the search for sparse networks as a fn-regularized optimization problem (Louizos al., 2017). resulting in method that can be fully described in the optimization framework. To approximate Eg rerrgularization, we propose a smooth re- parameterization, allowing for the sub- network's 's structure to be directly learned with gradient- -ased methods. Unlike previous works, our re-parameterization is deterministic, proving more convenient for the tasks of pruning and ticket search, while also yielding faster training times.
Experimentally, our method offers superior performance when pruning VGG to extreme regimes, and capable of finding winning tickets Residual Networks trained on CIFAR-IO a fraction of time taken by Iterative Magnitude Pruning. In particular, Continuous Sparsification successfully finds tickets in under 5 iterations, compared to 20 iterations required by Iterative Magnitude Pruning in the same setting. To further speed up the search for sub-networks, rewinding, a key ingredient of Iterative Magnitude Pruning. By showing superior results without rewinding, our experiments offer insights on how ticket search should be performed.
method abdicates parameter
2 RELATED WORK
2.1 LOTTERY TICKET HYPOTHESIS
The Lottery Ticket Hypothesis (Frankle & Carbin 2019) states that for network fa;; w), w E Rd, and candomly-nnitiaizze parameters We ~ D, there exists a sparse sub-network, defined by a configu- ration m {0, 11d, || < d, that, when trained from scratch, achieves higher performance than f(; u:) while requiring fewer training iterations. The authors support this conjecture experimentally, showing that such networkss indeed exist: in particular, they can be discovered by repeatedly train- ing, pruning, and re-initializing the network, through procedure named Iterative Magnitude Pruming (IMP: Algorithm DT (Frankle et al. 2019). More specifically, IMP alternates between: (1) training the weights w of a network, (2) removing a fixed fraction of the weights with the smallest magnitude (pruning), and (3) rewinding: setting the remaining weights back to their original initialization Wo.
The sub-networks found by IMP, which indeed train faster and outperform their original. dense networks, are called winning tickets, and can generalize across datasets (Mehta 2019] (Sollnn & Sheppard 2019) and training methods (Morcos et al. 2019). In this sense, IMP can be promising tool in applications that involve knowledge transfer, such as transfer or meta learning.
Zhou et al. (2019) perform extensive experiments re-evaluate and better understand the Lottery Ticket Hypothesis. Relevant to this work is the fact that the authors propose a method to learn the binary mask m in end-to-end manner through SGD, instead of relying on magnitude- based pruning. The authors show that learning only the binary mask and not the weights is sufficient to achieve competitive performance, confirming that the learned masks are highly dependent on the initialized values Wp. and are also capable of encoding substantial information about a problem's 's solution.
2.2 SPARSE NETWORKS
The core aspect of searching for winning ticket is finding sparse sub-network that attains high performance relative to its dense counterpart. One way to achieve this is through pruning methods (LoCun et al. 1990), which follow a strategy to remove weights from a trained network while minimizing negative impacts its performance. In Han et al. (2015). network is iteratively trained and pruned using parameter magnitudes as criterion: this iterative, two-stage algorithm is shown to outperform "one-shot pruning": training and pruning the network only once.
Other methods attempt to approximate 4 regularization on the weights of a network, yielding one- stage procedures that can be fully described in the optimization framework. In order to find a sparse
2

---

Under review as a conference paper at ICLR 2020
Algorithm I Iterative Magnitude Pruning (Frankle et al. 2019)
1: Initialize to <- wp ~ 'D and m < 7d
2: Minimize [[f(2; O w)) until wr produced
3: Set m, 0 for the active weights with smallest magnitudes (/wT,sl S T and my 1)
4: If satisfied, output ticket f(; m O wy)
5: Otherwise, set w < and go back to step 2
Algorithm 2 Iterative Stochastic Sparsification (inspired by Zhou et al. (2019))
1: Initialize < wo D, <- 50
2: Minimize (e)(ar(((s)) (I; m @ w))l + X (s)ll, until wr and sy are produced
3: If satisfied, output ticket f (a; m O wK), m ~ Ber(o (st))
4: Otherwise, set <- Wk, 8 +- -o0 for 8,, < $1,u, and go back to step 2
setting 10, of network fa; @ w). Srinivas al. 2016) and Louizos al. 2011 7 use stochastic re- parameterization m Bernouli(g(s)) with E K.T and R. + [0. 1] applied element-wise First-order methods, coupled with gradient estimators, are then used train both w and to minimize the expected loss. This approach performs continuous parameter removal during training an automatic fashion: any component s; of that assumes a value during training where g(s)) 0 effectively removes w; from the network. Moreover, approximating &o regularization has the advantage of not requiring a pruning strategy, which might be arbitrarily complex.
3 METHOD
Designing method to quickly find winning tickets requires an efficient way to sparsify networks: ideally, sparsification should be done early as possible in training, and the number of removed parameters should be maximized without harming the model's performance. In other words, sparsifi- cation must be continuously maximized following a trade-off with the performance of the network. This goal is not met by Iterative Magnitude Pruning: sparsification is done at discrete time steps, only after fully training the network, and optimal pruning rates likely depend on the model's performance and current sparsity: factors which are typically not accounted for note that these are inherent characteristics of magnitude-based pruning.
In light of this, we turn to fo-regularization methods for learning sparse networks, which consist of optimizing clear trade-off between sparsity and performance. As we will see, performing sparsification continuously is not only straightforward, but done automatically by the optimizer.
3.1 CONTINUOUS SPARSIFICATION BY LEARNING DETERMINISTIC MASKS
We first frame the search for sparse networks loss minimization problem with to regularization (Louizos et al. 2017 Srinivas et al., 2016):
min L(f(2; w)) + X l|wllo wERd
where À 2 O controls the sparsity of the solution, and, with a slight abuse of notation, (a; w)) denotes the loss incurred by the network f(; w) (e.g., the cross-entropy loss over training set). As lo regularization is typically intractable, we re-state the above minimization problem as:
min L(f(z; w)) A ||m|| wER" 10
which uses the fact that, for m E {0, 1]4, |lm = || The & term can be minimized with subgradient descent, however the m E {0, 1]d constraint makes the above problem combinatorial
and poorly suited for local search methods like SGD.
3

---

Under review as a conference paper at ICLR 2020
Algorithm 3 Continuous Sparsification
1: Initialize <- wo D, 8 & 80. 8 80
2: Minimize L[ 8) o w)) + A [as)B while increasing 3, producing wr, 87, and ,T
3: If satisfied, output ticket f fæ; b(sr) @ wk)
4: Otherwise, set s +- min(3r sr, So), 3 - 3o. (optionally, w < wo), and go back to step
3 200
1.5
B 4
G
B
1.0
(333)
b(2)
0.5
0.0
-0.5
2.5 0.0 2.3
-2. 0.0 2.5 -2. 0.0 2.5
-2. 0.0 2.5
2
2
2
2
Figure 1: Illustration of our proposed re- parameterization m = (Bs), where o(2) = 14e-= the
sigmoid function and / acts as a temperature. As 33 increases, a (3z) approaches b(=). which can can be used to frame a Eo-regularized problem (Equation 4 Note that the gradients of (Bs) vanish as increases, suggesting that B should be annealed slowly during training.
We can avoid the binary constraint m e 10. by re- parameterizing m function of newly- introduced variable E RR For example, Louizos et al. (2017) propose stochastic mapping + m and use gradient methods minimize the expected total loss, while using estimators for the gradients of (since m is still binary). Having stochastic mask (or, equivalently, distribution over sub- networks) poses an immediate challenge for the task of finding tickets, as it is not clear which ticket should be chosen once a distribution over is learned. Moreover, relying on gradient estimators often causes gradients to have high variance, requiring longer training to reach optimality. Alternatively, consider deterministic parameterization applicd element-wise:
b(s), where Rd and b R40 > {0, 1) is
1, >>>>0 0
b(z)
(3)
0. if 0
Applying this re-parameterization to Equation 2 yiclds:
min (((( [bb())
(4)
werd
.ER
Clearly, the above problem again intractable, as it is still equivalent to the original la problem in Equation [ More specifically, the step function b(z) is non-convex, and having zero gradients make gradient-basee optimization ineffective, Instead, we consider the following smooth relaxation of 6(-):
m = o(
(5)
where 3 E IR and the sigmoid function (=)) = I+e-r applied element-wise By controlling 3, which acts as temperature parameter, we effectively interpolate between o (s)). smooth function well-suited for SGD, and limg-rgo aB (3--- s) b(2), our original goal, which brings computational hardness to the problem. Figure illustrates this behavior. Note that, if Lf w)) is continuous in w, then:
4

---

Under review as a conference paper at ICLR 2020
min lim L(f(r o w)) + + ||o(3))] min b(((;;((s) + A [[(()]] "ER" 5-000 sER
wER* sER
(6)
Although gradient methods will become ineffective as 3 - do due to vanishing gradients of 8, we can increase 3 while optimizing and w with gradient descent. That our loss each iteration will be a function of 3 as follows:
Ls(w, 8) = L(f(xx @ w)) + A 11o(3 s)ll
How does the soft mask m aB3- behave as minimize (s s) while increasing B? As - 0o, every negative component of s will be mapped to 0, effectively removing its correspondent weight parameter from the network. While analytically the weights will never truly be zeroed-out, limited numerical precision has the fortunate side-effect causing actual sparsification to the network large enough value.
during training, long as 3 increased
In nutshell, we learn sparse networks by minimizing Ly(w, s) for I" parameter updates with gradient descent while jointly annealing 3: producing wr, ST and 3r, which ideally large enough such that, mumerically (5r sr) = b(sT). In case m is truly required to be binary (as in the task of finding tickets), the dependence on numerical imprecision can avoided by directly outputting m b(sT) at the end of training.
Finally, note that minimizing L, while increasing 3 not generally equivalent to minimizing the original fo-regularized problem. Informally, the former aims to solve limg min,,s (w, 8). while the & problem is min lim3- Lg(
3.2 TICKET SEARCH THROUGH CONTINUOUS SPARSIFICATION
The method presented above offers direct alternative to magnitude-based pruning when performing ticket search, but a few considerations must follow. Most importantly, when searching for winning tickets, there is strict constraint that the learned mask be binary: otherwise, the magnitude of the weights, defeating the purpose finding sub- nub-networks that can be trained from scratch. To guarantee that the output mask satisfies this constraint regardless of numerical precision, we always output ((ST) instead of (33 88).
also learn
Additionally, we also incorporate networks and searching for winning tickets. First, motivated by Han et al. (215)). where it is shown that iteratively pruning network yields improved sparsity compared to pruning it only once, enable "kept" weights- those whose corresponding component of is positive after many iterations be removed from the network at later stage. More specifically, when 3 becomes large after T gradient descent updates, the gradients of vanish and weights will no longer be removed from the network. avoid this, we set a f- min(3r. 8T, 8o), effectively resetting the soft mask parameters for the remaining weights while at the same time not interfering with weights that have been removed. This is followed by a reset on the temperature, 8 + Sg. to allow training of s once again.
techniques from successful methods for learning sparse
Second, we perform parameter rewinding, following Frankle & Carbin (211)), which is key component of Iterative Magnitude Pruning. More specifically, after gradient descent steps, we reset the weight values back to earlier stage results in Frankle & Carbin (2019) suggest that rewinding is necessary for successful ticket search, will see empirically, turns
Wk. where k < T. Even though experimental
we leave rewinding as optinal component of our algorithm: that ticket search is possible without rewinding weights. Our proposed algorithm to find winning tickets is presented as Algorithm and referred simply as "Continuous Sparsification".
We observed in our experiments that final temperature of 500 is sufficient for iterates of s when training with SGD with 32-bit precision. The required temperature is likely to depend on the how is numerically represented, reality method relies on numerical imprecision.
5

---

Under review as a conference paper at ICLR 2020
4 EXPERIMENTS
Our experiments aim at comparing different methods on the task of finding winning tickets in neural networks, hence evaluation focuses on the generalization performance of each ticket (sub-network) when trained from scratch (or from an iterate in early-training). Additionally, we measure the cost of the search procedure: the number of training epochs to find tickets with varying performance and sparsity.
Besides comparing our proposed method to Iterative Magnitude Pruning (Algorithm D.. we also design a baseline method, Iterative Stochastic Sparsification (ISS, Algorithm 2. motivated by the procedure in /hou al. (2019) to find a binary mask with gradient descent in end-to-end fashion. More specifically, ISS uses stochastic pe-aaameterrzatioon m ~ Bernoulli( E pdd and trains w and s jointly with gradient descent and the straight-through estimator (Bengio et al, 2013). When ran for multiple iterations, all components of the mask parameters which have decreased in value from initialization are set to -0,, such that the corresponding weight is permanently removed from the network. While this might look arbitrary, we observed empirically that ISS was unable to remove weights quickly without this step unless was chosen to be large- in which case the model's performance decrease in exchange for sparsity. The hyperparameters used in this section were chosen based on analysis presented in Appendix (...), where we study how the pruning rate affects IMP, and how X, so and 3T interact in CS.
with
4.1 CONVOLUTIONAL NEURAL NETWORKS
We train a neural network with 6 convolutional layers on the CIFAR-10 dataset (Krizhevsky) 2009), following Frankle & Carbin (2019). The network consists of 3 blocks of 2 eesoouutio-preseervee convolutional layers followed by 2 x max-pooling, where convolutions in each block have 64, 128 and 256 channels, 3 x kernel, and immediately followed by ReLU activations. The blocks are followed by fully-connected layers with 256, 256 and 10 neurons, with ReLUs in between. The network is trained with Adam (Kingma & Ba 2015) with a learning rate of 0.0003 and a batch size of 60.
Learning a Supermask: As a first baseline, we consider the task of learning "supermask" (Zhou iet al. 2019):: a binary mask m that, when applied to network with randomly initialized weights, yields performance competitive to that of training its weights. This task is equivalent to pruning a randomly-initaaizzed network, or learning an architecture that performs well prior to training with fixed initialization. We compare ISS and CS, where each method is run for a single iteration composed of 100 epochs. When ran for a single iteration, ISS is equivalent to the algorithm proposed in Zhou et al. 2019)) to learn a supermask, referred here as simply Stochastic Sparsification. We control the sparsity of the learned masks by varying 8 between -5 and 5 for Stochastic Sparsification (which showed to be more effective than varying A), while for Continuous Sparsification we vary between 10-11 and 10- (which results in stable and consistent training. unlike varying su). SS uses SGD with a learning rate of 100 to learn its mask parameters, while CS uses Adam with 3 x 10-1.
Results presented in Figure 2 CS outperforms SS in terms of both training speed and the quality of the learned mask. In particular, CS finds masks with over 75% sparsity that yield over 75% test accuracy, while the performance of masks found by SS decrease when sparsity is over 50%. Moreover, CS makes faster progress in training, showing that optimizing a deterministic mask is indeed faster than learning a distribution over masks through stochastic re-parameterizations.
We run IMP and ISS for total of 30 iterations, each consisting of 40 epochs. Parameters are trained with Adam (Kingma & Ba 2015) with a learning rate of 3 x 10 fol- lowing Frankle & Carbin (2019). For IMP, we use pruning rates of 15%/20% for convolutional/dennse layers. We initialize the Bernoulli parameters of ISS with 8q i. and train them with SGD and learning rate of 20, along with a E1 regularization of X- = 10 8 For CS we anneal the temperature from 30- = 1 to 3 = 250 following an exponential schedule (8, = 250 +) ), training both the weights and the mask with Adam and learning rate of 3 x 10-4.
Finding Winning Tickets:
To test whether our method is capable of finding winning tickets in a limited amount of time, we limit each run of CS to 4 iterations only, in contrast with IMP and ISS which are run for 30. We perform 6 runs of CS each with a different value for the mask initialization sp: -0.05, -0.03, -0.02, -0.01, -0.005, 0, keeping À= 10-10, such that sparsification is not enforced during training. but heavily

---

Under review as a conference paper at ICLR 2020
80
70-
70
60
Text Accuracy (5)
Teat Arounecy
50
Gioeheatic Spamification Continuous Starsiniationn
Soxceetic Sparaiicaioo
Contraooa Sparaticare
10
20
30
50
60
70
90
100
20
Esoch
Parcentage: weights remaining
Figure 2: Learning binary mask with weights frozen initialization with Stochastic Sparsification (SS, Algorithm@wiit one iteration) and Continuous Sparsification (CS), on a 6-layer CNN on CIFAR- Training curves with hyperparameters for which masks learned by SS and CS were both approximately 50% sparse. CS learns the mask significantly faster while attaining similar early-stop performance. Right: Sparsity and accuracy of masks learned with different settings for SS and CS: our method learns sparser masks while maintaining test performance, while SS is unable to successfully learn masks with over 50% sparsity.
10. Left:
85
94
Tee Aecurnyy (0)
Teal Recuracy (h1)
400
Benaiiv Segeiude Pranng
Pentive Magehude Prining (rents)
Inndie Magnitute Fruning
Haraliv Slachade
Aasolte Mugattzze Pruiin bunt)
54
Condinuzus Spartficat fesst trainto
Cenoraauss Spars roat gharttt
100.0
$1.4
26.5
13.7
7.1
3.7
1.0 100.0
$1.4
26.5
12.7
3.7
1.9
Percentage weightts permiining
Percentagc of weighss remaining (90)
Figure 3: Test accuracy of tickets found by different methods on CIFAR-I0. Error bars depict variance across 3 runs. Left: Performance of tickets found on 6-layer CNN, when trained from scratch. Right: Performance of tickets found on a ResNet 20, when rewinded to the second training epoch. In both experiments, tickets found by CS outperform ones found by IMP. In most cases, CS successfully finds winning tickets iterations (purple curves).
biased initialization. In order to evaluate how consistent our method is, we repeat each run with different random seeds so that error bars can be computed.
Figure (left) presents the quality of tickets found by each method, measured by their test accuracy when trained from scratch. To illustrate the quality of the tickets that can be found by Continuous Sparsification, we plot the Pareto curve (green) of the tickets founds with the 6 different values for 80. With 80 -0.03, in only iterations CS finds a ticket with over 77% sparsity (first marker of purple curve) which outperforms every ticket found by IMP its 30 iterations. The Pareto eurve of CS strictly dominates IMP for tickets with more less than 97% sparsity, where ticket performance is superior or similar to the original dense network.
In terms of computational time, the total cost to CS with the different values for is lower than performing a single run of IMP for 30 iterations, even though CS takes 15% extra time per epoch due the mask parameters. This shows the potential of our model in the setting where specific sparsity is desired for the tickets. When run in parallel, CS takes less wall-clock time to find all tickets in the Pareto curve than to IMP for 5 iterations.
7

---

Under review as a conference paper at ICLR 2020
4.2 FINDING WINNING TICKETS IN RESIDUAL NETWORKS WITHOUT REWINDING
Searching for tickets in realistic models is not as straightforward as finding tickets in a small CNN, and might require new strategies. Frankle et al. (2019) show that IMP fails at finding winning tickets in ResNets (He et 2016) unless the learning rate is smaller than the recommended value, leading to worse overall performance and defeating the purpose of ticket search. However, the authors propose a slight modification to IMP that enables search for winning tickets to be successful on complex networks: instead of training from scratch, tickets are initialized with weights from early training.
With this in mind, we evaluate how Continuous Sparsification performs in the time- consuminn task of finding winning tickets in a ResNet-20 (He et al. 2016) trained on CIFAR-10: setting where IMP might take over 10 iterations (850 epochs) to succeed. We follow the setup in Frankle & Carbin (2019) and Frankle et al. (2019): in each iteration, the network is trained with SGD, a learning rate of 0.1, and momentum of 0.9 for total of 85 epochs, using a batch size of 128. The learning rate is decayed by a factor of 10 at epochs 56 and 71, and a weight decay of O. 0.0001 is applied to the weights (for CS we do not apply weight decay to the mask parameters s). The two skin-connestions that perform 1 x convolutions and the output layer are not removable: for IMP, their parameters are not pruned, while for CS their weights do not have correspondent mask m nor mask parameters s.
When training the returned tickets in order to evaluate their performance, we initialize their weights with the iterates from the end of epoch 2 (780 parameter updates), similarly to Frankle al. (2019). Unlike when searching for winning tickets in the 6-layer CNN, IMP performs global pruning, removing 20% of the remaining parameters with smallest magnitude, ranked globally (across different layers). IMP runs for a total of 30 iterations, while CS is limited to only 5 iterations for each run. The sparsity of the tickets found by CS is controlled by varying the mask initialization so e {-0.3, -.2 1.11, - 0.05, - 0.03, O. 0.03, 0.05, 0.1, 0.2, 0.3) (a total of 11 values). To allow for even faster ticket search, we run CS without parameter rewinding: that is, the weights w are transferred from one iteration to another, removing the need to re-train the network the method progresses through iterations. For both CS and IMP, each run is repeated with different random seeds.
The results presented in Figure 3 (right) show that CS is able to successfully find winning tickets with varying sparsity in under 5 Ierations. Once again, the Pareto curve strictly dominates IMP, and variance across runs is smaller than IMP's. Most notably, CS is capable of quickly sparsifying the network in single iteration (first marker of each purple curve), and typically finds better tickets than IMP after only 2 rounds (compare blue curve and second marker of each purple curve), regardless of sparsity. When run in parallel, 2 iterations suffice for CS to find tickets that outperform the ones found by IMP.
We observed that not performing rewinding caused the performance of tickets with high sparsity to quickly degrade after 2 or more iterations of CS. We speculate that, when rewinding is not performed between iterations, the distance between wy and the parameter iterates produced by gradient descent W/ increase significantly with the number of iterations. This in turn can result in the learned mask mr to be highly sub-optimal for weight values w/ (k < T) which are used re-train the ticket. This suggests that in order to avoid re-training the network and hence make the search for winning tickets more efficient, rewinding should not be performed between iterations. In this case, the search must complete quickly, before performance degradation occurs due to "overtraining", requiring optimal ways to perform sparsification without negatively impacting the model's performance.
4.3 PRUNING VGG
Our experiments show that Continuous Sparsification is capable of finding tickets quickly and consis- tently, and we attribute its success to its deterministic re- parameterization of the binary mask. Here, we evaluate our method a pruning technique, to better assess whether our proposed ce-parameterization is advantageous only in terms of training time, or also in respect to the quality of the learned masks.
For this task, train VGG (Simonyan & Zisserman 2015) the CIFAR-10 10 dataset, following the protocol in Frankle & Carbin (2019): the network is trained with SGD and an initial learning rate of 0.1, which is decayed by factor of 10 at epochs 80 and 120. After 160 training epochs, the network
We used the same network as Frankle & Carhin 2019) and Frankle et al. 2019), where it is referred as
ResNet 18.
8

---

Under review as a conference paper at ICLR 2020
is sparsified and then fine-tuned for 40 epochs with learning rate of 0.001. We evaluate previously described methods when executed for a single iteration (one-shot pruning): Continuous Sparsification, Magnitude Pruning (IMP with iteration) (Han et al. (2015), and Stochastic Sparsification (ISS with 1 iteration), which similar to methods in /hou et al. (2019). (Srinivas et al. (2016). and Louizos al. (017))
At the sparsification step, IMP performs global pruning, ISS fixes the binary mask m be the maximum likelihood one under (er( (which performed better than sampling from the distribution), and CS changes the parameteriza- tion of the mask from o (Bs) to b(s) (or, equiv- alently, weights where 8; < O are removed). We use momentum of 0.9, a weight decay of 0.0001 (not applied to s). and batch-size of 64.
Tox Kouuaay 760
Following Frankle Carbin (2019). sparsifica- tion is not applied to batch normalization nor the final linear layer.
84
Kogeituur musing Stehartic Spantfictton
To evaluate each method when finding masks with different sparsity levels, we run IMP with
100.0
51.4
265
13.7
7.1
3.7
1.5
1.0
0.5
0.3
01
Percentage of we ghis remaarinn
global pruning rates 50%, 75%, 80%, 85%, 90%, 95%, 97.5%, 98%, 98.5%, 99%, 99.5%. 99.75%, and ISS and CS with initial mask val- ues 0.3, -0225, -0.2, -0.15. -0.1, -0.05. -0.01. 00.055 -0.001, Results are shown in Figure A both magnitude pruning and stochastic lg regularization (Stochastic Sparsifi-
Figure 4: Performance of different methods when performing one-shot pruning on VGG. CS main- tains over 90% test accuracy after removing 99.7% of the weights, while other methods fail success- fully remove more than 98% of the parameters.
cation) fail at removing over 98% of the weights without severely degrading the performance of the model. On the other hand, Continuous Sparsification successfully removes 99.7% the parameters in the convolutional layers while still yielding over 90% test accuracy. When taken to the extreme, our method is capable of removing 99.85% of the weights and still yield over 83% accuracy.
The dramatic performance difference between stochastic and continuous sparsification shows that proposed deterministic re- parameterization is key to achieve superior results in both network pruming and ticket search. The fact that it outperforms magnitude pruning, standard technique in the pruning literature, suggests that further exploration of b--aaeed methods could yield significant advances in pruning techniques.
5 DISCUSSION
With Frankle & Carbin 2019), we now realize that sparse sub-networks can indeed be successfully trained from seratch, putting question the belief that overparameterization is required for proper optimization of neural networks. Such sub-networks, called winning tickets, can be potentially used to significantly decrease the required resources for training deep networks, as they are shown to transfer between different, but similar, tasks (Mehta 2019 Soclen & Sheppard 2019).
Currently, the search for winning tickets is a poorly explored problem, where Iterative Magnitude Pruning (Frankle & Carbin 2019) stands as the only algorithm suited for this task, and it is unclear whether its key ingredients post-training magnitude pruning and parameter rewinding are the correct choices for the task. Here, we approach the problem of finding sparse sub-networks as an lo-regularized optimization problem, which we approximate through a smooth, parameterized relaxation of the step function. Our proposed algorithm for finding winning tickets, Continuous Sparsification, removes parameters automatically and continuously during training, and can be fully described by the optimization framework. We show empirically that, indeed, post-training pruning might not be sensible choice for finding winning tickets, raising questions on how the search for tickets differs from standard network compression. With this work, we hope to further motivate the problem quickly finding tickets in overparameterized networks, as recent work suggests that the task might be highly relevant to transfer learning and mobile applications.

---

Under review as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. ICML, 2019.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation. arXiv e-prints, art. arXiv:1308 130..333, 2013.
Jacob Devlin, Ming- Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. arXiv e-prints, art. arXiv: 180:000800.05 2018.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In ICLR, 2019.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, and Michael Carbin. Stabilizing the Lottery Ticket Hypothesis. arXiv e-prints, art. arXiv:1903.0161, 2019.
Song Han, Jeff Pool, John Tran, and William J. Dally. Learning both weights and connections for efficient neural networks. NIPS' 15, 2015.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. ICLR, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, 2016.
Forrest N. landola, Matthew W. Moskewicz, Khalid Ashraf, Song Han, William J. Dally, and Kurt Keutzer. SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <IMB model size. arXiv:1602.07360, 2016.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR, 2015.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Yann LeCun, John S. Denker, and Sara A. Solla. Optimal brain damage. In NIPS. 1990.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. ICLR, 2019.
Christos Louizos, Max Welling, and Diederik P. Kingma. Learning Sparse Neural Networks through Lo Regularization. arXiv e-prints, art. arXiv:1712.01312, 2017.
Rahul Mehta. Sparse Transfer Learning via Winning Lottery Tickets. arXiv e-prints, art. arXiv:1905.07785, 2019.
Ari S. Morcos, Haonan Yu, Michela Paganini, and Yuand ong Tian. One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers. arXiv e-prints, art. arXiv:1906.02773. 2019.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards Understanding the Role of Paramttramttinntioonn in Generalization of Neural Networks. arXiv e-prints,
2018.
Pedro Savarese and Michael Maire. Learning implicitly recurrent CNNs through parameter sharing. In ICLR, 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. ICLR, 2015.
Ryan Van Soelen and John W. Sheppard. Using winning lottery tickets in transfer learning for convolutional neural networks. In IJCNN, 2019.
Suraj Srinivas, Akshayvarun Subramanya, and R. Venkatesh Babu. Training Sparse Neural Networks. arXiv e-prints, art. arXiv: 1.06694, 2016.
10

---

Under review as a conference paper at ICLR 2020
Saining Xie, Ross B. Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. CVPR, 2017.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. ArXiv, abs/1905.01067, 2019.

---

Under review as a conference paper at ICLR 2020
APPENDIX
A HYPERPARAMETER ANALYSIS
A.1 CONTINUOUS SPARSIFICATION
In this section, we study how the hyperaarameters Continuous Sparsification affect its performance in terms of sparsity and performance of the found tickets. More specifically, consider the following hyperparameters:
Final temperature 3y: the final value for 3, which controls how smooth the parameterization m = (B3) is.
{1 penalty X: the strength of the regularization applied to the soft mask (Bs), which promotes sparsity.
Mask initial value sy: the value used initialize all components of the soft mask m (Bs). where smaller values promote sparsity.
Our setup is as follows: to analyze how each of the 3 hyperparameters impact the performance of Continuous Sparsification, we train ResNet 20 on CIFAR-10 (following the same protocol from Section 4.2) varying one hyperparameter while keeping the other two fixed. To capture how hyperparameters interact with each other, we repeat the described experiment with different settings for the fixed hyperparameters.
Since different hyperparameter settings naturally yield vastly distinct sparsity and performance for found tickets, we report relative changes in accuracy and in sparsity.
In Figure 5 we vary À between 0 and 10-8 for three different (so: 3o) settings: (sp = -0.2, Br 100), (5g 0.05, 3r = 200), and (sp = 0.3,, Br 100). As we can see, there little impact on either the performance 3r = 200, for which À = 10 yields slightly increased sparsity.
the sparsity of the found ticket, except for the case where so 0.05 and
33th -82 20-
Sy- 0.5 230
-03 8-0
20
0.20
Tox Reatvv Accurssy (N
Relatve Woights Romaining
10
0.10
10
-20
regudatizer
6 regularizer
Figure 5: Impact on relative test accuracy and sparsity tickets found in a ResNet 20 trained on CIFAR-10, for different values of À and fixed settings for BT and 50.
Next, we consider the fixed settings (so -0.2, 10 10-10011100 19), (so 0.05, X 10 10-12), (so
-0.3, A = 10-$), and proceed to vary the final temperature 3y between 50 and 200. Figure
shows the results: in all cases, a larger temperature of 200 yielded better accuracy. However,
decreased sparsity compared to smaller temperature values for the settings (sp = - 0.2, A 10
and (5g = 0.33, 10-8), while at the same time increasing sparsity for (sp = 0.05, = 10 While larger temperatures appear beneficial and might suggest that even higher values should be used, note that, the larger 3r is, the earlier in training the gradients training of the mask will stop. Since the performance for temperatures between 100 and 200 does not change significantly, we recommend values around 150 or 200 when either pruning or performing ticket search.
10
will vamish, at which point
12

---

Under review as a conference paper at ICLR 2020
Ja Satoy Aa
20
0.20
Tos Reaatre Accurscy (S)
Weigts Ramainino
10-
0.30
0.00
20
50
160
150
200
250
300
50
160
150
200
250
300
Finsl Temperature
Pnail Temperature (p+)
Figure 6: Impact relative test accuracy and sparsity of tickets found in ResNet 20 trained CIFAR-10, 10, for different values of By and fixed settings for À and 80-
1.00
20
0.80
Tost Relatve Actrocy (5)
Belativv Weights Remaning
10
0.60
-0.30
-0.20
-0.30
0.00
0.10
0.20
0.30
-0.30
-0.20
-0.30
0.10
0.20
0.30
Initial masks
Figure 7: Impact relative test accuracy and sparsity of tickets found in ResNet 20 trained on CIFAR-10, for different values of sy and fixed settings for Bg and
Lastly, we vary the initial mask value so between -0.3 and +0.3, with hyperpameter settings (Br = 100, À = 10-11), (3r = 200, A = 10-10-2 12), and (3r = 100, A = 10-8). Results are given in À and Sr, can that sp has a strong and consistent effect
Figure 7 unlike the exploration on the sparsity of the found tickets. For this reason, we suggest proper tuning of so when the goal achieve specific sparsity value. Since the percentage remaining weights is monotonically increasing with so, can perform binary search over values for to achieve any desired sparsity level. terms of performance, lower values for 8p naturally lead to performance degradation, since sparsity quickly increases so becomes more negative.
13

---

Under review as a conference paper at ICLR 2020
Test Accuracyy (96)
90
88
84
prune rale
INP: prune rate 2.4
IMP. prune rate 2.6
100.0
Percentage of geis ramaining 196
Figure 8: Performance of tickets found by Iterative Magnitude Pruning in a ResNet 20 trained on CIFAR, for different pruning rates.
A.2 ITERATIVE MAGNITUDE PRUNING
Here, we assess whether the running time of Iterative Magnitude Pruning can be improved by increasing the amount of parameters pruned each iteration. The goal of this experiment is to evaluate if Continuous Sparsification offers faster ticket search only because it prunes the network more aggressively than IMP, or because it is truly effective in how parameters chosen to be removed.
Following the same setup as the previous section, train a ResNet 20 CIFAR-10. We IMP for 30 iterations, performing global pruning with different pruning rates at the end of each iteration. Figure shows that the performance of tickets found by IMP decays when the pruning rate is increased to 40%. In particular, the final performance of found tickets is mostly monotonically decreasing with the number of remaining parameters, suggesting that, in order find tickets which outperform the original network, IMP is not compatible with more aggressive pruning rates.
14


Reviews:
[{"review_id": "SJlzXqz19r", "reviewer": "AnonReviewer2", "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 work propose a new iterative pruning methods named Continuous Sparsification. It will continuously prune the current weight until it reaches the target ratio instead of iterative prune the weight to specific ratio. The author gives a good analysis but the experiment is not yet convincing enough.\n\n1) This work actually presents compression algorithm with little connection with lottery ticket. As a lottery ticket discussion, it does not give the comparison between lottery ticket and random initialization based on new pruning method. As a pruning method, it does not show the results on common models like VGG and DenseNet with different depth. Figure. 3 only gives results of ResNet-18 while the setting is not the best setting. Normally we need to train at least 120 epochs. It also does not give the experiment on ImageNet. Thus making the conclusion less meaningful\n\n2) The author should also compare the continuous sparsification with one-shot pruning methods (non-iterative) to see the advantage of continuous sprsification.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "S1xheijnFr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a novel objective function that can be used to jointly optimize a classification objective while at the same time encourage sparsification in a network. The lottery ticket hypothesis and associated work shows that the iterative pruning of a network can lead to a sparse network that performs with high accuracy. On the other hand, the work of Zhou et al. shows that sparse masks (dubbed \"supermasks\") may be learned without training the parameters of the network. In a sense, this paper tries to combine these ideas by simultaneously training a network while also optimizing the mask.\n\nI think this paper serves as a reasonable contribution to the ever-growing \"lottery ticket hypothesis\" body of work. The paper is mostly clear, and the idea for joint optimization is very reasonable. It's not tremendously original (in that it basically combines two ideas that are already in the literature), but in spite of that, I still think this paper warrants being accepted to ICLR.\n\nFor me, the most interesting scientific point is about the issue of rewinding. In particular, the fact that continuous sparsification can find winning tickets without any parameter rewinding is fascinating and deserves further investigation. Do the authors have any sense for why this works, when prior work suggests that rewinding is necessary for sufficiently complicated models and datasets?\n\nA minor point, I think there's a typo on page 6 in that the paragraph beginning \"Results are presented in Figure 2\" both instances of \"SP\" should be \"SS\" instead.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Bklcxb3i5r", "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": "\nTo the authors of paper 2504: I have posted a private comment for the reviewer/AC discussion period based on your author responses and your revised paper. I want you to be able to see my full response, but I can't post additional public comments to the paper. As such, I'm editing my review with exactly what I sent to the AC.\n\nThank you to the authors for your thoughtful rebuttal and for updating the paper with both new text and (more impressively) new experiments. I read all three of your rebuttals and re-read the revised paper in detail. My comment to the AC is at the bottom of this message. I don't know if you will get an alert that the review was updated, but I hope you get a chance to take a look.\n\n===========================================\n\nEXECUTIVE SUMMARY OF REVIEW\n\nSummary of paper: This paper proposes a technique that simultaneously trains a neural network and learns a pruning mask. The goal of this technique is to make it faster to retroactively find sparse subnetworks that, from a point early in training, could have trained in isolation to the same performance as the full network (\"winning tickets\"). The best subnetworks found by this technique outperform those found by existing techniques [1] at every sparsity level.\n\nSummary of review: The technique introduces several new hyperparameters whose values are asserted without describing the extent of the search necessary to find them; it unclear whether the cost of the search cancels out the efficiency gains. In addition, the proposed technique is inconsistent across runs. The sparsity and accuracy of the subnetworks it produces vary greatly, and there are no hyperparameters to explicitly control these outcomes. It is also unclear whether results vary from run to run even with the same hyperparameters.  As such, this technique is not clearly a cost reduction as compared to existing approaches in [1] when it comes to studying lottery tickets. Moreover, the paper implicitly proposes a new pruning technique, and it should be evaluated against other related techniques in the pruning literature. Finally, the evaluation needs more rigor.\n\nConclusion: It is difficult to determine whether the technique is an improvement over existing methods since the true costs of using it in practical workflows are unclear. Weak reject.\n\nOpportunity to improve score: Include a more detailed analysis of the overall costs of finding winning tickets at a target sparsity using the proposed technique, particularly including the costs of hyperparameter search necessary to do so. Include multiple replicates of experiments, experiments on more networks, and information about the variance of performance across runs with the same hyperparameters. Compare against other state-of-the-art pruning techniques.\n\nPROBLEM STATEMENT AND PROPOSED SOLUTION\n\nProblem: Winning tickets are currently expensive to find. The best known procedure [1, 2] is \"iterative magnitude pruning\" (IMP), which involves repeatedly training a network to completion, pruning by a fixed percentage, and \"rewinding\" weights to an early iteration of training until the network reaches the desired level of sparsity. To reach sufficient sparsity on standard networks, this procedure must be repeated 10 or more times.\n\nGoal: To propose a procedure that finds winning tickets more efficiently.\n\nSignificance: A more efficient procedure would make it easier to study the lottery ticket phenomenon. (Whether studying that phenomenon is, itself, significant is debatable.) Personally, I have extensive experience using IMP to find winning tickets, so techniques to reduce the cost of finding winning tickets would be very valuable for my work.\n\nProposed solution: The authors propose \"continuous sparsification\" (CS), which makes it possible to learn which weights to prune simultaneously with the weights themselves. Accompanying each parameter w in the network is a second parameter s. The actual weight used in the network is w * sigmoid(s * beta), where beta is a temperature hyperparameter. If the learned value of s is such that sigmoid(s * beta) is approximately 0 at the end of training, then the parameter has been pruned. The value of beta increases exponentially throughout training, meaning the output of the sigmoid will be closer to a hard 0 or 1, producing a pruning mask. To ensure sparsification happens, a regularization term lambda |sigmoid(beta * s)| is added. When run over multiple iterations, values of s are reset to their original values for weights that are not pruned. In addition, weights are either rewound (as in IMP) or left at their final values (as in [3]).\n\nNovelty: The paper is slightly novel. The technique is a variation of those proposed in [4] and [5], but the changes are meaningful. This is the first known use for finding winning tickets, but any pruning technique could hypothetically be used for this purpose. In effect, the paper proposes a new pruning technique that is primarily evaluated for its efficacy in finding winning tickets.\n\nTECHNICAL REVIEW\n\n* This technique introduces several new hyperparameters: lambda, initial and final betas, and the initial values for s. The paper suggests good values for these hyperparameters for both networks considered. These values were presumably found through hyperparameter search of some kind. How extensive was this hyperparameter search, and what is the range of \"good\" combinations of values? This is not just a methodological footnote; this paper's stated goal is to improve the efficiency of finding winning lottery tickets, and - if good hyperparameters are hard to find - then that defeats the purpose of a more efficient technique. IMP, while far less efficient epoch for epoch as compared to CS, requires no hyperparameter search; global pruning 20% of parameters per iteration seems to work well in general [2]. In a revised version of the paper, I would be eager to learn more about this set of tradeoffs, since that is what matters in practice.\n\n* The authors only study two networks: a toy convolutional network and a small Resnet. It is hard to draw broad conclusions from such a limited set of examples. I would be particularly interested in seeing how this technique performs on a large-scale network for ImageNet (e.g., Resnet-50), since these are the situations where IMP becomes particularly cost-prohibitive. If the technique works well in these settings, it would enable lottery ticket research at much larger scales than is currently possible. If the technique works as efficiently at this scale, then doing could even be feasible during the rebuttal period. (I acknowledge getting experiments working on ImageNet is no small undertaking in terms of both engineering time and cost, but it would improve my confidence to see those results.)\n\n* The authors did an admirably careful job replicating the networks in [1], which include a variety of nonstandard hyperparameters.\n\n* Did the paper study Resnet-18 (a network designed for ImageNet with 11.2M parameters) or Resnet-20 (a network designed for CIFAR-10 with 272K parameters)? Frankle et al. [1, 2] describe Resnet-20 in their appendices but mistakenly refer to it as Resnet-18 throughout both papers, so I wanted to clarify. Based on the final test accuracy of the network, it appears to be Resnet-20; if so, I'd urge you to call it as such and note in a parenthetical or footnote that it's the same network as in [1, 2] but with Frankle et al's mistaken name corrected.\n\n* Are the values of s0 for CS sampled from a distribution, or are they all the same, fixed value?\n\n* Do the extra parameters lead to longer wall-clock training times? If you are making an argument about a more efficient technique, this is an important consideration.\n\n* Figure 2 includes the same graph twice. I believe a different graph should appear on the left, and I am eager to take a look at it in a revised version of the paper.\n\n* It does not appear that multiple replicates of each experiment were run with different network initializations in Figure 3. There don't appear to be any error bars on Figure 3, suggesting that this only represents a single initialization. Considering the wide variance in performance achieved by continuous sparsification across runs in Figure 3 (right), this graph needs to include multiple runs and error bars. (I assume the multiple runs shown in Figure 3 (right) are with different hyperparameters?)\n\n* What is the performance of CS as a pruning technique? By finding winning tickets, CS is also implicitly pruning the network. Is this competitive with L0 Regularization [4]? Is it more efficient than iterative magnitude pruning as in [3]? If this is a more efficient technique for finding winning tickets, it is also liable to be a more efficient pruning method, which seems like even broader impact for the proposed technique. Alternatively, if this technique is less effective than comparable work (especially [4]) as a pruning method, then it is possible comparable work (especially [4]) might also produce better winning tickets, in which case the importance of this work is diminished. In an updated version of the paper, I would be interested in seeing an evaluation of CS as a pruning technique independent of the lottery ticket hypothesis (and compared to standard techniques in the pruning literature as such). I have a hard time seeing any reason why new techniques for finding lottery tickets are any different than new pruning techniques, and they should be evaluated as such in the context of the broader literature on pruning.\n\n* The last paragraph of Section 4.1 is missing important details that are necessary to evaluate the utility of continuous sparsification in comparison to IMP. \"In only two iterations, CS finds a ticket with over 77% sparsity...\" - for which hyperparameters, and how many hyperparameters had to be explored to find these values? How was the pareto curve obtained? How many different runs were necessary to create it? How many total epochs of training did it take to find that curve? If obtaining this pareto curve required many runs of CS, then it may not be any more efficient than running IMP in practice. The pareto curves appear to make CS look misleadingly effective, since they hide many of the actual costs involved (e.g., hyperparameter search, number of separate runs that were conducted to produce the curve, etc.). Greater transparency of this aspect of the paper would go a long way toward increasing my confidence that the findings are an improvement over IMP. \n\n* The sparsity and accuracy of subnetworks found by CS appears to vary widely from run to run as shown in Figure 3 (right). The final sparsity appears to be a function of the values of s0, lambda, and beta, potentially along with luck from the optimization process. For the same values of s, lambda, and beta, how widely do the final sparsities and accuracies vary? If I wanted to find a winning ticket with a particular sparsity using CS, what would the procedure look like for doing so? Would I have to sweep across values of these hyperparameters, or is there a more straightforward way to do so? The practical usefulness of the procedure hinges on these questions.\n\n* \"We associate the performance drop of highly sparse tickets found by our method from the second iteration onwards to the lack of weight rewinding.\" Why didn't you also try it with weight rewinding? That seems like an easy way to evaluate this hypothesis. For both networks, it would be interesting to see the performance of CS with and without rewinding (analogous to Appendix B in [1]).\n\n* In the literature so far, the only winning tickets to be examined are those from IMP [1, 2]. CS is a different technique, and it likely finds different winning tickets. Do these winning tickets have different properties from [1, 2]? Can they be reinitialized? Can they be rewound earlier? These comparisons seem like an interesting scientific opportunity.\n\n* There are a few additional comparisons that I think are vital to include in the paper to appropriately contextualize results.  They're in the bullets below.\n\n* First comparison: it would be useful to include random reinitialization or random pruning baselines as in [1, 2] simply to make it easier for the reader to contextualize the performance of other sparse subnetworks.\n\n* Second comparison: what happens if you run IMP such that each iteration prunes to the same sparsity as achieved by each iteration of CS? Perhaps pruning by a fixed amount per iteration in IMP is wasteful, and one can prune more aggressively during earlier iterations as CS naturally appears to do. In other words, one way of explaining the advantage of CS would be that it prunes more aggressively. Is this indeed the case? I would be very curious to know.\n\n* Third comparison: What are the range of results achieved if IMP and CS are run \"one-shot\" (pruning after just one iteration; in the case of IMP, pruning directly to a desired sparsity)? That is, how well can these techniques do with just a single iteration?\n\nWRITING\n\nThe writing is excellent. The prose is clear, and I was able to fully understand a relatively sophisticated technique on the first read through the paper. Writing of this quality is rare, and the authors should be commended for it.\n\nOVERALL: Weak Reject\n\nThe problem statement is that IMP is not efficient. The paper claims that CS is more efficient. However, the paper does not present a convincing case that CS is, on the whole, more efficient when taking into account hyperparameter search to get CS to work, hyperparameter search to target a particular sparsity, potential variance across runs of CS, potential additional training costs of CS, and the possibility that IMP might be able to work comparable well given a more aggressive pruning schedule.\n\nIn addition, the evaluation needs more experiments, including multiple replicates for each experiment and more networks (ideally one on ImageNet).\n\nFinally, I am unclear on what distinguishes CS from any other pruning technique, and it should be evaluated in the context of the broader pruning literature.\n\nIf the authors clarify that the overall cost of CS (including all of the factors listed above) is lower than for IMP, address technical concerns about the evaluation, and evaluate CS as a pruning technique in an updated version of the paper, I will update my score accordingly.\n\n[1] Frankle & Carbin. \"The Lottery Ticket Hypothesis.\" ICLR 2019.\n[2] Frankle et al. \"Stabilizing the Lottery Ticket Hypothesis.\" Arxiv.\n[3] Han et al. \"Learning both Weights and Connections for Efficient Neural Networks.\" NeurIPS 2015.\n[4] Louizos et al. \"Learning Sparse Neural Networks through L0 Regularization.\" ICLR 2018\n[5] Zhou et al. \"Deconstructing Lottery Tickets: Signs, Zeros, and the SuperMask.\" NeurIPS 2019.\n\n=====================================\n\nCOMMENT TO THE AC AFTER READING REBUTTALS AND REVISED PAPER\n\nTLDR\n\nI believe the technique is novel and should be published, regardless of whether it is actually more efficient than IMP for practical workflows.\n\nHowever, I believe the current evaluation is inadequate, both in the experiments and in the way data is presented. Namely, it is impossible to actually compare the costs of CS and IMP in the scenarios the authors evaluate, despite the fact that efficiency is the authors' claimed contribution. From the data as presented, it is unclear whether CS is actually more efficient than IMP for scientific use-cases. I'm not particularly concerned if there isn't an efficiency advantage - it's an innovative contribution regardless. My concern is that it is impossible to compare the costs of these techniques given the current presentation of data. That speaks to flaws in the evaluation section.\n\nI therefore maintain my score: weak reject. The technique deserves to be published, but the paper in its current form does not.\n\nINTRODUCTION\n\nAfter reading the original submission, I had the following questions:\n\n1) Right now, the only way to find winning lottery tickets is through training the network and pruning it. IMP can be instantiated with any pruning technique, and the authors are really proposing a new pruning technique for use in the IMP framework. How does continuous sparsification perform as a pruning technique for network compression (i.e., independent of the lottery ticket hypothesis)?\n\n2) How efficient is continuous sparsification (CS) in the scientific use cases where one would seek to find winning lottery tickets? In my research experience, there are two such use cases: (a) producing a winning lottery ticket with a specific sparsity and (b) producing winning lottery tickets across the full range of different sparsities.\n\nIn their reubttal, the authors addressed these underlying questions:\n\nAS A PRUNING TECHNIQUE\n\n\"We have added new experiments showing that our method yields competitive results when pruning VGG trained on CIFAR, outperforming both magnitude pruning and stochastic l0 regularization\"\n\nMy response: The initial results that the authors present are quite impressive on a VGG-style network for CIFAR-10. However, I find it concerning that the authors study pruning on this specific model but no others, particularly because they focus on a different network (namely, Resnet-20) in all other experiments in the paper. Since the authors are, in essence, proposing a new pruning technique, I would like to see it comprehensively evaluated as such on a range of networks against other baselines (as the authors do in Figure 4 for one network - those baselines are fine to me).\n\nEFFICIENCY OF CONTINUOUS SPARSIFICATION\n\n- It increases the cost of each individual network training run slightly: \"Continuous Sparsification on a 1080 Ti: our method resulted in 15% extra wall-clock time per training epoch.\"\n\n- PRODUCING WINNING TICKETS ACROSS THE FULL RANGE OF SPARSITIES: Throughout the paper, the authors present \"pareto curves\" showing the highest accuracy achieved by CS subnetworks at various sparsities. I find these pareto curves misleading: they hide the fact that CS had to be run several times with different hyperparameters to produce these curves.\n\nFor example, in Figure 6 (right), the authors produce the pareto curves by training Resnet-20 (by my count) 22 times (each point along the purple lines). The corresponding IMP curve appears to have 14 points. In other words, to get winning lottery tickets across all sparsities, CS must be run for more iterations than IMP - it appears to be less efficient, contradicting the authors' core claim. The best argument in favor of CS is that one could perform each of these runs in parallel if sufficient GPUs were available, meaning less wall-clock time would be required.\n\nOne caveat to this analysis: the authors state that they run CS \"without rewinding,\" meaning that the second iteration of CS requires less training time than fully training the network (as IMP requires). The authors do not state how long they train when they *aren't* rewinding, so it is impossible to compare the efficiency of CS with IMP. All they say is that it \"allow[s] for even faster ticket search.\" They also do not study IMP without rewinding, which would be a helpful baseline for comparing to CS without rewinding.\n\n***In short, if the authors are making an argument that one technique is more efficient than the other on an epoch-for-epoch basis, they need to actually plot the epochs required by each technique.***\n\n- PRODUCING A WINNING TICKET AT A SPECIFIC SPARSITY: My concern about this use case is that there is a non-intuitive relationship between the initialization of the sparsity parameters and the final sparsity of the network. As the authors state in the rebuttal: \"To achieve a desired sparsity, one can either perform runs in parallel with different values for s_0, or perform sequential binary search if the goal is to minimize the overall computational cost and not wall-clock time.\" In other words, there is no precise way to target a particular sparsity other than trying many hyperparameter configurations. The authors do not provide any concrete costs of using CS in this way in comparison to IMP, and - from a usability perspective - this is a challenging workflow.\n\nOTHER CONCERNS\n\n- The authors only study CS on one toy network (the six-layer convolutional network, which - in my experience - is a particularly easy setting compared to deeper networks) and one \"real\" network (Resnet-20 on CIFAR-10). I would like to see results on other networks for CIFAR-10 (for example, the VGG network in Section 4.3).\n\n- More importantly, I would like to see results on an ImageNet network. If CS makes finding winning lottery tickets more efficient as the authors claim, then finding winning tickets efficiently on an ImageNet network should be an excellent demonstration of their contribution. This scenario has stretched IMP to its breaking point, as the authors note.\n\nARGUMENTS IN FAVOR OF ACCEPTING\n\n+ The authors propose a new pruning technique that appears to improve upon the increasingly popular L0-regularization technique.\n\n+ With the right hyperparameters, the proposed technique makes it possible to find winning lottery tickets more efficiently than existing methods (i.e., IMP with magnitude pruning).\n\n+ The winning tickets found by the proposed technique reach higher accuracy than IMP winning tickets and produce winning tickets at more extreme sparsities, improving upon our knowledge of the existence of winning lottery tickets.\n\nARGUMENTS IN FAVOR OF REJECTING\n\n- The authors perform only minimal evaluation of their method as a pruning technique. It is possible that this is a missed opportunity to show an additional contribution. It is also possible that other, existing pruning techniques outperform CS at both pruning and finding winning lottery tickets.\n\n- The technique is hard to use for the two existing use cases for finding winning tickets. In particular, there is no way to search for winning tickets at a specific sparsity.\n\n- It is unclear whether CS is actually more efficient than IMP on an epoch-for-epoch basis, even though this is the main claimed contribution. The authors do not disclose - let alone plot - the number of training epochs required to find (a) winning tickets at a specific sparsity and (b) winning tickets at a range of sparsities, so it is impossible to make these comparisons. Meanwhile, the pareto curves the authors present are misleading, since they are the amalgamation of many separate runs of CS.\n\n- The authors study their technique on only one \"real\" network (Resnet-20) for finding winning tickets and a separate \"real\" network (VGG-19) for pruning. The authors do not show how CS performs in other challenging settings, especially ImageNet.\n\n- This work is only valuable if we believe that \"lottery ticket hypothesis\" work is valuable. In other words, this is a narrow contribution to an already-narrow area of study. This is one reason why pitching CS as a pruning technique would make this a stronger paper. I personally believe that \"lottery ticket\" work is valuable area of study, but I understand that it may not be seen as such in the broader ICLR community.\n\nCONCLUSION\n\nI believe the technique deserves to be published regardless of whether it is actually more efficient than IMP. It is a novel contribution to both our knowledge of pruning and of finding winning lottery tickets. The paper is exceptionally well written, and - as such - I believe it will help to inspire other research in this area.\n\nHowever, I do not believe that the current paper - namely, the current evaluation - should be published. The paper presents no concrete data on the comparative costs of performing CS and IMP even though the core claim is that CS is more efficient. The paper does not disclose enough detail to compute these costs, and it seems like CS is more expensive than IMP for standard workflows. Moreover, the current presentation of the data through \"pareto curves\" is misleadingly favorable to CS.\n\nI also believe that the paper needs experiments on ImageNet and needs a more thorough evaluation as a pruning technique beyond the lottery ticket hypothesis.\n\nI therefore retain my current score of \"weak reject,\" though I am eager to hear the thoughts of other reviewers, and I am open to changing my score.\n", "extra_scores": {"experience_assessment": "I have published one or two 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": {}}]

Author rebuttal:

Meta-review: This paper proposes a new algorithm called Continuous Sparsification (CS) to search for winning tickets (in the context of the Lottery Ticket Hypothesis from Frankle & Carbin (2019)), as an alternative to the Iterative Magnitude Pruning (IMP) algorithm proposed therein. CS continuously removes parameters from a network during training, and learns the sub-network's structure with gradient-based methods instead of relying on pruning strategies. The papers shows empirically that CS finds lottery tickets that outperforms the ones learned by ITS with up to 5 times faster search, when measured in number of training epochs.

While this paper presents a novel contribution of pruning and of finding winning lottery tickets and is very well written, there are some concerns raised by the reviewers regarding the current evaluation. The paper presents no concrete data on the comparative costs of performing CS and IMP even though the core claim is that CS is more efficient. The paper does not disclose enough detail to compute these costs, and it seems like CS is more expensive than IMP for standard workflows. Moreover, the current presentation of the data through "pareto curves" is misleadingly favorable to CS. The reviewers suggest including more experiments on ImageNet and  a more thorough evaluation as a pruning technique beyond the lottery ticket hypothesis. We recommend the authors to address the detailed reviewers' comments in an eventual ressubmission.

Decision: Reject