Rare Gems: Finding Lottery Tickets at Initialization
Authors: Kartik Sreenivasan
Jy-yong Sohn
Liu Yang
Matthew Grinde
Alliot Nagle
Hongyi Wang
Eric Xing
Kangwook Lee
Dimitris Papailiopoulos
Venue: NeurIPS 2022 Accept (2022)

Abstract: Large neural networks can be pruned to a small fraction of their original size, with little loss in accuracy, by following a time-consuming "train, prune, re-train" approach. Frankle & Carbin conjecture that we can avoid this by training lottery tickets, i.e., special sparse subnetworks found at initialization, that can be trained to high accuracy. However, a subsequent line of work presents concrete evidence that current algorithms for finding trainable networks at initialization, fail simple baseline comparisons, e.g., against training random sparse subnetworks. Finding lottery tickets that train to better accuracy compared to simple baselines remains an open problem. In this work, we resolve this open problem by proposing Gem-Miner which finds lottery tickets at initialization that beat current baselines. Gem-Miner finds lottery tickets trainable to accuracy competitive or better than Iterative Magnitude Pruning (IMP), and does so up to $19\times$ faster. 

Rare Gems: Finding Lottery Tickets at Initialization
Kartik Sreenivasan" ", Jy-yong Sohn" ", Liu Yang", Matthew Grinde" Alliot Nagle." Hongyi Wang; Eric Xing Kangwook Lee," Dimitris Papailiopoulos
Carnegie Mellon University Mohamed Bin Zayed University of Artificial Intelligence PPetuum, Inc. University of Wisconsin-Maddsso
Abstract
Large neural networks can be pruned to a small fraction of their original size, with little loss in accuracy, by following time-consuming "train, prune, re-train" approach. Frankle & Carbin [9] conjecture that we can avoid this by training lottery tickets, i.e., special sparse subnetworks found at initialization, that can be trained to high accuracy. However, a subsequent line of work [11, 41] presents concrete evidence that current algorithms for finding trainable networks at initialization, fail simple baseline comparisons, e.g., against training random sparse subnetworks. Finding lottery tickets that train better accuracy compared to simple baselines remains an open problem. In this work, we resolve this open problem by proposing GEM-MINER which finds lottery tickets at initialization that beat current baselines. GEM-MINER finds lottery tickets trainable to accuracy competitive or better than Iterative Magnitude Pruning (IMP), and does so up to 19x faster.
Introduction
A large body of research since the 1980s empirically observed that large neural networks can be compressed or sparsified
small fraction of their original size while maintaining their predictive accuracy [14-16, 20, 23, 29, 45]. Although several pruning methods have been proposed during the past few decades, many of them follow the "train, prune, re-train" paradigm. Although the above methods result in very sparse, accurate models, they typically require several rounds of re-training, which is computationally intensive.
Frankle & Carbin [9] suggest that this computational burden may be avoidable. They conjecture that given a randomly initialized network, one can find sparse subnetwork that can be trained to accuracy comparable to that of its fully trained dense counterpart. This trainable subnetwork found at initialization referred to as lottery ticket. The study above introduced iterative magnitude pruning (IMP) as a means of finding these lottery tickets. Their experimental findings laid the groundwork for what now known as the Lottery Ticket Hypothesis (LTH).
Although Frankle & Carbin [9] establish that the LTH is true for tasks like image classification on MNIST, they were not able get satisfactory results for more complex datasets like CIFAR-10 and ImageNet when using deeper networks, such as VGG and ResNets [10]. In fact, subsequent work brought the effectiveness of IMP into question. Su al. [41] showed that even randomly sampled sparse subnetworks at initialization can beat lottery tickets found by IMP as long as the layerwise sparsities are chosen carefully. Gale al. [12] showed that methods like IMP which train tickets from initialization cannot compete with the accuracy of model trained with pruning as part of the optimization process.
Frankle et al. [10] explain the failures of IMP using the concept of linear mode connectivity which measures the stability of these subnetworks to SGD noise. Extensive follow-up studies propose
Authors contributed equally to this paper.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Pirtaly trined Dinoe Nitwork
heratively
Sitmetoork Warn Iradiestor
Vraned 99 Spara suineterr
Firetune
Wiemup
IMP
89L9SS Accurvty
Rasberb
slane intsllottoo
Spars
Subretwor
Firetune
Gem-Miner
Prune nébilizttion
59.3%
90.50
Figure 1: Conceptual visualization of MIMER IMP with warmup. The accuracies listed 99.5% sparse VGG-I6 16 trained on CIFAR-10. Given a randomly initialized network, both methods output subnetwork which is then finetuned. IMP requires warmup i.e, few epochs training before it can find a sparse subnetwork. GEM-MINER finds a rare gem, a subnetwork at initialization that achieves high accuracy both before and after weight training.
several heuristics for finding trainable sparse subnetworks at initialization [24, 42, 43]. However, subsequent work by Frankle et al. [11], Su et al. [41] show experimentally that all of these methods fail simple sanity checks. Most methods seem to merely identify good sparsities at each layer, but given those, random sparse subnetworks can be trained similar better accuracy.
Frankle et al. [10] show that with small modification, IMP can beat these sanity checks; the caveat is that it no longer finds these subnetworks at initialization, but after few epochs of warm-up training. Since these subnetworks are found after initialization, IMP with warmup does not find lottery tickets.
As noted the original work by Frankle Carbin [9], the importance finding trainable subnetworks at initialization is computational efficiency. It is far preferable to train sparse model from scratch, rather than having to deal with a large dense model, even that is for a few epochs (which is what IMP with warmup does). To the best of our knowledge, the empirical validity of the Lottery Ticket Hypothesis, i.e., the hunt for subnetworks at initialization trainable to SOTA accuracy, remains an open problem.
Our Contributions. We resolve this open problem by developing MEMMR, an algorithm that finds sparse subnetworks initialization, trainable accuracy comparable or better than IMP with warm-up. GEM-MINER does so by first discovering rare gems. Rare gems are subnetworks at initialization that attain accuracy far above random guessing, even before training. Rare gems can then be refined to achieve near state-of-the art accuracy. Simply put, rare gems are lottery tickets that also have high accuracy at initialization.
High accuracy at initialization is not a requirement for a network to be defined as a lottery ticket. However, if our end goal is high accuracy after training, then having high accuracy at initialization likely helps.
Rare gems found by GEM-MINED are the first lottery tickets beat all baselines in [11, 41]. In Fig. we give a sketch of how GEM-MINER compares with IMP with warm start. GEM-MINER finds subnetworks at initialization and is up to 19x faster than IMP which needs warmup.
2 Related Work
Lottery ticket hypothesis. Following the pioneering work of Frankle & Carbin [9], the search for lottery tickets has grown across several applications, such as language tasks, graph neural networks and federated learning [3, 4. 13, 25]. Savarese et al. [37] propose an alternative to IMP which is significantly faster given enough parallel computing resources. While the LTH itself has yet to be proven mathematically, the so-called strong LTH has been derived which shows that any target network can be approximated by pruning a randomly initialized network with minimal overparameterizatton [28, 30, 32]. Recently, it has been shown that for such approximation results it suffices to prune a random binary network with slightly larger overparametcrizztion [6, 40].
Pruning at initialization. While network pruning has been studied since the 1980s, finding sparse subnetworks at initialization is more recently explored approach. Lee et al. [24] propose SNIP,

---

Table I: We compare the different popular pruning methods in the literature on whether they prune at initialization, are finetunable and pass sanity checks. We also list the amount of computation they need to find 98.6% sparse subnetwork on ResNet-20, CIFAR-10. For consistency, we do not include the time required to finetune this subnetwork to full accuracy as it would be equal for all methods. For single-shot pruning method we list it as 1 epoch but this depends the choice of batch-size. Learning Rate Rewinding which we label Renda et al. [34] is a pruning after training algorithm and just outputs a high accuracy subnetwork and hence the sanity checks do not apply to it.
Praning Method
Prunes at inirializarion
Finetunable
Passes sanity checks
Computation to reach 98.6% sparsity
IMP [9]
2850 opochs
SNIP [24]
epach
GraSP [43]
X
I epoch
SynFlow [42]
/
X
1 epach
Edge-popup [33]
X
epocts O(1)
Smart Ratio [41]
/
Learning Rate Rewinding [34]
/ V X
3000 opachs
GEM-MINER
150 epochs
which prunes based a heuristic that approximates the importance of connection. Tanaka et al. [42] propose SynFlow which prunes the network to target sparsity without ever looking at the data. Wang et al. [43] propose GraSP which computes the importance of weight based on the Hessian gradient product. Patil & Dovrolis [31] propose PHEW which is based on the decomposition of the Neural Tangent Kernel. Lubana & Dick [26] create an interesting theoretical framework based on gradient flow that justifies the successes and failures of several of these algorithms. The goal of these algorithms to find subnetwork that can be trained to high accuracy. Ramanujan et al. [33] propose Edge-Popup (EP) which finds a subnetwork at initialization that has high accuracy to begin with. Unfortunately, they also note that in most cases, these subnetworks are not conducive to further finetuning.
The above algorithms are all based on the idea that one can assign a "score" to each weight to measure its importance. Once such a score is assigned, one simply keeps the top fraction of these scores based on the desired target sparsity. This may be done by sorting the scores layer-wise or globally across the network. Additionally, this can be done in one-shot (SNIP, GraSP) or iteratively (SynFlow). Note that IMP can also be fit into the above framework by defining the "score" to be the magnitude of the weights and then pruning globally across the network iteratively.
More recently, Alizadeh et al. [1] propose ProsPr which utilizes the idea of meta-gradien through the first few steps of optimization to determine which weights to prune. Their intuition is that this will lead to masks initialization that are more amenable to training to high accuracy. While it finds high accuracy subnetworks, we show in Section 4.2 that it fails to pass the sanity checks in [11, 41].
Sanity checks for lottery tickets. A natural question that arises with pruning at initialization is whether these algorithms are truly finding interesting and nontrivial subnetworks, or if their perfor- mance after finetuning can be matched by simply training equally sparse, yet random subnetworks. Ma et al. [27] propose more rigorous definitions of winning tickets and study IMP under several settings with careful tuning of hyperparameters. Frankle et al. [11] and Su et al. [41] introduce several sanity checks (i) Random shuffling (ii) Weight reinitialization (iii) Score inversion and (iv) Random Tickets. Even at their best performance, they show that SNIP, GraSP and SynFlow merely find good sparsity ratio in each layer and fail to surpass, in term of accuracy, fully trained randomly selected subnetworks, whose sparsity per layer is similarly tuned. Frankle et al. [11] show through extensive experiments that none of these methods show accuracy deterioration after random reshuffling. We explain the sanity checks in detail in Section 4 and use them as baselines to test our own algorithm.
Pruning during/after training. While the above algorithms prune at/near initialization, there exists rich literature on algorithms which prune turing/after training. Unlike IMP, algorithms in this category do not rewind the weights. They continue training and pruning iteratively. Frankle et al. [11] and Gale et al. [12] show that pruning at initialization cannot hope to compete with these algorithms. While they do not find lottery tickets, they do find high accuracy sparse networks. Zhu & Gupta [45] propose gradual pruning schedule where the smallest fraction of weights are pruned at a predefined frequency. They show that this results models up to 95% sparsity with negligible loss in performance on language as well as image processing tasks. Gale et al. [12] and Frankle et al. [11] also study this as a baseline under the name magnitude pruning after truining. Renda et al. [34] show that rewinding the learning rate opposed to weights(like in IMP) leads to the best performing
3

---

sparse networks. The closest among these to GEM-MINER is Movement Pruning by Sanh et al. [36] which also computes the mask as a quantized version of the scores in its soft variant. However, it is important to remark that these algorithms do not find Lottery Tickets, merely high accuracy sparse networks. We contrast these different methods in Table in terms of whether they prune at initialization, their finetunability, whether they pass sanity checks as well as their computational costs.
Finally, we note that identifying a good pruning mask can be thought of as training a binary network where the loss is computed over the element-wise product of the original network with the mask. This has been explored in the quantization during training literature [5, 19, 38).
3 GEM-MINER: Discovering Rare Gems
Setting and notation. Let 5 = ( v:) be a given training dataset for a k-classification problem, where 2; E R denotes a feature vector and label y: E {1..... .k. denotes its label. Typically, we wish to train a neural network classifier f(ww; a:) Rd - (T....,kk) where ur E Re denotes the set of weight parameters of this neural network. The goal of pruning algorithm is to extract a mask m = {0, 13d, so that the pruned network is denoted by f(w @ m: x). where @ denotes the element -ise product. We define the sparsity of this network to be the fraction of weights that have been pruned: s = (1 - || mm/lo//
ki),
following the convention set by Frankle et al. [11]. The loss of a classifier on single sample (æ, y) is denoted by [(f(w m; m;)), y), which captures measure of discrepancy between prediction and reality. In what follows, we will denote by we E IR to be the set of random initial weights. The type of randomness will be explicitly mentioned when necessary.
On the path to rare gems; first stop: Maximize pre-training accuracy. A rare gem needs to satisfy three conditions: (i) sparsity, (ii) non-trivial pre-training accuracy, and (iii) that it can be finetuned to achieve accuracy close to that of the fully trained dense network. This not an easy task as we have two different objectives in terms of accuracy (pre-training and post-training), and it is unclear a good subnetwork for one objective is also good for the other. However, since pre-training accuracy serves lower bound on the final performace, then attempt to further improve by finetuning.
focus on maximizing that first, and
LA- 1e-4)
SM (A- Se-5)
Our algorithm is inspired by Edge-Popup (EP) [33]. EP successfully finds subnetworks with high pre-training accuracy but it has two major limitations: (i) it does not work well in the high sparsity regime (e.g.. > 95%). and (ii)
Jc 50%)
80%
433351
(10.00 0, 10.0
Sparsity (%))
GM: 55,
EP: (70.69, 84.34)
95
GM: (73.36 89:32] EP: (90.06, 90.93)
most importantly, the subnetworks it finds are typically not conducive to further finetuning in
GM:
50-
EP: (91..7, 92.07/
100
200
300
400
500
600
that the final accuracy does not approach the performance of IMP.
Epoch
The sparsity intermediate results. the ac- curacy of the final output, and the accuracy after fine- tuning on MobileNet-V2. V2, CIFAR 10. For GEM-MINER (GM), also visualize the sparsity upper bounds as dotted lines. As À increases, note that the sparsity of
Figure 2:
In the following, we take GEM-MINER apart and describe the components that allow it to surpass these issues.
GEM-MINER without sparsity control. Much like EP, GEM-MINER employs a form of backpropagation, and works as follows. Each of the random weights [wo]s in the original network is associated with a normalized score Ps E [0, I]. These normalized scores become our optimization variables and are responsible for computing the supermask m, i.e., the pruning pattern of the network at initialization.
FEMMMINER 's output increases. For = 3. 10 the iterative freezing algorithm kicks in around epoch 220, regularizing the sparsity thereafter. The gem found by GEM-MINER(2 = 1.5 10- achieves accuracy of 84 .2.% before finetuning and 87.37% after finetuning. while EP is unable to achieve non-trivial accuracy before or after finctuning at 98.3% % sparsity.
For a given set of weights w and scores GEM-MINER sets the effective weights wall wor(p) where r(-) is an dement-wise rounding function, and m = r(p) the resulting supermask. The rounding function can be changed, e.g., r' can perform randomized rounding, in which case p; would be the probability of keeping weight wn in m. In our case, we found that simple deterministic rounding, i.e., r(p.) = 10:20.5 works well.

---

At every iteration GEM-MINER samples batch of training data and performs backpropagation on the loss of the effective weights. with respect to the scores p. while projecting back to [0, 1] when needed. During the forward pass, due to the rounding function, the effective network used is indeed a subnetwork of the given network. Here, since r(p) is a non-differentiable operation we use the Straight Through Estimator (STH) [2] which backpropagates through the indicator function as though it were the identity function. Therefore, even pruned scores can receive non-zero gradients which allows them to revive over the course of training.
Note that this vanilla version of PEMMMMNEERI is unable to exercise control over the final sparsity of the model. For reasons that will become evident in below, we will call this version of our algorithm GEM-MINER(O) There is already a stark difference from EP: GEM- (EM-MINER(0) will automatically find the optimal sparsity, while EP requires the target sparsity s as an imput parameter.
However, at the same time, this also significantly limits the applicability of GEM-MINER(() as one cannot obtain a highly sparse gem. Shown as a dark blue curve in Fig. 2 is the sparsity of GEM-MINER(O), Here, we run GEM-MINER with a randomly initialized MobileNet-Va V2 network on CIFAR-10. Note that the sparsity stays around 50% throughout the run, which is consistent with the observation by Ramanujan et al. [33] that accuracy of subnetworks at initialization is maximized at around 50% sparsity.
Regularization and Iterative freezing. GEM- (O)ER(() is good baseline algorithm for find- ing accurate subnetworks at initialization, but it cannot be used to find rare gems, which need to be sparse and trainable. To overcome this limitation, we apply a standard trick we add a regularization term to encourage sparsity. Thus, in addition to the task loss computed with the effective weights, we also compute the L22 or L1 norm of the score vector p and optimize over the total regularized loss. More formally, we minimize == frask + Abrog, where À is the hy- perparameter and freg. is either L2 or Li norm of the score vector p.
Algorithm I: GEM-MINER
Input: Dataset D = { y;)}, learning rate n, rounding function r()), number of epochs
E, freezing period T, target sparsity
8 [0, 1]
Output: Mask m r(p) @ {0, 13"
In
( 1a
w. pr.p< random vector in R
random vector in [0, 1]dd for ji in .... E do for (ass, 31) D do
Wett < (w o 9) O r(p)
p - p V, ((((.rr:)))))
/+ STE +/
p t--rojjo.1j'
We call this variant GEM-MINER(A), where À denotes the regularization weight. This naming convention should explain why we called the initial version GEM-MINERS
10
if mod((j. 7) 0 then
11 4 {i: g. 1 Psorted sort(p)eL,)
12
The experimental results in Fig. 2 show that this simple modification indeed allows us control the sparsity of the solution. We chose to use the L2 regularizer, however preliminary exper- iments showed that L1 performs almost identi- 6 and À 1.5 10 5, the final sparsity of the gem cally. By varying À from À to A = 7 10-6 found by GEM-MINER(A) becomes 97.5% and 98.6%, respectively.
Photiam + Bottom-(1 -0) fraction of Psorted
15
q xtgg q 2
ps Proocoo
One drawback of this regularization approach is that it only indirectly controls the sparsity. If we have a target sparsity s, then there is no easy way of finding the appropriate value of such that the resulting subnetwork is s-sparse. If we choose X to be too large, then it will give a gem that is way too sparse; too small a X and we will end up with a denser gem than what is needed. As a simple heuristic, we employ iterative freezing, which is widely used in several existing pruning algorithms, including IMP [9, 12, 45). More specifically, we can design an exponential function 3(j) = 1 e-c for some c > O. which will serve as the upper bound on the sparsity. If the total number of epochs is
E and the target sparsity is 8, we have 3 B(E) = 1 e e = s. Thus, we have
In
E
Once this sparsity upper bound is designed, the iterative freezing mechanism regularly checks the current sparsity to see if the lower bound is violated or not. If the sparsity bound is violated, it finds the smallest scores, zeros them out, and freezes their values thereafter. By doing so, we can guarantee the final sparsity even when À was not sufficiently large. To see this freezing mechanism in action, refer the blue curve in Fig. 2. Here, the sparsity lower bounds (decreasing exponential functions) are visualized as dotted lines. Note that for the case of x = 3 10-6, the sparsity of the network does
5

---

not decay as fast as desired, so it touches the sparsity lower bound around epoch 220. The iterative freezing scheme kicks in here, and the sparsity decay is controlled by the lower bound thereafter, achieving the specified target sparsity at the end.
The full pseudocode of GEM--MINER is provided in Algorithm 1. There details which differ from the explanation above: (i) we impose the iterative freezing every 'I' epochs, not every epoch and (ii) iterative freezing imposed even when the sparsity bound is not violated.
minor implementation
Weight training
Rende et el. treinit weight)
IMP (with warmup!
EP
5R
GM
GM Ishulffe mask)
GM (invert score)
ResNet-20
MobileNet-V V2
VGG-16
WideResNet-228
Test Acc. (%)
90
90
-0
70
50
30
95 97.396.5
59.5
50
80
95
97.5 96.5
50
5U
90
97.535.6
59.5
50
50
95 Sparsity (%)
97.5 v8.5
Sparsity (%6
Sparsity (%)
Sparsity (%)
2 90
90
80
80
80
80
70-
70-
60-
00
50
50
50
50
Sparsity
Sparsity
Sparsity (%)
Sparsity
Figure 3: Performance of different pruning algorithms on CIFAR- 10 for benchmark networks. Top: post- fest-finetune accuracy: Bottom: sanity check methods suggested in Frankle et al. [11] applied on GEM-MINER (GM). Note that GM achieves similar post-finetune accuracy as IMP, and typically outperforms in the sparse regime. GM has higher post-finetune accuracy than EP and Smart Ratio (SR). GM also passes the sanity checks suggested in Frankle et al. [11]. Finally, GM (which prunes al init) nearly achieves the performance of Renda et al. (which is pruning after training method) in the sparse regime, e.g.. 98.6% sparsity in ResNet-20.
4 Experiments
In this section, we present the experimental results² for the performance of GEM-MINER across various tasks.
Tasks. We evaluate our algorithm on (Task 1) CIFAR-10 classification, on ResNet-20, MobileNet- V2, VGG-16, and WideRessNet-8822 (Task 2) TinylmageNet classification ResNet- 18 and ResNet-50, (Task 3) Finetuning on the Caltech- [7] dataset using a ResNet-50 pretrained on ImageNet, and (Task 4) CIFAR-100 classification using ResNet-32. The detailed description of the datasets, networks and hyperparameters can be found in Section A of the Appendix.
Proposed scheme. We run GEM-MINER with an L2 regularizer. If network reaches its best accuracy after epochs of dense training, then we run GEM-MINER for E epochs from random init to get a sparse subnetwork at initialization, and then run weight training on the sparse subnetwork for another E epochs.
Comparisons. We tested our method against the following baselines: dense weight training and four pruning algorithms: (i) IMP [10], (ii) Learning rate rewinding [34], denoted by Renda et al., (iii) Edge-Popup (EP) [33], and (iv) Smart-Ratio (SR) which is the random pruning method proposed by Su et al. [41].
We also ran the following sanity checks, proposed by Frankle et al. [11]: (i) (Random shuffling): To test if the algorithm prunes specific connections, we randomly shuffle the mask every layer. (ii) (Weight reinitialization): To test if the final mask is specific to the weight initialization, we reinitialize the weights from the original distribution. (iii) (Score inversion): Since most pruning algorithms use a heuristic/score function as a proxy to measure the importance of different weights, we invert the scoring function check whether is valid proxy. More precisely, this test involves pruning the weights which have the smallest scores rather than the largest. In all of the above tests, if the accuracy after finetuning the new subnetwork does not deteriorate significantly, then the algorithm is merely identifying optimal layerwise sparsities.
"Or codebase can be found at https: : http://huubb.cco///eeeeeeaaaaaae
enough.

---

Weight training
Renda
IMP (with warmup! GM tshuftfe mask)
treinit weight)
GM Onivert scond)
TinyImageNet, ResNet-18
Tiay InageNet ResNet-50
Caltech- 101, ResNet-50
CIFAR-I00. ResNet-32
200
Test Acc. (56)
40
95 57 596.6 Sparsity (%)
69.5
97. 5..9966 Sparsity 1%5
97.5
30
97.566 15.5
Sparsity (%)
Sparsity 1%6
60
Tast Acc, (NU
10
80
Sparsity (96
Sparsity (86)
Sparsity (9%
Sparsity (55
Figure 4: Accuracy on image classification tasks on TinyImageNet, Caltech- 101 and CIFAR- 1000 For Caltech- 101, we pruned pre-trained ImageNet model (ResNct-50). Top: post- finetune accuracy, bottom: sanity check methods suggested in Frankle et al. [11] applied on GEM-MINER.
4.1 Rare gems obtained by GEM-MINER
Task 1. Fig. 3 shows the sparsity-accuraet tradeoff for various pruning methods trained on CIFAR- 10 using ResNet-20, MobileNet-V V2, VGG-16 and WideResNet-28-2.. For each column (network). we compare IMP. IMP with learning rate rewinding (Renda et al.) GEM-MINER, EP, and SR in two performance metries: the top row shows the accuracy of the subnetwork after weight training and bottom row shows the result of the sanity checks on GEM-MINER.
As shown in the top row of Fig. 3, BEM-MINER finds lottery ticket initialization. It reaches accuracy similar to IMP after weight training. Moreover, in the sparse regime (e.g., above 98.6% for ResNet-20 and MobileNet-V2), GEM-MINER outperforms IMP in terms of post-finetune accuracy. The bottom row of Fig. 3 shows that GEM-MINER passes the sanity check methods. For all networks, the performance in the sparse regime (98.6% sparsity above) shows that the suggested GEM- MINER algorithm enjoys 3-10% accuracy gap with the best performance among variants. The results in the top row show that GEM-MINER far outperforms the random network with smart ratio (SR).
Tasks 2-4 Fig. 4 shows the sparsity- sparsity-acuurccy tradeoff for Tasks 2-4. Similar to Fig. 3, the top row reports the ac- curacy after weight training, and the bottom row contains the results of the sanity checks.
Test Accuracy (%)
70
50
Weight training 300 epoch)
IMP (at 6000 epoch)
As shown in Fig. 4a and Fig. 4b, the results for Task 2 show that (i) MEMER achieves accuracy comparable to IMP as well Renda et al. (IMP with learning rate rewinding) even in the sparse regime, (ii) GEM-MINER has non-trivial accuracy before finetuning (iii) GEM-MINER passes all the sanity checks, and (iv) GEM-MINER outper- forms EP and SR. These results show that GEM-MINER successfully finds rare gems even in the sparse regime for Task 2.
30
GM
10
100
200
300 Epoch
400
500
600
Figure 5: Convergence plot for CIFAR- 10. MobileNet-V2 experiments, where we ap- ply GEM-MINER for 300 epochs and then finetune the sparse model for another 300 epochs, to reach 98.6% sparse model. We include the accuracy of dense weight train- ing. IMP and EP (98.6% sparse model) as references. Note that the comparison with 300 epochs of weight training, and IMP us- ing 20 rounds of iterative pruning, i.c., 300 x 20 = 6000 epochs, to reach 98.6% spar- sity. GEM- GEM-MINER achieves higher accu- racy than IMP despite its 19x shorter run- time to find a sparse subnetwork.
Fig. 4c shows the result for Task 3. Unlike other tasks, GEM-MINER does not reach the post-finetune accuracy of IMP, but GEM-MINER enjoys over an 8% accuracy gap compared with EP and SR. Moreover, the bottom row shows that than the sanity checks above 95% sparsity showing that the subnetwork found by GEM-MINER is unique in this sparse regime.
has over 20% higher accuracy
Fig. 4d shows the result for Task where once again, and outperforms it in the sparse regime.
comparable to IMP throughout
7

---

Table 2:
We compare ProsPr [1] vs GEM-MINER ResNet-20, CIFAR-IO and the random shuflling well as the weight reinit sanity checks. Note that GEM- -MMNER produces a subnetwork that is higher accuracy despite being more sparse. Moreover, ProsPr does not show significant decay in performance after the sanity checks while
does. Therefore, it is likely that ProsPr is merely identifying good layerwise sparsity ratios.
Algorithm
Sparsity
Accuracy after finetume
Accimey after Random shuffling
Accuracy after Weight reinitializaaion
ProsPr 95%
82.67% 83.4%
82.15%
81 81.64%
GEM-MINER
96.28%
78.73%
78.6%
4.2
Comparison to ProsPr
Alizadeh al. [1] recently proposed a pruning at init method called ProsPr which utilizes meta- gradients through the first few steps of optimization to determine which weights to prune, thereby accounting for the "trainability" of the resulting subnetwork. In Table 2 we compare against GEM- MINER on ResNet-20, CIFAR- 10 and also run the (i) Random shuffling and (ii) Weight reinitialization sanity checks from Frankle et al. [11]. We were unable to get ProsPr using their publicly available codebase to generate subnetworks at sparsity above 95% and therefore chose that sparsity. Note that GEM-MINER produces a subnetwork that higher accuracy despite being more sparse. After finetuning for 150 epochs, our subnetwork reaches 83.4% accuracy while the subnetwork found by ProsPr only reaches 82.67% after training for 200 epochs. More importantly, ProsPr does not show significant decay in performance after the random reshuffling or weight reinitialization sanity checks. Therefore, as Frankle et al. [11] remark, is likely that is identifying good layerwise sparsity ratios, rather than a mask specific to the initialized weights.
4.3 Observations on GEM-MINER
Convergence of accuracy and sparsity. Fig. 5 shows how the accuracy of GEM-MINER improves as training progresses, for MobileNet-V2 on CIFAR-I0 at sparsity 98.6%. This shows that GEM- MINER, reaches high accuracy even early in training, and can be finetuned accuracy higher than that of IMP (which requires 19x the runtime than our algorithm). EP remains at candom-guessin throughout as it typically does not work well in the sparse regime.
Weight training
Renda et al. treinit weight)
IMP (with warmunt
BP GM (invert score)
SR
GM
GM Ishutfle mask)
ResNet-20
MobilcNet-V. V2
VGG-16
WideResNet-288
Tost Acc. (96)
90
50
90-
70
70
70-
70
500
50
50
50
30
30
30
10
Sparsity 99.5
07.
30
80
99.5
Sparsity (56)
Sparsity (9)
Sparsity (%)
Figure 6: Performance of different pruning algorithms before finetuning on CIFAR- 10 for benchmark networks. finds subnetworks that already have reasonably high accuracy even before weight training. Note that, while IMP and SR have scarcely better than random guessing at initialization, subnetworks found by GEM-MINER typically perform even better than EP, especially in the sparse regime.
High pre-finetune accuracy. As shown in Fig. 6, GEM-MINER finds subnetworks at initialization that have reasonably high accuracy even before the weight training, e.g., above 90% accuracy for 98.6% sparsity in VGG-16, and 85% accuracy for 98.6% sparsity in MobileNet-V Note that, in contrast, IMP and SR have accuracy scarcely better than random guessing initialization. Clearly, GEM-MINER fulfills its objective in maximizing accuracy before finetuning and therefore finds rare gems - lottery tickets at initialization which already have high accuracy.
Limitations of GEM-MINER. We observed that in the dense regime (50% sparsity, 80% sparsity), GEM-MINER sometimes performs worse than IMP. While we believe that this can be resolved by appropriately tuning the hyperparameters, we chose to focus our attention on the sparse regime. We would also like to remark that GEM-MINER is fairly sensitive to the choice of hyperparameters and for some models, we had to choose different hyperparameters for each sparsity to ensure optimal performance. Though this occurs rarely, we also find that extremely aggressive choice of À can
8

---

Table We construct different variants of EP and compare their performance with GEM-MINER, for ResNet-20, CIFAR-IO, 99.41% sparsity. We establish that having a global score metric and gradually pruning is key to improved performance.
Pruning
Global EP with
Global EP with
Method
EP
Global EP
Gradual Pruning
Gradual Pruning and Regularization MINFR
Pre-finetune acc (%)
19:57
22.22
31.56
19.67
45.30
Post-Einctune acc (%)
24.47
34.42
63.54
63.72
66.15
lead to layer-collapse where one or more layers gets pruned completely. This happens when all the scores p of that layer drop below 0.5.
Layer-wise sparsity. We compare the layer- wise sparsities of different algorithms for ResNet-20 on CIFAR-10 in Fig. 7. Both GEM-
CM
IMP
Smart Ratio
EP
50% Sparsity
96.28% Sparsity
MINER and IMP spend most of their sparsity budget on the first and last layers. SR assigns 70% sparsity to the last layer and the sparsity increases smoothly across the others. EP main- tains the target sparsity ratio at each layer and therefore is always a horizontal line.
Spacts Aereety (%)
100
Num Par am
30
80
20
13
16
20
Layer ID
Layer ID
98. 98.6% Sparsity
99.41% Sparsity
Sparily (99)
100
100
Num Par Param
How does GEM-MINER resolve EP's failings? An open problem from Ramanujan et al. [33] is
80
20K
why most subnetworks found by EP are not fine- tunable. While GEM-MINER is significantly different from EP, it is reasonable to ask which modification allowed it to find lottery tickets without forgoing high accuracy at initialization. Table 3 explores this question for ResNet-20, CIFAR-10 10 at 99.41 % sparsity. Here, we com- pare EP, ants that we construct. (i) (Global EP) is a modification where the bottom-k scores are pruned globally, not layer-wise. This allows the algorithm to trade-off sparsity in one layer for another. (ii) (Gradual pruning) reduces the parameter k gradually as opposed to setting it to the target sparsity from the beginning. (iii) (Regularization); we add an L2 term on the score p of the weights to encour- age sparsity. The results indicate that global praning and gradual praning significantly improve both the pre and post-finetune accuracies EP. Adding regularization does not improve the performance significantly. Finally, adding all three features to EP allows it to achieve 63. 63.72% accuracy, while G reaches 66. % accuracy. is important to note that even with all three features, EP inherently different from GEM- in how it computes the supermask based on the scores. But we conjecture that aggressive, layerwise pruning is the key reason for EP's s failings.
11 Layer er
16
20
6
12
16
20
ID
Layer ID
Figure 7: The layerwise sparsity for ResNet-20 pruned by GEM-MINER, IMP, Smart Ratio, and EP. The dark bar is the layerwise number of parameters. Both GEM- MINER and IMP utilize most the sparsity budget for the first and last layers.
as well as three EP vari-
Ablation study on GEM-MINER. To better understand the relative importance of the different components of the algorithm, we do more thorough ablation study in the same vein the above analysis. We consider the setting of ResNet-20, CIFAR- 10 at a sparsity of 98. 56% and evaluate the performance of (i) GEM-MINER, (ii) GEM-MINER without regularization and (iii) GINEMINER without regularization and without global pruning. As shown in Table 4, GGM-MINER outperforms all of its ablated versions. In fact, GEM-MINER without regularization works extremely poorly, and the final variant is barely above random guessing. Note that when we ablate global pruning, the algorithm chooses the bottom-k A weights in each layer much like EP.
Table 4: Ablation study of GEM-MINER on ResNet-20, CIFAR- 10 at 98.56% sparsity. GM outperforms all of its variants and in fact, when we ablate regularization and global pruning, the performance is barely above random guessing. (GM- Regularization) denotes GM without regularization.
GEM-MINER variant
Accuracy before FT (%) Accuracy after FT (%)
GM
61.23
77.12
GM - Regularization
10.18
27.41
Regularization Global Pruning
11.6

---

Table 5: Comparison of GEM-MINER and its longer version, for ResNet-20, CIFAR-10 at 98.6% sparsity. LONG GM, when given the same number of epochs rivals the performance of Renda et al. [34]
Method
GM (cold)
Long GM (cold)
IMP (warm)
Renda et. (pruning after training)
Number of Epochs
300
3000
3000
3000
Accuracy (%)
77.89
79.50
74.52
80.21
Applying GEM-MINER for longer periods. Recall that FEEM-MNERR uses 19 x fewer epochs than methods like IMP [10] and Learning rate rewinding (Renda et al. [34]), to find subnetwork at 98.6% sparsity which can then be trained to high accuracy. Here, we consider a long version of GEM-MINER to see if it can benefit if it is allowed to run for longer. Table 5 shows the comparison of post-finetune accuracy for GEN-MINER, LONG GEM-MINER, IMP and Renda et al. [34] tested on ResNet-20, CIFAR-10 at 98.5% sparsity. Regular GEM-MINER, applies iterative freezing every 5 epochs to arrive at the target sparsity in 150 epochs. LONG GEM-MINER instead prunes every 150 epochs and therefore reaches the target spansity in 3000 epochs. We find that applying GEM-MINER for longer periods improves the post- post-finetune accuracy in this regime by 1.5%. This shows that given equal number of epochs, FEM-MINER, which prunes at initialization, can close the gap to Learning rate rewinding [34] which is a prume-after-traime method.
5 Conclusion
In this work, we resolve the open problem of pruning at initialization by proposing GEM-MINER, an algorithm that finds gems lottery tickets at initialization that have non-trivial accuracy before finetuning, and accuracy rivaling prune-after-train methods after finetuning. Unlike other methods, subnetworks found by GEM-MINER pass all known sanity checks and baselines. Moreover, we show that GEM-MINER is competitive with IMP despite not using warmup and up to 19x faster.
Acknowledgements
The authors would like to thank Jeff Linderoth for early discussions on viewing pruning as an integer programming problem. This research was supported by ONR Grant No. N00014-21-1-2806 and NSF/Intel Partnership on Machine Learning for Wireless Networking Program under Grant No. CNS-2003129.
References
[1] Alizadeh, M., Tailor, S. A., Zintgraf. M., van Amersfoort, J., Farquhar, S., Lane, N. D., and Gal, Y. Prospect pruning: Finding trainable weights at initialization using meta-gradients. In International Conference on Learning Representations, 2021. 3,8
[2] Bengio, Y., Léonard, N., and Courville, A. Estimating propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv: 300.3343. 2013. 5
[3] Chen, T., Frankle, J., Chang, S., Liu, S., Zhang, Y., Wang, Z., and Carbin, M. The lottery ticket hypothesis for pre-trained bert networks. arXiv preprint 2rXiv:2007.12223, 2020.
[4] Chen, T., Sui, Y., Chen, X., Zhang, A., and Wang, Z. A unified lottery ticket hypothesis for graph neural networks. In International Conference Machine Learning, pp. 1695-1706. PMLR, 2021. 2
[5] Courbariaux. M., Bengio, Y., and David, J.-P. Binaryconnect: Training deep neural networks with binary weights during propagations. Advances in neural information processing systems, pp. 3123-3131, 2015. 4
[6] Diffenderfer, and Kailkhura, B. Multi-prize lottery ticket hypothesis: Finding accurate binary neural networks by pruning randomly weighted network. In International Conference Learning Representations, 2020. 2
[7] Fei-Fei, L., Fergus, R., and Perona, P. Learning generative visual models from few training ex- amples: An incrrenntal bayesian approach tested on 101 object categories. In 2004 conference on computer vision and pattern recognition workshop, pp. 178-178. IEEE, 2004. 6, 13
10

---

[8] Fischer. J. and Burkholz, R. Towards strong pruning for lottery tickets with non-zery biases. arXiv preprint arXiv:2110.11150, 2021. 13
[9] Frankle, and Carbin, M. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint 1r0ivv1803.088
2018. 2, 2,2,3,3 3,5
[10] Frankle, J., Dziugaite, G. K., Roy, D., and Carbin, M. Linear mode connectivity and the lottery ticket hypothesis. International Conference on Machine Learning, pp. 3259-3269. PMLR, 2020. 1, 2, 6, 10, 14, 20
[11] Frankle, J., Dziugaite, G. K., Roy, D. M., and Carbin, M. Pruning neural networks at initializa- tion: Why are we missing the mark? arXiv preprint (.XXx:2009.0887000 2020. 2, 3, 4, 6, 7, 14, 15, 19
[12] Gale, T., Elsen, E., and Hooker, S. The state of sparsity in deep neural networks. arXiv preprint arXiv: 09574, 2019. 3, 5
[13] Girish, S., Maiya, S. R., Gupta, K., Chen, H., Davis, L. S., and Shrivastava, A. The lottery ticket hypothesis for object recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 762-771, 2021. 2
[14] Han, S., Pool, J., Tran, J., and Dally, W. Learning both weights and connections for efficient neural network. In Advances in neural information processing systems, pp. 1135-1143, 2015. 1
[15] Han, S., Mao, H., and Dally, W. J. Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding. arXiv:1510.00144 [es], February 2016. URL http: / arrxiv.i org/abs///a///eooo 0btp//110.0019. 00149.
[16] Hassibi, B. and Stork, D. G. Second order derivatives for network pruning: Optimal Brain Surgeon. In Hanson, J., Cowan, J. D., and Giles, C. L. (eds.), Advances in Neural Information Processing Systems 5, pp. 164-171. Borgan-Kaufman 1993.
[17] He, K., Zhang, X., Ren, S., and Sun, J. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015. 14
[18] He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778,
2016. 14
[19] Hubara, I., Courbariaux, M., Soudry, D., EI- Yaniv, R., and Bengio, Y. Binarized neural networks
In Advances in neural information processing systems, pp. 4107-4115, 2016.
[20] Hubara, I., Courbariaux, M., Soudry, D., Yaniv, R., and Bengio, Y. Quantized neural networks: Training neural networks with low precision weights and activations. The Journal of Machine Learning Research, (8(():6869-68)) 6898, 2017.
[21] Kingma, D. P. and Ba, J. Adam: method for stochastic optimization. arXiv preprint 11Xiv:1412.6980, 2014. 15
[22] Krizhevsky, A. et al. Learning multiple layers of features from tiny images. 2009. 13
[23] LeCun, Y., Denker, J. S., and Solla, S. A. Optimal Brain Damage. In Touretzky, D. S. (ed.), Advances Neural Information Processing Systems 2, pp. 598-605. Morgan-K Kaufmann, 1990. URL. http: tttetp://papeee papers. nips. cc/ p2per/ borl-brannnn damage pdf.
[24] Lee, N., Ajanthan, T., and Torr, P. H. Snip: Single-shot network pruning based on connection sensitivity. arXiv preprint arXiv:
2018. 2,
[25] Li, A., Sun, J., Wang, B., Duan, L., Li, S., Chen, Y., and Li, H. Lotteryfl: Personalized and communication-ettiiieei federated learning with lottery ticket hypothesis on non-iid datasets. arXiv preprint arXiv:2008.03:: 033771 2020. 2
[26] Lubana, S. and Dick, R. gradient flow framework for analyzing network pruning. In International Conference Learning Representations, 2020. 3
11

---

[27] Ma, X. Yuan, G., Shen, X., Chen, T., Chen, X.. Chen, X., Liu, N., Qin, M., Liu, S., Wang. Z.. et al. Sanity checks for lottery tickets: Does your winning ticket really win the jackpot? Advances in Neural Information Processing Systems, 34, 2021. 3
[28] Malach, E., Yehudai, G., Shalev-Schwartz, S., and Shamir, O. Proving the lottery ticket hypothesis: Pruning is all you need. In International Conference on Machine Learning, pP-
6682 6691. PMLR, 2020. 2
[29] Mozer, M. C. and Smolensky, P. Skeletonization: A Technique for Trimming the Fat from Network via Relevance Assessment. In Touretzky, D. S. (ed.), Advances in Neural Information Processing Systems pp. 107-115. Morgan-Kaufmann 1989.
[30] Orseau, L., Hutter, M., and Rivasplata, O. Logarithmic pruning all you need. Advances in Neural Information Processing Systems, 33, 2020. 2
[31] Patil, S. M. and Dovrolis, C. Phew: Constructing sparse networks that learn fast and generalize well without training data, In International Conference on Machine Learning, pp. 8432-8442.
PMLR, 2021. 3
[32] Pensia, A., Rajput, S., Nagle, A., Vishwakarma, H., and Papailiopoulos, D. Optimal lottery tickets via subsetsum: Logarithmic over- paramettccriinnnonnnn is sufficient. Advances in neural information processing systems, 2020. 2
[33] Ramanujan, V., Wortsman, M., Kembhavi, A., Farhadi, A., and Rastegari, M. What's hidden in a randomly weighted neural network? In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11893-11902, 2020. 4, 5, 6, 9, 13, 20
[34] Renda, A., Frankle, J., and Carbin, M. Comparing rewinding and fine-tuning in neural network pruning. arXiv preprini 2rXiv:2003.023389 2020. 3, 6, 10
[35] Sandler, M., Howard, A., Zhu, M., Zhmoginov, A., and Chen, L.-C. Mobilenetv2: Inverted residuals and linear bottlenecks. Proceedings of the IEEE conference on computer vision and pattemn recognition. pp. 4510-4520, 2018. 14
[36] Sanh, V., Wolf, T., and Rush, A. Movement pruning: Adaptive sparsity by fine-tuning, Advances in Neural Information Processing Systems, 0920378-20383 2020. 4
[37] Savarese. P., Silva, H., and Maire, M. Winning the lottery with continuous sparsification.
Advances in Neural Information Processing Systems, 33:1 1380-11390, 2020. 2
[38] Simons, and Lee, D.-J. review of binarized neural networks. Electronics, 8(6):661, 2019.
[39] Simonyan, K. and Zisserman, A. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1509. 2014. 14
[40] Sreenivasan, K., Rajput, S., Sohn, J.-y,, and Papailiopoulos, D. Finding everything within random binary networks. arXiv preprint arx.v221 2021.
[41] Su, J., Chen, Y., Cai, T., Wu, T. Gao, R., Wang, I.,, and Lee, J. D. Sanity-checking pruning methods: Random tickets can win the jackpot. arXiv preprint arXiv:2009.11094 2020. 1, 2, 6, 18, 19
[42] Tanaka, H., Kunin, D., Yamins, D. L., and Ganguli, S. Pruning neural networks without any data by iteratively conserving synaptic flow. Advances in Neural Information Processing Systems, 33, 2020. 2,
[43] Wang, C., Zhang, G., and Grosse, R. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2019. 2,
[44] Zagoruyko, S. and Komodakis, N. Wide residual networks. arXiv preprint 1rXiv:1605.071 2016. 14
[45] Zhu, M. and Gupta, S. To prune, or not to prune: exploring the efficacy of pruning for model compression. arXiv preprint arXiv:1710.01878, 2017. 1,
12


Reviews:
[{"review_id": "wVJo0xkfU5p", "reviewer": "Reviewer_Loxt", "summary": "The paper proposes GEM-MINER to find lottery tickets at initialization. The found subnetworks are trainable and can achieve comparable or better performance compared to existing approaches (e.g., IMP), and requires much less time (19x faster compared to IMP). The approach can pass the sanity checks proposed by prior work. The experiments with different datasets, different model architectures, and different sparisities show the effectiveness of the proposed approach. The paper claims it resolves the open problem of hunting for subnetworks at initialization trainable to SOTA accuracy.", "questions": "- Can GEM-MINER be applied to NLP tasks?", "limitations": "The limitations have been well discussed in the paper in an explicit section (e.g., it may require careful hyper-parameters tuning). I don’t see other major limitations of the approach.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well-written and very easy to understand.\n- The paper conducts extensive and solid experiments to study the effectiveness of the proposed method. The results are strong and exciting, and also provide insightful analysis (e.g., why EP failed).\n- The approach is simple and effective. I believe that the paper can facilitate more research in this field.\n\nWeaknesses:\nI don’t see a major concern with this paper. \n\nMinor: why is sparisity defined as the ratio of non-zero weights instead of zero weights? (Based on the current definition, 95% sparsity actually means a very dense model!)\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_LqYcZy8Ta", "reviewer": "Reviewer_YCDn", "summary": "This paper studies the problem of searching trainable subnetworks at initialization (winning tickets). The authors propose a method called GEM-MINER, which maximises the accuracy of subnetworks before weight training. GEM-MINER can discover subnetworks comparable to IMP with warmup (a widely-used method to find winning ticket subnetworks) while being 19 $\\times$ faster. GEM-MINER outperforms the Edge-popup, which is another method that also optimizes the subnetwork structure before weight training. The subnetworks found by GEM-MINER also pass the \"sanity check\", outperforming random sparse subnetworks.", "questions": "* Why not compare with SNIP, GraSP and SynFlow?\n* Could you remark on how to resolve the limitations you discussed in line 311-321?", "limitations": "Please refer to the Strengths And Weaknesses and Questions.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n* Searching for subnetworks at initialization with better after-training performance is an important problem in the lottery ticket hypothesis (LTH). This paper proposes a new method to tackle this problem and achieves promising results.\n* The main reasons (i.e., global pruning and gradual pruning) for the effectiveness of the proposed method are well explained in the ablation study (Tab.3), which can be used as default setups in follow-up works.\n* Extensive experiments are conducted to demonstrate the effectiveness of the proposal, covering multiple tasks and backbone models.\n* The paper is generally well-written and easy to follow.\n\n### Weaknesses\n1. Although the proposal is a new method to search trainable subnetworks at initialization, its core ideas (global pruning and gradual pruning) have already been studied in the literature on model compression [1]. This undermines the technical novelty of this paper.\n[1] Movement Pruning: Adaptive Sparsity by Fine-Tuning. In NeurIPS 2020.\n\n2. The effectiveness of global pruning and gradual pruning is a useful finding. However, it is unclear how these two factors contribute to identifying more trainable subnetworks at initialization. Further analysis is required.\n\n3.  Although extensive experiments are conducted, the empirical studies can still be improved in terms of comprehensiveness. For example:\n* Comparing with other \"pruning at initialization\" methods (e.g., SNIP, GraSP and SynFlow).\n* The paragraph \"Convergence of accuracy and sparsity\" can benefit from adding results of Edge-popup and SNIP, etc.\n\n4. Some arguments made in this paper are questionable. For example, \"EP subnetworks are not conducive to further fine-tuning\" does not always hold. At 5% sparsity, the accuracy of EP subnetworks can be improved from 70.69 to 84.34, according to Fig.2.\n\n5. Limitations of the GEM-MINER are well discussed. However, the authors did not provide any ways of solutions.\n\n### Typos\n* In the upper line of Fig.1 (the pipeline of IMP), it seems that the \"0.5% sparse Subnetwork at Warm Initialization\" should have the same color as the \"Partially trained dense network\" for the same weights.\n* CIFAR-100 is not mentioned in the paragraph \"Tasks\" (line 226-230), while appears in Fig.4.\n* The caption of Fig.4 mentions ImageNet, while only TinyImageNet can be found in the titles of 2nd and 3rd columns.\n* Line 272 mentions Fig.4c, which cannot be found in Fig.4.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZVASW05wofP", "reviewer": "Reviewer_BBr3", "summary": "This paper proposes an algorithm that finds sparse subnetworks at initialization, trainable to accuracy comparable or better than IMP with warm-up.", "questions": "If I understand the algorithm correctly, about half of the weights would be masked at initialization as score vector p is initialized randomly, which seems a little bit weird to me. According to Algorithm 1, only effective weights receive gradients, so if a weight is masked, it will be masked forever. So, could the authors explain the design behind this or correct my misunderstanding?", "limitations": "The authors address the limitations adequately.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nThis paper proposes an algorithm that finds winning tickets at initialization and validates the algorithm on several tasks.\nThe experiments are solid.\nWeakness:\nThe novelty is limited. \nThe proposed method is a combination of different techniques.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Dn7T9JUS_Bd", "reviewer": "Reviewer_nnnE", "summary": "This work aims to find lottery tickets at initialization efficiently by a proposed Gem-Miner. \nPrevious studies either find bad tickets at initialization (ineffectiveness) or find good tickets after initialization (inefficiency). \nTo tackle the open problem, the Gem-Miner is proposed to discover rare gems, which can find good enough tickets at initialization even before weight training. \nThe Gem-Miner can be essentially viewed as a bag of tricks for finding tickets. \nExperimental results show that rare gems perform far better than baselines in terms of both performance metrics and sanity checks. \nIn addition, rare gems hold the advantage of a faster identification process.\n", "questions": "Q1:\nThe authors state that \"exactly the same number of epochs\" yet \"faster than IMP\" at the same time in Line 61, which seems ambiguous to me. Would \"IMP\" consume longer training time for an epoch?\nIf I understand correctly, the \"IMP\" in Table 1 indicates \"IMP with warmup\" instead since it passes sanity checks as stated in Line 40. Then it can be acknowledged that Gem-Miner is faster than \"IMP with warmup\". However, this would be controversial to the above statement.\n\nQ2:\n\"after E epochs of weight training\" in Line 232 indicates that a pre-training stage is required, so I wonder whether other pruning methods require a pre-training stage if the pre-training is required by Edge-Popup. Would this lead to an unfair comparison?", "limitations": "Hyper-parameters are sensitive in Gem-Miner but are not listed in this paper.\n\n", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n1. The open problem is interesting and is somewhat solved by the proposed method.\n2. Appealing experiments results in terms of both effectiveness and efficiency.\n\nCons:\n1. There are several presentation flaws as listed in the Questions below.\n2. This work focuses on a specific pruning method (i.e., Edge-Popup), and I would glad to see further results of arming Gem-Miner to other pruning methods. \n3. This work can be viewed as a bag of tricks for finding good tickets at initialization. However, ablation studies are not thoroughly conducted for a better understanding. There is a related section describing how Gem-Miner resolves Edge-Popups failings by adding components to Edge-Popup, yet without adequate connections between these components and tricks introduced by Gem-Miner.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept