Progressive Skeletonization: Trimming more fat from a network at initialization
Authors: Pau de Jorge
Amartya Sanyal
Harkirat Behl
Philip Torr
Grégory Rogez
Puneet K. Dokania
Venue: ICLR 2021 Poster (2021)
Keywords: Pruning
Pruning at initialization
Sparsity

Abstract: Recent studies have shown that skeletonization (pruning parameters) of networks at initialization provides all the practical benefits of sparsity both at inference and training time, while only marginally degrading their performance. However, we observe that beyond a certain level of sparsity (approx 95%), these approaches fail to preserve the network performance, and to our surprise, in many cases perform even worse than trivial random pruning. To this end, we propose an objective to find a skeletonized network with maximum foresight connection sensitivity (FORCE) whereby the trainability, in terms of connection sensitivity, of a pruned network is taken into consideration. We then propose two approximate procedures to maximize our objective (1) Iterative SNIP: allows parameters that were unimportant at earlier stages of skeletonization to become important at later stages; and (2) FORCE: iterative process that allows exploration by allowing already pruned parameters to resurrect at later stages of skeletonization. Empirical analysis on a large suite of experiments show that our approach, while providing at least as good performance as other recent approaches on moderate pruning levels, provide remarkably improved performance on high pruning levels (could remove up to 99.5% parameters while keeping the networks trainable).

Published as a conference paper at ICLR 2021
PROGRESSIVE SKELETONIZATION: TRIMMING MORE FAT FROM A NETWORK AT INITIALIZATION
Pau de Jorge* University of Oxford NAVER LABS Europet
Amartya Sanyal University of Oxford & The Alan Turing Institute, London, UK
Harkirat S. Behl University of Oxford
Philip H. S. Torr University of Oxford
Grégory Rogez NAVER LABS Europe
Puneet K. Dokania University of Oxford & Five Al Limited
ABSTRACT
Recent studies have shown that skeletonization (pruning parameters) of networks at initialization provides all the practical benefits of sparsity both at inference and training time, while only marginally degrading their performance. However, we observe that beyond certain level of sparsity (approx 95%), these approaches fail to preserve the network performance, and to our surprise, in many cases perform even worse than trivial random pruning. To this end, we propose objective to find a skeletonized network with maximum foresight connection sensitiviry (FORCE) whereby the trainability, in terms of connection sensitivity, of a pruned network is taken into consideration. We then propose two approximate procedures maximize our objective (1) Iterative SNIP: allows parameters that were unimportant at earlier stages of skeletonization to become important at later stages; and (2) FORCE: iterative process that allows exploration by allowing already pruned parameters to resurrect at later stages of skeletonization. Empirical analysis on large suite of experiments show that our approach, while providing at least as good performance as other recent approaches on moderate pruning levels, provide remarkably improved performance on higher pruning levels (could remove up to 99.5% parameters while keeping the networks trainable).
INTRODUCTION
The majority of pruning algorithms for Deep Neural Networks require training dense models and often fine-tuning sparse sub-networks in order to obtain their pruned counterparts. In |Frankle & Carbin (2019), the authors provide empirical evidence support the hypothesis that there exist sparse sub-networks that can be trained from scratch to achieve similar performance as the dense ones. However, their method find such sub-networks requires training the full-sized model and intermediate sub-netue sub-networks, making the process much more expensive.
Recently, Lee al. (2019) presented SNIP. Building upon almost a three decades old saliency criterion for pruning trained models (Mozer& & Smolensky 1989), they are able to predict, at initialization, the importance each weight will have later in training. Pruning at initialization methods are much cheaper than conventional pruning methods. Moreover, while traditional pruning methods can help accelerate inference tasks, pruning at initialization may go one step further and provide the same benefits train time [Esen et al. (2020).
Wang al. (2020) (GRASP) noted that after applying the pruning mask, gradients are modified due to non-trivial interactions between weights. Thus, maximizing SNIP criterion before pruning might be sub-optimal. They present an approximation to maximize the gradient norm after pruning, where they treat pruning perturbation the weight matrix and use the first order Taylor's approximation. While they show improved performance, their approximation involves computing a Hessian-vector product which is expensive both in terms of memory and computation.
Cooresponnence to pau8 robots. Ox. ac. uk
www www.peur..e.... naver aaa.. com

---

Published as a conference paper at ICLR 2021
0.9
CIFARIO
0..8
0.7
0.6
FORCE (Ours)
0.5
Iter SNIP (Qurs)
0.4
0.3
GRASP
2.2
SNIP
0.1
Derde Baseline
0.0
.01%
.55% 0.1%
0.5%
1%
5% 10%
Percentage of remaining weights (log scale)
Figure I:
Test accuracies on CIFAR-10 (ResNer50) for different pruning methods. Each point is the average over runs of prune-train-test. The shaded areas denote the standard deviation of the runs (too small be visible in some cases). Random corresponds removing connections uniformly.
We argue that both SNIP and GRASP approximations of the gradients after pruning do not hold for high pruning levels, where large portion of the weights are removed at once. In this work, while we rely on the saliency criteria introduced by Mozer& & Smolensky (1989), we optimize what this saliency would be after pruning, rather than before. Hence, we name our criteria Foresight Connection sEnsitivity (FORCE). We introduce two approximate procedures to progressively optimize our objective. The first, which turns out to be equivalent to applying SNIP iteratively, removes a small fraction of weights at each step and re-computes the gradients after each pruning round. This allows to take into account the intricate interactions between weights, re-adjusting the importance of connections at each step. The second procedure, which we name FORCE, is also iterative in nature, but contrary to the first, it allows pruned parameters to resurrect. Hence, it supports exploration, which otherwise is not possible in the case of iterative SNIP. Moreover, one-shot SNIP can be viewed particular case of using only one iteration. Empirically, a sharp drop in performance when targeting higher pruning levels. Surprisingly, they perform even worse than random pruning as can be seen in Fig In contrast, our proposed pruning procedures prove to be significantly more robust on a wide range of pruning levels.
find that both SNIP and GRASP have
2 RELATED WORK
Pruning trained models Most of the pruning works follow the train prune fine-tune cycle
(Mozer & Smolensky, 1989 LeCun et al.) ( [Hassibi et al., 1993) Han al.) 2015 Molchanov
et al. 2017; et al. 2016). which requires training the dense network until convergence, followed by multiple iterations of pruning and fine-tuning until a target sparsity is reached. Particularly, Molchanov et al. (2017) present criterion very similar to Mozer & Smolensky (1989) and therefore similar to Lee et al. (2019) and our FORCE, but they focus on pruning whole neurons, and involve training rounds while pruning. Frankle & Carbin (2119) Frankle et al. (2020) showed that it was possible to find sparse sub-networks that, when trained from scratch or an early training iteration, were able to match
surpass the performance of their dense counterparts. Nevertheless, to find them they use costly procedure based on Han et al. (2015). All these methods rely on having a trained network, thus, they are applicable before training. In contrast, a trainable sub-network with randomly initialized weights. Making the overall pruning cost much cheaper and presenting an opportunity to leverage the sparsity during training as well.
algorithm is able find
Induce sparsity during training Another popular approach has been to induce sparsity during training. This can be achieved by modifying the loss function consider sparsity as part of the optimization (Chauvin, 1989: Carreira-Perpihãn & Idelbayev 2018 Louizos et al. 2018) or by dynamically pruning during training (Bellee et 22.11 Mocanu
al. 2018 Mostafa & Wang 2019 Dai et al.. 2019 Dettmers & Zettlemoyer] 2020 Lin et al. 2020 Kusupati et al.) 2020 Evei et al. 2019). These methods are usually cheaper than pruning after training, but they still need to train the network to select the final sparse sub-network. We focus on finding sparse sub-networks before any weight update, which is not directly comparable.
Pruning at initialization These methods present a significant leap with respect to other pruning methods. While traditional pruning mechanisms focused on bringing speed-up and memory reduction inference time, pruning at initialization methods bring the same gains both at training and inference time. Moreover, they can be seen as a form of Neural Architecture Search (Zoph & Le 2016) to find more efficient network topologies. Thus, they have both theoretical and practical interest.
2

---

Published as a conference paper at ICLR 2021
Lee al. (2019) presented SNIP, a method to estimate, at initialization, the importance that each weight could have later during training. SNIP analyses the effect of each weight on the loss function when perturbed at initialization. In Lee et al. (2020), the authors studied pruning at initialization from a signal propagation perspective, focusing on the initialization scheme. Recently, Wang et al. (2020) proposed GRASP, different method based on the gradient norm after pruning and showed significant improvement for higher levels of sparsity. However, neither SNIP nor GRASP perform sufficiently well when larger compressions and speed-ups are required and a larger fraction of the weights need to be pruned. In this paper, we analyse the approximations made by SNIP and GRASP, and present a more suitable solution to maximize the saliency after pruning.
PROBLEM FORMULATION: PRUNING AT INITIALIZATION
Given a dataset D = ((x,,y:) K-1 the training of a neural network f parameterized by A E Rm can be written minimizing the following empirical risk:
1 Σ
arg min
[(f(xx;)))) s.t. E
(1)
0
where L and C denote the loss function and the constraint set, respectively. Unconstrained (standard) training corresponds to C RTm. Assuming we have access to the gradients (batch-wiss wise) of the empirical risk, an optimization algorithm (e.g. SGD) is generally used to optimize the above objective, that, during the optimization process, produces a sequence of iterates {0:) where On and Or denote the initial and the final (optimal) parameters, respectively. Given target sparsity level of < m, the general parameter pruning problem involves C with a constraint 1r S k. i.e. the final optimal iterate must have maximum of k non-zero elements. Note that there is such constraint with the intermediate iterates.
Pruning initialization, the main focus of this work, adds further restrictions to the above mentioned formulation by constraining all the iterates to lie in a fixed subspace of C. Precisely, the constraints are to find an initialization Ou such that ||ollo I k and the intermediate iterates are 0, C C Vi {1...., T), where Č is the subspace of IR m spanned by the natural basis vectors (ej)jeaupp(0))) Here, supp(0o) denotes the support of to. i.e., the set of indices with non-zero entries. The first condition defines the sub-network at initialization with & parameters, and the second fixes its topology throughout the training process. Since there are (*²) such possible sub-spaces, exhaustive search to find the optimal sub-space optimize ① IS impractical it would require training (*) neural networks. Below we discuss two recent approaches that circumvent this problem by maximizing a designed data-dependent objective function. These objectives are tailored to preserve some relationships between the parameters, the loss, and the dataset, that might be sufficient to obtain reliable 0g. For the ease of notation, we will use denote the dense initialization.
SNIP Lee et al. (2019) present method based on the saliency criterion from Mozer & Smolensky (1899). They add a key insight and show this criteria works surprisingly well to predict, at initializa- tion, the importance each connection will have during training. The idea is to preserve the parameters that will have maximum impact on the loss when perturbed. Let e E {0, 1] 13m be a binary vector, and C the Hadamard product. Then, the connection sensitivity in SNIP is computed as:
g ac(0 O dc
AC(
2 0.
(2)
00
c=1
Once g(0) obtained, the parameters corresponding to the top-k values of [g()),] are then kept. Intuitively, SNIP favors those weights that are far from the origin and provide high gradients (irrespective of the direction). We note that SNIP objective can be written as the following problem:
max S(0,c)
10, VC())) s.t. (0,1)" ||e||o k. (Esupp(c
Σ
It is trivial to note that the optimal solution to the above problem can be obtained by selecting the indices corresponding to the top-k values of (0, V ((O))).
In practice, will he done in this work as well, subset of given dense initialization is found using some saliency criterion (will be discussed soon), however, note that our problem statement is more general than that.
3

---

Published as a conference paper at ICLR 2021
GRASP Wang al. (020) note that the SNIP saliency is measuring the connection sensitivity of the weights before pruning, however, it is likely to change after pruning. Moreover, they argue that, at initialization, it is more important to preserve the gradient signal than the loss itself. They propose to use as saliency the gradient norm of the loss ( = V C TM V (.)), but measured after pruning. To maximize it. Wann et al. (2020) adopt the same approximation introduced in [eCun et al. (1990)
and treat pruning as perturbation on the initial weights. Their method is equivalent to solving:
max G(O,c)
Σ
0s Hggh
s.t. Ce E 10, ||ello
k.
(4)
==))=
Where H and g denote the Hessian and the gradient of the loss respectively.
4 FORESIGHT CONNECTION SENSITIVITY
Since removing connections of neural network will have significant impact on its forward and backward signals, we are interested in obtaining a pruned network that is easy to train. We use connection sensitivity of the loss function as a proxy for the so-called trainability of a network. To this end, we first define connection sensitivity after pruning which we name Foresight Connection sEnsitivity (FORCE), and then propose two procedures to optimize it in order to obtain the desired pruned network. Let 0- O @ e denotes the pruned parameters once a binary mask with ||cllo k S m is applied. The FORCE at 0 for given mask is then obtained as:
Oc(0)
OC(0)
00
OC(0) 00
g(0) = Ōc
00
Dc c=
=
C O.
(5)
c=
The last equality is obtained by rewriting 0 as diag(O)c, where diag (0) is a diagonal matrix with 0 as its elements, and then differentiating w.r.t. c. Note, when m, the sub-network 0 is obtained by removing connections corresponding to all the weights for which the binary variable is zero. Therefore, only the weights corresponding to the indices for which c(i) contribute in equation (5), all other weights do not participate in forward and backward propagation and are to be ignored. We now discuss the crucial differences between our formulation ( SNIP 2 and GRASP
When è 1, the formulation is exactly the same the connection sensitivity used in SNIP. However, = 1 is too restrictive in the sense that it assumes that all the parameters are active in the network and they removed one by one with replacement, therefore, it fails to capture the impact of removing a group of parameters.
Our formulation uses weights and gradients corresponding to 0 thus, compared to SNIP, provides a better indication of the training dynamics of the pruned network. However, GRASP formulation is based on the assumption that pruning is a small perturbation on the Gradient Norm which, also shown experimentally, is not always a reliable assumption.
When ||é||, < |1 i.e., extreme pruning, the gradients before and after pruning will have very different values as ||0 @ éll, < ||0||g- making SNIP and GRASP unreliable (empirically we find SNIP and GRASP fail in the case of high sparsity).
FORCE saliency Note FORCE (5) is defined for a given sub-network which is unknown a priori, as objective itself is to find the sub-network with maximum connection sensitivity. Similar to the reformulation SNIP in (3), the objective to find such neb-network corresponding to the foresight connection sensitivity be written as:
max S(0,e) = Σ (Eaupp(c)
VL 2 c)al
s.t. e E (0, 1"", ||e||o =
(6)
c
Here V c), represents the i-th index of (C( As opposed 33 finding the optimal solution
80
of 66) is non trivial as it requires computing the gradients all possible (M) sub-networks in order
to find the with maximum sensitivity. To this end, present two approximate solutions to the above problem that primarily involve (i) progressively increasing the degree of pruning, and (ii)
solving approximation of (6) at each stage of pruning.
Progressive Pruning (Iterative SNIP) Let & be the number of parameters to be kept after pruning. Let us assume that we know a schedule (will be discussed later) to divide A into set of natural
4

---

Published as a conference paper at ICLR 2021
numbers {Kr Y such that ky > het1 and by = k. Now, given the mask c, corresponding to ke.
pruning from ky to ki41 can be formulated using the connection sensitivity (5) as:
Ct+1 = arg max S(0,c) s.t. c E {0,1) | = hi+1, c c =
where 0 = OC,. The additional constraint coc, ensures that no parameter that had been pruned earlier activated again. Assuming that the pruning schedule ensures a smooth transition from one
topology to another (lcc llo ||c++1 (lo) such that the gradient approximation aC10)
BC
C++1
is valid, 7 can be approximated as solving 3 at O. Thus. for a given schedule over k. our first approximate solution to (6) involves solving (3) iteratively. This allows re-assessing the importance of connections after changing the sub-network. For schedule with T = 1, we recover SNIP where crude gradient approximation between the dense network Co = 1 and the final mask C is being used. This approach of ours turns out to be algorithmically similar concurrent work (Verdenius et al., 2020). However, our motivation comes from a novel objective function (5) which also gives place to second approach (FORCE). Tanaka et al. (2020) also concurrently study the effect of iterative pruning and report, similar to our findings, pruning progressively is needed for high sparsities.
Progressive Sparsification (FORCE) The constraint e @ C c. in 77 (Iterative SNIP) might be restrictive in the sense that while re-assessing the importance of unpruned parameters, it does not allow previously pruned parameters to resurrect (even if they could become important). This hinders exploration which can be unfavourable in finding suitable sub-network. Here we remove this constraint, meaning, the weights for which c(i) 0 are not removed from the network, rather they are assigned value of zero. Therefore, while not contributing to the forward signal, they might have a non-zero gradient. This relaxation modifies the saliency in (5) whereby the gradient is now computed at a sparsified network instead of pruned network. Similar to the above approach, we sparsify the network progressively and once the desired sparsity reached, all connections with c(i) 0 are praned. Note, the step of removing zero weights is valid if removing such connections does not adversely impact the gradient flow of the unpruned parameters. We, in fact, found it to be true in experiments shown in Fig (Appendix). However, this assumption might not hold always.
An overview of Iterative SNIP and FORCE is presented in Algorithm
Sparsity schedule Both the above discussed iterative procedures approximately optimize 5 how- ever, they depend on a sparsity/pruning schedule favouring small steps to be able to reliably apply the mentioned gradient approximation. One such valid schedule would be where the portion of newly removed weights with respect to the remaining weights is small. We find a simple exponential decay schedule, defined below, to work very well on all experiments:
Exp mode: h = exp log & + (1 - a) log m), T
(8)
In section 5.3 we empirically show that these methods are very robust to the hyperparameter T.
Some theoretical insights When pruning weights gradually, we are looking for the best possible sub-network in a neighbourhood defined by the previous mask and the amount of weights removed at that step. The problem being non-convex and non-smooth makes challenging to prove if the mask
Algorithm 1 FORCE/Iter SNIP algorithms to find pruning mask
1: Inputs: Training set D. final sparsity k. number of steps T, weights Gu E R".
2: Obtain 1-1 using the chosen schedule (refer to Eq
3: Define intial mask cp = 1
4: for i. 0, .,....... T do
5: Sample mini-batch {2.)= from D
6: Define 0 O C, (as sparsified (FORCE) vs pruned (Iter SNIP) network)
7: Compute (θ) (refer to Eq (5))
8: I= (i....,, (k.m.) are top-ke+1 values of [g:l
9: Build c by setting to 0 all indices not included in I.
10:
end for
Return: cr.
5

---

Published as a conference paper at ICLR 2021
obtained by our method is globally optimal. However, in Appendix D we prove that each intermediate mask obtained with Iterative SNIP is indeed an approximate local minima, where the degree of sub-optimality increases with the pruning step size. This gives some validation on why SNIP fails on higher sparsity. We can not provide the same guarantees for FORCE (there is no obvious link between the step size and the distance between masks), nevertheless, we empirically observe that FORCE is quite robust and more often than not improves over the performance of Iterative SNIP, which is not able recover weights once pruned. We present further analysis in Appendix C.4
5
EXPERIMENTS
In the following we evaluate the efficacy of our approaches accross different architectures and datasets. Training settings, architecture descriptions, and implementation details are provided in Appendix [
5.1 RESULTS ON CIFAR-10
Fig 2 compares the accuracy of the described iterative approaches with both SNIP and GRASP. We also report the performance of dense and random pruning baseline. Both SNIP and GRASP consider a single batch to approximate the saliencies, while we employ a different batch of data at each stage of our gradual skeletonization process. For fair comparison, and understand how the number of batches impacts performance, we also run these methods averaging the saliencies over T batches, where T the number of iterations. SNIP-MB and GRASP-MB respectively refer to these multi-batch (MB) counterparts. In these experiments, we use T = 300. We study the syper--arameter robustness regarding T later in section 5.3
0.9
0.8
FORCE
50.7
GRASP
0.6
0.5
SNIMMB
50.5
SNP
0.4
Random
0.4
Random
GRASP
203
CRASP
0.2
SNIP
0.2
SXP
0.1
Demue Beswirw
0.1
Derive Beseiin
01%
.05%% 0.1%
0.5% 1%
10%
07%.1%
0.5% 1%
5%
Percentage of remaining weights (log scale)
Percentage of remaining weights (log scale!
(a) Resnet50
(b) VGG19
Figure 2: Test accuracies on CIFAR-10 10 for different pruning methods. With increased number of batches (-MB) one-shot methods are more robust at higher sparsity levels, but our gradual pruning approaches can go even further. Moreover, FORCE consistently reaches higher accuracy than other methods across most sparsity levels. Each point is an average of 2 runs of prune-train-ter train-test. The shaded areas denote the standard deviation of the runs (too small to be visible in some cases). Note that in (b), GRASP and GRASP-MB overlap.
We observe that for moderate sparsity levels, one batch sufficient for both SNIP and GRASP as reported in Lee et al. (2019); Wang et al. (202)). However, as we increase the level of sparsity, the performance of SNIP and GRASP degrades dramatically. For example, at 99.0% sparsity, SNIP drops down to 10% accuracy for both ResNet50 and VGGI9, which is equivalent to random guessing as there are 10 classes. Note, in the case of randomly pruned networks, accuracy is nearly 75% and 82% for ResNet50 and VGG19, respectively, which is significantly better than the performance of SNIP. However, to our surprise, just using multiple batches to compute the connection sensitivity used in SNIP improves it from 10% almost 90%. This clearly indicates that better approximation of the connection sensitivity is necessary for good performance in the case of high sparsity regime. Similar trends, although not this extreme, can be observed in the case of GRASP well. On the other hand, gradual pruning approaches are much more robust in terms of sparsity for example, in the case of 99.9% pruning. while one-shot approaches perform as good as a random classifier (nearly 10% accuracy), both FORCE and Iterative SNIP obtain more than 80% accuracy. While the accuracies obtained at higher sparsities might have degraded too much for some use cases, we argue this an encouraging result, as no approach before has pruned network at initialization to such extremes while keeping the network trainable and these results might encourage the community to improve the performance further. Finally, gradual pruning methods consistently improve over other methods at moderate sparsity levels (refer to FigS)) this motivates the use of FORCE or Iterative SNIP instead of other methods by default any sparsity regime. Moreover, the additional cost of using iterative

---

Published as a conference paper at ICLR 2021
pruning instead of ENIP-MB is negligible compared to the cost of training and is significantly cheaper than GRASP-MB, further discussed in section 5.3
0.7
CIFAR100
8 0.6
0.5
0.5
0.4
FORCE
0.4
FORCE
SNJP
GRASIMAS
0.3
0.2
Beselne
0.1
Denve Baselne
0.0 0.5%
1%
5%
10%
0.0
0.5%
1%
5%
10%
Percentage remalining weights (log scale)
Percentage of remaining weights scale)
(a) CIFAR 100 Resnet50
(b) CIFAR 100 VGG19
Tiny (eggen
0.6
0.5
0.5
0.4
Iter SNIP
0.44
Iter SNIP
FORCE
0.3
GRASP-MB
GRASP-MB
0.2
0.1
Dense Baseline
Random
0.1
Random
Baseline
0.0 0.5%
1%
5%
10%
0.0
0.5%
1%
5%
10%
Percentage of remaining weights (log scale)
Percentage of remaining weights (log scale)
(c) Tiny Imagenet- Resnet50
(d) Tiny Imagenet- VGG19
Test accuracies CIFAR- 100 and Tiny Imagenet for different pruning methods. Each point is the average over 3 runs of prune-train-tess The shaded areas denote the standard deviation of the runs (too small be visible in cases).
Figure 3:
5.2 RESULTS LARGER DATASETS
We now present experiments on large datasets. Wang et al. (2020) and Lee et al. (2019) suggest using batch of size ~0 times the number of classes, which is very large in these experiments. Instead, for memory efficiency, we average the saliencies over several mini-batches. For CIFAR100 and ImageNet,,,,, we average 10 and 20 batches per iteration respectively, with 128 examples per batch. As we increase the number of batches per iteration, computing the pruning mask becomes more expensive. From Fig 4 the following experiments we used 60 iterations. For a fair comparison, we run SNIP and GRASP with T batches, where is the number of iterations and B the number of batches per iteration in our method. We find the results, presented in Fig 3 consistent with trends in CIFAR-10.
we observe that the accuracy converges after just few iterations. Thus, for
In the case of Imagenet, we use batch size of 256 examples and 40 batches per iteration. We use the official implementation of VGG19 with batch norm and Resnet50 from Paszke et al. (017)) As presented Table 1 gradual pruning methods are consistently better than SNIP, with a larger gap we increase sparsity. We would like to emphasize that FORCE is able to prune 90% of the weights of VGG while losing less than 3% of the accuracy, we find this remarkable for a method that prunes before any weight update. Interestingly, GRASP performs better than other methods at 95% sparsity (VGG). moreover, also slightly surpasses FORCE for Resnet50 at 90%, however, under-
under-performs performs random pruning at 95%. In fact, we find all other methods perform worse than random pruning for Resne150. We hypothesize that, for a much more challenging task (Imagenet with 1000 classes), Resnet50 architecture might not be extremely overparametrized. For instance,
Table 1: Test accuracies on Imagenet for different pruning methods and sparsities.
Network
VGG19
Resnet50
Sparsity percentage
90%
95%
90%
95%
Accuracy
Top-1
Top-5
Top-1
Top-5
Top-1
Top-5
Top-1
Top-5
(Baseline)
73.1
91.3
75.6
92.8
FORCE (Ours)
70.2
89.5
65.8
86.8
64.9
86.5
59.0
82.3
Iter SNIP (Ours)
69.8
89.5
65.9
86.9
63.7
85.5
54.7
78,9
GRASP Wang al. 2020
69.5
89,2
67.6
87.8
65.4
86.7
46.2
66.0
SNIP Lee et al. 2019
68.5
86.0
61.5
83.9
44.3
69.6
Random
64.2
86.0
56.6
81.0
64.6
86.0
57.2
80.8

---

Published as a conference paper at ICLR 2021
Algorithm
Time
Acc
90.0%
98.0%
0.8
SNIP (T
14
10.0
Relotive Saltency
99.0%
0.7
GRASP b)
s
19.2
00.5
FORCE (20 it)
57 s
87.9
0..4
Iter SNIP (20 it)
57 s
88.9
0.3
SNIP (300 b)
4.8
76.1
FORCE
FORCE (300 it)
11.6 m
90.0
0.1
Ite SNIP
Iter SNIP (300 it)
11.6 m
89.0
Num Ittratiive stops llog scalo)
3.5 30 20
100 300
0.0
Num Iterative steps (log scale)
10 20
80 320
GRASP (300 b)
50.7 m
88.5
Figure 4: Left: FORCE saliency (6) obtained with ( when varying T normalized by the saliency with one-shot SNIP (T' = 1). Pruning iteratively brings more gains for higher sparsity levels. Error bars not shown for better visualization. Middle: Test acc pruning with FORCE and Iter SNIP at 99.5% sparsity for different T. Both methods are extremely robust to the choice of T. Right: Wall time to compute pruning masks for CIFAR www.eeenee50/eesaa--000000 vs acc at 99.5% sparsity; (o b) means used batches compute the gradients while (æ it) denotes used pruning iterations, with one batch per iteration. Numbers in red indicate performance below random pruning.
VGGI9 has 143.68M parameters while Resnet50 uses 25.56M (refer to Table 2). On the other hand, the fact that random pruning can yield relatively trainable architectures for these sparsity levels is somewhat surprising and might indicate that there still is room for improvement in this direction. Results seem to indicate that the FORCE saliency is a step in the right direction and we hypothesize further improvements on its optimization might lead to even better performance. In Appendix C.66 we show superior performance of our approach on the Mobilenet-v2 architecture (Sandler et al. 2018) as well, which is much more "slim" than Resnet and VGG
5.3 ANALYSIS
Saliency optimization To experimentally validate our approach we conduct an ablation study where we compute the FORCE saliency after pruning (5) while varying the number of iterations T for different sparsity levels. In Fig 4 (left) we present the relative change in saliency
vary the number of iterations T. note when T = 1 we recover one-shot SNIP. As expected, for moderate levels of sparsity, using multiple iterations does not have a significant impact the saliency. Nevertheless, as we target higher sparsity levels, we can see that the saliency can be better optimized when pruning iteratively. In Appendix C.I we include results for FORCE where we observe similar trends.
Hyperparameter robustness As shown in Figures and for low sparsity levels, all methods are comparable, but as move higher sparsity levels, the gap becomes larger. In Fig 4 (middle) we fix sparsity at 99.5% and study the accuracy as we vary the number of iterations T. Each point averaged over trials. SNIP (T' 1) yields sub-networks unable train (10% acc). but as we move to iterative pruning (T > 1) accuracy increases up to 90% for FORCE and 89% for Iter SNIP. Moreover, accuracy is remarkably robust the choice of the best performance for both FORCE and Iter SNIP is with more iterations, however small number of iterations already brings huge boost. This suggests these methods might be used by default by a user without worrying too much about hyper-parameter tuning, easily adapting the amount of iterations to their budget.
Pruning cost As shown Fig 2 SNIP performance quickly degrades beyond 95% sparsity. Wang al.) (2020) suggested GRASP more robust alternative, however, it needs to compute Hessian vector product which significantly more expensive in terms of memory and time. Fig (right), compare the time cost of different methods obtain the pruning masks along with the corresponding accuracy. We observe that both SNIP and GRASP are fragile when using only one batch (red accuracy indicates performance below random baseline). When using multiple batches their robustness increases, but so does the pruning cost. Moreover, we find that gradual pruning based on the FORCE saliency is much cheaper than GRASP-MB when using equal amount of batches, this is because GRASP involves an expensive Hessian vector product. Thus, FORCE (or Iterative SNIP) would be preferable over GRASP-MB even when they have comparable accuracies.
FORCE vs Iterative SNIP Empirically, we find that FORCE tends to outperform Iter SNIP more often than not, suggesting that allowing weights to recover is indeed beneficial despite having less theoretical guarantees (see gradient approximation in Section 4 Thus, we would make FORCE
Mobilenct has 2.3M params compared 20.03M and 23.5M of VGG and Resnet, respectively.
8

---

Published as a conference paper at ICLR 2021
algorithm our default choice, especially for Resnet architectures. In Appendix C.4 we empirically observe two distinct phases when pruning with FORCE. The first one involves exploration (early phase) when the amount of pruned and recovered weights seem to increase, indicating exploration of masks that are quite different from each other. The second, however, shows rapid decrease in weight recovery, indicating phase where the algorithm converges to a more constrained topology. As opposed to Iter SNIP, the possibility of the exploration of many possible sub-networks before converging to final topology might be the reason behind the slightly improved performance of FORCE. But this exploration comes at price, in Fig 4 (middle and left) we observe how, despite FORCE reaching higher accuracy when using enough steps, if we are under a highly constrained computational budget and can only afford a few pruning iterations, Iter SNIP is more likely to obtain a better pruning mask. This indeed expected as FORCE might need more iterations to converge to good sub-space, while Iter SNIP will be forced to converge by construction. A combination of FORCE and Iter SNIP might lead to an even better approach, we leave this for future work.
Early pruning an additional baseline Our gradual pruning approaches (SNIP-MB and GRASP- MB as well) use multiple batches to obtain a pruned mask, considering that pruning can be regarded as form of training (Mallya et al. 2018), we create another baseline for the sake of completeness. We train a network for one epoch, a similar number of iterations as used by our approach, and then use magnitude pruning obtain the final mask, we call this approach early pruning (more details in Appendix C.5) Interestingly, we find that early pruning tends to perform worse than SNIP-MB (and gradual pruning) for Resnet, and shows competitive performance low sparsity level for VGG but with sharp drop in the performance as the sparsity level increases. Even though these experiments support the superiority of our approach, we would like to emphasize that they do not conclude that any early pruning strategy would be suboptimal compared to pruning at initialization as an effective approach in this direction might require devising a well thought objective functioo.
Iterative pruning to maximize the Gradient Norm In Sec 4 we have seen Iterative SNIP can be used to optimize the FORCE saliency. We also tried to use GRASP iteratively, however, after a few iterations the resulting networks were not trainable. Interestingly, if we apply the gradient approximation to GRASP saliency (instead of Taylor), we can come up with a different iterative approximation to maximize the gradient norm after pruning. We empirically observe this method is more robust than GRASP to high sparsity levels. This suggests that 1) Iterative pruning, although beneficial, can not be trivially applied to any method. 2) The gradient approximation is more general than in the context of FORCE/SNIP sensitivity. We present further details and results in Appendix E
DISCUSSION
Pruning at initialization has become an active area of research both for its practical and theoretical interests. In this work, we discovered that existing methods mostly perform below random pruning at extreme sparsity regime. We presented FORCE. new saliency to compute the connection sensitivity after pruning, and two approximations to progressively optimize FORCE in order to prune networks at initialization. We showed that our methods are significantly better than the existing approaches for pruning at extreme sparsity levels, and are at least as good as the existing ones for pruning at moderate sparsity levels. We also provided theoretical insights on why progressive skeletonization is beneficial at initialization, and showed that the cost of iterative methods is reasonable compared to the existing ones. Although pruning iteratively has been ubiquitous in the pruning community. it was not evident that pruning at initialization might benefit from this scheme. Particularly, not every approximation could be used for gradual pruning as we have shown with GRASP. However, the gradient appreximation allowed us to gradually prune while maximizing either the gradient norm or FORCE. We consider our results might encourage future work to further investigate the exploration//xxlootttinn trade-off in pruning and find more efficient pruning schedules, not limited to the pruning at initialization.
ACKNOWLEDGMENTS
This work was supported by the Royal Academy of Engincering under the Research Chair and Senior Research Fellowships scheme, EPSRC/MURI grant EP/N019474/1 and Five AI Limited. Pau de Jorge was fully funded by NAVER LABS Europe. Amartya Sanyal acknowledges support from The Alan Turing Institute under the Turing Doctoral Studentship grant TU/C/000023. Harkirat was supported using a Tencent studentship through the University of Oxford.
9

---

Published as a conference paper at ICLR 2021
REFERENCES
Guillaume Bellec, David Kappel, Wolfgang Maass, and Robert Legenstein. Deep rewiring: Training very sparse deep networks. International Conference on Learning Representations, 2018. URL net www.ooiddnmnnooaa....
Miguel Á. Carreira-Perpiiánn and Yerlan Idelbayev. "Iearning-compa comprnesioommmsssion"" algorithms for neural net pruning. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
Yves Chauvin. A back- pack-propagation algorithm with optimal use of hidden units. In Advances in neural information processing systems, pp. 519-526, 1989.
Xiaoliang Dai, Hongxu Yin, and Niraj K Jha. Nest: A neural network synthesis tool based on a grow-and-prune paradigm. IEEE Transactions on Computers, 68(10):1487-1497, 2019.
Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing performance, 2020. URL C hatt::://ppenneevv.eeeenntttfrro
Erich Elsen, Marat Dukhan, Trevor Gale, and Karen Simonyan. Fast sparse convnets. Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 16699-46636 2020.
Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. arXiv preprint arXiv: 134, 2019.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable
neural networks. International Conference on Learning Representations, 2019. URL https
//openreview.rr net. http://wwww.eeeeeeeeeeeeeeoem (tte:/ormmmmiirl-.b333
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, and Michael Carbin. Stabilizing the
lottery ticket hypothesis, 2020.
Yiwen Guo, Anbang Yao, and Yurong Chen. Dynamic network surgery for efficient dons. In Advances in neural information processing systems, pp. 1379-1387, 2011377,2011 2016.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances in neural information processing systems, pp. 1 133-1143, 2015.
Babak Hassibi, David G Stork, and Gregory J Wolff. Optimal brain surgeon and general network pruming. In IEEE international conference neural networks, pp. 293-299. IEEE, 1993.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-10260000 1034, 2015.
Alex Krizhevsky et al. Learning multiple layers of features from tiny images, 2009.
Aditya Kusupati, Vivek Ramanujan, Raghav Somani, Mitchell Wortsman, Prateek Jain, Sham M. Kakade, and Ali Farhadi. Soft threshold weight reparameterization for learnable sparsity. ArXiv, 1b3/2002.032311, 2020.
Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In Advances in neural information processing systems, pp. 598-605, 1990.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr SNIP: SINGLE-SHOT NETWORK PRUNING BASED ON CONNECTION SENSITIVITY. In International Conference Learning Representations, 2019. URL httlhhttts://pperreeett ew net/ /tt.:/nrrrurreeeee wot.oooiouuliiiioooooooo
Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip H. S. Tor. A signal propagation perspective for pruning neural networks at initialization. International Conference on Learning Representations, 2020. URL http://////ppeeeeeeeeeeeeeeerrrr
10

---

Published as a conference paper at ICLR 2021
Tao Lin, Sebastian U. Stich, Luis Barba, Daniil Dmitriev, and Martin Jaggi. Dynamic model pruning with feedback. In International Conference on Learning Representations, 2020. URL
net/ (etpaarreieewnntt/oouueeeeeeeee Ftt/:/rrmmmi--eeemmsesee
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell, Rethinking the value of network pruning. In International Conference on Learning Representations, 2018. 8.
Christos Louizos, Max Welling, and Diederik P. Kingma. Learning sparse neural networks through 10 regularization. In International Conference on Learning Representations, 2018. URL https //openreview wtw..nneetooommmmdddaa-mam
Arun Mallya, Dillon Davis, and Svetlana Lazebnik. Piggyback: Adapting single network to multiple tasks by learning to mask weights. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 67-82, 2018.
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature communications, 9(1):1-12, 2018.
Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz. Pruning convolutional Pavlo
neural networks for resource efficient inference. In International Conference on Learning Repre- sentations, 2017.
Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization, 2019. URL https: http::tttt//ppptt https://pppevvveeeee net. forum?
id 11xB1xxsRRX
Michael C Mozer and Paul Smolensky. Skeletonization: A technique for trimming the fat from network via relevance assessment. In Advances in Neural Information Processing Systems, 1989.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch, 2017.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV). 115 (3):211-252, 2015. doi: 10.1007/s1 1263-015-0816.y.
M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L. Chen. Mobilenetv2: Inverted residuals and linear bottlenecks. In 2018 IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 4510 4520, 2018. doi: 1091C 8.00444.
Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, neurips pdf
pp. 6377-6389 Curran Associates, Inc., 2020. URL
Stijn Verdenius, Maarten Stol, and Patrick Forré. Pruning via iterative ranking of sensitivity statistics.
arXiv preprint arXiv:2006.0089 2020.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference Learning Representations, 2020. URL
htttps://openreval
n forum 2o
Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning, arXiv preprint 111.0016,..01578. 2016.
11

---

Published as a conference paper at ICLR 2021
A PRUNING IMPLEMENTATION DETAILS
We present experiments on RIFAR-10/100 Krizhevsky et al. 2009). which consists of 60k x2x32 colour images divided into 10/ 100 classes, and also on Imagenet challenge ILSVRC-2012 (Rus sakovsky et al. 2015) and its smaller version Imag-en,,,,e, which respectively consist of 1. 1.2M/IL IK Networks are initialized using the Kaiming normal initialization (He et al. 2015). For CIFAR datasets, we train Resnet5( and with batch size of 128. We start with a learning rate of 0.1 and divide it by 10 at 150 and 250 epochs. use SGD with momentum 0.9 and weight decay 5 x 10 We separate 10% of the training data for validation and report results on the test set. We perform mean and std normalization and augment the data with random crops and horizontal flips. For Iin-Immaennt, we use the same architectures. We train during 300 epochs and divide the learning rate by 10 at 1/2 and 3/4 of the training. Other haper-parameters remain the same. For ImageNet training, we adapt the official code Paszke et al. (2017) and we use the default settings. In this case, we use the Resnet50 and VGG19 with batch normalization architectures as implemented in Paszze et al. (2017).
and 100k /200 inages/classees
during 350 epochs
As optimizer
In the case of FORCE and Iter SNIP, we adapt the same public implementation of SNIP as Wang al. (2020). Instead of defining an auxiliary mask to compute the saliencies, we compute the product of the weight times the gradient, which was shown to be equivalent in [ee et al. (2020). As for GRASP, we use their public code After pruning, we implement pruned connections by setting the corresponding weight to 0 and forcing the gradient to be O. This way, pruned weight will remain 0 during training.
An important difference between SNIP and GRASP implementations is in the way they select the mini-bated to compute the saliency. SNIP implementation simply loads a batch from the dataloader. In contrast, in GRASP implementation they keep loading batches of data until they obtain exactly 10 examples each class, discarding redundant samples. In order to compare the methods in equal conditions, we decided to use the way SNIP collects the data since it is simpler implement and does not require extra memory. This might cause small discrepancies between our results and the ones reported in Wang al. (2020).
Table 2: Percentage of weights per layer for each network and dataset.
Layer type
Conv
Fully connected
BatchNorm
Bias
Prunable
Total
CIFARTO
Resnet50
99.69
0.09
0.11 0.03
0.11
99.78 99.95
23.52M
VGG19
99.92
0.03
0.03
20.04M
CIFARI00
Resnet50
98.91
0.86
0.11
0.11
99.78
2
VGG19
99.69
0.25
0.03
0.03
99.94
20.08M
Tinylmagenes
Resnet50
98.06
1.71
0.11
0.11
99.78
M
VGG19
99.44
0.51
0.03
0.03
99.94
20.13M
Imagenet
Resnet50
91.77
8.01
0.10
0.11
99.79
25.56M
VGG19
13.93
86.05
0.01
0.01
99.98
143.68M
A meaningful design choice regarding SNIP and GRASP implementations is that they only prune convolutional and fully connected layers. These layers constitute the vast majority of parameters in most networks, however, as we move to high sparsity regimes, batch norm layers constitute non non-negligible amount. For CIFARIO, batch norm plus biases constitute 0.2% and 0.05% of the parameters of Resnet50 and VGG19 networks respectively. For consistency, we have well restricted pruning to convolutional and fully connected layers and reported percentage sparsity with respect to the prunable parameters, is also done in Lee et al. (2019) and Wang et al. (2020) to the best of our knowledge. In Table 2 we show the percentage of prunable weights for each network and
py
httpss///qittbbb.cm////illlal
12

---

Published as a conference paper at ICLR 2021
0.86
20.0
0 04
FORCE
0.80
FORCE
Ber SNIP
00.88
Fer SKIP
0.
SNP MB
CRASHIAD
30.05
SNP MB
Random
2.0.1
Random
0.01
Dense Saseline
Denta Daseline
0.1%
0.5%
1%
5%
10%
0.1%
0.5%
18
10%
Percentage of remaining we weights (log scale!
Percentage remaining weights (log scale)
(a) Resnet50 CIFAR-10
(b) VGG19 CIFAR-10
Accuraty CIFARIOO
Denoe Baseline
accuracy
Baseine
1% Parcentage of remaining weights (lag scale)
5%
10%
Percentage of rumn ramaining weights Oog
(c) Resnet50 CIFAR-100
(d) VGGI9 CIFAR-100
8 88
0.58
FORCE
Ber ShiP
5062
2.
01
01
GRASP MB
SNP-MM
Random
Ter SNIP
FORCE
F-1
50
2.556
23
52
GAASP
Random
Dunid Basoline
SNIP-M4
40 46
2 46
0.42
6:47
0.3%
1%
5%
10%
0.5%
5%
Percentage of remaining weights (lag scale)
Percentage of run aining weights Oog sca
(c) Resnet50 Tiny Imagenet
(i) VGG19 Tiny Imagenet
Test accuracies on (FFAR-10/10) and Tiny Imagenet for different pruning methods. Each point is the average over 3 runs of prune-train-test. The shaded areas denote the standard deviation of the runs (too small to be visible in some cases).
Figure 5:
dataset we use. In future experiments we will explore the performance of pruning at initialization when including batch norm layers and biases well.
B ADDITIONAL ACCURACY-SPARSIIC PLOTS
In the main text we show the complete range of the accuracy-sparsity curves for the different methods so it is clear why more robust methods are needed. However, it makes it more difficult to appreciate the smaller differences at lower sparsities. In Fig 5 we show the accuracy-sparsity curves where cut the axis to show only the higher accuracies.
C FURTHER ANALYSIS OF PRUNING AT INITIALIZATION
C.1 SALIENCY VS
In 4 have that for higher sparsity levels, FORCE obtains higher saliency when we increase the number of iterations. In F we compare the relative saliencies as we increase the number of iterations for FORCE and Iterative SNIP. As can be seen, both have a similar behaviour.
C.2 PRUNING VS SPARSIFICATION
FORCE algorithm is able to recover pruned weights in later iterations of pruning. In order to do that, we do not consider the intermediate masks as pruming masks but rather as sparsification masks, where connections are set to 0 but not their gradients. In order to understand how does computing the FORCE 5 on a sparsified vs pruned network affect the saliency, we prune several masks with then compute their FORCE saliency
FORCE algorithm at varying sparsity levels. For each mask, either considering the pruned network (gradients of pruned connections will be set during the backward pass) the sparsified network (we only set O the connections, but let the gradient signal
13

---

40 60 100 Published as a conference paper at ICLR 2021
3.0
Relative Saliency
90.0%
Rel Relativv Sallency
90.0%
2.5
96.0%
99. 39.0%
99.0%
2.0
90.5%
99.5%
1.5
1.0
2
4.5
10
20
200300
3 4.5
10 20
40 60 100 200300
Num iterative steps (log scale)
Num Iterativv steps (log scale)
(a) Saliency vs 7 across sparsity levels (FORCE)
(b) Saliency vs T across sparsity levels (Iter SNIP)
Figure 6: FORCE saliency (6) obtained with iterative pruning normalized by the saliency obtained with one-shot SNIP, 7 = 1. (a) Applying the FORCE algorithm (b) Using Iterative SNIP. Note how both methods have similar behaviour.
FORCE (sparsification)
60
0.8
0.6
40
20
0.2
20 40 60
FORCE (pruning)
Figure 7: FORCE saliency computed for masks measuring FORCE when we allow the gradients of zeroed connections to be non-zero, while FORCE (pruning) cuts all backward signal of any removed connection. As can be seen on the plot, they are strongly correlated.
vary sparsity. FORCE (sparsification) refers
flow through all the connections). Results presented in Fig 7 We observe that the methods to compute the saliency are strongly correlated, thus, we can assume that when we use the FORCE algorithm that maximizes the saliency of sparsified networks we will also maximize the saliency of the corresponding pruned networks.
C.3 NETWORK STRUCTURE AFTER PRUNING
In Fig we visualize the structure the networks after pruning 99.9% of the parameters. We show the fraction of remaining weights and the total number of remaining weights per layer after pruning. As seen in (a) and (d), all analysed methods show a tendency to preserve the initial and final layers and prune more heavily the deep convolutional layers, this is consistent with results reported in Wang et al.) (2020). In (b) and (e), we note that FORCE has a structure that stands out compared other methods that are more similar. This reasonable since, it is the only method that allows pruned weights to recover. In the zoomed plots (c) and (f) we would like to point out that FORCE and Iterative SNIP preserve more weights on the deeper layers than GRASP and SNIP for VGG19 while we observe the opposite behaviour for Resnet50.
In Fig2, we observe that gradual pruning is able to prune the Resnet50 network up to 99.99% sparsity without falling to random accuracy. In contrast, with VGG19 we observe Iterative SNIP is not able to prune more than 99.9%. In Fig X we observe that for Resnet50, all methods prune some layers completely. However, in the case of ResNets, even if a convolutional layer is entirely pruned, skip connections still allow the flow of forward and backward signal. On the other hand, architectures without skip connections, such as VGG, require non-empty layers to keep the flow of information. Interestingly, in (c) we observe how FORCE and Iter SNIP have a larger amount completely pruned layers than GRASP, however, there unpruned weights. This seems to indicate that when a high sparsity is required, it more efficient to have fewer layers with weights than several extremely sparse layers.
few deep layers with significantly larger amount of
14

---

Published as a conference paper at ICLR 2021
SNIP-MB
Weight hts por lyer bx1000)
06
SNIP MB
GRASP-MB
0.09
SNIP-MB
Iter SNIP
SNIP
0.08
Ber SNIP
Denaiy
FORCE
FORCE
0.07
FORCE
0.06
20.05
0.004
0.2
50.03
0.1
0.02
0.0
0.00
48
16
Layer index
Layer index
Layer
(a) Resnet50 Layer density
(b) Resnet50 total weights
(c) Resnet50 total weights (zoom)
0.8
SNIP-MB
SNIP-MB
0.09
SNIP-MB
Weights por layer (x1000)
GRASP-MB
0.008
GRASP
Iter SNIP
SNIP
Ber SNIP
Layer Density
0.6
FORCE
FORCE
0.07
FORCE
0.06
20.05
0.4
0.03
1 0.00
0.01
0.0
0.00
16
Layer index
Index
Layer index
(d) VGG19 Layer density
(e) VGG19 total weights
(f) VGG19 total weights (zoom)
Figure 8: Visualization of remaining weights after pruning 99.9% of the weights Resnet-50 and VGG-19 for 10. (a) and (d) show the fraction of remaining weights for each prunable layer. (b) and (e) show the actual number remaining weights and (c) and (f) zoom to the bottom part of the plot. Observe in (c) and (f) that some layers have exactly 0 weights left, they are removed entirely.
15

---

Published as a conference paper at ICLR 2021
Pruned SNP
8 00.0
Pruwed FORCE Recovered FORCE
Recowered SMP
&0.7
206
50.5
0.1
0.0
100120140
360
20
180 260
Reration
Pruning
(a) Pruned and recovered weights (Iter SNIP)
(b) Pruned and recovered weights (FORCE)
Figure 9: Normalized amount of globally pruned and recovered weights at each pruning iteration for Resnet50, CIFAR-10 when pruned with (a) Iterative SNIP and (b) FORCE. As expected, the amount of recovered weights for Iterative SNIP constantly zero, since this is by design. Moreover, the amount of pruned weights decays exponentially as expected from our pruning schedule. On the other hand, we see the amount of recovered weights non-zero with FORCE, interestingly the amount of pruned/recovered weights does not decay monotonically but has a clear peak, indicating there is an "exploration" and a "convergence" phase during pruning.
C.4 EVOLUTION OF PRUNING MASKS
As discussed in the main text, FORCE allows weights that have been pruned at earlier iterations to become non-zero again, we argue this might be beneficial compared to Iterative SNIP which will not be able to correct any possible "mistakes" made in earlier iterations. In particular, it seems to give certain advantage to prune VGG to high sparsities without breaking the flow of information (pruning a layer entirely) as can be seen in Fig (b). order to gain a better intuition how does the amount of pruned/recovered weights ratio evolve during pruning, in Fig P we plot the normalized amount of pruned and recovered weights (globally on the whole network) at each iteration of FORCE and also for Iter SNIP sanity check. Note that Iterative SNIP does not recover weights and the amount of weights pruned at each step decays exponentially (this is expected since we derived Iterative SNIP constrained optimization of FORCE where each network needs to be sub-networt of the previous iteration. On the other hand, FORCE does recover weights. Moreover, the amount of pruned/recovered weights does not decay monotonically but has clear peak, indicating there are two phases during pruning: While the amount of pruned weights increases, the algorithm explores masks which are quite far away from each other, although this might be harmful for the gradient approximation (refer to section 4), we argue that during the initial pruning iterations the network is still quite werrparametrized. After reaching a peak, both the pruning and recovery rapidly decay, thus the masks converge to more constrained subset.
C.5 COMPARISON WITH EARLY PRUNING
For fair comparison, provided the same amount of data to SNIP and GRASP was used by approach and call this variant SNIP-MB and GRASP-MB. Similarly, under this new baseline which we call early praning, we train the network on I epoch of data of CIFAR-10. that is slightly more examples than our pruning at initialization methods which use 128 300 38400 examples (see section 5). After training for epoch perform magnitude pruning which requires extra cost
0.04
0.94
0.97
0 0..84
0.00
86
ker SNIP
00.84
0..00
fer SNIP
FaRLE
20.82
GRASP-MB
20.82
GRUSSP H4
8..80
SNIP He
00.80
SNIP MB
4 0.74
0.766
Rendom
Barty pruning
0.776
0.74
Rendom
Barly pruning
Dense Saseline
Dense Baselin
0.70 6.1%
0.5%
1%
5%
10%
0.1%%
0.5%
1%
5%
10%
Percentage of remaining weights (log scale!
Percentage remaining weights (log scale)
(a) Resnet50
(b) VGG19
Figure 10: Test accuracies CIFAR-10 10 for different pruming methods. Each point is the average over runs of prune-train-test The shaded areas denote the standard deviation the runs (too small to be visible in some cases). Early pruning is at most par with gradual pruning at initialization methods and has strong drop in performance as we go to higher sparsities.
16

---

Published as a conference paper at ICLR 2021
(results presented in Fig 10p. sparsity levels, soon degrades its performance as we prune more weights. On the other hand, for Resnet architecture it is sub-optimal at all evaluated sparsity levels. Note, this result does not mean that any early pruning strategy would be sub-optimal compared to pruning at initialization, however exploring this further is out of the scope of this work.
Although early pruning yields competitive results for VGG moderate
C.6 MOBILENET EXPERIMENTS
All experiments
overparameterizee architectures such as Resnet and VGG. To test the wider usability of our methods, in this section we prune the Mobilenet-v2 architectur (Sandler al. 2018) which much more "slim" than Resnet and VGG (Mobilenet has 2.3M params compared to 20.03M and 23.5M of VGG and Resnet respectively). Results are provided in Fig IT Similarly to Resnet and VGG architectures, we see that gradual pruning tends better preserve accuracy at higher sparsity levels than one-shot methods. Moreover, both FORCE and Iter SNIP improve over SNIP at moderate sparsity levels as well. FORCE and Iter SNIP have comparable accuracies except for high sparsity where Iter SNIP surpasses FORCE. We hypothesize for such slim architecture (+s 10 x fewer parameters than Resnet and VGG) the gradient approximation becomes even more sensitive to the distance between iterative masks and perhaps the exploration of FORCE is harmful in this case. As discussed in the main paper, we believe that further research to understand the exploration/cxploitation trade-off when pruning might yield to even more efficient pruning schemes, especially for very high sparsity levels. We train using the same settings as described in Appendix [A] except for the weight decay which is set to 4 10-5, following the settings of the original Mobilenet paper.
Accuracy CIFARIO
FORCE
Iter SNIP
000,000 00
GRASP-MB
SNIP-MB
0002000
Random
Dense Baseline
66
1%
2%
5%
10%
20%
Percentage of remaining weights (log scale)
Figure 11: Test accuracies CIFAR-10 for different pruning methods Mobilenet architecture. Each point is the average over 3 runs of prune-train-test. The shaded areas denote the standard deviation of the runs (too small be visible some cases). When pruning Mobilenet-v2 architecture, which has roughly 10x less parameters than Resnet or VGG, we observe a similar pattern: Gradual pruning tends to be able to preserve accuracy for higher sparsities better than one-shot methods. Moreover, it tends to improve slightly over SNIP at moderate sparsities as well. Although GRASP does not show an acute drop in performance like SNIP, seems be sub-optimal with respect to other methods across all sparsities.
D LOCAL OPTIMAL MASKS
Definition 1 ((p, local optimal mask). Consider any two sets c. S {1,... m} and c++1 C ca For any é >> and 0 S p < cc, ce+ils C++1 is a (p,c) e) local optimal with respect to e, the following holds
S (6, c--1) 2 (0, (ct+1 \S-)US_)-c
for all S_ C. C+41,1S1|= p and S_ c (c. \ c.41) |S+| =p.
Definition 2 (CRS; Coordinate-Restricteed Restrictedd-Smootnesss Smoothness). Given a function C Rm + R (which encodes both the network architecture and the dataset), L is said be Coorrdiied Restricted
httpps://gite wtwpthww...oouggiiiaa/aaa htt.:////wwuugguuggg/tttrroo-oaa far/bl far//blab/mastte//ooee
mobi eeeett2.pp.
Foor ease of notation, we will use this representation interchangeably with its binary encoding i.c. m-dimensional binary vector with its support equal to
17

---

Published as a conference paper at ICLR 2021
Smooth with respect to S {1, -I. .m) if there exists real number Xe such that
||e VC( O c) o VL @ م S Ae ||w oc w @0ll
(10)
for all
R and è When cc ट|. application of Holder's inequality shows
Ae w O ||| de |/ ||C E|l S ||
We define to be A-total CRS if there exists a function A {0, 11 R such that for all E {0,1]* 1)"h C is A -etbooddiatt-Rssttitteee----e-ee
with respect to (for ease of notation we use A (c) Xa).
Theorem (Informal), The mask C++1 produced from с₁ by FORCE is (p.2 |1011 [cr] -local optimal if the L is A-CRS..
Proof. Consider the masks et and c where the latter is obtained by one step of FORCE on the former. Let S_ and S+ be any set of size p such that S_ C C++1 and S_ C (c, Cc+1). Finally, for ease of notation we define (= (ct+1 (5-)US4
S (0. S (0,
Σ
10: (L(0
E 0 (f c441)
iE(
iER1+1
Σ iEc1+1
0 VL O
10: (1
+
Σ EES
10, VL 01 - Σ
10 VL(OOC)
(11)
IES
Ta
Let us look at the three terms individually. We assume that is A-CRS.
ri
Σ 10, (0 00 (Z00000)4))
(E0111
|cc41
@ 8 ② ( - c.+1 080 V
By Triangle Inequality
c1+1
@ 0|1 ||+1 @ VL c++1) c++1 @ (f Al
By Holder's Inequality
I 2dcmm
|e41/p11 p |
L A-CRS (12)
12
Σ 10,
VC (2
IES+
< Σ
10, (L(0 + + (ccal - (c411)
:: \ Cl = clcc - -|c++1,
iES+
(13)
13 =
Σ
0 (0 B (0
iES
< Σ
0, VL
2 c.),
A 1012 (1c,1 - 1c++1))
(14)
$ES_
Adding eqs.
13 and 14 get
P2 P2+ <
00, (0 Σ 10: vL(00c),, + 2Ac,P 11013 (leal - (ce+1
SE8+
$ES_
2\c, 1012 (lc.1 - |c++1]) 7p
(15)
1L cz)y - -0,00000)2000
where 7 = (.t
18

---

Published as a conference paper at ICLR 2021
Substituting eqs.
112) and 15 into
get
S (0, S ) I 2Act+1 |c--1pp 101 + 2h 1101 (lozl - (c++l)) - YP
2 P |101 (lc/+1l + (le/l |c(+1)) - Yp
S c4+1) 2 S (6, 2 ||0| 800 |cal + YP
S (0, cc+1) (6, 22c.- P |cc
E ITERATIVE PRUNING TO MAXIMIZE THE GRADIENT NORM
0.9
0.9
0.8
0.8
FORCE
SNPP
0.5
GRASP
0.5
Fer GRASP
GRASP-ann
0.44
CRASP-MB
SNIP HB
SNP HB
0.2
Random
0.2
Handtom
0.1
Dense Baseline
0.1
Dense Baseline
0.1%
0.5%
1%
5%
10%
0.1%
Percentage remaining weights (log scale)
Percentage of remaiiing weights (lag scale)
(a) CIFAR Resnet50
(b) CIFAR 10 VGG19
0.7
GFAR009
0.7
S 0.6
0.6
FORCE
0.5
FORCE
Rar SNPP
0.4
Rar SNIP
Fer CRASP
Per GRACP
GRASP MB
0.3
GRASP MB
0.2
SNIPMB
5NP -HB
Random
Random
0.5%
0.0
Percentage remaiining weights (log scale)
Percentage of remaining weights scale)
(c) CIFAR 100 Resnet50
(d) CIFAR 100 VGG19
0.5
FORCE
FORLE
Fer SNP
0.4
Per SNI
GRASP
0.3
GRASP MB
Fer GRASS
Bascline
Dense Bascline
0.0
1%
5%
10%
0.0
Percentage remaining weights (lag
Percentage of remaining weights
(e) Tiny Imagenet Resnet50
(i) Tiny Imagenet VGG19
Test accuracies for different datasets and networks when pruned with different methods. Each point is the average over 3 runs of prune-train-test The shaded areas denote the standard deviation the runs (sometimes too small to be visible).
Figure 12:
E. MAXIMIZING THE GRADIENT NORM USING THE GRADIENT APPROXIMATION
In order to maximize the gradient norm after pruning, the authors in Wang et al. (020) use the first order Taylor's approximation. While this seems be better suited than SNIP for higher levels of sparsity, it assumes that pruning is a small perturbation on the weight matrix. We argue that this approximation will not be valid as we push towards extreme sparsity values. Our gradiens approximation (refer to section Q can also be applied to maximize the gradient norm after pruning. In this case, we have
G c) == AC(O0c) AC(O)=
Σ -VC())),)
(16)
(A) cc=00
where we assume pruned connections have null gradients (this is equivalent to the restriction used for Iterative SNIP) and assume gradients remain unchanged for unpruned weights (gradient
19

---

Published as a conference paper at ICLR 2021
approximation), Combining this approximation with Eq. 7. we obtain new pruning method name Iterative GRASP, although it is not the same as applying GRASP iteratively. Unlike FORCE, Iterative GRASP does not recover GRASP when T 1.
In Fig 12 we compare Iterative GRASP to other pruning methods. We use the same settings as described in section[]] We observe that Iterative GRASP outperforms GRASP in the high sparsity region. Moreover, for VGG19 architecture Iterative GRASP achieves comparable performance to Iterative SNIP. Nevertheless, for Resnet50 that of FORCE and Iterative SNIP as we prune more weights. FORCE saliency takes into account both the gradient and the magnitude of the weights when computing the saliency. on the other hand, the Gradient Norm only takes gradients into account, therefore it is using less information. We hypothesize this might the reason why Iterative GRASP does not match Iterative SNIP.
see that Iterative GRASP performance falls below
E.2
ITERATIVE GRASP (PRUNING CONSISTENCY)
0.9
Density
0.9
Iteration
0.7
0.8
Dansity 0.7
0.7
0.8
Iteration
20.6
Density
8.6
Iteration
Dansity 0.01
0.
Iteration 12
804
0.3
0.2
0.1
0.0
0
12
16
20
32
36
40
48
52
12
16
20
24
28
32
36
40
52
Layer index
Layer index
(a) Ohe-shor GRASP
(b) Iterative GRASP
0.6
Denalyy
0.5
Density 0.9
Iteration
Density 0.7
Iteration
Density 0.3
Iteration
0.1
Donsity 0.01
Iteration
12
0.0
12
36
44
48
52
12
16
20
24
28
32
36
40
Layer index
Layer index
(c) One-shot SNIP
(d) Iterative SNIP
Figure 13: (a) (c) Portion of remaining weights for each layer. Each point is average of 3 runs and the error bars (hardly visible) denote standard deviation. (b) (d) Portion of remaining weights for each intermediate mask that is computed during iterative pruning with global portion of remaining weights of 0.01.
As explained in the main text, we tried to apply GRASP iteratively with the Taylor approximation described in Wang et al. (020). Unfortunately, we found that all resulting masks yield networks unable to train. In light of this result, we performed some analysis of the behaviour GRASP compared to that of SNIP and, in the following, provide some insights to why we not use GRASP's approximation iteratively.
In Liu al. (2018), the authors show that applying a pruning method to the same architecture with different random initializations would yield consistent pruning masks. Specifically, they find that the percentage of pruned weights in each layer had very low variance. We reproduce the same experiment and additionally explore another dimension, the (global) sparsity level. Given an architecture, we prune it varying levels of sparsity and extract the percentage of remaining weights at each layer. For each level of sparsity, we average the results over 3 trials of initialize- -prene. As shown in Fig 2 both SNIP and GRASP have very low variance across initializations, on the other hand, as we vary the global sparsity with GRASP, the percentage of remaining weights for each layer is inconsistent. The layers that are most preserved at high levels of sparsity, such as the initial and last layers, are the most heavily pruned at low sparsity levels.
The authors in Liu et al. (2018), reason that manually designed networks have layers which are more redundant than others. Therefore, pruning methods even this redundancies by pruning layers with different percentages. We extend this reasoning, and hypothesize that pruning algorithms should always have preference for pruning the same (redundant) layers across all levels of sparsity. We denote this as pruning consistency. We observe that when applying iterative pruning to GRASP, the resulting masks tend to prune almost all of the weights the initial and final layers, producing
20

---

Published as a conference paper at ICLR 2021
networks that unable to converge. When using iterative pruning, prune small portion of remaining weights at each step. Thus, we are always in the low sparsity regime, where the GRASP behaviour is reversed. Conversely, when we use SNIP the behaviour changes completely. In this case, the preserved layers are consistent across sparsity levels, and when we use iterative pruning we obtain networks that reach high accuracy values.
21


Reviews:
[{"review_id": "nRMdudFlSo", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper presented a new sensitivity-based pruning methods to cut network connections at initialisation. The proposed method FORCE shows great performance when compared to rencelty proposed SNIP and GRASP. In general, I liked the formulation of the problem, its in-depth analysis and detailed comparison to existing approaches. I see clear contribution in this paper to the field of pruning at initialisation and it is a clear accept from me.\n\nStrength:\n1. The paper comapres to very recently proposed pruning methods (SNIP and GRASP), and shows a great accuracy increase at very aggressive pruning levels.\n2. The paper discussed shortcomings of previous methods in details, and clearly differentiated their proposed method in Section 4. The novelty of this paper is clear to me.\n3. The paper is well written and easy to follow.\n4. The paper has some interesting insights (mask zeroing, exponential scheduling, etc.) and the proposed iterative pruning at initialization is easy to apply in practice. These might add knowledge to the network pruning community.\n\nWeakness:\n1. The paper only investigates, to my understanding, ‘fat’ models. Both VGG19 and ResNet50 cannot be considered as efficient model architectures. It might be more convincing for the paper to test on recently proposed efficient network architectures such as the MobileNet family.\n2. Although the paper has a potential contribution to theoretical understanding of pruning, I would like to argue aggressive pruning at initialisation cannot guarantee model’s post-training performance, and it might limit the use of this technique in reality.\nFined-grained pruning like proposed in this paper is hard to bring any real performance gains in today’s GPUs, especially when it is applied with a mask. \n\nDespite of the weaknesses mentioned above, in general, I think this paper is well-motivated and shows a clear contribution to the community, so it is a clear accept from my side.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Qje-ngTFIU2", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: Author observed that beyond a certain level of sparsity, existing pruning methods hat pruning at initialization performs even worse than random pruning. The author proposed FORCE and Iterative SNIP to handle this problem. These methods consistently significantly outperforms other methods on this problem.\n\nContributions: A new problem found in pruning. New effective methods proposed by author.\n\nWeaknesses: \nThe author only shows that his methods works better than SNIP and GRASP at super high sparsity. We wonder how it performs when sparsity is not that high.\nSuper high sparsity problem for methods pruning at initializations is a relative small problem. The importance of this problem is weak, although author improved performance in this case. I wonder whether this is truly useful in practice.\n\nThe writing of the paper is good. It is easy to follow the paper.\n\nIt is a narrow area, but the paper is deep and through.\n\nThe Theorem 1 in the appendix seems solid, but it is acutually based on previous paper. Just a litte bit modification on the gaint's shoulder.\n\nBut overall, it is still a good paper, though the area may be very narrow.", "extra_scores": {}, "extra_text": {}}, {"review_id": "7r-Z1aYy9c8", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\n\nThe paper finds that at extreme sparsities (>95%), existing approaches to pruning neural networks at initialization devolve to worse than random pruning. The paper posits that this degenerate behavior is due to the fact that weights are pruned in groups, though the saliency metrics only capture pointwise changes. The paper presents a modified saliency metric based on SNIP, allowing for calculating salience of partially pruned networks; this in turn allows for applying an iterative version of SNIP, as well as a variant of iterative SNIP that allows for rejuvenation. These pruning techniques are evaluated, showing that they maintain accuracy at high sparsities.\n\n# Strengths\n\n- Well-motivated: SNIP and GRASP's drops in accuracy at high sparsities is indeed surprising and worth addressing\n- Discussion of SNIP/GRASP and of Iter SNIP / FORCE is very clear\n- Evaluation of methods is strong, evaluating across different target sparsities, different networks/datasets, and robustness to hyperparameter choices\n\n# Weaknesses\n\n- A discussion/analysis of the differences in behavior between FORCE and Iter SNIP would be warranted, since in the main body of the paper they seem fairly similar in the results. Some discussion of this is presented in App. C4, but this feels a bit lacking in conclusions. Should I always choose FORCE over Iter SNIP? Is there a reason to present Iter SNIP at all?\n- The paper also needs more conceptualization and baselines for what it means to prune \"at initialization\". For VGG, FORCE uses $128\\cdot 300 = 38,400 \\approx 1 \\text{epoch}$ of examples to compute the mask. Learning a mask is in fact a form of training [1]. With seeing this number of examples before computing the mask, it is plausible that a better mask could be found through other simpler means (e.g., training a network and magnitude pruning), or more complex means (e.g., [2] Figure 5 shows a VGG-19 with higher accuracy from a mask on a network that saw 6,400 examples; though [2] doesn't propose a constructive technique, it seems worth considering as an upper bound). I believe the paper would benefit from a more through discussion of what \"at initialization\" actually means, and what appropriate lower/upper bounds for techniques that see large numbers of examples should be.\n\n# Overall recommendation\n\n7: Accept\n\n# Other comments and suggestions\n\n- Small typo: \"We\" is capitalized in the middle of the first sentence of Section 5.\n- Figure 4 middle: the x-axis is very hard to read. Figure 4 right: is there a difference between \"batch\", \"b\", \"iter\", and \"it\"?\n- Figure 4 left: would it be possible to also include the saliency obtained from the FORCE metric in this plot?\n\n# References used in review:\n\n[1] Arun Mallya, Dillon Davis, Svetlana Lazebnik. \"Piggyback: Adapting a Single Network to Multiple Tasks by Learning to Mask Weights\".\n[2] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, Michael Carbin. \"Stabilizing the Lottery Ticket Hypothesis\".\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is growing evidence that optimized deep networks (typically dense in the sense of nonzero parameters) often contain sparse sub-networks that can be trained from scratch to achieve similar performance as the full network. Such “skeletonization” is of obvious importance, given the rate at which deep networks in practice are increasing in size. However, many approaches to find such optimal sub-networks train the full model (and hence implicitly, the intermediate sub-networks as well), which is not a scalable path. 

Some recent works show that skeletonization at initialization may provide all the efficiency benefits of sparsity, while minimally impacting accuracy. This work first notes that accuracy in such approaches degrades significantly beyond a certain level of sparsity (around 95%). One of the ideas of this work is to resurrect parameters that were pruned away earlier in this work’s iterative skeletonization, via an approach called foresight connection sensitivity (FORCE) where the “trainability”  of the pruned network is also taken into consideration. An additional idea is “Iterative SNIP”, building on the SNIP approach of Lee et al. (2019). The empirical improvements, and the observations showing the limitations of SNIP and GRASP in the regime of high sparsity, are useful. 

The evaluation and overall contribution were generally appreciated by the reviewers. 

Decision: Accept (Poster)