"Lossless" Compression of Deep Neural Networks: A High-dimensional Neural Tangent Kernel Approach
Authors: Lingyu Gu
Yongqi Du
Yuan Zhang
Di Xie
Shiliang Pu
Robert C Qiu
Zhenyu Liao
Venue: NeurIPS 2022 Accept (2022)
Keywords: Deep learning theory
high-dimensional statistics
neural network compression
neural tangent kernel
random matrix theory.

Abstract: Modern deep neural networks (DNNs) are extremely powerful; however, this comes at the price of increased depth and having more parameters per layer, making their training and inference more computationally challenging. 
In an attempt to address this key limitation, efforts have been devoted to the compression (e.g., sparsification and/or quantization) of these large-scale machine learning models, so that they can be deployed on low-power IoT devices.
In this paper, building upon recent research advances in the neural tangent kernel (NTK) and random matrix theory, we provide a novel compression approach to wide and fully-connected \emph{deep} neural nets. 
Specifically, we demonstrate that in the high-dimensional regime where the number of data points $n$ and their dimension $p$ are both large, and under a Gaussian mixture model for the data, there exists \emph{asymptotic spectral equivalence} between the NTK matrices for a large family of DNN models. 
This theoretical result enables ''lossless'' compression of a given DNN to be performed, in the sense that the compressed network yields asymptotically the same NTK as the original (dense and unquantized) network, with its weights and activations taking values \emph{only} in $\{ 0, \pm 1 \}$ up to scaling. 
Experiments on both synthetic and real-world data are conducted to support the advantages of the proposed compression scheme, with code available at https://github.com/Model-Compression/Lossless_Compression.

"Lossless" Compression of Deep Neural Networks: A High-dimensional Neural Tangent Kernel Approach
Lingyu Gu
Yongqi Du
Yuan Zhang Di Xie
Shiliang Pu
Robert C. Qiu
Zhenyu Liao
EIC, Huazhong University of Science and Technology, Wuhan, China Hiikvision Research Institute, Hangzhou, China
Abstract
Modern deep neural networks (DNNs) are extremely powerful; however, this comes the price of increased depth and having more parameters per layer, making their training and inference more computationally challenging. In an attempt to address this key limitation, efforts have been devoted to the compression (c.g., sparsification and/or quantization) of these large-scale machine learning models, so that they can be deployed on low-power IoT devices. this paper, building upon recent advances in neural tangent kernel (NTK) and random matrix theory (RMT), we provide novel compression approach to wide and fully molly-connecttd deep neural nets. Specifically, we demonstrate that in the nigh-dimensional regime where the number data points n and their dimension p are both large, and under a Gaussian mixture model for the data, there exists asymplotic spectral equivalence between the NTK matrices for a large family of DNN models. This theoretical result enables "lossless" compression of given DNN to be performed, in the sense that the compressed network yields asymptotically the same NTK as the original (dense and unquantized) network, with its weights and activations taking values only in {0, =1} up to a scaling. Experiments on both synthetic and real- world data conducted to support the advantages of the proposed compression scheme, with code available at luttps://gg thub. com com/Modell Caasless_Compressse
Introduction
Modern deep neural networks (DNNs) are becoming increasingly wer-parameterized, having more parameters than required to fit the also increasingly large. complex, and high-dimensional data. While the list of successful applications of these large-scale machine learning (ML) models rapidly growing, the energy consumption of these models is also increasing, making them more challenging to deploy on close-to-user and low-power devices. To address this issue, compression techniques have been proposed that prune, sparsify, and/or quantize DNN models [14 23] thereby yielding
DNNs of much smaller size that can still achieve satisfactory performance on a given ML task. As an illustrative example, it has been recently shown that at least 90% of the weights in popular DNN models such as VGG19 and ResNet32 can removed with virtually no performance loss (53)
Despite the remarkable progress achieved by various DNN model compression techniques, due to the nonlinear and highly non-convex nature of DNNs, our theoretical understanding of these large-scale ML models, as well as of their compression schemes, is progressing at a more modest pace. For
Equual contribution, listed in a random order by rolling a dice on WeChat.
Author whom any correspondence should be addressed. Email: zhenyu_ Jiao hust.edu.cn
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

example, it remains unclear how much a given DNN model can be compressed without severe performance degradation; perhaps more importantly on the degree to which such a performance and complexity trade-off depends on the MI. task and the data also remains unknown.
In this respect, neural tangent kernels (NTKs) 28 provide a powerful tool for use in assessing the convergence and generalization properties of very wide (sometimes unrealistically so) DNNs by studying their corresponding NTK eigenspectra, which are solely dependent on the input data, the network architecture and activation function, as well as the random weights distribution
In this paper, building upon recent advances in random matrix theory (RMT) and high- -iseesiinns statistics, we demonstrate that for data Xi...., Xx E IR" drawn from a K -lllass Gaussian mixture model (GMM), in high-din fighh-imensional and non-trivial classification regime where the input data dimension and their size n are both large and comparable, the eigenspectra of both the NTK and the closely related conjugate kernel (CK) matrices any layer & {1,..., L.} are independent of the distribution of the i.i.d. entries of the (random) weight matrix We, provided that they are "normalized" have zero mean and unit variance, and only depend on the activation function ar(-) four scalar parameters. In a sense, we establish, at least for GMM data, the asymptotic spectral equivalence between the CK and NTK matrices of the corresponding network layers, and consequently of the whole network, for a large family of DNN models with possibly very different weights and activations, given that they have normalized weights and share the same few cntrvatioo-relatte parameters.
Since the convergence and generalization properties of wide DNNs depend only on the eigenspectra (i.e., eigenvalue-eigenveetoo pairs; see also Remark D below) of the corresponding NTK matrices 28 18]. in the sense that, e.g., the time evolutions (when trained with gradient descent using a sufficiently small step size) of both the residual error and the in-sample prediction of the network can be expressed as explicit functions of NTK eigenvalues and eigenvectors [18] | 26). we further exploit the above theoretical results propose novel "lossless" compression approach for fully- connected DNN models, by designing a sparse and quantized DNN that (i) has asymptotically the same NTK eigenspectra as the original "dense and full precision" network, and (ii) has both weights and activations taking values in the set { 0, +13 before scaling, and can thus be stored and computed much more efficiently.
Despite being derived here for Gaussian mixture data, an unexpected close match is observed between theory and the empirical results on real-world datasets, suggesting possibly wider applicability for the proposed "lossless" compression approach. Looking forward, we expect that our analysis will open the door improved analysis of involved ML methods based on RMT and nigh-dimensional statistics, which will demystify the seemingly striking empirical observations in, say, modern DNNs.
1.1 Our contributions
Our main results can be summarized as follows:
1. We provide, in Theorems 1 and respectively, for GMM data and in the high-dimensional regime of Assumption 1. precise eigenspectral characterizations of CK and NTK matrices of fully-connected DNNs; we particularly show that the CK and NTK eigenspectra do not depend on the distribution of i.i.d. network weights, and depend solely on the activation function of each layer via few scalar parameters.
2. In Corollary [and Algorithm I we exploit these results to propose a novel DNN compression scheme, with sparsified and ternarized weights and activations, without affecting the NTK spectral behavior, and thus the convergence and generalization properties of the network.
3. We provide empirical evidence on (not so) wide DNNs trained on both synthetic Gaussian and real-world datasets such as MNIST (3T] and CIFARIO (30], and show factor of 1 less memory is needed with the proposed DNN compression approach, with virtually no performance loss.
In the remainder of this article what we refer to as the "NTK matrix" is essentially the limiting (and nonrandom) NTK matrix which the random NTK converges under the infinite-wii wide limit.

---

1.2 Related work
Neural network model compression. The study of NN compression dates back to early 1990 [32], at which point, in the absence of the (possibly more than) sufficient computational power that we have today, compression techniques allowed neural networks to be empirically evaluated on computers with limited computational and/or storage resources 49] Alongside the rapid growth of increasingly powerful computing devices, the development more efficient NN architectures and training/inference protocols, and the need to implement NNs on mobile and low-power devices, (D)NN model compression has become an active research topic and many elegant and efficient compression approaches have been proposed over the years [22 25 27 23 However, due to the nonlinear and highly non-convex nature DNNs, our theoretical understanding of these large- scale ML models, as well as of (e.g., the fundamental "performance and complexity" trade-off of) compressed DNNs, is somewhat limited 23
Neural tangent kernel. Neural tangent kernel (NTK) theory proposed in 28 by considering the limit of infinitely wide DNNs, characterizes the convergence and generalization properties of very wide DNNs when trained using gradient descent with small steps. Initially proposed for fully-
connected nets, the NTK framework has been subsequently extended convolutional (5), graph [16],
and recurrent [3] settings. The NTK theory, while having the advantage of being mathematically more tractable (via, e.g., the characterization of the associated reproducing kernel Hilbert space [8] seems to diverge from the regime on which modern (and not so wide) DNNs operate, see [T0 38
Random matrix theory and neural networks. Random matrix theory (RMT), a powerful and flexible tool for assessing the behavior of large-scale systems with a large "degree of freedom",
gaining popularity in the field of NN analysis [44 45], in both shallow 48
37 and deep 47 settings, and for both homogeneous (c.g., standard normal) [4]] 46 and mixture-type data
36
7
36
From a technical perspective, the most relevant paper is 4 in which the authors proposed a
RMT-inspired NN compression scheme, albeit only in the single-hidden-laye setting. This paper extends the analysis in 4 to multi-layer fully- calle-connected DNNs, by focusing on both the CK and NTK matrices, and proposes novel sparsification and quantization scheme for fully-connected DNNs (which is spirit similar to, although formally different from, that in (4).
1.3 Notations and organization of the paper
We denote scalars by lowercase letters, vectors by bold lowercase, and matrices by bold uppercase. We denote the transpose operator by (.) and use || to denote the Euclidean norm for vectors and the spectral/operator norm for matrices. For a random variable B[2] denotes the expectation of z. We use 1, and Ip to represent an all-ones vector of dimension p and the identity matrix of size p x p.
The remainder of this article is structured as follows. In Section 2 we present the fully-connected DNN model under study, together with our working assumptions. Section 3 contains our main technical results on the eigenspectra of the conjugate kernel KCK and NTK matrix KNTK. along with an account of how they apply to the compression of fully-connected DNNs with the proposed "lossless" compression scheme. Empirical evidence is provided in Section 4 to demonstrate the significant computation and storage savings, with minimal performance degradation, that can be obtained using the proposed approach. Conclusion and future perspectives are placed in Section 5
2 Preliminaries
Let Xi,..., Xx E IPP be n data vectors independently drawn from one of the K K-class Gaussian mixtures CI.... Ck. and let X [xi....,,, X,] 12 with class Co having cardinality na; that is,
x, E C. + x, ~ Nu Vp. C./p).
(1)
for mean vector H4a RP and covariance matrix C2 E RPXP associated with class Ca.
In the nigh-dimensional scenario where p are both large and comparable, we position ourselves in the following non-trivin -riviiiial classification setting, so that the classification of the K-class mixture neither trivially easy nor impossible; see also [13] and ( Section 2].
Assumption 1 (High-dimmensional asymptotics). As n - xc, we have, for a E fl,..., ..., that (i)
for p/n + E (0, oo) and na/n + ca E [0, 1): (i) || O(1); (ii) for C = Ex au C.
3

---

and C. = C. CP, we have |Ca| = 0(1), tr C = Olvp) and Cr) O(p) for a, b E [I....,K], Ki and (iv) To vtr C converges in (0, 00).
We consider using a fully-connected DNN model of depth I for the classification of the above K-class Gaussian mixture. Such a network can be parameterized by a sequence of weight matrices W E pd xdo ..... Wt E Rdrxxd-11 (with the convention do p). and nonlinear activation functions 01,..,,0 that apply entry-wise, that the network output f(x) E R is given by:
vdz [(x) woo or. (V (Va
1 WLo (...
1 (.to
W201 (W (Wix)))) (VT,
(
(2)
for an input data vector x E RºP and output vector E RRdz. We denote Eg E Rexx the representations of the data matrix X E Rpxx layer E (1.....I) defined
(VLL Were-1 (...
1 ("VVT0>> ( (VT, W W (Wix)
Σg
Vix Ti
(3)
The normalization by 1/ dd follows from the NTK literature and ensures the consistent asymptotic behavior of the network in the sigh-dimensional setting in Assumption [
and 2 see also 22 8 [8].
The training and generalization performance of the NN model defined in 2 are closely related to two types of kernel matrices: the Conjugate Kernel (CK) matrix and Neural Tangent Kernel (NTK) matrix, defined respectively for é E (1,..., [ as follows:
Kck,t E Σg] E R"*"
(4)
with expectation taken with respect to the random weights Wi...., We and Σg E RR x the data representation the output of layer e defined in 33. In particular, CK matrices are known to satisfy
the following recursive relation 28 g
Kc Eu,, (or with u, e N (1, KcK,e-Iaa KcK,e-Ilis]
)
(5)
KCK,e-ili
K KcK,t-1ljs))
while for the NTK matrix KNTK, E Raxn of layer e, we have:
KNTK, KCK, KNTK.e- K'K, KNTK,0 = KCKO0 = =
where AA o B' denotes the Hadamard product between two matrices A, B of the same size, and K'C,e denotes the CK matrix with nonlinear function of instead of a as for KCK,t defined in (5): that is, (Kc (u,,lo'(()))((t)) Note in particular that for a given DNN model, the corresponding CK and NTK matrices depend only on the network structure (i.e., the number of layers and the activation function in each layer), the distribution of the random (initializations of the) weights be integrated over (e.g.. in the expectation in equation 44 ), and the input data.
has been shown in a series of previous efforts (28 18 26] that for very (and sometimes unrealis- tically) wide DNNs trained using gradient descent with small step size, the time evolution of the residual errors and sampe predictions of given DNN are explicit functionals of the corresponding KNTK involving its eigenvalues and eigenvectors. In this respect, the NTK theory provides, via the eigenspectral behavior of KNTK, precise characterizations of the convergence and generalization properties of DNNs 28 8) by focusing on the impact of the network structure, the input data, and the weight initialization schemes.
In this paper, we focus on fully-connected nets under the following assumption regarding the weights. Assumption 2 (On weight initializations). The random weights W1 E R WL E Rd xdz-1 independent and have i.i.d. entries of zero mean, unit variance, and finite fourth-order moment.
Assumption together with the 1/vde normalization, compatible with fully-connected DNNs in (2). which are admittedly less interesting, from practical perspective, compared to their convolutional counterparts. The proposed framework is envisioned to be extendable to a convolutional [5] g and more involved setting (e.g., graph NNs (16) by considering (e.g.. Toeplitz-type) structures Ws.
we do not assume the Gaussianity of the entries of W,s. but only that they are i.i.d. and "normalized" to have mean and unit variance. As it turns
Unlike most existing NTK literature 28 g 17

---

out, this assumption together with (Lyapunov- -tpee) central limit theorem argument, is sufficient to establish most existing results on the convergence and generalization of DNNs; see for example [34
We also need the following assumption on the activation functions in each layer. Assumption 3 (On activation functions). The uctivations 01....,
01 ,0, are least four-times differen- (k)
tiable with respect to standard normal measure, in the sense that m (0, ( (0)) < <C for some universal constant C >> 0, & N/ 1), and & [I....,L]..
Using the Gaussian integration by parts formula, has (E) ([] for ~~ (0, 1), as long as the right-hand side expectation exists. As result, for non ein-ifferrntiable functions, it suffices to have loe upper-bounded by some (high-degree) polynomial function for Assumption to hold.
With these preliminaries, we are now ready to present our main technical results on the eigenspectral behavior of the CK and NTK matrices for large family of fully-connected DNN models.
3
Main results
For a fully-connected DNN defined in 2). our first result is on the eigenspectral behavior of the corresponding CK matrices KcK defined in (4) More specifically, show for Gaussian mixture data in | and in the high-dimensional setting of Assumption | that the KCK, of layer & {l,..., L} is asymptotically spectrally equivalent to another random matrix KcK,,, in the sense that their spectral norm difference ||KCK KoK sll vanishes as n. P oo. This result is stated as follows, the proof of which is based on an induction on and is given in Section of the appendix.
Theorem (Asymptotic spectral equivalents for CK matrices). Let Assumptions D hold, and let 2 0 be sequence of non-negative numbers satisfying the following recursion:
TO, Th,
Tt - (io (~,(1,,), (E......,
Further assume that the activation activationfuunciionn oe(-)s are "centered," such that (T Then, for the CK matrix KCK, of layer & E {0, 10.1,..., L) defined in (4) as n, oc, one has thut:
|KCK,e Kek,el ell +0, KCK, x VA.T (Tē Ta.r, T6 Td,,,))
(8)
almost surely, with
vb) Rnx(K+D) A Sar,ttT + +
ar,2t
V V=
E <R(K+DI(K+D)
a,,2
ag,
for class label vectors = li......jkii jkl E guxk with [ia] 8x,Ec,, second-order data fluctucation vector 1/ {||x E|x,]
t = Ctr - E| E[x, E RR" second-order discriminative statistics
E RK and T = (tr C, Ca Ca/pla. E RR of the Gaussian mixture in (I.
as well as nen-negative scalars 06,100.21 02,3 satisfying the following recursions:
ac, (((((T-
0g2 Blo'(Te- 11] at- 1.2 + 2 ((
(10)
01,3 E(o'( (
Elo" (To 12
(11)
with 0² 1E (o)((T- + ( (Te-EE) for ~ 1)..
A few remarks Theorem are in order. The first remark is the assumption Ejoe(Te-1E) 0.
O. seemingly restrictive at first sight, infal fact only subtracts an identical constant from all entries of the data representation Eg a layer E, and should therefore not restrict the expressive power of the network, nor its performance on downstream ML tasks. For given DNN model of interest, suffices to "center" the output of each layer by subtracting a constant satisfy Assumption 3 and to further upply our Theorem 7
Remark (On activation centering). The condition B(ox(Te-1E)
Theorem I unveils the (possibly surprising) fact that, for the high-dimensional and non-trivial Gaussian mixture classification ( the spectral behavior of K KcK,,, and thus that of the CK matrix KCK, is (i) independent of the distribution of the (entries of the) weights We when they are
5

---

"normalized" to have zero mean and unit variance, as demanded in Assumption 2 and (ii) depends on the activation function d2 only via four scalar parameters ag,1, 2, 44,3 and Ty. such universal results have been previously observed in random matrix theory and high-dimensional statistics and indicate some kind of universality of DNN models.
literature (see for example [2 6 56]
On closer inspection of Theorem we further observe that:
(i) for given DNN, Theorem | characterizes, via the form of KcK, e in (8) and the recursions in (10) and T how the linear (via ag,1, which is multiplied by X and nonlinear (via 0,,, and 0g in Ae, which respectively weight the second-order data statistics t and T) data features "propagate" in DNN, in a layer-by-layer fashion, as l' increases, quantitatively measured by the corresponding ags; and
(ii) for two DNNs with the same number of layers, but possibly different weights and activations, given the same input data X (so that the two nets have the same KcK,o). if they have asymptotically equivalent CK matrices KcK,6- layer e é- 1 with the same ag-11.1; Qg-1,2 and 1,3- 1,3, then its follows from Equation (TO) and (11) that having the same (Te (T= and B[[o) (TE-1E))) (which only depends on the activation of layer & and 72-1) suffices for the two nets to have asymptotically equivalent Kck.t layer E.
It follows from the above item (ii) that for given DNN of depth L, it is possible to design novel DNN model that "matches" the original one - in the sense that both models will have asymptotically equivalent CK matrices each layer, by using the following layer-by-layer matching strategy: Starting from the same KCK,0 = X",, one chooses the first-layer weights W, of the novel DNN according Assumption [ and then select the first-layer activation 0 in such way that the novel net has the same parameters Q1,1, 01,2 and 01,3 as the original one, so that the first-layer CK matrices Kck,1 the two nets are spectrally matched as per Theorem | one then proceeds similarly match the second, the third, etc., and eventually the Lth layer of the two nets. As we shall see below, this layer-by-layer matching strategy facilitates the "lossless" compression of a given DNN.
Using the relation in (6), a similar result (as in Theorem I for CKs) can be established for NTK matrices, shown in the following theorem. The proof is also based
induction on E and is
provided in Section A.2 of the appendix.
Theorem 2 (Asymptotic spectral equivalent for NTK matrices), Let Assumptions 3 hold, let the activations (-)))s be centered so that Elore(T--EE) for TES defined (7). let fo, .,...., tL 27.20 be a sequence of non-negative numbers satisfying the following recursion:
: -2=vB B (()(tt)1)))) E 10,,1, L E
L}.
(12)
with to To (which is similar the defined in 7 but the derivative of instead of itself). and let KKL 2
KL
be a sequence of non-negative numbers satisfying
Ke = / kte)( ((,10, LE (L....,L}; L}.
(13)
with Ki = To. Then, for the NTK matrix KNTK, of layer i defined in (6), as n. - co, one has that
KNTK, - KNTK, + O, KNTK, = Br, x VB. + + - To. 3r,1 - To (r,aaa (14)
almost surely, with V E R1x((+1), tE RERR, REE as defined in Theorem and
B
Br,ttt Br.TT
Br
(K++))((++))
(15)
Be
BE
as well as scalars Be, B,, , 30,3 2 0, and de, die, such that
B = a1,1 Be
3e 0g, + Be- Be, 04,3 + Bt 3t + B (16)
IIt is worth noting that the parameter 72 appears in the CK eigenspectrum only by shifting all its eigenvalues (by 7f), thereby acting an (implicit) ridge-type regularization in DNN models, see also 22 [5 39]

---

and
tr-1 de-1 E1 + /
= 1e
of of(fe-iEioo
d Eo + v V
(or- it-1
1 de- Vden
0r, -Egi
of(te-1Eioo
E1
Ft-1
Fz
with A0-1= 12-
di for independent Ei, ~ 1).
Roughly speaking, Theorem shows that the eigenspectral behavior established Theorem foo CK matrices also holds for NTK matrices, up to a change of the associated coefficients ags to 3rs. The remarks after Theorem thus remain valid, at least in spirit, for NTK matrices.
Remark 2 (On spectral norm characterization). Note that the characterizations in Theorem 2 and for CK and NTK matrices are provided in a spectral norm sense. It then follows from Weyl's inequality (24] and the
theorem (6T] that the difference between the eigenvalues (e.g.. when listed in a decreasing order) and the associated eigenvectors (when the eigenvalues under study are "isolated") ) of KNTK and KNTK vanish asymptotically as n.P - OC. As such, the spectral norm guarantees in Theorem A more tractable access to the convergence and generalization properties of wide DNNs, at least for GMM data, via the spectral study of KNTK 128 [8].
Despite being derived here for the Gaussian mixture model (T). we conjecture that the results in Theorem and 2 hold beyond the Gaussian setting and extend, for example, to the family of concentrated random random vectors [50 33]. As discussed after Assumption 2 for the distribution of W. such universality commonly arises in random matrix theory and nigh-dimensional statistics we refer interested readers to Remark 4 in Appendix A for further discussions.
12 6 |
From technical perspective, the results in Theorem 1 and 2 extend the single-hidden-layer CK analysis in 36 both CK and NTK matrices of fully-connected DNNs with an arbitrary number of layers. In particular, taking E = 1 in Theorem | one obtains 4 Theorem 1] as special case W
Remark (On CK and NTK matrices). It follows from Theorem thht for a given DNN model, suffices to match the coefficients ae, 00,2 and 0x,3 in layer-by-layer manner to propose novel DNN with asymptotically equivalent CK matrices. Similarly, matching the key coefficients Be, Be, and Be, leads to DNN model with asymptotically equivalent NTK matrices. Moreover, for two nets with the same 0t,1, 2 04 3, and therefore the same CKs, it suffices to match the additional de, òr to render the two nets asymptotically equivalent in both CK and NTK senses.
In the following corollary, we present concrete example of how apply the results in Theo- rem and in the design of novel computationally and storage efficient DNN, that shares the same CK and NTK eigenspectra with any given fully-connectes neural net having centered activation.
Corollary 1 (Sparse and quantized DNNs). For a given fulennfflllycccceco of depth L with centered activation such that ((o=(TT-1E)] 0 for { (O, 1), one is able to construct, say in a layer-bylayeer manner, a sparse and quantized "equivalent" DNN model, of depth L and referred to as DNN2, such that the two nets have asymptotically the same eigenspectra for their CK (and NTK similarly, as per Remark 3) matrices, by using the following ternary weights:
DNN (referred to as DNN1)
[Wes = 0 with proba E E 10, [W]; +(1 - e)- each with probu 1/2 - 8/2, (17)
as well as quantized activations (as visually displayed in Figure 7]:
or (t) =a aa. (Lece, + +esss),
(t = b1 (Leers + LesTa) + by Iru
(18)
We refer readers to Appendix A.4 for the proof and discussions of Corollary D as well as the detailed expressions of E[o' (rE)), (olo(()))) and (o(((2(T)))") of direct algorithmic use for both or and oq as functions of the parameters a, $1, $2 and b1, b1, F1, T3, T4. Built upon Corollary [ we propose a DNN "lossless" compression scheme with equivalent CKs, as summarized in Algorithm below.
'Note that in 4 Theorem 1], the authors do assume (m))) "center" the CK matrices by pre- and post post-muuti Kes with P = 1. 1, //2. This can be shown equivalent to taking [[o((T)) = 0 in the single- siggel-iiden-llyeee setting; see Appendix A.3 for more details.
as in our Theorem hut instead
7

---

$1
82
[[or(TE))
erf
erf
+ a
2
V2T
V2T
B[oo(TE))
1
erf
71
crf
T4
+ bj
0
2
V2T
/2T
0
+
b2
erf
r3
erf
1'2
2
/2T
/2T
P1
12
81
82 13
74
Figure 1: Visual representations of activations or and σQ in (18) (left) and the expressions of Blor (TE) and ((og(r)))) with 12 rg 14 here and e-) the Gaussian enror function.
Algorithm "Lossless" compression scheme for fully-connected DNNs
1: Input: Input data XI...., X.. sparsity level ε E [o. 1), and DNN1 with activations oi,.... TT.
2: Output: Sparse and quantized model DNN2 with weights W, and activations oe. E (1, fl..... LJ.
3: Estimate To from data To
Σ x
Set 7 To for DNN1, and 7 for DNN2.
4: for 1,...., I, do
5: Compute 0g,1, 02,2, 0g23 of DNN1 using 7t-1, and derive the expressions of ( 0ke 0rg,3 DÑN2 using fz-1 as per (10) and (II).
6: Solve, with Corollary 1 and the detailed expressions in Appendix A.4 the system of equations (at,1, 22,2, ā2,3) for the parameters , 82, to get the activation ãg of
(or,, O, (kg,3)
DNN2 layer L.
Update T, 7 as
(T and (TE)
8: end for
9: For the layer f L. compute aL,1, aL, aL,3, TL and ă áz āL,3, Fz. Use them solve for the parameters b1. b2, 72, F3. F4 to obtain the activation ã of DNN2 at layer t. Draw independently the i.i.d. entries of W....., W according to (17 with sparsity level return DNN2 model with weights W. and activations og, l 1.....
11:
As side remark, note that the "sign" of activations does not matter in Corollary I Algorithm I in the sense that the key parameters ag,1, 02,2, and 0g,3 for CKs, as well Bt,1, Be.2, and 81,3 for NTKs, remain unchanged when (t) is used instead of (t)
would like bring the [4 19] showing that for wide and deep NN models, very efficient sparse sub-networks can be found that almost match the performance of the original dense nets with little or even no training, for instance by uniformly pruning the network weights [53]. To develop theoretical grasp of these (extremely counterintuitive) empirical successes, a few attempts have been made, for example, to carefully prune the network weights to retain the same (limiting) NTK 40]. or show that randomly pruned sparse nets have the same (limiting) NTK as the original net to a scaling factor (60). Instead, our work, by considering the statistical structure of the input data, leverages tools from RMT to "compress" both the weights and activations (per Theorem and Corollary T without affecting the NTK eigenstructure.
Before embarking the detailed numerical experiments in Section
readers' attention to the recent line of works 35 53 57
4 Numerical experiments
In this section, we provide numerical experiments to (i) validate the asymptotic characterizations in Theorem
[ and 2 on both synthetic GMM and real-world data (such as MNIST and CIFAR10) of (in fact not so) large sizes and dimensions; and to (ii) show how these results can used to sparsify and quantize fully-connected DNNs, leading to huge savings in computational and storage resources (up to factor of 103 in memory and a level of sparsity & 90%) without significant performance degradation. We refer readers to Section B in the appendix for further experiments and discussions.

---

10
10
Eigs of K
Figs K
Eigs of K
Rigs
Count
Count
Count
Count
0.5 Eigeowalee
0.5 Eigenwalte
30
Eigenwaiee
Eigenvaiu
Amplaude
Amplionie
4000
3000
1600
3200
Index
Index
Figure 2: Eigenvalue histograms (top) and dominant eigenvectors (bottom) of last-layer CK matrices Kek (blue) defined in 4 (with expectation estimated from 000 independent realizations of Ws) and the asymptotic equivalent KCK (red) matrices. (Left) Gaussian W on two-class GMM data, with
p 2000, n 8 0000, a = [sj 8; 0p-80+7]: C. = (1 + 8(a 1) Ip. a {1, 2] using [ReLU, ReLU, ReLUJ activations, here KCK - KCK || = 0.15; and (right) symmetric Bernoulli W on MNIST data (number versus 8) [31,, with p = 784, n 200, using [poly, ReLU, ReLU]
activations, |cck- Kckll = 6.86. X1...., Xn/2 C1 and / Xn E C2 in both cases.
Figure 2 compares the eigenvalues and dominant eigenvectors of the CK matrices Kok defined
in versus those of their asymptotic approximations KOK given in Theorem 1 in the case of fully- fully-coneccted DNNs having three hidden layers (of width di = 2000, d2 2000, dg = 1 000). For different types of activations: poly(!) 0.2/2 I and ReLU(()) = max(t, 0), different weight distributions (Gaussian and symmetric Bernoulli), and on synthetic GMM as well as MNIST data, we consistently observe close match between the eigenvalues and dominant eigenvectors of KeK and KeK. as a consequence of the spectral norm convergence in Theorem (and Remark 2). suggesting a possibly wider applicability of the proposed results beyond GMM data
Following the idea of CK matching in Figure 2 Figure B depicts the test accuracies of (i) the original dense and unquantized network with three fully culle-connected layers, (ii) the proposed "lossless" well as its
compression scheme described in Corollary [ and Algorithm | via CK matching, variant having ternarized weights but dense and unquantized activations, (iii) the popular magnitude- based pruning approach as in [20). together with (iv) two "heuristic" compression approaches: (iv-i) sparsification by uniformly zeroing out 80% of the weights (we cannot do more, as the resultant performance is too poor to be visually compared with other curves), and (iv-ii) binarization using (l) = -- +1, I, for different choices of width per layer, and the ten-class classification problems of MNIST and CIFARIO. Specifically, neural networks before and after compression have three fully-connected layers, and the original network uses ReLU activation in each layer. Classification is performed on concatenated and trainable fully-connected layer. For MNIST datasets, raw data are taken as the network input: for CIFARIO dataset, flattened output of the 16th convolutional layer of VGG19 5 are taken as the network input.
We observe from Figure 3 that the proposed "lossless" compression scheme produces significantly sparser networks (up to 90% of weights set to zero) with minimal performance loss, while occupying (up to) a factor of 10 less memory, when compared to the original or the heuristically compressed nets. Also, higher accuracies are obtained with the proposed approach than, e.g., the popular magnitude-based pruning under the same memory budget. In addition, the ternary weights variant (with quantized weights only) of the proposed scheme can achieve even better performance (with virtually no performance loss compared to the original dense net), however at the price of not conducive to inference accelerating, since the activations are unquantized. We also see that the sparsity level e has limited impact on the classification accuracy, as in line with our theory.
"Small eigenvalues of KCK, KCK close to removed from Figure 2 for better visualization.

---

These experimental results show that the proposed approach achieves better performance- trade-off than commonly used heuristic DNN compression methods.
Accuracy
0.8
0%
0.6
50%
90%
100
10
10
10"
10
original dense naive quantized
Memory (bits)
0.9
naive sparse
mased pruning
Accuracy
0.85
temary weights
0.8
0.65
1
10
10
10
10
10a
10
Memory (bits)
Figure 3: Classification accuracies of different compressed fully-connected nets on MNIST [31] (top) and CIFARIO 30 (bottom) datasets. Blue curves represent the proposed compression approach with different levels of sparsity {0%, 50%, 90%}. purple curves represent the heuristic sparsifi- cation approach by uniformly zeroing out 80% of the weights, green curves represent the heuristic quantization approach using the binary activation (t)) = 1, - + 1 red curves represent the original network, brown curves represent the proposed compression approach without activation quantization, with 90% for MNIST (top) and 95% for CIFAR 10 (bottom), and orange curves represent magnitude-baset pruning (20) with the same sparsity level e as brown. Memory varies due to the change of layer width of the network.
Conclusion and perspectives
In this paper, built upon recent advances random matrix theory and ditbe-iinniioall statisties. we provide precise characterizations of the eigenspectra of both conjugate kernel and neural tangent kernel matrices, for high-dimensional Gaussian mixture data and fully-connected multi-layer neural nets. These results further allows us to sparsify and quantize fully- culle-connected deep nets, resulting in factor of 10 less memory consumption with virtually no performance degradation.
Extending the present theoretical framework to more involved settings such as convolutional nets requires refined analysis on the block Toeplitz weights W and on their connection to the corresponding CK and NTK matrices [5] (59). Also, since the NTK eigenspectra determine the gradient descent dynamics of ultra-wide deep nets, the asymptotic characterizations in Theorem can be applied to assess the learning dynamics [37 of fully-connected DNN models, in and possibly beyond the infinitely wide NTK regime.
Acknowledgments and Disclosure of Funding
ZL would like to acknowledge the CCF-Hikvision Open Fund (20210008), the National Natural Science Foundation of China (via fund NSFC-62206101 and NSFC-12141 107), the Fundamental Research Funds for the Central Universities of China (2021XXIS1 10), the Key Research and De- velopment Program of Hubei (2021BA BAA037), and the Key Research and Development Program of Guangxi (GuiKe-AB2) 196034) for providing partial support.
10

---

References
[1] Ben Adlam and Jeffrey Pennington. The Neural Tangent Kernel in High Dimensions: Triple Descent and Multi-Scale Theory of Generalization. In Proceedings of the 37th International Conference on Machine Learning, volume 119 Proceedings of Machine Learning Research, pages 74-84, PMLR, 2020.
[2] Madhu S. Advani, Andrew M. Saxe, and Haim Sompolinsky. High High-dimensional dynamics of generalization error in neural networks, Neural Networks, 132:428 446, 2020.
[3] Sina Alemohammad, Zichao Wang, Randall Balestricro, and Richard Baraniuk. The Recurrent Neural Tangent Kernel. arXiv, 2020.
[4] Hafiz Tiomoko Ali, Zhenyu Liao, and Romain Couillet. Random matrices in service of ML footprint: ternary random features with performance loss. In International Conference on Learning Representa- tions, 2022.
[5] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov. and Ruosong Wang. On Exact Computation with an Infinitely Wide Neural Net. In Advances Neural Information Processing Systems, volume 32, 2019.
[6] Zhidong Bai and Jack W. Silverstein. Spectral Analysis of Large Dimensional Random Matrices, volume 20 of Springer Series in Statistics. Springer- Verlag New York, 2 edition, 2010.
[7] Lucas Benigni and Sandrine Péché. Eigenvalue distribution of nonlinear models of random matrices. arXiv, 2019.
[8] Alberto Bietti and Julien Mairal. On the Inductive Bias of Neural Tangent Kerelss. In Advances in Neural Information Processing Systems, volume 32 of NIPS' 19, pages 12893-12904 Curran Associates, Inc.. 2019.
[9] Avrim Blum, John Hopcroft, and Ravindran Kannan, Foundations of Data Science. Cambridge University Press, 2020.
[10] Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On Lazy Training in Differentiable Programming. In Advances in Neural Information Processing Systems, volume 32 of NIPS 19, pages 2937-2947. Curran Associates, Inc., 2019.
[11] Romain Couillet and Florent Benaych-Georges. Kernll spectral clustering of large dimensional data. Electronic Journal of Statistics, 10(1):13331144, 2016.
[12] Romain Couillet and Zhenyu Liao. Random Matrix Methods for Machine Learning. Cambridge University Press.
[13] Romain Couillet, Zhenyu Liao, and Xiaoyi Mai. Classification Asymptotics in the Random Matrix Regime. In 2018 26th European Signal Processing Conference (EUSIPCO), volume 00 of EUSIPCO 18, pages 1875-1879, 2018.
[14] By Lei Deng, Guoqi Li, Song Han, Luping Shi, and Yuan Xie. Model Compression and Hardware Acceleration for Neural Networks: A Comprehensive Survey. Proceedings of the IEEE, 10844)445-532, 2020.
[15] Michal Derezinski, Feynman T Liang, and Michael Mahoney, Exact expressions for double descent and implicit regularization via surrogate random design. In Advances in Neural Information Processing Systems, volume 33, pages 5152 5164. Curran Associates, Inc., 2020.
[16] Simon S Du, Kangeheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels. 32.
[17] Zhou Fan and Andrea Montanari. The spectral norm of random inner-product kemeel matrices. Probubility Theory and Related Fields, 1731--2)27-85, 2019.
[18] Zhou Fan and Zhichao Wang. Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networks. Advances in Neural Information Processing Systems, volume 33, pages 7710-7721. Curran Associates, Inc., 2020.
[19] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Pruning neural networks at initialization: Why are we missing the mark? In International Conference on Learning Representations. 2021.

---

[20] Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint 2019.
[21] J. Han and C. Moraga. The influence of the sigmoid function parameters the speed of backpropagation learning. 1995.
[22] Song Han, Huizi Mao, and William Dally. Deep Compression: Compressing Deep Neural Networks with Pruning. Trained Quantization and Huffman Coding. arXiv, 2015.
[23] Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. Journal of Machine Learning Research, 22(241):1-124 2021.
[24] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 2 edition, 2012.
[25] Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications. arXiv,, 2017.
[26] Jiaoyang Huang and Homg-Tzee Yau. Dynamics of Deep Neural Networks and Neural Tangent Hicrarchy. 119:4542 4551, 2020-13.
[27] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. Binarized Neural Networks. In Advances in Neural Information Processing Systems, volume 29 of NIPS 16, pages 4107- 4115. Curran Associates, Inc., 2016.
[28] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kemel: Convergence and Generaliza- tion in Neural Networks. In Advances in Neural Information Processing Systems, volume 31 of NIPS'18, pages 8571 15800. Curran Associates, Inc., 2018.
[29] Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clement Hongler, and Franck Gabriel. Implicit regu- larization of random feature models. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4631-4640. PMLR, 13-18 Jul 2020.
[30] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[31] Yann LeCun, Lcon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-basce learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2278-2324, 1998.
[32] Yann LeCun, John Denker, and Sara Solla. Optimal Brain Damage. In Advances in Neural Information Processing Systems, volume 2 of NIPS 90, pages 598-605. Morgan- Kaufmann, 1990.
[33] Michel Ledoux. The Concentration of Measure Phenomenon. Mathematical Surveys and Monographs. 2005,
[34] Jachoon Lee, Jascha Sohl-dickstein, Jeffrey Pennington, Roman Novak, Sam Schoenholz, and Yasaman Bahri. Deep Neural Networks Gaussian Processes. In International Conference on Learning Represen- tations, 2018
[35] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr SNIP: Single-shot network pruning based on connection sensitivity. In International Conference on Learning Representations, 2018
[36] Zhenyu Liao and Romain Couillet. On Spectrum Random Features Maps High Dimensional Data. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3063-3071, Stockholmsmässan, Stockholm Sweden, 2018. PMLR.
[37] Zhenyu Liao and Romain Couillet. The Dynamics of Learning: A Random Matrix Approach. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3072 3081, Stockholmsmässan. Stockholm Sweden, 2018. PMLR.
[38] Chaoyue Liu, Libin Zhu, and Misha Belkin. On the lincarity of large non-linear models: when and why the tangent kernel is constant. 33:15954-1596.
[39] Fanghui Liu, Zhenyu Liao, and Johan Suykens. Kernel regression in high dimensions: Refined analysis beyond double descent. In Proceedings of The 24th International Conference on Artificial Intelligence and Statisties, volume 130 of Proceedings of Machine Learning Research, pages 649-657, 657, PMLR, 13-15 Apr 2021.
12

---

[40] Tianlin Liu and Friedemann Zenke. Finding trainable sparse networks through neural tangent transfer. In Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings Machine Learning Research, pages 6336-6347. PMLR, 13-18 Jul 2020.
[41] Cosme Louart and Romain Couillet. Concentration of Mcasure and Large Random Matrices with an application Sample Covariance Matrices. arXiv, 2018.
[42] Andrew L.. Maas, Awni Y. Hamnun, and Andrew Ng. Rectifier Nonlinearities Improve Neural Network Acoustic Models. In ICML Workshop on Deep Learning for Audio, Speech and Language Processing, ICML Workshop, page 3, 2013.
[43] Vladimir A Marcenko and Leonid Andreevich Pastur. Distribution of eigenvalues for some sets of random matrices. Mathematics of the SOSR-Shornik, 144)457, 1967.
[44] Charles H. Martin and Michael W. Mahoney. Traditional and Heavy Tailed Self Regularization in Neural Network Models. Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4284-4293 PMLR, 2019.
[45] Charles H. Martin and Michael W. Mahoney. Heavy-Tailed Universality Predicts Trends in Test Accuracies for Very Large Pre-Traine Trained Deep Neural Networks. In Proceedings of the 2020 SIAM International Conference on Data Mining (SDM). SDM200 20, pages 505- 513. SIAM, 2020.
[46] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptoties and double descent curve. arXiv, 2019.
[47] Leonid Pastur. On Random Matrices Arising in Deep Neural Networks. Gaussian Case, arXiv, 2020.
[48] Jeffrey Pennington and Pratik Worah. Nonlinear random matrix theory for deep learning. In Advances in Neural Information Processing Systems, volume 30 of 17, pages 2637-2646. Curran Associates, Inc., 2017.
[49] Jürgen Schmidhuber. Deep learning in neural networks: An overview. Neural Networks, 61:85-111 117, 2015.
[50] Mohamed El Amine Seddik, Cosme Louart, Mohamed Tamaazousti, and Romain Couillet. Random Matrix Theory Proves that Deep Learning Representations of GAN-data Behave as Gaussian Mixtures. In Proceedings of the 37th International Conference on Machine Learning, Proceedings of Machine Learning Research, pages 8573 8582. PMLR, 2020.
[51] Mohamed EI Amine Seddik, Mohamed Tamaazousti, and Romain Couillet. Kernel Random Matrices of Large Concentrated Data: the Example of GAN- MAN-Generated Images. In 2019 IEFE International Conference on Acoustics, Speech and Signal Processing (ICASSP 20/9), 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 2019), pages 7480-7484. IEEE, 2019.
[S2] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recogni- tion. In International Conference on Learning Representations, ICLR' 14, 2014.
[53] Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao, Liwei Wang, and Jason D Lec. Sanity- Checking Pruning Methods: Random Tickets can Win the Jackpot. In Advances Neural Information Processing Systems, volume 33, pages 20390-20401. Curran Associates, Inc.
[54] Hidenori Tanaka, Daniel Kunin, Daniel I. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In Advances in Neural Information Processing Systems, volume 33, pages 6377-6389. Curran Associates, Inc., 2020.
[55] Terence Tao and Van Vu. Random matrices: the circular law. Communications in Contemporary Mathematics, 10(02):261-377, 2008.
[56] Roman Vershynin. higge-Dimessooall Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018
[57] Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2020.
[58] Eugene P. Wigner. Characteristic Vectors of Bordered Matrices with Infinite Dimensions. The Annals of Mathematics, 62(3):548, 1955.
13

---

[59] Lechao Xiao. Yasaman Bahri, Jaseha Sohl-Dicksteins Samuel Schoenholz. and Jeffrey Pennington. Dy- namical Isometry and Mean Field Theory of CNNs: How Train 10,000-Layer Vanilla Convolutional Neural Networks. Proceedings of the 35th International Conference on Machine Learning, volume 80
of Proceedings of Machine Learning Research, pages 5393-44944 5402, Stockholmsmässan, Stockholm Sweden, 2018. PMLR.
[60] Hongru Yang and Zhangyang Wang. On the Neural Tangent Kernel Analysis of Randomly Pruned Wide Neural Networks, arXiv, 2022.
[61] Y. Yu, Wang. and R. J. Samworth. A useful variant the Davis Kahan theorem for statisticians. Biometrika, 102(2):315-32) 2015.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof's of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [Yes]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [No]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "zkrDwDS-cBd", "reviewer": "Reviewer_7Ta5", "summary": "This paper characterizes the asymptotic spectral equivalence between NTKs of dense and quantized networks. It shows that under certain assumptions of data (high-dim, Gaussian mixture data) and network architectures (wide MLPs), quantized networks have the same NTK eigenspectra of unquantized ones. This finding allows the authors to perform model quantization with little performance degradation.", "questions": "* Quantized neural networks in the current theoretical and empirical results focus on ternary-valued weights, i.e., NNs with weights that take values in {-1, 0, 1}. Would it be possible to extend the results to binary networks, that is, {-1, 1}-valued networks? It seems that such binary-valued weights (up to a proper scaling) can still satisfy assumptions for Theorem 1 and 2. \n* In Figure 3 in Section 4, the proposed lossless compression approach is numerically compared with two heuristic sparsification and quantization approaches.  The heuristic sparsification approaches uniformly zero out 80% of the weights. This approach is very brutal. Would it be possible to add a more realistic baseline of magnitude-based pruning -- remove a fraction of weights that have the lowest magnitude (absolute value) and keep other weights. This baseline is used more often as a baseline for model pruning and is sometimes surprisingly strong (see, e.g., https://arxiv.org/pdf/1902.09574.pdf)\n* If I understand correctly, the current lossless compression approach uses layerwise pruning and quantization. That is, all layers share the same sparsity level in Algorithm 1. Would it be possible to use the same theoretical insights to perform global compression; that is, compress weights in MLP layers collectively without regard for the specific layer. This may lead to better compression results since it gives more freedom to the weight selection. ", "limitations": "One limitation of the paper, as mentioned in my questions above, is its lack of natural baselines for model pruning in the experiment sections. I encourage the authors to consider incorporating them.  ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well written -- the authors crafted their paper with immense care and taste for mathematical detail. The main results of the paper (Theorem 1 and Theorem 2) are novel and subsume previous studies [2, 32] as special cases. Overall, I think this is a high-quality paper. \n\nOne weakness of this paper is in its numerical evaluation. As I detailed below, the baselines used for the model pruning (randomly removing weights) seem to be too brutal and too weak. It is beneficial to incorporate more realistic baselines such as magnitude-based pruning.\n\n\n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "STPC6544o5W", "reviewer": "Reviewer_ZUPo", "summary": "The authors showed asymptotic eigen-spectral equivalence conditions for fully-connected NTK given GMM data and certain assumptions, based thereon they proposed a net compression scheme with sparse and low-precision random weights, and demonstrated with examples.  \n", "questions": "- The authors ran experiments on real not-so-wide DNNs that also break the assumptions, e.g. taking real image data that is not GMM and taking convolutional nets that are not fully-connected.  And they reported, in their own words \"unexpected close match\" to the theory.  This, in its own right, is an important observation that future theoretical relaxations might address.  But the gap is rather inadequately characterized by experiment here: e.g. any empirical characterization of the notion of \"unexpectedness\"?  \n- Another thing I do not appreciate is the trickiness of the scalar calibration due to nonlinearities.  This seems to stem from the requirement of unity Gaussianity.  Is there any empirical data supporting the near-Gaussianity under real data?  Does there exist any badly behaved nonlinearities that significantly deviated from theory?  Does this mean NNs trained with normalization layers are more conducive to such compression, or could the procedure be simpler in those cases?\n- I find the naive sparse/quantized baselines presented in experiments inadequate.  Of course this is a post-training compression technique, but since it is derived from NTK, it is natural and important to ask how it generalizes compared to much stronger, non-post-training baselines, such as, say, a winning lottery ticket--does there exist any other compressed nets that generalizes better regardless of how expensive the compression procedure was?  \n- \"Lossless\" (used not in quotation marks) might be a false advertisement.\n- Figure 2, missing axes labels.\n", "limitations": "See above.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[+] Results linking NTK and random matrix theory with DNN compression is of timely interest to the field.\n\n[+] Though I cannot say I followed all proofs, the main ideas and motivations are well presented.\n\n[-] A lack of comprehensive experimental comparison with baseline approaches is limiting the practical significance of the findings.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "F62y0GUFAy", "reviewer": "Reviewer_VcQf", "summary": "This paper studies the problem of neural network compression using analysis in the high-dimensional NTK regime. Their main results show that under this regime, the spectral properties of both NTK and CK matrices are independent of the distribution of the weights up to normalization and centering. Instead they depend on a number of parameters that define the activation functions at each layer. This finding informs a new compression technique where a new (compressed) network can match the activation parameters at each layer to enjoy the same spectral properties as the original net. This NTK-LC technique is evaluated on synthetic data by qualitatively comparing the distribution of eigenvalues and on real data by comparing test accuracy with naive baselines.", "questions": "Question: What is the novelty of the NTK-LC approach and how does it compare with state of the art methods?\n\nSuggestion: As mentioned in Weakness 1, the paper would benefit from a discussion on how the convergence and generalization properties of ultra-wide DNNs can depend only on the eigenspectra.\n\nSuggestion: As mentioned in Weakness 3, the paper would benefit from a quantitative metric of eigenvalue closeness.", "limitations": "The authors have addressed the limitations of using NTK theory to explain the behavior of modern neural networks.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper has a clear motivation in the field of neural network compression, a relevant problem that is lacking theory. It is clearly written with thorough theoretical results and experiments on both synthetic and real-world data.\n\nWeaknesses:\n1. The claim in line 49 seems to be a central theme of the paper but has no follow-up discussion on its meaning and implications.\n2. Theoretical claims are presented in the asymptotic regime of infinite n and p (Assumption 1).\n3. A particular GMM distribution is chosen for the input data of the studied model without justification for why it is the relevant distribution to be analyzing.\n4. The results in Figure 2 rely on a qualitative measure of \"closeness\" to evaluate the method instead of a metric that can be quantified and compared. Many of the markings in the top histograms are barely noticeable and require magnification to be seen.\n5. The results in Figure 3 are compared with \"naive\" baselines instead of competitive state of the art methods.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept