Year: 2021

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 widen to further increase the accuracy of the networks.

heading: 1 INTRODUCTION
text: 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 (e.g., LeCun et al., 1990; Hassibi et al., 1993; Reed, 1993; Han et al., 2015; Blalock et al., 2020). Pruning can either be unstructured, i.e. removing individual weights, or structured, i.e. 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 in 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, structured pruning can directly reduce inference time and even training time when applied at 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 a network until a 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 pruning, on 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 a 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 et al., 2018) learn the layer-wise pruning ratios in a 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-order methods (Molchanov et al., 2019), calculating the full second-order saliency objective is intractable for modern neural networks. Therefore, most saliency-based pruning methods such as OBD (e.g., LeCun et al., 1990) or C-OBD (Wang et al., 2019a) evaluate the effect of removing a 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 a global second-order method that both considers off-diagonal terms and scales to modern neural networks is still an unsolved research question.
Our main goal in this work is to devise a 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 on 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 on 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 a variety of state-of-the-art 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.
PyTorch code implementing our method will be published upon acceptance of this manuscript.
Related work is discussed in the light of our results in the Discussion section (Sec. 4).

heading: 2 SOSP: SECOND-ORDER STRUCTURED PRUNING
text: A neural network (NN) maps an input x ∈ Rd to an output fθ(x) ∈ RD, where θ ∈ RP are its P parameters. NN training proceeds, after random initialization θ = θ0 of the weights, by minibatch stochastic gradient descent on the empirical loss L(θ) := 1N ∑N n=1 ` (fθ(xn), yn), given the training dataset {(x1, y1), . . . , (xN , yN )}. In the classification case, y ∈ {1, . . . , D} is a discrete ground-truth label and `(fθ(x), y) := − log σ (fθ(x))y the cross-entropy loss, with σ : RD → RD the softmax-function. For regression, y ∈ RD and `(fθ(x), y) = 12 ‖fθ(x)− y‖ 2 is the squared loss.
Structured pruning aims to remove weights or rather entire structures from a NN fθ 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 a 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 θs ∈ RP as the vector whose only nonzero components are those weights from θ that belong to structure s.1 Then, a pruning mask is a set M = {s1, . . . , sm} of structures, and applying a mask M to a NN fθ means to consider the NN with parameter vector θ\M := θ − ∑ s∈M θs.
We now develop our pruning methods that incorporate global correlations into their saliency assessment by efficiently including the second-order loss terms. Our method SOSP-I allows a direct interpretation in terms of individual loss sensitivities, while our main method SOSP-H remains very efficient for large-scale networks due to its Hessian-vector product approximation.
1We require that each weight is assigned to at most one structure. In practice, we associate with each structure those weights that go into the structure, rather than those that leave it.
The basic idea behind both our pruning methods is to select the pruning mask M so as to (approximately) minimize the joint effect on the network loss
λ(M) := ∣∣L(θ)− L(θ\M )∣∣
of removing all structures in M , subject to 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(M) = ∣∣∣∣∣∣ ∑ s∈M θTs dL(θ) dθ − 1 2 ∑ s,s′∈M θTs d2L(θ) dθ dθT θs′ ∣∣∣∣∣∣ (1) collapses to single-structure contributions plus pairwise correlations.
The first-order terms λ1(s) := θs ·dL(θ)/dθ in (1) are efficient to evaluate by computing the gradient dL(θ)/dθ ∈ RP once and then a (sparse) dot product for every s. In contrast, the network Hessian H(θ) := d2L(θ)/dθ2 ∈ RP×P in (1) is prohibitively expensive to compute or store in full. We 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).

heading: 2.1 SOSP-I: SALIENCY FROM INDIVIDUAL SENSITIVITIES
text: SOSP-I approximates each individual term θTs H(θ)θs′ in (1) efficiently, as we will show in Eq. (5). We will therefore consider an upper bound to Eq. (1) which measures all sensitivities individually:
λI2(M) = ∑ s∈M ∣∣∣∣θTs dL(θ)dθ ∣∣∣∣+ 12 ∑ s,s′∈M ∣∣θTs H(θ)θs′ ∣∣ . (2) The absolute values are to prevent cancellations among the individual sensitivities of the network loss to the removal of structures, i.e. the derivatives λ1(s), and individual correlations θTs H(θ)θs′ . While objectives other than λI2 are equally possible in the method, including λ2 and variants with the absolute values not pulled in all the way, we found λI2 to empirically perform best overall.
Then, SOSP-I iteratively selects the structures to prune, based on the objective (2): Starting from an empty pruning mask M = {}, we iteratively add to M the structure s /∈ M that minimizes the overall sensitivity λI2(M ∪ {s}). In practice, the algorithm pre-computes the matrix Q ∈ RS×S ,
Qs,s′ := 1
2 ∣∣θTs H(θ)θs′ ∣∣+ ∣∣∣∣θTs dL(θ)dθ ∣∣∣∣ · δs=s′ , (3)
and selects at each iteration a structure s /∈M to prune by
argmin s/∈M λI2(M ∪ {s})− λI2(M) = argmin s/∈M
( Qs,s + 2 ∑ s′∈M Qs,s′ ) , (4)
terminating at the desired pruning ratio. To computeQ efficiently, we show in App. B that the Hessian terms can be approximated as
θTs H(θ)θs′ ≈ 1
N ′ N ′∑ n=1 (φ(xn)θs) T Rn (φ(xn)θs′) . (5)
Herein, the NN gradient φ(x) := ∇θfθ(x) ∈ RD×P forms the basis of the well-established GaussNewton approximation (see App. B for more details) used for the Hessian, and the matrices Rn ∈ RD×D 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 φ(xn)θs ∈ RD starting from the efficiently computable gradient φ(xn), before aggregating a batch onto the terms θTs H(θ)θs′ . Eq. (5) also has an interpretation as output correlations between certain network modifications, without derivatives (App. C).

heading: 2.2 SOSP-H: SALIENCY FROM HESSIAN-VECTOR PRODUCT
text: SOSP-H treats the second-order terms in (1) in a different way, motivated by the limit of large pruning ratios: At high pruning ratios, the sum ∑ s′∈M θs′ in (1) can be approximated by ∑S s′=1 θs′ =:
θstruc (this equals θ if every NN weight belongs to some structure s). The second-order term∑ s,s′∈M θ T s H(θ)θs′ ≈ (∑ s∈M θ T s )( H(θ)θstruc ) thus becomes tractable since the Hessian-vector product H(θ)θstruc is efficiently computable by a variant of the backpropagation algorithm. To account for each structure s and for the first- and second-order contributions separately, as above, we place absolute value signs in (1) so as to arrive at the final objective λH2 (M) := ∑ s∈M λ H 2 (s) with
λH2 (s) := ∣∣∣∣θTs dL(θ)dθ ∣∣∣∣+ 12 ∣∣θTs (H(θ)θstruc)∣∣ . (6)
To minimize λH2 (M), SOSP-H starts from an empty pruning mask M = {} and successively adds to M a structure s /∈M with smallest λH2 (s), until the desired pruning ratio is reached. Unlike the Gauss-Newton approximation in SOSP-I, SOSP-H uses the exact Hessian H(θ) in the Hessian-vector 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. (6), 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; we compare to the resulting first-order method in Sec. 3.1 (see also App. A.1).

heading: 2.3 COMPUTATIONAL COMPLEXITY
text: 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 (N ′D(F + P )) = O(N ′DF ) for computing all φ(xn)θs, where F ≥ P denotes the cost of one forward pass through the network (F ≈ P for fully-connected NNs), plus O(N ′DS2) for the sum in (5). This is tractable for modern NNs, while including the exact H(θ) would have complexity at least O(N ′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 ′DS2) +O(S3). (7)
SOSP-H requires computational complexity O(N ′DF ) both to compute all the first-order as well as all the second-order terms in Eq. (6). Together with the sorting of the saliency values λH2 (s), SOSP-H has thus the same low overall complexity as a first-order method, namely
O(N ′DF ) +O(S log(S)). (8)
Due to its weak dependency on S, in practice, SOSP-H efficiently scales to large modern networks (see Sec. 3.2), and may even be used for unstructured second-order pruning, where S = 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 O(N ′DSF ) scaling. Since SOSP-I builds on individual absolute sensitivities and on the established Gauss-Newton approximation, we use SOSP-I in the following in particular to validate our more efficient main method SOSP-H.

heading: 3 RESULTS
text: To evaluate our methods, we train and prune VGGs (Simonyan & Zisserman, 2014), ResNets (He et al., 2016), PlainNet (He et al., 2016), and DenseNets (Huang et al., 2017) on the Cifar10/100 (Krizhevsky et al., 2009) and ImageNet (Deng et al., 2009) datasets. Stochastic gradient descent with an initial learning rate of 0.1, a momentum of 0.9 and weight decay of 10−4 is used to train these networks. For ResNet-32/56 and VGG-Net on Cifar10/100, 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 a 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 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. The experiments were run on an internal cluster with Nvidia Tesla V100 GPUs.

heading: 3.1 COMPARISON ON MEDIUM-SIZED DATASETS
text: 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 to 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 on 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 use of our second-order objective which takes correlations into account. First, we compare the pruning accuracy of a first-order method (dropping all second-order terms in either Eq. (3) or (6)) to our second-order SOSP objectives. The results (see App. A.1) clearly
indicate, that second-order information improves the pruning performance. Second, we investigate whether the off-diagonal elements of the second-order terms improve the final accuracies. We perform this comparison using a variant of SOSP-I, where the off-diagonal terms ∑ s′ Qs,s′ in Eq. (4) are dropped. The results (see App. A.2) again suggest that adding these off-diagonal terms leads to a 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 to 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 et al., 2017) as well as EigenDamage and C-OBD (Wang et al., 2019a), e.g. capping the layer-wise ratio of removed structures at 95% for VGGs to prevent layer collapse and increasing the width of ResNet-32 by a factor 4. C-OBD is 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. 1 and for moderate pruning ratios in App. A.3. To enable the comparison to NN Slimming on 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-regularization on the batchnormalization 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 Cifar100 (see Tab. 4). The only exception is the accuracy for C-OBD applied to VGG-Net on Cifar100, which drops by approximately 1%. For ResNet-32 on Cifar100 the accuracy after pruning is 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 Cifar100, where SOSP outperforms EigenDamage by almost 3%. For DenseNet-40, we achieve similar results compared to NN Slimming. However, note that NN Slimming depends on the above L1-modification 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-20 (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.e. layer-wise, pruning algorithms: FPGM He et al. (2019), GAL (Lin et al., 2019), CCP (Peng et al., 2019) (see Fig. 7), Variational Pruning (VP; Zhao 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. 1a and b). For DenseNet-40, SOSP achieves better accuracies when compared over parameters (Fig. 1c) and is on par with the best other methods over MACs (Fig. 1d). The reason for this discrepancy is probably that the SOSP objective is agnostic to the number of MACs (image size) in each individual layer.

heading: 3.2 SCALABILITY AND APPLICATION TO LARGE-SCALE DATASETS
text: 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 O(S3) (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 is more efficient than SOSP-I, see Fig. 2 and App. A.5. Since SOSP-I becomes impractical for large-scale networks like other second-order methods (Molchanov et al., 2019; Wang et 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 a bias towards pruning small-scale structures. This tendency is strongest for ResNet-50, due to its 1 × 1-convolutions. Since these 1 × 1-convolutions tend to contribute disproportionately little to the overall number of MACs, we devised a scaled variant of SOSP, which
divides the saliency of every structure by its kernel size (e.g. 1, 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).
For both networks SOSP outperforms FPGM and HRank, especially when considering the main objective of SOSP, which is to reduce the number of parameters or structures. Since CCP uses a different way of calculating the MACs, which leads to consistently higher pruning ratios, we added an alternative MAC count to 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), a 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.1 and esp. App. A.1), where we show that including second-order information leads to improved accuracies.

heading: 3.3 IDENTIFYING & WIDENING ARCHITECTURAL BOTTLENECKS
text: 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 as 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. 8(d,g,e,h) and Fig. 3 (c,d,f,g)), namely that some layers are barely pruned while others are pruned by more than 80%. This could indicate towards architectural bottlenecks; widening these could further improve the performance of the model. We consider a 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 a schematic, see Fig. 3a). As a naive baseline that we call the widen-pruning procedure, we widen every 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 (e.g., leading to the width multiplier 1.1 in Fig. 3).
We evaluate the expand-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. 3(c,f) selected on the basis of the pruning masks shown in Suppl. Fig. 8(d,g)). Note that a more fine-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. 3(b,e)). While in principle any global pruning method could be used for the expand-pruning procedure, SOSP is especially suited since it does not require to modify the network architecture like EigenDamage. Further, SOSP can be applied directly at initialization (see App. A.9), unlike e.g. NN Slimming, allowing for a similar expand scheme directly at initialization (see App. A.10).

heading: 4 DISCUSSION
text: 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-sized networks. Further, we showed that the pruning masks found by SOSP can be used to systematically detect and widen architectural bottlenecks, further improving the performance of pruned networks.
Compared to other global pruning methods, SOSP captures correlations between structures by a simple, effective and scalable algorithm that requires to modify neither the training nor the architecture of the network model to be pruned. SOSP achieves comparable or better accuracies on benchmark datasets, while having the same low complexity as first-order methods. The C-OBD algorithm (Wang et al., 2019a) is a structured generalization of the original unstructured OBD algorithm (LeCun et al., 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. 1). This is in line with the results of our ablation study in App. A.2 (see also Sec. 3.1). The objective of EigenDamage (Wang et al., 2019a) to include second-order correlations is similar to ours, but the approaches are significantly different: EigenDamage uses the Fisher-approximation, which is similar to SOSP-I’s Gauss-Newton approximation and exhibits a similar scaling behaviour, and then, in addition to further approximations, applies low-rank approximations that require the substitution of each layer by a bottleneck-block structure. Our SOSP method is simpler, easier to
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., 2017) is more heuristic than SOSP and is easy to implement. However, networks need to be pretrained with L1-regularization on the batch-normalization parameters, otherwise the performance is severely harmed (Tab. 1 and Supp. Tab. 4). 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 Zhuang et 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 second-order structured pruning methods either approximate the Hessian as a diagonal matrix (Theis et al., 2018; Liu et al., 2021) or use an approximation similar to Gauss-Newton, which we used for SOSP-I (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 our SOSP-I method is the one by Peng et al. (2019). While both works consider second-order correlations between structures, theirs is based on a ranking scheme different from our absolute sensitivities in λI2 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 at initialization seems to preferentially prune initial layers and thus proposed a 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 Su 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. 8). 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-wise 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), EagleEye (Li et al., 2020), DMCP (Guo et al., 2020) and CafeNet (Su et al., 2021). It is difficult to enable a 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 a 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 et al., 2021). Further, introducing additional hyperparameters for each layer optimized to reduce the number of MACs as done by Chin et al. (2020) could potentially lead to further improvements, but would also significantly increase the complexity due to the need of hyperparameter optimization. Liu et al. (2021) 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 to 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 et al., 2020; Hayou et 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. A.8) that our SOSP method at initialization can, after comparable training time, achieve accuracies similar to pruning after training.
In accordance with Elsken et al. (2019), our results suggest that pruning can be used to optimize the architectural hyperparameters of established networks (Liu et al., 2018) or super-graphs (Noy et al., 2020); see also App. A.11. We envision our second-order 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.

heading: SOSP: Efficiently Capturing Global Correlations by

heading: Second-Order Structured Pruning

heading: A ADDITIONAL DATA AND EXPERIMENTS

heading: A.1 COMPARISON OF FIRST-ORDER STRUCTURED PRUNING WITH SOSP
text: 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 et al., 2019) on ImageNet, which is basically a first-order method (see Sec. 3.2).

heading: A.2 COMPARISON OF ACCURACIES ACHIEVED BY SOSP-I WITH AND WITHOUT CROSS-STRUCTURE CORRELATIONS
text: See Figure 5 and its caption (cf. also Sec. 3.1 for further descriptions).

heading: A.3 RESULTS FOR MEDIUM PRUNING RATES FOR COMPARING GLOBAL PRUNING METHODS
text: See Table 4 and its caption. (For high pruning rates, see Table 1 in Sec. 3.1.)

heading: A.4 COMPARISON TO PRUNING-METHODS THAT FIND LAYER-WISE PRUNING RATES
text: See Table 5 and its captions (cf. also Sec. 3.1 for further descriptions).

heading: A.5 RUNTIME COMPARISONS OF SOSP-H AND SOSP-I
text: The results of Table 6 complement the results of Fig. 2 and show that while SOSP-I is 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.

heading: A.6 PLOTS FOR COMPARISON OF SOSP ON RESNET-18/50 FOR LARGE-SCALE DATASETS
text: See Figure 6 and its caption (cf. also Sec. 3.2 for further descriptions).

heading: A.7 COMPARISON OF SOSP ON RESNET-56 AGAINST CCP
text: See Figure 7 and its caption (cf. also Sec. 3 for further comparisons on ResNet-56).

heading: A.8 PRUNING AT INITIALIZATION
text: Traditionally, pruning methods are 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 of Lee et al. (2018) and Frankle & Carbin (2018). Since SOSP employs the absolute value of the sensitivities, it can also be applied to a randomly initialized network without any modifications. Thus, SOSP can also be seen as an efficient second-order generalization of SNIP (Lee et al., 2018; van Amersfoort et al., 2020). While EigenDamage can in principle be modified and applied to a randomly initialized network as well, NN Slimming can not be applied at 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. 8a). 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. 8b; for further discussion, see App. A.9).
We observe that applying SOSP at initialization performs almost equally well than applying SOSP after training (see ResNet-56 and VGG in Fig. 8c 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.

heading: A.9 PRUNING AT INITIALIZATION VS PRUNING A PRETRAINED NEURAL NETWORK
text: In this section we investigate further why pruning a randomly initialized network tends to achieve lower accuracies compared to pruning a pretrained network (Lee et al., 2018; van Amersfoort et al., 2020). We compare the final accuracies of pruning and fine-tuning a randomly initialized and pretrained network (see Fig. 9). 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 one needs to device settings that enable a fair comparison, ensuring similar accuracies for random pruning accross both settings.

heading: A.10 EXPAND-INIT DATA
text: This section provides the experimental results of the corresponding expand-procedure at initialization (see Sec. 3.3). The results of Fig. 8 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 a pretrained
network but for a randomly initialized network. Following the expand scheme the network is pruned and then only fine-tuned once. The results are displayed in Fig. 10.

heading: A.11 SHUFFLE EXPERIMENTS
text: See Table 7 and its caption.

heading: A.12 MEAN AND STANDARD DEVIATION OF FINAL ACCURACIES FOR THE GLOBAL PRUNING COMPARISON
text: See Table 8 and its caption.

heading: A.13 TABULAR DATA AND MEAN AND STANDARD DEVIATION FOR LAYER-WISE PRUNING COMPARISON
text: This section provides additional data complementing the results of Fig. 1. The numerical data of Fig. 1 is shown in Tab. 9 and the mean and standard deviation of the final accuracies for both SOSP algorithms is shown in Tab. 10 and Fig. 11.

heading: B APPROXIMATIVE SECOND-ORDER DERIVATIVES
text: In order to approximate the Hessian terms θTs H(θ)θs′ in the matrix Q efficiently (see Eq. (2) and (3)), we omit from H(θ) = 1N ∑ n∇2θ`(fθ(xn), yn) those terms that involve the expensive second-order derivatives ∇2θfθ(xn) of the NN outputs, while including second-order couplings due to `. This is equivalent to approximating H(θ) ≈ H(f linθ ) := 1N ∑ n∇2θ`(f linθ (xn), yn) for the linearized
fθ′(x) ≈ f linθ′ (x) := fθ(x) + φ(x) · (θ′ − θ) with φ(x) := ∇θfθ(x) ∈ RD×P , which is well 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
∇2θ` ( f linθ (xn), yn ) = φ(xn) TRnφ(xn), (9)
where Rn ∈ RD×D is diagonal for squared loss, and has an additional rank-1 contribution for cross-entropy (see App. B.1 and App. B.2, respectively). Similar Hessian approximations were employed before in NNs (Hassibi et al., 1993; Wang et al., 2019a; Peng et al., 2019; Liu et al., 2021; Theis et al., 2018) and also in the Gauss-Newton optimization method (Fletcher, 2013).
Below we derive our approximation of the second-order loss derivatives Eq. (9) that lead to the desired Eq. (5), and especially the particular matrix structures of Rn 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 ∇2θfθ(xn) of the NN outputs fθ(xn) ∈ RD. We however still include second-order couplings due to the loss function `. Our approximation is thus to approximate the NN output
fθ′(x) ≈ f linθ′ (x) := fθ(x) + φ(x) · (θ′ − θ) (10)
to first order, where φ(x) := ∇θfθ(x) ∈ RD×P is the first-order derivative of the NN output, and then to approximate the second-order derivatives of the NN loss as follows:
∇2θ` (fθ(xn), yn) ≈ ∇2θ` ( f linθ (xn), yn ) . (11)
We now compute this approximation ∇2θ` ( f linθ (xn), yn ) for both the squared loss `(f, y) := 1 2 ‖f − y‖
2 as well as for the cross-entropy loss `(f, y) := − log σ(f)y, where σ : RD → RD denotes the softmax function. In this computation we use the following facts:
f linθ (xn) = fθ(xn), (12) ∇θf linθ (xn) := ∇θ′f linθ′ (xn) ∣∣ θ′=θ
= φ(xn) = ∇θfθ(xn), (13) ∇2θf linθ (xn) := ∇2θ′f linθ′ (xn) ∣∣ θ′=θ = 0, (14)
which follow directly from (10).

heading: B.1 SECOND-ORDER APPROXIMATION FOR SQUARED LOSS
text: For the squared loss, we obtain:
∇2θ` ( f linθ (xn), yn ) = ∇2θ
[ 1
2 (f linθ (xn)− yn)T (f linθ (xn)− yn)
] (15)
= (f linθ (xn)− yn)T (∇2θf linθ (xn)) + (∇θf linθ (xn))T (∇θf linθ (xn)) (16) = φ(xn) Tφ(xn) (17)
= φ(xn) TRnφ(xn), (18)
where Rn := 1D×D is here the D ×D-identity matrix. This is Eq. (9) for the squared loss. Due to this diagonal form of Rn, the matrix multiplication (φ(xn)θs)TRn(φ(xn)θs′) in Eq. (5) has, for each pair (s, s′), a computational complexity linear in the dimension D (which is the number of NN outputs), rather than quadratic:
(φ(xn)θs) TRn(φ(xn)θs′) = (φ(xn) T θs)(φ(xn)θs′) (19)
= D∑ j=1 (φ(xn)jθs)j(φ(xn)θs′)j , (20)
where (φ(xn)θs)j ∈ R denotes the j-th component of the vector φ(xn)θs ∈ RD. It is for this reason that the overall computational complexity of SOSP-I is linear in D (see Sect. 2.1), rather than of order O(D2).

heading: B.2 SECOND-ORDER APPROXIMATION FOR CROSS-ENTROPY LOSS
text: Note that the first derivatives of the softmax-function σ : RD → RD, defined by σ(f)i := efi/ ∑D k=1 e fk are:
∂
∂fj σ(f)i = −σ(f)i(σ(f)j − δij). (21)
We can thus compute for the cross-entropy loss, where δy· ∈ RD denotes the vector with entry 1 in component y and entries 0 everywhere else:
∇2θ` ( f linθ (xn), yn ) = −∇2θ [ log σ(f linθ (xn))yn ] (22)
= ∇θ [ (∇θf linθ (xn))T (σ(f linθ (xn))− δy·) ] (23)
= (∇θf linθ (xn))T (∇θσ(f linθ (xn))) + (∇2θf linθ (xn))T (σ(f linθ (xn))− δy·) (24)
= (∇θf linθ (xn))T · ( ∇θ σ(f linθ (xn)) ) . (25)
To compute ∇θσ(f linθ (xn) in (25), we consider its i-th component:
∇θ σ ( f linθ (xn) ) i = D∑ j=1 ∂σ(f)i ∂fj ∣∣∣∣ f=f linθ (xn) · ∇θ(f linθ (xn))j (26)
= D∑ j=1 σ(f linθ (xn))i ( δij − σ(f linθ (xn))j ) · ∇θ ( f linθ (xn) ) j
(27)
= D∑ j=1 (Rn)ij · ∇θ ( f linθ (xn) ) j
(28)
= ( Rn · ∇θ f linθ (xn) ) i , (29)
where Rn ∈ RD×D is the matrix with entries
(Rn)ij = σ(f lin θ (xn))iδij − σ(f linθ (xn))i σ(f linθ (xn))j (30)
= σ (fθ(xn))i δij − σ(fθ(xn))i σ(fθ(xn))j . (31)
Thus, plugging back into (25),
∇2θ` ( f linθ (xn), yn ) = ( ∇θf linθ (xn) )T Rn ( ∇θf linθ (xn) ) (32)
= φ(xn) T Rn φ(xn), (33)
which is Eq. (9) for the cross-entropy loss.

heading: B.3 SECOND-ORDER APPROXIMATION FOR OTHER LOSS FUNCTIONS
text: The same developments as above apply to any twice differentiable loss function `: The Hessian of the loss with the linearized model f linθ instead of the full network fθ can be written as
∇2θ ` ( f linθ (xn), yn ) = φ(xn) TRnφ(xn), (34)
where Rn = ∇2z`(z, yn) ∣∣ z=f linθ (xn)
∈ RD×D has a different form depending on the specific loss function. Thus, a general loss function ` still allows the use of the approximation used by SOSPI. The only caveat is that Rn in general can be any D × D-matrix (without sparsity or low-rank properties), so that matrix multiplication may in general not be as efficient as for the above loss functions (described in detail in App. B.4); in this case the second complexity term for SOSP-I in Eq. (7) can worsen from O(N ′DS2) to O(N ′D2S2).

heading: B.4 EFFICIENT MATRIX MULTIPLICATION FOR SQUARED LOSS AND CROSS-ENTROPY LOSS
text: Note that Rn is a sum of a diagonal matrix R diag n (first part in Eq. (31)) and a rank-1 matrix Rrank-1n (second part in Eq. (31)). Due to this special matrix form, the matrix multiplication (φ(xn)θs)
TRn(φ(xn)θs′) in Eq. (5) has, for each pair (s, s′), a computational complexity linear in the dimension D (the number of NN outputs), rather than quadratic. For the diagonal part( Rdiagn ) ij = σ (fθ(xn))i δij , the reason for this is similar to the one for the squared error:
(φ(xn)θs) TRdiagn (φ(xn)θs′) = D∑ i,j=1 (φ(xn)θs)i ( Rdiagn ) ij (φ(xn)θs′)j (35)
= D∑ j=1 (φ(xn)θs)i σ (fθ(xn))i (φ(xn)θs′)i. (36)
For the rank-1 part ( Rrank-1n ) ij = −σ(fθ(xn))i σ(fθ(xn))j , the O(D)-efficient computation is
(φ(xn)θs) TRdiagn (φ(xn)θs′) = ∑ ij (φ(xn)θs)i ( Rdiagn ) ij (φ(xn)θs′)j (37)
=− D∑ ij=1 (φ(xn)θs)i σ(fθ(xn))i (φ(xn)θs′)j σ(fθ(xn))j (38)
=− ( D∑ i=1 (φ(xn)θs)i σ(fθ(xn))i ) ·  D∑ j=1 (φ(xn)θs′)j σ(fθ(xn))j  . (39)
Again, for these reasons, the overall computational complexity of SOSP-I is linear inD (see Sect. 2.1), instead of quadratic in D. This can make a significant difference for some datasets (e.g. D = 1000 classes on ImageNet).
An alternative O(D)-efficient way of computing our second-order approximation follows by continuing from Eq. (25), noting that ∇θf linθ (xn) = ∇θfθ(xn) by (13):
∇2θ` ( f linθ (xn), yn ) = (∇θfθ(xn))T · (∇θ σ(fθ(xn))) (40) = φ(xn) T · φσ(xn), (41)
where we defined φσ(xn) := ∇θ (σ(fθ(xn))) ∈ RD×P . Thus, each term in the sum (5) can be written as
(φ(xn)θs) T (φσ(xn)θs′) = D∑ j=1 (φ(xn)θs)j (φ σ(xn)θs′)j , (42)
which again has complexity O(D). For this it is necessary to pre-compute each φσ(xn) in addition to φ(xn), but both have the same complexity.
We finally note that our 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 ∇2θfθ(xn) of the pre-softmax activations, Peng et al. (2019) dropped all second-order derivatives of the post-softmax activiations, i.e. all terms ∇2θ (σ(fθ(xn)). A consequence of this difference is 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.1 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)) are the same in our method as in (Peng et al., 2019)), and these do depend on the labels yn (cf. the expression in square bracket in Eq. (23)).

heading: C SECOND-ORDER APPROXIMATION CORRESPONDS TO OUTPUT-CORRELATION
text: The purpose of this section is to provide a 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
∇θfθ(x)θs = fθs(x), (43)
where θs is the weight vector, where all structures of the layer that contains structure s are set to zero expect for the weights of structure s itself. The identity is straightforward to derive, therefore we show the relation for a feed-forward neural network with zero biases, but the proof for a convolutional neural network is almost identical .
Let fθ be a fully-connected neural network with L layers and fθ(x) = WLlhL−1(x)≥0WL−1...lh1(x)≥0W1x, where Wl are the weight-matrices and hl(x) the output functions of the l-th layer and lhl(x)≥0 the diagonal matrix with the step function on the diagonal elements corresponding to the components of hl(x) ≥ 0. Now assuming that structure s is contained in the i-th layer, the only non-vanishing components of the vector θs are the once associated with structure s. Thus, one can evaluate the gradient to get
∇θfθ(x)θs =WLlhL−1(x)≥0WL−1...lhi(x)≥0W si ...lh1(x)≥0W1x, (44) where W si is the weight matrix of layer i where all components are set to zero except for those belonging to structure s. Using this, one directly receives∇θfθ(x)θs = fθs(x) Next, applying this identity to Eq. 5 gives
θTs H(θ)θs′ ≈ 1
N ′ N ′∑ n=1 (φ(xn)θs) T Rn (φ(xn)θs′)
= 1
N ′ N ′∑ n=1 (∇θfθ(xn)θs)T Rn (∇θfθ(xn)θs′)
= 1
N ′ N ′∑ n=1 fθs(xn)Rnfθs′ (xn),
where the explicit form of the Rn 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 outputcorrelations. 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.

heading: D COUNTING OF PARAMETERS AND MACS
text: 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 on 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), as 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 1 and 2), since these other works did not elaborate on their counting. Therefore, the comparability with the counts from other papers is not necessarily given. When we compare our exact counting to a 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-pruning-ratios that are 12-18 percentage points higher (better) than our exact numbers. We now explain our exact counting first.
The number of parameters of a convolutional layer l equals the number F inl of input filters of the layer times the number F outl of output filters times the kernel size K wh l (which equals the kernel width times the kernel height): Cl = F inl · F outl ·Kwhl . In addition to this count, there are 2F outl 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 outl ).
The subtlety is now that, within the chain of convolutional layers in the ResNet architecture, the number F inl+1 of input filters into the following convolutional layer l + 1 does not necessarily equal the number of output filters F outl of the present convolutional layer l. Namely, this can happen if the output of layer l is added to the output of a residual connection to compute the input into l + 1. At such a point in the chain of convolutional layers, the number of input filters F inl+1 into layer l + 1 depends on both the output filters of layer l as well as on the output filters of the residual connection.
More precisely, only those filters can be removed from the input into layer l + 1 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 F inl+1 of input filters into layer l + 1 cannot be determined by only knowing the number of output filters F outl and the number of output filters of the residual connection. Rather, the answer depends on which output filters have been pruned.) To determine F inl+1, two kinds of residual connections have to be distinguished:
(a) Residual connection is 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 l′ := l − 2 (when the skip connection is in a “BasicBlock”) or of layer l′ := l − 3 (when the skip connection is in a “BottleneckBlock”). F inl+1 thus equals the number of filters that are un-pruned in the output of both layer l′ and un-pruned in the output of layer l.
(b) Residual connection is a downsampling layer. As we exclude downsampling layers from pruning (see Sec. 3), 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 l is added to the output of a downsampling layer, then F inl+1 in the pruned network takes the same value as in the original (un-pruned) network, i.e. F inl+1 is the original number of input filters into layer l + 1.
The same reasoning and procedure applies 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 as would be the number of input filters into a 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-connected layers (incl. 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” F inl and F out l as just determined. The MAC count of a convolutional layer is Ml = Cl · Swl · Shl , where Swl and Shl are the numbers of width-wise and height-wise applications of each filter; for our networks, Swl equals the spatial picture width at layer l divided by the width-stride, and similarly for Shl .
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 l + 1 exactly the output filters from layer l, i.e. F inl+1 := F out l . 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 F inl and F out l for all convolutional layers (incl. the downsampling
layers, and the number of input nodes into the last fully-connected layer). Note, this approximate count is actually the exact count for a version of the pruned network where the size of the residual connections (identity skip connections and downsampling layers) has been adapted in a “natural” way to the sizes of the pruned convolutional layers in the chain of convolutional layers. In particular, this count can 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-pruned) 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-ratio of our SOSP-I(0.3) method is 15% (see Table 2), its MAC-pruning-ratio 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 to evaluate our method, which would thus appear more favorable, especially on the ImageNet experiments and especially on ResNet-50 (Table 2).
On a final note, we remark that the paper Tang et al. (2020) 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.

Review summaries:
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.

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. 

This paper address the problem of neural network single-shot structured-based model pruning.   Deep 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.  A 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.  The 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.   The 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.  Experiments on VGG, ResNets, PlainNet, DenseNet are shown promising results across various image classification datasets, including Cifar10/100 and ImageNet. 

This paper presents two novel approximation techniques for approximating the importance of a filter (the estimated loss difference between pruned and pre-trained networks) using second order approximations. The main difficulties of second order approximation lie in the computational burden of computing the full Hessian matrix. To circumvent this issue, this paper presents two novel ways to do so. The first approach, dubbed SOSP-I, linearize the neural network and only consider the coupling of the loss function. The second approach, dubbed SOSP-H, approximate the loss difference using a Hessian-vector product. Both approaches have much better efficiency compared to using the Hessian and empirically perform a little better than existing approaches. Overall, the approximations seem novel to me and I find the appendix helpful in understanding the derivations. However, their empirical advantages seem rather limited. Additionally, I think some of the related papers are missed and they need to be discussed and compared against.

This paper proposed a structured pruning method which include correlations among structures by second order information. The author also improved the computational efficiency by fast Hessian-vector products. The method is demonstrated to achieve comparable/better results than previous methods. And it can also be applied to pruning-at-initialization and reveal architecture bottlenecks.

This work proposes a structured pruning method that removes feature maps (channels) of convolutional neural networks without losing accuracy while increasing computational efficiency (MACs). The proposed method (SOSP-I/H) is based on a sensitivity based saliency and involves what they call global correlations through the second order partial derivatives with respect to different structures. SOSP shares a lot in common with previous works including OBD and C-OBD for the use of second order information except that they approximately incorporate all elements in the Hessian matrix. Then the paper evaluates the effectiveness of the proposed method for image classification task using VGG, ResNet, and Desnet on CIFAR and ImageNet datasets and achieve accuracies on par with previous works on both global and local (layerwise) pruning. The paper further presents that SOSP works on pruning at initialization and can improve further by performing expand-pruning based on skewed distribution of retained parameters over layers.