\section{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 \citep[e.g.,][]{lecun1990optimal,hassibi1993optimal,reed1993pruning,han2015learning,blalock2020state}.
Pruning can either be \emph{unstructured}, i.e.\ removing individual weights, or \emph{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 \emph{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 \citep{he2017channel}.
In contrast, structured pruning can directly reduce inference time and even training time when applied at initialization \citep{lee2018snip}. 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 \citep{Liu_2017_ICCV}, C-OBD and EigenDamage \citep{wang2019eigendamage}.
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 \citep{lin2019towards}, CCP \citep{peng2019collaborative}, FPGM \citep{he2019filter} and Variational Pruning \citep{zhao2019variational}.
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 \citep{he2018amc} 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 \citep{molchanov2019importance}, calculating the full second-order saliency objective is intractable for modern neural networks. Therefore, most saliency-based pruning methods such as OBD \citep[e.g.,][]{lecun1990optimal} or C-OBD \citep{wang2019eigendamage} 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:
\begin{itemize}
    \item
    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.
    \item
    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.
    
   
   
    
    \item
    We exploit the structure of the pruning masks found by our SOSP methods to remove architectural bottlenecks, which further improves the performance of the pruned networks. We diagnose layers with disproportionally low pruning ratios as architectural bottlenecks.
\end{itemize}


\section{SOSP: Second-order structured pruning}
\label{sec:methods}A neural network (NN) maps an input $x\in{\mathbb R}^d$ to an output $f_\theta(x)\in{\mathbb R}^D$, where $\theta\in{\mathbb R}^P$ are its $P$ parameters. NN training proceeds, after random initialization $\theta=\theta_0$ of the weights, by mini-batch stochastic gradient descent on the empirical loss ${\mathcal L}(\theta):=\frac{1}{N}\sum^N_{n=1}\ell\left(f_{\theta}(x_n),y_n\right)$, given the training dataset $\{(x_1,y_1),\dots,(x_N,y_N)\}$. In the classification case, $y\in\{1,\ldots,D\}$ is a discrete ground-truth label and $\ell(f_\theta(x),y):=-\log\sigma\left(f_\theta(x)\right)_{y}$ the cross-entropy loss, with $\sigma:{\mathbb R}^D\to{\mathbb R}^D$ the softmax-function. For regression, $y\in{\mathbb R}^D$ 
and $\ell(f_\theta(x),y)=\frac{1}{2}\left\|f_\theta(x)-y\right\|^2$ is the squared loss.



Structured pruning aims to remove weights or rather entire structures from a NN $f_\theta$ with parameters $\theta$. 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,\ldots,S$, which can potentially be pruned. We define the notation $\theta_{s}\in{\mathbb R}^P$ as the vector whose only nonzero components are those weights from $\theta$ that belong to structure $s$.\footnote{We require that each weight is assigned to at most one structure. In practice, we associate with each structure those weights that go \emph{into} the structure, rather than those that leave it.} Then, a \emph{pruning mask} is a set $M=\{s_1,\ldots,s_m\}$ of structures, and applying a mask $M$ to a NN $f_\theta$ means to consider the NN with parameter vector $\theta_{\setminus M}:=\theta-\sum_{s\in M}\theta_{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.


   
   







The basic idea behind both our pruning methods is to select the pruning mask $M$ so as to (approximately) minimize the \emph{joint} effect on the network loss
\begin{align*}
    \lambda(M) := \left| {\mathcal L}(\theta)-{\mathcal L}(\theta_{\setminus M})\right|
\end{align*}
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
\begin{align}\label{eq:second-order-approx-basic}
    \lambda_2(M) = \left|\sum_{s\in M}\theta_{s}^T\frac{d{\mathcal L}(\theta)}{d\theta}-\frac{1}{2}\!\sum_{s,s'\in M}\!\theta_{s}^T \frac{d^2{\mathcal L}(\theta)}{d\theta\,d\theta^T} \theta_{s'}\right|\!\!
\end{align}
collapses to single-structure contributions plus pairwise correlations.

The first-order terms $\lambda_1(s):=\theta_s\cdot d{\mathcal L}(\theta)/d\theta$ in (\ref{eq:second-order-approx-basic}) are efficient to evaluate by computing the gradient $d{\mathcal L}(\theta)/d\theta\in{\mathbb{R}}^P$ once and then a (sparse) dot product for every $s$. 
In contrast, the network Hessian $H(\theta):=d^2{\mathcal L}(\theta)/d\theta^2\in{\mathbb R}^{P\times P}$ in (\ref{eq:second-order-approx-basic}) 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).


   
   



\subsection{SOSP-I: Saliency from individual sensitivities}\label{sec:SOSP-I}
SOSP-I approximates each individual term $\theta_{s}^T H(\theta) \theta_{s'}$ in (\ref{eq:second-order-approx-basic}) efficiently, as we will show in Eq.\ (\ref{eq:H-approx}). We will therefore consider a modification of Eq.\ (\ref{eq:second-order-approx-basic}) which measures all sensitivities individually:
\begin{align}\label{eq:SOSP-I-objective}
    \lambda_2^I(M) = \sum_{s\in M}\left|\theta_{s}^T\frac{d{\mathcal L}(\theta)}{d\theta}\right|+\frac{1}{2}\!\!\sum_{s,s'\in M}\!\left|\theta_{s}^T H(\theta) \theta_{s'}\right|.
\end{align}
The absolute values prevent cancellations among the individual sensitivities $\lambda_1(s)$ and correlations $\theta_{s}^T H(\theta) \theta_{s'}$.
While objectives other than $\lambda_2^I$ are equally possible in the method, including $\lambda_2$ and variants with the absolute values not pulled in fully, we found $\lambda_2^I$ to empirically perform best overall.



Then, SOSP-I iteratively selects the structures to prune, based on the objective (\ref{eq:SOSP-I-objective}): Starting from an empty pruning mask $M=\{\}$, we iteratively add to $M$ the structure $s\notin M$ that minimizes the overall sensitivity $\lambda_2^I(M\cup\{s\})$. In practice, the algorithm pre-computes the matrix $Q\in{\mathbb R}^{S\times S}$,
\begin{align}\label{eq:Q-matrix}
    Q_{s,s'}:=\frac{1}{2}\left|\theta_{s}^T H(\theta) \theta_{s'}\right|+\left|\theta_{s}^T\frac{d{\mathcal L}(\theta)}{d\theta}\right|\cdot\delta_{s=s'},
\end{align}
and selects at each iteration a structure $s\notin M$ to prune by
\begin{align}
    &\argmin_{s\notin M}\lambda_2^I(M\cup\{s\})-\lambda_2^I(M)=\argmin_{s\notin M}\Big(Q_{s,s}+2\sum_{s'\in M}Q_{s,s'}\Big),\label{eq:SOSP-I-selection}
\end{align}
terminating at the desired pruning ratio.

To compute $Q$ efficiently, we show in App.\ \ref{app:approx-second-order-derivatives} that the Hessian terms can be approximated as
\begin{align}\label{eq:H-approx}
    \theta_{s}^T H(\theta) \theta_{s'}\approx\frac{1}{N'}\sum_{n=1}^{N'}\left(\phi(x_n)\theta_s\right)^T R_n \left(\phi(x_n)\theta_{s'}\right).
\end{align}
Herein, the NN gradient $\phi(x):=\nabla_\theta f_\theta(x)\in{\mathbb R}^{D\times P}$ forms the basis of the well-established Gauss-Newton approximation (see App.\ \ref{app:approx-second-order-derivatives} for more details) used for the Hessian, and the matrices $R_n\in{\mathbb R}^{D\times D}$ are diagonal plus a rank-1 contribution (App.\ \ref{app:approx-second-order-derivatives}). For further efficiency gains, the sum runs over a random subsample of size $N'<N$. In practice, one pre-computes all (sparse) products $\phi(x_n)\theta_s\in{\mathbb R}^D$ starting from the efficiently computable gradient $\phi(x_n)$, before aggregating a batch onto the terms $\theta_s^TH(\theta)\theta_{s'}$. Eq.\ (\ref{eq:H-approx}) also has an interpretation as output correlations between certain network modifications, without derivatives (App.\ \ref{sec:out-out-correlations}).





   
   
       
   
   


\subsection{SOSP-H: Saliency from Hessian-vector product}\label{sec:SOSP-H}

SOSP-H treats the second-order terms in (\ref{eq:second-order-approx-basic}) in a different way, motivated by the limit of large pruning ratios: At high pruning ratios, the sum $\sum_{s'\in M}\theta_{s'}$ in (\ref{eq:second-order-approx-basic}) can be approximated by $\sum_{s'=1}^S\theta_{s'}=:\theta_{struc}$ (this equals $\theta$ if every NN weight belongs to some structure $s$). The second-order term $\sum_{s,s'\in M}\theta_{s}^T H(\theta) \theta_{s'}\approx\big(\sum_{s\in M}\theta_{s}^T\big)\big(H(\theta)\theta_{struc}\big)$ thus becomes tractable since the Hessian-vector product $H(\theta)\theta_{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 (\ref{eq:second-order-approx-basic}) so as to arrive at the final objective $\lambda_2^H(M):=\sum_{s\in M}\lambda_2^H(s)$ with
\begin{align}\label{eq:SOSP-H-objective}
    \lambda_2^H(s):=\left|\theta_{s}^T\frac{d{\mathcal L}(\theta)}{d\theta}\right|+\frac{1}{2}\left|\theta_{s}^T\big(H(\theta) \theta_{struc}\big)\right|.
\end{align}
To minimize $\lambda_2^H(M)$, SOSP-H starts from an empty pruning mask $M=\{\}$ and successively adds to $M$ a structure $s\notin M$ with smallest $\lambda_2^H(s)$, until the desired pruning ratio is reached.


Unlike the Gauss-Newton approximation in SOSP-I, SOSP-H uses the \emph{exact} Hessian $H(\theta)$ 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.\ (\ref{eq:SOSP-H-objective}), contrary to (\ref{eq:SOSP-I-objective}). Both SOSP-H and SOSP-I reduce to the same first-order pruning method when neglecting the second order, i.e.\ setting $H(\theta):=0$; we compare to the resulting first-order method in Sec.\ \ref{sec:scalability} (see also App.\ \ref{app:sosp_first_second_comp}).



\subsection{Computational complexity}\label{sec:complexity
We detail here the computational complexities of our methods (for the experimental evaluation see Sec.\ \ref{sec:scalability-imagenet}). The approximation of $Q$ in (\ref{eq:Q-matrix}) requires complexity $O\left(N'D(F+P)\right)=O(N'DF)$ for computing all $\phi(x_n)\theta_s$, where $F\geq P$ denotes the cost of one forward pass through the network ($F\approx P$ for fully-connected NNs), plus $O(N'DS^2)$ for the sum in (\ref{eq:H-approx}).
This is tractable for modern NNs, while including the exact $H(\theta)$ would have complexity at least $O(N'DSF)$.
Once $Q$ has been computed, the selection procedure based on (\ref{eq:SOSP-I-selection}) has overall complexity $O(S^3)$,
which is feasible for most modern convolutional NNs (Sec.\ \ref{sec:scalability-imagenet}).
The total complexity of the SOSP-I method is thus
\begin{align}\label{eq:saling_sosp_i}
    O(N'DF)+ O(N'DS^2)+ O(S^3).
\end{align}

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.\ (\ref{eq:SOSP-H-objective}).
Together with the sorting of the saliency values $\lambda_2^H(s)$, SOSP-H has thus the same low overall complexity as a first-order method, namely
\begin{align}\label{eq:saling_sosp_h}
    O(N'DF)+ O(S\log(S)).
\end{align}
Due to its weak dependency on $S$, in practice,
SOSP-H efficiently scales to large modern networks (see Sec.\ \ref{sec:scalability-imagenet}), and may even be used for \emph{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. 



\section{Results}\label{sec:experiments}

To evaluate our methods, we train and prune VGGs \citep{simonyan2014very}, ResNets \citep{he2016deep}, PlainNet \citep{he2016deep}, and DenseNets \citep{huang2017densely} on the Cifar10/100 \citep{krizhevsky2009learning} and ImageNet \citep{deng2009imagenet} 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.\ \ref{sec:SOSP-I}).
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. 

\input{table_global}
\input{fig_layerwise}



\subsection{Comparison on medium-sized datasets}\label{sec:scalability}


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.\ \ref{sec:add_exp}. Our count of the network parameters and MACs is based on the actual pruned network architecture (cf.\ App.\ \ref{app:counting-parameters-macs}), even though our saliency measure associates with each structure only the weights \emph{into} this structure (see Sec.\ \ref{sec:methods}).


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.\ (\ref{eq:Q-matrix}) or (\ref{eq:SOSP-H-objective})) to our second-order SOSP objectives. The results (see App.\ \ref{app:sosp_first_second_comp}) 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 $\sum_{s'}Q_{s,s'}$ in Eq.\ (\ref{eq:SOSP-I-selection}) are dropped. The results (see App.\ \ref{app:sosp_corr_comp}) 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 \citep[NN Slimming;][]{Liu_2017_ICCV} as well as EigenDamage and C-OBD \citep{wang2019eigendamage}, 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 \citep{hassibi1993optimal}, 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.\ \ref{tab:one_pass_vgg_resnet_high} and for moderate pruning ratios in App.\ \ref{app:medium_global_pruning}.
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 $L_1$-regularization 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 Cifar100 (see Tab.\ \ref{tab:one_pass_vgg_resnet_medium}).
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 $L_1$-modification of network pretraining.

Next, we compare SOSP-H to AMC \citep{he2018amc} 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 \citep{he2016deep} and rank the filters in each layer according to their 2-norm (see also \cite{han2015learning}). The results in App.\ \ref{app:amc_exp} 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 \cite{he2019filter}, GAL \citep{lin2019towards}, CCP \citep{peng2019collaborative}, Variational Pruning \citep[VP;][]{zhao2019variational} and HRank \citep{lin2020hrank}.
For ResNet-56, our SOSP methods
outperform all other methods across all pruning ratios (see Fig.\ \ref{fig:layerwise_pruning_comp}a and b).
For DenseNet-40, SOSP achieves better accuracies when compared over parameters (Fig.\ \ref{fig:layerwise_pruning_comp}c) and is on par with the best other methods over MACs (Fig.\ \ref{fig:layerwise_pruning_comp}d). The reason for this discrepancy is probably that the SOSP objective is agnostic to the number of MACs (image size) in each individual layer.

\input{fig_imagenet}
\subsection{Scalability and application to large-scale datasets}\label{sec:scalability-imagenet}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(S^3)$ (see Sec. \ref{sec:complexity}), 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.\ \ref{fig:scaling_I_vs_H} and App.\ \ref{app:runtime_comp}.
Since SOSP-I becomes impractical for large-scale networks like other second-order methods \citep{molchanov2019importance,wang2019eigendamage}, 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.\ \ref{imagenet} or Suppl.\ Fig.\ \ref{fig:imagenet_plot_comp}.
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\times1$-convolutions. Since these $1\times1$-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.\ \ref{imagenet}).

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.\ \ref{app:counting-parameters-macs}).
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 \citep{molchanov2019importance}, 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.\ \ref{sec:scalability} and esp.\ App.\ \ref{app:sosp_first_second_comp}), where we show that including second-order information leads to improved accuracies.






\subsection{Identifying \& Removing Architectural Bottlenecks}
\label{sec:expand_prune}

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.\ \ref{fig:doubletrain_init}(d,g,e,h) and Fig.\ \ref{fig:expand_prune} (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; removing 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.
\input{fig_bottleneck}
To utilize this insight we devise a procedure that we call \emph{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, whichhas been proven to work well empirically.
Finally, we randomly initialize, train, prune, and fine-tune the expanded network (for a schematic, see Fig.\ \ref{fig:expand_prune}a).
As a naive baseline that we call the \emph{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.\ \ref{fig:expand_prune}).

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 \emph{width multipliers} in Fig.\ \ref{fig:expand_prune}(c,f) selected on the basis of the pruning masks shown in Suppl.\ Fig.\ \ref{fig:doubletrain_init}(d,g)).
Note that a more fine-grained removal of bottlenecks in ResNet-56, e.g.\ on layer level, is not possible without changing the overall ResNet architecture.
In summary, a selective removal of bottlenecks results in smaller network models with higher accuracy than pruning the vanilla network or unselectively increasing the network size (compare expand-pruning and widen-pruning in Fig.\ \ref{fig:expand_prune}(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.\ \ref{app:init_vs_retrain}), unlike e.g.\ NN Slimming, allowing for a similar expand scheme directly at initialization (see App.\ \ref{app:expand_init_comp}).









\section{Discussion}\label{sec: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-sized networks.
Further, we showed that the pruning masks found by SOSP can be used to systematically detect and remove 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 \citep{wang2019eigendamage} is a structured generalization of the original unstructured OBD algorithm \citep{lecun1990optimal}.
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 \emph{global} correlations consistently improves the performance, especially for large pruning ratios (Tab.\ \ref{tab:one_pass_vgg_resnet_high}).
This is in line with the results of our ablation study in App.\ \ref{app:sosp_corr_comp} (see also Sec.\ \ref{sec:scalability}).
The objective of EigenDamage \citep{wang2019eigendamage} 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 \citep{Liu_2017_ICCV} is more heuristic than SOSP and is easy to implement.
However, networks need to be pretrained with $L_1$-regularization on the batch-normalization parameters, otherwise the performance is severely harmed (Tab.\ \ref{tab:one_pass_vgg_resnet_high} and Supp.\ Tab.\ \ref{tab:one_pass_vgg_resnet_medium}).
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 \citet{zhuang2020neuron} 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 \citep{theis2018faster,liu2021group} or use an approximation similar to Gauss-Newton, which we used for SOSP-I \citep[e.g., the Fisher information matrix in][]{molchanov2019importance}. 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 \citet{peng2019collaborative}.
While both works consider second-order correlations between structures, theirs is based on a ranking scheme different from our absolute sensitivities in $\lambda_2^I$ 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, \cite{su2020sanity} 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 \cite{su2020sanity}, 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.\ \ref{fig:doubletrain_init}).
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 \citep{he2018amc} 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 \citep{liu2020autocompress}, EagleEye \citep{li2020eagleeye}, DMCP \citep{guo2020dmcp} and CafeNet \citep{su2021locally}. 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 remove 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 \citep{van2020single,liu2021group}. Further, introducing additional hyperparameters for each layer optimized to reduce the number of MACs as done by \cite{chin2020towards} could potentially lead to further improvements, but would also significantly increase the complexity due to the need of hyperparameter optimization. \citet{liu2021group} 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 \citep{lee2018snip,wang2019picking,tanaka2020pruning} and structured \citep{van2020single,hayou2021robust} 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.\ \ref{app:prune_init}) that our SOSP method at initialization can, after comparable training time, achieve accuracies similar to pruning after training.


In accordance with \cite{elsken_2019_nas}, our results suggest that pruning can be used to optimize the architectural hyperparameters of established networks \citep{liu2018rethinking} or super-graphs \citep{noy_2020_nas_pruning}; see also App.\ \ref{app:shuffle_exp}.
We envision our second-order sensitivity analysis to be a valuable tool to identify and remove 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.







