SOSP: Efficiently Capturing Global Correlations by Second-Order Structured Pruning
Authors: Manuel Nonnenmacher
Thomas Pfeil
Ingo Steinwart
David Reeb
Venue: ICLR 2022 Spotlight (2022)
Keywords: Structured Pruning
Saliency-based Pruning
Network Compression
Hessian Approximation
Neural Architecture Search
Deep Learning
Computer Vision

Abstract: Pruning neural networks reduces inference time and memory costs. On standard hardware, these benefits will be especially prominent if coarse-grained structures, like feature maps, are pruned. We devise two novel saliency-based methods for second-order structured pruning (SOSP) which include correlations among all structures and layers. Our main method SOSP-H employs an innovative second-order approximation, which enables saliency evaluations by fast Hessian-vector products. SOSP-H thereby scales like a first-order method despite taking into account the full Hessian. We validate SOSP-H by comparing it to our second method SOSP-I that uses a well-established Hessian approximation, and to numerous state-of-the-art methods. While SOSP-H performs on par or better in terms of accuracy, it has clear advantages in terms of scalability and efficiency. This allowed us to scale SOSP-H to large-scale vision tasks, even though it captures correlations across all layers of the network. To underscore the global nature of our pruning methods, we evaluate their performance not only by removing structures from a pretrained network, but also by detecting architectural bottlenecks. We show that our algorithms allow to systematically reveal architectural bottlenecks, which we then remove to further increase the accuracy of the networks.

Published as a conference paper at ICLR 2022
SOSP: EFFICIENTLY CAPTURING GLOBAL CORRELA- TIONS BY SECOND-ORDER STRUCTURED PRUNING
Manuel Nonnenmacher" Bosch Center for Artificial Intelligence (BCAI) Robert Bosch GmbH 71272 Renningen, Germany
Thomas Pfeil
Bosch Center for Artificial Intelligence (BCAI)
Robert Bosch GmbH
71272 Renningen, Germany
Ingo Steinwart
David Reeb
Institute for Stochastics and Applications University of Stuttgart 70569 Stuttgart, Germany
Bosch Center for Artificial Intelligence (BCAI)
Robert Bosch GmbH
71272 Renningen, Germany
ABSTRACT
Pruning neural networks reduces inference time and memory costs. On standard hardware, these benefits will be especially prominent if coarse-grained structures, like feature maps, are pruned. We devise two novel saliency-based methods for second-order structured pruning (SOSP) which include correlations among all struc- tures and layers. Our main method SOSP-H employs an innovative second-ordes -odder approximation, which enables saliency evaluations by fast Hessian-vedt products. SOSP-H thereby scales like a first-order method despite taking into account the full Hessian. We validate SOSP-H by comparing it to our second method SOSP-I that uses a well-established Hessian approximation, and to numerous state-of-the-an methods. While SOSP-H performs on par better in terms of accuracy, it has clear advantages in terms of scalability and efficiency. This allowed us to scale SOSP-H H large-scale vision tasks, even though it captures correlations across all layers of the network. To underscore the global nature of our pruning methods, we evaluate their performance not only by removing structures from pretrained network, but also by detecting architectural bottlenecks. We show that algorithms allow to systematically reveal architectural bottlenecks, which we then widen to further increase the accuracy of the networks.
INTRODUCTION
Deep neural networks have consistently grown in size over the last years with increasing performance. However, this increase in size leads to slower inference, higher computational requirements and higher cost. To reduce the size of the networks without affecting their performance, a large number of pruning algorithms have been proposed LeCn al. 1990; Hassibi al. 1993 Reed 1993
Han et al. 2015; Blalock et al. 2020). Pruning can either be wnstructured, i.e. removing individual weights, or structured, i.c. removing entire substructures like nodes or channels. Single-shot pruning methods, as investigated in this work, usually consist of three steps: 1) training, 2) pruning, 3) another training step often referred to as fine-tuning.
Unstructured pruning can significantly reduce the number of parameters of a neural network with only little loss the accuracy, but the resulting networks often show only a marginal improvement in training and inference time, unless specialized hardware is used (He et al.) 2017). In contrast, struc- tured pruning can directly reduce inference time and even training time when applied initialization (Lee et al.] 2018). To exploit these advantages, in this work, we focus on structured pruning.
Global pruning removes structure by structure from all available structures of network until predefined percentage of pruned structures is reached. Recent examples for global structured pruning methods are NN Slimming (Liu et al. 2017), C-OBD and EigenDamage (Wang et al. 2019a). Local
'Email: manuel nonnenmacher@@ee bosch. com

---

Published as a conference paper at ICLR 2022
pruning, the other hand, first subdivides all global structures into subsets (e.g. layers) and removes a percentage of structures of each subset. Recent examples for local pruning methods are HRank (Lin et al., 2019). CCP (Peng et al. 2019), FPGM (He et al. 2019) and Variational Pruning (Zhao) et al. 2019). Most local pruning schemes use predefined layer-wise pruning ratio, which fixes the percentage of structures removed per layer. While this prevents the layers from collapsing, it also reduces some of the degrees of freedom, since some layers may be less important than others. Other local pruning methods like AMC (He al. 2018 learn the layer-wise pruning ratios in first step.
A key challenge for global saliency-based pruning is to find an objective which can be efficiently calculated to make the approach scalable to large-scale, modern neural networks. While second-order pruning methods are usually more accurate than first-orde methods (Molchanov et al. 2019), calcu- lating the full second-order saliency objective is intractable for modern neural networks. Therefore, most saliency-based pruning methods such as OBD /e.g.[LeCCun et al. 1990) or C-OBD (Wang et al.) 2019a) evaluate the effect of removing single weight or structure on the loss of the neural network in isolation. However, this neglects possible correlations between different structures, which are captured by the off-diagonal second-order terms, and hence, can significantly harm the estimation of the sensitivities. Finding global second-order method that both considers off- off-diagonal terms and scales to modern neural networks is still an unsolved research question.
Our main goal in this work is to devise simple and efficient second-order pruning method that considers all global correlations for structured sensitivity pruning. In addition, we want to highlight the benefits that such methods may have over other structured global and local pruning schemes.
Our contributions are as follows:
We develop two novel saliency-based pruning methods for second-order structured pruning (SOSP) and analyze them theoretically. We show that both of our methods drastically improve the complexity of a naive second-order approach, which is usually intractable for modern neural networks. Further, we show that our SOSP-H method, which is based fast Hessian-vector products, has the same low complexity as first-order methods, while taking the full Hessian into account.
We compare the performance and the scaling of SOSP-H to that of SOSP-I, which is based on the well-known Gauss-Newton approximation. While both methods perform on par, SOSP-H shows better scaling. We then benchmark our SOSP methods against variety of state-of-th--an pruning methods and show that they achieve comparable or better results at lower computational costs for pruning.
We exploit the structure of the pruning masks found by our SOSP methods to widen architectural bottlenecks, which further improves the performance of the pruned networks. We diagnose layers with disproportionally low pruning ratios as architectural bottlenecks.
Related work is discussed in the light of our results in the Discussion section (Sec. 4. PyTTorch code implementing our method is provided at https///giubb..ooom/bbohrrrsrrre
SOSP: SECOND-ORDED STRUCTURED PRUNING
A neural network (NN) maps an input E Rd to an output fo(x) E RDD, where A E R. are its P parameters. NN training proceeds, after random initialization = Go of the weights, by mini- batch stochastic gradient descent on the empirical loss L()) == x Σn (fo(zn), yn), given the training dataset (1),,,))...., (#N, yN)].. In the classification case, y/ E (1...., . D} is discrete ground-truth label and ((fo(T).)) = log a (Jo (x)),, the cross-entropy loss, with o TRD - R
the softmax- For regression, E RR and ((fo(z), y) = 1 fz( yll is the squared loss.
Structured pruning aims to remove weights or rather entire structures from NN fa with parameters A structure can be a filter (channel) in a convolutional layer, a neuron in a fully-connected layer, or an entire layer in parallel architecture. We assume the NN in question has been segmented into S structures s = 1,..., S, which can potentially be pruned. We define the notation 0, E R as the vector whose only nonzero components are those weights from that belong to structure Then,
We require that each weight is assigned to most structure. In practice, we associate with each structure those weights that go into the structure, rather than those that leave it.
2

---

Published as a conference paper at ICLR 2022
pruning mask is set M (......, 8m of structures, and applying mask M to NN fo means to consider the NN with parameter vector A,M := 8 E 8,.
We now develop our pruning methods that incorporate global correlations into their saliency as- sessment by efficiently including the second-order loss terms. Our method SOSP-I allows direct interpretation in terms of individual loss sensitivities, while main method SOSP-H remains very efficient for large-scale networks due to its Hessian- vector product approximation.
The basic idea behind both pruning methods is select the pruning mask M to (approxi- mately) minimize the joint effect on the network loss
X(M) = [C(0) - C( M)]
of removing all structures in M, subject a constraint on the overall pruning ratio. To circumvent this exponentially large search space, we approximate the loss up to second order, so that
(2 =
0
dc(()
1
Σ
6 d' (())
db det 02
(1)
de
2
.EM
8.'EM
collapses to single-structure contributions plus pairwise correlations.
The first-order terms \ (s) := A. dd( in [ are efficient to evaluate by computing the gradient dC( E IR! once and then a (sparse) dot product for every 8. In contrast, the network Hessian (0) de /00)/d02 therefore propose two different schemes to efficiently overcome this obstacle. We name the full methods SOSP-I (individual sensitivities) and SOSP-H (Hessian-vector product).
PxP in (1) is prohibitively expensive to compute store in full. We
2.1 SOSP-I: SALIENCY FROM INDIVIDUAL SENSITIVITIES
SOSP-I approximates each individual term 0-¹ (0)00, in I efficiently, as we will show in Eq. ( We will therefore consider an upper bound to Eq. ① which measures all sensitivities individually:
dC(())
(M)
Σ SEM
A
Σ 10tT (()002)
de
The absolute values are to prevent cancellations among the individual sensitivities of the network loss to the removal of structures, i.e. the derivatives X (s), and individual correlations A H(0)0,, While objectives other than X/ are equally possible in the method, including x2 and variants with the absolute values not pulled in the way, we found X/ to empirically perform best overall.
Then, SOSP-I iteratively selects the structures to prune, based the objective (2): Starting from an empty pruning mask M = () we iteratively add M the structure 8 & M that minimizes the overall sensitivity (M U {8}). ). In practice, the algorithm pre-computes the matrix Q E S
dl( 0
Qs 00 H(0)0,
(3)
dB
and selects each iteration structure M to prune by
arg min X/(M (s}) { arg min agM
(Qa, +2 > Qa.)).
*gM
s'EM
terminating at the desired pruning ratio. To compute Q efficiently, we show in App. terms can be approximated as
that the Hessian
N" N Σ (M(x))0.) Ru (o(xn)0.).
0" H(0)0 Rs
(5)
Herein, the NN gradient ((x) (ofo( E DxP forms the basis of the well-established Gauss- Newton approximation (see App. Bor more details) used for the Hessian, and the matrices R, E DDDD are diagonal plus a rank-1 contribution (App. B For further efficiency gains, the sum runs over a random subsample of size N' N. In practice, one pre-computes all (sparse) products Φ(x,), )0, IR' starting from the efficiently computable gradient of ((x,), before aggregating batch onto the terms 87 H (8) (,) Eq. (5) also has an interpretation as output correlations between certain network modifications, without derivatives (App. C

---

Published as a conference paper at ICLR 2022
2.2 H: SALIENCY FROM RESSIAN-VECTOR PRODUCT
SOSP-H treats the second-order terms in ① in different way, motivated by the limit of large pruning
ratios: At high pruning ratios, the sum Es'Ess 0, in I can be approximated by Σx= 0, =: Ostrue (this equals 0 if every NN weight belongs to some structure s). The second-order term EM 05. (0)0g, ~ (EneM ( (H)) thus becomes tractable since the Hessian-vector product ( is efficiently computable by variant of the backpropagation algorithm. To account for each structure & and for the first- and second-order contributions separately, as above, we place absolute value signs in (1 so to arrive at the final objective X (M) == ΣEEM X (s) with
dC(O) 07
X
oo (H())0struc)
(6)
d0
To minimize X (M). SOSP-H starts from an empty pruning mask M { and successively adds to M structure s M with smallest > (s), until the desired pruning ratio is reached.
Unlike the the Hessian- vectoo product. But SOSP-H can therefore not account for individual absolute s-s'- correlations, as some of those may cancel in the last term in Eq. ( contrary to 2 Both SOSP-H and SOSP-I reduce to the same first-order pruning method when neglecting the second order, i.e. setting H (0) := 0; we compare to the resulting first-order method in Sec. 3.1 (see also App. A.I.
approximation in SOSP-I, SOSP-H uses the exact Hessian (()) in
2.3 COMPUTATIONAL COMPLEXITY
We detail here the computational complexities of our methods (for the experimental evaluation see Sec. 3.2). The approximation of Q in (3) requires complexity O
+ P)) O(N' for computing all ((r,)0., where F N P denotes the cost of one forward pass through the network (F = P for fully-connected NNs), plus D(N'DS)) for the sum in ( This is tractable for modern NNs, while including the exact H (0) would have complexity at least O DSF.. Once Q has been computed, the selection procedure based on (4) has overall complexity O(S3). which is feasible for most modern convolutional NNs (Sec. 3.2). The total complexity of the SOSP-I method is thus
O(N' DF) + O(N' D + O
SOSP-H H requires computational complexity O(N'DF) both to compute all the first-order well as all the second-order terms in Eq. 6 Together with the sorting of the saliency values X!" (s). SOSP-H has thus the same low overall complexity
first-order method, namely
D(' + ((g)).
Due to its weak dependency on S, in practice, SOSP-H efficiently scales to large modern networks (see Sec. B.2). and may even be used for unstructured second-order pruning, where 5 = P.
Both of our methods scale much better than naively including all off-diagonal Hessian terms, which is intractable for modern NNs due to its DSF) scaling. Since SOSP-I builds on individual absolute sensitivities and on the established Gauss-Newtor approximation, we use SOSP-I in the following in particular validate our more efficient main method SOSP-H.
3 RESULTS
To evaluate our methods, we train and prune VGGs (Simonyan & Zisserman, 2014). ResNets He al. 2016), PlainNet (He et al. 2016), and DenseNets (Huang al. 2017 on the Cifar10/100 (Krizhevsky et al. 2009) and ImageNet (Dng et al. 2009) datasets. Stochastic gradient descent with an initial learning rate of 0. momentum of 0.9 and weight decay of 10 used train these networks. For ResNet-32/56 and VGG-Net on Cifar 10/100,000 we use a batch size of 128, train for 200 epochs and reduce the learning rate by a factor of 10 after 120 and 160 epochs. For DenseNet-40 on Cifar10/100, we train for 300 epochs and reduce the learning rate after 150 and 225 epochs. To fine-tune the network after pruning, we exactly repeat this learning rate schedule. For ResNets on ImageNet, we use a batch size of 256, train for 128 epochs and use cosine learning rate decay. For all networks, we prune feature maps (i.e. channels) from all layers except the last fully-connected layer; for ResNets, we also exclude the downsampling- path path from pruning. We approximate the Hessians by a subsample of size N' = 1000 (see Sec. 2.1. We report the best or average final test accuracy over 3 trials if not noted otherwise.
4

---

Published as a conference paper at ICLR 2022
Comparison of SOSP to other global pruning methods for high pruning ratios. The compari- son for moderate pruning ratios is deferred to the appendix (sce App. A.3). We tuned our pruning ratios to similar values reported by the referred methods. To ensure identical implementations of the network models in PyTorch, reference numbers are taken from Wang et al. (2019a) and Mingjie & Zhuang (2018). In accordance with all referred methods, we report the mean and standard deviation of the best accuracies observed during fine-tuning. For final accuracies after fine-tuning see App. denotes the baseline model. Both SOSP methods perform either on par outperform the competing global pruning methods.
Table 1:
A.13
Dataset
Cifar10
Cifar100
Tost acc.
Reduct, weights (%)
Reduct. MACs (%)
Test acc.
Reduct. weights (%)
Reduct. MACs (%)
Method
(%)
(%)
YGG-Net
73.45
NN Slimming
85.01
97.85
97.89
58. 69
97.76
94.09
Slim. +/4
91.99
97.93
$7.07
97.59
C-OBD
92.34 0.18
97.68 + 0.02
77.39
0,36
58.07
= 0.60
97.97 + 0.04
77:55 + 0.25
EigenDamage
92.29 1: 0.21
97.15 1: 0.04
86.51
0.26
65.18
0.10
97.31 +: 0.01
88.63 0.12
SOSP-1 (ours)
92.62 1: 0.14
97.79
1: 0.02
83,52
0.29 86.32
64.20
0.23
97.83
+: 0.04
87.02 0.20
SOSP-H (ours)
92.71 1: 0.19
97.81 +: 0,01
0.29
64.59 d: 0.35
97.81 4: 0.01
86.32 4: 0.29
ResNet-32*
95.30
76.8
C-OBD
91.75 0:42
97. + 0.06
93.50 1 0.37
59.52 1: 0.21
97.74 + 0.08
94.88 =: 0.08
BigenDamage
93.05
96.05
94,74
65.72
0.04
95.21
0.04
94.62
SOSP-I
92.43 1: 0.09
95.47 + 0.33
94,07 0.66
67.36
0.16
92.69 + 0.07
95.63 = 0.13
SOSP-H (ours)
92.23
0.21
DenseNet-4ip 400
94,58
74,11
Slim. by
54.21
73.19
54.21
SOSP-I (ours)
94.21 0:04
47.00 0.10
36.35 0.12
73.05 0.11
45.22 = 0,10
42.05 1.16
SOSP-H (ours)
94,23 +: 0.05
49.39 + 0.65
38.86 0.70
73.05
0.24
48.58 + 0.22
42.05
ResNet-56
ResNet-56
DenseNet-40
DenseNet-40
b)
d)
94
94
SOSP-H
SOSPA
accuracy
93
93
Y
92
92
91
91
190M
W
93
0.75
50
100
parameters (10*)
MACs (109)
# parameters (10%)
# MACs (10f)
Figure Comparison of SOSP local, i.e. layer-wise, pruning methods on Cifarl (see Suppl. F for a comparison to the CCP method). The best final test accuracy is plotted over the effective number of model parameters (a, c) and MACs (b, d). A tabular representation as well as statistics across trials shown in App. A.14 SOSP-H especially outperforms all competing layer-wise pruning methods, especially over the number of effective parameters.
3.1 COMPARISON ON MEDIUM-SIZED DATASETS
In this section, we compare the performance of our SOSP methods and benchmark them against existing pruning algorithms on various medium-sized datasets and networks. First, we compare against other recent global pruning methods, then against pruning methods that learn layer-wise pruning ratios, and lastly against local structured pruning methods, i.e. with pre-specified layer-wise pruning ratios. For all comparisons we report the achieved test accuracy, the number of parameters of the pruned network, and the MACs (often referred as FLOPs). To facilitate direct comparisons, we report test accuracies in the same way as the competing methods (e.g. best trial or average over trials), but additionally report mean and standard deviation of the test error for our models in App. A Our count of the network parameters and MACs is based the actual pruned network architecture (cf. App. D). even though our saliency measure associates with each structure only the weights into this structure (see Sec. 2)
Before comparing our SOSP methods to other recently published pruning algorithms, we perform ablation studies to motivate the of our second-order objective which takes correlations into account. First, we compare the pruning accuracy a first-order method (dropping all second-order terms in either Eq. (3) or (6) to our second-order SOSP objectives. The results (see A.T) clearly
5

---

Published as a conference paper at ICLR 2022
indicate, that second-order information improves the pruning performance. Second, we investigate whether the off-diagonal elements of the recond-order terms improve the final accuracies. We perform this comparison using a variant of SOSP-I, where the off-diagonal terms Σv Qs,s' in Eq. (4) are dropped. The results (see App. A.2) again suggest that adding these off-diagonal terms leads to consistent improvement in final accuracy. In summary, we conclude that second-order pruning objectives that consider global correlations perform best.
We now first compare our SOSP methods global pruning methods on VGG-Net, ResNet-32 and DenseNet-40, We use the same variants and implementations of these networks as used by Neural Network Slimming (NN Slimming; Liu al., 2017) as well as EigenDamage and C-OBD (Wang et 2019a), e.g. capping the layer-wise wise ratio of removed structures at 95% for VGGs to prevent layer collapse and increasing the width of ResNet-32 by factor C-OBD a structured variant of the original OBD algorithm (Hassibi et al. 1993). which neglects all cross-structure correlations that, in contrast, SOSP takes into account. The results over three trials for high pruning ratios are shown in Tab. [ and for moderate pruning ratios in App. A.3 To enable the comparison to NN Slimming an already pretrained VGG, we included the results of NN Slimming applied to a baseline network obtained without modifications to its initial training. i.e. without L1 -e-reuulaiization on the batch- normalization parameters. For moderate pruning ratios, all pruning schemes approximately retain the baseline performance for VGG-Net and ResNet-32 on Cifar10 and VGG-Net on Cifar 10 (see Tab. 4. The only exception is the accuracy for C-OBD applied to VGG-Net on C0far100, which drops by approximately 1%. For ResNet-32 on Cifar100 the accuracy after pruning approximately 1% lower than the baseline. for all pruning schemes. In the regime of larger pruning ratios of approximately 97%, SOSP and EigenDamage significantly outperform NN Slimming and C-OBD. SOSP performs on par with EigenDamage, except for ResNet-32 on Cifar C00, where SOSP outperforms EigenDamage by almost 3%. For 4en we achieve similar results compared to NN Slimming. However, note that NN Slimming depends on the above -moodiiiiation of network pretraining.
Next, we compare SOSP-H to AMC (He et al., 2018) which, instead of ranking the filters globally, learns layer-wise pruning ratios and then ranks filters within each layer. For a fair comparison, we extract their learned layer-wise pruning ratios for PlainNet-22 (He et al. 2016) and rank the filters in each layer according to their 2-norm (see also Han et al. (2015). The results in App. A.4 show that SOSP performs better than AMC when compared over parameters, the main objective of SOSP, and on par with AMC when compared over MACs, the main objective of AMC.
Lastly, we compare our SOSP methods against four recently published local, i.c. laser-wise, pruning algorithms: FPGM He al. 2019), GAL (Lin al. 2019), CCP (Peng al. 2019) (see Fig. 7 Variational Pruning [VP:|Zha et al. 2019) and HRank (Lin et al., 2020). For ResNet-56, our SOSP methods outperform all other methods across all pruning ratios (see Fig. 1h and b). For DenseNet-40, SOSP achieves better accuracies when compared over parameters (Fig. [Tp) and is on par with the best other methods over MACs (Fig. Td). The reason for this discrepancy is probably that the SOSP objective is agnostic to the number of MACs (image size) in each individual layer.
3.2 SCALABILITY AND APPLICATION TO LARGE- DATASETS
Before going to large datasets, we compare the scalability of our methods SOSP-I and SOSP-H. As the preceding section shows, both methods perform basically on par with each other in terms of accuracy. This confirms that SOSP-H is not degraded by the approximations leading to the efficient Hessian-vector product, or is helped by use of the exact Hessian. In terms of efficiency, however, SOSP-H shows clear advantages compared to SOSP-I, for which the algorithm to select the structures to be pruned scales with OS$*) (see Sec. 2.3). potentially dominating the overall runtime for large-scale networks. Measurements of the actual runtimes show that already for medium-sized networks SOSP-H more efficient than SOSP-I, see Fig. 2 and App. A.6 App.[A.6] Since SOSP-I becomes impractical for large-scale networks like other second-order methods (Molchanov et al. 2019 Wang ct al. 2019a), for the ImageNet dataset we will only evaluate SOSP-H and refer to it as SOSP.
On ImageNet, we compare our results to the literature for ResNet-18 and ResNet-50, see Tab. 2 or Suppl. Fig. 6 Because SOSP assesses the sensitivity of each structure independently of the contributed MACs, it has bias towards pruning small-scale structures. This tendency is strongest for ResNet-50, due to its x 1-convolutions. Since these 1 x 1-convolutions tend to contribute disproportionately little to the overall of MACs, devised scaled variant of SOSP, which divides

---

Published as a conference paper at ICLR 2022
Table 2: On ResNet-18/50 for ImageNet SOSP outperforms all competing methods. We compare the best final test accuracies and pruning ratios (PR) across 2 trials. A visualisation of the results can be found in App- A.7] For comparison to CCP, we also provide their alternative MAC count (for details, see App. D denotes SOSP with kernel scaling (see main text)."Gap" "Gap" indicates the percentage gap to the respective baseline model.
Runtime (min)
505P-1 S0SP
5
0
Model
Top-1% (Gup)
Parameters (PR)
MACss (PR)
Alt. MACs (PR)
1.0
1.5
2.0
ResNet-18
69.76 (0.0)
11,7M (0%)
1.82B
Width of network
SOSP (ours)
69.63 (0.13)
7.12M (39%)
1.378 (2458)
1.31B (28%)
HPGM
68.41 (1.87)
7,10M (39%)
1.06B (419%)
SOSP (ours)
68.78 (0.98)
6.42M (45%)
1,29B (29%)
1,20B (34%)
Figure 2: Runtime to calculate the pruning masks for ResNet-56 on Ci- farl0 over the width of the network for SOSP-I and SOSP-H. We vary the width of the network by increas- ing the width of each layer by a mul- tiplicative factor.
ResNet-50
76.15 (0.0)
25.5M (0%)
3,858 (0H8)
3,8 (0%)
SOSP (ours)
(-0.11)
19.9M (22%)
3.06B (21%%)
2.72B (29%)
SOSP (ours)
76.60 (-0.45)
17.9M (30%)
2.79B (28%%
2.47B (36%)
Taylor
75.48 (0.67)
17.9M (30%)
(31%)
HRank
(1.17)
16.2M (36%)
2,30B (44%)
HPGM
75.59 (0.56)
15.9M (37%))
2,368 (42%))
(ours)
75.85 (0.30)
15.4M (40%)
(27%)
1.97B (49%)
Taylor
74.50
1,2M (4418)
2.25B (37%)
HRank
71.98 (4.17)
13.8 (46%)
1,55B (62%)
CCP
75.21 (0.94)
1,778 (54%)
SOSP (ours)
75.21 (0.94)
13.0M (49%)
2.138 (45%))
1,68B (56%)
SOSP (ours)
74.39 (1.76)
11.8M (54%)
1.8 1,898 (S156)
1,388 (64%))
SOSP" (ours)
(2.77)
9.9M (615)
1,58B (59%)
1.10B (72%)
the saliency of every structure by its kernel size (e.g. 3. or 7). Compared to the vanilla SOSP, the scaled variant of SOSP is able to remove larger percentages of MACs with similar drops in accuracy (see Tab. 2. We further show results on MobileNetV2 for Imagenet in the appendix (see App. A.5)
For both networks SOSP outperforms FPGM and HRank, especially when considering the main objective of SOSP, which is reduce the number of parameters or structures. Since CCP uses different way of calculating the MACs, which leads to consistently higher pruning ratios, we added an alternative MAC count enable a fair comparison (for details, see App. D). Since HRank and FPGM do not mention their MAC counting convention, we assume they use the same convention as we do. Taking this into account, our scaled SOSP variant is able to prune more MACs than CCP, while having the same final accuracy. Further, we compare SOSP to Taylor (Molchanov et al. 2019), global pruning method that uses only the first-order terms for its saliency ranking. SOSP clearly outperforms Taylor, even though both methods have the same scaling. This is also in line with the results of our ablation study (see Sec. 3.I and esp. App. A.T. where we show that including second-order information leads to improved accuracies.
3.3 IDENTIFYING & WIDENING ARCHITECTURAL BOTTLENECKS
In the previous sections we evaluated the SOSP algorithm by removing those structures considered as least significant and then assessed the algorithm based on the performance of the pruned model. Here we instead follow an alternative path to validate the importance ranking introduced by SOSP, namely, we increase the size of these NN layers ranked most significant. The idea for this comes from a common feature of the pruning masks found by SOSP for VGG and ResNet-56 (see Suppl. Fig. (.d.....h)) and Fig. (c.d.f.)) namely that some layers are barely pruned while others pruned by more than 80%. This could indicate towards architectural bottlenecks; widening these could further improve the performance of the model. We consider layer an architectural bottleneck if it has a considerably lower pruning ratio compared to the other layers. Thus, widening these layers may improve the overall performance, and subsequent pruning could allow for even smaller models with higher accuracies compared to pruning the original model. To utilize this insight we devise a procedure that we call expand-pruning. The idea is to first calculate the pruning ratios of the trained network and then to identify architectural bottlenecks, i.e. the layers with the lowest pruning ratios. Next, we widen these specific layers by a factor of two, which has been proven to work well empirically. Finally, we randomly initialize, train, prune, and fine-tune the expanded network (for procedure, we widen every
schematic, see Fig. B.). As a naive baseline that we call the widen-prunine layer in the network with a constant factor, instead of widening specific layers; this constant factor is chosen such that the overall number of parameters matches that of the expand- prune procedure (c.g.. leading to the width multiplier 1.1 in Fig. 3).
7

---

Published as a conference paper at ICLR 2022
a) expand-pruning
b)
expand-pruning
d)
widen-pruning
width m multip ler
NN
treii
init
ResNet:55
accuracy
94
pruning ratio
0.9
expeid
prune
93
+ train pr.
expand-pr. pr.
0.3
widen.pr
92
0.0
mask
NN
0.25
0.50
0.75
25
50
9)
25
50
width mu mutippier
94.0
pruning rabio
0.9
VGG accuracy
mask
NN
93.5
NN
93.0
0.3
92.5
10
# parameters (109)
layer index
layer index
Figure 3: We remove architectural bottlenecks found by SOSP using the expand-praning scheme (a) on Cifar10. The width of blocks and layers having low pruning ratios according to the standard pruming scheme ("train- prruning in Suppl. Fig. [d and g) are expanded by a width multiplier of 2 (c. f). As a baseline, we uniformly expand all layers in the network by multiplier of 1.1 (d, g). The layer-wise pruning ratios of the enlarged network models are shown as bar plots in (c. d, f. g). The average test accuracy and standard deviation are shown over the number of model parameters (b, e).
We evaluate the sxpand-pruning procedure for ResNet-56 and VGG on Cifar10, for which we expand the least pruned of the three main building blocks and the five least pruned layers, respectively (cf. red width multipliers in Fig. f..f) selected on the basis of the pruning masks shown Suppl. Fig. Bjd.g)). Note that more fine-gratd ene-grained widening of bottlenecks in ResNet-56, e.g. on layer level, is not possible without changing the overall ResNet architecture. In summary, a selective widening of bottlenecks results in smaller network models overall with higher accuracy than pruning the vanilla network or unselectively increasing the network size (compare expand-pruning and widen-pruning in Fig. (be)). While in principle any global pruning method could be used for the expand -rrunig procedure, SOSP is especially suited since it does not require to modify the network architecture like EigenDamaae. Further, SOSP can be applied directly at initialization (see App. A. unlike e.g. NN Slimming, allowing for a similar expand scheme directly at initialization (see App. A.11..
4 DISCUSSION
In this work we have demonstrated the effectiveness and scalability of our second-order structured pruning algorithms (SOSP). While both algorithms perform similarly well, SOSP-H is more easily scalable to large-scale networks and datasets. Therefore, we generally recommend to use SOSP-H over SOSP-I, especially for large-scale datasets and networks. The only regime where SOSP-I becomes a valuable alternative is for small pruning ratios and small- to medium- Further, we showed that the pruning masks found by SOSP be used to systematically detect and widen architectural bottlenecks, further improving the performance of pruned networks.
networks.
Compared other global pruning methods, SOSP captures correlations between structures by simple, effective and scalable algorithm that requires to modify neither the training nor the architecture of the network model be pruned. SOSP achieves comparable or better accuracies benchmark datasets, while having the same low complexity as first-order methods. The C-OBD algorithm (Wang al. 2019a) is structured generalization of the original unstructured OBD algorithm (LeCun et 1990). In contrast to OBD, C-OBD accounts for correlations within each structure. but does not capture correlations between different structures within and across layers. We show that considering these global correlations consistently improves the performance, especially for large pruning ratios (Tab. [ This is in line with the results of our ablation study in App. A.2 (see also Sec. Sec.3.1] The objective of EigenDamage (Wang et al.) (019a) to include second-order correlations is similar to ours, but the approaches are sigmificantly different: EigenDamage uses the Fisher- approximation, which is similar to SOSP-I's Newton approximation and exhibits similar scaling behaviour, and then, in addition to further approximations, applies low-rank approximations that require the substitution of each layer by sutteneck--lock structure. Our SOSP method is simpler, easier to
8

---

Published as a conference paper at ICLR 2022
implement and does not require to modify the network architecture, but nevertheless performs on par with EigenDamage. The approach of NN Slimming (Liu et al,, (017)) is more heuristic than SOSP and is easy to implement. However, networks need to be pretrained with -rreulllarzztionn on the hatch-normalization parameters, otherwise the performance is severely harmed (Tab. [ and Supp. Tab. D.. SOSP on the other hand does not require any modifications to the network training and thus can be applied to any network. A recent variant of NN Slimming was developed by ZZhangg ct al. (2020) who optimize their hyperparameters to reduce the number of MACs. Using the number MACs as an objective for SOSP is left for future studies. Most other existing global
structured pruning methods either approximate the Hessian as a diagonal matrix (Theis al. 2018]] Liu et al. 2021) or use an approximation similar to Newtsn which we used for SOSP-1 (e.g., the Fisher information matrix in Molchanov et al. 2019). These approaches based on the Gauss-Newton approximation or its variants usually share the same disadvantageous scaling as that encountered by SOSP-I, and thus cannot scale to ImageNet as SOSP-H can.
In addition to the above comparison to other global pruning methods, we also compared our methods to simpler local pruning methods that keep the pruning ratios constant for each layer and, consequently, scale well to large-scale datasets. The pruning method closest to SOSP-I method is the one by Peng et al. (2019). While both works consider second -odder correlations between structures, theirs is based on ranking scheme different from our absolute sensitivities in X/ and considers only intra-layer correlations. Furthermore, they employ an auxiliary classifier with a hyperparameter, yielding accuracy improvements that are difficult to disentangle from the effect of second-order pruning, Going beyond a constant pruning ratio for each layer, (Su et al.] (2020) discovered, for ResNets, that pruning initialization seems to preferentially prune initial layers and thus proposed pruning scheme based on a "keep-ratio per layer which increases with the depth of the network. Our experiments confirm some of the findings of (f et al. (2020). but we also show that the specific network architectures found by pruning can drastically vary between different networks and especially between initialization and after training (histograms in Suppl. Fig. B}. While all local pruning methods specify pruning ratios for each layer, our method performs automatic selection across layers. Further, SOSP performs on par or better than AMC (He et al. 2018) which learns these layer-wist pruning ratios as a first step. instead of specifying them in advance like the above local methods. This is surprising since AMC uses many iterations to learn the layer-wise pruning ratios, while SOSP uses only a single step. Further, there exist even more elaborate schemes to find these subnetworks, in the spirit of AMC, such as Autocompress (Liu et al. 2020), EagleBye (Li et al. 2020), DMCP (Guo) al. 2020p and CafeNet (Su al., 2021 It difficult to enable fair quantitative comparison between these iterative methods and our single-shot method SOSP.
SOSP's automatic selection of important structures allows us to identify and widen architectural bottlenecks. However, as the size of structures is usually identical within layers, our global pruning method has a bias towards pruning small structures, absent from local pruning methods. We proposed simple solution to remove some of this bias by scaling each structure by the inverse of the kernel size. Alternatively, to better reflect the computational costs in real-world applications, each structure could also be normalized by the number of its required MACs or memory (van Amersfoort et al.) 2020 Liu cet al. 202T). Further, introducing additional hyperparameters for each layer optimized to reduce the number of MACs done by Chin et al. (2200) could potentially lead to further improvements, but would also significantly increase the complexity due to the need of hyperparameter optimization. Liu et al. (202)) form groups of network structures that depend on each other, and compute the saliency for each group collectively, to better estimate the importance. While this proved to be beneficial, it is orthogonal the investigation of finding good second-order approximations.
Recently, unstructured (Lee et al. 2018 Wang et al. 2019b] Tanaka et al. 2020) and structured (van Amersfoort al., 2020 Hayou al. 2021 pruning schemes were proposed that are applicable to networks at initialization, While these methods fail to achieve similar accuracies compared to pruning after training, we show in a small ablation study (see App. App.[.99) A.9) that our SOSP method at initialization can, after comparable training time, achieve accuracies similar to pruning after training.
In accordance with Elsken et al. (001). our results suggest that pruning can be used optimize the architectural hyperparameters of established networks (Liu et al. 2018) or super-graph (Noy et al.) 2020); see also App. A.12 We envision our second-orden sensitivity analysis to be a valuable tool to identify and widen bottlenecks. For example, whenever a building block of the neural network cannot be compressed, this building block may be considered a bottleneck of the architecture and could be inflated to improve the overall trade-off between accuracy and computational cost.

---

Published as a conference paper at ICLR 2022
REFERENCES
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? arXiv preprint arXiv:2003.03033, 2020.
Ting- Wu Chin, Ruizhou Ding, Cha Zhang, and Diana Marculescu. Towards efficient model compres- sion via learned global ranking. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1518-1528 2020.
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 pattern recognition, pp. 248-255, Icee, 2009.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. Journal of Machine Learning Research, 20(55)11211, 2019. hww.httpp./mmmlr.ogg/ppeeeee
18 598 h
Roger Fletcher. Practical methods of optimization. John Wiley & Sons, 2013.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference Learning Representations, 2018.
Shaopeng Guo, Yujie Wang, Quanquan Li, and Junjie Yan. Dmep: Differentiable markov channel pruning for neural networks. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 1539-1547, 2020.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network, Advances neural information processing systems, 28:1 135-1143, 2015.
Babak Hassibi, David G Stork, and Gregory J Wolff. Optimal brain surgeon and general network pruning. In JEEE international conference on neural networks, pp. 293-299. IEEE, 1993.
Soufiane Hayou, Jean-Francois Ton, Arnaud Doucet, and Yee Whye Teh. Robust pruning at ini- tialization. In International Conference Learning Representations, 2021. URL https //openrevi ew net. fort:/oooommmddxx]__cee
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Yang He, Ping Liu, Ziwei Wang. Zhilan Hu, and Yi Yang. Filter pruning via geometric median for deep convolutional neural networks acceleration. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 4349, 2019.
Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural networks. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1199,197, 2017.
Yihui He, Ji Lin, Zhijian Liu, Hanrui Wang, Li-Jia Li, and Song Han. Ame: Automl for model compression and acceleration on mobile devices. Proceedings of the European conference on computer vision (ECCV), pp. 784-800, 2018
Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708. 2017.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kerne:: convergence and generalization neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp.
2018.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, John S Denker, and Sara Solla. Optimal brain damage. In Advances neural information processing systems, pp. 598-605, 1990.
10

---

Published as a conference paper at ICLR 2022
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. Snip: Single-shot network pruning based on connection sensitivity. In International Conference on Learning Representations, 2018.
Bailin Li, Bowen Wu, Jiang Su, and Guangrun Wang. Eagleeye: Fast sub-net evaluation for efficient Springer,
neural network pruning. In European Conference on Computer Vision, pp. 2020.
Mingbao Lin, Rongrong Ji, Yan Wang, Yichen Zhang, Baochang Zhang, Yonghong Tian, and Ling Shao. Hrank: Filter pruning using high-rank feature map. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1529-1538, 2020.
Shaohui Lin, Rongrong Ji, Chenqian Yan, Baochang Zhang. Liujuan Cao, Qixiang Ye, Feiyue Huang. and David Doermann. Towards optimal structured enn pruning via generative adversarial learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.
2790-2799) 2019.
Liyang Liu, Shilong Zhang, Zhanghui Kuang, Aojun Zhou, Jing-Hao Xue, Xinjiang Wang, Yimin Chen, Wenming Yang, Qingmin Liao, and Wayne Zhang. Group fisher pruning for practical network compression. In International Conference on Machine Learning, pp. 7021-7032. PMLR, 2021.
Ning Liu, Xiaolong Ma, Zhiyuan Xu, Yanzhi Wang, Jian Tang, and Jieping Ye. Autocompress: An automatic dnn structured pruning framework for ultra-high compression rates. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 4876 4883, 2020.
Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang, Shoumeng Yan, and Changshui Zhang. Learn- ing efficient convolutional networks through network slimming. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), Oct 2017.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell, Rethinking the value of network pruning. In International Conference on Learning Representations, 2018.
Sun Mingjie and Liu Zhuang. Network slimming. network-s 1 i imming 2018.
https:///gituuu..com/eee
Pavlo Molchanov, Arun Mallya, Stephen Tyree, Turi Frosio, and Jan Kautz. Importance estimation for neural network pruning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11264-11272, 2019.
Asaf Noy, Niv Nayman, Tal Ridnik, Nadav Zamir, Sivan Doveh, Itamar Friedman, Raja Giryes, and Lihi Zelnik. ASAP: Architecture search, anneal and prune. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings ggg of the Twenty Third International Conference on Artificial Intelligecce and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 493-503 PMLR, 26-28 Aug 2020. URL http::tp:// StRpattt//////ceeiinne wal.gg.ssm.......... www.s.pres///e wwwpesssvl0////
Hanyu Peng, Jiaxiang Wu, Shifeng Chen, and Junzhou Huang. deep networks. In International Conference on Machine Learning, pp. 5113-5122. PMLR, 2019.
Collaborative channel pruning for
Russell Reed. Pruning algorithms-a survey. IEEE transactions on Neural Networks, 4(5):740-747, 1993.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint veXiv:1409.15:: 2014.
Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao, Liwei Wang, and Jason Lee. Sanity-checking pruning methods: Random tickets can win the jackpot. In Advances in Neural Information Processing Systems, 2020.
Xiu Su, Shan You, Tao Huang, Fei Wang. Chen Qian, Changshui Zhang, and Chang Xu. Locally free weight sharing for network width search. arXiv preprint 210i::2002.02588 2021.
Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli. Pruning neural networks with- out any data by iteratively conserving synaptic flow. Advances in Neural Information Processing Systems, 33, 2020.
11

---

Published as a conference paper at ICLR 2022
Yehui Tang, Yunhe Wang. Yixing Xu, Dacheng Tao. Chunjing Xu, Chao Xu, and Chang Xu. Scop: Scientific control for reliable neural network pruning, Advances in Neural Information Processing Systems, 2020.
Lucas Theis, Iryna Korshunova, Alykhan Tejani, and Ferene Huszár. Faster gaze prediction with dense networks and fisher pruning. arXiv preprint arXiv:1801.05787, 2018.
Joost van Amersfoort, Milad Alizadeh, Sebastian Farquhar, Nicholas Lane, and Yarin Gal. Single shot structured pruning before training. arXiv preprint arXiv:2007.00388) 2020.
Chaoqi Wang, Roger Grosse, Sanja Fidler, and Guodong Zhang. Eigendamage: Structured pruning in the kronecker-factored eigenbasis. In International Conference Machine Learning, pp- 6566-6575, 2019a.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2019b.
Chenglong Zhao, Bingbing Ni, Jian Zhang, Qiwei Zhao, Wenjun Zhang, and Qi Tian. Variational convolutional neural network pruning. In Proceedings of the IEEF/CVF Conference on Computer Vision and Puttern Recognition, pp. 2780-2789, 2019.
Tao Zhuang, Zhixuan Zhang. Yuheng Huang, Xiaoyi Zeng, Kai Shuang, and Xiang Li. Neuron-level structured pruning using polarization regularizer. Advances in Neural Information Processing Systems, 33, 2020.
12

---

Published as a conference paper at ICLR 2022
Supplementary Material for
SOSP: Efficiently Capturing Global Correlations by Second-Order Structured Pruning
A ADDITIONAL DATA AND EXPERIMENTS
A.I COMPARISON OF FIRST-ORDER STRUCTURED PRUNING WITH SOSP
See Figure 4 and Table 3 and their captions (cf. also Sec. 3.1 for further descriptions). The experiments
are in line with our comparison to Taylor (Molchanov al. 2019) on ImageNet, which is basically first-order method (see Sec. 3.2
Pruning after (Cifar10)
Pruning before FT (Cifar10)
Pruning after (Cifar100)
Pruning before (Cifar100)
b
c)
d)
94
90
72
60
accuracy
93
40
92
SOSP
66
250
500
750
250
500
750
250
500
750
250 parameters (10*)
500
750
parameters (10*)
parameters (10')
# parameters (10*)
Comparison of the accuracies achieved by SOSP and first-order method, where all second-order terms are set to zero (see end of Sec. 2.2). for ResNet-56 before and after the fine-tuning step on Cifarl0 and 100. All shown experiments prune full ResNet-56 model with 855 x 10 parameters; the parameter count of the pruned network is shown on the horizontal axis. The results clearly show that adding second-order information increases the performance, before well after fine-tuning (FT). The advantage of using second-order information increases as the size of the pruned network decreases.
Figure 4:
Table 3: Comparison of SOSP to first-order global pruning for ResNet-56 on Cifar and 10f
Darneet
Cifart0
Olhar
Methed (Prsiing Ratio)
Test sant
1%
Tce scv. before F7
Nambh of Param.
(1D")
Nunb of MACC (1I7)
Taxt Janc (%)
Tesl sav:
(%)
beforn PT
Narbh Paratt:
(10")
Numb MACA
(167)(%)
Hns-Onder (0.))
03.00 U.1.1.
35.00 0,00
730
10
71.15 211.1
52.22 0,40
750
(1:05
1(N)
Order (0.3)
(0.5)
0.09
356
SOSP (0.5)
93.15 0.15
14.28 0.6
335
55
09.52 44005
51.32
358
Fia--Onke-003 (0.7)
01.55 0.20
12.02 3.5
195
65.51 10.18
22.96 6.15
291
SOSP (0.7)
91.90:200.13
79.35 0.28
133
31
06.07 30.28
40.7 =: 0.91
200
A.2 COMPARISON OF ACCURACIES ACHIEVED BY SOSP-I WITH AND WITHOUT CORRELATIONS
See Figure 5 and its caption (cf. also Sec. 3.J for further descriptions).
A.3 RESULTS FOR MEDIUM PRUNING RATES FOR COMPARING GLOBAL PRUNING METHODS
See Table and its caption. (For high pruning rates, see Table in Sec. 3.1
A.4 COMPARISON TO PRUNING-METHODS THAT FIND LAYER- WISE PRUNING RATES
See Table and its caption (cf. also Sec. 3.1 for further descriptions).
13

---

Published as a conference paper at ICLR 2022
ResNet-32
ResNet-32
VGG-Net
VGG-Net
a)
b)
c)
d)
95
94
94
accuracy
94
94
93
93
92
92
92
92
SOSP without correlations
90
90
0.6
0.8
Pruned Structures (in parameters (109)
Pruned Structures %)
parameters (10%)
Comparison of the accuracies achieved by vanilla SOSP-I and variation of SOSP-I, where all ofi-oiiaon terms of the Hessian are set to zero, for ResNet-56 and VGG on Cifar10. The results both networks suggest that cross-structure correlations can significantly improve pruning performance. The gap in performance is even larger before the fine-tuning step (not shown).
Figure 5:
Table Comparison of SOSP to other global pruning methods for moderate pruning rates. The setting is exactly the same in Tab. 1 For final accuracies after fine-tuning see App. A.13 denotes the baseline model.
Dataset
Cifar10
Cifar 100
Test acc.
Reduct, in weights (%)
Reduct. in MAC's (%)
Test acc. (%)
Reduct. in weights (%)
Reduct. in MAC's (%)
Method
(%)
VGG-Net
94.18
73.45
NN Slimming
92.84
80.07
42.65
71.89
74.60
38.33
NN Slim. +11
93.79
83.45
49.23
72.78
76.53
39.92
C-OBD
94.04 +: 0.12
82.01
0.44
38.18
+ 0.45
72.23
+ 0.15
77.03 +: 0.05
33.70
0.04
EamanDamage
93.98
0.06
78.18 = 0.12
37.13
- 0.41
72.90
0.06
76.64
0.12
37.40
SOSP-I (ours)
93.99 0.17
0.17
85.75 0.74
45.96 = 4.29
73.17
0.11
82.68
0.04
SOSP-H (ours)
0.16
87.29
57.74
73.11 0.19
79.20 0
51.61
ResNet-32
95.30
76.8
C-OBD
9..11
70.36
0.39
66.18
0.46
75.70
+.33
66.68
0.25
67.53
0.25
EigenDamage
95.17 -17:::0.11
71.99
0.13
70.25
+ 0.24
75.51
0.11
69.80
0.11
71.62
0.21
SOSP-1 (ours)
95.06 + 0.07
0.50
67.36 0.80
75.33
2 0.11
63,83 = 0.17
74.28 0.08
SOSP-H (ours)
95.22 0.12
72.85 = 0.40
0.37 67.85
75.52 - 0.20
69.31 0.36
71.60
0.38
DenseNet-40*
94.58
74.11
NN Slim. L
94.32
35.52
73.76
35.45
SOSP-I (ours)
94.42 4: 0.03
32.21 = 0.16
22.03 4 0.13
73.46 +: 0.05
31.38 4: 0.09
29.98 0.55
SOSP-H (ours)
94.41 0.12
0.67
26.14 - 0.13
73.60
0.17
34.15 0.13
28.23 =
A.5 COMPARISON OF SOSP ON MORILENETV2 FOR IMAGENET
See Table for comparison of SOSP for MobileNetV2 for Imagenet.
A.6 RUNTIME COMPARISONS OF SOSP-H AND SOSP-I
The results of Table 7 complement the results of Fig. 2 and show that while SOSP-I still practical for small-scale networks and datasets for large scale networks and datasets it becomes impractical. SOSP-H on the other side says practical across all network dataset sizes.
A.7 PLOTS FOR COMPARISON OF SOSP ON RESNET-18/SO FOR LARGE-SCALE DATASETS
See Figure and its caption (cf. also Sec. 3.2 for further descriptions).
14

---

Published as a conference paper at ICLR 2022
Table 5: We compare the results of SOSP and AMC for PlainNet-20 Cifar10. We show the mean and standard deviation of the accuracy over three independent runs.
Method
Acc.
Params (10")
MACS (10%)
AMC
90.23:::.100 10
132
20.9
SOSP (0.3)
90.93=20.17
124
26.7
(0.4)
90.14=:0.15
22.7
Table We compare the results SOSP with other state-of-the-art methods on MobileNetV2 for ImageNet. "Gap" indicates the percentage gap the respective baseline model and PR stands for pruning ratio.
Method
Top-1 1% (Ciup)
Parameters (PR)
MAC's (PR)
MobilsNetV2
71 88(8.000)
3 3.5M(0%)
0.30B(0%)
AMC
70.80(1.08)
0.21B(30%)
SOSP (0.2)
71.04(0.84)
2.5M(28%)
0.21B(29%)
A.8 COMPARISON OF SOSP ON RESNET-56 AGAINST CCP
See Figure 7 and its caption (cf. also Sec. for further comparisons on ResNet-56).
A.9 PRUNING AT INITIALIZATION
Traditionally, pruning methods applied to pretrained networks, as also done in the main part of our work, but recently there has been growing attention on pruning at initialization following the works Lee et al. (2018) and Frankle & Carbin (2018). Since SOSP employs the absolute value of the sensitivities. it can also be applied to randomly initialized network without any modifications. Thus, SOSP can also be seen as an efficient second-order generalization SNIP (Lee al. (0188)
van Amersfoort et al., 2020). While EigenDamage can in principle be modified and applied to randomly initialized network as well, NN Slimming can be applied initialization.
Usually pruning at initialization leads to worse accuracies than pruning after training (Liu et al. 2018). However, pruning an already trained network is often followed by fine-tuning, effectively training the network twice (Fig. (8)). For comparability with pruning at initialization, we unify the overall training schedule between these two settings and consequently apply two training cycles after pruning the randomly initialized network (Fig. Sb; for further discussion, see App. A.
We observe that applying SOSP at initialization performs almost equally well than applying SOSP after training (see ResNet-56 and VGG in Fig. S and f, respectively). In conclusion, applying SOSP at initialization can significantly reduce the time and resources required for network training with no or only minor degradation in accuracy.
A. PRUNING AT INITIALIZATION VS PRUNING A PRETRAINED NEURAL NETWORK
In this section we investigate further why pruning a randomly initialized network tends to achieve lower accuracies compared to pruning pretrained network (Lee et al. 2018 van Amersfoort et al. 2020). We compare the final accuracies pretrained network (see Fig. D.. While pruning a pretrained network leads to considerably higher accuracies compared to pruning a randomly initialized network, the random baseline curves show the same difference. Thus, to be able to compare pruning before and after training needs to device settings that enable a fair comparison, ensuring similar accuracies for random pruning accross both settings.
pruning and fine-tuning a randomly initialized and
15

---

Published as a conference paper at ICLR 2022
Table 7: Comparison of time needed to calculate the importance vector for SOSP-1 1 and SOSP-H for several networks on Cifar 10 and ImageNet.
Time noeded for pruning step (without training)
ResNet-56
ResNet-32
DenseNet-40
VGG
ResNet50 (Imageact)
SOSP-H H SOSP-1
50 + 2
123:-4s 1355#388s
67::2s 635+118
110:33 1647444s
40:2 min
926#226
ResNet-50
ResNet-50
ResNet-18
b)
SOSP
FPGM
SOSP
SOSP*
HRlank
FPCM
76
Taylor
accuracy
accuracy
Y
12
10.0
17.5
20.0
1.5
7.05 # parameters (10%)
parameters (10*)
# MACs (10*)
Figure 6: Comparison of the accuracies achieved by SOSP and its competing methods on ResNet- 18/50 on ImageNet. The plots visualize the data of Tab.
94
94
ResNet- accuracy
92
SOSP-1
92
SOSP-H
91
0.2
0.4
0.6
0.2
0.4
0.6
pruned structures (%)
pruned structures (%)
Figure 9: Comparison of pruning and fine-tuning a randomly initialized (left) and pretrained (right) network for ResNet-56 on Cifarl0. Random pruning is baseline which selects uniformly at random structures and adds them to the mask M until the predefined pruning ratio is reached.
A.11 EXPAND-INIT DATA
This section provides the experimental results of the corresponding graand-rrocedure initialization (see Sec. 3.3 The results of Fig. indicate that architectural bottlenecks exist not only for pretrained networks but also for randomly initialized networks. Therefore, we device also an expand scheme before training. In this scheme the mask for the expand- procedure is not calculated for pretrained network but for a randomly initialized network. Following the expand scheme the network pruned and then only fine-tuned once. The results displayed in Fig. TO
16

---

Published as a conference paper at ICLR 2022
S0SPI
94.0
S05P4
935
accuracy
93.0
92.5
20
40
Figure 7: Comparison of the accuracies for Cifar achieved by SOSP-H and SOSP-I vs. CCP (Peng
al. 2019 over the alternative MAC-count used by (Peng al. 2019) (see also App. D
train-pruning
Init train prune
pruning ratio
0.9
ResNe: accuracy
0.6
NN
mask
trainpruning
0.3
inttppining
0.0
b) init- pruning
f)
0.2
0.4
0.6
20
40
h)
20
40
pruning ratio
0.9
mask
VGG accuracy
0.6
92
0.3
0.0
15
parameters (10*)
layer index
layer index
Figure 8: Comparison between pruning after training and at initialization on Cifar10. Both pruning schemes, train-pruning (a) and init-pruning (b), train the network for the epochs, but generate and apply the pruning masks at different point in times. The average and standard deviation of the test accuracy across trials plotted against the number of model parameters for ResNet-56 (top row; c) and VGG (bottom row; f). For a single trial, in which overall 50% of the structures are pruned, we visualize the pruning masks of train- main--runing and init-pruning by showing the layer-wise pruning ratios in (d, g) and (e, h), respectively.
overall number of
a)
b)
2.0
92
0.8
ResNet-56 accuracy caac
1.5
width multiple
0.6
90
pruning
1.0
0.4
88
init:rr expand-init-pr.
0.2
0.5
0.0
0.0
0.1
0.2
0.3
25
50
d)
2.0
ratio
VGG19
accuracy
93
1.5
92
0.4
width
91
0.2
0.5
90
0.0
0.0
10
10
# parameters (10F)
layer index
layer index
Figure 10: We widen architectural bottlenecks found by SOSP starting with randomly initalized network. The width of blocks and layers with low Pruning ratios in the train-pruminn scheme (Fig, [ and h) expanded by width multiplier of 2 (b. e). As baseline, we again uniformly expand all layers in the network by a factor 1.1 (c, f). The layer-wise pruning ratios of the enlarged network models shown bar plots in (b. f). The average and standard deviation of the test accuracy

---

Published as a conference paper at ICLR 2022
A.12 SHUFFLE EXPERIMENTS
See Table 8 and its caption.
Table 8: We compare the results of SOSP with Shuffle SOSP, where the pruning masks of the structures within each layer, and therefore also the weights, are shuffled before the fine-tuning step. Therefore, Shuffle SOSP retains the same architecture (the same number of structures are pruned per layer) as SOSP, but prunes different structures within each layer. The results indicate that the dominant factor is the architecture and not he specific values of the weights.
Structured Pruning Ratio
SOSP
Acc.OOSP-Shuffl
0.3
+
92.59:10.12 92,94 0.09
0.5
93.15=+0.15
A.13 MEAN AND STANDARD DEVIATION OF FINAL ACCURACIES FOR THE GLOBAL PRUNING COMPARISON
See Table and its caption.
Table 9: Mean and standard deviation of the final accuracies after the full fine-tuning step of both SOSP methods on Cifarl0 and Ci for VGG-Net, ResNet-32 and DenseNet-40.
Tiener
EIFARI6
CIFARI06
Mirhed
Rakelan
kingls
MMN
MAC 191
8x (4g
Toi
Relacted
MMD'
KD (90
Rekeien MMC
00.80 6021
8575 0M
05.95 4:4
02:33 8.13
05.79 D00
13.53 1.0
72.9 8:38
82.68 006
4487 [M1
45/77 0.0
07.83 0:34
87.82 3:33
9:38
96.9 208
26 300
00.8 000
95.1
15 12
03:9 8.11
14.3 108
6590 0.30
92.99 1-1
55.33 9:13
2:9.1
116
14.8
3221 2-33
2.3
36.3
3247
3128
2008
22.00:0000
45.22 45.22:00..00
42.55 2.8
9-93
3111
0415
011
16 009
75:9 0--6
A.14 14 TABULAR DATA AND MEAN AND STANDARD DEVIATION FOR LAYER- WISE PRUNING COMPARISON
This section provides additional data complementing the results of Fig. [ The numerical data of Fig. is shown in Tab. 10 and the mean and standard deviation of the final accuracies for both SOSP algorithms is shown in Tab. and Fig. 11
ResNet-56
ResNet-56
DenseNet-40
DenseNet-40
a)
c)
d)
accuracy
94
94
94.5
94.5
94.0
94.0
S05P-1
93.5
505P1
93.5
S05P-H
50SP-H
0.75
50
300
0.50
0.75
200
# parameters (10%)
MACs (10%)
parameters (105)
MACs (10%)
Figure 11: Mean and standard deviation plots of the accuracies after fine-tuning of SOSP for ResNet-56 and DenseNet-40 on C0far10.
18

---

Published as a conference paper at ICLR 2022
Table 10: Pruning results of ResNet-56 and DenseNet-40 Cifar 10. Gap denotes the difference between the accuracy the pruned model and the baseline accuracy. PR denotes the pruning ratio, Le. the percentage drop in MACs parameters.
Model
Top-1
Parameters(PR)
MACs(PR)
ResNet-S6
93.38/0.0)
0.85M(05))
125M(05)
GAL (201
92.98(0.28)
0.75M(12%))
78M(389)
SOSP:T
94.22(-0.44)
0.74M (13%)
110M (13%)
SOSP-H (ours)
94.25(-0.47)
0.73M (15%)
109M (14%)
HRank Lin et
2020
93.52(-0.26)
0.71M(1755)
89M(29%)
93.85(0.03)
(33%)
SOSP MI (ours)
93.71(0.17))
0.52M (40%)
79M (37%)
FPGM 2019
93.01(0.58)
0.49M(42%)
81M(368)
[RRmkk
2040
93.17(0.09)
0.49M(4236)
(3M(5
SOSP-I (ours))
93.25(0.53)
0.36M (58%)
60M (53%)
SOSP-H (ours)
93,27(0.51)
0.33M
54M (57%))
Gil al. 2019)
90,36(2.10) 10)
0.29M(6619)
(0M(609))
I[Rank Lin
90.72(2.54)
32M(749)
SOSP-T (ain))
92.35(1.53)
1. (78%)
16M (6)
SOSP-11 (ours)
91.97(1911)
(.18)(799))
MIE (75%)
(ours]
90.80(3.08
I.I (87%)
I2M (825)
SOSP-H (ours)
90,78(3.00)
0.(7M)))%)
2IM (835)
NenseNett440
94.58(0.0)
L.4M(006)
(09)
SOSP-1 (ours)
94.46(0.12)
0.88M(1%%)
2555(10%)
SOSP MSSP-H (ours)
94.63 (.00))
0.86M(199)
245 (4%)
GAL Lin 2019
94.29(0.52)
0.67M(36%)
(83M(35%)
HRank
94.24(0.57)
0.66M(37%)
(67M(41%)
SOSP-I
(4.35(0.22)
0.72M(32186
22 (2
SOSP-11 (ours)
0.69M(35%)
M09
SOSP-T (ours)
94.14(0.44)
0.56M(475%
(80M(369)
SOSP-11 (ours)
94.27(0.31)
0.54M(49%)
172M(39%)
HRank
2020
93.68(1.13)
0.48M(5436)
1DM %:
GAL Lin et 2019
23.53(1.22 (28)
0.45M(57%)
128M(55%)
Zhao 2019)
93.16(0.95)
0.42M(60%%
156M(45%)
SUSP- (ours)
93,70(0.88)
0.42M(60%)
141M(500%)
(ours)
94.74(0.84)
0.40M(625%)
138M(515)
Table Mean and standard deviations of the accuracies after fine-tuning of SOSP for ResNet-56 and DenseNet-40.
Model
Top-1%
Pruned Paramoters (in %)
Pruned MACs (in %
ResNet-56
93.39
0
SOSP-I
94.22
0.10
12.95 0.15
12.78
0.09
SOSP.H
94.25 0.14
14.90 + 0.12
13.11
+ 0.36
SOSP-I
0.09
36.36 + 0.11
0.12
SOSP-H
93.71 0.11
39,70 + 0.39
36,86 :: 0.70
SOSP41
93.25 0.16
58.19 1: 0.28
52.53 0.21
SOSP.H
93.27 0.06
60.95 0.29
0.334
SOSP-1
92.35 0.25
77.98 + 0.46
0.21
SOSP-H
79.29
0.62
SOSP-I
90.8 + 0.18
86.68 0.14
81.79 0.23
SOSP-H
90.78 0.14
87.31 0.29
83.42 0.15
DenseNet-40
94.16
0
0 10:00 1:00::00
SOSP-I
0.11
16.59 +
SOSP.H
94.63 = 0.15
18.57 0.63
13.52 4: 2.13
SOSP-1
94,35+ 0.04
32.21 0.16
22.03
SOSP-H
94.43 0.11
34.78 + 0.67
26.14 1:14+:10 1.16
SOSP-1
94.14 1007
47.00 1: 0.10
36.35 10.12
SOSP.H
94.27 0.08
49.39 1 0.65
38.86 0.70
SOSP-1
94,70 20.08
60.32 0.31
50.244 0.80
SOSP-H
62.24
1.07
B APPROXIMATIVE SECOND-ORDER DERIVATIVES
In order to approximate the Hessian terms 0_' o.) in the matrix Q efficiently (see Eq. and ( omit from H(0) N Σn VZL(fo(In)) those terms that involve the expensive second-order derivatives (z,) of the NN outputs, while including second-order couplings due &. This equivalent approximating (0)) H( N Σ.. V3e(s (#a), yn) for the linearized
19

---

Published as a conference paper at ICLR 2022
for (a)) (2) motivated by the NTK limit (Jacot et al. 2018) for large NNs at both initialization and after training. The terms in the sum become then
f0 (z) == fo(x) + 6(z)
(8' - 0) with d(x) Vafo(z) E RPxP, which is well
Vile (Jo" (In), Un)
where R, E IR DxD is diagonal for squared loss, and has an additional rank-1 contribution for
cross-entropy (see App. [. and App. B.2 respectively). Similar Hessian approximations were
employed before in NNs (Hassibi et al. 1993 Wang et 20T9a: Peng al. [001 [iu et al. 202T
Theis et al. 2018) and also in the Newus- optimization method (Fletcher 2013).
Below we derive our approximation of the second-order loss derivatives Eq. ( that lead to the
desired Eq. (5). and especially the particular matrix structures of R., in these expressions (diagonal plus rank- 1), which allow for a more efficient matrix multiplication (App. B.4).
Our approximation is based on omitting from the exact loss derivative those terms that involve the (expensive) second-order derivatives V (rx) of the NN outputs fo fz E RP. We however still
include second-order couplings due to the loss function l. Our approximation is thus approximate the NN output
for (x) = f/im (x) fo(x) 6(x) (6'
(10)
to first order, where ((x) == Vofo(z) DDx is the first-order derivative of the NN output, and then to approximate the second-order derivatives of the NN loss as follows:
Vig (fa(In)) Mn) R Vig (5 (2.): Vo)
(11)
We now compute this approximation Vie (5% (In); Un) for both the squared loss {(f.y) = || y as well as for the cross-entropy loss L(J v) log (J) where TR + RD
denotes the softmax function. In this computation we use the following facts:
flin (In) fo(#)),
(12)
Volo din (#n) = Vor (iiii((sn (5x) (sn)) d(Fa) = Vola(an);
(13)
VoS pin (In) = V2rSbin pln (x ( O.
(14)
which follow directly from 10
B.1 SECOND-ORDER APPROXIMATION FOR SQUARED Loss
For the squared loss, we obtain:
vi 1 118m (( vn)) ((f (zn) ynn)
Vzl (f6""(zn)))))))))))(()(()))))( (In).
(15)
(fbi (æn) vn) (VV.. (f + (Vof6"(zz)) (Vooo
(16)
=(xx)² T (((z))
(17)
M(N,)" (T ((Ø()))
(18)
where Rú == LDDD is here the D D-identity matrix. This is Eq. (9) for the squared loss.
Due to this diagonal form of Rg the matrix multiplication (ø(a, )0.) y R., (0(2,))) )0x) in Eq. 5 has, for each pair s'),,, computational complexity linear in the dimension D (which the number of NN outputs), rather than quadratic:
= (0(x,) (
(19)
D -
(20)
where (d(I,)0,); R denotes the j-th component of the vector ( )0, E D.
is for this reason that the overall computational complexity of SOSP-I is linear D (see Sect.
2.1
rather than of order O
20

---

Published as a conference paper at ICLR 2022
B.2 SECOND-ORDER APPROXIMATION FOR CROSS-ENTROPY LOSS
Note that the first derivatives of the softmax-function RD RD, defined by of)); ==
e / efa are:
0 0f, of); - -di))-
(21)
We can thus compute for the cross-entropy loss, where by. E RR. denotes the vector with entry 1 in component and entries everywhere else:
Vil (I vn)
V (fo
(22)
Vo I(Volo" hi (x=)))(( (za)) ( -g.
(23)
(Vosl" (In)) " (Voo (f + (Vist plin (En)) (o( 8y
(24)
= (Volo"((nn) (Veo (Ix))
(25)
To compute Veo (xn) in 25 we consider its i-th component:
do(s);
V Vno (fo (In)); =
Vo(tbin(nn))
(26)
0f, s=))
= Σ
(fbi"(In)) (6is - ((8))))))) Vo (I)))))))
(27)
j=1
Σ
(Rm)is Vo (z6))
(28)
j=l
(Rn Ve fo (In)))
(29)
where RG E RDxD is the matrix with entries
(Rn) = a aS din (zn)) o(fo (In)); (fe(zn)), dig offolzn)) (ff(zx)))
(xn)) ((
(30)
(31)
Thus, plugging back into 25
Val (In)
(In), yn)
Rn (Volsin (s
(32)
= ((x)) Pn p(xn),
(33)
which is Eq. 99) for the cross-entropy loss.
B.3 SECOND-ORDER APPRUXIMATION FOR OTHER LOSS FUNCTIONS
The same developments as above apply to any twice differentiable loss function The Hessian of the loss with the linearized model fiom instead of the full network fe can be written
V3 l (56 un) ((x,)" R2 (II)),
(34)
DDD has different form depending on the specific loss function. Thus, general loss function E still allows the use of the approximation used by SOSP- I. The only caveat is that R, in general can be any D x D-matrix (without sparsity or low-rank properties), so that matrix multiplication may in general not be as efficient for the above loss functions (described in detail in App. B.4); l); in this case the second complexity term for SOSP-I in Eq. (7) can worsen from O 2 O(N D2
where R. V2 (2)())))) Bn))==
21

---

Published as a conference paper at ICLR 2022
B.4 EFFICIENT MATRIX MULTIPLICATION FOR SQUARED LOSS AND -OOOSSY LOSS
Note that Ra is sum of diagonal matrix Th (first part in Eq. (11 and rank-1 matrix Riank.1 (second part in Eq. 31) Due to this special matrix form, the matrix multiplication (o(x))),) R,, (o (0(zz))))) in Eq. 5 has, for each pair s'), computational complexity linear in the dimension D (the number of NN outputs), rather than quadratic. For the diagonal part (IC"" (fo(En)), ((((n)))
dzj. the reason for this is similar to the one for the squared error:
D
(o(zn)0,) R (o(zn)0.)) =
Σ (d(xn)0,); (H (o(zn)0u)s
(35)
W=
Σ (d(IN)0,): ( (d(x,)0,)).
(36)
For the rank-1 1 part (RRmik-I),, -f((((()) ((( the O(D)) computation
(6(xn)0,) ( (o(xn)0s) Σ (o(xn)).); (R (d(xn)0s))
(37)
D
Σ (o(x))).): o(o(zu)) (((ooa))))) (0(xn)oz), o(F((rn)))
(38)
4=1
2 (o(z..))) ((ole.)))))
2 Σ
(o(z))),) offozz)))
(39)
Again, for these reasons, the overall computational complexity of SOSP-I is linear in D (see Sect. 2.1
instead of quadratic in D. This can make a significant difference for some datasets (e.g. 1000 classes on ImageNet).
An alternative O D)-efficient way of computing our second-order approximation follows by continu- ing from Eq. 25 noting that Vellin (xn) = Vefa( by (13)
Vid (f (xn), Un) = (Vofo(zn)) (Voo(fo(zw))) = =((n))" o² (Ix),
(40)
(41)
where we defined (xxx = Vo(o(fe(zw))) E PxP. Thus, each term in the sum 5 can be written
(d" Σ (o(z,)0.)s (I.)0)))
(42)
which again has complexity ODD). For this is necessary to pre-compute each (xx,) in addition to Φ(xx), J, but both have the same complexity.
We finally note that approximation of the second-order derivatives (i.e., of the Hessian) is somewhat different from the approximation made in (Peng et al.) 2019) for the cross-entropy case:
While we dropped all second-order derivatives (2ff((n)) of the pre-softmax activations, Peng et al. (2019) dropped all second-order derivatives of the post-softmax activiations, i.c. all terms
V (a Jo (x.)). A consequence of this difference that our approximation (33) (or (42) does not
depend on the labels yn (this is already apparent from our intermediate step Eq. (25) whereas
the approximation made in (Peng et al., 2019) does depend on the labels yn- The fact that our second-order approximation is independent of the yn is similar to the second-order approximation in the squared-loss case (see App. B.I above, and also (Peng et al. 2019)). )) Note furthermore that the first-order terms in the loss approximation (see e.g. in Eq. (2) or (3) the same in method as in (Peng et al. 2019)), and these do depend on the labels yn (cf. the expression in square bracket in Eq. (3)).
22

---

Published as a conference paper at ICLR 2022
C SECOND-ORDER APPROXIMATION CORRESPONDS TO
The purpose of this section is provide better intuition of the second-order components of our loss approximation. First, we reformulate the expression for the second-order terms in Eq.[5) We use the fact that for any ReLU-NN without batch normalization layers it holds almost everywhere that
Vofo(z)0,- = fo-
(43)
where 0 is the weight vector, where all structures of the layer that contains structure set to zero expect for the weights of structure s itself. The identity straightforward to derive, therefore we show the relation for feed-forward neural network with zero biases, but the proof for convolutional neural network is almost identical..
Let fo be WL1,--10)20 WL-1 (=)20 W12, where Wi are the weight-matrices and h (z) the output functions of the 1-th layer and [)(())2 the diagonal matrix with the step function the diagonal elements corresponding to the components of h (xr) 2 Now assuming that structure is contained in the i-th layer, the only von-sanig components of the vector 0, are the once associated with structure s. Thus, one can evaluate the gradient to get
fully-connected neural network with L layers and fo(æ)
vofo(z)0, Wolw- -oo
(44)
where W is the weight matrix of layer i where components are set to zero except for those belonging to structure Using this, one directly receives Volo(x)0. (a-(x)
Next, applying this identity Eq. gives
8. ((00
1
Σ
(o(zn)02) Rn (o(zn)0,)
N
==1
1
(Vofo(z))..) R. (Vofo(zn)0.))
N
N Sa (2.)) Rn (In),
where the explicit form of the Rt matrix is provided in the previous section. From this relation one can now see that the second-order components of our pruning objective correspond to output- correlations. This connection could also explain, why our second-order pruning methods do not improve the pruning performance at initialization, but do improve performance after training, since at initialization different structures may not have as strong output-correlations as the learned features after training.
D COUNTING OF PARAMETERS AND MACS
Here we provide details on how we compute the number of parameters of our pruned NNs, and the number of MACs required for the evaluation of a pruned NN one input point. The description is specific to the ResNets and DenseNets used in our work; the main complication arises for the ResNet architecture (in particular for the residual connections). we describe below.
While our parameter and MAC counting is exact, it is somewhat intricate. We do not know whether this exact counting has been implemented in other papers on pruning as well (see the comparisons in Tables [ and 22). since these other works did not elaborate on their counting. Therefore, the comparability with the counts from other papers not necessarily given. When we compare our exact counting to more straightforward but approximative counting, we find that our exact counts for ResNet50 (Table 2) yield substantially higher parameter and MAC numbers than the straightforward approximate counting. The straightforward approximate counting would yield MAC-prunine ratios that are 12-18 18 percentage points higher (better) than our exact numbers. We now explain our exact counting first
23

---

Published as a conference paper at ICLR 2022
The number of parameters of convolutional layer I equals the number F of input filters of the layer times the number Flui of output filters times the kernel size K (which equals the kernel width times the kernel height); C' 17 FFout Kgrh, In addition to this count, there are 2 parameters for the batchnorm layer following each convolutional layer (our networks do not have bias terms in the convolutional layers, which would add another F,
The subtlety is now that, within the chain of convolutional layers in the ResNet architecture, the number F741 of imput filters into the following convolutional layer + 1 does not necessarily equal the number of output filters Fqut of the present convolutional layer 1. Namely, this can happen if the output of layer is added to the output of a residual connection to compute the input into | ++1 1. At such a point in the chain of convolutional layers, the number of input filters F into layer + 1 depends on both the output filters of layer I as well as on the output filters of the residual connection.
More precisely, only those filters can be removed from the input into layer + which are absent from both the output of layer l as well as from the output of the residual connection. (Note, thus, that the number Fi of input filters into layer / cannot be determined by only knowing the number of output filters F and the number of output filters of the residual connection. Rather, the answer depends on which output filters have been pruned.) To determine Fi41. two kinds of residual connections have to be distinguished:
(a) Residual connection an identity skip connection. In this case, the output filters of the residual connection are exactly the output filters of a previous layer: either the output filters of layer /' ;= - 2 (when the skip connection is in a "BasicBlock") or of layer I' := - 3 (when the skip connection is in a "BottleneckBlock), Fi thus equals the number of filters that are un-pruned in the output of both layer I' and un-pruned in the output of layer 1.
(b) Residual connection a downsampling layer. As we exclude downsampling layers from pruning (see Sec. B) the number of output filters of a downsampling layer in the pruned network equals the number of outputs of the downsampling layer in the original network. Therefore, if the output of layer is added to the output of a downsampling layer, then P in the pruned network takes the same value as in the original (un-pruned) network, i.c. F is the original number of input filters into layer I +
The same reasoning and procedure applics to determining the number of input filters into any downsampling layer (i.e., this number is the same as the number of inputs into the convolutional layer that has the same input as the downsampling layer; note, a downsampling layer is a convolutional layer as well, but not part of the "chain of convolutional layers"), and also to determine the number of inputs ("input neurons") into the final fully-connected layer (i.e., the number of "input neurons" into the last fully-connected layer is the same would be the number of input filters into convolutional layer at this stage).
Having determined the number of input and output filters (neurons) into all channels in this way, our parameter count sums up the parameter numbers for all convolutional layers (incl. downsampling layers), batchnorm layers, and fully-com connectdd layers (inel. bias terms). This is the exact number of parameters needed to specify the pruned NN and also to build the pruned NN, since these parameters specify all surviving filters (and the fully-connected layers).
Our exact MAC count is similar, also based on the "true" Fith and Fout as just determined. The MAC count of a convolutional layer is Mr- Ct ST" Sh. where S and Sth are the numbers of width-wise and height-wise applications of each filter; for our networks, S/" equals the spatial picture width at layer divided by the width-stride, and similarly for S..
Finally and as mentioned above we briefly describe the more straightforward but approximate counting method, that would yield pruning ratios that can appear quite a bit better. In this approximate way of counting, we take, within the chain of convolutional layers in the ResNet architecture, as input filters into layer / + 1 exactly the output filters from layer I, i.c. F := Frout Consequently for any downsampling layer, we take as its number of input filters the number of output filters of its preceding convolutional layer, and as its number of output filters we take the number of input filters into the following convolutional layer (as determined by the previous sentence). We compute the number of parameters and MACs then according to the same formulas as in the exact method, but with potentially other values for Pin and Fout for all convolutional layers (incl. the downsampling
24

---

Published as a conference paper at ICLR 2022
layers, and the number of input nodes into the last fully-connected layer). Note, this approximate count actually the exact count for version of the pruned network where the size of the residual connections (identity skip connections and downsampling layers) has been adapted in "natural" way to the sizes of the pruned convolutional layers in the chain of convolutional layers. In particular, this count therefore be computed by just knowing the numbers of pruned filters in each convolutional layer, instead of knowing exactly which of the filters in each convolutional layer have been pruned.
It is apparent from the way of approximate counting just described that its parameter and MAC count will be smaller or equal to the exact count (described futher above); both counts conincide for the original (un- unnppruned) network. For pruned networks, however, the difference in both counts can be substantial, esp. for the ResNet50 network (Table 2 For example, whereas the MAC-pruning-rane of our SOSP-I(0.3) method 15% (see Table 2 its MAC-pruning-ratte according to the approximate counting would equal 27%. In case that the competitor papers used this simpler approximate counting (which we do not know), we should also use this approximate counting evaluate our method, which would thus appear more favorable, especially on the ImageNet experiments and especially on ResNet-50 (
On final note, remark that the paper Tang al. (020 introducing the SCOP method, mentioned a discrepancy between the theoretically computed number of MACs and the experimentally measured value for this quantity, hinting at least at some inconsistency in the counting.
25


Reviews:
[{"review_id": "nV45x2mYZi0", "reviewer": "Reviewer_3yXC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "On the strengths\n\n1. Network pruning is important for deep learning approach and its wide application to practical tasks.\n2. It is sound to consider the second-order correlation information among the structures of neural networks to conduct pruning. \n3. Experimental study demonstrates the overall better performance of the proposed SOSP-H with respect to the relevant methods proposed in the literature;\n4. This papers provides detailed discussion and supplementary materials to explain the proposed work. \n\nOn the weaknesses\n1. Some parts on proposing SOSP can be made clearer. For example, it mentions Eq. (2) as \"a modification of Eq.(1).\" However, the relationship between Eq.(1)  and Eq.(2) is not clearly discussed. It seems that Eq.(2) is a (much) relaxed upper bound of Eq.(1)? In this case, how accuracy can Eq.(2) approximate Eq.(1)? The similar issue applies to the relationship between Eq. (6) to Eq.(1). Please clarify. \n2. The logic behind deciding the architectural bottleneck could be made more precise. Say, if some layers are barely pruned, does this actually mean they are so important that they shall not be removed? In this case, how to arrive at the idea in this work that \"removing these could further improve the performance of the model?” Please clarify.  \n3. This paper provides detailed discussion in Section 4, which is appreciated. Meanwhile, the summary of this discussion could be put before  Section 2 as Related Work. This will help to introduce the existing literature on second-order information based pruning and highlight the differences of the proposed work from the existing ones. This helps to better capture the novelty of this work.   \n", "summary_of_the_paper": "This paper proposes a method to prune deep neural networks. The aim is to reduce the computational cost and inference time while maximally maintaining the classification performance. The motivation of this work is to consider second-order structured pruning (SOSP), which considers the correlation information among the structures and layers when conducting network pruning. The key part of this work is the development of a method called SOSP-H that can have better scalability while considering the second-order correlation information for pruning. Experimental study is conducted to compare the proposed SOSP-H with its variant and other existing related methods, demonstrating its effectiveness.", "summary_of_the_review": "This is a piece of work of good quality, with detailed information. A rigorous and principled approach is taken by this work to address the second-order pruning issue. Experimental study demonstrates the overall competitive performance of the proposed method. At the same time, some parts of this work can be further clarified to make the argument more precise and clearer. The novelty and contribution with respect to the existing relevant methods can be better described. Also, the structure of the presentation can be improved a bit.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "dzZodtHQ6s3", "reviewer": "Reviewer_q96Z", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths(+):\n1. The proposed approximation schemes for second-order structured pruning is interesting with theoretical derivations and rigorous experimental test. \n2. The paper is well written and the presentation is clear.\n\nWeaknesses(-):\n1. I am concerned on the advantages of using second-order information to improve the pruning performance for networks with large number of parameters, as can be seen from Fig. 4, the performance gap between first-order method and SOSP is quite small when #parameters reach 750K. Modern large-scale networks usually have even more parameters. \n2. The Fig.5 also raises some concerns since the gap on test accuracy between first-order and SOSP is only around 0.1%~0.3% percent, which has quite limited improvement. \n3. It seems that the merit of capturing global correlation and good scalability is not achieved by a single approximation method, but by the SOSP-I and SOSP-H respectively. This may decrease the technical attractiveness of the paper.\n\nMinors:\n1. Maybe due to space limitation, some important Figures are put into supplementary materials, the readers need to read back and forth to get a clear understanding.", "summary_of_the_paper": "This paper develops two novel saliency-based pruning methods for second-order structured pruning which consider correlations among all structures and layers and have good scalability to large-scale neural network structures and datasets. The proposed method can also be used to find and remove architectural bottlenecks, which further improves the performance of the pruned networks.", "summary_of_the_review": "Due to the limited potential performance improvement in practical benchmark database, my overall rating would be (weak) rejection", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "V74_QEfvK9", "reviewer": "Reviewer_6Vrj", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n1. This paper makes a good contribution in presenting the idea around structured-based model pruning. The mathematical derivation is very well presented and easy to follow, and the literature review is also very well presented.\n\n2. The experiments are also promising, and they show the superior performance of the proposed approach in terms of effectiveness in reducing the parameters while keeping the classification performance.\n\nWeakness\n1. The second-order approximation seems to be specialized for squared loss and cross-entropy loss. I am not sure if the proposed approximation can be generalized to the other losses. This limits the impact of the proposed approach, as modern neural networks might involve many other forms of losses.e.g. MSELoss, NLLLoss, CTCLoss, PoissonNLLLoss. How can one adopt the proposed approximation for the wide range of loss functions?\n\n2. Some key implementation details are missing out in the paper.\n\na) The fast hessian-vector product seems to be the critical component of the proposed SOSP-H method. However, it is not clear how this is exactly implemented. It is not clear how the fast hessian-vector product is implemented to achieve the second-order approximation.\nUsing the hessian seems to be a great idea, but I am unsure how the proposed approach addresses the storage problems. For example, storing the hessian matrix for a standard ResNet50 would take at least 2.5 Petabytes of memory. For larger-scale neural networks, how would the proposed approach be able to address them? What are the theoretical limits on the proposed method that the SOSP-H cannot handle? Given that the SOSP-I results are not as great as those with SOSP-H, I think audiences might be more interested in the SOSP-H. But the high space cost seems to be a problem.\n\nb) The presentation arrangement of this paper could be improved significantly. Some technical terms are presented without explanation. For example, what does it mean “individual sensitives”?\n\n3. Some comparisons are missing out. How does the proposed approximation approach compare against the empirical Fisher approximation? I only get to know more about the mathematical details of this after reading the supplementary, it would be great to add some key approximation equations to the main paper.\n\n4. The main evaluation metrics used in this work are MAC numbers and the model Top-1 accuracy. It would be interesting to see the speed of the pruned networks on the standard devices, though this is missing in the current paper.", "summary_of_the_paper": "This paper address the problem of neural network single-shot structured-based model pruning. \n\nDeep convolutional neural networks grow to achieve higher performance, which also means slower inference and higher computational cost. Model pruning can help with that. Model pruning can be unstructured, which means to remove individual weights, or structured, which means to remove entire substructures, e.g., nodes or channels. This paper focuses on structured pruning.\n\nA key challenge for global saliency-based structured model pruning is to find a good objective that can be efficiently calculated to make the approach scalable to various modern convolutional neural networks. Existing saliency-based pruning methods such as OBD, C-OBD evaluate the effect of removing a single weight or structure on the loss of the neural network in isolation. This work is to devise a 2nd order pruning method that considers all global correlations for structured sensitivity pruning.\n\nThe basic idea in this work is to search for the pruning mask M to minimize the joint effect on the network loss approximately. The mathematical approximation focuses on the second-order approximation to the loss. \n\nThe key contributions of this work are the proposed 2nd-order structured pruning (SOSP). There are two variants of that. The first one is based on fast hessian-vector products, and it has the same complexity as that with first-order methods. A second one is based on the Gaussian-newton approximation. The first one with fast hessian-vector products do better in terms of scale.\n\nExperiments on VGG, ResNets, PlainNet, DenseNet are shown promising results across various image classification datasets, including Cifar10/100 and ImageNet.\n", "summary_of_the_review": "1. This paper is an exciting work, and it would have a solid impact on the structured-based model pruning.\n\n2. This submission also has a lot of minor issues. For example, the second-order approximation seems to be developed towards addressing particular two losses used in classification. It is not clear if the proposed approach would work for the other losses.\n\n3. Some technical terms are not well explained.\n\n4. The evaluation metrics used in this work should also include speed, but it is missing in the current submission.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SgHAh2AJ20z", "reviewer": "Reviewer_7bu1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "\nFor the SOSP-H, it assumes the pruning ratios should be high and then the approximation would be held. In Tab.1 and Tab.2, I can see that the reduction ratios of weights for Densenet40 on Cifar10/100 are around 50% and similarly for ResNet 18/50 on ImageNet. So I suggest the authors clarify what ratios are considered to be high.\n\nIn Tab.2, when comparing with the other methods, the performance of the proposed methods is on par with the SOTA. Whether the pruning efficiency will outperform the other methods. I can see in Fig. 1 the authors demonstrated results on Cifar, but how about on ImageNet?\n\nI am not an expert on network pruning. However, I am wondering why the compared methods are from 2019 and 2020. Whether some references published in 2021, such as Liu et al. 2021, Hayou et al. 2021, Su et al. 2021, can be compared?\n\nIn Fig. 3, the orange bars are not clear to me. The vertical axes are representing different meanings that are not easy for readers to understand. For c and f, whether the pruning mainly focuses on input and low-level layers? Why did those layers have low pruning ratios originally? Maybe the authors could explain it and visualise filters before and after pruning?\n\nI think the comparison with CCP is also needed in Tab. 1 as it is also based on second-order correlations.\n\nLast but not least, when I recap the formulation of this paper, from Eq. 1 to 6, I also wonder if in general eq. 6 is the main contribution of this paper while eq.5 is not scalable (though it has very nice deduction). Whether eq. 5 is not necessary for practical problems?", "summary_of_the_paper": "This paper presents saliency-based second-order structured pruning methods, namely SOSP-I and SOSP-H. The proposed methods are designed to capture the correlations among all structures and layers, known as second-order structure (Hessian). In particular, SOSP-I employs Hessian approximation while SOSP-H employs exact Hessian. Overall, the idea of this paper is very clear, and I kinda like the discussion part of it. The expand-pruning is also interesting. ", "summary_of_the_review": "Overall, I think this paper has its merits. However, as I am not an expert in this field but a general reader. I am lean to accept this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Four reviewers have evaluated this submission with one score 6 and three scores 8. Overall, reviewers like the work and note that *a rigorous and principled approach is taken by this work*. AC agrees and advocates an accept.
Decision: Accept (Spotlight)