Lookahead: A Far-sighted Alternative of Magnitude-based Pruning
Authors: Sejun Park*
Jaeho Lee*
Sangwoo Mo
Jinwoo Shin
Venue:  (2020)
Keywords: network magnitude-based pruning

Abstract: Magnitude-based pruning is one of the simplest methods for pruning neural networks. Despite its simplicity, magnitude-based pruning and its variants demonstrated remarkable performances for pruning modern architectures. Based on the observation that magnitude-based pruning indeed minimizes the Frobenius distortion of a linear operator corresponding to a single layer, we develop a simple pruning method, coined lookahead pruning, by extending the single layer optimization to a multi-layer optimization. Our experimental results demonstrate that the proposed method consistently outperforms magnitude-based pruning on various networks, including VGG and ResNet, particularly in the high-sparsity regime. See https://github.com/alinlab/lookahead_pruning for codes.

approach for a Published as a conference paper at ICLR 2020
LOOKAHEAD: A FAR-SIGHTED ALTERNATIVE OF MAGNITUDE-BASER PRUNING
Sejun Park"t, Jaeho Lee Sangwoo Mot and Jinwoo Shin t8
KAIST EE KAIST AI
(sejun. jaee jaeho-les, swmo, jinwoos]ekaisst..
ABSTRACT
Magnitude-based pruning one the simplest methods for pruning neural net- works. Despite its simplicity, magnitude-hased pruning and its variants demon- strated remarkable performances for pruning modern architectures. Based on the observation that magnitude-basee pruning indeed minimizes the Frobenius distor- tion of a linear operator corresponding to a single layer, we develop a simple prun- ing method, coined lookahead pruning, by extending the single layer optimization to a multi-layer optimization. Our experimental results demonstrate that the pro- posed method consistently outperforms magnitude-basee pruning on various net- works, including VGG and ResNet, particularly in the high-sparsity regime. See https: / gi thub com/ alin.aab//aaaaaa.aaaa.aaa.aaaabl lookahead, www.oohaadpruuuaiaaaaaaaaaaeaeee pruning for codes.
INTRODUCTION
approach has been long underlooked as an overly simplistic base- line among all imaginable techniques to eliminate unnecessary weights from over-parametrized neural networks. Since the early works of LeCun et al. (1989); Hassibi & Stork (1993) which provided more theoretically grounded alternatives of magnitude-based pruning (MP) based on sec- ond derivatives of the loss function, a wide range of methods including Bayesian information- theoretic approaches (Neal, 1996; Louizos et al., 2017; Molchanov al., 2017: Dai et al., 2018), ep-regularization (Wen et al., 2016; Liu et al., 2017: Louizos et al., 2018), sharing redundant chan- nels (Zhang al., 2018 8; Ding al., 2019), and reinforcement learning approaches (Lin al., 2017; Bellec et al., 2018; He et al., 2018 8) have been proposed as more sophisticated alternatives.
The
On the other hand, the capabilities of MP heuristics are gaining attention once more. Combined with minimalistic techniques including iterative pruning (Han et al., 2015) and dynamic reestablishment of connections (Zhu & Gupta, 2017), recent large-scale study by Gale et al. (2019) claims that MP can achieve a state-of-the-arr trade-off between sparsity and accuracy on ResNet-50. The unreason- able effectiveness magnitude scores often extends beyond the strict domain of network pruning; recent experiment by Frankle & Carbin (2019) suggests the existence of automatic subnetwork discovery mechanism underlying the standard gradient-based optimization procedures of deep, over- parametrized neural networks by showing that the MP algorithm finds efficient trainable subnet- work. These observations constitute a call to revisit the mmagniude-equull--aliiee better understanding of the deep neural network itself.
As an attempt to better understand the nature of MP methods, we study a generalization of magnitude scores under functional approximation framework: by viewing MP relaxed minimization of distortion in layerwise operators introduced by zeroing out parameters, we consider multi-layer extension of the distortion minimization problem. Minimization of the newly suggested distortion measure, which "looks ahead' the impact of pruning on neighboring layers, gives birth to novel pruning strategy, coined lookahead pruning (L.AP).
In this paper, we focus the comparison of the proposed LAP scheme to its MP counterpart. We empirically demonstrate that LAP consistently outperforms MP under various setups, including lin- networks, fully-connected networks, and deep convolutional and residual networks. In particular, LAP consistently enables more than x2 gain in the compression rate the considered models, with
"qqual contribution

---

We begin by a more formal description of the magnitude-based pruning (MP) algorithm (Han et al., 2015). Given an I--layer neural network associated with weight tensors Wi,..., WL, the MP al- gorithm removes connections with the smallest absolute weights from each weight tensor until the Published as a conference paper at ICLR 2020
(a) MP
LAP
Figure I:
An illustration of magnitude-based pruning (MP) and lookahead pruning (LAP). MP only
considers a single weight while LAP also considers the effects of neighboring edges.
increasing benefits under the high-sparsity regime. Apart from its performance, lookahead pruning enjoys additional attractive properties:
Easy-to-use: Like magnitude-
pruning, the proposed LAP is a simple score-based approach agnostic to model and data, which can be implemented by computationally light elementary tensor operations. Unlike most Hcssian- based methods, LAP does not rely on the availability of training data except for the retraining phase. It also has no hyper-parameter to tune, in contrast other sophisticated training-based and optimization-ban
schemes.
Versatility: As our method simply replaces the "magnitude-ad " criterion with looka- head alternative, it can be deployed jointly with algorithmic tweaks developed for magnitude- based pruning, such as iterative pruning and retraining (Han et al., 2015) or joint pruning and training with dynamic reconnections (Zhu & Gupta, 2017; Gale et al., 2019).
The remainder of this manuscript is structured as follows: Section 2, we introduce functional approximation perspective toward MP and motivate LAP and its variants as generalization of MP for multiple layer setups; Section we explore the capabilities of L.AP and variants with simple models, then move on to apply LAP to larger-scale models.
2 LOOKAHEAD: A RAR-SIGHTED LAYER APPROXIMATION
desired level of sparsity has been achieved. This layerwise procedure equivalent to finding a mask M whose entries are either 0 or I, incurring smallest Frobenius distortion, measured by
min
||W M @ WIlF:
M:|l 1lo=
where denotes the Hadamard product, - llo denotes the entrywise fo-norm, and is sparsity constraint imposed by some operational criteria.
Aiming to minimize the Frobenius distortion (Eq. (1)), the MP algorithm naturally admits func- tional approximation interpretation. For the case of a fully-connected layer, the maximal difference between the output from pruned and an unpruned layer be bounded
I|r x - (M W)rll2 S |W M @ W ||m||| S I|W M @ WIl ||rl2
Namely, the product of the layerwise Frobenius distortion upper bounds the output distortion of the network incurred by pruning weights. Note that this perspective on MP worst-case distortion minimization was already made in Dong et al. (2017), which inspired an advent of the layerwise optimal brain surgery (L-OBS) procedure.
A similar idea holds for convolutional layers. For the case of two-dimensional convolution with single input and single output channel, the corresponding linear operator takes a form of a doubly block circulant matrix constructed from the associated kernel tensor (see, e.g., Goodfellow et al. (2016)). Here, the Frobenius distortion of doubly block circulant matrices can be controlled by the Frobenius distortion of the weight tensor of the convolutional layer.'
'The case of multiple input/output channels or non-circular convolution can he dealt with similarly using channel-wise circulant matrices as block. We refer the interested readers Sedghi et al. (2019).
2

---

Published as a conference paper at ICLR 2020
Algorithm Lookahead Pruning (LAP)
1: Input: Weight tensors Wi...., Wz of a trained network, desired sparsities ......:
.......... 82
2: Output: Pruned weight tensors W1 .... WT
3: for 1==1, 1,...,,. I.
4:
Compute (:(w) according to Eq. (4) for all entry w of W; 5: Set Was as a s:-th smallest element of (C:(w) w is an entry of Wi}
6: Set M;- f- 1(W, Ws 2 0}
7: Set W; < M, @ W
8: end for
2.1 LOOKAHEAD DISTORTION AS A BLOCK APPROXIMATION ERROR
The myopic optimization (Eq. (1)) based on the per-layer Frobenius distortion falls short even in the simplest case of the two-layer linear neural network with one-dimensional output, where we consider predictors taking form y = u Wx and try minimize the Frobenius distortion of u W (equivalent to & distortion in this case). Here, if u, is extremely large, pruning any nonzero element in the i-th row of W may incur a significant Frobenius distortion.
Motivated by this observation, we consider a block approximation analogue of the magnitude-based pruning objective Eq. (1). Consider L-layer neural network associated with weight tensors WI.... WL. and assume linear activation for simplicity (will be extended to nonlinear cases later in this section). Let J JW;) denote the Jacobian matrix corresponding the linear operator charac- terized by W, For pruning the i-th layer, we take into account the weight tensors of adjacent layers W;-1, W++1 in addition the original weight tensor W,. particular, we propose minimize the i.e.,
Frobenius distortion of the operator block
min Mc 1 ([ [WW
J(W W.)
(3)
An explicit minimization of the block distortion (Eq. (3)), however, is computationally intractable in general (see Appendix D for a more detailed discussion).
To avoid an excessive computational overhead, we propose to use the following score-based pruning algorithm, coined lookahead pruning (LAP), for approximating Eq. (3): For each tensor W,, we prune the weights w with the smallest value of lookahead distortion (in single step), defined as
(4) where Wilweo denotes the tensor whose entries are equal to the entries of W; except for having zeroed out w. We let both Wo and WL+1 to be tensors consisting of ones. In other words, lookahead distortion (Eq. (4)) measures the distortion (in Frobenius norm) induced by pruning while all other weights remain intact. For three-layer blocks consisting only of fully-connected layers and convolutional layers, Eq. (4) reduces to the following compact formula: for an edge w connected to the j-th input neuron/channel and the k-th output neuron/channel of the i-th layer, where its formal derivation is presented in Appendix E.
(())) ==
-
(:ww)= = |w] || :l
(5)
where |w| denotes the weight of w. W[j.:] denotes the slice of W composed of weights connected to the j-th output neuron/channel, and W [: denotes the same for the k-th input neuron/channel.
In LAP, we compute the lookahead distortion for all weights, and then remove weights with the smallest distortions in a single step (as done MP). formal description of LAP presented in Algorithm 1. We also note the running time of LAP is comparable with that of MP (see Appendix G).
LAP on linear networks. To illustrate the benefit of lookahead, we evaluate the performance of MP and LAP on linear fully-connected network with single hidden layer of 1,000 nodes, trained with the MNIST image classification dataset. Fig. 2a and Fig. 2b depict the test accuracy of models pruned with each method, before and after retraining steps.
As can be expected from the discrepancy between the minimization objectives (Eqs. (1) and (3)), networks pruned with LAP outperform networks pruned with MP every sparsity level, in terms
3

---

Published as a conference paper at ICLR 2020
Test sccuracy
80
Test acouracy
80-
60
80
40
MP LAP
LAP
10"
10"
10"
10
10
10
10
Fraction of remaining weights
Fraction remaining weights
(a) before retraining
(b) after retraining
Figure 2: Test accuracy of pruned linear network under varying levels of sparsity, (a) before and (b) after a retraining phase. MP denotes magnitude-basee based pruning and LAP denotes lookahead pruning. All reported points are averaged over 5 trials.
of its performance before a retraining phase. Remarkably, we observe that test accuracy of models pruned with LAP monotonically increases from 91.2% 92.3% as the sparsity level increases, until the fraction of surviving weights reaches I 1.28%. At the same sparsity level, models pruned with MP achieves only 71.9% test accuracy. We also observe that LAP leads MP at every sparsity level even consider higher level of sparsity.
after retraining phase, with increasing margin
Understanding LAP with nonlinear activations. Most neural network models in practice deploy nonlinear activation functioos, e-g., rectified linear units (ReLU). Although the lookahead distortion has been initially derived using linear activation functions, LAP can also be used for nonlinear networks, as the quantity (w) remains relevant to the original block approximation point of view. This is especially true when the network is severely over-parametrized. To see this, consider case where one aims to prune a connection in the first layer of a two-layer fully-connected network with ReLU,
T - W20 (Wix),
(6)
where (x) ma x applied entrywise. Under the over- wer-parametrried scenario, zeroing out single weight may alter the activation pattern of connected neurons with only negligible probability, which allows one to decouple the probability of activation of each neuron from the act of pruning each connection. This enables us to approximate the root mean square distortion of the network output introduced by pruning w of Wi by (p)C((w), where & is the index of the output neuron that is connected to, and pk denotes the probability of activation for the k-th neuron. In this sense, LAP (Algorithm 1) can be understood as assuming i.i.d. activations of neurons, due to a lack of additional access to training data. In other words, LAP admits natural extension to the regime where we assume additional access to training data during the pruning phase. This variant, coined LAP-act, will be formally described in Appendix F, with experimental comparisons another data- dependent baseline of optimal brain damage (OBD) (LeCun et al., 1989).
Another theoretical justification using the lookahead distortion (Eq. (5)) for neural networks with nonlinear activation functions comes from recent discoveries regarding the implicit bias imposed by training via stochastic gradient descent (Du et al., 2018). See Appendix M for detailed discussion.
As will be empirically shown in Section 3.1, LAP is an effective pruning strategy for sigmoids and tanh activations, that are not piece-wise linear as ReLU.
2.2 LOOKAHEAD PRUNING WITH BATCH NORMALIZATION
Batch normalization (BN), introduced by Ioffe & Szegedy (2015), aims to normalize the output of layer per batch by scaling and shifting the outputs with trainable parameters. Based on our functional approximation perspective, having batch normalization layers neural network is not an issue for MP, which relies on the magnitudes of weights; batch normalization only affects the distribution of the input for each layer, not the layer itself. On the other hand, as the lookahead distortion (Eq. (3)) characterizes the distortion of the multi-layer block, one must take into account batch normalization when assessing the abstract importance of each connection.
The revision of lookahead pruning under the presence of batch normalization can be done fairly simply. Note that such a normalization process can be expressed as
b,
4

---

Published as a conference paper at ICLR 2020
for some a. b Rdim(a). Hence, revise lookahead pruning to prune the connections with minimum value of
(w)w) = | a (i--li..1l -l/// :
||
(8)
where a, [k] denotes the k-th index scaling factor for the BN layer placed at the output of the i-th fully-connected or convolutional layer (if BN layer does not exist, let a:[k] = 1). This modification of LAP makes an efficient pruning strategy, as will be empirically verified in Section 3.3.
2.3 VARIANTS OF LOOKAHEAD PRUNING
As the LAP algorithm (Algorithm 1) takes into account current states of the neighboring layers, LAP admits several variants terms of lookahead direction, the order of pruning, and sequential pruning methods; these methods extensively studied in Section 3.2. Along with "vanilla" LAP, we consider in total, six variants, which we now describe below:
Mono-directional LAPs. To prune layer, LAP considers both preceding and succeeding layers. Looking forward, i... only considering the succeeding layer, can be viewed as an educated modi- fication of the internal representation the present layer produces. Looking backward, on the other hand, can be interpreted as only taking into account the expected structure of input coming into the current layer. The corresponding variants, coined LFP and LBP, are tested.
Order of pruning. Instead of using the unpruned tensors of preceding/succeeding layers, also consider performing LAP based on stready-pruned layers. This observation brings up question of the order of pruning: an option is to prune in a forward direction, i.e., prune the preceding layer first and use the pruned weight to prune the succeeding, and the other is to prune backward. Both methods are tested, which are referred to as LAP-ffrwarr and war-backward, respectively.
Sequential pruning. We also consider a sequential version of LLAP-forward/bacwwal methods. More specifically, if we aim to prune total p% of weights from each layer, we divide the pruning bud- get into five pruning steps and gradually prune (p/5)% 55% of the weights per step in forward/backwaard direction. Sequential variants will be marked with suffix "-seq""
3 EXPERIMENTS
In this section, compare the empirical performance of LAP with that of MP. More specifically, validate the applicability of LAP to nonlinear activation functions in Section 3.1. In Section 3.2, we test LAP variants from Section 2.3. In Section 3.3, we test LAP VGG (Simonyan & Zisserman, 2015), ResNet (He et al., 2016), and Wide ResNet (WRN, Zagoruyko & Komodakis (2016)).
Experiment setup. We consider five neural network architectures: (1) The fully-connected net- work (FCN) under consideration is consist of four hidden layers, each with 500 neurons. (2) The convolutional network (Conv-6) consists of six convolutional layers, followed by fully-connected classifier with two hidden layers with 256 neurons each; this model identical that appearing in the work of Frankle & Carbin (2019) suggested as scaled-down variant of VGG." 2 (3) VGG-19 is used, with an addition batch normalization layers after each convolutional layers, and reduced number of fully-connected layers from three to one." (4) ResNets of depths {18, 50} are used. (5) WRN of 16 convolutional layers and widening factor 8 (WRN-16-8) is used. All networks used ReLU activation function, except for the experiments in Section 3.1. We mainly consider image clas- sification tasks. In particular, FCN is trained on MNIST dataset (Lecun et al., 1998). Conv-6, VGG, and ResNet are trained CIFAR-10 dataset (Krizhevsky & Hinton, 2009), and VGG, ResNet, and WRN are trained on Nmt We focus on the one-shot pruning of MP and LAP,, i.e., mod- els are trained with a single Shining-pruning ceaeiiing-rttriningggg cycle. All results in this section are averaged over five independent trials. We provide more details on setups in Appendix A.
"Convolutional layers organized as [64, 64] MaxPool 128, 128] MaxPool [256, 256). "This a popular configuration of VGG for CIFAR-10 (Liu et al., 2019; Frankle & Carbin, 2019) TTnny-ImageNet visual recognition challenge, https: / im- www.kuapp.pp..... com.
5

---

Published as a conference paper at ICLR 2020
100
100
Text accursy
80
Test acourse
Test accuraty
80
Test accurasy
60
40
40
MP
MP
LAP
LAP
LAP
20
80
10
10
10
10
10"
10
1.00
0.10
0.04
Fraction romahinng weights
Fraction remaining weights
Fraction
remaannng weishts
Fraction remaining weights
(a) sigmoid
(b) tanh
(c) ReLU
(d) before retraining
Figure 3: Test accuracy of FCN with (a) sigmoid, (b) tanh, (c) ReLU activations; (d) test accuracy
of FCN with ReLU activation before retraining, for the MNIST dataset.
3.1 NETWORKS WITH NONLINEAR ACTIVATION FUNCTIONS
We first compare the performance of LAP with that of MP FCN using three different types of activation functions: sigmoid, and tanh, and ReLU. Figs. 3a to 3c depict the performance of models pruned with LAP (Green) and MP (Red) under various levels of sparsity.
Although LAP was motivated primarily from linear networks and partially justified for positive- homogenous activation functions such ReLU, the experimental results show that LAP consis- tently outperforms MP even on networks using sigmoidal activation functions. We remark that LAP outperforms MP by larger margin as fewer weights survive (less than 1%). Such a pattern will be observed repeatedly in the remaining experiments of this paper.
In addition, we also check whether LAP still exhibits better test accuracy before retraining under the usage of nonlinear activation functions, as in the linear network case (Fig. 2b). Fig. 3d illustrates the test accuracy of prumed FCN using ReLU on the MNIST dataset before retraining. We observe that the network pruned by LAP continues perform better than MP in this case; the network pruned by LAP retains the original test accuracy until only 38% of the weights survive, and shows less than 1% performance drop with only 20% of the weights remaining. On the other hand, MP requires 54% and 30% to achieve the same level of performance, respectively. pruned with MP requires about 50% more survived parameters than the models pruned with LAP to achieve a similar level of performance before being retrained using additional training batches.
other words, the models
3.2 EVALUATING LAP VARIANTS
Now we evaluate LAP and its variants introduced in Section 2.3 on FCN and Conv-6, each trained on MNIST and CIFAR-10 10, respectively. Table summarizes the experimental results on FCN and Table 2 summarizes the results on Conv-6. addition to the baseline comparison with MP, we also compare with random pruning (RP), where the connection to be pruned was decided completely independently. We observe that LAP performs consistently better than MP and RP with similar or smaller variance in any case. In the case of an extreme sparsity, LAP enjoys significant perfor- mance gain; over 75% gain on FCN and 14% on Conv-6. This performance gain comes from a better training accuracy, instead of better generalization; see Appendix L for more information.
Comparing -ino-directional lookahead variants, we observe that LFP performs better than LBP in the low-sparsity regime, while LBP performs better in the high-sparsity regime; in any case, LAP performed better than both methods. Intriguingly, the same pattern appeared in the case of the ordered pruning. Here, fAP-forward they both consider layers closer to the input to be more critical. Likewise, LAP-backwand can be considered an analogue of LFP. We observe that LAP-forward performs better than LAP-backward in the high-sparsity regime, and vice versa in the low-sparsity regime. Our interpretation is as follows: Whenever the sparsity level is low, carefully curating the imput signal not important due to high redundancies in the natural image signal. This causes a relatively low margin of increment by looking backward in comparison looking forward. When the sparsity level high, the input signal is scarce, and the relative importance of preserving the input signal is higher.
be considered an analogue of LBP in the sense that
Finally, we observe that employing forward/backward ordering and sequential methods leads to better performance, especially in the high-sparsity regime. There is no clear benefit of adopting directional methods the low-sparsity regime. The relative gain in performance with respect to LAP is either marginal or unreliable.

---

Published as a conference paper at ICLR 2020
Table 1:
Test error rates of FCN on MNIST. Subseripts denote standard deviations, and bracketed numbers denote relative gains with respect to MP. Unpruned models have 1.98% error rate.
6.36%
3.21%
1.63%
0.84%
0.43%
0.23%
0.12%
MP (baseline)
1.75
2.11
2.53+20.00
3.32+0.27
4.77=0..2
19.85=8
67.62=9.0
RP
2.36:10.13
2.72:0.16
3.6410.17
17.54:17.07
82.48:44.03
88.65=0.00
88.65=0.00
LFP
1.63.10.08
1.8910.11
1..3
3.32.0.13
4.23
9,59 L1.7
50.11
(-6.41%)
(-10.60%)
(-3.95%)
(-0.12%)
(-11,40%)
(-51.70%)
(-25.91%)
LBP
1.75
2.04
2.61
3.62
4.19
9.09=1.41
28,51
(+0.69%)
(-3.31%)
(+3.00%)
(+8.97%)
(-12.23%)
(-54.21%)
(4%)
LAP
1.67 10.11
1.891
1.48
3,2910.06
3.93
6.72.0.44
16.4515.61
(-4.24%)
(-10.61%)
(-2.05%)
(-1.08%)
(-17.72%)
(-66.15%)
(-75.68%)
LAP-forward
1,60:0.08
1,93
2.51
3,5640.19
4,47=0.20
6,58=0.38
12.00
(-8,25%)
(-8.43%)
(-0,95%)
(47.03%)
(-6,41%)
(-66.81%)
(-82.26%%
LAP-backward
1,631
1.88
2.3510.02
3,1210.08
3,87
5.62
13,00
(-6.64%)
(-10.80%)
(-7.03%)
(-6,08%)
(-19.02%)
(-71.71%)
(-80.78%)
LAP-forward-seq
1.68#0.11
1.92+0.30
2.49
3.3940.24
4.21
6.20=0.a2
10.98
(-3.66%)
(-9.09%)
(-1.42%)
(+1.93%)
(-11.86%)
(-68.73%)
(-83.76%)
LAP-backwand-seq
1.57+0008
1.84+a.0
2.20=aa00
3.13+0.16
3.62+0.14
5,42+m.27
11.92+461
(-10.08%)
(-12.41% %)
(-13.27%)
(-5.90%)
(-24.13%)
(-72.71%)
(-82.36%%
Table 2: Test error rates of Conv-6 on CIFAR-10. Subscripts denote standard deviations, and brack-
eted numbers denote relative gains with respect to MP. Unpruned models have 11.97% error rate.
10.62%
8.86%
7.39%
6.18%
5.17%
4.32%
3.62%
MP (baseline)
11.86
12.20+0.21
13.30+0.30
15.81
20.19+2.36
24.43+1.48
28. 28.60=2.10
RP
1..25
29.72+1.13
32.98+1.10
35.92+1.05
39.13+1.05
41.20#1.19
43.60=0.82
LFP
11.81
12.18
13.27:0044
15.04+0.43
18.50+0.80
22.86:1.66
26.65+1133
(-0.39%)
(-0.20%%
(-0.26%%
(-4.87%)
(-8.37%)
(-6.40%)
(-6.83%)
LBP
12.08
12.3410.38
13.2610.18
14.93
18.11
22.57.0..1
26.3411.80
(+1.84%)
(-1.15%)
(-0.33%)
(-5.57%)
(-10.31%)
(-7.59%)
(-7.91%)
LAP
11.76.:024
12.161027
13.05-0.14
14.3910.44
17.10
21.24
24.52.1111
(-0.83%)
(-0.34%)
(-1.86%
(-8.99%)
(-15.30%)
(-13.04%)
(-14.29%)
LAP-forward
11.82#0.16
12.35+0.34
13.09
14.42+0.45
17.05+1.30
22.80+0.01 20.28+1.40
(-0.33%)
(+1,24%)
(-1.62%)
(-8.79%)
(-15.57%)
(-16.98%)
(-20.30%)
LAP-backward
11.82
12.29
12.93
14.55
17.00
20.00
23.37
(-0.32%)
(+0.68%)
(-2.78%)
(-7.98%)
(-15.78%)
(-18.11%)
(-18.30%)
LAP-forward-seg
12.01
12.4710.37
13.1910.11
14.12 0.28
16.73_095 0.95
19.63_
22.44.1.M
(+1.28%)
(+2.21%)
(-0.8196)
(-10.70%)
(-17.13%)
(-19.62%)
(-21.54%)
Aa--hacwward-seg
12.35 11
13.25-0a1
14.17=044
16.99_097
19.94_1m
23.15
(-0.39%%
(+1.25%)
(-0.41%)
(-10.37%)
(-15.87%)
(-18.38%)
(-19.08%)
3.3 DEEPER NETWORKS: VGG, RESNET, AND WRN
We also compare empirical performances of MP with IAPP deeper networks. We trained VGG-19 and ResNet-18 18 on CIFAR-10 (Tables and 4), and VGG-19, ResNet-50, and WRN-16-8 on Tiny- ImageNet (Tables 5 to 7). For models trained on CIFAR-1O. we also test LAP-forward to verify the observation that it outperforms LAP in the high-sparsity regime on such deeper models. We also report additional experimental results on VGG-(11, 16) trained on CIFAR-10 in Appendix B. For models trained on Imag-en,,,Ne,, top-1 eтror rates are reported in Appendix C.
From Tables 7. we make the following two observations: First, as in Section 3.2, the models pruned with LAP consistently achieve a higher or similar level of accuracy compared to models pruned with MP, at all sparsity levels. In particular, test accuracies tend to decay a much slower rate with LAP. In Table 3, for instance, we observe that the models pruned by LAP retain test accuracies of 70~80% even with less than 2% of weights remaining. In contrast, the performance of models pruned with MP falls drastically, to below 30% accuracy. This observation is consistent on both CIFAR-10 and Tiny-ImageNe datasets.
Second, the advantages of considering ordered pruning method (LAP-forward over LAP is lim- ited. While we observe from Table 3 that LAP-forward outperforms both MP and LAP in the high- sparsity regime, the gain is marginal considering standard deviations. LAP-forward is consistently worse than LAP (by at most 1% in absolute scale) in the low-sparsity regime.
7

---

Published as a conference paper at ICLR 2020
Table 3: Test error rates of VGG-19 on CIFAR-IO. Subscripts denote standard deviations, and
bracketed numbers denote relative gains with respect to MP. Unpruned models have 9.02% error rate.
12.09%
8.74%
6.31%
4.56%
3.30%
2.38%
1.72%
1.24%
MP (bascline) 8.99=012
9.90a0.0
11,43+a24
15.62=10s
29.10
40.27
63.27=11.91
77.90a7s4
LAP
8.89
9.51
10.56:025
12.11
13.644077
16.38+147
20.88
22.82+0a1
(-1.07%)
(-3.96%) %)
(-7.63%)
(-22.48%+
(-53.13%)
(-59.31%)
(-67.00%)
(-70.71%)
LAP-forward
9.63==025
+0.3
11,10+a22
12.24
13.54=022
16.03:+044
19,33+1.14
21,59+0a2
(+7.16%)
(+4.12%%
(-2.99%)
(-21.66%)
(-53.46%)
(-60.18%)
(-69.44%) %6
(-72.29%)
Table 4: Test error rates of ResNet-18 on CIFAR-10. Subscripts denote standard deviations, and
bracketed numbers denote relative gains with respect to MP. Unpruned models have 8.68% error rate.
10.30%
6.33%
3.89%
2.40%
1.48%
0.92%
0.57%
0.36%
MP (baseline)
8.18
8.74
9.82.1.18
11.28:0.30
14.31
18.5610.36
22.93
26.77=1104
LAP
8.091..10
8.97
9,74...5
11.35.0000
13.731024
16.29...29
22.45 20.2
(-1.0%%) %)
(+2.59%)
(-0.81
(+0.64%)
(-4.08%)
(-12.23%)
(-11.82%) )
(-15.82%)
LAP-forward
8.19
9.17
10.32.027
12.38
15.3
18.56
21.09
23.89
(+0.12%)
(+4.85%%
(+5.09%)
(+9.79%)
(+6.96%)
(-0.02%%
(-8.04%)
(-10.44%)
Table 5: Top-5 test error rates of VGG-19 on Tiny- ImageNe. Subscripts denote standard deviations, and bracketed numbers denote relative gains with respect to MP. Unpruned models have 36.89% enror rate. Top-1 test error rates are presented in Table 10.
12.16%
10.34%
8.80%
7.48%
6.36%
5.41%
4.61%
3.92%
MP (baselinc)
36.40=1.1
37.37=108
38.40+1.30
40.23+1126
42.68+1.97
45,83+276
49.79#227
56.15-5514
LAP
36.01
37.03
38.20
39.36-1130
40.95
43.14
4
48.34_1030
(-1.07%) )
(-0.90%)
(-0.52%)
(-2.16%)
(-4.05%)
(-5.87%) %)
(-9.02%)
(-13.92%)
LAP-forward
36.981104
37.35_090
38.4911.10
1995
10.94
43.30.1.77
15.7611.37
48.95
(+1.58%)
(-0.04%)
(+0.24%)
(-1.65%)
(-4.06%)
(-5.53%)
(-8.08%)
(-12.84%)
Table 6: Top-5 test error rates of ResNet-50 on Imag-em Subscripts denote standard de- viations, and bracketed numbers denote relative gains with respect to MP. Unpruned models have 23.19% error rate. Top-1 test error rates are presented in Table 11.
6,52%
4.74%
3.45%
2.51%
1.83%
1.34%
0.98%
0.72%
MP (baseline)
23.88+0.27
24.99s0.34
26.84:0.39
29.5440.58
34,04:0.48
40.19 as
45.13
59.18=16.a1
LAP
23.64:2040
24.91::a5
26.52:a..8
28.84
33.71=448
39.07=045
43.05
46. 16.16.1104
(-1.00%)
(-0.34%)
(-1.17%)
(-2.38%)
(-0.98%)
(-2.79%)
(-4.61% %)
(-22.00%)
LoP-forward
24.2620.4
24.92:1041
27. 27.66
30.9310.11
35.90
39, 39,9920 5s
43.42:10.32
45.45
(+1.57%)
(-0.30%)
(+3.08%)
(+4.71%)
(45.46%%
(-0.48%%
(-3.79%)
(-23.19%)
Table 7: Top-5 test error rates of WRN-16-8 on Imay-em Subscripts denote standard de- viations, and bracketed numbers denote relative gains with respect to MP. Unpruned models have 25.77% error rate. Top-1 test error rates are presented in Table 12.
12.22%
8.85%
6.41%
4.65%
3.37%
2.45%
1.77%
1.29%
MP (baseline)
25.27
26.7
1..
31.91=050
37.01
42.89+2.48
51.10=2.50
59.73+2.85
LAP
24.99:0a5
26.55+144
28.68
32.22+2.51
35.82+246
41.37=3a7
45.43+-144
51.83=1.1
(-1.12%)
(-0.87%)
(-0.58%)
(+0.98%)
(-3,22%)
(-3.55%)
(-11.106)
(-13,22%)
LAP-forward
26.30
28. 28.52.2213
30.9811:39
34.7211.88
38.41
42.02.1.46
45.10
$1.9211.44
(+4.08%)
(+6.48%)
(+7.42%)
(+8.83%)
(+3.79%)
(-2.02%)
(-11.74%)
(-13.07%)
4 CONCLUSION
In this work, we interpret magnitude-basse pruning as a solution to the minimization of the Frobe- nius distortion of single layer operation incurred by pruning. Based on this framework, we consider the minimization of the Frobenius distortion of multi-layer operation, and propose a novel lookahead pruning (LAP) scheme as computationally efficient algorithm to solve the optimization. Although LAP was motivated from linear networks, it extends to nonlinear networks which indeed minimizes the root mean square lookahead distortion assuming i.i.d. activations. We empirically show its effec- tiveness on networks with nonlinear activation functions, and test the algorithm on various network architectures including VGG, ResNet and WRN, where LAP consistently performs better than MP.
8

---

Published as a conference paper at ICLR 2020
Acknowledgments. We thank Seunghyun Lee for providing helpful feedbacks and suggestions in preparing the early version of the manuscript. JL also gratefully acknowledges Jungseul Ok and Phillip M. Long for enlightening discussions about theoretical natures of neural network prun- ing. This research was supported by the Engineering Research Center Program through the Na- tional Research Foundation of Korea (NRF), funded by the Korean Govermment MSIT (NRF. 201 1SRIA5A105992
REFERENCES
S. Arora, N. Cohen, and E. Hazan. On the optimization of deep networks: Implicit acceleration by overparametrization. Proceedings of the International Conference Machine Learning, 2018.
G. Bellec, D. Kappel, W. Maass, and R. Legenstein. Deep rewiring: training very sparse deep networks. In International Conference on Learning Representations, 2018.
B. Dai, C. Zhu, B. Guo, and D. Wipf. Compressing neural networks using the variational information bottleneck. Proceedings of the International Conference on Machine Learning, 2018.
Dangel, F. Kunstner, and P. Hennig. BackPACK: Packing more into backprop. In International Conference Learning Representations, 2020.
X. Ding, G. Ding, Y. Guo, and J. Han. Centripetal SGD for pruming very deep convolutional net- works with complicated structure. IEEE Conference on Computer Vision and Pattern Recog- nition, 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, 2017.
S. S. Du, W. Hu, and J. D. Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. Advances in Neural Information Processing Systems, 2018.
J. Frankle and M. Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks
In International Conference on Learning Representations, 2019.
T. Gale, E. Elsen, and S. Hooker. The state of sparsity in deep neural networks. arXiv preprint 1902.09574, 2019.
X. Glorot and Y. Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the International Conference on Artificial Intelligence and Statistics, 2010.
I. Goodfellow, Y. Bengio, and A. Courville. Deep Learning. MIT Press, 2016. http:// /ww.. deeplearningbook org.
S. Han, J. Pool, J. Tran, and W. J. Dally. Learning both weights and connections for efficient neural networks. In Advances in Neural Information Processing Systems, 2015.
B. Hassibi and D. G. Stork. Second order derivatives for network pruning: Optimal brain surgeon. In Advances in Neural Information Processing Systems, 1993.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition, 2016.
Y. He, J. Lin, Z. Liu, H. Wang, L. Li, and S. Han. AMC: AutoML for model compression and acceleration on mobile devices. In European Conference on Computer Vision, 2018.
S. Ioffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proceedings of the International Conference on Machine Learning, 2015.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.

---

Published as a conference paper at ICLR 2020
Y. LeCun, S. Denker, and S. A. Solla. Optimal brain damage. In Advances in Neural Information Processing Systems, 1989.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recog- nition. In Proceedings of the IEEE, 1998.
Lin, Y. Rao, J. Lu, and Zhou. Runtime neural pruning. Advances Neural Information Processing Systems, 2017.
Z. Liu, J. Li, Z. Shen, G. Huang, S. Yan, and C. Zhang. Learning efficient convolutional networks through network slimming. In JEEE International Conference on Computer Vision, 2017.
Z. Liu, M. Sun, T. Zhou, G. Huang, and T. Darrell. Rethinking the value of network pruning. In International Conference Learning Representations, 2019.
C. Louizos, K. Ullrich, and M. Welling. Bayesian compression for deep learning. In Advances in Neural Information Processing Systems, 2017.
C. Louizos, M. Welling, and D. P. Kingma. Learning sparse neural networks through lo regulariza- tion. In International Conference on Learning Representations, 2018.
D. Molchanov, A. Ashukha, and D. Vetrov. Variational dropout sparsified deep neural networks. In Proceedings of the International Conference Machine Learning. 2017.
K. G. Murty and N. Kabadi. Some NP-complete problems in quadratic and nonlinear program- ming. Mathematical programming, 39(2):117-229 1987.
R. M. Neal. Bayesian learning for neural networks. Springer. 1996.
M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L. Chen. MobileNetV2: Inverted residuals and linear bottlenecks. In IEEE Conference on Computer Vision and Pattern Recognition, 2018.
H. Sedghi, V. Gupta, and P. M. Long. The singular values of convolutional layers. In International Conference on Learning Representations, 2019.
K. Simonyan and Zisserman. Very deep convolutional networks for large-scale image recogni- tion. In International Conference on Learning Representations, 2015.
W. Wen, C. Wu, Y. Wang, Y. Chen, and H. Li. Learning structured sparsity in deep networks. In Advances in Neural Information Processing Systems, 2016.
Ye, X. Lu, Z. Lin, and J. Z. Wang. Rethinking nel pruning of convolutional layers. In International Conference Learning Representations, 2018.
assumption in chan-
S. Zagoruyko and N. Komodakis. Wide residual networks. In Proceedings of British Machine Vision Conference, 2016.
D. Zhang, H. Wang, M. Figueiredo, and L. Balzano. Learning to share: simultancous parameter ty- ing and sparsification in deep learning, In International Conference on Learning Representations, 2018.
M. Zhu and S. Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression, arXiv preprint 1710v17100018722 2017.
10

---

Published as a conference paper at ICLR 2020
A EXPERIMENTAL SETUP
Models and datasets. We consider four neural network architectures: (I) The fully-connectee network (FCN) under consideration is composed of four hidden layers, each with 500 hidden neu- rons. (2) The convolutional network (Conv-6) consists of six convolutional layers, followed by fully-connected classifier with two hidden layers with 256 hidden neurons each; this model is iden- tical to that appearing in the work of Frankle & Carbin (2019) suggested as scaled-down variant of VGG. (3) VGGs of depths {11, 16, 19} were used, with an addition of batch normalization layers after each convolutional layers, and reduced number of fully-connected layers from three one. (4) ResNets with depth {18, 50} are used. (5) Wide ResNets with depth 16 and widening factor 8 used. All networks are initialized via the method of Glorot & Bengio (2010), except for ResNets and WRN. We use the ReLU activation function except for the experiments in Section 3.1. We fo- cus on image classification tasks. FCN is trained with MNIST dataset (Lecun et al., 1998), Conv-6, VGG-(11, 16, 19} and ResNet- 18 are trained with CIFAR- 10 dataset (Krizhevsky & Hinton, 2009), and VGG-19, ResNet-50, WRN-16-8 ware trained with Tiny-ImageNet dataset.
Optimizers and hyperparameters. We use Adam optimizer (Kingma & Ba, 2015) with batch size 60. We use learning rate of 1.2 10 3 for FCN and 3- 10 for all other models. For FCN, we use [50k, 50k] for the initial training phase and retraining phase. For Conv-6, we use [30k, 20k] steps. For VGG-11 and ResNet-18, use [35k, 25k] steps. For VGG-16, use [50k, 35k]. For VGG-19, ResNet-50, and WRN-16-8 we use [60k, 40k). We do not use any weight decay, learning rate scheduling, or regularization.
Sparsity levels. To determine the layerwise pruning ratio, we largely follow the the guidelines of Han et al. (2015); Frankle & Carbin (2019): For integer values of r, we keep p fraction of weights in all convolutional layers and q² fraction in all fully-connected layers, except for the last layer where we use (1 + /) instead. For FCN, we use (p, g) (0, 0.5). For Conv-6, VGGs ResNets, and WRN, we use (0.85, 0.8). For ResNet-(115 18, 50), we do not prune the first convolutional layer. The range of sparsity for reported figures in all tables is decided as follows: we start from where test error rate starts falling below that of an unprumed model and report the results at T, T + +,, 2.... for FCN and Conv-6, T, + 2, T + 4,... for VGGs, ResNet-50, and WRN, and T, + 3. + 6.... for R8sNet-18.
B ADDITIONAL VGG EXPERIMENTS
Table 8: Test error rates of VGG-11 on CIFAR-10. Subscripts denote standard deviations, and brack- eted numbers denote relative gains with respect MP. Unpruned models have 11.51 % error rate.
16.74%
12.10%
8.74%
6.32%
4.56%
3.30%
2.38%
1.72%
MP (haseline) 11.41 1024
12.38
13.542035
16.0821
19.762167
28. 12:344
45.38=11
15.97
LAP
11.19auu
11.7920.44
12.95+a44
13.95+au7
15.59+aas
20.96=6.2
22.00
28.9643.30
(-1.96%)
(-4.78%)
(-4.39%)
(-13,25%)
(-21.13%)
(-25,47%%
(-51.52%)
(-48.25%)
LAP-forward
11.47
12.3320.1
13.15
13.961025
15.42
18.22:109
21.74
25.85
(+0.56%)
(-0.44%)
(-2.87%)
(-13.18%)
(-21.97%)
(-52.10%)
(-53.82%)
Table 9: Test error rates of VGG-16 on CIFAR-10. Subscripts denote standard deviations, and bracketed numbers denote relative gains with respect to MP. Unpruned models have 9.33% error rate.
10.28%
7.43%
5.37%
3.88%
2.80%
2.03%
1.46%
1.06%
MP (baseline) 9.55ga011
10.78=045
13.42=219
17.83
26.61
48.8
48.87
69.39+1185
83,47+560
LAP
9.35-
10.07=a199
11.52#026
12.57=034
14.23
17.01=1.4
25.03
32.45+1220
(-2.05%)
(-6.59%)
(-14.21%)
(-29.50%)
(-46.52%)
(-65.19%)
(-63.92%)
12%)
LAP LAP-forward
9.45
10.40.o.0
11.33
13.091021
14.61 10:25
17.1010.9
22.39
24.9910.4
(-1.03%)
(-3.49%)
(-15.60%)
(-26.56%)
(-45.08%)
(-65.02%%
(-67.74%)
(-70.06%)
'Convolutional layers are organized as [64, 64] - MaxPool - 1128, 128] - MaxPool [256, 256).
TThi is popular configuration of VGG for CIFAR-10 (Liu et al., 2019; Frankle & Carbin, 2019)
11

---

Published as a conference paper at ICLR 2020
C TOP-1 1 ERROR RATES FOR TINY-IMAGENET EXPERIMENTS
Table 10: Top-1 test error rates VGG-19 on Imny-ImageNet. Subscripts denote standard devi- ations, and bracketed numbers denote relative gains with respect to MP. Unpruned models have 64.55% emor rate.
12.16%
10.34%
8.80%
7.48%
6.36%
5.41%
4.61%
3.92%
MP (baselinc)
63.35
64.43+1.0
65.44
67.09=1004
69.40+1.40
72.36+2.0
75.35
79.98-128
LAP
63.15
63.91
65.56.1442
66.
68.40
70.45
72.16:142
75.05-0.2
(-0.31 %)
(-0.80%)
(+0.18%)
(-0.80%)
(-1.44%)
(-2.63%)
(.4.24%)
(-6.17%)
LAP-forward
64.22+1.11
64.77+0.6
65.63+121
67.03=1225
68.52+1.39
70.55+1.a1
73.13=097
75.71=138
(+1.38%)
(+0.53%)
(+0.28%)
(-0.09%)
(-1.26%
(-2.50%)
(-2.95%)
(-5.34%)
Table 11: Top-1 test enror rates of ResNet-50 on Imny-ImageNet. Subscripts denote standard de- viations, and bracketed numbers denote relative gains with respect to MP. Unpruned models have 47.50% error rate.
6.52%
4.74%
3.45%
2.51%
1.83%
1.34%
0.98%
0.72%
MP (buseline)
48.18
49.85
22
55.46.0.37
60.51
66.6010.42
70.7520:3
80.02....4
LAP
48.27
29
51.92:021
54.91
60,31
65.46:1227
69.131..91
71.81
(+0.20%)
(+0.22%)
(40.69%)
(-0.99%)
(-0.34%)
(-1.71%%
(-2.29%)
(-10.26%)
LAP-forward
48.65 18.6920.52
50.25+0.26
53.55+0.42
57.59+0.41
62.74=0.57
66.59+0.80
69.55=0.25
71.49=0.7
(+1.05%)
(+0.79%))
(+2.42%)
(+3.84%)
(+3.69%)
(-0.02%)
(-1.69%)
(-10.67%)
Table 12: Top-I test error rates of WRN-16-8 on Tiny-ImageNet. Subscripts denote standard de- viations, and bracketed numbers denote relative gains with respect to MP. Unpruned models have 51.85% error rate.
12.22%
8.85%
6.41%
4.65%
3.37%
2.45%
1.77%
1.29%
MP (buseline)
50.3811.00
12.64.0.84
55.23
58.7910s1
64.1
69.22.12.3
75.9012.03
81.8312.17
LAP
49.85=119
52.33:14
54.96:126
59.06:2.40
62.68:1.7
67.82:2.9
71.30:3.65
76.51
(-1.04%)
(-0.60%)
(-0.49%)
(+0.46%)
(-2,23%)
(-2.02%)
(-6.06%)
(-6.50%)
LAP-forward
51.86+1.14
54.77=2.37
57.65+1.75
61.84
65.30 15.30&2.14
69.03+2.44
71.75=1.00
77.00
(+2.95%)
(+4.05%)
(+4.38%)
(+5.18%)
(+1.85%)
(-0.27%)
(+5.46%)
(-5.91%)
12

---

Published as a conference paper at ICLR 2020
D NP-HARDNESS OF EQ. (3)
In this section, we show that the optimization Eq. (3) is NP-hard by showing the reduction from the following binary quadratic programming which is NP-hard (Murty & Kabadi, 1987):
min xf Ax xE(0,1)
for some symmetric matrix A E RTXn, Without loss of generality, we assume that the minimum eigenvalue of A (denoted with X) is negative; if not, Eq. (9) admits trivial solution (0,...,0),
Assuming À < 0, Eq. (9) can be reformulated as:
min H' X =E(0.11
Σ Tz
(10)
where H = A A.. Here, one easily observe that the above optimization can be solved by solving the below optimization for I, ,
min
x" HE
(11)
10 21=8
Finally, we introduce the below equality
x Hr x UAU
(12)
= VIVAUT T x01?
(13)
VIVAUT x1
(14)
= -IIVUU VAU ((1 ((1-1) o
(15)
where denotes vector of ones, U is a matrix consisting the eigenvectors of H its column vectors, and A is a diagonal matrix with corresponding (positive) eigenvalues of H as its diagonal elements. The above equality shows that Eq. (11) is a special case of Eq. (3) by choosing Wi = VAUT, W2 = 1, W3 and M = T. This completes the reduction from Eq. (9) Eq. (3).
E DERIVATION OF EQ. (5)
In this section, we provide a derivation of Eq. (5) for the fully-connected layers. The convolutional layers can be handled similarly by substituting the multiplications in Eqs. (16) and (17) by the convolutions.
The Jacobian matrix of the linear operator correponding to fully-connected layer is the weight matrix itself, i.e. JWW)) = W.. From this, lookahead distortion can be reformulated as
(ww))
W,W,-1 - W W. W
(16)
Now, we decompose the matrix product W W,W:1 in terms of entries of W; as below:
WW1WWWW
wi (: Σ 3.k
(17)
where W.[k; j], Wi+1l,,k k), and W;- W, denote kjth) element of W,, k-th column of W and j-th row W,-1, respectively. The contribution of single entry w == W, [k, to the prod- uct W++1 W,W,1 equivalent to Wi11: (1..) Therefore, in terms of the Frobenius distortion, we conclude that
(w) | Wi+1 -/-,-1 |u| -I. |[aea|&
which completes the derivation of Eq. (5) for fully-connected layers.
13

---

Published as a conference paper at ICLR 2020
F LAP-ACT: IMPROVING LAP USING TRAINING DATA
Recall two observations made from the example of two-layer fully connected network with ReLU activation appearing in Section 2.1: LAP is designed to reflect the lack of knowledge about the training data at the pruning phase; once the activation probability of each neuron can be estimated, it is possible refine LAP to account for this information.
In this section, we continue our discussion on the second observation. In particular, we study an extension of LAP called lookahead pruning with activation (LAP-act) which prunes the weight with smallest value of
[w)) = | W. 1i.
[:
(18)
Here, W; is a scaled version of W; and T is the corresponding scaled value of w, defined by
W:bi::] = Σ
VPk [.
(19)
kE
where I1, denotes the set of ReLU indices in the j-th output neuron/channel of i-th layer. For example, 1,, = {i} for fully connected layers and 45 is a set of ReLU indices the j-th channel for convolutional layers. Also, P& denotes the k-th ReLU's probability of activation, which can be estimated by passing the training data.
We derive LAP-act (Eq. (18)) in Appendix F.1 and perform preliminary empirical validations in Appendix F.2 with using optimal brain damage (OBD) as baseline. We also evaluate a variant of LAP using Hessian scores of OBD instead of magnitude scores. It turns out that in the small networks (FCN, Conv-6), 6), LAP-act outperforms OBD.
F.1 DERIVATION OF LAP-ACT
Consider a case where one aims to prune a connection a network with ReLU, i.e.
(W(
(20)
where (I) max{0, x is applied entrywise. Under the over werrppaaametrized scenario, zeroing out single weight may alter the activation pattern of connected neurons with only negligible probability, which allows one to decouple the probability of activation of each neuron from the act of pruning each connection. From this observation, we first construct the below random distortion, following the philosophy of the linear lookahead distortion Eq. (4)
[w(w:
-
(21)
where J(W)) denotes a random matrix where J(W))kk = 9:[k] [k, and g [k] is 0-1 random variable corresponding to the activation, i.e., gi[k] if and only if the k-th output, i.e., ReLU, of the i-th layer is activated. However, directly computing the expected distortion with re- spect to the real activation distribution might be computationally expensive. To resolve this issue, we approximate the root mean square lookahead distortion by applying the mean mean-fiell approximation to the activation probability of neurons, i.e., all activations are assumed to be independent, as
pln (4) E Ey-p(g) E [w] R (Bal:)))>BBBBBBBBB (o. (oo
=: (.(w)
(22)
where g = [ss].. p(g) denotes the empirical activation distribution of all neurons and I. p(g: [k]) denotes the mean-field approximation p(g). Indeed, the lookahead distortion with ReL.U non- linearity (Eq. (22)) three-layer blocks consisting only of the fully-connected layers and the
volutional layers can easily computed by using the rescaled weight matrix Wi:
W.I.
Σ Vpla.(k)11) kEh.
W.
(23)
where Iúj denotes the set ReLU indices the j-th output neuron/channel of i-th layer. For example, Ti, = (j) for fully connected layers and Ti is set of ReL.U indices in the j-th channel
14

---

Published as a conference paper at ICLR 2020
for convolutional layers. Finally, for an edge connected to the j-th input neuron/channel and the k-th output neuron/channel of the i-th layer, Eq. (22) reduces to
(ww)) = |
(24)
where w denotes the rescaled value of w. This completes the derivation of Eq. (18).
F.2 EXPERIMENTS WITH LAP-ACT
We compare the performance of three algorithms utilizing training data at the pruning phase: opti- mal brain damage (OBD) which approximates the loss via second order Taylor seris approximation with the Hessian diagonal (LeCun et al., 1989), LAP using OBD instead of weight magnitudes (OBD+LAP), and LAP-act as described in this section. We compare the performances of three al- gorithms under the same experimental setup as in Section 3.2. To compute the Hessian diagonal for recently introduced software package called "BackPACK," (Dangel
OBD and OBD+LAP, et al., 2020), which is the only open-source package supporting an efficient of Hessians, up to our knowledge. Note that the algorithms evaluated in this section are also evaluated for global pruning experiments in Appendix I.
The experimental results for FCN and Conv-6 are presented in Tables 13 and 14. Comparing to algorithms relying solely on the model parameters for pruning (MP/LAP in Tables 1 and 2), we observe that OBD performs better in general, especially in the high sparsity regime. This observation is coherent to the findings of LeCun et al. (1989). Intriguingly, however, we observe that applying lookahead critertion to OBD (OBD+LAP) sigmificantly enhances to OBD significantly enhances the performance in the high sparsity regime. We hypothesize that LAP helps capturing correlation among scores (magnitude or (lessian-based) of adjacent layers. Also, we observe that LAP-act consistently exhibits better performance compared to OBD. This result is somewhat surprising, in the sense that LAP-act only utilizes (casicr-to-este -ostimmate information about activation probabilities of each neuron to correct lookahead distortion.
The average running time of OBD, OBD+LAP, and LAP-act summarized in Table 15. We use Xeon E5-2630v4 2.20GHz for pruning edges, and additionally used a single NVidia GeForee GTX- 1080 for the computation abiility (for LAP-act). We observe that LAP-act runs in significantly less running time than OBD/OBD+LAP, and the gap widens as the number of parameters and the dimensionality of the dataset increases (from MNIST to CIFAR-10).
Hessian diagonals (used for OBD, OBD+LAP) and activation prob-
Table 13: Test error rates of FCN MNIST. Subscripts denote standard deviations, and bracketed numbers denote relative gains with respect to OBD. Unpruned models achieve 1.98% error rate.
6.36%
3.21%
1.63%
0.84%
0.43%
0.23%
0.12%
OBD (haseline) 1.8740.05
1.
2.51
3.07
4.08
5.6622.39
11.01
OBD+LAP
1.81
2.18
2.5240.14
3.48
4.1622.35
5.8820.51
8.65
(-3.42%)
(+5.31%)
(+0.48%)
(+13.35%)
(+1.91%)
(+3.81%)
(-21.41%)
LAP-act
1.78=
1.85=
2.21:013
2.73:004
3.50
4.74:021
1.99
(-4.60%)
(-10.63%)
(-12.11%)
(-11.13%)
(-14.31%
(-16.21%)
(-27.48%)
Table 14: Test rates of 6onv-6 CIFAR-10. Subscripts denote standard deviations, and bracketed numbers denote relative gains with respect to OBD. Unpruned models achieve 11.97% rate.
10.62%
8.86%
7.39%
6.18%
5.17%
4.32%
3.62%
OBD (baseline)
12.10=0021
42.61
13.18
14.28
15.54:2.40
16.8340.27
19.1440.32
OBD+LAP
12.51+0.22
13.22+0.48
13.68+0.67
14.31 4033
15.094036
16.31
17.29+..47
(43.41%)
(43.20%%
(42.23%)
(40.18%)
(-2.90%%
(-3.13%)
(-9.65 %)
LAP-act
12.11
12.72.0.11
12.9210.48
13.45
14.8610.15
16.47.006
18.48 10.3
(+0.125%
))
(-3,47%)
())87%)
(-4.40%)
(-2.13%)
(-3.46%%
15

---

Published as a conference paper at ICLR 2020
Table 15: Computation time of OBD, OBD+LAP and LAP-act (averaged over 100 trials).
FCN
Conv-6
OBD (baseline)
11.38 (s)
167.87 (s)
OBD+LAP
11.61 (s)
168.03 (s)
LAP-act
6,28 (s)
8.95 (s)
weight parameters
1.15M
2.26M
G COMPUTATIONAL COST OF LOOKING AHEAD
In this section, we briefly describe how a computation of lookahead distortion Eq. (5) can done efficiently, and provide experimental comparisons of average computation times for MP and LAP. It tums out that most the computational load for LAP comes from the sorting procedure, and tensor operations introduce only minimal overhead.
MP comprises of three steps: (1) computing the absolute value of the tensor, (2) sorting the absolute values, and (3) selecting the cut-off threshold and zero-ing out the weights under the threshold. Steps (2) and (3) remain the same LAP, and typically takes On log n) steps (n denotes the number of parameters in layer). On the other hand, Step (1) is replaced by computing the lookahead distortion
(ww |w|- ||W,-1 [i. |[ A:]l
for each parameter w. Fortunately, this need not be computed separately for each parameter. Indeed, one can perform tensor operations compute the squared lookahead distortion, which has the same ordering with lookahead distortion. For fully-connected layers with 2-dimensional Jacobians, the
squared lookahead distortion for W Rdixx W; E BRd xd, 1, S,W;1 R 1xd, is
(W,) = (1:-1 i+1
T O (W?2) (WO21))
(25)
where 1, denotes all-one matrix of size dj-2 x d;; multiplying 1, denotes summing operation along an axis and duplicating summed results into the axis, and 62 denotes the element-wise square oper- ation. The case of convolutional layers can be handled similarly.
We note that an implementation of Eq. (25) is very simple. Indeed, the following PyTorch code segment calculates a lookahead score matrix:
def Lookahead Brrkahead_scrree_ee score (W, W. prev,, W W_next)
W_prev_sq (W (W_prev ** 2) sum (dim-1)
W W_prev_mat "_prrv__q.vive view (1, -1) repeat (W. size (0) 1)
W_next_sq (W_next 2) sum (dim=0)
W_next_mat L.next_sq.vies (-1, 1) repeat size (1))
return (W++2) *W. prrpprreettee Seepatt=__eee___e_e___ mat
Combined with modern tensor computation frameworks, computing Eq. (25) does not introduce heavy overhead. To show this, we compare the computation time of MP and LAP for six neural networks in Table 16, where fixed the layerwise pruning rate to be uniformly 90%. The codes are implemented with PyTorch, and the computations have taken place on 40 CPUs of Intel Xeon E5-2630v4 @ 2.20GHz. All figures averaged over 100 trials.
We make two observations from Table 16. First, the time required for LAP did not exceed 150% of the time required for MP, confirming our claim on the computational benefits of LAP. Second, most of the added computation comes from considering the factors from batch normalization, without which the added computation load =5%.
16

---

Published as a conference paper at ICLR 2020
Table 16: Computation time of MP and LAP on FCN, Conv-6, VGG-(11,16.19). ResNet-18. All
figures are averaged over 100 independent trials. Bracketed numbers denote relative increments. Number of weight parameters denote the number of parameters that are the target of pruning.
FCN
Conv-6
VGG-11
VGG-16
VGG-19
ResNet-18
MP (haseline)
46.23 (ms)
108.92 (ms)
542.95 (ms)
865.91 (ms)
1188.29 (ms)
641.59 (ms)
LAP (w/o batchnorm)
47.73 (ms)
116.74 (ms)
560.60 (ms)
912.47 (ms)
1241.55 (ms)
671.61 (ms)
(+3.14%)
(+7.18%)
(+3.25%)
(45.28%)
(44.48%)
(+4.68%)
LAP
805 98 (ms)
1213.24 (ms)
1653.02 (ms)
943,88 (ms)
(+48.44 44%)
(+40. (1%)
(+39.19%)
(+47.11%)
# weight parameters
1.15M
2.26M
9.23M
14.72M
20.03M
10.99M
H LOOKAHEAD FOR CHANNEL PRUNING
In the main text, LAP is compared to MP in the context of unstructured pruning, where we do not impose any structural constraints on the set of connections be pruned together. On the other hand, the magnitude-based pruning methods are also being used popularly as a baseline for channel pruning (Ye et al., 2018), which falls under the category of structured pruning.
MP in channel pruning is typically done by removing channels with smallest aggregated weight magnitudes; this aggregation can be done by either taking & nnorr or é2-norm of magnitudes. Simi- larly, we can consider channel pruning scheme based on an & or Eg aggregation of LAP distortions, which we will call LAP-& 1 and LAP-E2 (as opposed to MP-(1 and MP-(2).
We compare the performances of LAP-based channel pruning methods to MP-based channel pruning methods, along with another baseline of random channel pruning (denoted with RP). We test with Conv-6 (Table 17) and VGG-19 (Table 18) networks on CIFAR-10 dataset. All reported figures are averaged over five trials, experimental settings are identical to the unstructure pruning experiments unless noted otherwise.
Similar to the case of unstructured pruning, we observe that LAP-based methods consistently out- perform MP-based methods. Comparing & with l aggregation, we note that LAP-(2 performs better than LAP-L in both experiments, by a small margin. Among MP-based methods, we do not observe any similar dominance.
Table 17: Test error rates of Conv-6 CIFAR-10 for channel pruning. Subscripts denote standard deviations, and bracketed numbers denote relative gains with respect to the best of MP-(1 and MP- l2. Unpruned models achieve 1 11.97% error rate.
34.40%
24.01%
16.81%
11.77%
8.24%
5.76%
4.04%
2.82%
MP-2;
12.55=004
13.62+044
16.85=1.14
20.05=061
23.98
27.75+039
37.56=2.16
MP-1z
11.97=029
12.66
14.17+0.53
16.69=1.s
20.09=096
+1.6
28.30+147
35.18=130
RP
12.94=041
14.82=027
17.57=005
20. 10.54
22.50=a.9
25.86+002
30.644087
38.26=278
LAP-E;
12.08=028
12.57=002
13.37
15.46=0.1
18.30=053
21.40
24.88
30.43-1.07
(+0.87%)
(40.16%)
(-185%%
(-7.42%
(-8.76%)
(-10.75%)
(-10.37%)
(-13.50%)
LAP-&2
11.70-037
12.31=023
13.70=us1
15.42=2062
17.94-091
21.38+1.24
24.36=:1.5
30.55=3.4
(-2.21%
(-1.90%)
(+0.62%)
(-7.62%%
(-10.55%)
(-10.84%)
(-12.23%)
(-13.16%%
Table 18: Test error rates of VGG-19 on CIFAR-10 for channel pruning. Subscripts denote standard deviations, and bracketed numbers denote relative gains with respect to the best of MP-4, and MP- l. Unpruned models achieve 9. 9.02% error rate.
34.30%
28.70%
24.01%
20.09%
16.81%
14.06%
11.76%
9.84%
MP-6,
9,25+122
9,81
10.12-011
10.77=033
14.28
14.53
18. 18.8443.53
23.7144.94
MP-6,
9,401003
9.73
10.27_0.1
10.61=074
12.26:119
1..74:...6
17.70.3.46
33.27:15m
RP
10.581061
11.72.126
12.86_039
19.491128
20.1912245
24.9916.33
14.52.11661 16.18
LAP-6
9.051
9,461025
10.07-0.6
10,53 0227
10.95
12.37.074
15. 15.501081
16.65
(-2.23%)
(-2.75%)
(-0.47%)
(-0.81 %
(-10.73%)
(-9.99%)
(-12.43%)
(-29.77%)
LAP-12
9.0611020
9,42
9.74_037 0.37
10.53 0.40
10.74...22
11.87.10.3
13.51
15.67
(-2.10%)
(-3.21% %)
(-3.77%)
(-0.79%
(-12.39%)
(-13.61 %)
(-23.66%
(-33.92%)
17

---

Published as a conference paper at ICLR 2020
I LOOKAHEAD FOR GLOBAL PRUNING
In this section, we present global pruning results for MP, LAP, OBD, OBD+LAP and LAP-act in Table 19 and Table 20. In this methods, we prune a fraction of weights with smallest scores (e.g. weight magnitude, lookahead distortion, Hessian-based scores) among all weights in the whole net- work. The suffix "-normalize" in the tables denotes that the score is normalized by the Frobenius norm of the corresponding layer's ss score. For MP, LAP, OBD+LAP and LAP-act, we only report the results for global pruning with normalization, as the normalized versions outperform the unnormal- ized ones. In the case of OBD, whose score is already globally designed, we report the results for both unnormalized and normalized versions.
As demonstrated in Section 3.2 for fixed layerwise pruning rates, we observe that LAP and its vari- ants perform better than their global pruning baselines, i.c. MP-normalize and OBD. We also note that LAP-normalizz performs better than MP with pre-specified layerwise pruning rates (appeared in Section 3.2), with a larger gap for higher levels sparsity.
Table 19: Test error rates of FCN on MNIST for global pruning. Subscripts denote standard devia- tions, and bracketed numbers denote relative gains with respect to MP-normalize (for data-agnostic algorithms) and OBD-normalize (for data-dependent algorithms), respectively. Unpruned models achieve 1.98% error rate.
6.36%
3.21%
1.63%
0.84%
0.43%
0.23%
0.12%
MP-normmlize (baselinc)
1.824o.08
2,16#0.06
2.72+to.17
3.54
6.54
59.59+16.22
08.65
LAP -oP-noomalize
1.71100.0
2.07
2.6910.09
3.42
4.15
6.68
19.18
(-6.16%%
(44.26%)
(-1.03%)
(+3,33%)
33).57%)
(-88.79%)
(-78.36%)
OBD (buseline)
1.71
1.93
2.12
2.82
3.59
10.52 5.12
OBD-nomalize
1.71
1.92:0.10
2.22:0.08
2.77
3.55
4.99 26
11.08
(-0.12%)
(-0.52%)
(+4,62%)
(-1884%
(-1.11%)
(-2.54%)
(+5,36%)
OBD+LAP-normal
1.84+0.13
2.00+0.13
2.22+0.16
2.93+0.34
3.55+0.27
5.04
8.33=2261
(47.48%)
(+3.73%)
(+4.99%%
(43.97%)
(-1,22%)
(-1.52%)
(-20.79%)
LAP-act-normalize
1.68
1.80
2.06
2.80
3.50
4.82=0.27
8.50#1.16
(-1.77%
(-6.84%)
(-3.02%)
(-0.78%)
(-2.56%)
(-5.90%)
(-19.21%)
Table 20: Test error rates of Conv-6 on CIFAR-10 for global pruning. Subscripts denote standard deviations, and bracketed numbers denote relative gains with respect to MP-normalize (for data- agnostic algorithms) and OBD-normalize (for data-dependent algorithms), respectively. Unpruned models achieve 11.97% error rate.
10.62%
8.86%
7.39%
6.18%
5.17%
4.32%
3.62%
MP-normalize (baseline)
12.42+0.17
13.1420.35
14.17=0.40
15.39=0.40
17.57
21.01=0.42
24.40=1.57
IAP-normalize
11.81
22.23
12.44.0.22
13.02=0.12
13.73
15.97=0.30 14.81
())87%%
(-12.19%)
(-15.42%)
(-21.86 %)
(-29.61% %)
(-34.54%)
OBD (baseline)
12.0311064
12.30.0.53
12.64.10.15
13.1610.23
13.75
14.70....8
16.11.0.50
OBD-normalize
11.69=0.84
11.93=0.21
12.58
12.87=0.22
13.62
14.60
15.82=0.44
(-2.86%)
(-2.99%)
(-0.47%)
(-2,26%)
(-0.89%)
(-0.67%)
(-1.75%)
OBD+LAP-nommal
12.11
12.66:0.46
13.36=0.47
13.60=0.33
14.05
14,98=0.3
15.82=0.39
(+0.68%)
(+2.96%)
(45.66%)
(+3.30%%)
(+2.249%
(+1.89%)
(-1.809)
LAP-ac a-aactnoormalize
11.92=0.28
12.24=0.05
12.51
12.89=0.36
13.53
14.21
15.42=0.18
(-0.90%)
(-0.49%)
(-1.08%)
(-2.05%)
(-1.54%)
(-3.31%)
(-4.26%)
18

---

Published as a conference paper at ICLR 2020
J LAP-ALL: LOOKING AHEAD THE WHOLE NETWORK
We also report some experimental results on a variant lookahead pruning, coined LAP-alI, which treats (a linearized version of) the whole network an operator block. More specifically, one attempts to minimize the Frobenius distortion of the operator block
min
[J.+1J JMM O W.)J-1all
Mi M,llo:
where Jitja = J JW (Wa5-) J.W.).
We test LAP-all FCN under the same setup as in Section 3.2, and report the results in Table 21. All figures are averaged over five trials.
We observe that LAP-all achieves similar level of performance to LAP, while LAP-all underper- forms under high-sparsity regime. We suspect that such shortfall originates from the accumulation of error terms incurred by ignoring the effect of activation functions, by which the benefits of look- ing further fades. An in-depth theoretical analysis for the determination of an optimal "sight range" of LAP would be an interesting future direction.
Table 21: Test error rates of FCN on MNIST, with LAP-all variant. Subscripts denote standard deviations. Unpruned models achieve 1.98% error rate.
6.36%
3.21%
1.63%
0.84%
0.43%
0.23%
0.12%
MP (haseline)
1.75 0.11
2.53 0.09 0.14
3.32 0.27
4.77+ 0.22
19.85 8.67
67.62 9.91
RP
2.36+ 0.13
2.72+ 0.16
0.64
17.54 7.07
82.48 4.03
88.65 0.00
88.65= 0.00
LAP
1.67 0.11
1.89 0.12
2.48 0.13
3.29 n06
3.93 0.26
6.72. 0.44
16.45 5.61
LAP-all
1.64: 0.05
2.06 0.17
2.53 0.15
3.23 0.13
4.01 0.10
6.78 0.14
25.64 5.42.
K COMPARISON WITH SMALLER NETWORKS
As sanity check, we compare the performance of large neural networks pruned via MP and LAP to the performance of a small network. In particular, we prune VGG-16, VGG-19, and ResNet- 18 trained on CIFAR-10 dataset, to have similar number of parameters MobileNetV2 (Sandler et al., 2018). For training and pruning VGGs and ResNet, we follows the prior setup in Appendix while we use the same setup for training MobileNetV2 (Adam optimizer with learning rate of 3 10-4 with batch size 60, and trained 60k steps). We observe that models pruned via LAP (and MP) exhibit better performance compared to MobileNetV2, even when pruned to have a smaller number of parameters.
Table 22:
Test error rates of various networks CIFAR-10. Subscripts denote standard deviations, and bracketed numbers denote relative gains with respect to the unpruned MobileNetV2..
VGG-16
VGG-19
ResNet-18
MobileNetV2
Unpruned
9.33+0..15
9,02+0.36
8.68+0.21
9,81
MP
8,92+t0.15
9.4640.25
7.70-10.23
(-9.07%)
(-3.57%%
(-21.51 %
LAP
8.77=t0.20
0.30
7.73+1.22
(-10.60 %
(-5.20%)
(-21.20%%
weight parameters
2.09M/14.72M
2.06M/20.03M.
2.17M/10.99M
2.20M
(14.23%)
(10.28%)
(19.17%)
19

---

Published as a conference paper at ICLR 2020
L WHERE IS THE PERFORMANCE GAIN OF LAP COMING FROM?
In this section, we briefly discuss where the benefits of the sub-network discovered by LAP comes from; does LAP subnetwork have better generalizability or expressibility? For this purpose, we look into the generalization gap, i.e., the gap between the training and test accuracies, of the hypoth- esis learned via LAP procedure. Below we present plot of test accuracies (Fig. 4a) and a plot of generalization gap (Fig. 4b) for FCN trained with MNIST dataset. The plot hints us that the network structure learned by LAP may not necessarily have smaller generalizability. Remarkably, the gen- eralization gap of the MP-pruned models and the LAP-pruned models are very similar to each other; the benefits of I.AP subnetwork compared to MP would be that can express a better-perfoor pereer-perormiig architecture with network of similar sparsity and generalizability.
100
Generalization gap
Test accuracy
80
80
40
MP
MP +
20-
LAP
LAP
10
10
10
10"
10
10"
Fraction remaining weights
Fraction remaining weights
(a) Test accuracy
(b) Generalization gap
Figure 4: Test accuracy and generalization gap of FCN trained MNIST.
M CONNECTIONS TO IMPLICIT BIAS OF SGD
Another theoretical justification of using the lookahead distortion (Eq. (5)) for neural networks with nonlinear activation functions comes from recent discoveries regarding the implicit bias imposed by training procedures using stochastic gradient descent. More specifically. Du et al. (2018) proves the following result, generalizing the findings of Arora et al. (2018): For any two neighboring layers of fully-connected neural network using positive homogeneous activation functions, the quantity
(26)
remains constant for any hidden neuron j training via gradient flow. In other words, the total outward flow of weights is tied to the inward flow weights for each neuron. This observation hints the possibility of relative undergrowth of weight magnitude of an 'important' connection, in the case where the connection shares the same input/output neuron with other 'important' connections. From this viewpoint, the multiplicative factors in Eq. (5) take into account the abstract notion of neuronal importance score, assigning significance to connections to the neuron through which more gradient signals have flowed through. Without considering such factors, LAP reduces to the ordinary magnitude-bant based pruning.
20


Reviews:
[{"review_id": "SJla8mLA_r", "reviewer": "AnonReviewer3", "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 proposed Lookahead Pruning (LAP), a new method for model weight pruning to generate neural networks with sparse weights. The authors interpret the conventional magnitude pruning (MP) as pruning each layer individually while the proposed lookahead method considers neighboring layers' weights. Specifically, the proposed methods prune weights which introduce small distortion to the Jacobian matrix of 3 consecutively connected (linear) layers; and the conventional magnitude pruning can be viewed as a degenerated/special case of the LAP. The primary contributions of the paper are: 1) the authors propose the LAP method for fully connected layers; 2) they present empirical applications/extensions to models with non-linear-activations and batchnorms (which are two important components of modern neural networks); 3) The authors empirically show that LAP (and its variants such LAP-forward and LAP-forward-seq) can generate sparse models with better test accuracy than MP, across fully-connected network (FCN), and Conv models (such as VGG and ResNet) on MNIST and CIFAR dataset.\n\nI think the method in this paper is well motivated both mathematically (minimizing distortions of Jacobian) and intuitively (considering multiple layers holistically). The empirical benefits of the proposed method is properly validated against MP in various dataset and models. Also the paper is well written. Thus I give weak accept and I am willing to raise the score if convincing clarification on the following questions can be provided in author responses and in the future draft:\n\n1. As the LAP method introduces higher computation overhead in pruning weights, I was wondering how it compares to MP in terms of run-time-efficiency. As LAP requires computing a score for each single weight value (though some of the computationally heavy terms can be reused), it is important to discuss how long does LAP pruning take, comparing to the run-time of retraining (after pruning). This will help further evaluate the empirical efficiency of the LAP method.\n\n2. The experiment focus on CNNs while the authors advocating versatility of the methods. Thus I was wondering how LAP performs on models in other domains, such as transformer-based NLP models.\n\n3. (Relatively minor). The experiment purely focused on comparing pruning methods. To demonstrate the empirical merits of LAP, I think it will be more convincing to also compare with naive baselines of using narrow / shallower networks such as in Sohoni et al.[1]. This will demonstrate that pruning itself and LAP as an instantiation of pruning should be considered over these naive narrow / shallower baselines with the same amount of weight parameters as pruned models.\n\n4. The tables (table 1-5) are massive but the take-away message is not crystal clear in the text or captions of the table. Is the take-away message something like 1) one might want to use LAP-forward(backward) over LAP when you have very high sparsity, and 2) the sequential versions can further enhance the performance? \n\n\nMinor suggestions to improve the paper:\n\n1. Line 5 and 6 in Algorithm 1 is confusing. I suppose the authors mean selecting the weights which trigger small value for L to zero-out. To me the current line 5,6 does not directly reflect this.\n\n2. It might be good to provide a proof in appendix on equation 5), it take me quite a few minutes to verify it. Providing a proof can help readers to read more smoothly.\n\n3. The order of the content can be slight reorganized, e.g. why talking about the adaptation of LAP on batchnorm after you discussed all the directional and sequential variants of LAP?\n\nReference\n[1] Low-Memory Neural Network Training: A Technical Report. Sohoni et al. \n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "S1eyoo0F9B", "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 new magnitude-based pruning method (and a few variants) by extending the single-layer distortion minimization problem to multi-layer cases so that the correlation between layers is taken into account. Particularly, the authors take into account the weight tensors of neighboring layers in addition to the original layer. The proposed algorithm looks promising and interesting. Empirically, the authors show that the proposed method consistently outperforms the standard magnitude-based pruning method.\n\nOverall, the paper is well-written and I think the algorithm is novel. Therefore, I've given the score of 6.\n\nComments:\n(1) It seems obvious that the proposed method would increase the computation cost, but the authors didn't give any discussion or results on that. \n(2) Although the main focus of the paper is magnitude-based pruning, I think the authors should include one baseline of Hessian-based pruning methods for comparison. As I know, the computation overhead of Hessian-based methods (e.g., OBD) is relatively small for the networks used in this paper. In particular, Hessian-based pruning methods can also be interpreted as a distortion minimization problem but in a different space/metric. So I wonder if the authors can extend LAP to Hessian-based pruning methods.\n(3) The authors introduced LAP with deep linear networks. However, the details of LAP in non-linear network are missing. I encourage the authors to fill in the details in section 2.2 in the next revision.\n(4) Currently, all experiments are done on CIFAR-10 dataset. I wonder if the author can include one more dataset. For example, comparison between MP and LAP on Tiny-ImageNet or even ImageNet. As I know, experiments of ImageNet can fit into a 4-GPU server for magnitude-based methods.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "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."}, "extra_text": {}}, {"review_id": "HJlG50bnqr", "reviewer": "AnonReviewer5", "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": "[Summary]:\nThis paper interprets the underlying objective of magnitude pruning(MP) as minimizing the Frobenius distortion of a single layer. Then the authors provide a motivating example to show that MP may cause a large Frobenius distortion due to ignoring the inter-layer interactions. Based on this observation, the authors propose a simple modification to MP by explicitly enforcing to minimize the Frobenius distortion of an operator block consisting of multiple linear layers, and demonstrate better performance than MP on CIFAR10 and MNIST datasets.\n\n[Pros]:\n- The proposed algorithm is simple and easy to implement.\n- The empirical results show that the proposed method beat MP consistently, and in particular for high sparsities.\n- The ablation study about LAP, LFP and LBP is interesting.\n\n[Cons & Questions]:\n(1) Minimizing Frobenius distortion is not meaningful, and it only minimizes the change in the output to the first order. Moreover, I don’t think minimizing the change in the output is as meaningful as minimizing the increase in training error as is done in Hessian-based pruning methods, e.g., Optimal Brain Damage (OBD) ( LeCun et al. 1989). My reason is that it is possible that the output changes a lot, but the training error still remains low after pruning.\n\n(2) Can the authors elaborate what are the advantages of MP/LAP over Hessian-based pruning, such as OBD? OBD only needs the diagonal Hessian matrix and is also tractable, and MP is only a special case of OBD when the Hessian is an identity matrix. I am not quite convinced MP can achieve state-of-the-art performance, and also Gale et al. (2019) did not include any Hessian-based pruning algorithm into comparisons. Therefore, it would be great if the authors can provide more justifications for why MP/LAP is advantageous to Hessian-based pruning methods, e.g., OBD. Besides, I would be happy to see the authors can include OBD as a baseline in the experiments.\n\n(3) The interpretation of the objective of MP as minimizing the Frobenius distortion is well-known, and more general results are already presented in Dong et al. (2017). The authors should discuss it in the main paragraph and give the corresponding credits to Dong et al. (2017).\n\n(4) Why do you need to specify the pruning ratio for each layer manually? It makes MP or LAP hard to use in practice, and it usually needs expert knowledge to specify the pruning ratios for different layers. For Hessian-based methods, it reflects the change in loss and thus can be used to automatically determine the pruning ratio at each layer. \n\n(5) In table 1 and table 2, LFP is better than LBP when pruning ratio is low, while LBP becomes better for high pruning ratios. Is there any explanations?\n\n(6) My understanding of the LAP is that it tries to minimize the Frobenius distortion of the input-output Jacobian matrix of the operator block. In the paper, the operator block consists of 3 consecutive linear layers. I am curious about what is the performance if we treat the entire network as an operator block?\n\n(7) The experiments are only conducted on MNIST and CIFAR-10, which are overly simple. Further experiments on larger datasets will make the paper stronger and the results more convincing. Anyway, this is not a big issue, but I encourage the authors can test the proposed method on more challenging datasets and make fair comparisons.\n\nOverall, my rating is largely due to the concerns of (1)&(2).\n\n[References]:\nY. LeCun, J. S. Denker, and S. A. Solla. Optimal brain damage. In Advances in Neural Information Processing Systems, 1989.\nT. Gale, E. Elsen, and S. Hooker. The state of sparsity in deep neural networks. arXiv preprint 1902.09574, 2019.\nDong, Xin, Shangyu Chen, and Sinno Pan. \"Learning to prune deep neural networks via layer-wise optimal brain surgeon.\" Advances in Neural Information Processing Systems. 2017.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkgyu_mq5r", "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": "*Summary*\nThe paper proposes a multi-layer alternative to magnitude-based pruning. The operations entailed in the previous, current, and subsequent layers are treated as linear operations (by omitting any nonlinearities), weights are selected for pruning to minimize the \"Frobenius distortion\", the Frobenius norm of the difference between products of the (i-1, i, i+1)-layer Jacobians with and without the selected weight. This simplifies to a cost-effective pruning criterion. In spite of the simplistic linear setting assumed for the derivation, results show the criterion prunes better than weight-based methods at unstructured pruning of a variety of modern architectures with CIFAR-10, particularly excelling at higher sparsity.\n\n*Rating*\nThe paper has some clear positives, particularly:\n    + Clear writing and formatting\n    + Simple method\n    + Good structure for the experimental analysis (with 5x replications!)\nHowever there are a few limitations, noted below; while none is fatal on its own, in total the limitations have led me to recommend \"weak reject\" currently.\n\nLimitations of the method:\n(1) Residual networks: The lack of an explicit strategy for handling residual connections (and the accompanying worsened relative performance) is a notable limitation since residual/skip connections are nearly universal in state-of-the-art large networks. The performance was shown to still be *slightly* better than with magnitude pruning.\n(2) Global ranking: Since connections are pruned layerwise, rather than taking the best-k neurons across the entire network at once, I assume that the LAP pruning criterion doesn't scale reasonably across layers. This implies that the method cannot be used to learn network structure. Instead the user must decide the desired number of neurons at each layer.\n(3) Structured pruning: There is no mention of pruning entire convolutional kernels or \"neurons\" at once, so I assume that only individual weights were pruned. Since structured pruning is the simplest way to achieve speedup in network inference (as opposed to merely reduction in model size), how does the LAP criterion perform when adapted for structured pruning, e.g. removing filters/neurons with the best average LAP score?\n\nLimitations of the experiments:\n(4) Baselines: While the paper is explicitly focused on an easy to compute replacement for magnitude-based pruning, there are a wide variety of alternative methods available. These vary in complexity, runtime, etc., but they deserve mention and either explicit comparison in the experiments or reasoning to justify the omission of such comparisons.\n(5) ImageNet: (Insert obligatory statement about the ubiquity of ImageNet experiments, ...) While it is cliche to request ImageNet experiments and CIFAR-10 is a helpful stand-in, they would be really nice to have.\n(6) Activations after non-linearities: While Fig. 3 and the remaining experiments present a reasonable case that the presence of non-linearities doesn't prevent LAP from improving upon magnitude-based pruning, it doesn't resolve the issue either. Whether considering negative values clipped by with ReLU or large magnitude values that are squashed by sigmoid and tanh, the linear-only model is a poor approximation for some unknown fraction of neurons for probably most inputs. Does this mean that LAP is underperforming in those cases? Are those cases sufficiently rare or randomly distributed that they are merely noise? Is there another mechanism at play? In practical terms, how much does the activation rate (positive for ReLU, linear/unsquashed for sigmoid/tanh) vary by neuron? This seems like a reasonably simple thing to compute and incorporate into pruning.\n\n*Notes*\nEq. (4): Is (4) simply the one-step/greedy approximation to the optimization in (3)? If so, it may be helpful to state this explicitly. Also, is $w = W_i[j,k]$? If so, this is useful to explicitly state.\nSec 2.1: Consider noting that the linear-model setup is used to construct the method, but non-linearities are addressed subsequently\nSec 2.2: Is the activation probability p_j used in practice, or is it merely an explanatory device?\npg5: \"gradually prune (p/5)%\" and marked with a suffix '-seq'\"\npg5: note that residual connections are discussed in the experiments?\nTables 3-6: note that these all use CIFAR-10", "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 introduces a pruning criterion which is similar to magnitude-based pruning, but which accounts for the interactions between layers. The reviewers have gone through the paper carefully, and after back-and-forth with the authors, they are all satisfied with the paper and support acceptance.
Decision: Accept (Poster)