The Sooner The Better: Investigating Structure of Early Winning Lottery Tickets
Authors: Shihui Yin
Kyu-Hyoun Kim
Jinwook Oh
Naigang Wang
Mauricio Serrano
Jae-Sun Seo
Jungwook Choi
Venue:  (2020)
Keywords: pruning
lottery ticket hypothesis
deep neural network
compression
image classification

Abstract: The recent success of the lottery ticket hypothesis by Frankle & Carbin (2018) suggests that small, sparsified neural networks can be trained as long as the network is initialized properly. Several follow-up discussions on the initialization of the sparsified model have discovered interesting characteristics such as the necessity of rewinding (Frankle et al. (2019)), importance of sign of the initial weights (Zhou et al. (2019)), and the transferability of the winning lottery tickets (S. Morcos et al. (2019)). In contrast, another essential aspect of the winning ticket, the structure of the sparsified model, has been little discussed. To find the lottery ticket, unfortunately, all the prior work still relies on computationally expensive iterative pruning. 

In this work, we conduct an in-depth investigation of the structure of winning lottery tickets. Interestingly, we discover that there exist many lottery tickets that can achieve equally good accuracy much before the regular training schedule even finishes. We provide insights into the structure of these early winning tickets with supporting evidence. 1) Under stochastic gradient descent optimization, lottery ticket emerges when weight magnitude of a model saturates; 2) Pruning before the saturation of a model causes the loss of capability in learning complex patterns, resulting in the accuracy degradation. We employ the memorization capacity analysis to quantitatively confirm it, and further explain why gradual pruning can achieve better accuracy over the one-shot pruning. Based on these insights, we discover the early winning tickets for various ResNet architectures on both CIFAR10 and ImageNet, achieving state-of-the-art accuracy at a high pruning rate without expensive iterative pruning. In the case of ResNet50 on ImageNet, this comes to the winning ticket of 75:02% Top-1 accuracy at 80% pruning rate in only 22% of the total epochs for iterative pruning.

THE SOONER THE BETTER: INVESTIGATING STRUCTURE OF EARLY WINNING LOTTERY TICKETS
Anonymous authors Paper under double-blind review
ABSTRACT
The recent success of the lottery ticket hypothesis by Frankle & Carbin (2018) suggests that small, sparsified neural networks can be trained as long the network is initialized properly. Several follow- up discussions on the initialization of the sparsified model have discovered interesting characteristies such the necessity of rewinding (Frankle et al. (2019)) importance of sign of the initial weights (Zhou et al. (2019)) and the transferability of the winning lottery tickets (S. Morcos et al. (201)). In contrast, another essential aspect of the winning ticket, structure of the sparsified model, has been little discussed. To find the lottery ticket, unfortunately, all the prior work still relies on computationally expensive iterative pruning.
In this work, we conduct an in-depth investigation of the structure of winning lottery tickets. Interest- ingly, we discover that there exist many lottery tickets that can achieve equally good accuracy much before the regular training schedule even finishes. We provide insights into the structure of these early winning tickets with supporting evidence. 1) Under stochastic gradient descent optimization, lottery ticket emerges when weight magnitude of a model saturates; 2) Pruning before the saturation of a model causes the loss of capability in learning complex patterns, resulting in the accuracy degradation. We employ the memorization capacity analysis to quantitatively confirm it, and further explain why gradual pruning can achieve better accuracy over the one-shot pruning. Based on these insights, we discover the early winning tickets for various ResNet architectures on both CIFARIO and ImageNet, achieving state-of-the-ee accuracy at a high pruning rate without expensive iterative pruning. In the case of ResNet50 ImageNet, this comes to the winning ticket of 75.31% Top-1 accuracy at 80% pruning rate in only 22% of the total epochs for iterative pruning.
I
INTRODUCTION
Deep Neural Networks (DNNs) achieve superior accuracy in a wide spectrum of applications through the use of very large and deep models (Goodfellow et al. (2016)). These high-capacity but complex models, however, pose a tremendous challenge for their deployment, particularly in resource-constraingg many techniques have been developed to compress the models to compact counterpart to alleviate the computational costs. Among these techniques, pruning less important parameters to obtain a compact sub-network has emerged to be popular and efficient approach (Cun et al. (1990); Han et al. (2015)). search of these sub-networks, new intuitions are also built up for understanding the DNN working mechanism, one example of which is the recently proposed "lottery ticket hypothesis" " by Frankle Carbin (2018).
edge environments. Over the years,
The lottery ticket hypothesis states that, once sub-network is found to match the accuracy of the original neural network, the sub-network (i.c., lottery ticket) together with its initialized weights can be trained in isolation and still achieve accuracy comparable to the original network within a similar number of iterations. This conjecture intrigues discussions on a series of topics, such as the importance of initialization scheme (Liu et al. (2018), /hou et al. (2019). the role of over- parameterization in training (Frankle et al. (2019) and even the transferability of the "winning ticket" (S. Morcos et al. (2019)) However, all these discussions start from the point that the winning ticket has been obtained after painfully long iterative pruning procedures, which often take up to thousands of epochs. When and how winning ticket can be found in the course of pruning procedures has not been studied; most of the prior works use traditional way of repeated cycles of pruning and retraining, which makes such study less practical.
In this work, we provide insights to find the winning tickets early. We start with an interesting observation that there exist many lottery tickets that can achieve equally good accuracy much before the regular training schedule finishes.

---

This leads to our in-depth investigation of the weight magnitude; we discover that a model saturates early but not too early under stochastic gradient descent (SGD) optimization. To understand this characteristic of the winning lottery tickets, we conjecture that pruning a premature model causes the loss of capability in learning complex patterns, leading to accuracy degradation. We confirm this conjecture with the empirical evidence as well as the quantitative analysis based the memorization capacity. Using this analysis framework, we further provide reasoning behind the success of the gradual pruning over the one-shot pruning. Based on these insights, we identify the early winning tickets for various ResNet architectures on both CIFARIO and ImageNet, achieving state-of-the of-the-art accuracy at high pruning rate without expensive iterative pruning. In the case of ResNet50 on ImageNet, this comes to the winning ticket of 75.31% % Top-1 accuracy 80% pruning rate obtained within only 22% of the total epochs for iterative pruning. This promising outcome not only sheds light on understanding the optimization behavior of the pruned models but also enables performance gain for fast training of the pruned models.
2 RELATED WORK
The lottery ticket hypothesis was first proposed in Frankle & Carbin (2018) where the presence of a trainable sub- network that achieves compelling final accuracy with the inherited initial values for the un un-pruned connections is demonstrated. This paper also argued that the initial weight of the original network is essential for maintaining good accuracy when the model is sparsified. This claim has been extended to the per-pparaettriieed neural networks on the larger datasets in Frankle et al. (2019) with the notion of "rewinding"; the authors claim that rewinding of the weights not to the initial values but to the values after a few epochs can stabilize the accuracy of the winning lottery tickets. As follow-up work, Zhou et al. (0119) studied the critical components of the lottery tickets such as zeros, signs and the super-mask. Also. Morcos et al. (2019) investigated the transferability of winning tickets obtained in one dataset to the network of a similar structure for the other datasets. But none of these focused on the structure of the winning lottery tickets; it involves several repetitions of the full training schedule for iterative pruning and retraining, often taking hundreds to thousands of epochs. In this work, we demonstrate that many winning tickets can be found in the early stage of the baseline training schedule, drastically reducing the computational effort to obtain them.
Most work on the lottery ticket hypothesis, including this work, rely on magnitude- based weight pruning for identifying unimportant weights to be pruned (usually via global sorting). Such an intuitive method was first proposed in Han al. (2135) and became popular. Afterwards, more complex pruning methodologies have been presented to improve pruning performance, such as having different pruning criteria (Li et al. (2017). Wen et al. (2016), Liu et al. (2017)) or different pruning granularity (Mao et al. (2017). Molchanov et al. (2019). ). While these attempts offer insights on training pruned models, there is little discussion about the interesting interplay between the pruning criteria and the structure of model pruned by it. In this work, we reveal that the pruned structure obtained based on the weight magnitude has tangible impact on the final accuracy, and further propose a way to quantitatively distinguish good structures for pruning.
There have been various strategies to apply pruning to the neural networks. Iterative pruning by Han et al. (2015) involves several repetition of pruning (with gradual increase of the pruning rate) and retraining. One can increase the repetition cycles arbitrarily large to achieve good accuracy at high pruning rate; Frankle & Carbin (2018) employed iterative pruning with hundreds to thousands of pruning epochs to match the baseline accuracy for the challenging neural networks. On the other hand, gradual pruning introduced by Zhu & Gupta (201)) determines the pruning rate and frequency via polynomial equation as a function of the starting and ending epochs as well as the target pruning rate. Although it provides systematic pruning schedule, there is lack of discussion about when to start the gradual pruning. Lastly, [ee et al.] (2018) proposes a method of pruning weights at initialization. This method takes most advantage in performance since pruned model can be obtained without any expensive retraining procedures. However, its effectiveness has not been demonstrated for the challenging neural networks on large datasets such as ImageNet. In contrast, we propose a mechanism to identify the winning lottery ticket early in the course of baseline training so that we can avoid costly iterative pruning while maintaining the baseline accuracy.
3 STRUCTURE OF EARLY WINNING TICKETS
In this section, we extend the lottery ticket hypothesis by Frankle & Carbin (2018); Frankle et al. 2019) to discuss the early winning tickets. The lottery ticket hypothesis can be summarized as:
2

---

vis
20
40
60
100
120
140
160
180
200
Baseline
80.26
83.74
82.72
85.30
84.31
84.95
87.55
92.08
91.63
92.11
92.05
0
89.81
90.15
89.97
90.50
89.89
90.08
89.94
89.72
90.10
89.67
89.37
5
89.83
90.30
90.91
91.08
91.28
91.65
91.52
91.50
91.48
91.42
91.13
10
90.21
90.31
90.74
91.12
91.37
91.55
91.43
91.43
91.48
91.45
91.32
20
90.32
90.27
91.05
91.13
91.39
91.47
91.25
91.43
91.33
91.25
91.45
40
90.43
90.46
90.63
90.97
91.58
91.67
91.36
91.56
91.54
91.43
91.59
60
90.03
90.19
90.82
90.96
91.45
91.56
91.30
91.64
91.67
91.38
91.45
80
90.05
90.28
90.67
91.18
91.21
91.42
91.34
91.62
91.54
91.23
91.45
100
90.55
90.26
90.74
91.39
91.36
91.54
91.43
91.50
91.34
91.39
91.54
120
90.17
90.55
90.94
91.31
91.35
91.49
91.62
91.55
91.32
91.38
91.41
140
90.16
90.50
90.88
91.11
91.46
91.77
91.14
91.65
91.41
91.48
91.25
160
90.16
90.29
90.82
91.30
91.34
91.67
91.41
91.56
91.36
91.40
91.44
180
90.73
90.33
90.80
91.28
91.56
91.60
91.58
91.66
91.31
91.49
91.38
200
90.33
90.64
90.86
90.94
91.47
91.68
91.37
91.55
91.55
91.15
91.32
Figure I: Extended lottery ticket experiments using ResNet20 on CIFAR10. From the baseline ResNet20 training. weight- magnitude based pruning is applied at different epoch (columns, labeled as s) to obtain the sparsified structure. Each structure is then rewound to the weights from another epoch (rows, labeled as v), where v=0 indicates rewind to the initial weight. Lottery tickets emerge much earlier before the full training ends, achieving matching accuracy compared the conventional winning ticket, i.e., (==200,==200)
for given network of {x; Wp O mp) with the initial weight wo and the mask of all ones me, there exists winning lottery ticket m where |myl/ |/ol 1 p% (p is the pruning rate) and training of f(z; wa C my) for 0 < < achieves test accuracy comparable to the baseline f(x; wy mo)-
There are two main components of winning lottery ticket: the sparsified structure my and the weight that initializes it, wi. In the previous work, my has been obtained only after expensive iterative pruning. We characterize the structure of the early lottery ticket m, where < S, then propose a strategy for finding it early.
3.1 EXTENDED LOTTERY TICKET EXPLORATION
Frankle et al. 2019 suggests that a lottery ticket found after baseline training can achieve the accuracy of the bascline model if it is initialized with the weight of the baseline model after a few epochs, which is called rewinding. We extend this exploration toward different structures obtained at different epochs of the baseline training (via magnitude-base weight pruning).
Fig. shows the validation accuracy after retraining of ResNet20 model on CIFARIO pruned at different epochs of its baseline training. The same learning rate schedule of 0.1 reduced by 10x at epoch 120 and 160 is used for both the baseline training and retraining, and the total number of epochs is 200. The rows (= v) correspond to the different rewinding epoch, whereas the columns rate= 80%). For example, the validation accuracy along the lottery ticket configurations of (s = 200, v = =0- 200) resembles the phenomena of "rewinding" observed in Frankle al. 2019).
correspond the different epoch that apply one-shot pruning (pruning
Interestingly, Fig. T further demonstrates that the winning tickets emerge at much earlier epochs of the baseline training; the lottery ticket configurations of (s 2 100, v 5) achieve almost the same accuracy the accuracy of (s 200, = 200). The accuracy then gradually decreases as < 80. This result implies two important aspects: 1) winning ticket can be found in the middle of the baseline training so that one can avoid expensive iterative pruning used in the prior work, and 2) the winning ticket, however, does not emerge arbitrarily early in the process of training. In the following sections, we investigate the characteristics of these early winning tickets. In particular, we focus on their structure, as the weight initialization is not the major factor provided proper rewinding.
3.2 ANALYSIS ON WEIGHT MAGNITUDE
As the first step of understanding the characteristics of the carly winning tickets, we focus on the important quantity of pruning, weight magnitude. At pruning, we determine the structure of the sparsified model based the rank of the
3

---

0.225
1.0
0.200
Layer
0.9
Lawe
Per-Layer Pruning Rate
Layer
0.175
Layer
Weight Std
0.8
Layer 8
Layer
0.125
0.7
Lawer
0.100
0.6
Lawer
Lawer
0.075
Layer
Layar
0.5
Laver 18
0.050
Laver
50
100
150
200
150
Epochs
Epochs
(a) Pey-Layer Weight Stdev.
(b) Per-Layer Pruning Rate
Figure 2: (a) Change of standard deviation weights (Wata) in layer during the training ResNet20 on CIFARIO. the beginning of the training, the weights of different layers change in different rate, dominated by the gradient terms. When the training evolves, weight magnitude is primarily determined by the interplay between learning rate and weight decay, resulting in parallel movement of Wstd. (b) Change of per-layer pruning rate over the epochs. Due to regular shift of W std the later epochs of training, the per-layer pruning converges saturating point, emerging stable structure for pruning.
weight magnitude (via global sorting). Therefore, the change in the weight magnitude during training has large impact the lottery ticket structure.
In Fig. 2h, we measure the standard deviation of weight (W sta) for each layer in the course of training ResNet20 on CIFARIO (note: the mean of weight typically near zero). The same learning rate schedule is used as above. The first thing to note is that the change in Wata has strong correlation with the learning rate change. In particular, different layers show different rate of change W sta when the learning rate is 0.1, from the second learning rate (after epoch 120), all the weights follow very similar decreasing trend.
This trend in std can be understood via steps of stochastic gradient descent. From the typical setting of weight update with momentum and weight decay, we have:
U++1 me; + (Awx + Wg,t), W++1 w² 7/++1-
(1)
where wt, Wg.t and i2 are the weight, gradient and momentum step f, respectively; m is the momentum factor, 7) is the learning rate and X is the weight decay factor. After n steps,
Uttn u
(m" n F
Wg b.g..tk-11
(m" wo+k-1).
(2)
T1
Wr+n = (1 1--)
Σ
(mo))== + wg.t+k-1))
k=1
From this derivation, we can see that the two factors determine the mode of change in Wed.. When learning rate is high, the gradient terms play the major role in weight update. On the other hand, if the gradient activity becomes low, e.g., when the learning rate is low and the gradients oscillate around zero, we can further simplify Eq, 3 Assume that m²'; approaches to zero when n is relatively large, W++k-1 the gradients oscillate around zero, we have Ve-r 1-m
and Ex=((1 ((1
wg.t+kk1) and
Ex_ (m=-= "0,,- approach approximated as
Aws Then Wh+n is
((1 7722² mmw
Witn R (1 n
Wi
(4)
1=
Note that (1 - n/A"" xe nnd since yr &< and
1=0 ((1 m)))*) xe n. Thus,
nndmww
Wite R wrjd)wt
Wr--
(5)
1 m
m
4

---

(PPR) model at each baseline epoch, we measure In other words, when the gradient activity is low, the change in Watd is dominated by the both the learning rate and the weight decay. As an example, in Fig. p. Watd is decreased with the slope following Eq. when learning rate is low; Watd of layer 10 is decreased by 1.5e-3 in 782 updates of CIFARIO (with À = =le- and m 0.9), confirming the slope from Eq. [5]
These two modes governing the change of weight magnitude are critical for understanding the behavior of pruning. In particular, the interplay between learning rate and weight decay causes the per-layer pruning rate to converge after enough number of epochs. Fig. 2 shows the pseudo per-layer pruning rate, where we just measure the layer-wise pruning rate without really pruning out the weights in the model, for the same CIFARIO training experiment. As the figure shows, the per-layer pruning rates saturate around epoch 100, indicating that pruning before that would select the weights based on the premature model.
Moreover, although the weight magnitude is important factor, we discovered that the ranking of individual weight does not play critical role in winning lottery tickets. Specifically, we empirically show that there exist many winning lottery tickets that are vastly different in terms of its sparse structure my. Fig. 3 shows the hamming distance of the sparse structure of the lottery tickets at different configuration (s, v). Note that the two distant lottery tickets (e.g.. (s 200, v = 100) and (s 100, v 100)) show large hamming distance of 0.159 (where z/y = 200/ 100) while achieving the equally good accuracy as shown in Fig. | indicating that the ranking of the weights itself can not explain the quality of the structure of the lottery ticket.
x
100
120
140
160
180
200
100
0
0.154
0.153
0.158
0.159
0.159
120
0.052
0.079
0.080
0.062
140
0.047
0.047
0.048
160
0
0.008
0.011
180
0
0.006
200
0
Figure 3: The hamming distance of the sparse structure of the lottery tickets at different configuration for ResNet20 on CIFARIO. z/y denotes the distance between (s = x) and (s = y). A large distance between two lottery tickets with equally good accuracy suggests the existence of many winning tickets.
3.3 UNDERSTANDING IMPACT OF PRUNED STRUCTURE
The weight magnitude analysis motivates not to prune model too early. It is also implied that a distance-based metric might not reveal the winning structure of the model at different epochs. To understand the early winning structures, we further investigate the impact of the sparsified structure on the final accuracy. Considering that highly pruned network is likely to have limited learning capability, we make a conjecture that the accuracy degradation of a pruned model is due to the loss of capability for learning complex pattern if pruned too early. Recently, [Li et al. (2019) reveals that the training behavior of a sufficiently paeepaaramtterized model with non non-linearity highly depends on the learning rate schedule, where a model tends to memorize the complex patterns when a small learning rate applied while learning simple patterns with large learning rate. To validate this claim in the context of pruning, we construct an experiment where a model is pseudo-pruned at every epoch of the baseline training then retrained with large or small learning rate for just one epoch. For the reeuudo-rrueed-hhe--etttte the validation accuracy recovered from the retraining.
Fig shows the result of this experiment on CIFAR10 ResNer20. When it is retrained with the large retraining learning rate (= 0.1), in just I-epoch retraining, the PPR models from all the baseline epochs achieve the accuracy matching with the baseline accuracy. This indicates that those pruned models maintain the capability of learning the simple patterns. Whereas, when the small retraining learning rate (= 0.01) is used, the accuracy of the PPR models pruned at later epochs (epoch 100-200) is higher than the accuracy of the models from earlier epochs (epoch 20-60). This reveals that the PPR models from different epoch exhibit varying capability of learning complex patterns. In particular, the accuracy of the PPR models increases until around 100 epoch of the baseline training, then it saturates. Note that this coincides with the epoch when the early winning tickets emerges in Fig.
Based on this observation, we hypothesize that the models pruned at 100 epoch of the baseline training or later will preserve the capability of learning complex patterns, To validate this hypothesis, we conducted the memorization test proposed by Boo et al. (2019), where model is trained with training data of varying size with the randomized labels.
5

---

90
20
80
75
epoch 200
epach
Valld Accuracy (90
70
-1
Traniin Accurscy8%)
63
60
65
50
60
50-
No Retraining
PPR LR=0.01
50
58
Data Sizo 15000
100
150
Epochs
10000 12500 15000 17500
20000
50
100
150
200
Data S1z0
Epoch
The seuubo-puundd-thee--errrnnnn (PPR) models for CIFARIO ResNet20, which exhibit increas- ing capability of memorizing the complex patterns over the epochs. Validation accuracy for the baseline training and validation accuracy after pruning without retraining also included for comparison.
Figure 4:
Figure 5: Left: Memorization capacity (i.e., training accu- racy) of the models pruned 3 different epochs. The models pruned at epoch 120 and 200 show almost identical memoriza- tion capacity, whereas the model pruned epoch 20 exhibits lower memorization capacity. Right: Memorization capacity of models pruned different epochs (training data size 15000).
A model has "high memorization capacity" if it achieves high training accuracy for large data size. Fig. (left) shows the training accuracy of the models pruned at different epochs, measured from 10 independent simulations (the average capacity shown as solid lines, and min and maz shown as the shaded regions). As the training data size increases, the memorization capacity decreases. The model pruned too early (i.e., at epoch 20) suffers higher degradation in the memorization capacity compared to the models pruned later epochs (i.e., epochs 120 or 200). Also, Fig. 5 (right) shows that those models pruned at later than 100 epochs (i.e., the early winning tickets) exhibit similar memorization capacity. This result not only confirms our conjecture on the impact of pruned structure to the capability of learning complex patterns, but also leads us to employ the PPR accuracy check computationally reasonable heuristic to discover the early winning tickets.
3.4 UNDERSTANDING GRADUAL PRUNING
Gradual pruning is popular pruning approach that applies pruning gradually over period of training. For example, gradual pruning proposed by Zhu & Gupta (2017) provides a systematic way to schedule iterative pruning as follows:
St sy + (s: (5)s)) s4) (I (1-1-46 1-40
(6)
ndt
where s and sy are the final and initial sparsity, and is the time when pruning applied. Eq. determines how much sparsity is applied at a certain time step t. But it is still a ussr-hyper-parrmeter parameter to decide when to or how often At apply pruning. Based on the insights we discussed in the previous section, we explain why gradual pruning helps to obtain better lottery tickets.
The reasoning behind the gradual pruning is that the model can be changed graciously the pruning is applied gradually. In terms of the early winning ticket analysis, there are two factors playing the critical role: 1) by applying low pruning rate in the beginning, the structure found that pruning level can preserve the memorization capacity better, 2) once pruning is applied, the remaining weights of the pruned model is updated via SGD, granting chance for the pruned model to adopt its weights toward better accuracy. Thanks to these two factors, a structure with better memorization capacity can be found when the increased pruning rate is applied next time.
Table I confirms this explanation using the CIFARIO ResNet20 example. In this experiment, we perform the memoriza- tion test for the 4-step gradual pruning well four 1-step pruning at the corresponding epoch for comparison. The gap in memorization capacity is maintained across the different epochs, demonstrating that the memorization capacity is maintained thanks the gradual application of pruning and the evolution of weights after pruning. This suggests strategy for gradual pruning where 1) we can use gradual pruning to reduce the loss of capability in learning complex patterns, and 2) by applying a smaller pruning rate in the beginning, we can start pruming early and finding the winning lottery tickets faster. The benefit of this strategy combining gradual pruning with the early winning tickets will be demonstrated in Sec.

---

Table 1: Memorization capacity (i.e., train accuracy) comparison between 1-shot and 4-shot pruning.
Epoch
120
160
200
240
Unit
Pruning rate
40
60
70
80
%
I-shot pruning
79.72
66.88
59.81
50.46
%
4-shot gradual pruning
79.72
68.83
61.21
51.45
%
4 EXPERIMENTS: FINDING WINNING TICKET EARLY
In this section, demonstrate our strategy of finding the early winning tickets over popular neural networks CIFARIO and ImageNet. The detail experimental setup is described in Appendix [ We perform the lottery ticket experiments of Sec. 3.1 for both one-shot and gradual pruning with the pruning rate of 80%. We also conduct the PPR accuracy check of Sec. 3.3 to predict from which epoch the early winning ticket can be found. By comparing the two results, demonstrate that the proposed heuristic for finding early winning tickets works robustly across the networks and the datasets. Furthermore, we showcase our gradual pruning strategy by comparing the performance in terms of the accuracy and the required pruning epochs with the existing lottery ticket approaches.
4.1 EXPERIMENTS ON CIFAR10
Table 2 summarizes the lottery ticket experiments of ResNet20 and ResNet56 on CIFARIO dataset. In case of one-shot pruning, the winning tickets can be found from epoch 100. In case of gradual pruning, the gradual pruning schedule can start from epoch 75 (which is earlier than the one-shot pruning). Note that the gradual pruning can achieve better accuracy can preserve higher memorization capacity discussed in Sec. [.4 Fig. [6 shows the pseudo-pruning curve that highlights the presence of the winning tickets from the epoch around 100, which is consistent with the results of the lottery ticket experiment in Table 2
Valid 1-epach Retraining (%)
Valid Acc. w/ 1-epoch Retraining (%)
90
winning lostery tickets
60
winning lottery Sckets
80
55
70
50
60-
45
50
40
35
50
100
150
Epochs
Epochs
(a) ResNet56 on CIFARIO
(b) ResNet18 on ImageNet
Figure 6: The results of PPR accuracy check (retraining learning rate=0.01) for (a) ResNet56 on CIFAR1O (sampled at every epoch) and (b) ResNet18 on ImageNet (sampled every 5 epochs).
4.2 EXPERIMENTS ON IMAGENET
Table summarizes the lottery ticket experiments ImageNet dataset, and the predicted results of the early winning tickets from the seeudo-pruning are shown in Fig. (6p. Similar to the CIFAR 10 experiments, the results of the lottery ticket experiment matches with the results from the PPR accuracy check (which indicates epoch 45 for early winning tickets), demonstrating the robust behavior of the proposed strategy of finding the early winning tickets. Furthermore, the gradual pruning at the early winning tickets achieves the accuracy near to the baseline (ResNet18. 8: baseline=69.77 7% vs ours=69.2444 ResNet50: baseline=75. 75.7% vs o5.3=75.311), showcasing the superior quality of the winning tickets discovered by the proposed gradual pruning strategy.
7

---

Table 2: One-shot and gradual pruning different epochs for ResNet20 and ResNet56 on CIFARIO. To clarify randomness effect, the average accuracy (%) over 10 different runs is reported.
One-Shot
20
100
120
160
200
ResNer20
90.01
(+0007)
91.20 (++0228)
91.49 (+0.27)
91.37 (+:0.24)
91.63
(+0.19)
91.63 (++0.21)
ResNe156
92.94 (+0.28)
93.60 (+0.18)
94.07 (+0.16)
94.24 (+0.19)
94.29 (+0.17)
94.34 (#0.14)
Gradual
25-75
50-100
75-125
100-150
125-175
150-200
ResNe120
91.43 (4:0.37)
91.56 (4.028)
91.78 (4:0.26
91.87 (7.0.1)
91.84 (1:0.32)
91.83 (+00.08
ResNet56
93.34 (#:0.19)
93.89 (+0.12)
94.03 (#0.229)
94.25 (=0.19)
94.15 (=0.17)
94.24 (=0.27)
Table 3: One-shot and gradual pruning for ResNet18 and ResNet50 on ImageNet.
One-Shot Pruning
15
30
45
75
90
ResNe118
Top-1 Ace. (%)
64.89
66.53
67.30
68.32
68.79
68.98
69.03
ResNe150
Top-1 Acc. (%)
71.65
73.11
73.71
74.51
74.90
74.92
75.03
Gradual Pruning
0-30
10-40
20-50
30-60
40-70
50-80
60-90
ResNet18
Top-1 Acc. (%)
66.11
67.31
68.31
68.64
69.24
69.06
69.18
ResNe150
Top-1 Acc. (%)
72.90
73.72
74.54
74.92
75.26
75.31
74.94
4.3 PERFORMANCE GAIN FROM EARLY WINNING TICKET
To demonstrate the performance gain from our gradual pruning strategy, the pruning results of the proposed algorithm (GP EWT) and the previous implementation of iterative pruning (IP) along with the winning ticket (WT) of Frankle & Carbin (218)) are shown for the ResNet variants on CIFAR10 and ImageNet in Table 4 Our GP+EWT algorithm consistently achieves high pruming rate with the number of pruning epochs even lower than the regular retraining epochs for all the models, i.e., 80% pruning with negligible accuracy degradation on ResNer50 for ImageNet. In contrast, the iterative pruning approach (IP+WT) achieves the similar accuracy at the cost of more than 4.5x increase in the total training epochs.
5 CONCLUSION
In this work, investigate the structure of the winning lottery ticket, which leads to the computationally efficient discovery of the winning lottery tickets. Based on a careful analysis of the characteristics of the structure of the winning lottery tickets, we proposed computationally reasonable heuristic identify when the early lottery tickets emerge. Furthermore, we proposed gradual pruning strategy incorporating the early lottery ticket analysis to achieve high accuracy at large pruning rate. This results in the state-of-the-art accuracy on ResNet50 for 80% pruning only within 22% of the total epochs for iterative pruning.
Table Performance gain by our gradual pruning strategy on CIFAR-10 and ImageNet.
ResNer20 (CIFAR-10) PR" acc.A epochs
ResNet18 (ImageNet)
ResNer50 (ImageNet) PR/ / acc. epoch
PR/ acc. / epochs
GP + EWT
80.0 -0.20 / 1
80.0 60.0/-0.56/ 70+90
80.0 -0.4 80+90
IP+ WT
82.2 / 0.00 1600
-/-/-
79.0/ 0.0 720
Frankle et al.
2019
GP: gradual pruning, IP: iterative method, EWT: early winning ticket, WT: winning ticket
pruning rate (PR). ** number of pruning epochs regular retraining epochs
1 the delta of accuracy measured against the baseline accuracy. Bold: highlight of comparison
8

---

REFERENCES
Yoonho Boo, Sungho Shin, and Wonyong Sung. Memorization capacity of deep neural networks under parameter quantization. ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1383-1387. IEEE, 2019.
Yann Le Cun, John S. Denker, and Sara A. Solla. Optimal brain damage. In Advances in Neural Information Processing Systems, pp. 598-605. Morgan Kaufmann, 1990.
Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred A Hamprecht. Essentially no barriers in neural network energy landscape. arXiv preprint arXiv:8033. 00885, 2018.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXiv:/803.0360 2018.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Stabilizing the lottery ticket hypothesis. arXiv preprint arXiv:1903.01611. 2019.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016.
Song Han, Jeff Pool, John Tran, and William J. Dally. Learning both Weights and Connections for Efficient Neural Networks. arXiv e-prints, art. arXiv:1506.02633 Jun 2015.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. S. Torr. SNIP: Single-shot Network Pruning based Connection Sensitivity. arXiv e-prints, art. 1810.02300 Oct 2018.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. ICLR, 2017.
Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. arXiv preprint arXiv: 04595, 2019.
Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang, Shoumeng Yan, and Changshui Zhang. Learning Efficient Convolutional Networks Through Network Slimming. In The IEEE International Conference Computer Vision (ICCV), October 2017.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the Value of Network Pruning. arXiv e-prints, art. arXiv: 181.00800,05270, Oct 2018.
Huizi Mao, Song Han, Jeff Pool, Wenshuo Li, Xingyu Liu, Yu Wang, and William J Dally. Exploring the Granularity of Sparsity in Convolutional Neural Networks. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, July 2017.
Pavlo Molchanov, Arun Mallya, Stephen Tyree, luri Frosio, and Jan Kautz. Importance estimation for neural network pruning. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, 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. arXiv preprint 190.v:1906002777 2019.
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning Structured Sparsity in Deep Neural Networks. In NIPS, 2016.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinki. Deconstructing lottery tickets: Zeros, signs, and the supermask. arXiv preprint
2019.
Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression. arXiv preprint 17000117,, 2017.

---

Table 5: Memorization capacity comparison for different group size.
Group size
1
2
4
8
16
32
64
Mem. Cap
60.3
60.4
59.4
59.1
58.5
55.0
52.4
A EXPERIMENTAL SETUP
A.1 EXPERIMENTS ON CIFAR10
We try to find the winning tickets early for ResNet20 (baseline accuracy: 92.5%) and ResNet56 (baseline accuracy: 94.25%) on CIFARIO dataset. All the baseline models trained using SGD optimizer with momentum (m =0.9) and weight decay (A =le-4) for 200 epochs. The initial learning rate for the first 120 epochs is 0.1 and decrease to 0. x every 40 epochs. For the lottery ticket experiments, the retraining schedule is the same as the baseline learning rate schedule. Following convention, we do not prune the first and the last layers of the ResNets.
A.2 EXPERIMENTS ON IMAGENET
We further try to find the winning tickets early for ResNet18 (baseline accuracy: 69.7%) and ResNet50 (baseline accuracy: 75.7%) ImageNet dataset. All the baseline models are trained using SGD optimizer with momentum (m =0.9) and weight decay (A = 1e-44 for 90 epochs. The initial learning rate for the first 30 epochs is 0.1 and decrease to 0.1x every 30 epochs. For the lottery ticket experiments, the retraining schedule is the same the baseline learning rate schedule. Following convention, we do not prune the first and the last layers of the ResNets.
Weight Tensor
Pruned Weights
gs=8
W
Structured Pruning (Grouped along Channel)
Element-wise Pruning
Figure 7: Structured pruning with variable group size. We consider group weights along the channel dimension with a varying group-size (gs). In case of gs=1, it the same as the element-wise pruning.
B DISCUSSION
B.1 IMPACT OF STRUCTURED SPARSITY ON LOTTERY TICKET HYPOTHESIS
In this section, we expand our scope of analysis on the characteristics of the early winning tickets toward the sparsity obtained via structured pruning. Structured pruning is popular method that prunes weights by group. For example, Liu et al. (2017) proposes channel-pruning where group consists of weights along each channel. The main motivation of looking the structured sparsity is that there is significant discrepancy in the best pruning rate we achieve between the dlement-wise pruning (i.e., group-size=1) and the structured pruning (i.e., croup-size=channe).. For example, on CIFAR1O- CIFAR1O-VGG19, the element-wise pruning achieves 95% of pruning rate whereas the Shannel--puning achieves 70% of pruning rate for the same level of accuracy (Liu et al. (2018)). Although such discrepancy has been observed for quite while, there is no in-depth investigation understand why. To find out the reasoning behind it, we analyze the impact of structured sparsity with varying group sizes in the context of the lottery ticket hypothesis, illustrated in 7
First, we revisit the extended lottery ticket experiments of Fig. while applying group sparsity along the channel dimension (instead pruning individual weights). Fig. g shows the results when the group size (gs) is 8, Comparing
10

---

vls
10
20
40
60
80
100
120
140
160
180
200
Baseline
80.26
83.74
82.72
85.30
84.31
84.95
87.55
92.08
91.63
92.11
92.05
90.10
90.27
89.92
89.85
90.02
89.73
90.07
89.76
90.19
89.95
89.85
90.12
90.14
89.99
90.65
90.41
90.42
90.46
90.29
90.49
90.17
90.53
10
90.04
90.30
90.20
90.37
90.43
90.58
90.68
90.41
90.41
90.68
90.46
20
90.35
90.43
90.23
90.56
90.30
90.65
91.02
90.88
90.65
90.29
90.58
90.30
90.38
90.05
90.30
90.76
90.82
90.72
91.10
90.52
90.24
90.80
60
90.27
90.32
90.30
90.58
90.58
90.83
90.86
90.95
90.78
90.73
90.45
80
90.28
90.39
90.27
90.50
90.48
90.76
90.93
90.69
90.26
90.66
90.69
100
90.30
90.70
90.48
90.63
90.22
90.11
90.83
90.79
90.55
90.72
90.53
120
90.00
90.56
90.30
90.52
90.82
90.52
90.74
90.50
90.79
90.45
90.79
140
90.35
90.52
90.54
90.37
90.54
91.03
90.48
90.69
90.75
90.60
90.99
160
90.58
90.34
90.57
90.44
90.68
90.52
90.79
90.35
90.41
90.85
90.53
180
90.57
90.41
90.54
89.97
90.82
90.56
90.80
90.64
90.61
90.89
90.20
200
90.43
90.41
90.23
90.64
90.58
20.87
20.93
99.73
90.57
.2.22
.2022
When group size(ss is 8, winning tickets (found when gs= disappear
Figure 8: Revisiting the extended lottery ticket experiments of Fig. but with the group size (gs) of 8. As before, (s, v) stands for (epoch drawing the sparse structure, epoch for rewinding). In contrast to Fig. the winning tickets found when gs=1 (green color in Fig. (T) disappear the group size becomes 8.
92.0
Group Sie
Group Saow
41.5
Size
41.0-
80.0
90.0
89.5
88.
125
150
Figure 9: Impact of structured sparsity on the saturation of pruning accuracy. The x-axis corresponds to the epoch when the model is 80% pruned. The dotted lines correspond to the moving average of the accuracy to show trends. The larger the group size, the later the accuracy of the pruned models converges at.
it with Fig. 1 there are two notable points; 1) there is > 1% accuracy degradation when the group size is increased from to and 2) when ys = 8, the trend that the tickets drawn at epochs s >> 100 achieve the higher accuracy disappears (as highlighted with red rectangle in the figure). (Note that the two figures achieve the similar accuracy when s < 60 (colored in yellow), but the tickets with high accuracy (colored green) can only be seen in Fig. I The former observation makes sense the more regularization accuracy. But the latter observation is quite surprising; it seems that a distinct behavior the lottery ticket hypothesis (i.e., the opportunity of finding winning tickets given proper initialization) is disrupted group structure is asserted on the sparsity.
the sparse weight structure would result in the lower
We find clue this disrupted behavior by employing the memorization capacity analysis. Table shows the results of memorization capacity experiments on CIFAR 10-ResNet20 with an increasing group size gs (1, 4, 8, 16, 32, 64). The memorization capacity degrades significantly as the group size increases. Intuitively, by asserting large group size, the model's expressivity is degraded and it becomes harder to learn the complex patterns, leading to accuracy loss. Note that had similar observation when the tickets are drawn early (cf.,s 60 in Fig Tp. From this, we can
11

---

hypothesize that the winning tickets disappear as the memorization capacity is degraded, which can be observed when the tickets are drawn too early or the group sparsity is forced.
Fig. 9 further demonstrates the impact of structured sparsity on the saturation of pruning accuracy. For different group sizes, the figure shows the accuracy of CIFAR RO-RROO-E 10------eee 10-ResNe120 80% pruned at varying epochs. It can be observed that the models with the larger group size not only achieve the lower accuracy but also converge at earlier epochs. (E.g., the knee points for gs = 1 and gs 16 are around 90 and 50 epochs, respectively.) This experimental result supports our claim that the larger group size enforced in the sparse structure results in the earlier convergence of the pruned models that misses the winning tickets.
ResNer50 on Imagetett
20 on CIFAR10
100
90
Val.d000 Snor (4)
70
e5och VS
VAl 000000 Smoo
opech 20 to opech 200
10-
52
0.8
0.3 Intrppad
Figure 10: Mode connectivity: Lottery tickets of ImageNet-ResNetIy and C0 drawn from different epochs are linearly interpolated, then the accuracy is measured for each interpolation coefficient. It can be observed that only the early winning tickets are connected to the winning tickets (drawn at the end of training, i.e., epoch 90 for ImageNet and epoch 200 for CIFARIO).
B.2 MODE CONNECTIVITY OF EARLY WINNING TICKETS
Mode connectivity is phenomenon that SGD solutions are connected through paths of approximately equal loss (Draxler et al.] (2018)) It provides the perspective of how well the models trained via a proposed method can generalize. In the context of early winning tickets. we for the first time reveal that the lottery tickets drawn early based on PPR are indeed connected from the one obtained by IMP, whereas the tickets chosen too early do not.
For the mode connectivity experiments, we draw three lottery tickets one drawn too early (i.e., a premature ticket, PT), one drawn based on PPR (i.e., an early winning ticket, EWT), and one at the end of the training schedule (i.e., winning ticket, WT). Note that all the tickets are trained from the same initial weights and with the same retraining schedule. Then we linearly interpolate PT and EWT with WT, and plot the test error for different interpolation coefficient (from O to 1).
Fig. 10 shows the results of the mode connectivity experiments for ImageNet and CIFAR10. For both datasets, the linearly interpolated models between PT and WT depict barrier, indicating that PT and WT are disconnected. Whereas, the linearly interpolated models between EWT and WT show consistently low test error. Note that such linear mode connectivity is observed even when 1) the weights are sparse (i.e., 80% pruning rate) and 2) the mask distance is large (cf., Fig. 3). This intriguing observation counters some observations of prior work; Draxler et al. 2018) claims that it takes a careful search (instead of a simple linear interpolation) to find a pass connecting the modes, and the existence of such non-linear pass requires enough number of parameters. Our novel observation of early lottery tickets provide new aspect of sparse model training; the sparse structures mature early in the training, and they converge to a flat local minimum even if its shape is vastly distant. A deeper investigation about the sparse structure of the lottery tickets and the mode connectivity is an interesting future research topic.
C EARLY WINNING TICKET ALGORITHMS
In this section, we describe the detail algorithms for finding early winning tickets via one-shot and gradual pruning.
12

---

Algorithm 1: Early Winning Ticket Identification with One-Shot Pruning
Require:
Initial weights lg. learning rate schedule LSS := {n(n)): n 0,1,... N pruning ratio p, PPR
accuracy checking period Tppn, PPR accuracy saturation detection threshold kprn. PPR retraining learning rate 1)PRi
Initialize model with lo t 0;
Step 1: Early winning ticket (EWT) identification by tracking PPR accuracy
for = 0; < N; +++ do
Train the model with learning rate 17(i) for one epoch;
if i % TPpR= 0 then
Save copy of the model and optimization state;
Prune p% of the model parameters and create mask PRR
Train the pruned model 0g MPPR for one epoch and obtain the test accuracy AccPPR,
Restore the model and optimization state with the saved copy;
if AccPPR, <= AcCpPR,' for f,t 1...., t Set the model parameters 0 mpPR, break;
kppa + then
end
1++;
end end
Step 2: Retraining EWT with the same LS
for = 0; i < N; +++ do
Train the pruned model with learning rate nti) for epoch;
end
Algorithm 2: Early Winning Ticket Identification with Gradual Pruning
Require:
Initial weights 0o. learning rate schedule LS = {v(#)), n O, 0, I,.....! N 1, pruning ratio PPR
accuracy checking period TPPR, PPR accuracy saturation detection threshold kPPR. PPR retraining learning rate 1PPR, gradual pruning period Tgr Initialize model with fg.
Step 1: Early winning ticket (EWT) identification by tracking PPR accuracy
for = 0; i N: +++ do
Train the model with learning rate v7i) for one epoch;
if % TPPR = 0 then
Save copy of the model and optimization state;
Prune p% the model parameters and create a mask MPPR,
Train the pruned model 0, mppR for epoch and obtain the test accuracy AccpPRA Restore the model and optimization state with the saved copy;
if AccpPR.
-1 t' t,t L..... kPPR then
break;
end
end 1++;
end
Step 2: Gradual Pruning to refine the EWT structure
for i == 0; i Tyr: +++ do
Prune model gradually toward the pruning ratio according to Eq. (6) and create a mask mgr. Train the pruned model fgr mgr.s for one epoch;
end
Step 3: Retraining EWT with the same LS
for i == 0; i < N; +++ do
Train the pruned model with learning rate vy(i) for one epoch;
end
13


Reviews:
[{"review_id": "SkgLQMNaFr", "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": "Overview:\n\nThe paper is dedicated to conducting an in-depth investigation of the structure of winning lottery tickets. The author provides supporting evidence for the structure of the early winning tickets: 1) lottery tickets emerge when the weight magnitude of a model saturates with SGD optimization. 2) pruning before model saturation may result in accuracy degradation. In the experiment part, they employ the memorization capacity analysis and discover the early wining tickets without expensive iterative pruning. The author also conducts extensive experiments with various ResNet architectures on both CIFAR 10 and ImageNet, achieving state-of-the-art results with only 1/5 of the total epochs for iterative pruning.\n\nStrength Bullets:\n\n1. The experiment organization is complete and convincing. Especially for the figure, it not only clearly shows that lottery tickets emerge much earlier before full training ends, but also shows the effect of rewinding. \n2. The author not reveal interesting observations, but also provides useful guidance. It is a complete logic chain that is also aligned with my intuition. For example, first, the author discusses the memorization capacity of different pruned models at different epochs. Then, they introduce a reasonable gradual pruning technique. Finally, they conduct experiments to confirm it.\n3.  The early winning tickets in this paper achieve state-of-the-art results with only 1/5 of the total epochs for iterative pruning.\n\nWeakness Bullets:\n\n1. For lottery tickets, especially for early winning tickets, I think there is a lot of randomnesses. Thus, for the plot like figure 2, figure 5, they need to contain an error bar and the curve should be the average of tens of experiments. It will be more convincing if it decouples the randomness from the real patterns.\n2. The description and organization of section 4 need to be more clear. For example, an algorithm pseudo code will definitely give readers a much more clear understanding of the early winning tickets finding strategy.\n\n\n\nQuestion the authors don't answer which confuses me more:\nNeed more convincing analysis about the indicator - Hamming Distance \n\nJust as the comment I posted after Review 1, we would like to see more analysis about Hamming Distance between different winning tickets. The author mentioned in the following way:\n\n''However, as we demonstrate in Fig. 3 of our paper, the mask-distance does not well characterize the winning tickets. E.g., the lottery tickets drawn at Epoch 120 and 200 have a mask distance of 0.082 in Fig. 3, which is much larger than the mask distance between Epoch 180 and 200. Whereas, all three tickets achieve comparably high accuracy as shown in Fig. 1, implying a shallow correlation between the accuracy and the mask distance''\n\nAs far as I know, this observation only tells us that the structure of the lottery tickets changes, which are drawn from 120 epochs to 180 epochs (although the maintain a similar accuracy). However, we can not conclude that the mask distance is not a reliable measure. As mention by the [EB] paper provided by the authors, you can use the rate of the distance change to indicate the early winning tickets. In this way, we can find winning tickets much earlier than authors' work.\n\nTo better address this question, I suppose the authors need to provide more analysis of the mask distance indicator. I think all three reviewers would like to see the results. A good indicator for early winning tickets is very important, otherwise authors' notion of early still involves quite a lot of training.\n\nRecommendation:\n\nDue to the unsolved important question, here is a weak reject.", "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": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SkgFH5o3FS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper attempts an in depth study of the lottery ticket hypothesis. The lottery ticket hypothesis holds that sparse sub-networks exist inside dense large models and that the sparse sub-networks achieve at least as good an accuracy as the underlying large model. These sub-networks are discovered by training and iteratively pruning the dense model. This paper investigates the epoch at which pruning should occur as well as the epoch at which weights should be rewound when retraining. Then, the authors conduct experiments with different pruning strategies (one-shot vs. gradual) in an attempt to find such sparse models (or \"winning tickets\") earlier than they otherwise would have been found.\n\nThe experiments conducted by the authors seem to be very extensive, and I think the paper contains useful data to have for researchers interested in better understanding the lottery ticket hypothesis. However, my main issue is with both the originality and significance of this work. This paper gives evidence that winning tickets may be found \"early,\" although their notion of early still involves quite a lot of training. \n\nAlthough the paper is interested in addressing the structure of the winning tickets, I really didn't find any of the discussion of structure to give much insight into the lottery ticket hypothesis. Most of the section focuses on analyzing weight magnitude, though I was hoping for something more about the actual structure of the sparse subnetwork -- especially given the title of the paper. Figure 3 is notable, showing that different winning tickets (parameterized by different prune and rewind epochs) can have a large Hamming distance between them. This is very interesting, and I wish the authors had more to say. How is this affected by different initializations? Are these solutions connected on a loss landscape? Is there something invariant about the sparse architecture after symmetries are taken into account? It's not clear to me that Hamming distance alone is enough.\n\nIn conclusion, the paper presents a set of nice experiments, but doesn't really shed too much additional light on the scientific nature of the lottery ticket hypothesis.", "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": "N/A"}, "extra_text": {}}, {"review_id": "B1xmfZs6Yr", "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 carefully observes the behavior of weight magnitudes during training, finding the is a stage of saturation that is closely related to the winning lottery tickets drawing. Based on this observation the authors hypothesize that we can draw lottery tickets early but too early pruning can irreversibly hurt the learning capability for complex pattern. To remedy this and draw the tickets as soon as possible, the authors propose to adopt gradual pruning, which 1) can start early without hurting the learning capability too much; 2) avoid computation-heavy iterative pruning in previous works.\n\nQuestions:\n\n1. Overall I am very happy with the interesting observations and analysis of the dynamics of weight magnitudes and how it can be related to the early winning lottery tickets drawing. But how valuable is it for practical use? In practice, we cannot know in advance when to start (gradual) pruning.\n\n2. In Fig.1, what does it mean if we perform weight-magnitude based pruning at 10th epoch but rewind the weight to the 20th epoch? Is there a baseline network that is normally trained straight to the end and to which we rewind all pruned models?\n\n3. I am not quite convinced by the experiment of Fig. 4 and argument at the bottom half of page 5. I buy the intuition that pruning too early might irreversibly hurt the capability of learning complex pattern. But I have trouble understanding how the experiment of Fig. 4 supports this intuition. The curve of retraining with smaller LR (0.01) has the save trend as the baseline and retraining with larger LR (0.1). Retraining only one epoch can hardly convince me of its relationship with learning capability. Also, for the experiment in Fig. 5, to validate the proposed hypothesis, it's more valuable to provide results around the claimed turning point, i.e. around 100 epoch instead of suddenly jumping from 20 epoch to 120 epoch.\n\n4. In Tab. 2, the results of ResNet56 with gradual pruning is not presented. In Tab. 3, the results of ResNet50 with one-shot pruning is not presented. It would be better to have these results for clear comparison.\n\nOverall, I love the empirical observation of weight magnitudes and think it would help the community to understand lottery tickets and training process of deep models.\n\nUpdate:\nThe response from the authors addressed some of my questions and more experiments were added per my suggestions. However, also considering the authors' response to R#1 and R#3, I don't think it's strong enough for me to raise my score. Therefore I will keep my current score.", "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": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper does extensive experiments to understand the lottery ticket hypothesis. The lottery ticket hypothesis is that there exist sparse sub-networks inside dense large models that achieve as good accuracy as the original model. The reviewers have issues with the novelty and significance of these experiments. They felt that it didn't shed new scientific light. They felt that epochs needed to do early detection was still expensive. I recommend doing further studies and submitting it to another venue.
Decision: Reject