## QUANTIZED SPARSE PCA FOR NEURAL NETWORK
### WEIGHT COMPRESSION

**Anonymous authors**
Paper under double-blind review

ABSTRACT

In this paper, we introduce a novel method of weight compression. In our method,
we store weight tensors as sparse, quantized matrix factors, whose product is computed on the fly during inference to generate the target model’s weight tensors.
The underlying matrix factorization problem can be considered as a quantized
sparse PCA problem and solved through iterative projected gradient descent methods. Seen as a unification of weight SVD, vector quantization and sparse PCA,
our method achieves or is on par with state-of-the-art trade-offs between accuracy
and model size. Our method is applicable to both moderate compression regime,
unlike vector quantization, and extreme compression regime.

1 INTRODUCTION

Deep neural networks have achieved state-of-the-art results in a wide variety of tasks. However,
deployment remains challenging due to their large compute and memory requirements. Neural
networks deployed on edge devices such as mobile or IoT devices are subject to stringent compute
and memory constraints, while networks deployed in the cloud do not suffer such constraints but
might suffer excessive latency or power consumption.

To reduce neural network memory and compute footprint, several approaches have been introduced
in literature. Methods related to our approach, as well as their benefits and downsides, are briefly
introduced in this section and described in more detail in the related works section. Tensor factor_ization approaches (Denil et al., 2013) replace a layer in a neural network with two layers, whose_
weights are low-rank factors of the original layer’s weight tensor. This reduces the number of parameters and multiply-add operations (MACs), but since the factorizations are by design restricted
to those that can be realized as individual layers, potential for compression is limited. By pruning
a neural network (Louizos et al., 2017; He et al., 2017), individual weights are removed. Pruning
has shown to yield moderate compression-accuracy trade-offs. Due to the overhead required to keep
track of which elements are pruned, real yield of (unstructured) pruning is lower than the pruning
ratio. An exception to this is structured pruning, in which entire neurons are removed from a network, and weight tensors can be adjusted accordingly. However, achieving good compression ratios
at reasonable accuracy using structured pruning has proven difficult. Scalar quantization (Jacob
et al., 2018; Nagel et al., 2021) approximates neural network weights with fixed-point values, i.e.,
integer values scaled by a fixed floating point scalar. Scalar quantization has shown to yield high
accuracy at reasonable compression ratios, e.g., 8 bit quantization yields a 4x compression ratio and
virtually no accuracy degradation on many networks. However, scalar quantization does not yield
competitive compression vs accuracy trade-offs at high compression ratios. Vector quantization
(Stock et al., 2019; Martinez et al., 2021) approximates small subsets of weights, e.g., individual
3 × 3 filters in convolutional weight tensors, by a small set of codes. This way, the storage can be
reduced by storing the codebook and one code index for each original vector, instead of the individual weights. While vector quantization can achieve high compression with moderate accuracy loss,
these methods usually struggle to reach the accuracy of uncompressed models in low compression
regimes.

In this paper, we provide a novel view on tensor factorization. Instead of restricting factorization to
those that can be realized as two separate neural network layers, we show that much higher compression ratios can be achieved by shifting the order of operations. In our method, we find a factorization
**C, Z for an original weight tensor W, such that the matrix product CZ closely approximates the**


-----

a1

0

a3

a4


c1

0

0

c4


d1

d2

0

d4


b2

b3


Quantized

Sparse PCA


Tile and

reshape


Weight tensor
!!"#[×!]$%[×ℎ×$]


Weight tensor tiled and
reshaped to %×&; & ≫%


C, shape %×); ) < % Z, shape )×&; & ≫); sparse


Figure 1: An illustration of application of Quantized Sparse PCA to a convolutional weight tensor.
The weight tensor is reshaped into a matrix of shape d×n and factorized into a codebook C ∈ R[d][×][k]
and a latent Z ∈ R[k][×][n]. Both factors are quantized while only Z is sparse. During inference the
arrows are followed backwards: the reshaped and tiled matrix is computed from the product of the
factors C and Z. The result is reshaped into the original weight tensor.

reshape Weight tensor tiled and Sparse PCA matrix

original weight tensor. The compression is then pushed further by obtaining quantized factors andreshaped to %×&; & ≫% %×);

Z matrix (sparse)

)×&; & ≫)

) < %
# *

additionally sparse Z. During inference, the product CZ is computed first, and its result is reshaped

Sparse PCA

back into the original weight tensor’s shape, and used for the following computations. This approach
allows the use of an arbitrary factorization of the original weight tensor.Weight tensor

**C and Z**

Tile and

reshape

additionally sparse Z

!!"#[×!]$%[×ℎ×$] & = !!"#[×!]$%[×ℎ×$/%]

We show that this approach outperforms or is on par with vector quantization in high compression regimes, yet extends to scalar quantization levels of compression-accuracy trade-offs for lower
compression ratios.

Our contributions in this paper are as follows:

-  We show that the problem of tensor factorization and vector quantization can be formulated
in a unified way as quantized sparse principle component analysis (PCA) problem.

-  We propose an iterative projected gradient descent method to solve the quantized sparse
PCA problem.

-  Our experimental results demonstrate the benefits of this approach. By simultaneously
solving tensor factorization and vector quantization problem, we can achieve better accuracy than vector quantization in low compression regimes, and higher compression ratios
than scalar quantization approaches at moderate loss in accuracy.

2 RELATED WORK

**SVD-based methods and tensor decompositions SVD decomposition was first used to demon-**
strate redundacy in weight parameters in neural networks in Denil et al. (2013). Later several methods for reducing the inference time based on SVD decomposition were suggested (Denton et al.,
2014; Jaderberg et al., 2014). A similar technique was proposed for gradients compression in dataparallel distributed optimization by Vogels et al. (2019). The main difference between these methods
is the way 4D weights of a convolutional layer is transformed into a matrix which leads to different
shapes of the convolutional layers in the resulting decomposition. Following a similar direction,
several works focus on higher-order tensor decomposition methods which lead to introducing of
three or four convolutional layers (Lebedev et al., 2014; Kim et al., 2015; Su et al., 2018).

**Weight pruning** A straightforward approach to reducing neural network model size is removing
a percentage of weights. A spectrum of weight pruning approaches of different granularity has
been introduced in the literature. Structured pruning approaches such as He et al. (2017) kill entire
channels of the weights, while unstructured pruning approaches (Louizos et al., 2017; Zhu & Gupta,
2017; Neklyudov et al., 2017; Dai et al., 2018) focus on individual values. A recent survey on
unstructured pruning is provided in Gale et al. (2019).

**Scalar quantization and mixed precision training** By quantizing neural network weights to
lower bitwidths, model footprint can be reduced as well, as each individual weight requires fewer


-----

bits to be stored. For example, quantizing 32 bit floating points weight to 8 bit fixed point weights
yields a 4x compression ratio. Most quantization approaches use the straight-through estimator
(STE) for training quantized models (Bengio et al. (2013); Krishnamoorthi (2018)). One way to further improve the accuracy of quantized models is learning the quantization scale and offset jointly
with the network parameters (Esser et al. (2019); Bhalgat et al. (2020)). A recent survey on practical
quantization approaches can be found in Nagel et al. (2021).

In order to improve the accuracy of quantized models, several methods suggest using mixed precision quantization. The work by Uhlich et al. (2019) introduced an approach on learning integer
bit-width for each layer using STE. Using non-uniform bit-width allows the quantization method to
use lower bit-width for more compressible layers of the network. Several works (van Baalen et al.,
2020; Dong et al., 2019; Wang et al., 2019) improve upon the approach by Uhlich et al. (2019) by
using different methods for optimization over the bit-widths.

**Vector quantization. Several works use vector quantization approach for compression of weights**
of convolutional and fully connected layers (Gong et al. (2014); Martinez et al. (2021); Fan et al.
(2020); Stock et al. (2019); Wu et al. (2016)). The convolutional weight tensors are reshaped into
matrices, then K-means methods is applied directly on the rows or columns. Besides weight compression, the work by Wu et al. (2016) suggests using vector quantization for reducing the inference
time by reusing parts of the computation.

Recently several works suggested improvements on the basic vector quantization approach. Dataaware vector quantization which improves the clustering method by considering input activation data
is demonstrated to improve the accuracy of the compressed models by Stock et al. (2019). Another
direction is introducing a permutation to the weight matrices which allows to find subsets of weights
which are more compressible (Martinez et al., 2021). An inverse permutation is applied at the output
of the corresponding layers to preserve the original output of the model.

Besides weights compression problem, various improved vector quantization methods were applied
in image retrieval domain in order to accelerate scalar product computation for image descriptors (Chen et al. (2010); Ge et al. (2013); Norouzi & Fleet (2013)). In particular, additive quantization method which we will show is related to quantized sparse PCA was introduced Babenko
& Lempitsky (2014). Surveys on vector quantization methods are provided in Matsui et al. (2018);
Gersho & Gray (2012).

**Sparse PCA. Introduced in Zou et al. (2006), sparse PCA can be solved by a plethora of algorithms.**
The method proposed in this paper can be considered as an instance of thresholding algorithms (Ma,
2013). Although soft-thresholding methods are prevalent in the literature, we adopt an explicit
projection step using hard thresholding to have direct control over the compression ration. Note that
sparse PCA can be extended to include additional structures with sparsity (Jenatton et al., 2010; Lee
et al., 2006).
3 METHOD

In this section, we describe the main algorithm, which can be considered as sparse quantized principle component analysis (PCA).
3.1 QUANTIZED SPARSE PCA
Consider a weight tensor of a convolutional layer W ∈ R[f][out][×][f][in][×][h][×][w], where fin, fout are the
number of input and output feature maps, and h, w are the spatial dimensions of the filter. We
reshape it into a matrix **W ∈** R[d][×][n], where d is the tile size and n is the number of tiles. For the
reshape, we consider the dimensions in the order fout, fin, h, w in our experiments. The goal is to
factorize **W into the product of two matrices as follows:[f]**

**W = CZ,** (1)

[f]

where C R[d][×][k] is the codebook, and Z R[k][×][n] is the set of linear coefficients, or a latent variable
_∈_ _∈_ f
(k < d < n). Following the standard PCA method, we factorize the zero mean version of **W. With**
this decomposition, every column of **W, denoted by** **W:,i, is a linear combination of k codebook**
vectors (columns of C): [f]

_k_

[f] [f]

**W:,i =** _ZjiC:,j,_ (2)

_j=1_

X

f


-----

where C:,j is the j-th column of C. This decomposition problem is an instance of sparse PCA
methods (Zou et al. (2006)). For network compression, we are additionally interested in quantized
matrices C and Z. The quantization operation for an arbitrary C and Z is defined as follows:

**Cq = Qc(C; sc, bc),** (3)
**Zq = Qz(Z; sz, bz),** (4)

where bc,bz are the quantization bit-widths, and sc and sz are the quantization scale vectors for C
and Z, respectively. We consider per-channel quantization, i.e., the quantization scale values are
shared for each column of C and each row or column of Z (see section 3.2 for details on which is
used when):

_Cij_
_Cq,ij = clamp_ _, 0, 2[b][c]_ 1 _si,_ (5)

_si_ _−_

  

_Zij_
_Zq,ij = clamp_ _, 0, 2[b][z]_ 1 _sj,_ (6)

_sj_ _−_

  

where ⌊·⌉ is rounding to nearest integer, and clamp(·) is defined as:


_x < a_
_a ≤_ _x ≤_ _b_ _._ (7)
_x > b_


clamp(x, a, b) =


We refer to the problem of finding quantized factors C and Z with sparse Z as quantized sparse PCA
problem. Once we obtain the factors C and Z, we get the matrix **_W = (CZ), which can be reshaped_**
back to a convolutional layer. The reshaped convolutional layer for factors C, Z is denoted by [CZ].
It is well known in network compression literature that it is better to find the best factorization on

[f]
the data manifold (Zhang et al. (2015); He et al. (2017); Stock et al. (2019)). Therefore, we solve
the following optimization problem:

**C[∗], Z[∗]** = argminCq,Zq E(X,Y )∼D _∥Y −_ [CqZq] ∗ **_X∥F[2]_** (8)
 

s.t. **Cq = Qc(C; sc, bC)**
**Zq = Qz(Z; sz, bZ)**

**Zq** 0 _S, Z_ R[k][×][n], C R[d][×][k],
_∥_ _∥_ _≤_ _∈_ _∈_

where the parameter S controls the sparsity ratio of Z, X and Y are the stored input output of the
target layer in the original model, is the data distribution, and is the convolution operation. L0
_D_ _∗_
norm is used for the constraint on the number of nonzero elements in the matrix Zq. We approximate
the expected value of above optimization problem using a subset of the training data:


E(X,Y )∼D _∥Y −_ [CqZq] ∗ **_X∥F[2]_** _≈_ _m[1]_
 


_i=1_ _∥Yi −_ [CqZq] ∗ **_Xi∥F[2]_** _[,]_

X


where m is the number of samples used for optimization. Following the compression method introduced in Zhang et al. (2015), we use output of the previous compressed layer as X instead of the
stored input to the layer in the original model. This approach aims at compensating for the error
accumulation in deep networks.

3.1.1 PROJECTED GRADIENT DESCENT OPTIMIZATION ALGORITHM

The above optimization problem can be solved using an iterative projected gradient descent method.
The projection step is a hard thresholding operation which project onto the space of sparse matrices.
The optimization algorithm is given below.

1. Initialization. The codebook C is initialized with first k left singular vectors of **W. Given**
the SVD decomposition of **W as follows:**

[f]

**W = UΣV[⊤],** (9)

[f]

f


-----

**Algorithm 1 Projected Gradient Descent Optimization**

**Require:** **W**

1: SVD of **W = UΣV[⊤],**

2: C **U[f]k**
_←_
3: Z **U[⊤]k[f]W**
_←_

4: while Stopping criteria not met do
5: **Gradient descent step:[f]** **C, Z ←** gradient descent update on equation (10).

6: **M** binary mask for largest S values of Qz(Z; sz, bZ).
_←_

7: **Hard thresholding step: Z ←** **Z ⊙** **_M_** .

8: end while
9: return: Qc(C; sc, bC), Qz(Z; sz, bZ).


we choose C[(0)] = Uk, where Uk denotes the top k left singular vectors of **W. The**
latent matrix Z is initialized as the projection of **W onto the set of first k singular vectors,**
**Z[(0)]** = U[⊤]k **W.** [f]

[f]

2. Gradient Descent. At iteration t, the matrices C[(][t][−][1)], Z[(][t][−][1)] are updated by gradient
descent on the following objective w.r.t.[f] **C and Z:**

_m_

1

**Yi** [Qc(C; sc, bC)Qz(Z; sz, bZ)] **Xi]** _F_ _[,]_ (10)

_m_ _i=1_ _∥_ _−_ _∗_ _∥[2]_

X


We use the straight through estimator (STE) (Bengio et al. (2013)) to compute the gradients
of the quantization operation, i.e. we use the following gradient estimate for the rounding
operation:
_∂_ _p_
_⌈_ _⌋_ = 1.

_∂p_

The outcome of this step is denoted by C[(]gd[t][)][,][ Z][(]gd[t][)][.]

3. Hard thresholding. After the gradient descent, we project Z[(]gd[t][)] [onto the space of sparse]

matrices. The projection is done using entrywise product of Z[(]gd[t][)] [with a binary mask matrix]

**M[(][t][)], namely Z[(]gd[t][)]**

_[⊙]_ **[M][(][t][)][. The mask matrix][ M][ (][t][)][ is obtained finding the support of][ S]**

largest entries of Qz(Z[(]gd[t][)][;][ s][z][, b][Z][)][. This is the hard thresholding step. For the next iteration]
we set:
**Z[(][t][)]** = Z[(]gd[t][)] _[⊙]_ **_[M][ (][t][)][,][ C][(][t][)][ =][ C][(]gd[t][)][.]_**

4. Repeat the previous three steps using Z[(][t][)], C[(][t][)] until termination criteria is met
(MSE error or a fixed iterations number). The final matrices are given be
_Qc(C[(][t][)]; sc, bC), Qz(Z[(][t][)]; sz, bZ)._

This iterative projection step has theoretical support for well behaved optimization problems. See
Appendix A for more details.

3.1.2 RELATION TO OTHER APPROACHES

In this section, we discuss the connection with other existing methods.

(A) Vector quantization. If we replace the quantizers for C and Z by identity functions, i.e.
_Qc = id(·), Qz = id(·), then matrix C is in full precision, while Z encodes the indices_
such that
_Zij = δimi_ _,_ (11)

where mi is the centroid index corresponding to tile i.


-----

(B) Additive vector quantization. If Qc = id(·), bz = 1 (binary quantization), then


_ρjiC:,j,_ (12)
_j=1_

X


**W:,i =**


where ρji 0, 1 are binary coefficients. Note that in the original work by Babenko &
Lempitsky (2014), an additional constraint of ∈{ _}_ _j_ _[ρ][ji][ =][ n][t][ is enforced, i.e. each][ W][i,][:][ is a]_

sum of a fixed number of terms.

(C) Principle component analysis. If Qc = id(·), and[P] _Qz = id(·), then_


_ZjiC:,j._ (13)
_j=1_

X


**W:,i =**


This case corresponds to SVD factorization of zero mean version of weight matrix **W.**
For specific values of n and d, the method is mathematically equivalent to the SVD decomposition methods for neural network compression (Denton et al. (2014); Jaderberg et al.

[f]
(2014)). For example, if n = fouth, and d = finw, then the method is equivalent to the
spatial SVD decomposition by Jaderberg et al. (2014). In contrast to the above-mentioned
approaches, we do not decompose the convolutional operation into two convolutional layers, which gives extra flexibility in the choice of PCA dimensionality d.

3.2 COMPRESSION RATIO
Without sparsity, the compression ratio is computed as follows. Let Lo(W) = fout _fin_ _h_ _w_ 32
_×_ _×_ _×_ _×_
denote the number of bits required to represent the original 32 bit floating point tensor W, and
_Lc(W) = d × k × bc + k × n × bz the size of the quantized tensor factors C and Z of W. The_
compression ratio Cr is then defined as Cr = _[L]L[o]c([(]W[W])[)]_ [.]

Note that, since k < d < n, the latent matrix Z contributes more to the resulting model size than
the codebook matrix C. For example, let us assume fout = fin = 256, h = w = 3, d = 256,
and k = 128. In this scenario, the original weight tensor W has 256 × 256 × 3 × 3 = 589, 824
elements, the codebook matrix C has 256 × 128 = 32, 768 elements and the latent matrix Z has
128 _×_ 2, 034 = 260, 356 elements, almost 8 times as many as C. For this reason, efforts to compress
**Z, e.g., by using a lower bitwidth bc or pruning elements, will likely yield a better accuracy vs**
compression trade-off than focusing similar efforts on C.

Additional compression is achieved by encoding the sparse matrix Z as follows. We assume the
sparsity mask M is stored as a binary matrix. Then, we only store the nonzero values in Z. At
runtime, Z can be decoded by only reading values in Z for which the corresponding binary mask
value is equal to 1. The total number of bits required to store M and the nonzero values in Z is
_k × n + (1 −_ _r) × k × n × bz, where r = 1 −_ _S/kn is the sparsity ratio of Z with ∥Z∥0 = S. Note_
that this method only reduces memory footprint if r > 1/bz.

The size of the compressed tensor must be adjusted for quantization parameters introduced by perchannel quantization. We assume that each quantization scale parameter is encoded using FP16. To
account for this we add a quantization adjustment term Lq(W) to Lc(W), where Lq = 2k × 16 is
used for per-row quantization of Z.

Finally, taking into account the adjustments for sparsity and quantization parameters, the size of a
compressed tensor is computed as Lc(W) = d × k × bc + k × n + (1 − _r) × k × n × bz + Lq(W)._

4 EXPERIMENTS

In this section we describe two sets of experiments: one set to explore the effect of compression
hyperparameters on compression-accuracy trade-offs, and one set of experiments to compare against
various baseline methods.

4.1 EXPERIMENTAL SETUP
**Initial factorization** We start with a pre-trained model and perform the factorization as described
in Section 3.1.1. We initialize the per-channel quantization scale using min-max quantization (Krishnamoorthi, 2018).


-----

**Per layer data-aware optimization** To perform the data-aware optimization, we sample a single
batch of 64 input and output activations for a layer. We split the data into a training set and a
validation set (we keep one eighth of the data as the validation set). We keep track of the error on
the validation set. During this step we use the Adam optimizer (Kingma & Ba (2014)) with learning
rate 10[−][4] and weight decay 10[−][5].

**Sparsification** Sparsification is applied after per layer data-aware optimization in a form of hard
thresholding. We consider one-shot and iterative thresholding. Specifically, for each layer, the
quantized weights are sorted by absolute value, then a desired percentage of values is masked out.
We do not prune weights that become zeros after the quantization step, instead, we add extra sparsity
on top of accidental sparsity that occurs after the quantization. During the consequent fine-tuning
stage, the sparsity mask is frozen.

**Fine-tuning** We follow Martinez et al. (2021) and fine-tune our models end-to-end using the target
training set. Model-specific finetuning procedures are described below.

4.1.1 A NOTE ON COMPRESSION RATIO

In our experiments we leave the first convolutional weight tensor, all bias tensors, all batch normalization parameters, and the PCA centering vectors in FP32. We denote these uncompressible

**W** _[L][o][(][W][)]_

parameters as Lu. The sparsity ratio for a network is then computed as Cr = _LuP+[P]W_ _[L][c][(][W][)]_

4.2 IMAGENET EXPERIMENTS

We evaluate our method on the ResNet18 and MobileNetV2 achitectures for ImageNet classification.
We apply our method on pretrained versions of the model, where we take the pretrained weights from
the PyTorch model zoo. In all our experiments we keep the tile size d constant at 256, the bitwidth
of the codebook matrix C constant at 4, and use per-channel scalar quantization of 4 bits for the fully
connected classification layer weights. To achieve different compression ratios we vary the rank k
with values between 64-256, the bitwidth of the latent matrix Z between 3-6, and the extra sparsity
of Z between 0% and 40%. Further experimental details can be found in Section B.1.

4.2.1 BASELINE METHODS

We compare our methods against scalar quantization by Esser et al. (2019), binary CNNs by Lin
et al. (2017) (ABC-Net), the vector quantization method by Martinez et al. (2021) (PQF), the vector
quantization method by Stock et al. (2019) (BGD), trained ternary quantization by Zhu et al. (2016)
(TTQ). The results for scalar quantization are produced using LSQ Esser et al. (2019), with 4, 3
and 2-bit per-channel weight quantization and FP32 bit activations. For these experiments a weight
decay of 10[−][4] and cosine learning rate decay to 10[−][2] of the original learning rate was used.

4.2.2 RESULTS

The Pareto dominating results of our method and comparison to the baselines can be found in Figure 2. The full set of (non Pareto dominating) results can be found in Figure 3a. The same results
along with the values for rank, bitwidth and sparsity and resulting compression ratios can be found in
Table 2 in the Appendix. In this figure we see that we outperform BGD, TTQ, ABC-Net and 3 and 2
bit scalar quantization by considerable margins. Furthermore, we outperform or match the strongest
baseline at high compression ratios, PQF for compression ratios of 17x and higher, and are on par
with 4-bit scalar quantization for compression ratios under 17x. Lastly, we are the only method to
achieve SOTA compression-accuracy trade-offs over the full range from 5x to 40x compression.
4.3 ABLATION STUDIES

4.3.1 HARD THRESHOLDING METHODS

In this section, we study the impact of the hard thresholding method and the stopping criterion for
data-aware optimization. Algorithm 1 applies the hard-thresholding step at each iteration. However,
we can also apply it only after the end of gradient descent iterations. We call this one-shot hardthresholding. The method has precedence in non-convex sparse optimization (Shen (2020)). We
consider two different stopping criteria. The first is using the fixed number of gradient descent
iterations, e.g., 30, 100, or 1000. The second is based on achieving the MSE error threshold on the
validation set. We split the data used for per-layer optimization into a training set and a validation
set. We stop the iterations as soon as the error on the validation set is not decreasing for more


-----

Compression ratio vs accuracy (ResNet18)

71

Scalar quantization

70 VQ (Bit goes down)

69 VQ (Permute, quantize, finetune)

ABC-Net (M=5,3,1)

68 TTQ

Ours

67

FP32 baseline

Accuracy66 1% below FP32 baseline

65

64

63

62

5 10 15 20 25 30 35 40

Compression ratio

Compression ratio vs accuracy (MobileNetV2)

72

Scalar quantization

71 VQ (our implementation)

70 Ours

FP32 baseline

69 1% below FP32 baseline

68

Accuracy

67

66

65

64

7 8 9 10 11 12

Compression ratio


Figure 2: Results for Resnet18 and MobileNetV2 trained on ImageNet

than two iterations. Finally, we compare both methods with one-shot hard-thresholding without
data-aware optimization.

We present the results for Resnet18 in the Table 1. Three different levels of sparsity are considered
for a model with 4 bit latent. We report the validation accuracy of the model before and after finetuning. The results suggest that the most important aspect of data-aware optimization is the stopping
criterion. The best pre-finetuning results are obtained by using iterative hard thresholding with the
least number of iterations, namely 30. The second best method is one-shot iterative hard thresholding
with the stopping criterion based on the validation set. These results suggest that it is important to
limit the number of iterations of per layer optimization in order to prevent the method from overfitting to the layer input and output data sample. This intuition is further supported by observing the
lowest pre-finetuning accuracy for hard thresholding with the highest number of iterations, namely
1000.

However, overall benefits of per layer optimization methods become marginal after the compressed
model is fine-tuned. In various experiments, we observed an 0.1-0.3% improvement in the validation accuracy compared to using one-shot hard thresholding without any data-aware optimization.
Therefore, in our further full model experiments, we used one-shot hard thresholding with the stopping criterion based on the validation set as a method of low computational complexity, which gives
nearly the best results compared to the other methods.

4.3.2 QUANTIZATION VS PRUNING VS RANK
In our method, compression can be achieved by lowering rank, lowering the bit-width for latent
matrices (hence referred to as ‘bit-width’), or increasing extra sparsity. Thus, similar compression
ratios can be achieved with different values for rank, bit-width and sparsity. For example, for a
given model, we can retain the same compression ratio by increasing rank and decreasing bit-width
to compensate. In this section we investigate whether we can discover patterns that would help guide
compression hyperparameter search.

In Figure 3a we show a scatter plot with the full set of results. In this figure, we see that for low
compression ratios (below 14x) only minor improvements can be achieved by tweaking compression
hyperparameters. For example, around 10x compression even the worst performing compression hy

-----

Pre-FT accuracy Post-FT accuracy
Hard
threshold- Stopping. 10% 20% 30% 10% 20% 30%
ing critetion sparsity sparsity sparsity sparsity sparsity sparsity
method

One-shot HT val. set 63.2 58.9 47.3 **69.1** 68.7 **68.1**
One-shot HT 100 iter. 59.4 55.5 45.2 68.8 68.4 68.0
Iterative HT 30 iter. **64.5** **63.0** **58.8** **69.1** **68.8** 68.0
Iterative HT 100 iter. 62.0 60.7 57.3 69.0 68.7 **68.1**
Iterative HT 1000 iter. 55.0 55.4 54.1 68.5 68.3 67.9
No data-aware opt. -  58.5 53.3 37.8 69.0 68.7 67.9


Table 1: Resnet18 ablation on the impact of the hard thresholding method and the stopping criterion
on top-1 validation accuracy of the compressed model. Iterative hard-thresholding with 30 iterations
shows the best results among all the other methods, however, the benefit vanishes after fine-tuning.

Compression ratio vs accuracy (ResNet18)


70

68

66


64

62


60

|Col1|Col2|Col3|Col4|Col5|Col6|Col7|Col8|
|---|---|---|---|---|---|---|---|
|||||||||
|||||||||
|||||||||
|||||||||
|||||||||
|Scalar VQ (Bi VQ (Pe ABC-N|quantization t goes down) rmute, quanti et (M=5,3,1)|ze, finetune)||||||
|TTQ Ours FP32 b 1% be|aseline low FP32 base|line||||||


10 15 20 25 30 35 40

Compression ratio


Rank vs accuracy Bitwidth vs accuracy Sparsity vs accuracy

69.8

69.7

69.6

69.5

Accuracy %

69.4

69.3

150 200 250 3 4 5 0 10 20 30 40

65

60

Accuracy %

55

40 50 60 70 80 90 3 4 5 6 0 10 20 30 40

Rank Bitwidth Sparsity %


(b) Effect of rank, bit-width and sparsity for models
near 11x (top row) and 25x (bottom row) compression ratios.


(a) All results for ResNet18, including non-Pareto
dominating results


Figure 3: Full results and effect of rank, bit-width and sparsity.

perparameters are still on par with quantization to 3 bits (10.67x compression). However, for higher
compression ratios the compression hyperparameters have a larger impact on model performance.

In Figure 3b we show the effect of rank, bit-width and sparsity ratios on a set of models with a low
(near 11x, top row) and a high (near 25x, bottom row) compression ratio. Again we see little effect
(roughtly 0.5%) for the lower compression ratio. However, for the more aggressively compressed
models in the bottom row, we see that increasing rank while lowering bit-width to compensate has
a strong positive effect on model performance. Finally, in both plots we see no clearly discernible
trend in the effect of compression ratio on model accuracy.

Based on these results we conclude that, at high compression ratios, increasing rank and decreasing
bit-widths can improve results. Sparsity can be used to further fine-tune the target compression ratio.


5 CONCLUSION

We presented a weight compression method based on quantized sparse PCA which unifies SVDbased weight compression, sparse PCA, and vector quantization. We tested our method on ImageNet classification and show compression-accuracy trade-offs which are state-of-the-art or on
par with strong baselines, and demonstrated that our method is the only method to achieve SOTA
compression-accuracy trade-offs in both low and high compression regimes. Lastly, we investigated whether low rank approximations, quantization, or sparsity yield the best efficiency-accuracy
trade-offs, and found that at high compression ratios, increasing rank and decreasing bit-width can
improve results. For future work, we plan to investigate methods for automated rank, bit-width,
and sparsity ratio selection in order to further improve the accuracy and reduce the hyper-parameter
search time.


-----

REFERENCES

Artem Babenko and Victor Lempitsky. Additive quantization for extreme vector compression. In
_Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 931–938,_
2014.

Yoshua Bengio, Nicholas L´eonard, and Aaron Courville. Estimating or propagating gradients
through stochastic neurons for conditional computation. arXiv preprint arXiv:1308.3432, 2013.

Yash Bhalgat, Jinwon Lee, Markus Nagel, Tijmen Blankevoort, and Nojun Kwak. Lsq+: Improving
low-bit quantization through learnable offsets and better initialization. In Proceedings of the
_IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, June_
2020.

Yongjian Chen, Tao Guan, and Cheng Wang. Approximate nearest neighbor search by residual
vector quantization. Sensors, 10(12):11259–11273, 2010.

Bin Dai, Chen Zhu, Baining Guo, and David Wipf. Compressing neural networks using the variational information bottleneck. In International Conference on Machine Learning, pp. 1135–1144.
PMLR, 2018.

Misha Denil, Babak Shakibi, Laurent Dinh, Marc’Aurelio Ranzato, and Nando De Freitas. Predicting parameters in deep learning. arXiv preprint arXiv:1306.0543, 2013.

Emily L Denton, Wojciech Zaremba, Joan Bruna, Yann LeCun, and Rob Fergus. Exploiting linear
structure within convolutional networks for efficient evaluation. In Advances in neural informa_tion processing systems, pp. 1269–1277, 2014._

Zhen Dong, Zhewei Yao, Amir Gholami, Michael W Mahoney, and Kurt Keutzer. Hawq: Hessian
aware quantization of neural networks with mixed-precision. In Proceedings of the IEEE/CVF
_International Conference on Computer Vision, pp. 293–302, 2019._

Steven K Esser, Jeffrey L McKinstry, Deepika Bablani, Rathinakumar Appuswamy, and Dharmendra S Modha. Learned step size quantization. arXiv preprint arXiv:1902.08153, 2019.

Angela Fan, Pierre Stock, Benjamin Graham, Edouard Grave, R´emi Gribonval, Herve Jegou, and
Armand Joulin. Training with quantization noise for extreme model compression. arXiv preprint
_arXiv:2004.07320, 2020._

Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis. Springer New York, New York, NY, 2013. ISBN
[978-0-8176-4947-0 978-0-8176-4948-7. URL http://link.springer.com/10.1007/](http://link.springer.com/10.1007/978-0-8176-4948-7)
[978-0-8176-4948-7.](http://link.springer.com/10.1007/978-0-8176-4948-7)

Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv
_preprint arXiv:1902.09574, 2019._

Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization. IEEE transac_tions on pattern analysis and machine intelligence, 36(4):744–755, 2013._

Allen Gersho and Robert M Gray. _Vector quantization and signal compression, volume 159._
Springer Science & Business Media, 2012.

Yunchao Gong, Liu Liu, Ming Yang, and Lubomir Bourdev. Compressing deep convolutional networks using vector quantization. arXiv preprint arXiv:1412.6115, 2014.

Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural networks. In Proceedings of the IEEE international conference on computer vision, pp. 1389–1397,
2017.

Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew G. Howard,
Hartwig Adam, and Dmitry Kalenichenko. Quantization and training of neural networks for
efficient integer-arithmetic-only inference. In 2018 IEEE Conference on Computer Vision and


-----

_Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018, pp. 2704–_
2713. Computer Vision Foundation / IEEE Computer Society, 2018. doi: 10.1109/CVPR.
[2018.00286. URL http://openaccess.thecvf.com/content_cvpr_2018/html/](http://openaccess.thecvf.com/content_cvpr_2018/html/Jacob_Quantization_and_Training_CVPR_2018_paper.html)
[Jacob_Quantization_and_Training_CVPR_2018_paper.html.](http://openaccess.thecvf.com/content_cvpr_2018/html/Jacob_Quantization_and_Training_CVPR_2018_paper.html)

Laurent Jacques, Jason N Laska, Petros T Boufounos, and Richard G Baraniuk. Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors. IEEE Transactions on Informa_tion Theory, 59(4):2082–2102, 2013._

Max Jaderberg, Andrea Vedaldi, and Andrew Zisserman. Speeding up convolutional neural networks
with low rank expansions. arXiv preprint arXiv:1405.3866, 2014.

Rodolphe Jenatton, Guillaume Obozinski, and Francis Bach. Structured sparse principal component
analysis. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and
_Statistics, pp. 366–373, 2010._

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, 2015._

Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint
_arXiv:1412.6980, 2014._

Raghuraman Krishnamoorthi. Quantizing deep convolutional networks for efficient inference: A
whitepaper. arXiv preprint arXiv:1806.08342, 2018.

Vadim Lebedev, Yaroslav Ganin, Maksim Rakhuba, Ivan Oseledets, and Victor Lempitsky.
Speeding-up convolutional neural networks using fine-tuned cp-decomposition. arXiv preprint
_arXiv:1412.6553, 2014._

Honglak Lee, Alexis Battle, Rajat Raina, and Andrew Y. Ng. Efficient sparse coding algorithms. In
_Proceedings of the 19th International Conference on Neural Information Processing Systems, pp._
801–808. MIT Press, 2006.

Xiaofan Lin, Cong Zhao, and Wei Pan. Towards accurate binary convolutional neural network.
_arXiv preprint arXiv:1711.11294, 2017._

Christos Louizos, Max Welling, and Diederik P Kingma. Learning sparse neural networks through
_l 0 regularization. arXiv preprint arXiv:1712.01312, 2017._

Zongming Ma. Sparse principal component analysis and iterative thresholding. _The Annals of_
_Statistics, 41(2):772–801, April 2013._ ISSN 0090-5364. doi: 10.1214/13-AOS1097. URL
[http://projecteuclid.org/euclid.aos/1368018173.](http://projecteuclid.org/euclid.aos/1368018173)

Julieta Martinez, Jashan Shewakramani, Ting Wei Liu, Ioan Andrei Bˆarsan, Wenyuan Zeng, and
Raquel Urtasun. Permute, quantize, and fine-tune: Efficient compression of neural networks.
In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.
15699–15708, 2021.

Yusuke Matsui, Yusuke Uchida, Herv´e J´egou, and Shin’ichi Satoh. A survey of product quantization.
_ITE Transactions on Media Technology and Applications, 6(1):2–10, 2018._

Markus Nagel, Marios Fournarakis, Rana Ali Amjad, Yelysei Bondarenko, Mart van Baalen, and
Tijmen Blankevoort. A white paper on neural network quantization. ArXiv, abs/2106.08295,
2021.

Kirill Neklyudov, Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Structured bayesian
pruning via log-normal multiplicative noise. arXiv preprint arXiv:1705.07283, 2017.

Mohammad Norouzi and David J Fleet. Cartesian k-means. In Proceedings of the IEEE Conference
_on computer Vision and Pattern Recognition, pp. 3017–3024, 2013._

Jie Shen. One-bit compressed sensing via one-shot hard thresholding. In Conference on Uncertainty
_in Artificial Intelligence, pp. 510–519. PMLR, 2020._


-----

Pierre Stock, Armand Joulin, R´emi Gribonval, Benjamin Graham, and Herv´e J´egou. And the bit
goes down: Revisiting the quantization of neural networks. arXiv preprint arXiv:1907.05686,
2019.

Jiahao Su, Jingling Li, Bobby Bhattacharjee, and Furong Huang. Tensorized spectrum preserving
compression for neural networks. arXiv preprint arXiv:1805.10352, 2018.

Stefan Uhlich, Lukas Mauch, Kazuki Yoshiyama, Fabien Cardinaux, Javier Alonso Garcia, Stephen
Tiedemann, Thomas Kemp, and Akira Nakamura. Differentiable quantization of deep neural
networks. arXiv preprint arXiv:1905.11452, 2(8), 2019.

Mart van Baalen, Christos Louizos, Markus Nagel, Rana Ali Amjad, Ying Wang, Tijmen
Blankevoort, and Max Welling. Bayesian bits: Unifying quantization and pruning. arXiv preprint
_arXiv:2005.07093, 2020._

Thijs Vogels, Sai Praneeth Karinireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient
compression for distributed optimization. Advances In Neural Information Processing Systems
_32 (Nips 2019), 32(CONF), 2019._

Kuan Wang, Zhijian Liu, Yujun Lin, Ji Lin, and Song Han. Haq: Hardware-aware automated quantization with mixed precision. In Proceedings of the IEEE/CVF Conference on Computer Vision
_and Pattern Recognition, pp. 8612–8620, 2019._

Jiaxiang Wu, Cong Leng, Yuhang Wang, Qinghao Hu, and Jian Cheng. Quantized convolutional
neural networks for mobile devices. In Proceedings of the IEEE Conference on Computer Vision
_and Pattern Recognition, pp. 4820–4828, 2016._

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, 2015._

Chenzhuo Zhu, Song Han, Huizi Mao, and William J Dally. Trained ternary quantization. arXiv
_preprint arXiv:1612.01064, 2016._

Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for
model compression. arXiv preprint arXiv:1710.01878, 2017.

Hui Zou, Trevor Hastie, and Robert Tibshirani. Sparse principal component analysis. Journal of
_computational and graphical statistics, 15(2):265–286, 2006._

A HARD THRESHOLDING FOR SPARSE OPTIMIZATION

The sparse optimization method sketched in this paper is based on one-shot or alternating applications of a projection step onto the space of sparse vectors. In this section, we provide some
theoretical supports for this approach. Consider the following optimization problem:

min (14)
**_x_** _[f]_ [(][x][)][.]
_∈D_

The set D is a generic set. The projection function on D is defined as

Π (z) = arg min
_D_ **_x∈D_** _[∥][x][ −]_ **_[z][∥][2][ .]_**

When the set D is the set of sparse vectors denoted by Σs(R[n]) with sparsity order s, the projection
function is hard thresholding. For a vector x, the hard thresholding function Hs(x) yields a vector
with at most s non-zero entries, which are the s entries of x with largest absolute value.

The following proposition provides a general condition under which the optimization problem (14)
can be solved using iterative projection methods.


-----

**Proposition A.1. Consider the optimization problem equation 14 and assume that x⋆** is the minimizer of the problem. Consider an iterative optimization algorithm with the initial point x0 and the
iteration t defined by:
_xt+1 = Π_ (xt ∆f (xt)),
_D_ _−_
where ∆f (.) is a function such that x ∆f (x) is L-Lipschitz, and ∆f (x⋆) = 0. Then we have:
_−_

_∥xt −_ **_x⋆∥2 ≤_** (2L)[t] _∥x0 −_ **_x⋆∥2 ._**

In particular, if L 1/2, the algorithm converges to the minimizer x⋆ as t .
_≤_ _→∞_

_Proof. First, for an arbitrary set_ R[n], the projection operation onto the set Π ( ) and any x
_D ⊆_ _D_ _·_ _∈D_
and z ∈ R[n], we have the following inequality

_∥ΠD(z) −_ **_x∥2 ≤_** 2 ∥z − **_x∥2_**
We can obtain this inequality in two steps. We first use triangle inequality:

_∥ΠD(z) −_ **_x∥2 ≤∥z −_** **_x∥2 + ∥ΠD(z) −_** **_z∥2 ._**

For the last term, we use the definition of projection operation that for each x ∈D, the projection
of z to D minimizes its distance to the points in D:

_∥ΠD(z) −_ **_z∥2 ≤∥z −_** **_x∥2 ._**

Consider the iteration step t + 1. We have:

_∥ΠD(xt −_ ∆f (xt)) − **_x⋆∥2 ≤_** 2 ∥xt − ∆f (xt) − **_x⋆∥2 ≤_** 2L ∥xt − **_x⋆∥2,_**

which implies
_∥xt −_ ∆f (xt) − **_x⋆∥2 ≤_** (2L)[t][+1] _∥x0 −_ **_x⋆∥2 ._**


Some remarks are in order. First, the assumption ∆f (x⋆) = 0 means that x⋆ is a stationary point
of the algorithm. This holds particularly for gradient descent based methods where ∆f (x⋆) =
_α_ _f_ (x) and x⋆ is a stationary point of f .
_∇_

The Lipschitz property of x ∆f (x) holds in many situations. As an example, consider the function
_−_
_f_ (·) as a simple mean squared error (MSE) loss, i.e., f (x) = ∥y − **_Ax∥2[2][. In this case, we have:]_**

**_x_** ∆f (x) = x _αAA[⊤]x = (I_ _αAA[⊤])x,_
_−_ _−_ _−_

which satisfies L-Lipschitz property with L bounded by the spectral norm of I − _αAA[⊤]. In many_
situations, when this spectral norm is restricted to the set D, it can be controlled to be less than
1/2. A notable example, closely related to our problem, is the sparse recovery problem where
one can prove recovery guarantee for iterative hard thresholding methods when the matrix A satisfies restricted isometry property. See Foucart & Rauhut (2013) for a comprehensive exposition
of the topic including iterative hard thresholding for linear problems. Hard thresholding methods
are widely used in sparse optimization literature. Particularly relevant to our problem is the one-bit
sparse recovery problem, where iterative hard thresholding is used Jacques et al. (2013).

B RESNET18 EXPERIMENTS

B.1 EXPERIMENTAL DETAILS

We run a small number of pilot experiments for 5 epochs, to find good settings for the optimizer,
learning rate, and learning rate schedule. We then run a large number of 5 epoch experiments to find
good compression-accuracy trade-offs. For the best performing compression-accuracy trade-offs we
then run longer experiments of 25 epochs, with the two best optimization schedules. We use a batch
size of 64 for Resnet18, use cosine learning rate decay to 10[−][3] of the initial learning rate, and turn
off weight decay.

B.2 PARETO DOMINATING RESULTS

B.3 ABLATION STUDY RESULTS


-----

K D bw mpfd cr sparse eval score

256 256 5 0.00 6.01 70.26
256 256 5 0.20 6.96 70.06
256 256 4 0.20 8.91 70.04
192 256 4 0.20 11.50 69.77
192 256 3 0.00 13.20 69.47
128 256 3 0.00 16.95 69.15
128 256 3 0.00 18.17 68.91
128 256 4 0.40 20.19 68.73
128 256 3 0.20 21.70 68.63
92 256 3 0.15 23.04 68.17
92 256 3 0.15 25.34 68.11
100 256 3 0.12 27.49 67.52
64 256 3 0.00 29.02 67.20
92 256 3 0.15 30.02 66.94
64 256 3 0.20 32.62 66.86
64 256 3 0.00 33.78 66.37
64 256 3 0.20 39.88 64.48

Table 2: All Pareto dominating results for ResNet18

|compression ratios near 11x K D bw sparsity comp. ratio accuracy|compression ratios near 25x K D bw sparsity comp. ratio accuracy|
|---|---|


|256 256 4 0.3 10.87 69.31 128 256 5 0.1 11.41 69.32 256 256 3 0.0 11.77 69.45 192 256 5 0.4 11.07 69.49 128 256 5 0.0 11.24 69.57 192 256 4 0.2 11.19 69.77 192 256 4 0.1 10.56 69.72|39 256 6 0.00 25.97 54.04 40 256 6 0.10 25.52 54.06 48 256 5 0.00 25.26 63.03 58 256 4 0.00 25.57 64.89 64 256 5 0.40 25.57 66.03 58 256 4 0.00 25.57 67.11 60 256 4 0.13 25.45 67.18 64 256 3 0.00 26.07 67.40 77 256 3 0.00 25.56 68.00 92 256 3 0.15 25.34 68.11|
|---|---|



Table 3: Various hyperparameter settings and resulting compression ratios and accuracies for compression ratios near 11x and 25.5x


-----

