Sparse matrix products for neural network compression
Authors: Luc Giffon
hachem kadri
Stephane Ayache
Ronan Sicre
thierry artieres
Venue:  (2021)
Keywords: Compression
sparsity

Abstract: Over-parameterization of neural networks is a well known issue that comes along with their great performance. Among the many approaches proposed to tackle this problem, low-rank tensor decompositions are largely investigated to compress deep neural networks. Such techniques rely on a low-rank assumption of the layer weight tensors that does not always hold in practice. Following this observation, this paper studies sparsity inducing techniques to build new sparse matrix product layer for high-rate neural networks compression. Specifically, we explore recent advances in sparse optimization to replace each layer's weight matrix, either convolutional or fully connected, by a product of sparse matrices. Our experiments validate that our approach provides a better compression-accuracy trade-off than most popular low-rank-based compression techniques.


Under review as a conference paper at ICLR 2021
SPARSE MATRIX PRODUCTS FOR NEURAL NETWORK COMPRESSION
A Anonymous authors Paper under double-blind review
A ABSTRACT
Over-parameterization of neural networks well known issue that comes along with their great performance. Among the many approaches pro- posed to tackle this problem, low-rank tensor decompositions are largely investigated to compress deep neural networks. Such techniques rely low-rank assumption of the layer weight tensors that does not always hold in practice. Following this obscrvation, this paper studics sparsity inducing techniques to build new sparse matrix product layer for high-rate neural networks compression. Specifically, we explore recent advances in sparse optimization to replace each layer's weight matrix, either convolutional or fully connected, by product of sparse matrices. Our experiments validate that our approach provides a better compression-accuras trade-off than most popular low-rank-basse based compression techniques.
INTRODUCTION
The success of neural networks in the processing of structured data is in part due to their over-parametrristion which plays a key role in their ability to learn rich features from the data (Neyshabur et al. 2018). Unfortumately, this also makes most state-of-the-art models so huge that they are expensive to store and impossible to operate on devices with limited resources (memory, computing capacity) that cannot integrate GPUs (Cheng al. 2017). This problem has led to a popular line of research for "neural networks compression" which aims at building models with few parameters while preserving their accuracy.
State of the art techniques for neural network compression. Popular matrix or tensor decomposition methods including Singular Value Decomposition (SVD), CANDE- COMP COMP/PARAFAC (CP) and Tucker have been used to address the problem of model com- pression by low-rank approximation of the neural net wetkork's 's weights after learning. [aannth et al. (0133) describe a method based on SVD to compress weight matrices in fully con- nected layers. Denton et al. (2014); Lebedev et al. (2015): Kim et al. (016)) generalize this idea. to convolutional layers and then reduce the memory footprint of convolution kernels by using higher-order low-rank decompositions such as CP or Tucker decompositions.
Besides, the Tensor-Train (TT) docomposition has been explored to compress both dense and convolutional layers after a pre-training step (Novikov et al. 2015). This approach may achieve extreme compression rates but it also have impractical downsides that demonstrale now. In a TT format, all the elements of a .M-order tensor are expressed by product of M matrices whose dimensions are determined by the TT-ranks (Ro, Ri...., Ry For each of the M dimension of the initial tensor, the corresponding matrices can be stacked into an order 3 tensor called "core" of the decomposition. Hence, the layer weight is decomposed as set of M cores of small dimensions. Novikov et al.] (2015) use this tensor representation to factorize fully connected layers. They first reshape the matrix of weights into an M-order tensor, then apply the TT decomposition. By choosing sufficiently small Rm values, this technique allows to obtain a high compression ratio on extremely wide ad hoc neural architectures. Garipov et al. (2016) have adapted this idea to convolutional layers. However, the current formulation of such TT convolutional layer involves the multiplication of all input values by matrix of dimension R₁ thus causing inflation of R times

---

Under review as a conference paper at ICLR 2021
the size of the input in memory. This makes the available implementation Garipov 2020 unusable for recent wide convolutional networks at inference time.
Other compression methods include unstructured pruming techniques that review more in details in Section 2.3 and structured pruning techniques that reduce the inner hidden dimensions of the network by completely removing neurons (Anwar et al. 2017). According to the recent paper of Liu et al. (2018) however, these tochniques are more akin to Newral Architecture Search than actual network compression. Finally, quantization-basse compres- sion maps the columns of the weight matrices in the network to a subset of reference columns with lower memory footprint (Guo) 2018).
Sparse matrices product for full rank decompositions. We are specifically inter- ested in high-rate compression of neural networks via the efficient factorization of the layer weight matricos. Most known approaches to layer decomposition usually makes low-rank assumption on the layer weight tensors which does not always hold in practice. As we will show in the experiments, this makes the Tucker and SVD based techniques unable to effectively reach high compression rales for standard architectures including both convo- lutional and fully connected layers, such as VGG19 or ResNet50,, whose weight matrices usually exhibit full rank. In this paper, we propose instead to express the weight matrices of connece
convolutional layers little parameters but still can represent high-rank matrices. Moreover, products of matri- with total sparsity budget are strictly more expressive than single matrices with that sparsity (Dao et al. 2019), which motivates our interest in products of multiple matrices. Usually, a linear operator (a matrix) from IDD to RD has a time and space complexities of O(D)). But some well known operators like the Hadamard or the Fourier transforms can be expressed in the form of a product of log D sparse matrices, each having O() non-zero values (Dao et al., 2019 Magoarou & Gribonval 2016). These linear operators, called fast-operators, thus have a time and space complexities lowered to O D). This interesting feature of fast-operators have inspired the design of new algorithms that learn sparse matrix product representations of existing fast-transforms (Dao et al., 2019) or even that computes sparse product approximations of any matrix in order to accelerate learn- ing and inference (Magoarou & Gribonval 2016 Giffon et al., 2019). Even though these new methods were initially dosigned to recover the log D factors corresponding to a fast- transform, they are more general than that and can actually be used to find a factorization with Q log D sparse matrices.
product of sparse factors which contains very
Contributions. We introduce a general framework for neural network compression using the factorization of layers into sparse matrix products. We explore the of the recently proposed palm4MSA algorithm (Magoarou & Gribonval 2016) on every layer of a pre-trained neural network to express them as a product of sparse matrices. The obtained sparse matricos are then refined by gradient descent to best fit the final prediction task. When there only one sparse matrix in the decomposition, our approach recovers the simple procedure of hard thresholding the weights of a matrix after pre-training. We evaluate the effect of different syper-parameeeers on our method and show that layers can be factorized into two or three sparse matrices to obtain high compression rates while preserving good performance, compared to several main state-of thet--r methods for neural network compression.
LEARNING SPARSE MATRIX PRODUCTS FOR NETWORK COMPRESSION
We describe how to compress NN weight matrices by sparse matrix factorization. We call our procedure PSM for Product of Sparse Matrices. It obvious to see that a product of sparse matrices with a given sparsity budget can recover a full rank matrix or a matrix with more non-zero values than the initial sparsity budget. This observation motivates the use of sparse matrix factorization in place of usual low-rank decomposition and sparsity inducing techniques for neural network compression. We first recall linear transform operations in fully-connected and convolutional layers. Then, inspired by recent work on learning linear operators with fast-transform structures, we propose to use a product of sparse matrices to replace linear transforms in neural networks. We also introduce a procedure to learn such factorization for every layers in deep architecture. Finally, we review some known neural network compression techniques that appear as particular cases of our framework.
2

---

Under review as a conference paper at ICLR 2021
2.1 WEIGHT MATRICES AS PRODUCT OF SPARSE MATRICES
Fully-connected and convolutional layers are based on the computation of linear operations.
In a fully-connected layer, the output z E Rp' simply given by z = (Wx) where a is some non-linear activation function. W E DDD'D is the weight matrix of the layer and R is the output of the preceding layer.
The linear operation in a convolutional layer can be represented by a doubly-block Toeplitz matrix (Wang et al. 2020). An other way to perform the operation to employ reshap- ing operators to represent the linear operator as a dense matrix applied to all the patches extracted from the input (Garipov et al. 2016). In this work, we focus on this latter represen- tation of the convolution operation. More formally, let rs "xxxx + R be the reshape operation that creates the matrix of all vectorized patches of size (height and width) S on an input image with C' channels. The matrix of filters W E RCS** can then be applied to these patches (multiplied with rs) to produce the output of the convolutional layer a mairix shape. Finally, a second reshape operator t: R# x + RR xX is ap- plied on the feature map matrix to reconstruct the output tensor of the layer Z TeR "xxxx Altogether, the convolution operation can be written as = ((t(rr(XX)))) non-linear activation function and X' is the output 3-D tensor of the preceding layer. We preserve simplicity in notation here, assuming without loss of generality that the stride used by rs is equal to and that the input tensor is padded with 1 zeros vertically and horizontally. The whole process is depicted in Supplementary Material A.2
where a some
Our general idea is to replace the weight matrix of each neural network layer with a product of Q sparse matrices, hence reducing the storage and computational complexities of the layer. Indeed, for an initial matrix of dimension (D x D'), if all sparse matrices store O(D) non-zero values, then the total complexity of the product becomes ((QD) instead of O(DD'). To define fast-transform operator, one would use Q log D but in practice we show that we can chose much smaller Q and achieve huge compression rates without lowering much the performance. Supplementary Material A.I illustrates the effect of our compression scheme dense layer. Given an input vector x E RR, expressing the weight matrix W E D'DD of fully connected layer as a product of sparse matrices gives output z such that:
simple architecture including one convolution layer and single
Q
==a
II S
(1)
where ||Sillo O(D) that the complexity in time and space of this layer is reduced to ((QD) instead of O(DD').
Similarly, in the convolution layers, the output Z e BxW is obtained from an input tensor X E R #xXC.
2 Z= TS I[s.
rs (X)
i=1
where ||S:|lo (m) that the time complexity of the layer is reduced from OSWCSS* K) to O(HQQ max K)) and the complexity in space is reduced from K) to O(Q max (CS²,K))
Since there is no constraint on the rank of factors, the sparse matrix products of each layer can reach full rank, unlike low-rank decomposition methods. Moreover, the reconstruction of a sparse matrix product with a total of O(QD) non-zero values can produce a matrix with more than ((QD) non-zero values. This is consistent with the intuition that product of sparse matrices can be more expressive than a single sparse matrix.
2.2 FULL NEURAL NETWORK COMPRESSION
The full compression pipeline propose includes first the learning of a standard NN, second the compression of each layer independently as a product of sparse matrices, and finally a fine tuning of the compressed NN whose layers are all expressed as PSM layers.
3

---

Under review as a conference paper at ICLR 2021
The second step requires approximating each weight matrix W (of dense convolutional layer) as a product of sparse factors, which is cast as the following optimization problem:
min {S
W
S F
+
gg (Si),
(3)
where for each i E [Q], òg, (S.) 0 S; E, and de, (S.) to otherwise. E, the set of solutions that respect a sparsity constraint (e.g. number of non zeros values). Although this problem is non-convex, non-differentiabl,, and the computation of a global optimum cannot be ascertained, the palm4MSA algorithm proposed by Magoarou & Gribonval (2016)
able to learn such factorization by finding a local minimum with convergence guaranlees. For more details about palm4MSA, see Supplmentary Materiel
A.4
Once every layer's weight matrix is approximated by a product of sparse matrices, these PSM layers are assembled in compressed NN which is refined to optimize the initial task objective while the sparsity support of all factors kept fixed.
2.3 RELATED WORK
Some techniques based on inducing sparsity in neural connections, e.g. zeroing single weights in layer tensors, can be seen as particular cases of our method. The most straightforward approach to this is to simply remove the weights with lowest magnitude until given sparsity ratio is reached. This can be done in a very trivial fashion by just removing weights on a pre-trained network and then finetuning the remaining connections. This method can be seen as the particular case of ours when there is only one factor to approximate weight matrices (i.e., Q 1). As show in the experiments, this method doesn't allow high compression rate without degradation of the accuracy. Zhu & Gupta (2017) proposed instoad to intertwine the removal of the connections by finetuning remaining weights, achieving better classification performance. Others, approaches for inducing sparsity in the network were proposed (Molchanov et al. 2017 Louizos offer performance improvements in general settings [Gall et al. 2019).
(018-06-22 but they do not seem to
The idea of replacing layers by sparse factorization has been previously explored but re- stricted to particular structures. In Deep Fried Convnets, Yang et al. (2015) propose to replace dense layers of convolutional neural networks by the Fastfood approximation (Le et al. 2013). This approximation is product of diagonal matrices, permutation matrix, and Hadamard matrix which can itself be expressed as a product of log sparse matrices (Dao et al. 2019). The Fastfood approximation thus provides product of sparse factors and from this perspective, the Fastfood layer proposed by Yang et al. 2015)) is a particu- lar, constrained, case of our more general framework. Moreover, the Deep Fried Convnets architecture based on the Hadamard matrix that imposes a strong structural constraint on the factorization, which might not be suitable for all layers of deep architecture.
The term sparse decomposition used in Liu et al. (2015) for network compression refers to separate products between dense and sparse matrices to represent the weights of the convolution kernels in a network. Finally, Wu et al. (0019) have recently proposed a very similar framework than ours along with regularization strategy learn the sparsity in the sparse factors but their method does not allow for more than two sparse factors and the compression of the convolutional layers is not considered although best performing architectures tend to store most of their parameters in these layers.
3 EXPERIMENTS
Section 3.1 details the experimental settings and parameters ensure reproducibility. We provide an in depth analysis of our method in Section 3.2 Finally we report in Section 3.3 comparative study of our method with state-of-the-art. methods.

---

Under review as a conference paper at ICLR 2021
3.1 EXPERIMENTAL SETTING
Our analysis is focused on image classification tasks, we investigate the compression of standard architectures (pretrained models) with our approach and with a few state of the art methods. We evaluate all methods by measuring both the compression ratio and the accuracy of compressed models. We first present implementation details and datasets, then we detail the baselines and the hyperparameters we used.
Implementation details. The code was written in Python, including the Palm4MSA al- gorithm (it will be made available on github). NNs were implemented with Keras (Chollet, 2015 and Tensorflow (Abadi et al. 2015 Due to the lack of efficient. implement ation of the sparse matrices in Tensorflow, we had to hijack the implementations of the dense matrix product and convolution offered by Keras in order to make the learning of networks as efficient as possible (See Supplementary matorial A.3 for details).
Datasets and Neural Architectures. Our experiments are conducted on four stan- dard image classification data sets of varying difficulty: MNIST (Deng) 2012), SVHN (Netzer et al. 2011 CIFAR10, CIFAR100 (Krizhevsky) 2009)). Pretrained NNs to be compressed classically used with these data sets i.c. Lenet (LCCun et al. 1998), VCC19 &
Zisserman 2015), Resnet50 and Resnet20 (He et al. 2016). Details on datasets and neural architectures may be found in Supplemenaary Material A.5
Competing baselines. We present below the baselines and the variants of our approach that we considered. In all cases the methods were applied on the same pre-trained models and all compressed models were fine-tuned after compression:
Low-rank factorization methods, including Tensor-Train decomposition NNviikov et al., 2015 Garipov et al. 2016) (named TT hereafter) and an hybrid
Tucker decomposition (Kim et al.; 2016) and SVD (Sainath al. 2013) (named Tucker-SVD) where Tucker and SVD decomposition are used respectively for the compression convolutional and dense layers.
Two sparsity inducing pruning techniques. The first one simple magni- tude based projection of weight matrices
sparse support. This be seen as a particular case of our model where only one sparse factor is required. We name this strategy "Hard pruning" (HP in the following). The second method, named Neralive pruning (IP) is the iterative stralegy proposed by Zhu & Gupla 2017). which refine magnitude based projection with finetuning steps.
Finally, we evaluate the interest of using the palm4MSA algorithm to discover sparse matrix decomposition of the layers compared to some random decomposition. More precisely, we evaluate (I) the performance of model whose layers would be decomposed by palm4MSA but whose weights would be re-initialized while peserving the sparsituy support; and (II) the performance a model whose weights and sparsity support would be randomly sampled at initialization.
Note that we initially considered Deep Fried conmelss an additional baseline but we finally did not include on our experimental study since this method is originally dedicated to compress fully connected layers and our attempts to make it able to compress convolutional layers as well actually failed, preventing the method to be applied to compress many state of the art architectures that contain mostly convolutional layers.
Hyper-parane paperr-prramterss.. The stopping criteria used for the Palm4MSA algorithm is 300 iter- ations or a relative change between two iterations below 10-6 The projection method is the one used in Magoarou & Gribonval (2016). With K the desired level of sparsity, this method ensures that each sparse factor contains at least K non-zero values per row and per column and at most 2K on average.
For experiments with random sparsity support, the initialization of the weights must be adapted to the reduced number of connections in the layer. To do this, we adapt the initializations Xavier (Glorot & Bengio 2010) and He (He et al. 2015) to the initialization of sparse matrices (See Supplementary Material A.3).
5

---

Under review as a conference paper at ICLR 2021
We chose M = 4 cores for the Tensor-Train decomposition of any tensor and the maximum possible rank value of the decompositions is specified by the value R in the experiments.
In the hybrid of Tucker and SVD decomposition, the rank of the Tucker decomposition is automatically detected by the Variational Bayes Matrix Factorization method, as explained by Kim et al. (2016); the rank of the SVD in the dense layers is chosen such that only cortain percentage (specified in the experiments) of the singular values are kept.
Fine-tuning of the Lenet network epochs. The VGG19 and Resnet networks are fine-tuned with Adam (Kingma & Ba 2014) optimizer and respectively 300 and 200 epochs. For each compression method and con- figuration, the best learning rate is chosen using the classification error on a validation sample after 10 iterations, with learning rate values in {10-3, 10 10- Standard data augmentation is applied: translation, rotation and flipping.
done with the RMSProp optimizer and 100 learning
3.2 ANALYSIS OF THE METHOD
We first provide an in-depth analysis of our method validate the use of Palm4MSA for the decomposition of layer weight matrices into a product of sparse matrices. We then evaluate the impact of hyper-parameten Q and on model accuracy and compression rate.
Approximation error. We evaluate the quality of the Palm4MSA approximation of orig- inal weight matrices, and its influence on the final performance of the method. We report results gained on the compression VGG19 trained CIFAR100 as illustration. Figure shows the approximation error between the product of Q sparse factors : I S and the original weights W for each layer. It is computed as the normalized distance between the matrices: error = W| - WI2 W|
Figure 2 further shows that higher K, iec the minimum number of non-zero values per row and per column, yield better approximation. We observe that for some layers, the error can be high, despite relative good accuracy performance observed in Table suggesting the of the Palm4MSA is limited. In order to examine this usefulness, we have built two other types of models that implement the decomposition of layers into product of sparse matrices, either with random sparsity support, or with random weights, rather than considering those provided by Palm4MSA:
"PSM random": We construct completely random sparse factorization. The sparsity support is chosen by projecting reduced centered Gaussian matrix. The weights are initialized using the procedure described in Section 3.1
"PSM re-init.": We use the sparsity support obtained by Palm4MSA but initialize the weights using the procedure described in Section 3.1
Table shows the network with the Palm4MSA method obtains the best performance in clas- sification after refining the network (more results in Table Supplementary Material A.7). Overall sPSM re-init> and #PSM randoms may perform very badly on some cases, which suggests the importance of both weights and sparsity support found by Palm4MSA.
MNIST
VOG19
CIFARIO VEGIO
CIPARIO0 Resnet20
CIFAR100
Q-d K-14
0.96
0.92
0.70
PSM meinit. Q=3 K=14 PSM mundom Q-3 K-14
3.99
0.80
0.81
0.31
0.60
0.50
0.81
0.51
0.00
0.59
Table 1: Porformance of NN models compressed by 3 techniques layer docomposition into sparse matrix products. "PSM" refers to the proposed procedure using Palm4MSA on the pre-trained layers; "PSM re-init" uses Palm4MSA to define the sparsity support but the weights are re-initialized; "PSM random" randomly initializes weights and sparsity support.
Sparsity level and the number of factors. Sparsity level corresponds to the approxi- mate number non-zero values in each row and each column of the sparse matrices consti- tuting the sparse decomposition. Figure [ and Table 4 show the performance of our model

---

Reliability. First of all, the behaviour of the baseline methods seems quite dependent the experiment. For instance TT performance may vary depending on the chosen rank (c.g. rank 10 in figure (b)); Hard Pruning technique performs badly MNIST. Moreover these baselines are not always manageable practice (e.g. no results of TT on Resnet stable performances with Under review as a conference paper at ICLR 2021
Accuracy (%)
1
A
0.8
0.5
7.89
10k
2
8
100k
100k
1M
10M
(a) MNIST Lenet
(b) SVHN VGG19
Accuracy (%)
0.8
0.6
0.6
0.4
A
0.4
0.2
0.2
100k
1M
10M
100k
1M
10M
(c) CIFAR10 VGG19
(d) CIFAR100 VGG19
Accuracy (%6)
0.75
$
0.75
0.7
O
0.7
0.65
0.65
0.6
0.55
100k
1M
1M
10M
# Param. in Conv. and Dense layers
# Param. in Conv. and Dense layers
(e) CIFAR100 Resnet20
(L) CIFAR100 Resnet50
PSM K=2 K=2
PSM Q=2 K-3
PSM Q=2 K=4
PSM Q-2 K-8
PSM Q=2 K:14
PSM Q=3 K-2
PSM Q=3 K=3
PSM Q=3 K=4
PSM Q=3 K=8
PSM Q=3 K=14
20%
R=10
IP 959
IP 50%
* HP 95%
HP 98%
8
Base
Figure 1: Accuracy number of parameters (log scale) for compressing standard architec- ture (pretrained models) on few datasets. Comparative results our approach (PSM), the hybrid SVD-Tucker (Tucker-SVD), the TT method (TT), the Hard (Hard Pruning) and iterative (Jterative Pruning) pruning techniques. Details on the hyperparameters for each tested method included in the name of the methods. Base stands for the uncompressed pretrained model.
obtained with various sparsity levels K and numbers factors Q. We notice that the num- ber of factors seems to have rather limited effect the quality of the performance, while sparsity level is a more determining factor of the quality the approximation. Note that did not considered the Hierarchical version of Palm4MSA (Magoarou & Gribonval 2016) since requires Q = log D factors, which greatly increases the number of non-zero values in the decomposition without significantly improving the final performance of the model.
3.3 COMPARATIVE STUDY
Figure [ reports comparative results gained on standard benchmark datasets with well known architectures. We discuss below the main comments to be drawn from these results.
compression, below). On the contrary, observe

---

Under review as a conference paper at ICLR 2021
Relative crr
PSM K-14
I PSM K-2
Layer
Figure 2: Relative error approximation by layers using Palm4MSA for VGG19 architecture.
regards to the choice of hyper-parameters and systematic very low variance obtained with our method.
Comparison to low rank decomposition techniques. Our approach significantly out- performs the Tucker-SVD method any case. We believe that the low rank approximation may make more dilficult to reach high compression rates while preserving good performance. This emphasizes our point that standard low rank decomposition methods cannot afford high compression regime, e.g. low-rank assumption, without degradation of the accuracy of the network. On the contrary, the TT formulation may achieve higher compression rates than Tucker, was already observed in past works. It seems better suited than Tucker decomposition and may performs similarly or better as our method in some cases. Yet, the method has few drawbacks: first it may exhibit very strong variance, especially for high compression rates (see results in figures 1 (b) to (d) on SVHN, CIFAR10-100) second, as illustrated in Supplementary Material A.6 the implementation provided by authors do not allow getting results in any case, when the product of the number of filters and of the TT rank is large. In particular we were unable run experiments on models such Resnet20 and Resnet50 because the memory footprint is increased considerably (figures [[e) and (D). We thus are unable get results for higher compression rates that those in the higure with VGG19 (figures (c) and (d)).
Comparison with pruning techniques. In the "Hard" pruning case, the compressed network perform very badly. This confirms that a sparse factorization with more than one factor is profitable. When applying the procedure of Zhu & Gupta (2017), however, the magnitude based pruning method preserve good accuracy while removing up to 98% of the connections from the model, except for the MNIST dataset. While our approach significantly outperforms the Hard pruning technique in any case, its Iterative pruning variant Zhu & Guptal (2017) may sometimes leads to significantly higher performance compression in high compression set tingsn than our approach, this is the case in particular with Resnet models CIFAR100 (figures (e) and (f)). Otherwise, other settings on Resnet models, and for compressing other models, this technique allows similar performance off than our method. Since the Hard pruning technique may be viewed as a special case of method, this suggests that an itcrative-liko extension of our method could reach even better results, which a perspective this work.
compression trade-
CONCLUSION
The proposed approach able to compress dense and convolutional layers of a neural network by decomposing weight matrices into sparse matrices products. Unlike common decomposition methods, our method does not make any assumptions on the rank of the weight matrices and allows high compression rate while maintaining good accuracy. The experiments show the interest of using a product of multiple sparse matrices instead of a single sparse matrix to convey, in theory, more information for fixed number of non-zero values. A possible extension of this work would be to study a strategy for progressive sparcity inducing Zhu & Gupta (2077) that could offer further improvements.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jefirey Dean, Matthieu Devin, Sanjay Ghemawat, lan Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefow- icz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandclion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Πya Sutskever, Kunal Talwar, Paul Tucker, Vincent. Vanhoucke, Vijay Vasudevan, Fer- nanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenbery, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on helerogeneous systems. 2015. URL
http://wwwwweeoofoo.....o org/
Sajid Anwar, Kyuyeon Hwang, and Wonyong Sung. Structured pruning of deep convolu- tional neural networks. 13(3):1-18, 2017.
Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. A survey of model compression and acceleration for deep neural networks. 2017.
Francois Chollet. Keras: The Python deep learning API, 2015. URL httpp:// .
Tri Dao, Albert Gu, Matthew Eichhorn, Atri Rudra, and Christopher Ré. Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations. volume 97, pp. 1517 1527. PMLR, 2019. URL httt:://arxiv.oot org. abs 0tt//9903.0000 05895.
Li Deng. The MNIST Database of Handwritten Digit Images for Machine Learning Research. 29(6):141-142, 2012. ISSN 1558-0792.
doi: 10. 10.1109/MSPP 2M0000MMMP..02.22117777
Emily I. Denton, Wojeiech Zaremba, Joan Bruna, Yann LeCun, and Rob Fergus. Exploiting linear structure within convolutional networks for efficient evaluation. In Advonces in Neural Information Processing Systems, pp. 1269 1277, 2014.
Trevor Gale, Erich Elsen, and Sara Hooker. The State of Sparsity in Deep Neural Networks. 2019. URL http:pppaaaxx...or///////00.0.0
Timur Garipov. Github Tensorizing Neural Networks, 2020. URL https://github.... com/
Eingaripoo//TessooNee--T
Timur Garipov, Dmitry Podoprikhin, Alexander Novikov, and Dmitry Vetrov. Ultimate lensorization: Compressing convolutional and FC layers alike, 2016. http://aarrr
org/abs/1611.00 03214
Lue Giffon, Valentin Emiya, Liva Ralaivola, and Hachem Kadri. QuicK- Acceleration of K-means by learning a fast transform. 2019. URL lattt::t/////tt www.iaeeeiiivveeeeeeeeeee ouvertes.
fr/hal-0217484
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the Thirleenth International Conference on Artificial Intelligence and Statistics, pp. 249 256, 2010.
Yunhui Guo, A Survey on Methods and Theories of Quantized Neural Networks, 2018 URL http://aaxiv..orr//////000 04752)
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving Deep into Rectifiers:
Surpassing Human-Level Performance on ImageNet Classification. 2015. URL http:
//arxiv.orr org/ talb//502...m 01852
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition, pp. 770-778. IEEE, 2016. ISBN 978-1-4673-8851-1. doi: 10.1109/ CVPR.2016.90. URL htsp::/ieeeexpooree ieee org//occment/77704599/
Yong-Deok Kim, Eunhyeok Park, Sungjoo Yoo, Taclim Choi, Lu Yang, and Dongjun Shin. Compression of Deep Convolutional Neural Networks for Fast and Low Power Mobile Applications. 2016. URL http:///aa....oo///b///////// wwt.://a////..........

---

Under review as a conference paper at ICLR 2021
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In arXiv Preprint arXiv:1412.6900 69800, 2014.
Alex Krizhevsky. Learning multiple layers of features from tiny images, 2009.
Quoc Le, Tamás Sarlós, and Alex Smola. Fastfood Approximating Kernel Expansions in Loglinear Time. pp. 9, 2013.
Lebedev, Ganin, M Rakhuba, Oseledets, and V Lempitsky. Speeding-up convolutional neural networks using fine-tuned CP-decomposition. In 3rd International Conference on Learning Representations, ICLR 2015-Conference Truck Proceedings, 2015.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. tradient-based learning applied document recognition. 86(11):2278 2324, 1998.
Baoyuan Liu, Min Wang, Hassan Foroosh, Marshall Tappen, and Mariaana Pensky. Sparse convolutional neural networks. In Proceedings of the IEEE Conference on Computer Vision and Pallern Recognition, pp. 806 814, 2015.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the Value of Network Pruning. 2018. URL http:///arxvv.rr/aab///1/1
Christos Louizos, Max Welling, and Diederik P. Kingma, Learning Sparse Neural Networks through SL 0$ Regularization. 2018-06-22
http://arrdir.orr/bbb//7/
Lue Le Magoarou and Rémi Gribonval. Flexible Multi-layer Sparse Approximations of Matrices and Applications. 10(4):688 700, 2016. ISSN 1932-4553, 1941-0484. doi: 10. 1000/USTSP:2016.255333
URL http://arxiv.
07300
Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Variational Dropout Sparsifies Deep Neural Networks. 2017. URL http:://axxi..oo
http://aaa...rrabba////a/aaa wtt./oog///////e/ /tw.a/////1...00 05369
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading Digits in Natural Images with Unsupervised Feature Learning, 2011.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over-parametrriation in generalization of neural nelworks. In International Conference on Learning Represenlations, 2018.
Alexander Novikov, Dmitry Podoprikhin, Anton Osokin, and Dmitry Vetrov. Tensorizing Neural Networks. 2015. URL http:://arsv..rrg// abs//50b/ 06569
Tara N. Sainath, Brian Kingsbury, Vikas Sindhwani, Ebru Arisoy, and Bhuvana Ram- abhadran. Low-rank matrix factorization for Deep Neural Network training with high- dimensional output largets. pp. 6655 6659. IEEE, 2013. ISBN 978-1-4799-0356-6. doi: 10. 1109/ICASSP 2011.666999... URL http::/ieeexploreee ieee. wwwg///ccmet//eeeee... /6339499/
Karen Simonyan and Andrew Zisserman. Very Deep Convolutional Networks for Large-Scale Image Recognition. 2015. URL http:://axxv..rr//////LL0... 1556.
arg/abs/14099
Jiayun Wang, Yubei Chen, Rudrasis Chakraborty, and Stella X. Yu. Orthogonal convolu- tional neural worksrks. In Proceedings of the IEEF/CVE Conference on Compuder Vision and Pattern Recognition (CVPR), 2020.
Kailun WU, Yiwen Guo, and Changshui Zhang, Compressing deep neural networks with sparse matrix factorization. 2019.
Zichao Yang, Marcin Moczulski, Misha Denil, Nando de Freitas, Alex Smola, Le Song, and Ziyu Wang. Deep Fried Convnets. 2015. URL http::/aarrv..or//ab//11222 7149.
Michael Zhu and Suyog Gupta. To prune, or not to prune: Exploring the efficacy of pruning for model compression. 2017. URL http: http://axxvvvv.oo /at/a//www.//aaa////00111177777
10

---

Under review as a conference paper at ICLR 2021
A SUPPLEMENTARY MATERIAL
A.1 ILLUSTRATION OF THE PROPOSED METHOD
The proposed method allows network compression through the factorization of layers weights Figure g highlight the difference between the standard and compressed archi- tecture composed of convolutional and fully connected layer, where each layer weight matrix is replaced by a product of sparce matrices.
W
Convolution layer
Fully-connected layer
(a) Standard architecture
S
S1
So
Convolution layer as Product Sparse Matrices
Fully-connected layer as Product of Sparse Matrices
(b) Compressed architecture
Figure 3: Illustration of the proposed sparse factorization method.
A.2 RESHAPE OPERATIONS IN CONVOLUTIONAL LAYERS
In order apply factorization of convolutions weights, we employ reshaping operators to represent the linear operator as a dense matrix applied to all the patches extracted from an input (Garipov et al. 2016), see Figure for more details.
A.3 IMPLEMENTATION DETAILS
IMPLEMENTATION OF SPARSE MATRICES. In our implementation, a sparse matrix is in fact defined as the Hadamard product O, or pairwise product, between dense matrix that encodes the weights to be learned and matrix of constant binary elements that encodes the sparsity support. Thus, the implementation a sparse matrix DDD |S||o = O(D) is:
$ = W M,
(4)
where W E DxD is a dense weight matrix and M E (0, pxD, |M = O(D) con- stant binary matrix. With this implementation, the values of the gradient weights of W
11

---

Under review as a conference paper at ICLR 2021
(s(2)
(s(
t(rs(X)W)
X
HW
H
S
W
CS2
W
Figure 4: Description of the reshape operations and locally linear transformations computed in the convolutional layers. The grey box represent the receptive field of the convolution filters at the black dot coordinate. The white squares in the second step correspond to the zero padding of the input.
outside the sparsity support defined by M are always equal to zero and thus the correspond- ing weights of W are never updated. In other words, the sparsity support of is fixed by M. Although this implementation allows to evaluate method, the dense storage of all the values of W and M required. Specifically, 2D2 values are stored to simulate the sparsity of matrix of size D containing O(D) non-zero values. This non-optimal implementation takes advantage of the parallel algorithms of the matrix product and is actually faster on GPU than an implementation that would use Tensorflow's SparseTensor class
IMPLEMENTATION OF THE CONVOLUTION. To compute the convolutions in the network, rebuild the convolution kernel from the product of sparse matrices. Then this convolution kernel is directly used as a parameter of the Tensorflow function conv2d for fast computation.
IMPLEMENTATION THE TENSORTRAIN DECOMPOSITION. The decomposition is per- formed by applying the decomposition function Detrrixprrouutt.. Tensorly library on the tensors obtained on the pre-trained networks.
provided by the
IMPLEMENTATION OF PRUNING AS A FUNCTION OF MACNITUDE. To implement the method from Zhu & Gupta 2017), ; we used the function prune_low wtw__agnittueee from the library tensorflou model_ poodel_optmmieee owt.oppitaiiiiiiooooooooooooiiot provided by Tensorflow. With this method, the pruning and the refinement of the weights are combined by progressively removing the connections during the learning process until the desired percentage of pruning is obtained.
OF THE WEIGHTS OF A SPARSE MATRIX DECOMPOSITION. When the weights of sparse matrix factorization are not provided by palm4MSA, the initialization of the weights must be adapted to the reduced number of connections in the layer. We adapt the Xavier (Glorot & Bengio 2010) and (He al. 2015) initialization methods for sparse matrices. Specifically, the first sparse factor is initialized using the He method because ReLU activation function is apllied yielding values that are not zero-centered. The following sparse factors are initialized using the Xavier method since there is no non-linearity between factors.
A.4 PALM4MSA ALGORITHM
The palm4MSA algorithm Magoarou & Gribonval (0066) is given in Algorithm together with the time complexity of each line, using min D, D') and B Maxx(D,D1 for matrix to factorize W E DxD' Even more general constraints can be used, the constraint
'One can use the SparseTensor in conjunction with the Variable class to implement these layers sparingly and have exactly reduced number of parameters but this implementation was slower and we preferred not to use it for experiments.
12

---

Under review as a conference paper at ICLR 2021
sets Eg are typically defined as the intersection of the set of unit Froehenius-norm matrices and of a set of sparse matrices. The unit Froebenius norm is used together with the factor to avoid scaling indeterminacy. Note that to simplify the model presentation, factor is used internally in palm4MSA and is integrated in factor S1 at the end the algorithm (Tine 14) that S1 does not. satisfy the unit Froebenius norm in & at the end of the algorithm. The sparse constraints we used, as in Magoarou & Gribonval (2016), consist of trying have given number of non-zero coefficients in each row and each column. This number of non-zero cocfficients is called sparsity level in this paper. In practice, the projection function Line 9 keeps the largest non-zero coefficients in each row and in each column, which only guarantees the actual number of non-zero coellicients is al least equal to the sparsity level.
Algorithm 1 palm4MSA algorithm
Require: The matrix to factorize U DDDD the desired number of factors Q, the straint sets Eg E [Q] and a stopping criterion (e.g., here, number of iterations
1: + || {O(B)}
2: S + J; {O(B)}
3: for [1] while the stopping criterion is not met do
4: for Q down to 1 do
5:
Lg 11: S
R₂ < [ S (1+1
6:
7:
Choose > X2 R L {O(A log B B)}
8:
D+ S; A (AL,S,R, U) R {O(AB log B)}
S (i+1) Pε, (D) 10(42 log A) O(AB log B)}
9:
10:
end for
Ú.= I1
$ (f+1) {O log B AB))
11:
12: At Trace U 0) (O(AB)
Prace( O Uj
13: end for
14: SI + -S (O(B)}
Ensure: {S, : Sg Egl such that [L Sg = U
A.5 DATASET DETAILS
Experiments are conducted on four public image classification dataset: MNIST, SVHN, CIFARIO, and CIFARI00, with three pretrained network architectures: Lenet, VGG-19, Resnet50, and Resnet20. Table details the datasets' characteristics and the corresponding NN models on which we evaluated compression methods.
Nom
Input shape
# classes
Train size
Validation size
Test size
NN models
MNIST
(28 28
10
40 000
10 000
000
SVHN
(32 x 32 3
10
63 257
10 000
26 032
VGG19
CIFAR10
(32 x 32 3)
10
50 000
10 000
10 000
VGG19
CIFAR100
(32 x 3)
100
50 000
10 000
000
VOG19, Resnet55, Reanet20
Table 2: Datasets: attributes and investigated NN models.
A.6 EXPERIMENTS ON TENSOR TRAIN MEMORY OVERIEAD
Although Tensor Train can obtain impressive compression rates the method may require large amounts of memory. This memory requirement does not allow to experiment on architectures with many convolution layers with many filters, such ResNet. Table highlights the increase in memory when experimenting on investigated architectures for few hyperparameter settings. The row Others stands for requirement of all other methods.
13

---

Under review as a conference paper at ICLR 2021
Clfar1o Cifar100 VGG19
Ciffu100 Resmet20
Clfar100 Resnet50
Others
1024
65,436
65,536
65.536
65,536
262,1 14
Pensortrain R=6 K=4
2,301
396,216
335.216
393.216
384 318
1,572.864
Pensortrain R=10 K=1
2,621.440
Tensortrain R=1d K=4
5,376
917,504
917,504
917,504
917,504
3,670,016
Table 3: Magnification of a sample's representation induced by the Tensortrain layers. The maximum number of non-zero values in sampl's representatio during architecture execution is displayed.
A.7 EXPERIMENTS OF THE PROPOSED METHOD
Since the error of the matrix approximation can be high, despite the relative good accuracy, we investigate other factorization method than Palm4MSA. Specifically, two other methods evaluated. #PSM re-init.w use the same sparsity support as palm with re-initialized weights and x xPSM random> has random sparsity support and weights. Table 4 present the results and shows the supperiority of Palm4MSA.
Vgg19
Vgg19
Cifar100 Vgg19
Cifar100
Cifar100 Remer150
Bose
0.99
0.96
0.93
0.67
0.73
0.76
PSM Q Q-2K--200 K-2
0.90
0.84
0.46
0.56
0.67
PSM re re-init. Q=2 K=2
0.99
0.81
0.42
0.53
0.57
PSM random Q-2 K-2
0.98
0.91
0.81
0.44
0.48
0.41
PSM Q=2 K=14
PSM re-init. Q-2 K-14
0.98
0.44
0.36
0.57
0.63
0.63
PSM random Q-2 K-14 K-14
0.90
0.92
0.85
0.58
0.62
0.62
PSM Q=3
PSM ro-init. Q-3 K-2
0.98
0.91
0.80
0.32
0.48
PSM random K-2 K=2
0:98
0.90
0.79
0.31
0.29
0.47
PSM Q-3
0.92
0.62
11.00
0..22
PSM re-init. Q=3 K=11
0.98
0.89
0.81
0.31
0.60
0.98
PSM random Q-3 K=14
K-14
0.98
0.93
0.84
0.51
0.60
0.59
Table 4: Performance of neural network models compressed by 3 techniques of layer de- composition into sparse matrix products. <PSM> refers to the proposed procedure using Palm4MSA on the pre-trained layers; *PSM re-init> uses Palm4MSA to define the sparsity support but the weights are re-initialized; sPSM random= randomly initializes weights and sparsity support.
14


Reviews:
[{"review_id": "tvS0Fq0DeP-", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors introduced a neural network compressing method, based on factorization of weight matrix to the products of multiple sparse matrices. The goal is to achieve high compression rate. The author used a previous algorithm (Palm4MSA) to implement the method. The experiment result is better than other low-rank-based method, but is similar or worse to Iterative pruning and TT method.\n\nPros: \n\n- The introduced method is easy to understand and seems to make sense. \n- The idea of using products of multiple sparse matrices to represent the weight matrix is nice.\n\nCons:\n\n- The introduced method is almost direct application of existing algorithm (Palm4MSA).\n- The experiment result is not state-of-the-art: it is worse than Iterative pruning. The authors stated that \"an iterative-like extension of our method could reach even better results\",  so it would be important to include these results in the paper.\n\nQuestions and suggestions: \n\n- In Eq. 1, the \\prod S_i x is confusing. (\\prod S_i) x could be better.\n\n- In Fig. 1, you can use compression rate rather than actual # of parameters as the measurement. You can also use a curve to better illustrate the compression-accuracy tradeoff.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "pyY2TGsxKBR", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose to impose sparsity upon the low-rank compressions methods. Imposing sparsity is generally interesting and meaningful. The experimental results are appreciated.\n\nThere are some concerns that make this paper cannot be fully appreciated:\n1. There are so many structured matrix schemes to compress neural networks. Now, the authors claim sparsity + low-rank can provide better accuracy-efficiency tradeoff.  \n    This is surely not enough.  We compress neural networks for mobile computing devices, while the \"best\" accuracy-efficiency tradeoff is not the final goal, unless you are theoretically drawing the boundaries.  \n    A more important question with the proposed scheme is as follows: 1). the current compression schemes in the literature are good enough in balancing accuracy-efficiency. Sparsity will surely contributed. 2). however, when the compressed model is downloaded onto a mobile device, will sparse neural networks easy to run on such platforms?\n   This is a naturally question that needs an answer.  The best accuracy-efficiency tradeoff is not the final goal;  a high cost-performance is the objective to optimize. I mean you may add sparsity to achieve better accuracy-efficiency tradeoff, but we do not allow it to introducing much computation overhead of sparse computations.\n\n2. I have to raise the principle of \"simple and effective\" is the best, for this kind of tasks.\n    The previous schemes (circulant, low-rank, sparsity only, etc) are simple and shown to be effective. Now, your model is more sophisticated and the overhead is higher. Will this solution serve the purpose of compressing neural networks for mobile devices?\n    I would hope the authors do not answer too quickly.  The purpose of achieving better accuracy-efficiency tradeoff is finally making deep learning be practically deployed onto mobile devices, while computing power, memory, bandwidth and energy are limited.", "extra_scores": {}, "extra_text": {}}, {"review_id": "V6VeQ4dAhjh", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers compression of neural network weight matrices by decomposition into a product of sparse matrices. Its main contribution is an experimental study of the effectiveness of this type of compression in neural networks for image classification (MNIST and CIFAR) with standard architectures such as RESNET and VGG19. The compression algorithm, Palm4MSA, is taken from previous work. I am not familiar with other experimental studies of Palm4MSA, but the paper has a good overview of other compression methods that I am familiar with, so I trust that the overview is complete.\n\nThe main reason that I am not too excited about the paper is that the results are kind of expected. We know that architectures with much smaller number of parameters exist (a comparison with MobileNetV2 which has about 40x fewer parameters would be suitable).\n\nAs a side remark, I don't think it makes a lot of sense to distinguish between neural architecture search and neural network compression. You can think of neural architecture search as yet another compression method that happens during training (not post training).\n\nOne way of making the paper more interesting would be to consider the compression objective already during training, rather than merely fine tuning post compression. The \"PSM random\" and \"PSM re-init\" methods seem like rather arbitrary choices for comparison.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "U98elJIeqL2", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**: The paper proposes compressing the layers of the neural networks using a product of sparse matrices. This approach is in line with the initial methods on neural network compression: direct (task-independent) compression of weights, which is followed by NN task-dependent fine-tuning. In this case, the direct compression is obtained using the Palm4MSA method of Magoarou and Gribonval (2016), and then models are fine-tuned in an end-to-end fashion using TensorFlow.\n\n**Decision**: Given the contributions of the paper and the lackluster experimental evaluation, I am recommending rejection.\n\n**Detailed comments**:\nThe factorization as a product of sparse matrices is an interesting approach, and in its general form, such a scheme has not been studied in the context of neural network compression. However, the evaluation of the proposed approach is not convincing:\n\n - Effect of chaining sparse matrices for the actual inference is not discussed. As authors are well aware, the support of sparse matrix-vector products is limited in major frameworks and hardware. Therefore, chaining multiple sparse products might significantly delay the actual inference, even though it has fewer parameters and theoretically fewer FLOPs. \n\n - Comparison of different compression mechanism for neural networks is a very complex task: since most methods are applied per layer, the parameters of the compressions must be tuned per layer too: e.g., ranks/sparsity of every layer cannot have the same value, as some layers require more/fewer parameters. However, in the comparison, authors use uniform settings across layers for their method (e.g., M=4 cores) and for other methods. The conclusions under such comparison strategy have a limited value: it says that chosen hyperparameters of compression A beats the chosen (by hand) hyperparameters of compression B in terms of final compression ratio/tradeoff etc. It leaves the possibility that by tuning parameters of B we might outperform A. To fully understand the usefulness of the compression scheme, we need to ask a different question: given the scheme A and B (with the best selection of hyperparameters for both), compression using which scheme gives the smallest model for a given accuracy?  Or even better, which compression results in a better tradeoff when optimizing the shape/form of the schemes to suit the compression target?\n\n- Related to the previous point, authors miss a large body of the methods that instead of expecting the weights to be in a certain form (e.g., sparse or low-rank), actually force the network to attain such form using penalties and constraints. For example, in terms of low-rank compression, here are some of the relevant works:\n   1. Accelerating Very Deep Convolutional Networks for Classification and Detection (IEEE TPAMI 2016)\n   2. Coordinating Filters for Faster Deep Neural Networks (ICCV 2017)\n   3. Compression-Aware Training of Deep Networks (NIPS2017)\n   4. Constrained Optimization Based Low-rank Approximation of Deep Neural Networks (ECCV 2018)\n   5. Automated Multi-Stage Compression of Neural Networks (ICCV Workshops 2019)\n   6. Low-Rank Compression of Neural Nets: Learning the Rank of Each Layer (CVPR 2020)\n   7. Factorized Higher-Order CNNs with an Application to Spatio-Temporal Emotion Estimation (CVPR 2020)\n   8. TRP: Trained Rank Pruning for Efficient Deep Neural Networks (IJCAI 2020)\n\nThere is an equally large body of literature on network sparsification. Please add the comparison to best-in-its-class results from the literature in order to fully evaluate the proposed scheme.\n\n*Minor concerns*:\nI strongly believe citing Li Deng for the MNIST dataset is inadequate.  Please correct.\n\n*Post rebuttal comments*: I appreciate the author's efforts for the rebuttal, however, the feedback did not adequately address my questions. I am not changing the score.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The idea of using multiple sparse matrices seems to be new, but the novelty of the idea alone isn't enough to convince the AC and reviewers (indeed, the idea might not be new, but has never been discussed in literature because of the drawbacks we discuss here). As the authors and reviewers/AC seem to agree, the actual benefits of sparse matrix multiplies are hard to realize, especially on embedded devices, so the contributions at this point are mainly hypothetical and only about the new idea. Each reviewer brought up issues (even the most positive reviewer) and mostly the reviewers were not persuaded by the rebuttal. In short, there wasn't evidence that this new idea could really contribute to the state-of-the-art.  This is now a fairly crowded topic (e.g., all the  papers brought up by R3 in just that one class of methods), and new papers should beat state-of-the-art and/or introduce new theory -- an example would be a paper from last year's ICLR, https://openreview.net/forum?id=HJfwJ2A5KX , "Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds" (Baykal, Liebenwein, Gilitschenski, Feldman, Ru) which not only gives an efficient technique (not based on sparsity of weights) but also gives types of generalization guarantees.

As R1 said, the results are not state-of-the-art, and we have to believe the authors that "an iterative-like extension of our method could reach even better results". The rebuttal says that the paper's goal is to "pioneer a new approach to neural network compression". But if you can get better results with something better than Palm4MSA, then please do so, and demonstrate the evidence!  Right now, the paper assumes we could implement sparse multiplication efficiently on embedded devices, and assumes we could get better results: both these are quite hypothetical. The AC encourages a resubmission of this paper after these results have been addressed.
Decision: Reject