# Compressing Neural Networks: Towards Determining the Optimal Layer-wise
Decomposition

Lucas Liebenwein
MIT CSAIL
<EMAIL_ADDRESS>
&Alaa Maalouf∗
University of Haifa
<EMAIL_ADDRESS>
Oren Gal
University of Haifa
<EMAIL_ADDRESS>&Dan Feldman
University of Haifa
<EMAIL_ADDRESS>
&Daniela Rus
MIT CSAIL
<EMAIL_ADDRESS>
denotes authors with equal contributions. Code:
https://github.com/lucaslie/torchprune

###### Abstract

We present a novel global compression framework for deep neural networks that
automatically analyzes each layer to identify the optimal per-layer
compression ratio, while simultaneously achieving the desired overall
compression. Our algorithm hinges on the idea of compressing each
convolutional (or fully-connected) layer by slicing its channels into multiple
groups and decomposing each group via low-rank decomposition. At the core of
our algorithm is the derivation of layer-wise error bounds from the
Eckart–Young–Mirsky theorem. We then leverage these bounds to frame the
compression problem as an optimization problem where we wish to minimize the
maximum compression error across layers and propose an efficient algorithm
towards a solution. Our experiments indicate that our method outperforms
existing low-rank compression approaches across a wide range of networks and
data sets. We believe that our results open up new avenues for future research
into the global performance-size trade-offs of modern neural networks.

##  1 Introduction

Figure 1: ALDS, _Automatic Layer-wise Decomposition Selector_ , can compress
up to 60% of parameters on a ResNet18 (ImageNet), 3x more compared to
baselines. Detailed results are described in Section 3.

Neural network compression entails taking an existing model and reducing its
computational and memory footprint in order to enable the deployment of large-
scale networks in resource-constrained environments. Beyond inference time
efficiency, compression can yield novel insights into the design (Liu et al.,
2019b), training (Liebenwein et al., 2021a, b), and theoretical properties
(Arora et al., 2018) of neural networks.

Among existing compression techniques – which include quantization (Wu et al.,
2016), distillation (Hinton et al., 2015), and pruning (Han et al., 2015) –
_low-rank compression_ aims at decomposing a layer’s weight tensor into a
tuple of smaller low-rank tensors. Such compression techniques may build upon
the rich literature on low-rank decomposition and its numerous applications
outside deep learning such as dimensionality reduction (Laparra et al., 2015)
or spectral clustering (Peng et al., 2015). Moreover, low-rank compression can
be readily implemented in any machine learning framework by replacing the
existing layer with a set of smaller layers without the need for, e.g., sparse
linear algebra support.

Within deep learning, we encounter two related, yet distinct challenges when
applying low-rank compression. On the one hand, each layer should be
efficiently decomposed (the “local step”) and, on the other hand, we need to
balance the amount of compression in each layer in order to achieve a desired
overall compression ratio with minimal loss in the predictive power of the
network (the “global step”). While the “local step“, i.e., designing the most
efficient layer-wise decomposition method, has traditionally received lots of
attention (Denton et al., 2014; Kim et al., 2015b; Lebedev et al., 2015;
Garipov et al., 2016; Novikov et al., 2015; Jaderberg et al., 2014), the
“global step” has only recently been the focus of attention in research, e.g.,
see the recent works of Idelbayev and Carreira-Perpinán (2020); Alvarez and
Salzmann (2017); Xu et al. (2020).

In this paper, we set out to design a framework that simultaneously accounts
for both the local and global step. Our proposed solution, termed _Automatic
Layer-wise Decomposition Selector_ (ALDS), addresses this challenge by
iteratively optimizing for each layer’s decomposition method (local step) and
the low-rank compression itself while accounting for the maximum error
incurred across layers (global step). In Figure 1, we show how ALDS
outperforms existing approaches on the common ResNet18 (ImageNet) benchmark
($60\%$ compression compared to ${\sim}20\%$ for baselines).

Figure 2: ALDS Overview. The framework consists of a global and local step,
see Section 2.

##### Efficient layer-wise decomposition.

Our framework relies on a straightforward SVD-based decomposition of each
layer. Inspired by Denton et al. (2014); Idelbayev and Carreira-Perpinán
(2020); Jaderberg et al. (2014) and others, we decompose each layer by first
folding the weight tensor into a matrix before applying SVD and encoding the
resulting pair of matrices as two separate layers.

##### Enhanced decomposition via multiple subsets.

A natural generalization of low-rank decomposition methods entails splitting
the matrix into multiple subsets (subspaces) before compressing each subset
individually. In the context of deep learning, this was investigated before
for individual layers (Denton et al., 2014), including embedding layers
(Maalouf et al., 2021; Chen et al., 2018). We take this idea further and
incorporate it into our layer-wise decomposition method as additional
hyperparameter in terms of the number of subsets. Thus, our local step, i.e.,
the layer-wise decomposition, constitutes of choosing the number of subsets
($k^{\ell}$) for each layer and the rank ($j^{\ell}$).

##### Towards a global solution for low-rank compression.

We can describe the optimal solution for low-rank compression as the set of
hyperparameters (number of subspaces $k^{\ell}$ and rank $j^{\ell}$ for each
layer in our case) that minimizes the drop in accuracy of the compressed
network. While finding the globally optimal solution is NP-complete, we
propose ALDS as an efficiently solvable alternative that enables us to search
for a locally optimal solution in terms of the maximum relative error incurred
across layers. To this end, we derive spectral norm bounds based on the
Eckhart-Young-Mirsky Theorem for our layer-wise decomposition method to
describe the trade-off between the layer compression and the incurred error.
Leveraging our bounds we can then efficiently optimize over the set of
possible per-layer decompositions. An overview of ALDS is shown in Figure 2.

##  2 Method

In this section, we introduce our compression framework consisting of a layer-
wise decomposition method (Section 2.1), a global selection mechanism to
simultaneously compress all layers of a network (Section 2.2), and an
optimization procedure (ALDS) to solve the selection problem (Section 2.3).

###  2.1 Local Layer Compression

We detail our low-rank compression scheme for convolutional layers below and
note that it readily applies to fully-connected layers as well as a special
case of convolutions with a $1\times 1$ kernel.

##### Compressing convolutions via SVD.

Given a convolutional layer of $f$ filters, $c$ channels, and a
$\kappa_{1}\times\kappa_{2}$ kernel we denote the corresponding weight tensor
by $\mathbf{\mathcal{W}}\in\mathbb{R}^{f\times
c\times\kappa_{1}\times\kappa_{2}}$. Following Denton et al. (2014); Idelbayev
and Carreira-Perpinán (2020); Wen et al. (2017) and others, we can then
interpret the layer as a linear layer of shape $f\times c\kappa_{1}\kappa_{2}$
and the corresponding rank $j$-approximation as two subsequent linear layers
of shape $f\times j$ and $j\times c\kappa_{1}\kappa_{2}$. Mapped back to
convolutions, this corresponds to a $j\times
c\times\kappa_{1}\times\kappa_{2}$ convolution followed by a $f\times j\times
1\times 1$ convolution.

##### Multiple subspaces.

Following the intuition outlined in Section 1 we propose to cluster the
columns of the layer’s weight matrix into $k\geq 2$ separate subspaces before
applying SVD to each subset. To this end, we may consider any clustering
method, such as k-means or projective clustering (Maalouf et al., 2021; Chen
et al., 2018). However, such methods require expensive approximation
algorithms which would limit our ability to incorporate them into an
optimization-based compression framework as outlined in Section 2.2. In
addition, arbitrary clustering may require re-shuffling the input tensors
which could lead to significant slow-downs during inference. We instead opted
for a simple clustering method, namely _channel slicing_ , where we simply
divide the $c$ input channels of the layer into $k$ subsets each containing at
most $\lceil c/k\rceil$ consecutive input channels. Unlike other methods,
channel slicing is efficiently implementable, e.g., as grouped convolutions in
PyTorch (Paszke et al., 2017) and ensures practical speed-ups subsequent to
compressing the network.

##### Overview of per-layer decomposition.

In summary, for given integers $j,k\geq 1$ and a $4$D tensor
$\mathbf{\mathcal{W}}\in\mathbb{R}^{f\times
c\times\kappa_{1}\times\kappa_{2}}$ representing a convolution the per-layer
compression method proceeds as follows:

  1. 1.

Partition the channels of the convolutional layer into $k$ subsets, where each
subset has at most $\lceil c/k\rceil$ consecutive channels, resulting in $k$
convolutional tensors $\\{\mathbf{\mathcal{W}}_{i}\\}_{i=1}^{k}$ where
$\mathbf{\mathcal{W}}_{i}\in\mathbb{R}^{f\times
c_{i}\times\kappa_{1}\times\kappa_{2}}$, and $\sum_{i=1}^{k}c_{i}=c$.

  2. 2.

Decompose each tensor $\mathbf{\mathcal{W}}_{i}$, $i\in[k]$, by building the
corresponding weight matrix $W_{i}\in\mathbb{R}^{f\times
c_{i}\kappa_{1}\kappa_{2}}$, c.f. Figure 3, computing its $j$-rank
approximation, and factoring it into a pair of smaller matrices $U_{i}$ of $f$
rows and $j$ columns and $V_{i}$ of $j$ rows and $c_{i}\kappa_{1}\kappa_{2}$
columns.

  3. 3.

Replace the original layer in the network by $2$ layers. The first consists of
$k$ parallel convolutions, where the $i^{\text{th}}$ parallel layer,
$i\in[k]$, is described by the tensor
$\mathbf{\mathcal{V}}_{i}\in\mathbb{R}^{j\times
c_{i}\times\kappa_{1}\times\kappa_{2}}$ which can be constructed from the
matrix $V_{i}$ ($j$ filters, $c_{i}$ channels, $\kappa_{1}\times\kappa_{2}$
kernel). The second layer is constructed by reshaping each matrix $U_{i}$,
$i\in[k]$, to obtain the tensor
$\mathbf{\mathcal{U}}_{i}\in\mathbb{R}^{f\times j\times 1\times 1}$, and then
channel stacking all $k$ tensors
$\mathbf{\mathcal{U}}_{1},\cdots,\mathbf{\mathcal{U}}_{k}$ to get a single
tensor of shape $f\times kj\times 1\times 1$.

The decomposed layer is depicted in Figure 3. The resulting layer pair has
$jc\kappa_{1}\kappa_{2}$ and $jfk$ parameters, respectively, which implies a
parameter reduction from $fc\kappa_{1}\kappa_{2}$ to
$j(fk+c\kappa_{1}\kappa_{2})$.

Figure 3: Left: 2D convolution. right: decomposition used for ALDS. For a
$f\times c\times\kappa_{1}\times\kappa_{2}$ convolution with $f$ filters, $c$
channels, and $\kappa_{1}\times\kappa_{2}$ kernel, our per-layer decomposition
consists: (1) $k$ parallel
$j\times\nicefrac{{c}}{{k}}\times\kappa_{1}\times\kappa_{2}$ convolutions; (2)
a single $f\times kj\times 1\times 1$ convolution applied on the first layer’s
(stacked) output.

###  2.2 Global Network Compression

In the previous section, we introduced our layer compression scheme. We note
that in practice we usually want to compress an entire network consisting of
$L$ layers up to a pre-specified relative reduction in parameters
(“compression ratio” or $\mathbf{CR}$). However, it is generally unclear how
much each layer $\ell\in[L]$ should be compressed in order to achieve the
desired $\mathbf{CR}$ while incurring a minimal increase in loss.
Unfortunately, this optimization problem is NP-complete as we would have to
check every combination of layer compression resulting in the desired
$\mathbf{CR}$ in order to optimally compress each layer. On the other hand,
simple heuristics, e.g., constant per-layer compression ratios, may lead to
sub-optimal results, see Section 3. To this end, we propose an efficiently
solvable global compression framework based on minimizing the maximum relative
error incurred across layers. We describe each component of our optimization
procedure in greater detail below.

##### The layer-wise relative error as proxy for the overall loss.

Since the true cost (the additional loss incurred after compression) would
result in an NP-complete problem, we replace the true cost by a more efficient
proxy. Specifically, we consider the maximum relative error
$\varepsilon\coloneqq\max_{\ell\in[L]}\varepsilon^{\ell}$ across layers, where
$\varepsilon^{\ell}$ denotes the theoretical maximum relative error in the
$\ell^{\text{th}}$ layer as described in Theorem 1 below. We choose to
minimize this particular cost because: (i) minimizing the maximum relative
error ensures that no layer incurs an unreasonably large error that might
otherwise get propagated or amplified; (ii) relying on a relative instead of
an absolute error notion is preferred as scaling between layers may
arbitrarily change, e.g., due to batch normalization, and thus the absolute
scale of layer errors may not be indicative of the increase in loss; and (iii)
the per-layer relative error has been shown to be intrinsically linked to the
theoretical compression error, e.g., see the works of Arora et al. (2018) and
Baykal et al. (2019a) thus representing a natural proxy for the cost.

##### Definition of per-layer relative error.

Let $\mathbf{\mathcal{W}}^{\ell}\in\mathbb{R}^{f^{\ell}\times
c^{\ell}\times\kappa^{\ell}_{1}\times\kappa^{\ell}_{2}}$ and
$W^{\ell}\in\mathbb{R}^{f^{\ell}\times
c^{\ell}\kappa_{1}^{\ell}\kappa_{2}^{\ell}}$ denote the weight tensor and
corresponding folded matrix of layer $\ell$, respectively. The per-layer
relative error $\varepsilon^{\ell}$ is hereby defined as the relative
difference in the operator norm between the matrix $\hat{{{W}}}^{\ell}$ (that
corresponds to the compressed weight tensor
$\hat{\mathbf{\mathcal{W}}}^{\ell}$) and the original weight matrix $W^{\ell}$
in layer $\ell$, i.e,.

$\varepsilon^{\ell}\coloneqq{\|\hat{{{W}}}^{\ell}-W^{\ell}\|}/{\|W^{\ell}\|}.$
(1)

Note that while in practice our method decomposes the original layer into a
set of separate layers (see Section 2.1), for the purpose of deriving the
resulting error we re-compose the compressed layers into the overall matrix
operator $\hat{{{W}}}^{\ell}$, i.e.,
$\hat{{{W}}}^{\ell}=[U_{1}^{\ell}V_{1}^{\ell}\cdots
U_{k^{\ell}}^{\ell}V_{k^{\ell}}^{\ell}]$, where $U_{i}^{\ell}V_{i}^{\ell}$ is
the factorization of the $i$th cluster (set of columns) in the $\ell$th layer,
for every $\ell\in[L]$ and $i\in[k^{\ell}]$, see supplementary material for
more details. We note that the operator norm $\|\cdot\|$ for a convolutional
layer thus signifies the maximum relative error incurred for an individual
output patch (“pixel”) across all output channels.

##### Derivation of relative error bounds.

We now derive an error bound that enables us to describe the per-layer
relative error in terms of the compression hyperparameters $j^{\ell}$ and
$k^{\ell}$, i.e., $\varepsilon^{\ell}=\varepsilon^{\ell}(k^{\ell},j^{\ell}).$
This will prove useful later on as we have to repeatedly query the relative
error in our optimization procedure. The error bound is described in the
following.

######  Theorem 1.

Given a layer matrix $W^{\ell}$ and the corresponding low-rank approximation
$\hat{{{W}}}^{\ell}$, the relative error
$\varepsilon^{\ell}\coloneqq{\|\hat{{{W}}}^{\ell}-W^{\ell}\|}/{\|W^{\ell}\|}$
is bounded by

$\displaystyle\varepsilon^{\ell}\leq\nicefrac{{\sqrt{k}}}{{\alpha_{1}}}\cdot\max_{i\in[k]}{\alpha_{i,j+1}},$
(2)

where $\alpha_{i,j+1}$ is the $j+1$ largest singular value of the matrix
$W^{\ell}_{i}$, for every $i\in[k]$, and $\alpha_{1}=\|W^{\ell}\|$ is the
largest singular value of $W^{\ell}$.

###### Proof.

First, we recall the matrices $W^{\ell}_{1},\cdots,W^{\ell}_{k}$ and we denote
the SVD factorization for each of them by:
$W^{\ell}_{i}=\tilde{U}^{\ell}_{i}\tilde{\Sigma}^{\ell}_{i}{{{\tilde{V}}_{i}}^{\ell}}$.
Now, observe that for every $i\in[k]$, the matrix $\hat{{{W}}}^{\ell}_{i}$ is
the $j$-rank approximation of $W^{\ell}_{i}$. Hence, the SVD factorization of
$\hat{{{W}}}^{\ell}_{i}$ can be writen as
$\hat{{{W}}}^{\ell}_{i}=\tilde{U}^{\ell}_{i}\hat{\Sigma}^{\ell}_{i}{{{\tilde{V}}_{i}}^{\ell^{T}}}$,
where $\hat{\Sigma}^{\ell}_{i}\in\mathbb{R}^{f\times d}$ is a diagonal matrix
such that its first $j$-diagonal entries are equal to the first $j$-entries on
the diagonal of $\tilde{\Sigma}^{\ell}_{i}$, and the rest are zeros. Hence,

$\begin{split}W^{\ell}-\hat{{{W}}}^{\ell}&=[W^{\ell}_{1}-\hat{{{W}}}^{\ell}_{1},\cdots,W^{\ell}_{k}-\hat{{{W}}}^{\ell}_{k}]=[\tilde{U}^{\ell}_{1}(\tilde{\Sigma}^{\ell}_{1}-\hat{\Sigma}^{\ell}_{1})\tilde{V}^{\ell}_{1},\cdots,\tilde{U}^{\ell}_{k}(\tilde{\Sigma}^{\ell}_{k}-\hat{\Sigma}^{\ell}_{k})\tilde{V}^{\ell}_{k}]\\\
&=[\tilde{U^{\ell}_{1}}\cdots\tilde{U}^{\ell}_{k}]\operatorname*{diag}\left((\tilde{\Sigma}^{\ell}_{1}-\hat{\Sigma}^{\ell}_{1})\tilde{V}^{\ell}_{1},\ldots,(\tilde{\Sigma}^{\ell}_{k}-\hat{\Sigma}^{\ell}_{k})\tilde{V}^{\ell}_{k}\right).\end{split}$
(3)

By (3) and by the triangle inequality, we have that

$\displaystyle\left\lVert
W^{\ell}-\hat{{{W}}}^{\ell}\right\rVert\leq\left\lVert{\left[\tilde{U^{\ell}_{1}}\cdots\tilde{U}^{\ell}_{k}\right]}\right\rVert\left\lVert\operatorname*{diag}\left((\tilde{\Sigma}^{\ell}_{1}-\hat{\Sigma}^{\ell}_{1})\tilde{V}^{\ell}_{1},\ldots,(\tilde{\Sigma}^{\ell}_{k}-\hat{\Sigma}^{\ell}_{k})\tilde{V}^{\ell}_{k}\right)\right\rVert.$
(4)

Now, we observe that

$\displaystyle\left\lVert{\left[\tilde{U^{\ell}_{1}}\cdots\tilde{U}^{\ell}_{k}\right]}\right\rVert^{2}=\left\lVert{\left[\tilde{U^{\ell}_{1}}\cdots\tilde{U}^{\ell}_{k}\right]}{\left[\tilde{U^{\ell}_{1}}\cdots\tilde{U}^{\ell}_{k}\right]^{T}}\right\rVert=\left\lVert\operatorname*{diag}(k,\ldots,k)\right\rVert=k.$
(5)

Finally, we show that

$\displaystyle\left\lVert\operatorname*{diag}\left((\tilde{\Sigma}^{\ell}_{1}-\hat{\Sigma}^{\ell}_{1})\tilde{V}^{\ell}_{1},\ldots,(\tilde{\Sigma}^{\ell}_{k}-\hat{\Sigma}^{\ell}_{k})\tilde{V}^{\ell}_{k}\right)\right\rVert$
$\displaystyle=\max_{i\in[k]}\left\lVert(\tilde{\Sigma}^{\ell}_{i}-\hat{\Sigma}^{\ell}_{i})\tilde{V}^{\ell}_{i}\right\rVert$
(6)
$\displaystyle=\max_{i\in[k]}\left\lVert(\tilde{\Sigma}^{\ell}_{i}-\hat{\Sigma}^{\ell}_{i})\right\rVert=\max_{i\in[k]}\alpha_{i,j+1},$
(7)

where the second equality holds since the columns of $V$ are orthogonal and
the last equality holds according to the Eckhart-Young-Mirsky Theorem (Theorem
2.4.8 of Golub and Van Loan (2013)). Plugging (7) and (5) into (4) concludes
the proof. ∎

##### Resulting network size.

Let $\theta=\\{\mathbf{\mathcal{W}}^{\ell}\\}_{\ell=1}^{L}$ denote the set of
weights for the $L$ layers and note that the number of parameters in layer
$\ell$ is given by
$|\mathbf{\mathcal{W}}^{\ell}|=f^{\ell}c^{\ell}\kappa^{\ell}_{1}\kappa^{\ell}_{2}$
and $|{\theta}|=\sum_{\ell\in[L]}|\mathbf{\mathcal{W}}^{\ell}|$. Moreover,
note that
$|{\hat{\mathbf{\mathcal{W}}}^{\ell}}|=j^{\ell}(k^{\ell}f^{\ell}+c^{\ell}\kappa^{\ell}_{1}\kappa^{\ell}_{2})$
if decomposed,
$\hat{\theta}=\\{\hat{\mathbf{\mathcal{W}}}^{\ell}\\}_{\ell=1}^{L}$, and
$|\hat{\theta}|=\sum_{\ell\in[L]}|\hat{\mathbf{\mathcal{W}}}^{\ell}|$. The
overall compression ratio is thus given by
$1-\nicefrac{{|\hat{\theta}|}}{{|\theta|}}$ where we neglected other
parameters for ease of exposition. Observe that the layer budget
$|\hat{\mathbf{\mathcal{W}}}^{\ell}|$ is fully determined by
$k^{\ell},j^{\ell}$ just like the error bound.

Algorithm 1 ALDS($\theta$, $\mathbf{CR}$, $n_{\text{seed}}$)

Input: $\theta$: network parameters; $\mathbf{CR}$: overall compression ratio;
$n_{\text{seed}}$: number of random seeds to initialize
Output: $k^{1},\ldots,k^{L}$: number of subspaces for each layer;
$j_{1},\ldots,j^{L}$: desired rank per subspace for each layer

1: for $i\in[n_{\text{seed}}]$ do

2: $k^{1},\ldots,k^{L}\leftarrow\textsc{RandomInit()}$

3: while not converged do

4:
$j^{1},\ldots,j^{L}\leftarrow\textsc{OptimalRanks}(\mathbf{CR},k^{1},\ldots,k^{L})$
$\quad\triangleright$ Global step: choose s.t.
$\varepsilon^{1}=\ldots=\varepsilon^{L}$

5: for $\ell\in[L]$ do

6: $b^{\ell}\leftarrow
j^{\ell}(k^{\ell}f^{\ell}+c^{\ell}\kappa_{1}^{\ell}\kappa_{2}^{\ell})$
$\quad\triangleright$ resulting layer budget

7: $k^{\ell}\leftarrow\textsc{OptimalSubspaces}(b^{\ell})$
$\quad\triangleright$ Local step: minimize error bound for a given layer
budget

8: end for

9: end while

10:
$\varepsilon_{i}=\textsc{RecordError}(k^{1},\ldots,k^{L},j^{1},\ldots,j^{L})$

11: end for

12: return $k^{1},\ldots,k^{L},j^{1},\ldots,j^{L}$ from
$i_{\text{best}}=\operatorname*{\arg\\!\min}_{i}\varepsilon_{i}$

##### Global Network Compression.

Putting everything together we obtain the following formulation for the
optimal per-layer budget:

$\displaystyle\varepsilon_{opt}=$
$\displaystyle\min_{\begin{subarray}{c}\\{j^{\ell},k^{\ell}\\}_{\ell=1}^{L}\end{subarray}}$
$\displaystyle\max_{\ell\in[L]}\varepsilon^{\ell}(k^{\ell},j^{\ell})$ (8)
subject to $\displaystyle
1-\nicefrac{{|\hat{\theta}(k^{1},j^{1},\ldots,k^{L},j^{L})|}}{{|\theta|}}\leq\mathbf{CR},$

where $\mathbf{CR}$ denotes the desired overall compression ratio. Thus
optimally allocating a per-layer budget entails finding the optimal number of
subspaces $k^{\ell}$ and ranks $j^{\ell}$ for each layer constrained by the
desired overall compression ratio $\mathbf{CR}$.

###  2.3 Automatic Layer-wise Decomposition Selector (ALDS)

We propose to solve (8) by iteratively optimizing $k^{1},\ldots,k^{L}$ and
$j^{1},\ldots,j^{L}$ until convergence akin of an EM-like algorithm as shown
in Algorithm 1 and Figure 2.

Specifically, for a given set of weights $\theta$ and desired compression
ratio $\mathbf{CR}$ we first randomly initialize the number of subspaces
$k^{1},\ldots,k^{L}$ for each layer (Line 2). Based on given values for each
$k^{\ell}$ we then solve for the optimal ranks $j^{1},\ldots,j^{L}$ such that
the overall compression ratio is satisfied (Line 4). Note that the maximum
error $\varepsilon$ is minimized if all errors are equal. Thus solving for the
ranks in Line 4 entails guessing a value for $\varepsilon$, computing the
resulting network size, and repeating the process until the desired
$\mathbf{CR}$ is satisfied, e.g. via binary search.

Subsequently, we re-assign the number of subspaces $k^{\ell}$ for each layer
by iterating through the finite set of possible values for $k^{\ell}$ (Line 7)
and choosing the one that minimizes the relative error for the current layer
budget $b^{\ell}$ (computed in Line 6). Note that we can efficiently
approximate the relative error by leveraging Theorem 1. We then iteratively
repeat both steps until convergence (Lines 3-8). To improve the quality of the
local optimum we initialize the procedure with multiple random seeds (Lines
1-11) and pick the allocation with the lowest error (Line 12).

We note that we make repeated calls to our decomposition subroutine (i.e. SVD;
Lines 4, 7) highlighting the necessity for it to be efficient and cheap to
evaluate. Moreover, we can further reduce the computational complexity by
leveraging Theorem 1 as mentioned above.

Additional details pertaining to ALDS are provided in the supplementary
material.

##### Extensions.

Here, we use SVD with multiple subspaces as per-layer compression method.
However, we note that ALDS can be readily extended to any desired _set_ of
low-rank compression techniques. Specifically, we can replace the local step
of Line 7 by a search over different methods, e.g., Tucker decomposition, PCA,
or other SVD compression schemes, and return the best method for a given
budget. In general, we may combine ALDS with any low-rank compression as long
as we can efficiently evaluate the per-layer error of the compression scheme.
In the supplementary material, we discuss some preliminary results that
highlight the promising performance of such extensions.

##  3 Experiments

(a) DenseNet22

(b) VGG16

(c) WRN16-8

Figure 4: One-shot compress+retrain experiments on CIFAR10 with baseline
comparisons.

##### Networks and datasets.

We study various standard network architectures and data sets. Particularly,
we test our compression framework on ResNet20 (He et al., 2016), DenseNet22
(Huang et al., 2017), WRN16-8 (Zagoruyko and Komodakis, 2016), and VGG16
(Simonyan and Zisserman, 2015) on CIFAR10 (Torralba et al., 2008); ResNet18
(He et al., 2016), AlexNet (Krizhevsky et al., 2012), and MobileNetV2 (Sandler
et al., 2018) on ImageNet (Russakovsky et al., 2015); and on Deeplab-V3 (Chen
et al., 2017) with a ResNet50 backbone on Pascal VOC segmentation data
(Everingham et al., 2015).

##### Baselines.

We compare ALDS to a diverse set of low-rank compression techniques.
Specifically, we have implemented PCA (Zhang et al., 2015b), SVD with energy-
based layer allocation (SVD-Energy) following Alvarez and Salzmann (2017); Wen
et al. (2017), and simple SVD with constant per-layer compression (Denton et
al., 2014). Additionally, we also implemented the recent learned rank
selection mechanism (L-Rank) of Idelbayev and Carreira-Perpinán (2020).
Finally, we implemented two recent filter pruning methods, i.e., FT of Li et
al. (2016) and PFP of Liebenwein et al. (2020), as alternative compression
techniques for densely compressed networks. Additional comparisons on ImageNet
are provided in Section 3.2.

##### Retraining.

For our experiments, we study one-shot and iterative learning rate rewinding
inspired by Renda et al. (2020) for various amounts of retraining. In
particular, we consider the following unified compress-retrain pipeline across
all methods:

  1. 1.

Train for $e$ epochs according to the standard training schedule for the
respective network.

  2. 2.

Compress the network according to the chosen method.

  3. 3.

Retrain the network for $r$ epochs using the training hyperparameters from
epochs $[e-r,e]$.

  4. 4.

Iteratively repeat 1.-3. after projecting the decomposed layers back
(optional).

ResNet20, CIFAR10

(a) Compress-only (r=0)

(b) One-shot (r=e)

(c) Retrain sweep ($\Delta\text{-Top1}$$\geq$-$1\%$)

ResNet18, ImageNet

(d) Compress-only (r=0)

(e) One-shot (r=e)

(f) Retrain sweep ($\Delta\text{-Top1}$$\geq$-$1\%$)

Figure 5:  The size-accuracy trade-off for various compression ratios,
methods, and networks. Compression was performed after training and networks
were re-trained once for the indicated amount (one-shot). (a, b, d, e): the
difference in test accuracy for fixed amounts of retraining. (c, f): the
maximal compression ratio with less-than-1% accuracy drop for variable amounts
of retraining.

##### Reporting metrics.

We report Top-1, Top-5, and IoU test accuracy as applicable for the respective
task. For each compressed network we also report the compression ratio, i.e.,
relative reduction, in terms of parameters and floating point operations
denoted by CR-P and CR-F, respectively. Each experiment was repeated $3$ times
and we report mean and standard deviation.

(a) MobileNetV2 (ImageNet)

(b) DeeplabV3-ResNet50 (VOC)

(c) legend

Figure 6: One-shot compress+retrain experiments on various architectures and
datasets with baseline comparisons.

###  3.1 One-shot Compression on CIFAR10, ImageNet, and VOC with Baselines

We train reference networks on CIFAR10, ImageNet, and VOC, and then compress
and retrain the networks _once_ with $r=e$ for various baseline comparisons
and compression ratios.

##### CIFAR10.

In Figure 4, we provide results for DenseNet22, VGG16, and WRN16-8 on CIFAR10.
Notably, our approach is able to outperform existing baselines approaches
across a wide range of tested compression ratios. Specifically, in the region
where the networks incur only minimal drop in accuracy
($\Delta\text{-Top1}$$\geq$$-1\%$) ALDS is particularly effective.

Table 1:  Baseline results for $\Delta\text{-Top1}$$\geq$$-0.5\%$ for one-shot
with highest CR-P and CR-F among tensor decomposition methods bolded for each
network. Results coincide with Figures 4, 5, 6.

Model Metric Tensor decomposition Filter pruning ALDS (Ours) PCA SVD-Energy
SVD L-Rank FT PFP CIFAR10 ResNet20 Top1: 91.39 $\Delta$-Top1 -0.47 -0.11 -0.21
-0.29 -0.44 -0.32 -0.28 CR-P, CR-F 74.91, 67.86 49.88, 48.67 49.88, 49.08
39.81, 38.95 28.71, 54.89 39.69, 39.57 40.28, 30.06 VGG16 Top1: 92.78
$\Delta$-Top1 -0.11 -0.02 -0.08 +0.29 -0.35 -0.47 -0.47 CR-P, CR-F 95.77,
86.23 89.72, 85.84 82.57, 81.32 70.35, 70.13 85.38, 75.86 79.13, 78.44 94.87,
84.76 DenseNet22 Top1: 89.88 $\Delta$-Top1 -0.32 +0.20 -0.29 +0.13 +0.26 -0.24
-0.44 CR-P, CR-F 56.84, 61.98 14.67, 34.55 15.16, 19.34 15.00, 15.33 14.98,
35.21 28.33, 29.50 40.24, 43.37 WRN16-8 Top1: 89.88 $\Delta$-Top1 -0.42 -0.49
-0.41 -0.96 -0.45 -0.32 -0.44 CR-P, CR-F 87.77, 79.90 85.33, 83.45 64.75,
60.94 40.20, 39.97 49.86, 58.00 82.33, 75.97 85.33, 80.68 ImageNet ResNet18
Top1: 69.62, Top5: 89.08 $\Delta$-Top1, Top5 -0.40, -0.05 -0.95,-0.37 -1.49,
-0.64 -1.75, -0.72 -0.71, -0.23 +0.10, +0.42 -0.39, -0.08 CR-P, CR-F 66.70,
43.51 9.99, 12.78 39.56, 40.99 50.38, 50.37 10.01, 32.64 9.86, 11.17 26.35,
17.96 MobileNetV2 Top1: 71.85, Top5: 90.33 $\Delta$-Top1, Top5 -1.53, -0.73
-0.87, -0.55 -1.27, -0.57 -3.65, -2.07 -19.08, -13.40 -1.73, -0.85 -0.97,
-0.40 CR-P, CR-F 32.97, 11.01 20.91, 0.26 20.02, 8.57 20.03, 31.99 20.00,
61.97 21.31, 20.23 20.02, 7.96 VOC DeeplabV3 IoU: 91.39 Top1: 99.34
$\Delta$-IoU, Top1 +0.14, -0.15 -0.26, -0.02 -1.88, -0.47 -0.28, -0.18 -0.42,
-0.09 -4.30, -0.91 -0.49, -0.21 CR-P, CR-F 64.38, 64.11 55.68, 55.82 31.61,
32.27 31.64, 31.51 44.99, 45.02 15.00, 15.06 45.17, 43.93

##### ResNets (CIFAR10 and ImageNet).

Moreover, we tested ALDS on ResNet20 (CIFAR10) and ResNet18 (ImageNet) as
shown in Figure 5. For these experiments, we performed a grid search over both
multiple compression ratios and amounts of retraining. Here, we highlight that
ALDS outperforms baseline approaches even with significantly less retraining.
On Resnet 18 (ImageNet) ALDS can compress over 50% of the parameters with
minimal retraining (1% retraining) and a less-than-1% accuracy drop compared
to the best comparison methods (40% compression with 50% retraining).

Table 2: AlexNet and ResNet18 Benchmarks on ImageNet. We report Top-1, Top-5
accuracy and percentage reduction of FLOPs (CR-F). Best results with less than
0.5% accuracy drop are bolded.

Method $\Delta$-Top1 $\Delta$-Top5 CR-F (%) ResNet18, Top1, 5: 69.64%, 88.98%
ALDS (Ours) -0.38 +0.04 64.5 ALDS (Ours) -1.37 -0.56 76.3 MUSCO (Gusak et al.,
2019) -0.37 -0.20 58.67 TRP1 (Xu et al., 2020) -4.18 -2.5 44.70 TRP1+Nu (Xu et
al., 2020) -4.25 -2.61 55.15 TRP2+Nu (Xu et al., 2020) -4.3 -2.37 68.55 PCA
(Zhang et al., 2015b) -6.54 -4.54 29.07 Expand (Jaderberg et al., 2014) -6.84
-5.26 50.00 PFP (Liebenwein et al., 2020) -2.26 -1.07 29.30 SoftNet (He et
al., 2018) -2.54 -1.2 41.80 Median (He et al., 2019) -1.23 -0.5 41.80 Slimming
(Liu et al., 2017) -1.77 -1.19 28.05 Low-cost (Dong et al., 2017) -3.55 -2.2
34.64 Gating (Hua et al., 2018) -1.52 -0.93 37.88 FT (He et al., 2017) -3.08
-1.75 41.86 DCP (Zhuang et al., 2018) -2.19 -1.28 47.08 FBS (Gao et al., 2018)
-2.44 -1.36 49.49 AlexNet, Top1, 5: 57.30%, 80.20% ALDS (Ours) -0.21 -0.36
77.9 ALDS (Ours) -0.41 -0.54 81.4 Tucker (Kim et al., 2015a) N/A -1.87 62.40
Regularize (Tai et al., 2015) N/A -0.54 74.35 Coordinate (Wen et al., 2017)
N/A -0.34 62.82 Efficient (Kim et al., 2019) -0.7 -0.3 62.40 L-Rank (Idelbayev
et al., 2020) -0.13 -0.13 66.77 NISP (Yu et al., 2018) -1.43 N/A 67.94 OICSR
(Li et al., 2019a) -0.47 N/A 53.70 Oracle (Ding et al., 2019) -1.13 -0.67
31.97

##### MobileNetV2 (ImageNet).

Next, we tested and compared ALDS on the MobileNetV2 architecture for ImageNet
as shown in Figure 6. Unlike the other networks, MobileNetV2 is a network
already specifically optimized for efficient deployment and includes layer
structures such as depth-wise and channel-wise convolutional operations. It is
thus more challenging to find redundancies in the architecture. We find that
ALDS can outperform existing tensor decomposition methods in this scenario as
well.

##### VOC.

Finally, we tested the same setup on a DeeplabV3 with a ResNet50 backbone
trained on Pascal VOC 2012 segmentation data, see Figure 6. We note that ALDS
consistently outperforms other baselines methods in this setting as well (60%
CR-P vs. 20% without accuracy drop).

##### Tabular results.

Our one-shot results are again summarized in Table 1 where we report CR-P and
CR-F for $\Delta\text{-Top1}$$\geq$$-0.5\%$. We observe that ALDS consistently
improves upon prior work. We note that pruning usually takes on the order of
seconds and minutes for CIFAR and ImageNet, respectively, which is usually
faster than even a single training epoch.

###  3.2 ImageNet Benchmarks

Next, we test our framework on two common ImageNet benchmarks, ResNet18 and
AlexNet. We follow the compress-retrain pipeline outlined in the beginning of
the section and repeat it iteratively to obtain higher compression ratios.
Specifically, after retraining and before the next compression step we project
the decomposed layers back to the original layer. This way, we avoid recursing
on the decomposed layers.

Our results are reported in Table 2 where we compare to a wide variety of
available compression benchmarks (results were adapted directly from the
respective papers). The middle part and bottom part of the table for each
network are organized into low-rank compression and filter pruning approaches,
respectively. Note that the reported differences in accuracy ($\Delta$-Top1
and $\Delta$-Top5) are relative to our baseline accuracies. On ResNet18 we can
reduce the number of FLOPs by 65% with minimal drop in accuracy compared to
the best competing method (MUSCO, 58.67%). With a slightly higher drop in
accuracy (-1.37%) we can even compress 76% of FLOPs. On AlexNet, our framework
finds networks with -0.21% and -0.41% difference in accuracy with over 77% and
81% fewer FLOPs. This constitutes a more-than-10% improvement in terms of
FLOPs compared to current state-of-the-art (L-Rank) for similar accuracy
drops.

###  3.3 Ablation Study

Figure 7: One-shot ablation study of ALDS for Resnet20 (CIFAR10).

To investigate the different features of our method we ran compression
experiments using multiple variations derived from our method, see Figure 7.
For the simplest version of our method we consider a constant per-layer
compression ratio and fix the value of $k$ to either 3 or 5 for all layers
denoted by ALDS-Simple3 and ALDS-Simple5, respectively. Note that ALDS-Simple
with $k=1$ corresponds to the SVD comparison method. For the version denoted
by ALDS-Error3 we fix the number of subspaces per layer ($k=3$) and only run
the global step of ALDS (Line 4 of Algorithm 1) to determine the optimal per-
layer compression ratio. The results of our ablation study in Figure 7
indicate that our method clearly benefits from the combination of both the
global and local step in terms of the number of subspaces ($k$) and the rank
per subspace ($j$).

We also compare our subspace clustering (channel slicing) to the clustering
technique of Maalouf et al. (2021), which clusters the matrix columns using
projective clustering. Specifically, we replace the channel slicing of ALDS-
Simple3 with projective clustering (Messi3 in Figure 7). As expected Messi
improves the performance over ALDS-Simple but only slightly and the difference
is essentially negligible. Together with the computational disadvantages of
Messi-like clustering methods (unstructured, NP-hard; see Section 2.1) ALDS-
based simple channel slicing is therefore the preferred choice in our context.

##  4 Related Work

Our work builds upon prior work in neural network compression. We discuss
related work focusing on pruning, low-rank compression, and global aspects of
compression.

##### Unstructured pruning.

Weight pruning (Singh and Alistarh, 2020; Lin et al., 2020b; Molchanov et al.,
2016, 2019; Wang et al., 2021; Yu et al., 2018) techniques aim to reduce the
number of individual weights, e.g., by removing weights with absolute values
below a threshold (Han et al., 2015; Renda et al., 2020), or by using a mini-
batch of data points to approximate the influence of each parameter on the
loss function (Baykal et al., 2019a, b). However, since these approaches
generate sparse instead of smaller models they require some form of sparse
linear algebra support for runtime speed-ups.

##### Structured pruning.

Pruning structures such as filters directly shrinks the network (Li et al.,
2019b; Luo and Wu, 2020; Liu et al., 2019a; Chen et al., 2020; Ye et al.,
2018; Lin et al., 2020a). Filters can be pruned using a score for each filter,
e.g., weight-based (He et al., 2017, 2018) or data-informed (Yu et al., 2018;
Liebenwein et al., 2020), and removing those with a score below a threshold.
It is worth noting that filter pruning is complimentary to low-rank
compression.

##### Low-rank compression (local step).

A common approach to low-rank compression entails tensor decomposition
including Tucker-decomposition (Kim et al., 2015b), CP-decomposition (Lebedev
et al., 2015), Tensor-Train (Garipov et al., 2016; Novikov et al., 2015) and
others (Denil et al., 2013; Jaderberg et al., 2014; Ioannou et al., 2017).
Other decomposition-like approaches include weight sharing, random
projections, and feature hashing (Weinberger et al., 2009; Arora et al., 2018;
Shi et al., 2009; Chen et al., 2015a, b; Ullrich et al., 2017). Alternatively,
low-rank compression can be performed via matrix decomposition (e.g., SVD) on
flattened tensors as done by Denton et al. (2014); Yu et al. (2017); Sainath
et al. (2013); Xue et al. (2013); Tukan et al. (2020) among others. Chen et
al. (2018); Maalouf et al. (2021); Denton et al. (2014) also explores the use
of subspace clustering before applying low-rank compression to each cluster to
improve the approximation error. Notably, most prior work relies on some form
of expensive approximation algorithm – even to just solve the per-layer low-
rank compression, e.g., clustering or tensor decomposition. In this paper, we
instead focus on the global compression problem and show that simple
compression techniques (SVD with channel slicing) are advantageous in this
context as we can use them as efficient subroutines. We note that we can even
extend our algorithm to multiple, different types of per-layer decomposition.

##### Network-aware compression (global step).

To determine the rank (or the compression ratio) of each layer, prior work
suggests to account for compression during training (Alvarez and Salzmann,
2017; Wen et al., 2017; Xu et al., 2020; Ioannou et al., 2015, 2016), e.g, by
training the network with a penalty that encourages the weight matrices to be
low-rank. Others suggest to select the ranks using variational Bayesian matrix
factorization (Kim et al., 2015b). In their recent paper, Chin et al. (2020)
suggest to produce an entire set of compressed networks with different
accuracy/speed trade-offs. Our paper was also inspired by a recent line of
work towards automatically choosing or learning the rank of each layer
(Idelbayev and Carreira-Perpinán, 2020; Gusak et al., 2019; Tiwari et al.,
2021; Zhang et al., 2015c; Li and Shi, 2018; Zhang et al., 2015b). We take
such approaches further and suggest a global compression framework that
incorporates multiple decomposition techniques with more than one hyper-
parameter per layer (number of subspaces and ranks of each layer). This
approach increases the number of local minima in theory and helps improving
the performance in practice.

##  5 Discussion and Conclusion

##### Practical benefits.

By conducting a wide variety of experiments across multiple data sets and
networks we have shown the effectiveness and versatility of our compression
framework compared to existing methods. The runtime of ALDS is negligible
compared to retraining and it can thus be efficiently incorporated into
compress-retrain pipelines.

##### ALDS as modular compression framework.

By separately considering the low-rank compression scheme for each layer
(local step) and the actual low-rank compression (global step) we have
provided a framework that can efficiently search over a set of desired
hyperparameters that describe the low-rank compression. Naturally, our
framework can thus be generalized to other compression schemes (such as tensor
decomposition) and we hope to explore these aspects in future work.

##### Error bounds lead to global insights.

At the core of our contribution is our error analysis that enables us to link
the global and local aspects of layer-wise compression techniques. We leverage
our error bounds in practice to compress networks more effectively via an
automated rank selection procedure without additional tedious hyperparameter
tuning. However, we also have to rely on a proxy definition (maximum relative
error) of the compression error to enable a tractable solution that we can
implement efficiently. We hope these observations invigorate future research
into compression techniques that come with tight error bounds – potentially
even considering retraining – which can then naturally be wrapped into a
global compression framework.

## Acknowledgments

This research was sponsored by the United States Air Force Research Laboratory
and the United States Air Force Artificial Intelligence Accelerator and was
accomplished under Cooperative Agreement Number FA8750-19-2-1000. The views
and conclusions contained in this document are those of the authors and should
not be interpreted as representing the official policies, either expressed or
implied, of the United States Air Force or the U.S. Government. The U.S.
Government is authorized to reproduce and distribute reprints for Government
purposes notwithstanding any copyright notation herein. This work was further
supported by the Office of Naval Research (ONR) Grant N00014-18-1-2830.

## References

  * Alvarez and Salzmann (2017) Jose M Alvarez and Mathieu Salzmann.  Compression-aware training of deep networks.  In _Advances in Neural Information Processing Systems_ , pages 856–867, 2017.
  * Arora et al. (2018) Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang.  Stronger generalization bounds for deep nets via a compression approach.  In _International Conference on Machine Learning_ , pages 254–263, 2018.
  * Baykal et al. (2019a) Cenk Baykal, Lucas Liebenwein, Igor Gilitschenski, Dan Feldman, and Daniela Rus.  Data-dependent coresets for compressing neural networks with applications to generalization bounds.  In _International Conference on Learning Representations_ , 2019a.  URL https://openreview.net/forum?id=HJfwJ2A5KX.
  * Baykal et al. (2019b) Cenk Baykal, Lucas Liebenwein, Igor Gilitschenski, Dan Feldman, and Daniela Rus.  Sipping neural networks: Sensitivity-informed provable pruning of neural networks.  _arXiv preprint arXiv:1910.05422_ , 2019b.
  * Chen et al. (2020) Jianda Chen, Shangyu Chen, and Sinno Jialin Pan.  Storage efficient and dynamic flexible runtime channel pruning via deep reinforcement learning.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Chen et al. (2017) Liang-Chieh Chen, George Papandreou, Florian Schroff, and Hartwig Adam.  Rethinking atrous convolution for semantic image segmentation.  _arXiv preprint arXiv:1706.05587_ , 2017.
  * Chen et al. (2018) Patrick H. Chen, Si Si, Yang Li, Ciprian Chelba, and Cho-jui Hsieh.  GroupReduce: Block-Wise Low-Rank Approximation for Neural Language Model Shrinking.  _Advances in Neural Information Processing Systems_ , 2018-December:10988–10998, jun 2018.  URL http://arxiv.org/abs/1806.06950.
  * Chen et al. (2015a) Wenlin Chen, James Wilson, Stephen Tyree, Kilian Weinberger, and Yixin Chen.  Compressing neural networks with the hashing trick.  In _International conference on machine learning_ , pages 2285–2294, 2015a.
  * Chen et al. (2015b) Wenlin Chen, James T. Wilson, Stephen Tyree, Kilian Q. Weinberger, and Yixin Chen.  Compressing convolutional neural networks.  _CoRR_ , abs/1506.04449, 2015b.  URL http://arxiv.org/abs/1506.04449.
  * Chin et al. (2020) Ting-Wu Chin, Ruizhou Ding, Cha Zhang, and Diana Marculescu.  Towards efficient model compression via learned global ranking.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 1518–1528, 2020.
  * Clarkson and Woodruff (2015) Kenneth L Clarkson and David P Woodruff.  Input sparsity and hardness for robust subspace approximation.  In _2015 IEEE 56th Annual Symposium on Foundations of Computer Science_ , pages 310–329. IEEE, 2015.
  * Dempster et al. (1977) Arthur P Dempster, Nan M Laird, and Donald B Rubin.  Maximum likelihood from incomplete data via the em algorithm.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 39(1):1–22, 1977.
  * Denil et al. (2013) Misha Denil, Babak Shakibi, Laurent Dinh, Marc Aurelio Ranzato, and Nando de Freitas.  Predicting parameters in deep learning.  In _Advances in Neural Information Processing Systems 26_ , pages 2148–2156, 2013.
  * Denton et al. (2014) Emily Denton, Wojciech Zaremba, Joan Bruna, Yann LeCun, and Rob Fergus.  Exploiting Linear Structure Within Convolutional Networks for Efficient Evaluation.  _Advances in Neural Information Processing Systems_ , 2(January):1269–1277, apr 2014.  URL http://arxiv.org/abs/1404.0736.
  * Ding et al. (2019) Xiaohan Ding, Guiguang Ding, Yuchen Guo, Jungong Han, and Chenggang Yan.  Approximated oracle filter pruning for destructive cnn width optimization.  In _International Conference on Machine Learning_ , pages 1607–1616. PMLR, 2019.
  * Dong et al. (2017) Xuanyi Dong, Junshi Huang, Yi Yang, and Shuicheng Yan.  More is less: A more complicated network with less inference complexity.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 5840–5848, 2017.
  * Everingham et al. (2015) Mark Everingham, SM Ali Eslami, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman.  The pascal visual object classes challenge: A retrospective.  _International journal of computer vision_ , 111(1):98–136, 2015.
  * Gao et al. (2018) Xitong Gao, Yiren Zhao, Łukasz Dudziak, Robert Mullins, and Cheng-zhong Xu.  Dynamic channel pruning: Feature boosting and suppression.  _arXiv preprint arXiv:1810.05331_ , 2018.
  * Garipov et al. (2016) Timur Garipov, Dmitry Podoprikhin, Alexander Novikov, and Dmitry Vetrov.  Ultimate tensorization: compressing convolutional and fc layers alike.  _arXiv preprint arXiv:1611.03214_ , 2016.
  * Golub and Van Loan (2013) Gene H Golub and Charles F Van Loan.  _Matrix computations_ , volume 3.  JHU press, 2013.
  * Goyal et al. (2017) Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He.  Accurate, large minibatch sgd: Training imagenet in 1 hour.  _arXiv preprint arXiv:1706.02677_ , 2017.
  * Gusak et al. (2019) Julia Gusak, Maksym Kholiavchenko, Evgeny Ponomarev, Larisa Markeeva, Philip Blagoveschensky, Andrzej Cichocki, and Ivan Oseledets.  Automated multi-stage compression of neural networks.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops_ , pages 0–0, 2019.
  * Han et al. (2015) Song Han, Huizi Mao, and William J. Dally.  Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding.  _CoRR_ , abs/1510.00149, 2015.  URL http://arxiv.org/abs/1510.00149.
  * Hariharan et al. (2011) Bharath Hariharan, Pablo Arbeláez, Lubomir Bourdev, Subhransu Maji, and Jitendra Malik.  Semantic contours from inverse detectors.  In _2011 International Conference on Computer Vision_ , pages 991–998. IEEE, 2011.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * He et al. (2018) Yang He, Guoliang Kang, Xuanyi Dong, Yanwei Fu, and Yi Yang.  Soft filter pruning for accelerating deep convolutional neural networks.  In _Proceedings of the 27th International Joint Conference on Artificial Intelligence_ , pages 2234–2240. AAAI Press, 2018.
  * He et al. (2019) Yang He, Ping Liu, Ziwei Wang, Zhilan Hu, and Yi Yang.  Filter pruning via geometric median for deep convolutional neural networks acceleration.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 4340–4349, 2019.
  * He et al. (2017) Yihui He, Xiangyu Zhang, and Jian Sun.  Channel pruning for accelerating very deep neural networks.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pages 1389–1397, 2017.
  * Hinton et al. (2015) Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  _arXiv preprint arXiv:1503.02531_ , 2015.
  * Hua et al. (2018) Weizhe Hua, Yuan Zhou, Christopher De Sa, Zhiru Zhang, and G Edward Suh.  Channel gating neural networks.  _arXiv preprint arXiv:1805.12549_ , 2018.
  * Huang et al. (2017) Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger.  Densely connected convolutional networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4700–4708, 2017.
  * Idelbayev and Carreira-Perpinán (2020) Yerlan Idelbayev and Miguel A Carreira-Perpinán.  Low-rank compression of neural nets: Learning the rank of each layer.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 8049–8059, 2020.
  * Ioannou et al. (2016) Y Ioannou, D Robertson, J Shotton, R Cipolla, and A Criminisi.  Training cnns with low-rank filters for efficient image classification.  In _4th International Conference on Learning Representations, ICLR 2016-Conference Track Proceedings_ , 2016.
  * Ioannou et al. (2015) Yani Ioannou, Duncan Robertson, Jamie Shotton, Roberto Cipolla, and Antonio Criminisi.  Training cnns with low-rank filters for efficient image classification.  _arXiv preprint arXiv:1511.06744_ , 2015.
  * Ioannou et al. (2017) Yani Ioannou, Duncan Robertson, Roberto Cipolla, and Antonio Criminisi.  Deep roots: Improving cnn efficiency with hierarchical filter groups.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 1231–1240, 2017.
  * Jaderberg et al. (2014) Max Jaderberg, Andrea Vedaldi, and Andrew Zisserman.  Speeding up convolutional neural networks with low rank expansions.  In _Proceedings of the British Machine Vision Conference. BMVA Press_ , 2014.
  * Kim et al. (2019) Hyeji Kim, Muhammad Umar Karim Khan, and Chong-Min Kyung.  Efficient neural network compression.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 12569–12577, 2019.
  * Kim et al. (2015a) Yong-Deok Kim, Eunhyeok Park, Sungjoo Yoo, Taelim Choi, Lu Yang, and Dongjun Shin.  Compression of Deep Convolutional Neural Networks for Fast and Low Power Mobile Applications.  _4th International Conference on Learning Representations, ICLR 2016 - Conference Track Proceedings_ , nov 2015a.  URL http://arxiv.org/abs/1511.06530.
  * Kim et al. (2015b) Yong-Deok Kim, Eunhyeok Park, Sungjoo Yoo, Taelim Choi, Lu Yang, and Dongjun Shin.  Compression of deep convolutional neural networks for fast and low power mobile applications.  _arXiv preprint arXiv:1511.06530_ , 2015b.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems 25_ , pages 1097–1105. Curran Associates, Inc., 2012.  URL http://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.pdf.
  * Laparra et al. (2015) Valero Laparra, Jesús Malo, and Gustau Camps-Valls.  Dimensionality reduction via regression in hyperspectral imagery.  _IEEE Journal of Selected Topics in Signal Processing_ , 9(6):1026–1036, 2015.
  * Lebedev et al. (2015) Vadim Lebedev, Yaroslav Ganin, Maksim Rakhuba, Ivan V. Oseledets, and Victor S. Lempitsky.  Speeding-up convolutional neural networks using fine-tuned cp-decomposition.  In _ICLR (Poster)_ , 2015.  URL http://arxiv.org/abs/1412.6553.
  * Li and Shi (2018) Chong Li and CJ Shi.  Constrained optimization based low-rank approximation of deep neural networks.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 732–747, 2018.
  * Li et al. (2016) Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf.  Pruning filters for efficient convnets.  _arXiv preprint arXiv:1608.08710_ , 2016.
  * Li et al. (2019a) Jiashi Li, Qi Qi, Jingyu Wang, Ce Ge, Yujian Li, Zhangzhang Yue, and Haifeng Sun.  Oicsr: Out-in-channel sparsity regularization for compact deep neural networks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 7046–7055, 2019a.
  * Li et al. (2019b) Yawei Li, Shuhang Gu, Luc Van Gool, and Radu Timofte.  Learning filter basis for convolutional neural network compression.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pages 5623–5632, 2019b.
  * Liebenwein et al. (2020) Lucas Liebenwein, Cenk Baykal, Harry Lang, Dan Feldman, and Daniela Rus.  Provable filter pruning for efficient neural networks.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=BJxkOlSYDH.
  * Liebenwein et al. (2021a) Lucas Liebenwein, Cenk Baykal, Brandon Carter, David Gifford, and Daniela Rus.  Lost in pruning: The effects of pruning neural networks beyond test accuracy.  _Proceedings of Machine Learning and Systems_ , 3, 2021a.
  * Liebenwein et al. (2021b) Lucas Liebenwein, Ramin Hasani, Alexander Amini, and Daniela Rus.  Sparse flows: Pruning continuous-depth models.  _arXiv preprint arXiv:2106.12718_ , 2021b.
  * Lin et al. (2020a) Mingbao Lin, Rongrong Ji, Yan Wang, Yichen Zhang, Baochang Zhang, Yonghong Tian, and Ling Shao.  Hrank: Filter pruning using high-rank feature map.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 1529–1538, 2020a.
  * Lin et al. (2020b) Tao Lin, Sebastian U. Stich, Luis Barba, Daniil Dmitriev, and Martin Jaggi.  Dynamic model pruning with feedback.  In _International Conference on Learning Representations_ , 2020b.  URL https://openreview.net/forum?id=SJem8lSFwB.
  * Liu et al. (2019a) Zechun Liu, Haoyuan Mu, Xiangyu Zhang, Zichao Guo, Xin Yang, Kwang-Ting Cheng, and Jian Sun.  Metapruning: Meta learning for automatic neural network channel pruning.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 3296–3305, 2019a.
  * Liu et al. (2017) Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang, Shoumeng Yan, and Changshui Zhang.  Learning efficient convolutional networks through network slimming.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pages 2736–2744, 2017.
  * Liu et al. (2019b) Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell.  Rethinking the value of network pruning.  In _International Conference on Learning Representations_ , 2019b.  URL https://openreview.net/forum?id=rJlnB3C5Ym.
  * Luo and Wu (2020) Jian-Hao Luo and Jianxin Wu.  Autopruner: An end-to-end trainable filter pruning method for efficient deep model inference.  _Pattern Recognition_ , 107:107461, 2020.
  * Maalouf et al. (2021) Alaa Maalouf, Harry Lang, Daniela Rus, and Dan Feldman.  Deep learning meets projective clustering.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=EQfpYwF3-b.
  * Molchanov et al. (2016) Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz.  Pruning convolutional neural networks for resource efficient inference.  _arXiv preprint arXiv:1611.06440_ , 2016.
  * Molchanov et al. (2019) Pavlo Molchanov, Arun Mallya, Stephen Tyree, Iuri Frosio, and Jan Kautz.  Importance estimation for neural network pruning.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 11264–11272, 2019.
  * Novikov et al. (2015) Alexander Novikov, Dmitry Podoprikhin, Anton Osokin, and Dmitry Vetrov.  Tensorizing neural networks.  In _Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume 1_ , pages 442–450, 2015.
  * Paszke et al. (2017) Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer.  Automatic differentiation in pytorch.  In _NIPS-W_ , 2017.
  * Peng et al. (2015) Xi Peng, Zhang Yi, and Huajin Tang.  Robust subspace clustering via thresholding ridge regression.  In _Twenty-Ninth AAAI Conference on Artificial Intelligence_ , 2015\.
  * Renda et al. (2020) Alex Renda, Jonathan Frankle, and Michael Carbin.  Comparing fine-tuning and rewinding in neural network pruning.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=S1gSj0NKvB.
  * Russakovsky et al. (2015) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.  ImageNet Large Scale Visual Recognition Challenge.  _International Journal of Computer Vision (IJCV)_ , 115(3):211–252, 2015.  doi: 10.1007/s11263-015-0816-y.
  * Sainath et al. (2013) Tara N Sainath, Brian Kingsbury, Vikas Sindhwani, Ebru Arisoy, and Bhuvana Ramabhadran.  Low-rank matrix factorization for deep neural network training with high-dimensional output targets.  In _2013 IEEE international conference on acoustics, speech and signal processing_ , pages 6655–6659. IEEE, 2013.
  * Sandler et al. (2018) Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  Mobilenetv2: Inverted residuals and linear bottlenecks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4510–4520, 2018.
  * Shi et al. (2009) Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alex Smola, and SVN Vishwanathan.  Hash kernels for structured data.  _Journal of Machine Learning Research_ , 10(Nov):2615–2637, 2009.
  * Simonyan and Zisserman (2014) Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Simonyan and Zisserman (2015) Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In _International Conference on Learning Representations_ , 2015.
  * Singh and Alistarh (2020) Sidak Pal Singh and Dan Alistarh.  Woodfisher: Efficient second-order approximations for model compression.  _arXiv preprint arXiv:2004.14340_ , 2020.
  * Tai et al. (2015) Cheng Tai, Tong Xiao, Yi Zhang, Xiaogang Wang, et al.  Convolutional neural networks with low-rank regularization.  _arXiv preprint arXiv:1511.06067_ , 2015.
  * Tiwari et al. (2021) Rishabh Tiwari, Udbhav Bamba, Arnav Chavan, and Deepak Gupta.  Chipnet: Budget-aware pruning with heaviside continuous approximations.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=xCxXwTzx4L1.
  * Torralba et al. (2008) Antonio Torralba, Rob Fergus, and William T Freeman.  80 million tiny images: A large data set for nonparametric object and scene recognition.  _IEEE transactions on pattern analysis and machine intelligence_ , 30(11):1958–1970, 2008.
  * Tukan et al. (2020) Murad Tukan, Alaa Maalouf, Matan Weksler, and Dan Feldman.  Compressed deep networks: Goodbye svd, hello robust low-rank approximation.  _arXiv preprint arXiv:2009.05647_ , 2020.
  * Ullrich et al. (2017) Karen Ullrich, Edward Meeds, and Max Welling.  Soft weight-sharing for neural network compression.  _arXiv preprint arXiv:1702.04008_ , 2017.
  * Wang et al. (2021) Huan Wang, Can Qin, Yulun Zhang, and Yun Fu.  Neural pruning via growing regularization.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=o966_Is_nPA.
  * Weinberger et al. (2009) Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg.  Feature hashing for large scale multitask learning.  In _Proceedings of the 26th annual international conference on machine learning_ , pages 1113–1120, 2009.
  * Wen et al. (2017) Wei Wen, Cong Xu, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li.  Coordinating Filters for Faster Deep Neural Networks.  _Proceedings of the IEEE International Conference on Computer Vision_ , 2017-Octob:658–666, mar 2017.  URL http://arxiv.org/abs/1703.09746.
  * Wu et al. (2016) Jiaxiang Wu, Cong Leng, Yuhang Wang, Qinghao Hu, and Jian Cheng.  Quantized Convolutional Neural Networks for Mobile Devices.  In _Proceedings of the International Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * Xu et al. (2020) Yuhui Xu, Yuxi Li, Shuai Zhang, Wei Wen, Botao Wang, Yingyong Qi, Yiran Chen, Weiyao Lin, and Hongkai Xiong.  TRP: Trained Rank Pruning for Efficient Deep Neural Networks.  _IJCAI International Joint Conference on Artificial Intelligence_ , 2021-Janua:977–983, apr 2020.  URL http://arxiv.org/abs/2004.14566.
  * Xue et al. (2013) Jian Xue, Jinyu Li, and Yifan Gong.  Restructuring of deep neural network acoustic models with singular value decomposition.  In _Interspeech_ , pages 2365–2369, 2013.
  * Ye et al. (2018) Jianbo Ye, Xin Lu, Zhe Lin, and James Z. Wang.  Rethinking the smaller-norm-less-informative assumption in channel pruning of convolution layers.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=HJ94fqApW.
  * Yu et al. (2018) Ruichi Yu, Ang Li, Chun-Fu Chen, Jui-Hsin Lai, Vlad I Morariu, Xintong Han, Mingfei Gao, Ching-Yung Lin, and Larry S Davis.  Nisp: Pruning networks using neuron importance score propagation.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 9194–9203, 2018.
  * Yu et al. (2017) Xiyu Yu, Tongliang Liu, Xinchao Wang, and Dacheng Tao.  On compressing deep models by low rank and sparse decomposition.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 7370–7379, 2017.
  * Zagoruyko and Komodakis (2016) Sergey Zagoruyko and Nikos Komodakis.  Wide residual networks.  _arXiv preprint arXiv:1605.07146_ , 2016.
  * Zhang et al. (2015a) Xiangyu Zhang, Jianhua Zou, Kaiming He, and Jian Sun.  Accelerating Very Deep Convolutional Networks for Classification and Detection.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 38(10):1943–1955, may 2015a.  URL http://arxiv.org/abs/1505.06798.
  * Zhang et al. (2015b) Xiangyu Zhang, Jianhua Zou, Kaiming He, and Jian Sun.  Accelerating very deep convolutional networks for classification and detection.  _IEEE transactions on pattern analysis and machine intelligence_ , 38(10):1943–1955, 2015b.
  * Zhang et al. (2015c) Xiangyu Zhang, Jianhua Zou, Xiang Ming, Kaiming He, and Jian Sun.  Efficient and accurate approximations of nonlinear convolutional networks.  In _Proceedings of the IEEE Conference on Computer Vision and pattern Recognition_ , pages 1984–1992, 2015c.
  * Zhuang et al. (2018) Zhuangwei Zhuang, Mingkui Tan, Bohan Zhuang, Jing Liu, Yong Guo, Qingyao Wu, Junzhou Huang, and Jinhui Zhu.  Discrimination-aware channel pruning for deep neural networks.  _arXiv preprint arXiv:1810.11809_ , 2018.

Supplementary Material Lucas Liebenwein∗
MIT CSAIL
<EMAIL_ADDRESS>
&Alaa Maalouf∗
University of Haifa
<EMAIL_ADDRESS>
Oren Gal
University of Haifa
<EMAIL_ADDRESS>&Dan Feldman
University of Haifa
<EMAIL_ADDRESS>
&Daniela Rus
MIT CSAIL
<EMAIL_ADDRESS>

###### Contents

  1. 1 Introduction
  2. 2 Method
    1. 2.1 Local Layer Compression
    2. 2.2 Global Network Compression
    3. 2.3 Automatic Layer-wise Decomposition Selector (ALDS)
  3. 3 Experiments
    1. 3.1 One-shot Compression on CIFAR10, ImageNet, and VOC with Baselines
    2. 3.2 ImageNet Benchmarks
    3. 3.3 Ablation Study
  4. 4 Related Work
  5. 5 Discussion and Conclusion
  6. A Further Method Details
    1. A.1 Method Preliminaries
    2. A.2 Clustering Methods
    3. A.3 Compressing via SVD
    4. A.4 Efficient Implementation of ALDS (Algorithm 1)
    5. A.5 Additional Discussion of ALDS (Algorithm 1)
    6. A.6 Extensions of ALDS
  7. B Experimental Setup and Hyperparameters
    1. B.1 Experimental Setup for CIFAR10
    2. B.2 Experimental Setup for ImageNet
    3. B.3 Experimental Setup for Pascal VOC
    4. B.4 Baseline Methods
    5. B.5 Compress-Retrain Pipeline
  8. C Additional Experimental Results
    1. C.1 Complete Tables for One-shot Compression Experiments from Section 3.1
    2. C.2 Complete ImageNet Benchmark Results from Section 3.2
    3. C.3 Ablation Study
    4. C.4 Extensions of ALDS

##  Appendix A Further Method Details

In this section, we provide more details pertaining to our method.

###  A.1 Method Preliminaries

Our layer-wise compression technique hinges upon the insight that any linear
layer may be cast as a matrix multiplication, which enables us to rely on SVD
as compression subroutine. Focusing on convolutions we show how such a layer
can be recast as matrix multiplication. Similar approaches have been used by
Denton et al. (2014); Idelbayev and Carreira-Perpinán (2020); Wen et al.
(2017) among others.

Figure 8: Convolution to matrix multiplication. A convolutional layer of
$f=20$ filters, $c=6$ channels, and $2\times 2$ kernel
($\kappa_{1}=\kappa_{2}=2$). The input tensor shape is $6\times 3\times 3$.
The corresponding weight matrix has $f=20$ rows (one row per filter) and $24$
columns ($c\times\kappa_{1}\times\kappa_{2}$), as for the corresponding
feature matrix, it has $24$ rows and $4$ columns, the $4$ here is the number
of convolution windows (i.e., number of pixels/entries in each of the output
feature maps). After multiplying those matrices, we reshape them to the
desired shape to obtain the desired output feature maps.

##### Convolution to matrix multiplication.

For a given convolutional layer of $f$ filters, $c$ channels,
$\kappa_{1}\times\kappa_{2}$ kernel and an input feature map with $c$
features, each of size $m_{1}\times m_{2}$, we denote by
$\mathbf{\mathcal{W}}\in\mathbb{R}^{f\times
c\times\kappa_{1}\times\kappa_{2}}$ and
$\mathbf{\mathcal{X}}\in\mathbb{R}^{c\times m_{1}\times m_{2}}$ the weight
tensor and input tensor, respectively. Moreover, let $W\in\mathbb{R}^{f\times
c\kappa_{1}\kappa_{2}}$ denote the unfolded matrix operator of the layer
constructed from $\mathbf{\mathcal{W}}$ by flattening the $c$ kernels of each
filter into a row and stacking the rows to form a matrix. Finally, let $p$
denote the total number of sliding blocks and
$X\in\mathbb{R}^{c\kappa_{1}\kappa_{2}\times p}$ denote the unfolded input
matrix, which is constructed from the input tensor $\mathbf{\mathcal{X}}$ as
follows: while simulating the convolution by sliding $\mathbf{\mathcal{W}}$
along $\mathbf{\mathcal{X}}$ we extract the sliding local blocks of
$\mathbf{\mathcal{X}}$ across all channels by flattening each block into a
$c\kappa_{1}\kappa_{2}$-dimensional column vector and concatenating them
together to form $X$. As illustrated in Figure 8 we may now express the
convolution $\mathbf{\mathcal{Y}}=\mathbf{\mathcal{W}}*\mathbf{\mathcal{X}}$
as the matrix multiplication $Y=WX$, where
$\mathbf{\mathcal{Y}}\in\mathbb{R}^{f\times p_{1}\times p_{2}}$ and
$Y\in\mathbb{R}^{f\times p}$ correspond to the tensor and matrix
representation of the output feature maps, respectively, and $p_{1}$, $p_{2}$
denote the spatial dimensions of $\mathbf{\mathcal{Y}}$. The equivalence of
$\mathbf{\mathcal{Y}}$ and $Y$ can be easily established via an appropriate
reshaping operation since $p=p_{1}p_{2}$.

Figure 9: Low-rank decomposition for convolutional layers via SVD. The given
convolution, c.f. Figure 8, has $20$ filters, each of shape $6\times 2\times
2$, resulting in a total of $480$ parameters. After extracting the
corresponding weight matrix $W\in\mathbb{R}^{20\times 24}$ ($f\times
c\kappa_{1}\kappa_{2}$), we compute its $(j=7)$-rank decomposition to obtain
the pair of matrices $U\in\mathbb{R}^{20\times 7}$ ($f\times j$) and
$V\in\mathbb{R}^{7\times 24}$ ($j\times c\kappa_{1}\kappa_{2}$). Those
matrices are encoded back as a pair of convolutional layers, the first
(corresponding to $V$) has $j=7$ filters, $c=6$ channels and a $2\times 2$
($\kappa_{1}\times\kappa_{2}$) kernel, whereas the second (corresponding to
$U$) is a $1\times 1$ convolution of $f=20$ filters, and $j=7$ channels. The
resulting layers have $308$ parameters.

##### Efficient tensor decomposition via SVD.

Equipped with the notion of correspondence between convolution and matrix
multiplication our goal is to decompose the layer via its matrix operator
$W\in\mathbb{R}^{f\times c\kappa_{1}\kappa_{2}}$. To this end, we compute the
$j$-rank approximation of $W$ using SVD and factor it into a pair of smaller
matrices $U\in\mathbb{R}^{f\times j}$ and $V\in\mathbb{R}^{j\times
c\kappa_{1}\kappa_{2}}$. More details on how to compute $U$ and $V$ are given
in Section A. We may then replace the original convolution, represented by
$W$, by two smaller convolutions, represented by $V$ and $U$ for the first and
second layer, respectively. Just like for the original layer, we can establish
an equivalent convolution layer for both $U$ and $V$ as depicted in Figure 9.
To establish the equivalence we note that (a) every row of the matrices $V$
and $U$ corresponds to a flattened filter of the respective convolution, and
(b) the number of channels in each layer is equal to the number of channels in
its corresponding input tensor. Hence, the first layer, which is represented
by $V\in\mathbb{R}^{j\times c\kappa_{1}\kappa_{2}}$ has $j$ filters, c.f. (a),
each consisting of $c$ channels, c.f. (b), with kernel size
$\kappa_{1}\times\kappa_{2}$. The second layer corresponding to $U$ has $f$
filters, c.f. (a), $j$ channels, c.f. (b), and a $1\times 1$ kernel and may be
equivalently represented as the tensor
$\mathbf{\mathcal{U}}\in\mathbb{R}^{f\times j\times 1\times 1}$. Note that the
number of weights is reduced from $fc\kappa_{1}\kappa_{2}$ to
$j(f+c\kappa_{1}\kappa_{2})$.

###  A.2 Clustering Methods

As previously explained in Section 2.1, one can cluster the columns of the
corresponding weight matrix $W$, instead of clustering the channels of the
convolutional layer. Here, the channel clustering can be defined as constraint
clustering of these columns, where columns which include entries that
correspond to the same kernel (e.g., the first $4$ columns in $W$ from Figure
9) are guaranteed to be in the same cluster.

This generalization is easily adaptable to other clustering methods that
generate a wider set of solutions, e.g., the known $k$-means. An intuitive
choice for our case is projective clustering and its variants. The goal of
projective clustering is to compute a set of $k$ subspaces, each of dimension
$j$, that minimizes the sum of _squared_ distances from each column in $W$ to
its _closest_ subspace from this set. Then, we can partition the columns of
$W$ into $k$ subsets according to their nearest subspace from this set. This
is a natural extension of SVD that solves this problem for the case of $k=1$.
However, this problem is known to be NP-hard, hence expensive approximation
algorithms are required to solve it, or alternatively, a local minimum
solution can be obtained using the Expectation-Maximization method (EM)
(Dempster et al., 1977).

A more robust version of the previous method is to minimize the sum of _non-
squared_ distances from the points to the subspaces. This approach is known to
be more robust toward outliers (“far away points”). Similarly to the original
variant (the case of squared distance), we can use the EM method to obtain a
“good guess” for a solution of this problem, however, the EM method requires
an algorithm that solves the problem for the case of $k=1$, i.e., computing
the subspace that minimizes the sum of (non-squared) distances from those
columns (for the sum of squared distances case, SVD is this algorithm).
Unfortunately, there is only approximation algorithms (Tukan et al., 2020;
Clarkson and Woodruff, 2015) for this case, and the deterministic versions are
expensive in terms of running time.

Furthermore, and probably more importantly, all of these methods cannot be
considered as structured compression since arbitrary clustering may require
re-shuffling the input tensors which could lead to significant slow-downs
during inference. For example, when compressing a fully-connected layer, the
arbitrary clustering may result in nonconsecutive neurons from the first layer
that are connected to the same neuron in the second layer, while neurons that
are between them are not. Hence, these layers can only have a large, sparse
instead of a small, dense representation.

To this end, we choose to use channel slicing, i.e., we simply split the
channels of the convolutional layer into $k$ chunks, where each chunk has at
most $c/k$ consecutive channels. Splitting the channels into consecutive
subsets (without allowing any arbitrary clustering) and applying the
factorization on each one results in a structurally compressed layer without
the need of special software/hardware support. Furthermore, this approach is
the fastest among all the others. Finally, while other approaches may give a
better initial guess for a compressed network in theory, in practice this is
not the case; see Figures 10. This is due to the global compression framework
(Section 2.2) which repeatedly utilizes the channel slicing.

We see that in practice, our method improve upon state-of-the-art techniques
and obtains smaller networks with higher accuracy without the use of those
complicated approaches that may result in sparse but not smaller network; see
Section C.3.

###  A.3 Compressing via SVD

As explained in Section 2.1, the weights of a convolutional layer (or a dense
layer) can be encoded into a matrix $W\in\mathbb{R}^{f\times ck_{1}k_{2}}$,
where $f$ and $c$ are the number of filters and channels in the layer,
respectively, and $k_{1}\times k_{2}$ is the size of the kernel. In order to
compress the matrix $W$ (and thus its corresponding layer) we aim to factor it
into a pair of smaller matrices $U\in\mathbb{R}^{f\times j}$ and
$V\in\mathbb{R}^{j\times ck_{1}k_{2}}$, such that $UV$ approximates the
original matrix operator $W$.

##### How to compute the matrices $U$ and $V$?

For simplicity, let $d=ck_{1}k_{2}$. We factor the matrix
$W\in\mathbb{R}^{f\times d}$ via SVD to obtain
$W=\tilde{U}\tilde{\Sigma}\tilde{V}$, where $\tilde{U}$ is an ${f\times f}$
orthogonal matrix, $\tilde{\Sigma}$ is an ${\displaystyle f\times d}$
rectangular diagonal matrix with non-negative real numbers on the diagonal,
and $\tilde{V}$ is an ${\displaystyle d\times d}$ orthogonal matrix.

To compute a $j$-rank approximation of $W$, we can simply define the following
$3$ matrices: $U\in\mathbb{R}^{f\times j}$,
$\overline{V}\in\mathbb{R}^{j\times d}$, and $\Sigma\in\mathbb{R}^{j\times
j}$, where $U$ is constructed by taking the first $j$ columns of $\tilde{U}$,
$\overline{V}$ by taking the first $j$ rows of $\tilde{V}$, and $\Sigma$ is a
diagonal matrix such that the $j$ entries on its diagonal are equal to the
first $j$ entries on the diagonal of $\tilde{\Sigma}$. Now we have that
${U}{\Sigma}\overline{V}$ is the $j$-rank approximation of $W$.

Finally, we can define $V=\Sigma\overline{V}$ to obtain a factorization of the
$j$-rank approximation of $W$ as $UV$.

###  A.4 Efficient Implementation of ALDS (Algorithm 1)

Our algorithm that is suggested in Section 2.2 aims at minimizing the maximum
relative error $\varepsilon\coloneqq\max_{\ell\in[L]}\varepsilon^{\ell}$
across the $L$ layers of the network as a proxy for the true cost, where
$\varepsilon^{\ell}$ is the theoretical maximum relative error in the
$\ell^{\text{th}}$:

$\varepsilon^{\ell}\coloneqq\frac{\left\lVert\hat{{{W}}}^{\ell}-W^{\ell}\right\rVert}{\left\lVert
W^{\ell}\right\rVert}.$

Through Algorithm 1, for every $\ell\in[L]$ we need to repeatedly compute
$\varepsilon^{\ell}$ as a function of $j^{\ell}$ and $k^{\ell}$. At Line 4, we
are given a guess for the optimal values of $k^{1},\dots,k^{L}$, and our goal
is to compute the values $j^{1},\dots,j^{L}$ such that the resulting errors
$\varepsilon^{1},\dots,\varepsilon^{L}$ are (approximately) equal in order to
minimize the maximum error $\max_{\ell\in[L]}\varepsilon^{\ell}$ while
achieving the desired global compression ratio. To this end, we guess a value
for $\varepsilon$ and for given $k^{1},\ldots,k^{L}$ pick the corresponding
$j^{1},\ldots,j^{L}$ such that $\varepsilon$ constitutes a tight upper bound
for the relative error in each layer. Based on the now resulting budget (and
consequently compression ratio) we can now improve our guess of $\varepsilon$,
e.g., via binary search or other types of root finding algorithms, until we
convergence to a value of $\varepsilon$ that corresponds to our desired
overall compression ratio.

Subsequently, for each layer we are given specific values of $k^{\ell}$ and
$j^{\ell}$, which implies that we are given a budget $b^{\ell}$ for every
layer $\ell\in[L]$. Subsequently, we re-assign the number of subspaces
$k^{\ell}$ and their ranks $j^{\ell}$ for each layer by iterating through the
finite set of possible values for $k^{\ell}$ (Line 7) and choosing the
combination of $j^{\ell}$, $k^{\ell}$ that minimizes the relative error for
the current layer budget $b^{\ell}$ (computed in Line 6).

We then iteratively repeat both steps until convergence (Lines 3-8).

Hence, instead of computing the cost of each layer at each step, we can save a
lookup table that stores the errors $\varepsilon^{\ell}$ for the possible
values of $k^{\ell}$ and $j^{\ell}$ of each layer. For every layer
$\ell\in[L]$, we iterate over the finite set of values of $k^{\ell}$, and we
split the matrix $W^{\ell}$ to $k^{\ell}$ matrices (according to the channel
slicing approach that is explained in Section 2.1), then we compute the SVD
factorization of each matrix from these $k^{\ell}$ matrices, and finally,
compute $\varepsilon^{\ell}$ that corresponds to a specific $j^{\ell}$
($k^{\ell}$ is already given) in $O(fd)$ time, where $f$ is the number of rows
in the weight matrix that corresponds to the $\ell$th layer and $d$ is the
number of columns.

Furthermore, instead of computing each option of $\varepsilon^{\ell}$ in
$O(fd)$ time, we use the upper bound derived in Theorem 1 to compute it in
$O(k)$ time and saving it in the lookup table. Specifically, we can express
the relative error as a function of the rank and we thus only need to solve
the underlying SVD for each layer once for each value of $k^{\ell}$. Without
Theorem 1 we would need to compute the relative error (operator norm) for each
pair $j^{\ell},k^{\ell}$ separately. This would in turn result in a
significant slowdown of the runtime of Algorithm 1. Hence, the combined use of
a look-up table and the application of Theorem 1 ensures a more efficient
implementation of Algorithm 1.

###  A.5 Additional Discussion of ALDS (Algorithm 1)

Below, we include additional details and clarification regarding Algorithm 1.

#### Overview

At a high-level, Algorithm 1 aims to find a local optimum for the optimization
procedure described in Equation (8). We hereby iteratively optimize for
$k^{1},\ldots,k^{L}$ and $j^{1},\ldots,j^{L}$. The step where we fix the set
of $k$’s and optimize for the set of $j$’s is Line 4, whereas in Line 7 we fix
the layer budget and optimize for the set of $k$’s. At each step the objective
is minimized. Thus for a fixed seed, ALDS converges to a local optimum of (8).
We then repeat the entire procedure multiple times with different random seeds
to improve the quality of the local optimum.

#### Line 4: $\textsc{OptimalRanks}(\mathbf{CR},k^{1},\ldots,k^{L})$

At this step we are given a guess for the optimal values of
$k^{1},\dots,k^{L}$, and our goal is to compute the values $j^{1},\dots,j^{L}$
that minimize the objective function described in Equation (8), i.e., the
maximum error $\max_{\ell\in[L]}\varepsilon^{\ell}$, while achieving the
desired global compression ratio $\mathbf{CR}$.

To find the optimal solution, we note the following. Recall that $k$’s are
fixed.

  1. 1.

The maximum error is minimized exactly when all errors are equal. To see that
this is indeed the case we can proceed by contradiction. Suppose we found an
optimal solution where all errors are not equal. Then we could use some of our
compression budget to add more parameters to the layer with the maximum error
while removing the same amount of parameters from the layer with minimum
error. Since adding more parameters improves the error we just lowered the
maximum error by adding more parameters to the layer with the maximum error.
Hence, this leads to a contradiction proving our initial statement.

  2. 2.

A given constant error across layers corresponds to a fixed compression ratio.
This should be very straightforward to see. Specifically, for a given layer
error we can find the corresponding rank and the rank implies how many
parameters the compressed layer will have. This then implies a fixed
compression ratio. Moreover, note that this relation is monotonic.

Both (1.) and (2.) together imply that we can use a binary search or some
other root finding algorithm to determine the corresponding constant error for
a desired compression ratio OptimalRanks. The solution of our binary search
will then be the corresponding set of $j$’s (ranks) for each layer that
minimizes the maximum error for a desired compression ratio and given set of
$k$’s (recall that we optimize for $k$’s separately).

#### Line 7: $\textsc{OptimalSubspaces}(b^{\ell})$

This step is fairly straightforward to follow. First, we note that for this
step we proceed on a per-layer basis. Here, for each layer we are given
specific values of $k^{\ell}$ and $j^{\ell}$, which implies that we are given
a budget $b^{\ell}$ for every layer $\ell\in[L]$. Subsequently, we re-assign
the number of subspaces $k^{\ell}$ and their ranks $j^{\ell}$ for each layer
$\ell$ as follow: We iterate through the finite set of possible values for
$k^{\ell}$, for every such value $k^{\ell}$ we pick its corresponding
$j^{\ell}$ such that the total size (number of parameters) of this layer is
(approximately) the given budget $b^{\ell}$. Now, for every pair of candidates
$k^{\ell}$ and $j^{\ell}$ we compute the relative error on this layer that is
caused after compression with respect to these values. Finally, we choose the
combination of $j^{\ell}$, $k^{\ell}$ that minimizes the relative error for
the current layer budget $b^{\ell}$. We then discard the values found for
$j^{1},\ldots,j^{L}$ and re-optimize them in the next iteration of
OptimalRanks.

Note that for OptimalSubspaces there is no monotonic relation between the
value of $k^{\ell}$ and the corresponding error like there is between the
value of $j^{\ell}$ and the error. Hence, we proceed on a per-layer basis
where we keep the per-layer budget constant during OptimalSubspaces as
described above.

#### Optimality

From the details of the two steps, it should be very clear that the cost is
decreasing at each step in the optimization procedure and we can thus conclude
that for each random seed Algorithm 1 converges to a local optimum (at which
point the cost will be non-increasing).

#### Even More Remarks

Note that above for OptimalRanks we assumed that the errors
($\varepsilon^{\ell}$’s) are continuous but they are actually discrete given
that they are a function of the rank which is discrete. However, as long as we
can ensure that the objective decreases at every iteration we can still reach
a local minimum.

Alternatively, we can solve the continuous relaxation of the above problem and
use a randomized rounding111https://en.wikipedia.org/wiki/Randomized_rounding
approach to get an approximately optimal solution.

In practice, however, we found that it is not necessary to add this additional
complication step since it is sufficient that the cost objective decreases at
every time step and we cannot hope to obtain a global optimum anyway (we can
only approximate it with repeating the optimization procedure with multiple
random seeds, which we do, see Algorithm 1).

###  A.6 Extensions of ALDS

As mentioned in Section 2.3 ALDS can be readily extended to any desired _set_
of low-rank compression techniques. Specifically, we can replace the local
step of Line 7 by a search over different methods, e.g., Tucker decomposition,
PCA, or other SVD compression schemes, and return the best method for a given
budget. In general, we may combine ALDS with any low-rank compression as long
as we can efficiently evaluate the per-layer error of the compression scheme.
Note that this essentially equips us with a framework to automatically choose
the per-layer decomposition technique fully automatically.

To this end, we test an extension of ALDS where in addition to searching over
multiple values of $k^{\ell}$ we simultaneously search over various flattening
schemes to convert a convolutional tensor to a matrix before applying SVD.

As before, let $\mathbf{\mathcal{W}}\in\mathbb{R}^{f\times
c\times\kappa_{1}\times\kappa_{2}}$ denote the weight tensor for a
convolutional layer with $f$ filters, $c$ input channels, and a
$\kappa_{1}\times\kappa_{2}$ kernel. Moreover, let $j$ denote the desired rank
of the decomposition. We consider the following schemes to automatically
search over:

  * •

Scheme 0: flatten the tensor to a matrix of shape $f\times
c\kappa_{1}\kappa_{2}$. The decomposed layers correspond to a $j\times
c\times\kappa_{1}\times\kappa_{2}$-convolution followed by a $f\times j\times
1\times 1$-convolution. This is the same scheme as used in ALDS.

  * •

Scheme 1: flatten the tensor to a matrix of shape $f\kappa_{1}\times
c\kappa_{2}$. The decomposed layers correspond to a $j\times c\times
1\times\kappa_{2}$-convolution followed by a $f\times j\times\kappa_{1}\times
1$-convolution.

  * •

Scheme 2: flatten the tensor to a matrix of shape $f\kappa_{2}\times
c\kappa_{1}$. The decomposed layers correspond to a $j\times
c\times\kappa_{1}\times 1$-convolution followed by a $f\times j\times
1\times\kappa_{2}$-convolution.

  * •

Scheme 3: flatten the tensor to a matrix of shape $f\kappa_{1}\kappa_{2}\times
c$. The decomposed layers correspond to a $j\times c\times 1\times
1$-convolution followed by a $f\times
j\times\kappa_{1}\times\kappa_{2}$-convolution.

We denote this method by ALDS+ and provide preliminary results in Section C.4.
We note that since ALDS+ is a generalization of ALDS its performance is at
least as good as the original ALDS. Moreover, our preliminary results actually
suggest that the extension clearly improves upon the empirical performance of
ALDS.

##  Appendix B Experimental Setup and Hyperparameters

Our experimental evaluations are based on a variety of network architectures,
data sets, and compression pipelines. In the following, we provide all
necessary hyperparameters to reproduce our experiments for each of the
datasets and respective network architectures.

All networks were trained, compressed, and evaluated on a compute cluster with
NVIDIA Titan RTX and NVIDIA RTX 2080Ti GPUs. The experiments were conducted
with PyTorch 1.7 and our code is fully open-sourced 222Code repository:
https://github.com/lucaslie/torchprune.

All networks are trained according to the hyperparameters outlined in the
respective original papers. During retraining, which is described in Section
B.5, we reuse the same hyperparameters.

Moreover, each experiment is repeated 3 times and we report mean and mean,
standard deviation in the tables and figures, respectively.

For each data set, we use the publicly available development set as test set
and use a 90%/5%/5% split on the train set to obtain a separate train and
_two_ validation sets. One validation set is used for data-dependent
compression methods, e.g., PCA (Zhang et al., 2015a); the other set is used
for early stopping during training.

###  B.1 Experimental Setup for CIFAR10

All relevant hyperparameters are outlined in Table 3. For each of the networks
we use the training hyperparameters outlined in the respective original
papers, i.e., as described by He et al. (2016), Simonyan and Zisserman (2014),
Huang et al. (2017), and Zagoruyko and Komodakis (2016) for ResNets, VGGs,
DenseNets, and WideResNets (WRN), respectively.

We add a warmup period in the beginning where we linearly scale up the
learning rate from 0 to the nominal learning rate to ensure proper training
performance in distributed training settings (Goyal et al., 2017).

During training we use the standard data augmentation strategy for CIFAR: (1)
zero padding from 32x32 to 36x36; (2) random crop to 32x32; (3) random
horizontal flip; (4) channel-wise normalization. During inference only the
normalization (4) is applied.

The compression ratios are chosen according to a geometric sequence with the
common ratio denoted by $\alpha$ in Table 3, i.e., the compression ratio for
iteration $i$ is determined by $1-\alpha^{i}$. The compression parameter
$n_{\text{seed}}$ denotes the number of seeds used to initialize Algorithm 1
for compressing with PP.

Table 3:  The experimental hyperparameters for training, compression, and
retraining for the tested CIFAR10 network architectures. “LR” and “LR decay”
hereby denote the learning and the (multiplicative) learning rate decay,
respectively, that is deployed at the epochs as specified. “$\\{x,\ldots\\}$”
indicates that the learning rate is decayed every $x$ epochs.

CIFAR10 Hyperparameters VGG16 Resnet20 DenseNet22 WRN-16-8 (Re-)Training Test
accuracy (%) 92.81 91.4 89.90 95.19 Loss cross-entropy cross-entropy cross-
entropy cross-entropy Optimizer SGD SGD SGD SGD Epochs 300 182 300 200 Warm-up
10 5 10 5 Batch size 256 128 64 128 LR 0.05 0.1 0.1 0.1 LR decay 0.5@{30, …}
0.1@{91, 136} 0.1@{150, 225} 0.2@{60, …} Momentum 0.9 0.9 0.9 0.9 Nesterov ✗ ✗
$\checkmark$ $\checkmark$ Weight decay 5.0e-4 1.0e-4 1.0e-4 5.0e-4 Compression
$\alpha$ 0.80 0.80 0.80 0.80 $n_{\text{seed}}$ 15 15 15 15

###  B.2 Experimental Setup for ImageNet

We report the relevant hyperparameters in Table 4. For ImageNet we consider
the networks architectures Resnet18 (He et al., 2016), AlexNet (Krizhevsky et
al., 2012), and MobileNetV2 (Sandler et al., 2018).

During training we use the following data augmentation: (1) randomly resize
and crop to 224x224; (2) random horizontal flip; (3) channel-wise
normalization. During inference, we use a center crop to 224x224 before (3) is
applied.

Note that for MobileNetV2 we deploy a lower initial learning rate during
retraining. Otherwise, all hyperparameters remain the same during retraining.

Table 4:  The experimental hyperparameters for training, compression, and
retraining for the tested ImageNet network architectures. “LR” and “LR decay”
hereby denote the learning and the (multiplicative) learning rate decay,
respectively, that is deployed at the epochs as specified. “$\\{x,\ldots\\}$”
indicates that the learning rate is decayed every $x$ epochs.

ImageNet Hyperparameters ResNet18 AlexNet MobileNetV2 (Re-)Training Top 1 Test
accuracy (%) 69.64 57.30 71.85 Top 5 Test accuracy (%) 88.98 80.20 90.33 Loss
cross-entropy cross-entropy cross-entropy Optimizer SGD SGD RMSprop Epochs 90
90 300 Warm-up 5 5 0 Batch size 256 256 768 LR 0.1 0.1 0.045 (1e-4) LR decay
0.1@{30, 60, 80} 0.1@{30, 60, 80} 0.98 per step Momentum 0.9 0.9 0.9 Nesterov
✗ ✗ ✗ Weight decay 1.0e-4 1.0e-4 4.0e-5 Compression $\alpha$ 0.80 0.80 0.80
$n_{\text{seed}}$ 15 15 15

###  B.3 Experimental Setup for Pascal VOC

In addition to CIFAR and ImageNet, we also consider the segmentation task from
Pascal VOC 2012 Everingham et al. (2015). We augment the nominal data training
data using the extra labels as provided by Hariharan et al. (2011). As network
architecture we consider a DeeplabV3 Chen et al. (2017) with ResNet50 backbone
pre-trained on ImageNet.

During training we use the following data augmentation pipeline: (1) randomly
resize (256x256 to 1024x1024) and crop to 513x513; (2) random horizontal flip;
(3) channel-wise normalization. During inference, we resize to 513x513 exactly
before the normalization (3) is applied.

We report both intersection-over-union (IoU) and Top1 test accuracy for each
of the compressed and uncompressed networks. The experimental hyperparameters
are summarized in Table 5.

Table 5:  The experimental hyperparameters for training, compression, and retraining for the tested VOC network architecture. “LR” and “LR decay” hereby denote the learning and the learning rate decay, respectively. Note that the learning rate is polynomially decayed after each step. Pascal VOC 2012 – Segmentation | Hyperparameters | DeeplabV3-ResNet50
---|---|---
(Re-)Training | IoU Test accuracy (%) | 69.84
Top 1 Test accuracy (%) | 94.25
Loss | cross-entropy
Optimizer | SGD
Epochs | 45
Warm-up | 0
Batch size | 32
LR | 0.02
LR decay | $\text{(1 - ``step''/``total steps'')}^{\text{0.9}}$
| Momentum | 0.9
| Nesterov | ✗
| Weight decay | 1.0e-4
Compression | $\alpha$ | 0.80
$n_{\text{seed}}$ | 15

###  B.4 Baseline Methods

We implement and compare against the following compression methods for our
baseline experiments:

  1. 1.

PCA (Zhang et al., 2015a) decomposes each layer based on principle component
analysis of the pre-activation (output of linear layer). We implement the
symmetric, linear version of their method. The per-layer compression ratio is
based on the greedy solution for minimizing the product of the per-layer
energy, where the energy is defined as the sum of singular values in the
compressed layer, see Equation (14) of Zhang et al. (2015a).

  2. 2.

SVD-Energy (Alvarez and Salzmann, 2017; Wen et al., 2017) decomposes each
layer via matrix folding akin to our SVD-based decomposition. The per-layer
compression ratio is found by keeping the relative energy reduction constant
across layers, where energy is defined as the sum of squared singular values.

  3. 3.

SVD (Denton et al., 2014) decomposes each layer via matrix folding akin to our
SVD-based decomposition. However, we hereby fix $k^{\ell}=1$ for all layers
$\ell\in[L]$ in order to provide a nominal comparison akin of “standard”
tensor decomposition. The per-layer compression ratio is kept constant across
all layers.

  4. 4.

L-Rank (Idelbayev and Carreira-Perpinán, 2020) decomposes each layer via
matrix folding akin to our SVD-based decomposition. The per-layer compression
is determined by minimizing a joint cost objective of the energy and the
computational cost of each layer, see Equation (5) of Idelbayev and Carreira-
Perpinán (2020) for details.

  5. 5.

FT Li et al. (2016) prunes the filters (or neurons) in each layer with the
lowest element-wise $\ell_{2}$-norm. The per-layer compression ratio is set
manually (constant in our implementation).

  6. 6.

PFP Liebenwein et al. (2020) prunes the channels with the lowest sensitivity,
where the data-dependent sensitivities are based on a provable notion of
channel pruning. The per-layer prune ratio is determined based on the
associated theoretical error guarantees.

###  B.5 Compress-Retrain Pipeline

Recall that our baseline experiments are based on the following unified
compress-retrain pipeline across all compression methods:

  1. 1.

Train for $e$ epochs according to the standard training schedule for the
respective network.

  2. 2.

Compress the network according to the chosen method.

  3. 3.

Retrain the network for the desired amount of $r$ epochs using the original
training hyperparameters from the epochs in the range $[e-r,e]$.

  4. 4.

Iteratively repeat 1.-3. after projecting the decomposed layers back
(optional).

In addition, we also consider experiments in the iterative learning rate
rewinding setting, where steps 2 and 3 are repeated iteratively (optional step
4).

While various papers combine their compression methods with different retrain
schedules we unify the compress-retrain pipeline across all tested methods for
our baseline experiments to ensure that results are comparable. Note that the
implemented compress-retrain pipeline as originally introduced by Renda et al.
(2020) has been shown to yield consistently good compression results across
various compression/pruning setups (unstructured, structured) and tasks
(computer vision, NLP). Hence, we choose to concentrate on that particular
pipeline.

##  Appendix C Additional Experimental Results

In this section, we provide additional results of our experimental
evaluations.

###  C.1 Complete Tables for One-shot Compression Experiments from Section 3.1

Table 6:  The maximal compression ratio for which the drop in test accuracy is
at most some pre-specified $\delta$ on CIFAR10. The table reports compression
ratio in terms of parameters and FLOPs, denoted by CR-P and CR-F,
respectively. When the desired $\delta$ was not achieved for any compression
ratio in the range the fields are left blank. The top values achieved for CR-P
and CR-F are bolded.

CIFAR10 Model Prune Method $\delta=0.0\%$ $\delta=0.5\%$ $\delta=1.0\%$
$\delta=2.0\%$ $\delta=3.0\%$ Top1 Acc. CR-P CR-F Top1 Acc. CR-P CR-F Top1
Acc. CR-P CR-F Top1 Acc. CR-P CR-F Top1 Acc. CR-P CR-F ResNet20 Top1: 91.39
ALDS +0.09 64.58 55.95 -0.47 74.91 67.86 -0.68 79.01 71.59 -1.88 87.68 83.23
-2.59 89.65 85.32 PCA +0.16 39.98 38.64 -0.11 49.88 48.67 -0.58 58.04 57.21
-1.41 70.54 70.78 -2.11 75.23 76.01 SVD-Energy +0.14 40.22 39.38 -0.21 49.88
49.08 -0.83 57.95 57.15 -1.52 64.76 64.10 -2.17 70.47 70.01 SVD +0.24 14.36
15.34 -0.29 39.81 38.95 -0.90 49.19 50.21 -1.08 57.47 57.80 -2.88 70.14 71.31
L-Rank +0.14 15.00 29.08 -0.44 28.71 54.89 -0.44 28.71 54.89 -1.56 49.87 72.57
-2.82 64.81 80.80 FT +0.15 15.29 16.66 -0.32 39.69 39.57 -0.75 57.77 55.85
-1.88 74.89 71.76 -2.71 79.29 76.74 PFP +0.12 28.74 20.56 -0.28 40.28 30.06
-0.85 58.26 46.94 -1.56 70.49 59.78 -2.57 79.28 69.27 VGG16 Top1: 92.78 ALDS
+0.29 94.89 83.94 -0.11 95.77 86.23 -0.52 97.01 88.95 -0.52 97.03 88.95 -0.52
97.03 88.95 PCA +0.47 87.74 81.05 -0.02 89.72 85.84 -0.02 89.72 85.84 -1.12
91.37 89.57 -1.12 91.37 89.57 SVD-Energy +0.35 79.21 78.70 -0.08 82.57 81.32
-0.83 87.74 85.36 -1.22 89.71 87.13 -2.08 91.37 88.58 SVD +0.29 70.35 70.13
+0.29 70.35 70.13 -0.74 75.18 75.13 -1.58 82.58 82.39 -1.58 82.58 82.39 L-Rank
+0.35 82.56 69.67 -0.35 85.38 75.86 -0.35 85.38 75.86 -0.35 85.38 75.86 -0.35
85.38 75.86 FT +0.17 64.81 62.16 -0.47 79.13 78.44 -0.87 82.61 82.41 -1.95
89.69 89.91 -2.66 91.35 91.68 PFP +0.16 89.73 74.61 -0.47 94.87 84.76 -0.96
96.40 88.38 -1.33 97.02 90.25 -1.33 97.02 90.25 DenseNet22 Top1: 89.88 ALDS
+0.17 48.85 51.90 -0.32 56.84 61.98 -0.54 63.83 69.68 -1.87 69.67 74.48 -1.87
69.67 74.48 PCA +0.20 14.67 34.55 +0.20 14.67 34.55 -0.73 28.83 57.02 -0.73
28.83 57.02 -2.75 40.51 70.03 SVD-Energy -0.29 15.16 19.34 -0.29 15.16 19.34
-1.28 28.62 33.26 -2.21 40.20 44.72 SVD +0.13 15.00 15.33 +0.13 15.00 15.33
-0.87 26.73 27.41 -0.87 26.73 27.41 -2.51 37.99 39.25 L-Rank +0.26 14.98 35.21
+0.26 14.98 35.21 -0.90 28.67 63.55 -1.82 40.33 73.45 -1.82 40.33 73.45 FT
+0.15 15.49 16.70 -0.24 28.33 29.50 -0.24 28.33 29.50 -1.46 51.10 51.03 -2.40
64.12 63.09 PFP +0.00 28.68 32.60 -0.44 40.24 43.37 -0.70 49.67 51.94 -1.36
58.20 58.21 -2.43 65.17 64.50 WRN16-8 Top1: 95.21 ALDS +0.05 28.67 13.00 -0.42
87.77 79.90 -0.88 92.75 87.39 -1.53 95.69 92.50 -2.23 97.01 95.51 PCA +0.14
15.00 7.98 -0.49 85.33 83.45 -0.96 91.33 90.23 -1.76 93.90 93.15 -2.45 94.87
94.30 SVD-Energy +0.29 15.01 6.92 -0.41 64.75 60.94 -0.81 85.38 83.52 -1.90
91.38 90.04 -2.46 92.77 91.58 SVD -0.96 40.20 39.97 -1.63 70.48 70.49 -1.63
70.48 70.49 L-Rank +0.25 14.99 6.79 -0.45 49.86 58.00 -0.88 75.20 82.26 -1.70
87.73 92.03 -2.18 89.72 93.51 FT +0.03 64.54 61.53 -0.32 82.33 75.97 -0.95
89.70 83.52 -1.78 94.91 90.82 -2.86 96.42 93.33 PFP +0.05 57.92 54.74 -0.44
85.33 80.68 -0.77 89.71 85.16 -1.69 95.65 92.60 -2.40 96.96 94.36

Table 7:  The maximal compression ratio for which the drop in test accuracy is
at most $\delta=1.0\%$ for ResNet20 (CIFAR10) for various amounts of
retraining (as indicated). The table reports compression ratio in terms of
parameters and FLOPs, denoted by CR-P and CR-F, respectively. When the desired
$\delta$ was not achieved for any compression ratio in the range the fields
are left blank. The top values achieved for CR-P and CR-F are bolded.

CIFAR10 Model Prune Method $r=0\%\,e$ $r=5\%\,e$ $r=10\%\,e$ $r=25\%\,e$
$r=50\%\,e$ $r=100\%\,e$ Top1 Acc. CR-P CR-F Top1 Acc. CR-P CR-F Top1 Acc.
CR-P CR-F Top1 Acc. CR-P CR-F Top1 Acc. CR-P CR-F Top1 Acc. CR-P CR-F ResNet20
Top1: 91.39 ALDS -0.13 14.82 7.03 -0.53 35.87 26.27 -0.73 43.12 33.65 -0.65
43.14 33.33 -0.86 62.39 54.40 -0.88 81.29 74.23 PCA -0.74 19.31 18.64 -0.70
19.34 18.44 -0.59 36.21 35.19 -0.74 60.29 59.81 SVD-Energy -0.64 14.99 14.09
-0.70 19.61 18.81 -0.59 19.61 18.81 -0.73 43.46 42.49 -0.46 55.25 54.59 SVD
-0.83 14.36 15.34 -0.58 14.36 15.34 -0.69 28.21 29.11 -0.77 51.58 51.52 L-Rank
-0.64 15.00 29.08 -0.33 15.00 29.08 -0.44 28.71 54.89 FT -0.67 15.29 16.66
-0.69 27.76 28.40 -0.75 57.77 55.85 PFP -0.77 14.88 9.61 -0.83 32.71 23.85
-0.54 52.89 42.04

Table 8:  The maximal compression ratio for which the drop in test accuracy is
at most some pre-specified $\delta$ on ResNet18 and MobileNetV2 (both
ImageNet). The table reports compression ratio in terms of parameters and
FLOPs, denoted by CR-P and CR-F, respectively. When the desired $\delta$ was
not achieved for any compression ratio in the range the fields are left blank.
The top values achieved for CR-P and CR-F are bolded.

ImageNet Model Prune Method $\delta=0.0\%$ $\delta=0.5\%$ $\delta=1.0\%$
$\delta=2.0\%$ $\delta=3.0\%$ Top1/5 Acc. CR-P CR-F Top1/5 Acc. CR-P CR-F
Top1/5 Acc. CR-P CR-F Top1/5 Acc. CR-P CR-F Top1/5 Acc. CR-P CR-F ResNet18
Top1: 69.62 Top5: 89.08 ALDS +0.08/+0.18 59.43 33.08 -0.15/-0.03 66.73 44.14
-0.97/-0.49 72.73 52.81 -1.63/-0.76 77.62 60.46 -2.53/-1.44 81.75 67.62 PCA
-0.88/-0.43 9.97 12.02 -1.84/-0.94 50.43 51.07 -2.34/-1.23 59.38 60.08 SVD-
Energy -1.91/-0.93 50.47 51.46 -2.82/-1.53 59.42 60.24 SVD -1.53/-0.83 50.44
50.38 -2.06/-1.03 59.36 59.33 L-Rank -0.72/-0.26 10.01 32.40 -0.72/-0.26 10.01
32.40 -2.30/-1.26 26.25 58.59 FT +0.17/+0.21 9.96 10.78 +0.17/+0.21 9.96 10.78
-0.66/-0.32 26.12 26.62 -1.72/-0.81 39.58 37.89 -2.82/-1.55 50.62 45.74 PFP
+0.25/+0.33 10.04 7.72 -0.38/-0.15 26.35 19.14 -0.38/-0.15 26.35 19.14
-0.38/-0.15 26.35 19.14 -2.80/-1.84 50.41 37.59 MobileNetV2 Top1: 71.85 Top5:
90.33 ALDS -1.53/-0.73 32.97 11.01 -1.53/-0.73 32.97 11.01 PCA -0.87/-0.55
20.91 0.26 -0.87/-0.55 20.91 0.26 -0.87/-0.55 20.91 0.26 SVD-Energy
-1.27/-0.57 20.02 8.57 -2.50/-1.45 32.72 20.83 SVD L-Rank FT -1.73/-0.85 21.31
20.23 -2.68/-1.46 32.75 28.23 PFP -0.97/-0.40 20.02 7.96 -1.44/-0.51 32.74
13.49 -2.17/-0.85 43.32 19.21

Table 9:  The maximal compression ratio for which the drop in test accuracy is
at most $\delta=1.0\%$ for ResNet18 (ImageNet) for various amounts of
retraining (as indicated). The table reports compression ratio in terms of
parameters and FLOPs, denoted by CR-P and CR-F, respectively. When the desired
$\delta$ was not achieved for any compression ratio in the range the fields
are left blank. The top values achieved for CR-P and CR-F are bolded.

ImageNet Model Prune Method $r=0\%\,e$ $r=5\%\,e$ $r=10\%\,e$ $r=25\%\,e$
$r=50\%\,e$ $r=100\%\,e$ Top1/5 Acc. CR-P CR-F Top1/5 Acc. CR-P CR-F Top1/5
Acc. CR-P CR-F Top1/5 Acc. CR-P CR-F Top1/5 Acc. CR-P CR-F Top1/5 Acc. CR-P
CR-F ResNet18 Top1: 69.62 Top5: 89.08 ALDS -0.54/-0.24 39.57 15.20 -0.48/-0.24
50.46 23.70 -0.72/-0.30 53.50 26.90 -0.64/-0.31 61.90 36.58 -0.40/-0.23 68.78
47.23 -0.73/-0.31 70.73 49.85 PCA -inf/-inf 3.33 3.99 -0.80/-0.38 26.21 27.53
-0.76/-0.51 39.53 40.45 -inf/-inf 6.65 8.14 SVD-Energy -0.28/-0.14 10.00 11.05
-0.25/-0.12 10.00 11.05 -0.55/-0.25 26.24 27.14 -0.66/-0.33 39.56 40.48
-inf/-inf 3.33 3.66 SVD -0.32/-0.13 9.98 9.94 -0.19/-0.07 9.98 9.94
-0.71/-0.34 30.63 30.82 -0.59/-0.32 39.53 39.51 -inf/-inf 3.33 3.31 L-Rank
-inf/-inf 3.34 10.88 -0.40/-0.23 10.01 32.40 -0.16/+0.03 10.01 32.40
-0.72/-0.26 10.01 32.40 FT -inf/-inf 3.36 3.75 -0.21/-0.15 9.95 10.78
-0.83/-0.46 26.29 26.57 -0.66/-0.32 26.12 26.62 PFP -inf/-inf 3.34 2.37
-0.14/-0.13 9.96 7.72 -0.37/-0.31 20.76 15.14 -0.38/-0.15 26.35 19.14

Table 10:  The maximal compression ratio for which the drop in test accuracy
is at most some pre-specified $\delta$ on DeeplabV3-ResNet50 (Pascal VOC2012).
The table reports compression ratio in terms of parameters and FLOPs, denoted
by CR-P and CR-F, respectively. When the desired $\delta$ was not achieved for
any compression ratio in the range the fields are left blank. The top values
achieved for CR-P and CR-F are bolded.

VOCSegmentation2012 Model Prune Method $\delta=0.0\%$ $\delta=0.5\%$
$\delta=1.0\%$ $\delta=2.0\%$ $\delta=3.0\%$ IoU/Top1 Acc. CR-P CR-F IoU/Top1
Acc. CR-P CR-F IoU/Top1 Acc. CR-P CR-F IoU/Top1 Acc. CR-P CR-F IoU/Top1 Acc.
CR-P CR-F DeeplabV3-ResNet50 IoU: 68.16 Top1: 94.25 ALDS +0.14/-0.15 64.38
64.11 +0.14/-0.15 64.38 64.11 +0.14/-0.15 64.38 64.11 -1.22/-0.36 71.36 70.89
-2.76/-0.61 76.96 76.37 PCA -0.26/-0.02 31.59 31.63 -0.88/-0.24 55.68 55.82
-1.74/-0.39 64.33 64.54 -2.54/-0.46 71.29 71.63 SVD-Energy -1.88/-0.47 31.61
32.27 -2.78/-0.62 44.99 45.60 SVD +0.01/-0.02 14.99 14.85 -0.28/-0.18 31.64
31.51 -0.89/-0.25 45.02 44.95 -1.97/-0.50 64.42 64.42 -1.97/-0.50 64.42 64.42
L-Rank -0.42/-0.09 44.99 45.02 -0.42/-0.09 44.99 45.02 -1.29/-0.33 55.74 56.01
-2.50/-0.57 64.39 64.82 FT PFP +0.01/-0.05 31.79 30.62 -0.49/-0.21 45.17 43.93
-0.84/-0.32 55.78 54.61 -0.84/-0.32 55.78 54.61 -2.43/-0.61 64.47 63.41

###  C.2 Complete ImageNet Benchmark Results from Section 3.2

Results are provided in Table 11.

Table 11: AlexNet and ResNet18 Benchmarks on ImageNet. We report Top-1, Top-5 accuracy and percentage reduction in terms of parameters and FLOPs denoted by CR-P and CR-F, respectively. Best results with less than 0.5% accuracy drop are bolded. | Method |  $\Delta$-Top1 |  $\Delta$-Top5 | CR-P (%) | CR-F (%)
---|---|---|---|---|---
ResNet18, Top1, 5: 69.64%, 88.98% | ALDS (Ours) | +0.41 | +0.37 | 66.70 | 42.70
ALDS (Ours) | -0.38 | +0.04 | 75.00 | 64.50
ALDS (Ours) | -0.90 | -0.25 | 78.50 | 71.50
ALDS (Ours) | -1.37 | -0.56 | 80.60 | 76.30
MUSCO (Gusak et al., 2019) | -0.37 | -0.20 | N/A | 58.67
TRP1 (Xu et al., 2020) | -4.18 | -2.5 | N/A | 44.70
TRP1+Nu (Xu et al., 2020) | -4.25 | -2.61 | N/A | 55.15
TRP2+Nu (Xu et al., 2020) | -4.3 | -2.37 | N/A | 68.55
PCA (Zhang et al., 2015b) | -6.54 | -4.54 | N/A | 29.07
Expand (Jaderberg et al., 2014) | -6.84 | -5.26 | N/A | 50.00
PFP (Liebenwein et al., 2020) | -2.26 | -1.07 | 43.80 | 29.30
SoftNet (He et al., 2018) | -2.54 | -1.2 | N/A | 41.80
Median (He et al., 2019) | -1.23 | -0.5 | N/A | 41.80
Slimming (Liu et al., 2017) | -1.77 | -1.19 | N/A | 28.05
Low-cost (Dong et al., 2017) | -3.55 | -2.2 | N/A | 34.64
Gating (Hua et al., 2018) | -1.52 | -0.93 | N/A | 37.88
FT (He et al., 2017) | -3.08 | -1.75 | N/A | 41.86
DCP (Zhuang et al., 2018) | -2.19 | -1.28 | N/A | 47.08
FBS (Gao et al., 2018) | -2.44 | -1.36 | N/A | 49.49
AlexNet, Top1, 5: 57.30%, 80.20% | ALDS (Ours) | +0.10 | +0.45 | 92.00 | 76.10
ALDS (Ours) | -0.21 | -0.36 | 93.0 | 77.9
ALDS (Ours) | -0.41 | -0.54 | 93.50 | 81.4
Tucker (Kim et al., 2015a) | N/A | -1.87 | N/A | 62.40
Regularize (Tai et al., 2015) | N/A | -0.54 | N/A | 74.35
Coordinate (Wen et al., 2017) | N/A | -0.34 | N/A | 62.82
Efficient (Kim et al., 2019) | -0.7 | -0.3 | N/A | 62.40
L-Rank (Idelbayev et al., 2020) | -0.13 | -0.13 | N/A | 66.77
NISP (Yu et al., 2018) | -1.43 | N/A | N/A | 67.94
OICSR (Li et al., 2019a) | -0.47 | N/A | N/A | 53.70
Oracle (Ding et al., 2019) | -1.13 | -0.67 | N/A | 31.97

###  C.3 Ablation Study

In order to gain a better understanding of the various aspects of our method
we consider an ablation study where we selectively turn off various features
of ALDS. Specifically, we compare the full version of ALDS to the following
variants:

  1. 1.

ALDS-Error solves for the optimal ranks (Line 4 of Algorithm 1) for a desired
set of values for $k^{1},\ldots,k^{L}$. We test
$k^{\ell}=3,\,\forall\ell\in[L]$. This variant tests the benefits of varying
the number of subspaces compared to fixing them to a desired value.

  2. 2.

SVD-Error corresponds to ALDS-Error with $k^{\ell}=1,\,\forall\ell\in[L]$.
This variants tests the benefits of having multiple subspaces in the first
places in the context error-based allocation of the per-layer compression
ratio.

  3. 3.

ALDS-Simple picks the ranks in each layer for a desired set of values of
$k^{1},\ldots,k^{L}$ such that the per-layer compression ratio is constant. We
test $k^{\ell}=3,\,\forall\ell\in[L]$, and $k^{\ell}=5,\,\forall\ell\in[L]$.
This variant tests the benefits of allocating the per-layer compression ratio
according to the layer error compared to a simple constant heuristic.

  4. 4.

Messi proceeds like ALDS-Simple but replaces the subspace clustering with
projective clustering (Maalouf et al., 2021). We test
$k^{\ell}=3,\,\forall\ell\in[L]$. This variant tests the disadvantages of
having a simple subspace clustering technique (channel slicing) compared to
using a more sophisticated technique.

We note that ALDS-Simple with $k^{\ell}=1,\,\forall\ell\in[L]$ corresponds to
the SVD comparison method from the previous sections.

We study the variations on a ResNet20 trained on CIFAR10 in two settings:
compression only and one-shot compress+retrain. The results are presented in
Figures 10. We highlight that the complete variant of our algorithm (ALDS)
consistently outperforms the weaker variants providing empirical evidence on
the effectiveness of each of the core components of ALDS.

We note that varying the number of subspaces for each layer in order to
optimally assign a value of $k^{\ell}$ in each layer is crucial in improving
our performance. This is apparent from the comparison between ALDS, ALDS-
Error, and SVD-Error: having a fixed value for k yields sub-optimal results.

Picking an appropriate notion of cost (maximum relative error) is furthermore
preferred over simple heuristics such a constant per-layer compression ratio.
Specifically, the main difference between ALDS-Error and ALDS-Simple is the
way how the ranks are determined for a given set of $k$’s: ALDS-Error
optimizes for the error-based cost function while ALDS-Simple relies on a
simple constant per-layer compression ratio heuristic. In practice, ALDS-Error
outperforms ALDS-Simple across all tested scenarios.

Finally, we test the disadvantages of using a simple subspace clustering
method. To this end, we compare ALDS-Simple and Messi for fixed values of $k$.
While in some scenarios, particularly without retraining, Messi provides
modest improvements over ALDS-Simple, the improvement is negligible for most
settings. Moreover, note that Messi requires an expensive approximation
algorithm as explained in Section A.2. This would in turn prevent us from
incorporating Messi into the full ALDS framework in a computationally
efficient manner. However, as apparent from the ablation study we exhibit the
most performance gains for features related to global considerations instead
of local, per-layer improvements. In addition, we should also note that Messi
does not emit a structured reparameterization thus requires specialized
software or hardware to obtain speed-ups. Consequently, we may conclude that
channel slicing is the appropriate clustering technique in our context.

(a) no retraining ($r=0$)

(b) one-shot ($r=e$)

Figure 10:  The difference in test accuracy (“Delta Top1 Test Accuracy”) for
various target compression ratios, ALDS-based/ALDS-related methods, and
networks on CIFAR10.

###  C.4 Extensions of ALDS

We test and compare ALDS with ALDS+ (see Section A.6) to investigate the
performance gains we can obtain from generalizing our local step to search
over multiple decomposition schemes. We run one-shot compress-only experiments
on ResNet20 (CIFAR10) and ResNet18 (ImageNet).

The results are shown in Figure 11. We find that ALDS+ can significantly
increase the performance-size trade-off compared to our standards ALDS method.
This is expected since by generalizing the local step of ALDS we are
increasing the search space of possible decomposition solution. Using our ALDS
framework we can efficiently and automatically search over the increased
solution space. We envision that our observations will invigorate future
research into the possibility of not only choosing the optimal per-layer
compression ratio but also the optimal compression scheme.

(a) ResNet20 (CIFAR10)

(b) ResNet18 (ImageNet)

Figure 11:  The difference in test accuracy (“Delta Top1 Test Accuracy”) for
various target compression ratios, ALDS-based/ALDS-related methods, and
networks on CIFAR10. The networks were compressed once and not retrained
afterwards.