Picking Winning Tickets Before Training by Preserving Gradient Flow
Authors: Chaoqi Wang
Guodong Zhang
Roger Grosse
Venue:  (2020)
Keywords: neural network
pruning before training
weight pruning

Abstract: Overparameterization has been shown to benefit both the optimization and generalization of neural networks, but large networks are resource hungry at both training and test time.  Network pruning can reduce test-time resource requirements, but is typically applied to trained networks and therefore cannot avoid the expensive training process. We aim to prune networks at initialization, thereby saving resources at training time as well. Specifically, we argue that efficient training requires preserving the gradient flow through the network. This leads to a simple but effective pruning criterion we term Gradient Signal Preservation (GraSP). We empirically investigate the effectiveness of the proposed method with extensive experiments on CIFAR-10, CIFAR-100, Tiny-ImageNet and ImageNet, using VGGNet and ResNet architectures. Our method can prune 80% of the weights of a VGG-16 network on ImageNet at initialization, with only a 1.6% drop in top-1 accuracy. Moreover, our method achieves significantly better performance than the baseline at extreme sparsity levels. Our code is made public
at: https://github.com/alecwangcq/GraSP.

Published as a conference paper at ICLR 2020
PICKING WINNING TICKETS BEFORE TRAINING BY PRESERVING GRADIENT FLOW
Chaoqi Wang, Guodong Zhang, Roger Grosse University of Toronto, Vector Institute (cquang, gdzhang, rgrosse ccs toronto. edu
ABSTRACT
Overparameterization has been shown benefit both the optimization and gen- eralization of neural networks, but large networks are resource hungry at both training and test time. Network pruning can reduce test-time resource require- ments, but is typically applied to trained networks and therefore cannot avoid the expensive training process. We aim to prune networks initialization, thereby saving resources training time well. Specifically, training requires preserving the gradient flow through the network. This leads simple but effective pruning criterion term Gradient Signal Preservation (GraSP). We empirically investigate the effectiveness of the proposed method with extensive experiments ageNet, using VGGNet and ResNet architectures. Our method can prune 80% of the weights of VGG-16 network on ImageNet at initialization, with only a 1.6% drop in top-1 accuracy. Moreover, our method achieves significantly better performance than the baseline extreme sparsity levels. Our code is made public at: https: / com/ http://wwwwaggg/ra.....
argue that efficient
CIFAR-10, CIFAR-100. Tiny-ImageNet and Im-
INTRODUCTION
Deep neural networks exhibit good optimization and generalization performance in the overpa- rameterized regime (Zhang et al., 2016; Neyshabur et al., 2019; Arora al., 2019; Zhang al.. 2019b), but both training and inference for large networks are computationally expensive. Network pruning (LeCun et al., 1990; Hassibi et al., 1993; Han al., 2015b; Dong et al., 2017: Zeng Urtasun, 2019; Wang et al., 2019) has been shown to reduce the fest-time resource requirements with minimal performance degradation. However, as the pruning is typically done to a trained network, these methods don't save resources at training time. Moreover, it has been argued that it is hard to train sparse architectures from scratch while maintaining comparable performance to their dense counterparts (Han al., 2015a; Li et al., 2016). Therefore, ask: training, so that we can improve computational efficiency at training time?
prune a network prior to
Recently, Frankle & Carbin (2019) shed light this problem by proposing the Lottery Ticket Hypothesis (LTH), namely that there exist sparse, trainable sub-networks (called "winning tickets") within the larger network. They identify the winning tickets by taking pre-trained network and removing connections with weights smaller than a pre-specificed threshold. They then reset the remaining weights to their initial values, and retrain the sub-network from scratch. Hence, they showed that the pre-trained weights are not necessary, only the pruned architecture and the corresponding initial weight values. Nevertheless, like traditional pruning methods, the LTH approach still requires training the full-sized network in order to identify the sparse sub-networks.
Can we identify sparse, trainable sub-networks initialization? This would allow us to exploit sparse computation with specified hardware for saving computation cost. (For instance, Dey et al. (2019) demonstrated 5x efficiency gains for training networks with pre-specified sparsity.) At first glance, randomly initialized network seems to provide little information that we can use to judge the importance of individual connections, since the choice would seem to depend on complicated training dynamics. However, recent work suggests this goal is attainable. Lee al. (2018) proposed the first algorithm for pruning at initialization time: Single-shot Network Pruning (SNIP), which uses connection sensitivity criterion to prune weights with both small magnitude and small gradients.

---

Published as a conference paper at ICLR 2020
Their empirical results are promising in the sense that they can find sparse, trainable net-neeworks at initialization. However, connection sensitivity is sub-optimal as a criterion because the gradient of each weight might change dramatically after pruning due to complicated interactions between weights. Since SNIP only considers the gradient for one weight in isolation, it could remove connections that important to the flow of information through the network. Practically, find that this blocking of information flow manifests as a reduction in the norm of the gradient.
Therefore, we aim to prune connections in way that accounts for their role in the network's gradient flow. Specifically, we take the gradient norm after pruming as our criterion, and prune those weights whose removal will result in least decrease in the gradient norm after pruning. Because we rely on preserving the gradient flow to prune the network, we name our method Gradient Signal Preservation (GraSP). Our approach is easy to implement and conceptually simple. Moreover, the recently introduced Neural Tangent Kernel (NTK) (Jacot et al., 2018) provides tools for studying the learning dynamies in the output space. Building on the analysis of Arora et al. (2019), we show that our pruning criterion tends to keep those weights which will be beneficial for optimization. We evaluate GraSP on CIFAR-IO, CIFAR-I00 (Krizhevsky. 2009), Tiny-ImageNer and ImageNet (Deng et al., 2009) with modern neural networks, such as VGGNet (Simonyan & Zisserman, 2014) and ResNet (He et al., 2016). GraSP significantly outperforms SNIP in the extreme sparsity regime.
2 RELATED WORK AND BACKGROUND
In this section, we review the literature on neural network pruning including pruning after training, pruning during training. dynamic sparse training and pruning before training. We then discuss propagation of signals in deep neural networks and recent works in dynamical isometry and mean- field theory. Lastly, we also review the Neural Tangent Kernel (NTK) (Jacot et al., 2018), which builds up the foundation for justifying our method in Section 4.
2.1 NETWORK PRUNING
After training. Most pruning algorithms (LeCun et al., 1990; Hassibi et al., 1993; Dong et al., 2017; Han et al., 2015b; Li et al., 2016; Molchanov al., 2016) operate on pre-trained network. The main idea is to identify those weights which are most redundant, and whose removal will therefore least degrade the performance. Magnitude based pruning algorithms (Han al., 2015b;a remove those weights which are smaller than a threshold, which may incorrectly measure the importance of each weight. In contrast, llessia-bbased pruning algorithms (LeCun et al., 1990; Hassibi et al., 1993) compute the importance of each weight by measuring how its removal will affect the loss. More recently, Wang et al. (2019) proposed a network reparamcterization based on the Kronecker- factored Eigenbasis for further boosting the performance of Hessian -based methods. However, all the aforementioned methods require pre-training, and therefore aren't 't applicable at initialization.
During training. There are also some works which attempt to incorporate pruning into the training procedure itself. Srinivas & Babu (2016) proposed generalized dropout, allowing for tuning the individual dropout rates during training, which can result in sparse network after training. Louizos et al. (2018) proposed a method for dealing with discontinuity in training Lo norm regularized networks in order to obtain sparse networks. Both methods require roughly the same computational cost as training the full network.
Dynamic Sparse Training Another branch of pruning algorithms is Dynamic Sparse Training methods, which will dynamically change the weight sparsity during training. Representative works, such as Bellec al. (2018); Mocanu et al. (2018); Mostafa & Wang (2019); Dettmers & Zettlemoyer (2019), follow a iere--rddisrrbbuteeeeroooe cycle for pruning. Among them, Dettmers & Zettlemoyer (2019), proposed the sparse momentum algorithm, which dynamically determines the sparse mask based on the mean momentum magnitude during training. However, their method requires maintaining the momentum of all the weights during training, and thus does not save memory. These techniques generally achieve higher accuracy compared with fixed sparse connectivity, but change the standard training procedure and therefore do not enjoy the potential hardware acceleration.
Before training. Pruning at initialization is more challenging because need to account for the effect on the training dynamics when removing each weight. There have been several attempts to conduct pruning before training. Frankle & Carbin (2019); Frankle et al. (2019) proposed and
2

---

Published as a conference paper at ICLR 2020
validated the Lottery Ticket Hypothesis (LTH), namely that the network structure found by traditional pruning algorithms and the corresponding initialization are together sufficient for training the sub- network from scratch. Lee et al. (2018) proposed the SNIP algorithm, which was the first attempt to directly identify trainable and sparse sub-networks at initialization time. Their method was based on connection sensitivity, which aims preserve the loss after pruning, and achieved impressive results. Concurrently to our work, Lee et al. (2019b) studied the pruning problem from a signal propagation perspective, and proposed to use an orthogonal initialization ensure faithful signal propagation. Though their work shares the same spirit as our GraSP algorithm, they focused on the weight initialization scheme, while we focus on the pruning criterion.
2.2 SIGNAL PROPAGATION AT INITIALIZATION
Our pruning criteria shares the same spirit as recent works dynamical isometry and mean-field theory (Saxe et al., 2013; Xiao et al., 2018; 8; Yang & Schoenholz, 2017; Poole et al., 2016) where they derived initialization scheme theoretically by developing a mean field theory for signal propagation and by characterizing singular values of the input-output Jacobian matrix. Particularly, Xiao et al. (2018) successfully train 10,0rs-layers vanilla ConvNets with specific initialization scheme. Essen- tially, this line of work shows that the trainability of neural network at initialization is crucial for final performance and convergence. While they focus on address the trainability issue of very deep networks, we aim to solve the issue of sparse neural networks. Besides, they measure the trainability by examining the input-output Jacobian while we do that by checking the gradient norm. Though different, gradient norm is closely related the input-output Jacobian.
2.3 NEURAL TANGENT KERNEL AND CONVERGENCE ANALYSIS
Jacot et al. (2018) analyzed the dynamics of neural net training by directly analyzing the evolution of the network's predictions in output space. Let L denote the cost function, X' the set of all training samples, 2 = f(X:; 0) E R the outputs the neural network, and and n the output space
dimension and the number of training examples. For step of gradient descent, the change to the network's 's predictions can be approximated with a first-order Taylor approximation:
f(x; 0.+1) = f(x; 0,) VVV,,,
(1)
where the matrix 0,(X, X) is the Neural Tangent Kernel (NTK) at time step t:
(xX, Oo Vof 0,)T E gnkxnn
(2)
where f 0) denotes the network Jacobian over the whole training set. Jacot et al. (2018) showed that for infinitely wide networks, with proper initialization, the NTK exactly captures the output space dynamics throughout training. In particular, (, X)) remains constant throughout training. Arora et al. (2019) used the NTK to analyze optimization and generalization phenomena, showing that under the assumptions of constant NTK and squared error loss, the training dynamics can be analyzed in closed form:
|| f(x:
Σ (1 nd (u.))) #
where y E Rn is all the targets, θ = UAU = =E u is the eigendecomposition, and e is a bounded error term. Although the constant NTK assumption holds only in the infinite width limit, Lee et al. (2019a) found close empirical agreement between the NTK dynamics and the true dynamics for wide but practical networks, such wide ResNet architectures (Zagoruyko & Komodakis, 2016).
REVISITING SINGLE-SHOP NETWORK PRUNING (SNIP)
Single-shot network pruning was introduced by Lee et al. (2018), who used the term to refer both to the general problem setting and their specific algorithm. To avoid ambiguity, we refer to the general problem of pruning before training as foresight pruning. For completeness, we first revisit the formulation of foresight pruning, and then point out issues of SNIP for motivating our method.
3

---

Published as a conference paper at ICLR 2020
Algorithm 1 Gradient Signal Preservation (GraSP).
Require: Pruning ratio p. training data D, network f with initial parameters Oo
1: D, = {(x; y:) R== ~ DD
b Sample a collection of training examples See Algorithm 2 b Compute the importance of each weight
2: Compute the Hessian- -oriiangggaientttt product Hg (see Eqn. (8))
3: S(-0,) = 0, C Hg
4: Compute Pch percentile of (0)0g) as
5: m = ((-0)) <
> Remove the weights with smallest importance
6: Train the network fmoo D until convergence.
Problem Formulation. Suppose we have a neural network f parameterized by E Red, and objective is to minimize the empirical risk [(0) = N Σ, (x;; 0), v+)] given a training set D {xx,, H.) Then, the foresight pruming problem can be formulated as:
min (xxx)>> [e (ʃ (x; A(m, .)] 8.t. ||m]lo/ 1 mc (0.1))
(4)
where [p-d] is the number of weights to removed, and A is a known training algorithm (e.g. SGD), which takes the mask m (here we marginalize out the initial weights 6, for simplicity), and returns the trained weights. Since globally minimizing Eqn. intractable, we are instead interested in heuristics that result in good practical performance.
Revisiting SNIP. SNIP (Lee et al., 2018) was the first algorithm proposed for foresight pruning, and it leverages the notion of connection sensitivity to remove unimportant connections. They define this in terms of how removing a single weight fg in isolation will affect the loss:
(())) L(o. + cōg)
0g ac
S(O,)
lim c00
(5)
80,
where 0g is the Qua element of Og, and 8, is a one-hot vector whose yea, element equals 0g. Essentially, SNIP aims to preserve the loss of the original randomly initialized network.
Preserving the loss value motivated several classic methods for pruning a trained network, such as optimal brain damage (LeCun et al., 1990) and optimal brain surgery (Hassibi et al., 1993). While the motivation for loss preservation of a trained network is clear, it is less clear why this is good criterion for foresight pruning. After all, at initialization, the loss no better than chance. We argue that at the beginning of training, it is more important to preserve the training dynamics than the loss itself. SNIP does not do this automatically, because even removing a particular connection doesn't t affect the loss, it could still block the flow of information through the network. For instance, noticed in our experiments that SNIP with a high pruning ratio (e.g. 99%) tends to climinate nearly all the weights in particular layer, creating a bottleneck in the network. Therefore, would prefer a pruning criterion which accounts for how the presence or absence of one connection influences the training of the rest of the network.
GRADIENT SIGNAL PRESERVATION
We now introduce and motivate our foresight pruning criterion, Gradient Signal Preservation (GraSP). To understand the problem we are trying to address, observe that the network after pruning will have fewer parameters and sparse connectivity, hindering the flow of gradients through the network and potentially slowing the optimization. This reflected in Figure 2, which shows the reduction in gradient norm for random pruning with various pruning ratios. Moreover, the performance of the pruned networks is correspondingly worse (see Table 1).
Mathematically, larger gradient norm indicates that, to the first order, each gradient update achieves a greater loss reduction, as characterized by the following directional derivative:
L (0 + cV) - L()) V VL(
AC lim c++
(6)
We would like to preserve or even increase (if possible) the gradient flow after pruming (i.e., the gradient flow of the pruned network). Following LeCun et al. (1990), cast the pruning operation
4

---

Published as a conference paper at ICLR 2020
Algorithm 2 Hessian-gradient Product.
Require: A batch of training data Dr. network f with initial parameters On. loss function L I: (())) = E (xx,))>D,(( [x[](x; 0o), v)]
D Compute the loss and build the computation graph > Compute the gradient of loss function with respect to do Compute the Hessian vector product of Hg
2: g = (())), 0)) 0))
3: Hg = grad(g stop_ 0n)
4: Return Hg
as adding a perturbation ò to the initial weights. We then use a Taylor approximation to characterize how removing one weight will affect the gradient flow after pruning:
S (8) = AC + +ō) - AC((,) = 28 v2 +=
+
Const
2 Hg 1))
28
where S( approximately measures the change to (6). The Hessian matrix H captures the dependen- cies between different weights, and thus helps predict the effect of removing multiple weights. When Hi is approximated as the identity matrix, the above criterion recovers SNIP up to the absolute value (recall the SNIP criterion is 18 g)). However, it has been observed that different weights are highly coupled (Hassibi et al., 1993), indicating that H is in fact far from the identity.
GraSP uses eqn. (7) as the measure of the importance of each weight. Specifically, if S(0) is negative, then removing the corresponding weights will reduce the gradient flow, while if it is positive, it will increase the gradient flow. We prefer to first remove those weights whose removal will not reduce the gradient flow. For each weight, the importance can be computed in the following way (by abuse of notation, we use bold S to denote vectorized importance):
S(-0) = - Hg
For a given pruning ratio p. we obtain the resulting pruning mask by computing the importance score every weight, and removing the bottom p fraction the weights (see Algorithm 1). Hence, GraSP takes the gradient flow into account for pruning. GraSP is efficient and easy to implement; the -essian-gradient product can be computed without explicitly constructing the Hessian using higher-order automatic differentiation (Pearlmutter, 1994; Schraudolph, 2002).
4.1 UNDERSTANDING GRASP THROUGH LINEARIZED TRAINING DYNAMICS
The above discussion concerns only the training dynamics at initialization time. To understand the longer-term dynamics, we leverage the recently proposed Neural Tangent Kernel (NTK), which has been shown to be able to capture the training dynamics throughout training for practical networks (Lee al., 2019a). Specifically, error changes throughout the training process, which only depends on time step f. training targets Y and the NTK O. Since the NTK stays almost constant for wide but practical networks (Lee et al., 2019a), egg., wide ResNet (Zagoruyko & Komodakis, 2016), eqn. is fairly accurate in those settings. This shows that NTK captures the training dynamics throughout the training process. Now we decompose eqn. (6) in the following form:
introduced in section 2.3, eqn. (3) characterizes how the training
VL()) VC(0) = V C O(X, (U"
(2) (U = Σ Ar V
(9)
By relating it to eqn. (3), we can see that GraSP implicitly encourages C to be large in the directions corresponding output space gradients. Since larger eigenvalue directions of O train faster according to eqn. (3), this suggests that GraSP should result in efficient training. In practice, the increasing of gradient norm might be achieved by increasing the loss. Therefore, we incorporate a temperature term on the logits to smooth the prediction, and so as to reduce the effect introduced by the loss.
5 EXPERIMENTS
In this section, we conduct various experiments to validate the effectiveness of our proposed single- shot pruning algorithm in terms of the test accuracy vs. pruning ratios by comparing against.
5

---

Published as a conference paper at ICLR 2020
Table 1: Comparisons with Random Pruning with VGG19 and ResNet32 CIFAR-
Dataset
CIFAR-10
CIFAR: 100
Pruming ratio
95%
98%
99%
99.5%
95%
98%
99%
99.5%
Random Pruning (VGG19)
89.47(0.55
86.71
82.21(0.5)
72.89(16)
66.36(0.3)
61.33(0.1) 1)
35. 18(16)))))
36.88(6.8)
GraSP (VGGI9)
93.04(0.2)
(2.1
91.33(0.1)
88.6100.7)
71.230.1)
68.90K0.5)
66.15(0.2)
60.21(0.1)
Random Pruning (ResNer32)
89.75(0.)
85 90(0.4
71.78(9.9)
50.08(7.0)
50.92(0.9) 64.72(0.22)
34.62(2.8)
(8.51(0.43)
GraSP (ResNer32)
91.39X0.3)
88.81(0.1)
85.43(0.5)
80.5010.3)
66.5000.1)
58.43(0.4)
48.73(0.3)
36.55(2.4)
Table 2:
Test accuracy of pruned VGG19 and ResNet32
CIFAR-10 and CIFAR-I00 datasets. The bold
number is higher one between the accuracy of GraSP and that of SNIP.
Dataset
CIFAR-10
CIFAR-100
Pruning ratio
90%
95%
98%
90%
95%
98%
VGG19 (Baseline)
94.23
74.16
OBD (LeCun et ul., 1990)
93.74
93.58
93.49
73.83
71.98
67.79
MLPrune (Zeng Urtasun, 2019)
93.83
93.69
93.49
73.79
73.07
71.69
LT (original initialization)
93.51
92.92
92.34
72.78
71.44
68.95
LT (reset to epoch 5)
93.82
93.61
93.09
74.06
72.87
70.55
DSR (Mostafa & Wang. 2019)
93.75
93.86
93.13
72.31
71.98
70.70
SET Mocanu et ul. (2018)
92.46
91.73
89.18
72.36
69.81
65, .4
Deep-R (Bellec al., 2018)
86.77
63.46
59.58
SNIP (l.ce al., 2018)
93.6
93.43-+0.20
92.05=0.28
72.84++0.22
71.83-
58.46+t
GraSP
93.30++0.14
93.04++0.18
9..19:0.12
71.95++0.18
71.23-0.12
68.90
ResNet32 (Baseline)
94.80
74.64
OBD (LeCun 1990)
94.17
93.29
90.31
71.96
68.73
60.65
MLPrune (Zeng & Urtasun, 2019)
94.21
93.02
89.65
72.34
67.58
59.02
LT (original initialization)
92.31
91.06
88.78
68. 99
65.02
$7.37
LT (reset to epoch 5)
93.97
92.46
89.18
71.43
67.28
58.95
DSR (Mostafa Wang, 2019)
92.97
91.61
61.24
SET Mocanu al. (2018)
92.30
90.76
88.29
69.66
67.41
62.25
Deep-R (Bellec al., 2018)
91.62
89.84
86.45
66.78
63,90
58.47
SNIP (L.ee et al., 2018)
92.59+00.10
91.01++0.21
87.51 0.331
68.89++0.45
(6.22-0.69
54.81+1443
GraSP
92.38=00211
91.39:10.25
88.81=0.14
69.24:10.24
66.50=0.11
58.43++0.43
SNIP. We also include three Dynamic Sparse Training methods, DSR (Mostafa & Wang. 2019), SET (Mocanu et al., 2018) and Deep-R R (Bellec et al., 2018). We further include two traditional pruning algorithms (LeCun et al., 1990; Zeng Urtasun, 2019), which operate on the pre-trained networks, for serving as an upper bound for foresight pruning. Besides, we study the convergence performance of the sub-networks obtained by different pruning methods for investigating the relationship between gradient norm and final performance. Lastly, we study the role of initialization and batch sizes in terms of the performance of GraSP for ablation study.
5.1 PRUNING RESULTS ON MODERN CONVNETS
To evaluate the effectiveness of GraSP on real world tasks, we test GraSP on four image classification datasets, CIFAR-10/100 Tiny-ImageNet and ImageNet, with two modern network architectures, VGGNet and ResNet'. For the experiments batch with ten times of the number of classes for both GraSP and SNIP according to Lee et al. (2018). The pruned network is trained with Kaiming initialization (He et al., 2015) using SGD for 160 epochs for 0.1 and batch size 128. The learning rate decayed by a factor of 0.1 at 1/2 and 3/4 of the total number of epochs. Moreover, we run each experiment for 3 trials for obtaining more stable results. For ImageNet,
CIFAR- 10/100 and Tiny-ImageNet, we use mini-
and 300 epochs for Imy-ImmaeNet, with an initial learning rate of
adopt the Pytorch (Paszke al., 2017) official implementation, but used more epochs for training according to Liu et al. (2019). Specifically, we train the pruned networks with SGD for 150 epochs, and decay the learning rate by factor of 0.1 every 50 epochs.
We first compre GraSP against random pruning, which generates the mask randomly for given pruning ratio. The test accuracy is reported Table 1. We can observe GraSP clearly outperforms
For experiments on CIFAR- 10/100 and Iny-ImmaeNNt, we adopt ResNet32 and double the number of filters in each convolutional layer for making it able to overfit CIFAR-100. For SNIP, adopt the implementation public http://gittuh..co/miiaaaaua

---

Published as a conference paper at ICLR 2020
Table 4: Test accuracy pruned VGGI9 and ResNet32 on Tiny-ImageNet dataset. The bold number is the higher one between the accuracy of GraSP and that of SNIP.
Network
VGG19
ResNet32
Pruning
90%
95%
98%
85%
90%
95%
VGG19/ResNet32 (Bascline)
61.38
62.89
OBD (LeCun al., 1990)
61.21
60.49
54,98
58.55
56.80
51.00
MI.Prune (Zeng & Urtasun, 2019)
60.23
59.23
55,55
58 86
57.62
$1.70
LT (original initialization)
60.32
59.48
55.12
56.52
54.27
49.47
LT (resct to epoch 5)
61.19
60.57
56.18
60.31
57.77
51.21
DSR (Mostafa Wang. 2019)
62.43
59,81
58.36
57.08
57.19
56.08
SET Mocanu et ul. (2018)
62.49
59,42
56,22
57.02
56,92
56.18
Deep-R (Bellec et al., 2018)
55.64
52.93
49.32
53.29
52.62
$2.00
SNIP (Lee et al., 2018)
61.02:10.41
59.27-10.39
48.95
56.33:10,24
55.43-0.14
49.57-10.44
GraSP
60.76++0.23
59.50++0.33
57.28 0.34
57.25++0.11
55.53 0.11
51.34++.299
random pruning, and the performance gap can be up to more than 30% in terms of test accuracy. We further compare GraSP with more competitive baselines on CIFAR-10/100 and for pruning ratios {85%, 90%, 95%, 98%), ). and the results can be referred in Table 2 and 4. When the pruning ratio is low, i.c. 85%, 90%, both SNIP and GraSP can achieve very close results to the baselines, though still do not outperform pruning algorithms that operate trained networks, as expected. However, GraSP achieves significant better results for higher pruning ratios with more complicated networks (e.g. ResNet) and datasets (e.g. CIFAR-100 and Tiny-ImageNet), showing the advantages of directly relating the pruning criteria with the gradient flow after pruning. Moreover, in most cases, notice that either SNIP or GraSP can match or even slightly outperform LT with original initialization, which indicates that both methods can identify meaningful structures. We further experiment with the late resetting as suggested in Frankle al. (2019) by resetting the weights of the winning tickets to their values at epoch. By doing so, we observe boost in the performance of the LT across all the settings, which is consistent with (Frankle et al., 2019). As for the comparisons with Dynamic Sparse Training (DST) methods, DSR is the best performing one, and also we can observe that GraSP is still quite competitive to them even though without the flexibility to change the sparsity during training. In particular, GraSP can outperform Deep-R R in almost all the settings, and surpasses SET in more than half of the settings.
However, the above three datasets overly simple and small-scale to draw ro- bust conclusions, and thus conduct further experiments on ImageNet using ResNet-50 and VGG16 with pruning ratios {60%, 80%, 90%) to validate the effective- ness of GraSP. The results are shown in Table 3, we can see that when the pruming ratio 60%, both SNIP and GraSP can achieve very close performance to the orig- inal one, and these two methods perform increase the pruning ratio, we observe that GraSP surpasses SNIP more and more. When the pruning ratio is 90%, GraSP can beat SNIP by 6.2% for ResNet-50 and 4.7% for VGG16 in t accuracy, showing the advantages of GraSP at larger pruning ratios. We seek to investigate the reasons behind in Section 5.2 for obtaining a better understanding on GraSP.
Table 3: Test accuracy ResNet-50 and VGG16 on Ima- geNet with pruning ratios 60%, 80% and 90%.
Pruning ratios
60%
80%
90%
Accuracy
top-1
top-5
top-1
top5
top-1
top5
ResNet-50 (Baseline)
75.70
92.81
SNIP (Lee el 2018)
73.95
91.97
69.67
89.24
61.97
82.90
GraSP
74,02
91.86
72.06
90.82
68.14
88.67
VGG16 (Baseline)
73.37
91.47
SNIP (Loc et al., 2018)
72.95
91.39
69.96
89.71
65.27
86,
GraPP
72.91
90.58
69.94
almost the same. However,
5.2 ANALYSIS ON CONVERGENCE PERFORMANCE AND GRADIENT NORM
Based on our analysis in Section 4.1 and the observations in the previous subsection, we conduct further experiments on CIFAR- 100 with ResNet32 to investigate where the performance gains come from in the high sparsity regions. We present the training statistics in terms of the training and test loss in Figure/ 1. We observe that the main bottleneck of pruned neural networks underfitting, and thus support the network pruned with GraSP can achieve much lower loss for both training and testing and the decrease in training loss is also much faster than SNIP.
optimization considerations when deriving the pruning criteria. As a result,

---

Published as a conference paper at ICLR 2020
Training loss
3.5
Testing loss
Relative grad nom
GraSP
GraSP SNIP
Loss
Reodl ni
2.5
0
50
100
150
50
100
150
80.0
82.5
85.0
87.5
90.0
92.5
95.0
97.5
100.0
Epochs
Epochs
Pruning ratio (%)
Figure The gradient norm ResNet32 after pruning on CIFAR- 100 of various pruning ratios. Shaded area is the 95% confidence interval calculated with 10 trials.
Figure 1: The training and testing loss on 1-FAR-100 of SNTP and GraSP with ResNet32 and pruning ratio of 98%.
CIFAR-10, ResNet-32
CIFAR-10, VGG19
CIFAR-10D, ResNet-32
CIFAR-100, VGG19
100
100
100
100
Remaining weights (%)
Grasp
SNIP
80
40
40
40
0
0
0
0
Layer index
Layer index
Layer index
Layer index
Figure 3: The portion of remaining weights at each layer after pruning with a pruning ratio of 95%.
Besides, we also plot the gradient norm of pruned networks at initialization for a ResNet32 on CIFAR-100. The gradient norm is computed as the average of the gradients over the entire dataset, and we normalize the gradient of the original network to be 1. We run each experiment for 10 trials in order to obtain more stable results. We observe that both SNIP and GraSP result in lower gradient norm at high sparsity (e.g. 3. but GraSP can better preserve the gradient norm after pruning, and also yield better results than SNIP at the high sparsity regions. Moreover, in these high sparsity regions, the pruned network usually underfits the training data, and thus the optimization will be problem. The randomly pruned network has much lower gradient norm and performs the worst. In contrast, the network pruned by GraSP can start with a higher gradient norm and thus hopefully more training progress can be made as evidenced by our results in Figure
5.3 VISUALIZING THE NETWORK AFTER PRUNING
In order to prohe the difference of the network pruned by SNIP and GraSP, we present the portion of the remaining weights at each layer of the sparse network obtained by SNIP and GraSP in Figure. 3. We observe that these two pruning methods result in different pruning strategies. Specificallyy, GraSP aims for preserving the gradient flow after pruning, and thus will not prune too aggressively for each layer. Moreover, it has been known that those convolutional layers at the top usually learn highly sparse features and thus more weights prune most of the weights at the top layers, but GraSP will preserve more weights than SNIP due to the consideration of preserving the gradient flow. In contrast, SNIP is more likely prune nearly all the weights in top layers, and thus those layers will be the bottleneck of blocking the information flow from the output layer to the input layer.
be pruned (Zhang et al., 2019a). As result, both methods
5.4 EFFECT OF BATCH SIZE AND INITIALIZATION
We also study how the batch size and initializa- tion will affect GraSP on CIFAR- 10 and CIFAR- 100 with ResNet32 for showing the robustness to different hyperparameters. Specifically, we test GraSP with three different initialization meth- ods: Kaiming normal (He et al., 2015), Nor- mal (0 0.1), and Xavier normal (Glorot & Bengio, 2010), well different mini-batch sizes. We present the mean and standard variance
Table 5: Mean and standard variance of the test accuracy CIFAR-10 10 and CIFAR- 100 with ResNet32.
CIFAR-10
CIFAR-100
60%
90%
60%
90%
Kaiming
93:42 1: 0.39
92 1 0.39
71.60
0.65
68.93 1: 0.36
Normal
93.31 2: 0,36
92.13 1 0.36
71.48
0.60
67.98
0.83
Xavier
71.10
68.11
8

---

Published as a conference paper at ICLR 2020
of the test accuracy obtained with different initialization methods and by varying the batch sizes in Table 5. For CIFAR-I0 10 and CIFAR-100, we use batch sizes {100, 400, ... 25600, 50000) and {1000, 4000, 16000, 32000, 50000} respectively. We observe that GraSP can achieve reasonable performance with different initialization methods, and also the effect of batch size is minimal for net- works pruned with Kaiming initialization, which is of the most commonly adopted initialization techniques in training neural networks.
DISCUSSION AND CONCLUSION
We propose Gradient Signal Preservation (GraSP), a pruning criterion motivated by preserving the gradient flow through the network after pruning. It can also be interpreted aligning the large eigenvalues of the Neural Tangent Kernel with the targets. Empirically, GraSP is able to prune the weights of network initialization, while still performing competitively traditional pruning algorithms, which requires first training the network. More broadly, foresight pruning can be a way for enabling training super large models that no existing GPUs can fit in, and also reduce the training cost by adopting sparse matrices operations. Readers may notice that there is still a performance gap between GraSP and traditional pruning algorithms, and also the LT with late resetting performs better than LT with original initialization. However, this does not negate the possibility that foresight pruning can match the performance of traditional pruning algorithms while still enjoying cheaper training cost. As evidence, Evei et al. (2019) show that there exists linear and monotonically decreasing path from the sparse initialization to the solution found by pruning the fully-trained dense network, but current optimizers fail to achieve this. Therefore, designing better gradient-basee optimizers that can exploit such paths will also be a good direction to explore.
REFERENCES
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In Proceedings of the 36th International Conference on Machine Learning, pp. 322-332, 2019.
Guillaume Bellec, David Kappel, Wolfgang Maass, and Robert Legenstein. Deep rewiring: Training very sparse deep networks. In International Conference on Learning Representations, 2018. URL
https: httpp:://ppeeeeeeeee http:://ppppeeeee..em net forumm BotoormmiddB__OOO111111
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and puttern recognition, pp. 248 2003-2552222 2009.
Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing performance. arXiv preprint 1rXiv:1977.048400 2019.
Sourya Dey, Kuan- Wen Huang, Peter A Beerel, and Keith M Chugg. Pre-defined sparse neural networks with hardware acceleration. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 2019.
Xin Dong, Shangyu Chen, and Sinno Pan. Learning to prune deep neural networks via layer-wise optimal brain surgeon. In Advances in Neural Information Processing Systems, pp. 4857-4867, 2017.
Utku Evci, Fabian Pedregosa, Aidan Gomez, and Erich Elsen. The difficulty of training sparse neural networks. arXiv preprint arXiv: 10732, 2019.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019. URL https:
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. The lottery ticket 2019.
hypothesis scale. arXiv preprint

---

Published as a conference paper at ICLR 2020
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256, 2010.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. International Conference on Learning Representations, 2015a.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances in neural information processing systems, pp. 1135-1143, 2015b.
Babak Hassibi, David G Stork, and Gregory J Wolff. Optimal brain surgeon and general network pruning. In IEEE international conference on neural networks, pp. 293-299. IEEE, 1993.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp.
2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: generalization neural networks. In Advances in neural information processing systems, pp. 8571-8580, 2018
Convergence and
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Yann LeCun, John S Denker, and Sara Solla. Optimal brain damage. In Advances in neural information processing systems, pp. 598-559866 605, 1990.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Jascha Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. arXiv preprint arXiv: /902.06720 2019a.
and Jeffrey
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr. Snip: Single-shot network pruning based on connection sensitivity. International Conference on Learning Representations, 2018.
Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip HS Tom. A signal propagation perspective for pruning neural networks at initialization. arXiv preprint arXiv:1906.06:33 2019b.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. International Conference on Learning Representations, 2016.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. International Conference on Learning Representations, 2019.
Christos Louizos, Max Welling, and Diederik Kingma. Learning sparse neural networks through 1_0 regularization. International Conference Learning Representations, 2018 88
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):3383, 2018.
Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz. Pruning convolutional neural networks for resource efficient inference. International Conference on Learning Represen- fations, 2016.
Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. International Conference Machine Learning, 2019.
10

---

Published as a conference paper at ICLR 2020
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of pwer-aaramtttizzation in generalization of neural networks. In International Conference on Learning Representations, 2019. URL https:
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.
Barak A Pearlmutter. Fast exact multiplication by the Hessian. Neural computation, 6(1):147-160, 1994.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein. and Surya Ganguli. Exponential expressivity in deep neural networks through transient chaos. In Advances in neural information processing systems, pp. 3360-3368, 2016.
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamies of learning in deep linear neural networks. arXiv preprint arXiv: 1312.610 2013.
Nicol N Schraudolph. Fast curvature matrix-vector products for second-order gradient descent. Neural computation, 14(7):1723-133, 2002.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. International Conference on Learning Representations, 2014.
Suraj Srinivas and Venkatesh Babu. Generalized dropout. arXiv preprint arXiv:1611.0677 2016.
Chaoqi Wang, Roger Grosse, Sanja Fidler, and Guodong Zhang. EigenDamage: Structured pruning in the frantoeer-factored eigenbasis. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 6566-6575. PMLR, 2019. URL http: http:::://poocediggs.... mll.prres/vve vvtss//vv///// /ttp/////////g// html.
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel Schoenholz, and Jeffrey Pennington. Dynamical isometry and a mean field theory of cnns: How to train 10,000-layer vanilla convo- lutional neural networks. In International Conference Machine Learning, pp. 5393-54900 2018.
Ge Yang and Samuel Schoenholz. Mean field residual networks: On the edge of chaos. In Advances in neural information processing systems, pp. 7103-7114, 2017.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In BMVC, 2016.
Wenyuan Zeng and Raquel Urtasun. MLPrume: Multi-layer pruning for automated neural network compression, 2019. URL https: http///wpeeeeeeeeeeeeeeee..eeeee wwwp:ewwwwwwweeeeonoeuouuaa.aa
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Representations, 2016.
Chiyuan Zhang, Samy Bengio, and Yoram Singer. Are all layers created equal? arXiv preprint arXiv:1902.01996, 2019a.
Guodong Zhang, James Martens, and Roger Grosse. Fast convergence of natural gradient descent for overparameterizee neural networks. arXiv preprint mr:iv:99905 10961, 2019b.


Reviews:
[{"review_id": "S1e9hXy0FS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a method to prune networks at initialization in a way that (mostly) preserves the gradient flow through the resulting pruned network. This is a direct improvement over previous methods (e.g. SNIP) which have no guarantees that pruned connections will break the gradient flow and thereby harm learning.\n\nI quite like this paper, the motivation and results are convincing and it is well presented. The writing is excellent for most of the paper. From section 5 onwards the writing does need quite a bit of editing, as its quality is significantly reduced from what came before.\n\nSome detailed comments:\n- Figure 1 is very nice and really clarifies the idea!\n- In paragraph below Equation (8): what does \"can be computed by backward twice\" mean?\n- Please specify where the equalities in equation (9) are coming from.\n- Table 3 & 4: Why are the pruning ratios different for each model?\n- Table 3: Why are values missing for the baseline for 80% and 90%?\n- Section 5.2: \"We observed that, the main bottleneck or pruned... when deriving the pruning criteria\": it's not clear where this conclusion is coming from.\n- Table 5 has no batch size results, even though you're referencing them in the text.\n\nAnd some minor comments to help with the writing:\n- Intro: \"As shown in Dey et al. (2019) that with pre-specified sparsity, they can achieve\" would read better as \"As shown by Dey et al. (2019), with pre-specified sparsity one can achieve\"\n- Equation (3): Clarify that this is a function of $t$\n- Sentence below Equation (6): \"of the pruned network, and thus our goal\" remove the \"and thus\"\n- Table 1: Specify that you're reporting accuracy.\n- Section 4.1: \"e.g. wide ResNet (Zagaruyko & Komodakis, 2016), and thus we can regard\" remove the \"and thus\"\n- Sentence below equation (9): \"encouraging the eigenspace of \\Theta align\" add a \"to\" before \"align\"\n- Sentence before section 5: \"it will encourage the eigenspace of the NTK distributing large eigenvalues in the direction of Y, which will in turn accelerates the decrease of the loss (Arora et al., 2019) and benefits to the optimization in A\" would read better as \"it will encourage the eigenspace of the NTK to distribute large eigenvalues in the direction of Y, which in turn accelerates the decrease of the loss (Arora et al., 2019) and benefits the optimization in A\"\n- Throughout section 5, write it in present tense rather than past tense. e.g. \"In this section, we conduct various experiments\" instead of \"In this section, we conducted various experiments\"\n- Sentence below table 2: you have \"the the\"\n- Second paragraph of section 5.1: \"We can observe GraSP outperform random pruning clearly\" would read better as \"We can observe GraSP clearly outperforms random pruning\"\n- Second paragraph of section 5.1: \"In the next, we further compared\" remove \"In the next\"\n- Second paragraph of section 5.1: \"Besides, we further experimented with the late resetting\" remove \"Besides\"\n- Paragraph above section 5.2: \"GraSP surpassing SNIP\" use \"surpasses\" instead\n- Paragraph above section 5.2: \"investigate the reasons behind in Section 5.2 for promoting better understanding\" would read better as \"investigate the reasons behind this in Section 5.2 for obtaining a better understanding\"\n- Section 5.2: \"We observed that, the main bottleneck\" -> \"We observe that the main bottleneck\"\n- Section 5.2: \"Besides, we also plotted the the gradient norm of the pruned\", remove \"Besides\" and the extra \"the\"\n- Section 5.2: \"the average of the gradients of the entire dataset\" use \"over the entire dataset\"\n- Section 5.2: \"hopefully more training progress can make as evidenced\" would read better as \"hopefully more training progress can be made as evidenced\"\n- Section 5.3 title would be better using \"Visualizing\" instead of \"Visualize\"\n- Section 5.3: Join the first two sentences with a comma into a single sentence.\n- Section 5.3: \"In contrast, SNIP are more likely\" -> In contrast, SNIP is more likely\"\n- Section 5.4: \"for ablation study\" would read better as \"via ablations\"\n- Section 5.4: \"we tested GraSP with three different initialization methods;\" use a \":\" instead of \";\"\n- Section 6: \"Besides, readers may notice that\", remove the \"Besides\"\n- Section 6: \"traditional pruning algorithms while still enjoy the cheaper training cost. As an evidence,\" would read better as \"traditional pruning algorithms while still enjoying cheaper training costs. As evidence,\"\n- Your citation for Evci et al. (2019) is missing the publication venue/arxiv ID.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkgFzZMcFB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe paper proposes a new prunning criterion that performs better than Single-shot Network Pruning (SNIP) in prunning a network at the initalization. This is an important and potentially very impactful research direction, The key idea is to optimize the mask for the loss decrease after an infinimitesal step, rather than for the preservation of loss after prunning. While with the benefit of hindsights it might seem simple, it is a clever innovation. However, I am not convinced by the theoretical explanation and some of the experimental results (see detailed comment below). Based on this I am leaning at the moment towards rejecting the paper. I will be happy to revisit my score if these concerns are addressed.\n\nDetailed comments:\n\n1. I am not sure that NTK based analysis helps explain the efficacy of the method. An increase of the (matrix) norm of the NTK kernel can be achieved by simply scaling up by a constant scalar the logits weights (see for instance https://arxiv.org/abs/1901.08244). Or equivalently (comparing the resulting learning dynamics in NTK, as also can be read from (3)), by just increasing the learning rate. In other words, I could just prune weights randomly, and then scale up logits' weights, and end up with the same effect on the NTK kernel. I think that for this argument to work, NTK kernel should change in a scale-invariant manner. This would correspond to a better conditioning of the loss surface (because Hessian has the same eigenspectrum as the NTK kernel under the NTK assumption), which is a scale invariant property.\n\n2. From the Figure 2 it seems SNIP-prunned network underfits data severly. Could you add training accuracy to the Tables (maybe in the Supplement)? If in all cases when GraSP wins, it is due to underfitting, this should be commented on. Is it common for prunning algorithms to result in underfitting, or is achieving generalization a larger challenge? Could the bad performance at high prunning ratios of SNIP be due to a conflation of two effects: (1) \"good\" prunning, but (2) lowering the effective learning rate (given the gradient norm is low)? Would, for high prunning ratios, a tuned learning rate improve SNIP performance/reduce underfitting? \n\n3. In Table 5 is the batch-size used for training of the network, or only for the computation of the Hessian-vector product in the GraSP procedure? If for training, then the relatively small spread of results is a bit surprising given results by Keskar (https://arxiv.org/abs/1609.04836)\n\nEdit\n\nThank you for the rebuttal. Raise my score. I agree with Reviewer #4 that increasing gradient norm at initialization is a promising direction on its own, which warrants acceptance.\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BJlsJthO5S", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a novel one-shot-pruning algorithm which improves the training of sparse networks by maximizing the norm of the gradient at initialization. The utility of training sparse neural networks and shortcomings of dense-to-sparse algorithms like Pruning, LotteryTicket are nicely motivated at introduction. The pruning criterion is motivated by the first order approximation of the change in the gradient norm when a single connection is removed, though the results show that removing many connections together with GraSP increases the total gradient norm therefore allowing the loss to decrease faster. Experiments suggest employing such pruning algorithm improves final performance over two baselines: random and SNIP. \n\nThough I find the proposed method intriguing and well motivated, experiments section of the paper misses some important sparse training baselines and needs some improvement. I am willing to increase my score given my concerns/questions below are addressed. \n\n(1) The paper doesn't mention some important prior work on the topic. Since the paper focuses on end-to-end sparse training, the following sparse training methods needs to be considered and compared with:\n- Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science [Mocanu, 2018]\n- Parameter Efficient Training of Deep Convolutional Neural Networks by Dynamic Sparse Reparameterization [Mostafa, 2019]\n- Deep Rewiring: Training very sparse deep networks [Bellec, 2017] \n- There is also few recent work submitted to ICLR2020: https://openreview.net/forum?id=SJlbGJrtDB, https://openreview.net/forum?id=ryg7vA4tPB, https://openreview.net/forum?id=ByeSYa4KPS\n\n(2) Pruning baselines can be improved. I am not convinced that they represent the best achievable sparse training results. I would recommend method proposed by `Prune or Not to Prune` as a strong baseline. You can also check `State of Sparsity` paper to obtain some competitive pruning results.\n\n(3) It's great that the authors are aware of the importance of having experiments on larger datasets. Though, I found the results reported on Imagenet to be limited. Is there a reason why Imagenet-2012 results are missing pruning baselines? I think having other reported pruning results here along with performance of other sparse training methods (SET, DSR) would be useful. Most of these numbers should be readily available in the papers mentioned above, but I guess it is always better to run them using the same settings. \n\n(4) To demonstrate the usefulness of the pruning criteria proposed, it would be nice to do some simple ablations. Some suggestions: (1) Remove weights that would *decrease* the gradient norm most (2) Do random pruning while preserving exact per layer sparsity fractions. (3) sweep over batch size used to calculate the importance scores and evaluate final accuracies or the initial gradient norm. The second experiment would help identifying whether the gains are due to better allocation of sparsities across layers or due to increased gradient norm. Looking at Figure-4 and seeing the per layer sparsities are different, It is not clear to me which one is the underlying reason for improved performance.\n\n(5) (Page 8 / Table 5) Do you aggregate all accuracies in Table 5 using different batch sizes and initialization methods? If, so I am not sure what the intended message here is, since it is difficult to infer how these hyper-parameters affect the result. Do you sweep different batch sizes for estimating importance of units, too? It would be nice to see whether the two batch sizes interact with each other and/or how increased batch size affects the quality of pruned networks. \n\nSome minor comments:\n(a) (Page 1) I found the motivation very intriguing. Though the statement `Recently, F&C (2019) shed light on this...` seems a bit off, given that LT can't find solutions as well as the pruning solution in most practical (larger datasets and architectures) settings. Therefore I would be better to pose this as an `open problem`. \n\n(b) (end of page-1) `However, connection sensitivity is sub-optimal as a criterion because the gradient of each weight might change dramatically after pruning due to complicated interactions between weights`. I think this is still the case for GraSP. Since the criterion it uses assumes independence (i.e. what if we remove a single weight?). It would be nice to see some ablations on this. Does `K=number of weights removed` affect the norm of the sparsified networks?\n\n(c) (Figure 1) I find the comparative illustration between SNIP and GraSP very useful. Though, the architecture presented seems a bit artificial (i.e. I am not aware of any architecture with single hidden layer and a single output unit). I think the same motivation can be made by removing the top unit (therefore having 6-4-1 units) and removing all incoming connections for the output unit until a single connection remains. Then SNIP would remove that single connection whereas GraSP would remove one of the connections in the previous layer.\n\n(d) (Section 2.1) `In contrast, Hessian based algorithms...` Though it is a structured pruning algorithm It might be nice to include the following work, https://arxiv.org/abs/1611.06440. \n\n(e) (Section 2.1) Previous work needs following citations:  [Bellec, 2017], [Mocanu, 2018] and [Mostafa, 2019] \n\n(f) (Section 2.2) Why the initial dynamics affect the final performance? One explanation given in the paper is through recent work on NTK and this is great. Though training settings used at `Lee et al (2019a)` and in the paper are a bit different. Usage of MSE, small datasets, etc… So it might be nice to point out differences. \n\n(g) (Section 3) At $D = {(x_i, y_i)}_{i=1}^n$, `n`->`N` \n\n(h) (Page 4) `Preserving the loss value motivated several…` -> `motivated by several…`\nI think it is better to use existing terminology whenever available.I think using `One-shot pruning` instead of `Foresight pruning` would be a better choice and would prevent confusion. \n\n(j) (Page 5) `However, it has been observed that different weights are highly coupled …` This has been observed much earlier, too: like in Hassibi, 1993. \n\n(k) (Page 7) Last sentence `and thus hopefully..`: needs to be fixed.\n\n(l) (Page 8) The whole page needs some proof-reading. Some of them: (a) `SNIP and GraSP. We present...` probably connect with comma (b) `aims for preserving` -> `aims to preserve` (c) `In contrast, SNIP are more` `are`->`is` (d) `for ablation study` -> `as an ablation study`... \n\n(m) Is there a specific reason why VGG networks are preferred for experiments? I don't think they are relevant to any practical application anymore and they are massively over-parameterized for tasks in hand. Specifically for Cifar-10. I think focusing on more recent networks and larger datasets would increase the impact of the work. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method to improve the training of sparse network by ensuring the gradient is preserved at initialization. The reviewers found that the approach was well motivated and well explained. The experimental evaluation considers challenging benchmarks such as Imagenet and includes strong baselines. 
Decision: Accept (Poster)