Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks
Authors: Melih Barsbey
Milad Sefidgaran
Murat A Erdogdu
Gaël Richard
Umut Simsekli
Venue: NeurIPS 2021 Poster (2021)
Keywords: heavy tails
stochastic gradient descent
deep learning
compression

Abstract: Neural network compression techniques have become increasingly popular as they can drastically reduce the storage and computation requirements for very large networks. Recent empirical studies have illustrated that even simple pruning strategies can be surprisingly effective, and several theoretical studies have shown that compressible networks (in specific senses) should achieve a low generalization error. Yet, a theoretical characterization of the underlying causes that make the networks amenable to such simple compression schemes is still missing. In this study, focusing our attention on stochastic gradient descent (SGD), our main contribution is to link compressibility to two recently established properties of SGD: (i) as the network size goes to infinity, the system can converge to a mean-field limit, where the network weights behave independently [DBDFŞ20], (ii) for a large step-size/batch-size ratio, the SGD iterates can converge to a heavy-tailed stationary distribution  [HM20, GŞZ21]. Assuming that both of these phenomena occur simultaneously, we prove that the networks are guaranteed to be '$\ell_p$-compressible', and the compression errors of different pruning techniques (magnitude, singular value, or node pruning) become arbitrarily small as the network size increases. We further prove generalization bounds adapted to our theoretical framework, which are consistent with the observation that the generalization error will be lower for more compressible networks. Our theory and numerical study on various neural networks show that large step-size/batch-size ratios introduce heavy tails, which, in combination with overparametrization, result in compressibility.

Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks
Melih Barsbey"
Milad Sefidgaran"
Boğaziçi University
LTCI, Télécom Paris, Institut Polytechnique de Paris milad. sefidgarantteeeccom www.lleeeoonaiii...... paris.fr
melih. barsbey@boun. edu.tz
Murat A. Erdogdu
Gaöl Richard
University of Toronto & Vector Institute erdogdušcs. toronto. edu
LTCI, Télécom Paris, Institut Polytechnique de Paris
gael. wwwpaaaddtteeeccopprr......m
Umut Şimşekli
INRIA & ENS PSL Research University umut. s
Abstract
Neural network compression techniques have become increasingly popular they can drastically reduce the storage and computation requirements for very large networks. Recent empirical studies have illustrated that even simple pruning strategies can be surprisingly effective, and several theoretical studies have shown that compressible networks (in specific senses) should achieve a low generalization error. Yet, theoretical characterization of the underlying causes that make the networks amenable such simple compression schemes still missing. In this study, focusing our attention stochastic gradient descent (SGD), our main contribution is to link compressibility to two recently established properties of SGD); (i) as the network size goes to infinity, the system can converge to a mean-field limit, where the network weights behave independently [DBDF$20], (ii) for large step- size/batch-size ratio, the SGD iterates can converge to heavy-tailed stationary distribution [HM20, G$Z21J. Assuming that both of these phenomena occur simultaneously, prove that the networks guaranteed to be "op-oempesssible" and the compression errors of different pruning techniques (magnitude, singular value, node pruning) become arbitrarily small the network size increases. We further prove generalization bounds adapted to our theoretical framework. which are consistent with the observation that the generalization error will be lower for more compressible networks. Our theory and numerical study on various neural networks show that large step-size/batch-sizz ratios introduce heavy tails, which, in combination with overparametrization, result in compressibility.
1 Introduction
With the increasing model sizes in deep learning and with its increasing use in low-resource environ- ments, network compression is becoming ever more important. Among many network compression techniques, network pruning has been arguably the most commonly used method (O'N20J, and rising in popularity and success [BOFG20]. Though various pruning methods successfully used in practice and their theoretical implications in terms of generalization are increasingly apparent [AGNZI8], a thorough understanding of why and when neural networks compressible is lacking.
"Equal contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

A common conclusion in pruning research is that overparametrized networks can be greatly com- pressed by pruning with little to no cost at generalization, including with simple schemes such as magnitude pruning [BOFG20, O' O'N20J. For example, research on ilerative magnitude pruning [FC19] demonstrated the possibility of compressing trained deep learning models by iteratively eliciting a much sparser substructure. While it is known that the choice of training hyperparameters such as learning rate affects the performance of such pruning strategies [FDRC20, HJRY20, RFC20J, usually such observations are low in granularity and almost never theoretically motivated. Overall, the field lacks a framework to understand why or when a pruning method should be useful (2'....
Another strand of research that highlights the importance of understanding network compressibility includes various studies [AGNZI8. SAM+20. SAN20. HJTW21, KLG+ that presented general- ization bounds and/or empirical evidence that imply that the more compressible network is, the more likely is to generalize well. The aforementioned bounds are particularly interesting since classical generalization bounds increase with the dimension and hence become irrelevant in high dimensional deep learning settings, and fall short of explaining the generalization behavior of overparametrized neural networks. These results again illustrate the importance of understanding the conditions that give rise to compressibility given their implications regarding generalization.
In this paper, we develop a theoretical framework to address (i) why and when modern neural networks can be amenable to very simple pruning strategies and (ii) how this relates to generalization. Our theoretical results are based on two recent disparate discoveries regarding deep neural networks trained with the stochastic gradient descent (SGD) algorithm. The first one is the emergence of heavy- tailed stationary distributions, which appear when the networks are trained with large learning rates and/or small biteh-sizes [HM20, G$Z21J. The second one is the propagation of chaos phenomenon, which indicates that, as the network size goes to infinity, the network weights behave independently [MMN18, SS20, DBD]
We show that, assuming both of the aforementioned phenomena occur simultaneously, fully connected neural networks will be provably compressible in a precise sense, and the compression errors of (i) unstructured global or layer-wise magnitude pruning, (ii) pruning based on singular values of the weight matrices, (ii)) and node pruning can be made arbitrarily small for any compression ratio as the dimension increases. Our formulation of network compressibility in terms of "Lp- co-ppresssiiilityy enables us to access results from compressed sensing literature [GCD12, AUM11] to be used in neural network analysis. Moreover, we prove generalization bounds adapted to our framework that agree with existing compression-batt based generalization bounds [AGNZI8, SAM+20, SAN20] and confirm that compressibility implies better generalization. We conduct experiments on fully connected and convolutional networks and show that the results are in strong accordance with our theory.
Our study reveals an interesting phenomenon: depending on the algorithm hyperparameters, such as learning rate and batch-size the resulting neural networks might possess different compressibility properties. Under the decoupling effect of propagation of chaos that emerges with overparametriza- tion [DBDF$20], the networks become compressible in way that they are amenable to simple pruning strategies as the tails get heavier, which is shown to depend on the hiep-sizebbatch-sizz ratio [G$Z21]. Finally, when compressible, the networks become likely to generalize better. this sense, our results also provide an alternative perspective to the recent theoretical studies that suggest that heavy tails can be beneficial in terms of generalization I$SDE20, ZFM+20] 20].
2 Preliminaries and Technical Background
Notation. Matrices and vectors are denoted by upper- and lower-case bold letters, respectively, e.g. X and x. A sequence of sealars 21,...; Fr, is shown as (a,)/_. Similar notations used for sequences of matrices (x,) and vectors {x4 )= whose entries are indexed with convention X, x and x,= 24,2, II,,) respectively. The set of integers {m, m,, n) is denoted by []] We denote the f (semi-)norm of vector x E IR. as || |., 1/) for all E (0, x and ||x|| implies |x||2_ For a matrix A E g2xm, ||A]] denotes its Frobenius norm.
Fully connected neural networks. In the entirety of the paper, consider a multi-class classifi- cation setting. We denote the space of data points by Z = X'' x V, where X' C Rdx is the space of features and ) {1, 2, ........ dy) } is the space of the labels. Similar to prior art (e.g., [NBS18]), we focus our attention on the bounded feature domain X' X33 {x dx ||x| B}.
2

---

We denote fully connected neural network with L layers by a collection of weight matrices (Wi)-= such that W, E R 1, where h denotes the number of hidden units at layer I with ho = dx and hy = dy. Accordingly, the prediction function fw(x) XB + RR with elements (x) = [1], fw corresponding to the neural network is defined as follows: (x( =
(I)
where : IR + is the rectified linear unit (ReLU) activation function, i.e. Φ(z) = max(0. z). and it is applied element-wise when its input is a vector. For notational convenience, let us define di == hy x 11 and d = Σí dr. Furthermore, let wt denote the vectorized weight matrix of layer I, i.., wi vee( Wi) 12, where vec denotes vectorization. Finally, let w be the concatenation of all the vectorized weight matrices, i.e., w == [W1...., WL] IRd. We assume that L 2 2.
Risk minimization and SGD. In order to assess the quality of neural network represented by its weights w. we consider a loss function é: y x y + IR.,, such that fly, Jw (x)) measures the loss incurred by predicting the label of x as arg max, fw [x)] when the true label is y. By following standard statistical learning theoretical setup, we consider an unknown data distribution pzz over 2,
and training dataset with n elements, i.e., S = {Zi,... Zn where each z; =: (xi, 3/6 Lid. uzz. We then denote the population and empirical risks as R(w) == (xxx))= [C Jw (x)) and R(w) =
n >.=
E(y.. fw,)))
Since jız is unknown, we cannot directly attempt to minimize R in practice. One popular approach to address this problem is the empirical risk minimization strategy, where the goal is to solve the following optimization problem: min R(w). To tackle this problem, SGD has been one of the most popular optimization algorithms, which is based on the following simple recursion:
w (++1) = (*) - R (w (*)), where VR&(W) = (1/b) Σ iEs, (W
(2)
Here, w (k) denotes the weight vector at iteration E N 1) > is the step-size (or learning rate). (.) is the stochastic gradient, and 24 is the mini-batch with size b, drawn with or without replacement from [L.
Heavy-tailed distributions and the o-stable family. In this study, we will mainly deal with heavy-tailed random variables. While there exist different definitions of heavy tails in the literature, here, we call random variable heavy-tailed if its distribution function has a power-law decay, iee. P(X 2 z) ~ cz as + oo, for some e >> O and a E (0, 2). Here, the tail index a determines the tail thickness of the distribution, i.e., as a get smaller, the distribution becomes heavier-tailed.
An important subclass of heavy-tailed distributions is the family of stable distributions. A random variable X has symmetric a-stable distribution, denoted by SaS(a). if its characteristic function is equal to E[|exp(ixx)]] = exp(-low) ("), where E (0, 2] is again the tail index and a E (0, oo) is the scale parameter. An important property of Sa.S is that whenever a < 2, E X|" is finite if and only if < a. This implies that the distribution has infinite variance as soon as < 2. In addition to their wide use in applied fields [No]20], recently, SaS distributions have also been considered in deep learning theory [SSG19, PFF20, ZFM* 20, $SDE20] and optimization [WGZ*21] 211.
3 Compressibility and the Heavy-Tailed Mean-Field Regime
In this section, we will present our first set of theoretical results. We first identify sufficient condition, then we prove that, under this condition, the compression errors of different pruning techniques become arbitrarily small as the network size increases.
3.1 The heavy-tailed mean-field regime
Due to the peculiar generalization behavior of neural networks trained with SGD, recent years have witnessed an extensive investigation of the theoretical properties of SGD in deep learning [Lon17, DR17, KL.18, ZZL19, AZLLI9, $SDE20, Neu21, CDE*21 21, BLGŞ21J. We will now men- tion two recently established theoretical properties of SGD, and our main contribution is studying the compressibility properties of the network under the assumption that these two seemingly unrelated 'phenomena" occur simultaneously.
The heavy tail phenomenon. Several recent studies [MM19, SSG19, SGN+19, $ZTG20, 7FM+ ZKV+20 20, cWZ+21] have empirically illustrated that neural networks can exhibit heavy-tailed
3

---

behavior when optimized with SGD. Theoretically investigating the origins of this heavy-tailed behavior, [HM20] and [G$Z21] later proved several theoretical results on online SGD, with rather surprising implications: due to the 'multiplicative" structure of the gradient noise (i.e., VR& (w) VR(w)). as k + oc, the distribution of the SGD iterates w(f) can converge to heavy-tailed distribution with infinite second-order moment, and perhaps more surprisingly. this behavior can even emerge in simple linear regression with Gaussian data. The authors of [G$Z2I] further showed that, in the linear regression setting, the tail index a monotonic with respect to the step-size n and batch-size b: larger 1j and/or smaller b result in smaller (ie., heavier tails).
Propagation of chaos and mean-field limits. Another interesting property of SGD appears when the size of the network goes to infinity. Recently, it has been shown that, under an appropriate scaling of step-sizes, the empirical distribution of the network weights converges to fixed mean- field distribution, and the SGD dynamics can be represented as a gradient flow in the space of probability measures [MMN18. CB18, SS20, DBDF$20]. Moreover, [DBDF$20] showed that a propagation of chaos phenomenon occurs in this setting, which indicates that when the network weights are initialized independently (i.e., a-priori chaotic behavior), the weights stay independent as the algorithm evolves over time (i.e., the chaos propagates) [Szn91].
Our focus in this paper is the setting where both of these phenomena occur simultaneously:
assume that as the size of the network goes to infinity, the SGD iterates become independent and their distribution converges to heavy-tailed distribution. To formalize this setting, let us introduce the required notations. For an integer my < di, let Wi.(1=m;) denote the first my coordinates of w,, and for my 2 di set (1.(1:mg) = Wi- Furthermore, parametrize the dimension of each layer dj with parameter / E R. i.e., di = di(p), such that for all 1 1, .....: I, we have:
(p) E N+, and limp- (p) = 00.
(3)
This construction enables to take the dimensions of each layer to infinity simultaneously INP21]. Condition 1 (Heavy-tailed mean-field limit condition). The SGD recursion (2) satisfies the heavy- tailed mean-field limit (HML) condition, if the dimensions obey (3) and if there exist heavy- probability measures {uî LL on IR with tail indices {ai)e-r such that pi (103) = 0 for all I and
for any -.,,..,,,,, E N4,, the joint distribution of
W (R)
(1) "((1mm)) L.(imm))) weakty converges to (pt) 2 ... & (pT,) )mm,
(4)
as p,k + 00, where p denotes the product measure and n denotes the n-fold product measure.
Informally, the HML condition states that in the infinite size and infinite iteration limit, the entries of the weight matrices will become independent, and the distribution of the elements within the same layer will be identical and heavy-tailed. We acknowledge that the above condition may not be always satisfied, and theoretical evidence for this condition is provided in rather seemingly simpler settings such as linear regression [G$Z21] and/or two-layer neural networks [DBDF$20). However, we will empirically illustrate the behavior described by the HML condition in Section 5 in certain scenarios. Note that, in (4), the particular form of independence in the limit not crucial and we will discuss weaker alternatives in Section 3.3.
We further note that [2BDF$20] proved that similar form of (4) indeed holds for SGD applied on single hidden-layered neural networks, where the limiting distributions possess second-order moments (i.e., not heavy-tailed) and the independence is column-wise. Recently, (PFF20) investigated the infinite width limits of fully connected networks initialized from a SoS distribution and proved heavy-tailed limiting distributions. On the other hand, heavy-tailed propagation of chaos results have been proven in thcoretical probability [JMW88, LMW20]; however, their connection to SGD has not been yet established. We believe that (4) can be shown to hold under appropriate conditions, which we leave as future work.
3.2 Analysis of compression algorithms
In this section, we will analyze the compression errors of three different compression schemes under the HMI condition. All three methods are based on pruning, which we formally define as follows. Let x be a vector of length d, and consider its sorted version in descending order with respect to the magnitude of its entries, i.e., [z;,]] Z |xtg]] 2 ... 2 |Ztale where (i,,... id) = (l,...,dd d}. For any
). is defined follows: k S d, the best term approximation of x, denoted as (*) (x1 ..... z.
(k) (k))

---

for 1 E [1, [,,1, of x with the largest magnitudes, and 'prune' the remaining ones. Current results pertain to one-shot pruning with no fine-tuning; other settings are left for future work (ef. [EKT20]).
(k)
by and for 1 $ [1, [K]]
(k) = 0. Informally, we keep the k-largest entries
In this section, we consider that we have access to sample from the stationary distribution of the SGD, Le. w and for conciseness we will simply denote by w. We then consider a compressed network W (that can be obtained by different compression schemes) and measure the performance of the compression scheme by its 'relative Ey-compression error' (cf. [AUMII, GCD12)). defined as: | - w w/lp- Importantly for the following results, in the supplement, we further prove that a small compression error also implies small perturbation on the network output.
Magnitude pruning. Magnitude pruning has been one of the most common and efficient algorithms among all the network pruning strategies [HPTD15, BOFG20, KLG++11). In this section, we consider the global and layer-wise magnitude pruning strategies under the HML condition.
More precisely, given network weight vector E R and remaining parameter ratio K E (0, 1), the global pruning strategy compresses w by using w(xd), i.e., it prunes the smallest (in magnitude) (1 - x)dd entries of w. Also, note that 1/1s corresponds the frequently used metric compression rate [BOFG20]. On the other hand, the layer-wise pruning strategy applies the same approach to each layer separately, i.e., given layer-wise remaining parameter ratios K₁ E (0, 1), we compress each layer weight w E Rd by using (xadd)) The following result shows that the compression error of magnitude pruning can be made arbitrarily small as the network size grows.
Theorem 1. Assume that the recursion (2) satisfies the HML condition.
(i) Global magnitude pruning: if the weights of all layers have identical asymptotic distributions
pf μe with tail index af a. for all L E []. then for every e >> 0, E > 0, K E (0, 1), and
p 2 a, there exists do E N, such that [/w(d)) w|lp p S e|[w]lp holds with probability at least
1 1- for d 2 do-
(ii) Layer-wise magnitude praning: for every c > E1 0 and kι (0, 1), where I E [1,,
and p 2 max; on, there exists di, E N, such that [| [w(rrd)) willp S E [Wellp holds with probability at least - c, for di 2 di,0-
(mid))
This result shows that any pruning ratio of the weights is achievable as long as the network size is sufficiently large and the network weights are close enough an i.i.d. heavy-tailed distribution. Empirical studies report that global magnitude pruning often works better than layer-wise magnitude pruning [BOFG20], except when it leads to over-aggressive pruning of particular layers [WZG20).
The success of this strategy under the HML condition is due to a result from compressed sensing theory, concurrently proven in [GCDI2, AUM11], which informally states that for a large vector of i..dd heavy-tailed random variables, the norm of the vector is mainly determined by a small fraction of its entries. We also illustrate this visually in the supplementary document.
An important question here that, to achieve fixed relative error Ej, how would the smallest Kı differ with varying tail-indices ag, i.e., whether "heavier tails imply more compression", In our experiments, we illustrate this behavior positively: heavier-tailed weights are indeed more compressible. We partly justify this behavior for certain range of p in the supplement; however, a more comprehensive theory needed, which we leave as future work.
Singular value pruning. In recent studies, it has been illustrated that the magnitudes of the eigen- values of the sample covariance matrices (for different layers) can decay quickly, hence pruning the singular values of the weight matrices, i.e., only keeping the largest singular values and corresponding singular vectors, is a sensible pruning method. Exploiting the low-rank nature of fully connected and convolutional layer weights in network compression has been investigated theoretically and empirically [AGNZ18. YLWT17J. Here we will present a simple scheme to demonstrate our results.
More precisely, for the weight matrix at layer 1, Wt, consider its singular value decomposition, W, UEVT, and then, with a slight abuse of notation, define wi where y (Mohe-1) the diagonal matrix whose diagonal entries contain the [Kyht-] largest singular values (ic., prune the diagonal of E). Accordingly, denote w [r] vee( nee(W//hh-l))
(s V
W
5

---

The next theorem shows that under the HML condition with an additional requirement that the limiting distributions are Sas, the eigenvalues of the (properly normalized) sample covariance matrices will be indeed compressible and the pruning strategy achieves negligible errors as the network size grows.
Theorem 2. Assume that the recursion (2) satisfies the HML condition, L 2 3, and for all [2, L - 1I. 1 = SauS(or) with some di O. Then, for every > E1 > and ka E (0, 1), there exists (1r,0, such that the following inequalities hold for every by 2 h4, and p 2 max 0n/2:
| Aello S =f and [[w]
will S E will
(5)
with probability at least 1- - e, where A E Rh denotes the vector of eigenvalues corresponding to the sample covariance matrix hi 2 T, W..
We shall note that the proof of Theorem 2 in fact only requires the limiting distributions to be 'regularly varying' [TTR*20) and symmetric around zero, which covers broad range of heavy-tailed distributions beyond the a-stable family [BDM* 16]. The sole reason why we require the SaS condition here is to avoid introducing further technical notation.
In Theorem 2, P needs to be greater than equal a:2, in contrast to the condition p 2 in Theorem 1. The reason is that Theorem 2 is based on pruning the eigenvalues of the normalized covariance matrix and moreover in general if a matrix A I has elements [A] that are independent and identically distributed from the symmetric a-stable distribution, then by [TTR+ Theorem 2.7], as m - 2o, the eigenvalues of m 2/a A A variables, that are identically distributed from positive stable distribution with tail index a/2.
A weakly converge to independent random
Node pruning. The last pruning strategy that we consider a structured pruning strategy, that corresponds to the removal of the whole columns of a fully connected layer weight matrix. Even though below we consider pruning based on the norms of the weight layer columns, the same arguments apply for pruning rows; see supplement for further discussion.
The idea in column pruming that, for a given layer we first sort the columns of the weight matrix Wi E Ayx with respect to their Ep- fp-norms for a given p 2 max; ag. Then, we remove the entire columns that have the smallest ép -orms.. More precisely, let Wi( E 1d be the i-th column of
Wi, for i E [1, 11 and suppose that (6>) 2 ||1 2 ... 2 [ )lp,s where fir...., 8he-13 } = {1,..... 1. Then, we define the k-best column approximation of W,, denoted
as wi (RhP E 1R/1xx11 as follows: for j E [1, [k]]. (( ((y)))))))))))))))(())) = Wi(t)) and for j & [1, [.]]
(6).p w (K) (())(())) = O. Denote also w w == vec W (K).P)
Theorem 3. Assume that the recursion (2) satisfies the HML condition. Then, for every 6 > > O, Ky E (0, 1), where E [2, L]. and 2 max there exists h1-100 E N, such that [|w] (abhiih - willp S Ex|l willp holds with probability at least 1 - f.r every h4-1 2 h4-1,0-
This theorem indicates that we can remove entire columns in each layer, without considerably affecting the network weights, as long as the network is large enough. In other words, effectively the widths of the layers can be reduced. Structured pruning schemes are commonly used in CNNs where filters, channels, or kernels can be pruned by worm-based or other criteria [LKD + 17, HZS17, HPTD15).
3.3
A note on the limiting independence structure in the HML condition
We conclude this section by discussing the particular independence condition in the limit, which appears in Condition 1. We shall underline that the clement-wise independence is not a necessity and under weaker conditions, we can still obtain Theorems 1-3 with identical or almost identical proofs. For instance, the proof of Theorem 3 remains the same when the columns of W, are i.i.d. vectors with dependent components; hence, the element-wise independence is indeed not needed, but is used for the clarity of presentation. More generally, in all three theorems, the main requirement is to ensure a weak dependence between the components of the weight vector. More precisely, for Theorems 1, 2, 3, we respectively need (1) the entries of W, (2) its singular values, or (3) the f,-norms of its columns to be stationary and ergodic with heavy-tailed distribution. Under this condition, the same proof strategies will still work by invoking [SD15, Theorem 1], instead of [GCD12, Proposition 1].

---

4
Generalization Bounds
So far, we have shown that the heavy-tailed behavior in the weights of a network together with their independence result in compressibility. In this section, we further show that these phenomena bring forth a better generalization performance bound in the network. More precisely, we establish a generalization bound such that if a network more compressible, then the corresponding compressed network has a smaller generalization error bound. Throughout the section, we will focus on layer-wise magnitude pruning; yet, our results can easily extended to the other pruning strategies. Note that similar results have already been proven in [AGNZI8, S0M+200 SAN20, HJTW21]; yet, they cannot be directly used in our specific setting, hence, we prove results that are customized to our setup. More precisely, although these works, similar to our result, are based on the assumption of the "compressibility" of the network and moreover the generalization gap of the population risk with respect to the empirical margin risk is considered in [AGNZI8. HJTW21], they cannot be applied directly to the cocopreessiiillity based strategies discussed the previous section. We should emphasize that our results, well as the previous mentioned works, are merely upper bounds on the generalization performance of the network.
Our generalization bounds are derived by applying the previously developed techniques as in [AGNZ.18, NBS18). In particular, we follow the approach of [AGNZ.88 by further adapting the technique for the magnitude pruning strategy and allowing the compressed network weights to take unbounded continuous values. As in [AGNZ18], we consider the 0-1 loss function with margin y' x x + 1). for the multiclass classifier fw. given follows:
7 0, by:
(w,,5w()) = { 0, otherwise.
1,
if f - max fw (x)] S m,
(6)
Still denoting w w( the population and empirical risks associated with by are denoted as (w) and (w). respectively. By having the dataset S ~ uzz 80m we assume the weights w are sampled according to the stationary distribution Pwis of SGD. Denote the joint distribution of (S, w) by Ps.. = pg Pwis-
In the following theoretical results, we will assume that we have access to a random compressible neural network that is amenable to the layer-wise magnitude pruning strategy with high probability. This assumption is essentially the outcome of Theorem under the HML condition together with an additional uniformity requirement on di,0 over St.
H 1. For e 2 0, > O, and {ma |=1 Ki E (0, 1), there exists {d : dı,0 E N independent of S. such that for di 2 d1,0. l E [1, LJ. the relation || -wll S e e/ll holds for all E [1, L] simultaneously with probability at least 1 1-6 where wi := := (eidd) and the probability is w.r.t. Ps.w-
In the following result, we relate the population risk of the compressed network to the empirical margin risk of the original (uncompressed) network. For notational convenience, for 8, T > 0, let
R(6) = inf R: P[[[]| 2 R) S 5), and ((T,5) = V2BL (2R(6)/VIL) L-1 /T/ /T,
(7)
where the probability is with respect to the joint distribution Ps.w-
Theorem 4. Assume H/ holds. Then for n: n/ a/log(n)= 2 10L, (di di 2 di and any 8, > 0. with probability at least 1 - -dd/2 5 6-6,
Ro(w)= S (w) + (12C(T,)) + vd) (x)
(8)
where R()) and L(T,,) 5) are defined in === Et [ [1]d]]]2
= (2hv(k) k log()), and 76, : V2B
(RO/VE) (1+))~-1)) 1).
'Note that the uniformity assumption is mild and can be avoided by combining Theorem I with Egoroff's theorem with additional effort, as in [$SDE20].
'The binary entropy (K) (in nats) is defined -n log(k) (1 - x)) log(1 rt) for k E [0, 1J. with the
convention (0) h1) O. Note that 0 & (xx) I log(2).
7

---

FCN4, CIFARIO
FCNS, CIFAR1
CNN. CIFARIO
FCN4, MNIST
FCN MNIST
CNN, MNIST
Noan Untdee
2.0
Mean be Irdie 18)
Moan Indde 10)
one
Oal Iidder 18)
2.8
10
20
nb
22
ob
Figure Mean estimated tail index (á) vs. n for each trained model. a-axes are log-scaled.
This result establishes a generalization bound such that, for a fixed relative compression error s, if network is more compressible, i.e. if is smaller, then its corresponding compressed network has smaller generalization error bound, as the bound is scaled by the factor RVK..
In our proof, we prove an intermediate result, inspired by [NTS15] and stated in the supplement, which bounds the perturbation of the network output after compression. This guarantees that the risks of the original and pruned networks can be made arbitrarily close, as long as the relative compression error small enough.
To have a better understanding of the constants in Theorem 4, in the next result, we consider a special case where the weights follow stable distribution, and make the above bound more explicit.
Corollary 1. Assume that for I E [1, and i E [1, di]. the conditional distribution of wi, fid SajS(or) with aq E (1. Further, assume that the scale parameters satisfy the following property:
L o²= = (d/d)((r1/00))) (44-1// (ddd)//oodd
(9)
oU)TT 1/a1 a= miny ay and oo is a constant, and also {ai and a are independent from S. Then, for every & > 0 and Ki E (0, 1), E I.. there exists di,0 E N. such for di 2 di,0. n: n/ log(n) 2 10L, and every T > O, with probability at least 1 1-3d-ai (2L),
where oan = (2r(
Ro(w) S (w) + (aot/ /T + 1) (n + do)loggn)
(10)
where (wih = (w/ (m(ddd)) 11- = t + bot /J/T, a = 6/2BB2 and be =
V2B(11+ (1++)4-11
To simplify our presentation, we have set the 'scale' of the distribution as a decreasing function of dimension, which intuitively states that the typical magnitude of each entry of the network will get smaller as the network grows. We observe that for a fixed e and d, the bound improves as pruning ratio, k, increases. This result is of interest in particular since it is observed experimentally (and in part, theoretically) that heavier-tailed weights are more compressible, and hence due to this result have better generalization bounds. This provides an alternative perspective to the recent bounds that aim at linking heavy tails to generalization through a geometric approach I$SDE20].
Finally, in the supplement, we further show that the uncompressed network also inherits this good generalization performance bound, which is consistent with the results of [HJTW21, KLG+21J: if a network is more "compressible", not only the generalization performance for the compressed network but also for the original network improves. The generalization bound adapted to bp- compressibility based strategies, discussed in the previous section, is highlighted in Section S2 of the supplement.
5 Experiments
In this section, we present experiments conducted with neural networks to investigate our theory. We use three different model architectures: fully connected network with 4 hidden layers (FCN4), fully connected network with 6 hidden layers (FCN6), and a convolutional neural network with 8 convolutional layers (CNN). Hidden layer widths were 2048 for both FCN models. All networks include ReLU activation functions and none include batch normalization, dropout, residual blocks, or any explicit regularization term in the loss function. Each model is trained on MNIST [LCB10] 10] and CIFAR10 [Kri09] datasets under various hyperparameter settings, using the default splits for training and evaluation. The total number of parameters were approximately 14M for FNN4-MNIST, 19M for FCN4-CIFAR 10, 23MM for FCN6-NNIST, 27M for FCN6-CIFAR 10, and 9M for both CNN models. All models were trained with SGD until convergence with constant learning rates and no momentum. The convergence criteria comprised 100% training accuracy and training negative log- likeliood
8

---

less than 5 X 10-5. The training hyperparameter settings include two batch-sizes (b = 50, 100) and various learning rates (11) to generate a large range of n/ values. See the supplement for more details.
By invoking [G$721, Corollary 11] which shows the ergodic average of heavy-tailed SGD it- erates converges to multivariate stable distribution, after convergence, for 1000 additional iterations to obtain the average of the parameters to be used in this estima- tion. The tail index estimations were made by the estimator proposed in [MM015, Corollary 2.4], which has been used by other recent studies that estimate tail index in neural network parame- ters ISSDE20, GŞZ21, ZFM+20) 20]. The ergodic averaging does not change the tail index of the parameters, and was employed to facilitate tail index estimation by enabling the utilization of the aforementioned estimator. The rest of the experiments have been conducted without ergodic averag- ing, We also observe that the results with/without ergodic averaging are virtually identical in both tail index estimation tasks and pruning experiments. centered before pruning is conducted with the median value to conform with the tail index estimation.
kept running SGD)
pruning methods, the parameters were
Training hyperparameters and layer statis- tics. We first verify that models trained with higher learning rate to batch-size ratio (1/6) lead to heavier-tailed parameters, replicating the re- sults presented in [G$Z21]. For each trained model, we compute the mean of separately es- timated tail indices for all layers, so that each model is represented by single value. This averaging is a heuristic without a clear theoret- ical meaning, and has been also used by recent works in the literature [G$Z21, MM19J. Results
10a
16a
Figure 2: Empirical distribution of CNN layer trained on MNIST. (Left) Overlaid histograms of random par- tition of the weights, showing an identical distribution. (Right) Comparing the network weights to samples sim- ulated i.i.d. from symmetric a-stable distribution with the same tail index a z 1.95. y-axes are log-scaled. presented in Figure demonstrates that higher n leads to heavier tails (lower â).
Also of interest are the distribution of the resulting parameters from training. Figure 2 (left) demon- strates representative example of the parameters from an CNN layer trained on MNIST, where two overlaid histograms representing empirical distributions of random partition of the parameters are almost identical. On the right in the same figure, this distribution is compared to a simulated symmetric a- stable distribution that has the same tail index (>> 1.95). The figure demonstrates that the two distributions have similar qualitative properties.
FCN4, OFAR10
FCN6, OFARIO
CNN, CIFAR10
FCN4, MNIST
FCN6, MNIST
CNN, MNIST
1.93
Est. bal hoor
).72
Layer
0.24
0.31
0.37
0.28 0.31 0.37
0.31
0.37
0.24
0.31
0.37
0.24 Pruning
0.31
0:37
0.24
0.31
0:37
Pruning (20
husing 10t
Pruning
Pruning noce
Pruning ratlo 11
Figure 3: Estimated tail index (6) vs. pruning ratio
kD,, relative compression error 0.1, p-
CIFAR10
FCNG, CIFARIO
CNN. CIFAR10
FCN4,
MNIST
0.75
197
0.50
192
0.00
9.5
0.5
Fruning
Pruning nale -00
rab
Prusiig
Pruning ratle 12-
Figure 4: Relative test accuracy vs. pruning ratio for layer-wise magnitude pruning. Colors denote mean estimated tail index (a).
Tail index and prunability. In this section we examine whether networks with heavier-tailed layers, trained with higher n/b b ratios, are more prunable and whether they generalize better. As a baseline test, we first examine whether neural network layers which are heavier-tailed can be pruned more given a fixed maximum relative compression error. Figure 3 demonstrates for an error of 0. that this is indeed the case. We next test our hypothesis that posit models with heavy-tailed parameters to be more prunable. Both the results pertaining to layer-wise magnitude pruning and singular value pruning, demonstrated in Figures 4 and 5 show that this is indeed the case. Here, relative test accuracy

---

FCN4, CIFAK10
FCNS, CIFARIO
CNN. CIFAR10
FCN4, MINIST
FCN6, MNIST
CNN, MINIST
SAWive ENC SCCONC
S0lEvo Last ACCUNNC
2.03
0.50
192
0.25
0.00
1.07
0.0
2.5
1.0
0.0
0.5
9.5
3.0
0.0
0.5
1.0
0.5
1.0
0.0
0.5
Fruning FACO 11-14
Pruning natoo 11-14
Pruning rabo 12
Prunng rato 11-41
Pruting rabe (2
Praning ratie 12-41
Figure 5: Relative test accuracy vs. pruning ratio for singular value pruning. Colors denote mean
estimated tail index (á).
stands for test accuracy after pruning / unpruned test accuracy. The results show that models with heavier-tailed parameters (shown with darker colors) are starkly more robust against pruning. Similar results with global magnitude pruning can be seen in the supplement.
For structured pruning, we prune 3 x 3 kernel parameters in CNN models. The results (Figure 6) show a similar, hypothesis conforming pattern. Results for FCNs, pre- sented in the supplement, were underwhelming: perhaps unsurprisingly as structured pruning is not as commonly used in FCNs N20]. More successful attempts could be due alternative scoring methods [SAM+20]; our approach might require wider layers to conform with theoretical conditions.
CNN. CIFARIO
CNN, MNIST
1.00
2.00
5.5
155
Rolaate 0.50
192
0.25
189
187
Hoth
0.50
025
3.50
025
fruning F2t5
Pruriig a00
Figure 6: Relative test accuracy vs. prun- ing ratio for structured pruning. Colors denote mean estimated tail index (á).
Tail index and generalization. Following our theoreti-
cal results, examine whether the heavier-tailed networks lead to better generalization performance. Consistent with our hypothesis, Figure shows that models with the highest tail index have con- sistently the worst test performances. The same conclusion applies generalization performance as training accuracy is 100% for all models. See supplementary material for additional experiment results and discussion of the findings.
FCNA, CIFARIO
FCN6, AR10
CNN, GFAR10
FCM, MNIST
FCNO, MNIST
CNN, MNIST
Teat ooursoy th0
25.7
$7.0
95.5
50.4
58.5
95.2
58.0
56.1
52.1
11.6
25.0
10-2
1.50
1.46
1.62
166
3.55
1.40
1.05
1.63
1.67
2.00
Edlimatd ball Index:
Extimated indee (3)
Extimated Lindex
Edimmated Indee 14)
Extimated index (1)
Extimated on Index
Figure 7: Test accuracy vs. mean estimated tail index (d:) for each model. Color: training n//b ratio.
6 Conclusion
We investigated the conditions under and the mechanism through which various pruning strategies can be expected to work, and confirmed the relationship between pruning and generalization from theoretical approach. Future directions for rescarch include formally identifying settings in which HML condition holds, eliciting the relationship between à and k more clearly, and further examination of structured pruning in FCNs. Extending our work to other pruning strategies and network structures is also another important future direction. For example, it has recently been observed that gradients also exhibit heavy-tailed behavior I$GN+19 19, ZKV+ 20, ZFM +20;; we suspect that our theory might be applicable in the case of gradient-based pruning as well. The extension of our analyses other network structures such as recurrent layers or ResNet blocks [H7RS15) would also be valuable.
Acknowledgements
The authors are grateful to A. Taylan Cemgil, Valentin De Bortoli, and Mohsen Rezapour for fruitful discussions on various aspects of the paper. MAE partially funded by CIFAR AI Chairs program, and CIFAR AI Catalyst grant, NSERC Grant [2019-0616]] UŠ's research is supported by the French government under management of Agence Nationale de Recherche as part of the "Investissements d' "vvenii" program, reference ANR- 19-1 19-331A-0001 (PRAIRIE 3IA Institute).
10

---

References
[AGNZI8] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Zhang. Stronger generalization bounds for deep nets via compression approach. In Proceedings of the 35th Interna- tional Conference on Machine Learning, volume 80, pages 254-263, PMLR, 10-15 Jul 2018.
[AUMI]] Arash Amini, Michael Unser, and Farokh Marvasti. Compressibility of deterministic and random infinite sequences. IEEE Transactions on Signal Processing, 59(1 1951193 5201, 2011.
[AZLL19] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in over- parameterized neural networks, going beyond two layers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Gamett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[BDM 16] Dariusz Buraczewski, Ewa Damek, Thomas Mikosch, al. Stochastic models with power-law tails. Springer, 2016.
[Bha97] Rajendra Bhatia. Matrix Analysis, volume 169. Springer, 1997.
[BLGŞ21] Tolga Birdal, Aaron Lou, Leonidas Guibas, and Umut Şimşekli. Intrinsic dimension, persistent homology and generalization in neural networks. In NeurIPS, 2021.
[BLM20] Witold M. Bednorz, Rafat M. Lochowski, and Rafal Martynek. On tails of symmet- ric and totally asymmetric ShalphaS-stable distributions. arXiv:1802.00612 [math]. November 2020.
[BOFG20] Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the State of Neural Network Pruning? arXiv:2003.03033 [cs, stat), March 2020.
[CB18] Lénaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[CDE 21] Alexander Camuto, George Deligiannidis, Murat A Erdogdu, Mert Gürbüzzalaban, Umut Şimşekli, and Lingjiong Zhu. Fractal structure and generalization properties of stochastic optimization algorithms. NeuriPS, 2021.
(1W Alexander Camuto, Xiaoyu Wang, Lingjiong Zhu, Chris Holmes, Mert Gürbüzbalahan, and Umut Şimşekli. Asymmetric heavy tails and implicit bias in gaussian noise injections. ICML, 2021.
[DBDF220] Valentin De Bortoli, Alain Durmus, Xavier Fontaine, and Umut Şimşekli. Quantitative propagation of chaos for sgd in wide neural networks. In H. Larochelle, M. Ran- zato, R. Hadsell, M. F. Balcan, and Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 278-288. Curran Associates, Inc., 2020.
[DR17] Gintare Karolina Dziugaite and Daniel M. Roy. Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data. arXiv: 1008 [cs]. October 2017.
[EKT20] Bryn Elesedy, Varun Kanade, and Yee Whye Teh. Lottery Tickets Linear Models: An Analysis of Iterative Magnitude Pruning. arXiv:2007. 00843 [cs, stat], August 2020.
[FC19] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations. 2019.
[FDRC20] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. In Hal Daumé and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 2269. PMLR, 13-18 Jul 2020.
11

---

[Gal68] Robert G. Gallager. Information Theory and Reliable Communication. John Wiley & Sons, Inc., USA, 1968.
[GCDI2] Rémi Gribonval, Volkan Cevher, and Mike E Davies. Compressible distributions for high-dimensional statistics. IEEE Transactions Information Theory, 58(8):0016- 5034, 2012.
[G$Z21] Mert Gurbuzbalaban, Umut Şimşekli, and Lingjiong Zhu. The Haivy-Tail Phenomenon in SGD. In ICML, 2021.
[HJRY20] Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask. arXiv:1905.0106 [cs, stat], March 2020.
[HJTW21] Daniel Hsu, Ziwei Ji, Matus Telgarsky, and Lan Wang. Generalization bounds via distillation. In International Conference on Learning Representationss 2021.
[HM20] Liam Hodgkinson and Michael W. Mahoney. Multiplicative noise and heavy tails in stochastic optimization. arXiv:2006.0622 202-20030.0223 [cs, math, stat], June 2020.
[HPTD15] Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connec- tions for efficient neural network. In Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[HZRS15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. arXiv:/512.0333 CVJ, 2015.
[HZS17] Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural networks. urXiv:1707.0611 [cs], August 2017. arXiv: 1707.06168.
[JM088] Benjamin Jourdain, Sylvie Méléard, and Wojbor Woyezynski. Nonlinear SDEs driven by Lévy processes and related PDEs. Alea, 4:29, 2008.
[KL18] Ilja Kuzborskij and Christoph H. Lampert. Data-Dependent Stability of Stochastic Gradient Descent. arXiv:1703.0I1 01678 [cs], February 2018.
[KLGG21] Lorenz Kuhn, Clare Lyle, Aidan N. Gomez, Jonas Rothfuss, and Yarin Gal. Robustness to Pruning Predicts Generalization in Deep Neural Networks. arXiv:2 [cs, stat], March 2021.
[Kri09] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
[LCB10] Yann LeCun, Corinna Cortes, and Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http:///aam.eccu.coomeee wwtp://////////istt...mmmmmm 2, 2010.
[LKD 17] Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient ConvNets. arXiv: arXiv:160..00 087/0 [cs], March 2017. arXiv: 1608.08711 10.
[LMW20] Mingjie Liang, Mateusz B. Majka, and Jian Wang. Exponential ergodicity for SDEs and McKean-Vlasse processes with L\' (clvy noise. urXiv:190.11122. [math], November 2020.
[Lon17] Ben London. A pac-bayesian analysis of randomized learning with application to stochastic gradient descent. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[LWZ81] Raoul LePage, Michael Woodroofe, and Joel Zinn. Convergence to a stable distribution via order statistics. The Annals of Probability, 9(4):624 632, 1981.
[MM19] Charles H. Martin and Michael Mahoney. Traditional and Heavy- Tailed Self Regularization in Neural Network Models. arXiv:1901.08276 [cs, stat], January 2019.
12

---

[MMN18] Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115(3)) 2018.
[MMO15] Mohammad Mohammadi, Adel Mohammadpour, and Hiroaki Ogata. On estimating the tail index and the spectral measure of multivariate a-stable distributions. Metrika, 78(5):549-555 -6114999-662200 2015.
[NBS18] Behnam Neyshabur; Srinadh Bhojanapalli, and Nathan Srebro. A PAC- Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks. arXiv:/7077 700.00967 [cs], February 2018.
[Neu21] Gergely Neu, Iiformatiion-Thoreeee Generalization Bounds for Stochastic Gradient Descent. arXiv:2102.0099 [cs, stat), February 2021.
[No120] John P. Nolan. Univariate Stable Distributions: Models for Heavy Tailed Data. Springer, Switzerland, 2020.
[NP21] Phan-Minh Nguyen and Huy Tuan Pham. A Rigorous Framework for the Mean Field Limit of Multilayer Neural Networks, arXiv:2001. [cond-mat, stat], May 2021.
[NTS15] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm- capacity control in neural networks. In Conference on Learning Theory, pages 1376-1401, 2015.
[O'N20] James O' O'Neill. An overview of neural network compression. arXiv:2006.0300 [cs, stat], August 2020.
[PF220] Stefano Peluchetti, Stefano Favaro, and Sandra Fortini. Stable behaviour of infinitely wide deep neural networks. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108, pages 1137-1146, 2020.
[PGM 19] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein. Luca Antiga, Alban Desmai- son, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style. peerforrrrrm deep learning library. In H. Wal- lach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Bi Buch E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019.
[RFC20] Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine- tuning in neural network pruning. arXiv:2003..0 02389 [cs, staf], March 2020.
[Rob55] Herbert Robbins. A remark on stirling's formula. The American Mathematical Monthly, 62(1))26-29, 1955.
(SAM-20) Taiji Suzuki, Hiroshi Abe, Tomoya Murata, Shingo Horiuchi, Kotaro Ito, Tokuma Wachi, So Hirai, Masatoshi Yukishima, and Tomoaki Nishimura. Spectral pruning: Compressing deep neural networks via spectral analysis and its generalization error. In International Joint Conference on Artificial Intelligence, pages 1839-2846, 2020.
[SAN20] Taiji Suzuki, Hiroshi Abe, and Tomoaki Nishimura. Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network. In International Conference on Learning Representations, 2020.
[SD15] Jorge F Silva and Milan S Derpich. On the characterization of comppesesiiiee ergodic sequences. IEEE Transactions on Signal Processing, 63 1):2915-29223 2015.
[$GN 19] Umut Şimşekli, Mert Gürbüzbalaban, Thanh Huy Nguyen, Gaël Richard, and Levent Sagun. On the Heavy-Tailee Theory of Stochastic Gradient Descent for Deep Neural Networks. arXiv: /r1iv: 192.00001 [cs, math, stat], November 2019.
[SS20] Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: central limit theorem. Stochastic Processes and their Applications, 130(3):1820-15 2020.
13

---

[$SDE20] Umut Şimsekli, Ozan Sener, George Deligiannidis, and Murat A Erdogdu. Hausdorff dimension, heavy tails, and generalization neural networks. In H. Larochelle, M. Ran- zato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 5138-5151. Curran Associates, Inc., 2020.
[SSG19] Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference Machine Learning, pages 5827-5837. PMLR, 2019.
[SU20] Aastha M. Sathe and N. S. Upadhye. Estimation of the parameters of mul- tivariate stable distributions. Communications in Statistics SSimlltiinn and Computation, 0(0):1-18, July 2020. Publisher: Taylor & Francis _eprint:
https://doi.oor//0.. 1080/03610918.0000 211.1.220.1884444
[SZ15] Karen Simonyan and Andrew Zisserman. Very Deep Convolutional Networks for Large-Scale Image Recognition, arXiv: [cs], April 2015.
[Szn91] Alain-Sol Sznitman. Topics in propagation of chaos. In Ecole d'été de probabilités de Saint-Flour XIX-1989, pages 165-251. Springer, 1991.
[$ZTG20] Umut Şimşekli, Lingjoong Zhu, Yee Whye Tch, and Mert Gürbüzzalaban. Fractional underdamped langevin dynamics: Retargeting sgd with momentum under heavy-tailed gradient noise. In ICML,, 2020.
[TNT18] G. Tzagkarakis, J. P. Nolan, and P. Tsakalides. Compressive Sensing of Temporally Correlated Sources Using Isotropic Multivariate Stable Laws. In 2018 26th European Signal Processing Conference (EUSIPCO), pages 1710-1714, September 2018. ISSN: 2076-1465.
Asma Teimouri, Mahbanoo Tata, Mohsen Rezapour, Rafal Kulik, and Narayanaswamy Balakrishnan. Asymptotic behavior of eigenvalues of variance-covariane matrix of high-dimensional heavy-tailed lévy process. Methodology and Computing in Applied Probability, pages 1-23, 2020.
[WGZ- Hongjian Wang. Mert Gürbüzballaaa, Lingjiong Zhu, Umut Şimşekli, and Murat A Erdogdu. Convergence rates of stochastic gradient descent under infinite noise variance. In NeurlPS, 2021.
[Wu20] Yihong Wu. Lecture notes information-theerreie methods for high-dimensional statistics, 2020.
[WZG20] Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. arXiv:2002.07376 [cs, stat], August 2020.
[YLWT17] Xiyu Yu, Tongliang Liu, Xinchao Wang, and Dacheng Tao. On compressing deep models by low rank and sparse decomposition. In 2017 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 67-76, Honolulu, HI, July 2017. IEEE.
[ZFM- 20] Pan Zhou, Jiashi Feng, Chao Ma, Caiming Xiong, Steven Chu Hong Hoi, and Weinan E. Towards theoretically understanding why SGD generalizes better than adam in deep learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21285-21296. Curran Associates, Inc., 2020.
[ZKV-20 20] Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungycon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21285-21222 Curran Associates, Inc., 2020.
[ZZL19] Yi Zhou, Huishuai Zhang, and Yingbin Liang. Understanding generalization error of sgd in nonconvex optimization. In International Conference on Acoustics, Speech, and Signal Processing (ICASSP), May 2019.
14

---

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] For theoretical and practical
limits of the work presented here see Section 6.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work on the effective pruning of deep neural networks and how this relate to generalization. We expect the downstream effects of both the practical and theoretical aspects of our research to be positive in terms of future energy and storage use, as well as in the creation of robust algorithms. However, we understand that this is high-dimensional issue and are happy to reconsider our opinion if the reviewers have any concerns.
(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] Please see Sections 3 and 4.
(b) Did you include complete proofs of all theoretical results? [Yes] Please see the supplementary material regarding our results in Sections 3 and 4.
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 or URL)? [Yes] We provided these in the supplemetary material.
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] We provided much detail as possible Section 5 within space limits, we provided the rest in the supplementary material.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No] As can be seen in Section our results involve running the same experiment many times with range of hyperparameters that are fairly close to each other. Our hypotheses are supported by the overall consistency and direction of these results. We believe that replicating these experiments numerous times would both be both too costly and would provide only marginal benefit.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes] We provided these in the supplementary material.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [Yes]
The code base of this paper was made accessible through supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We use publicly available and non-personal data only, namely MNIST and 10 datasets.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] We use publicly available and non-personal data only, namely MNIST and CIFARIO datasets.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] This item is not applicable for our research.
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A] This item is not applicable for our research.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] This item is not applicable for our research.
15


Reviews:
[{"review_id": "zvXk4c15yec", "reviewer": "Reviewer_9D1o", "summary": "The paper looks at the compressibility and generalization ability of multi-layer neural networks under the heavy tailed mean-field limit. The mean-field condition is invoked to simplify the analysis of the distribution of weight parameters as the distributions of individual weights are independent, while the heavy-tailed condition is needed to ensure an abundance of small weights (weights at the tail) whose removal would result in bounded relative error. Compression error is defined in weight space as the relative distance between the compressed weight vector (weight vector where small weights are set to zero) and the original weight vector.\n\nThe paper shows that arbitrarily low compression errors can be achieved under a range of pruning strategies (global pruning, layer-wise pruning, singular value pruning, and neuron pruning) if the network is sufficiently large. Another condition is for the p-norm used to calculate the error to have p larger than the heavy tail coefficients.\n", "questions": "", "limitations": "", "rating": 6, "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": "The paper is well-written and the authors are to be commended for providing the necessary background for making their theoretical contributions accessible to readers who are new to this subject area. I believe the theoretical results are novel, even if the main results follow in a rather straightforward manner from a standard result on the compressibility of heavy-tailed i.i.d random variables (Lemma S2 in the appendix). In general the compressibility results are largely intuitive: The larger the number of weights is, and the more heavy-tailed their distribution is, the more probable that there will be enough small weights so that their removal would have minimal impact on the weight vector norm. The results are thus not surprising, especially that they follow from standard results in the statistics of heavy-tailed distributions.\n\nIn the empirical results, the authors convincingly demonstrate that in several cases, there is a correlation between the tail indices and the prunability and generalization ability of the network.\nHowever, the authors do not control the tail indices directly. Rather, they vary the learning rate and batch size to obtain the desired tail indices. As such, the empirical results do not categorically prove that tail indices have a causal influence on the prunability and generalization ability of the network. There could be other confounding factors here as the tail indices are not controlled directly. The authors, however, phrase the discussion as if heavier tail indices lead to better generalization and prunability. The empirical evidence certainly points in that direction, but it is not categorical. The authors need to either 1)devise experiments where they can directly control tail indices while other factors are constant and observe the effects, 2) modify the discussion to highlight that the empirical results are circumstantial (but not definite) evidence that heavier tails are the causal factors leading to more prunable and generalizable networks in the experimental results.\n\nFinally, it is not clear what the practical benefits of the theoretical results are. The effect of $\\eta/b$ (ratio between learning rate and batch-size) on generalization accuracy is known, as is the fact that a larger ratio leads to heavier tailed weight . While deeper theoretical understanding is a worthy goal in itself, the paper would benefit from discussing any novel practical implications of the theoretical results.\n\n\n\nMinor comments:\n1)L198: remove duplicate $\\epsilon > 0$\n2)L357: remove confirm\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper has no negative societal effects that I am aware of.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "hX49RyWyya1", "reviewer": "Reviewer_jjg2", "summary": "The main contribution of this paper is to link the two properties of compressibility and SGD. (i) as the network size goes to infinity, the system can converge to a mean-field limit, where the network weights behave independently, (ii) for a large step-size/batch-size ratio, the SGD iterates can converge to a heavy-tailed stationary distribution. In the case where these two phenomena occur simultaneously, we prove that the networks are guaranteed to be ‘lp-compressible’. Further experiments on fully connected and convolutional neural networks and show that the results are in strong accordance with the theory.", "questions": "", "limitations": "", "rating": 6, "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": "Originality: Novel. This work links compressibility with SGD, and theoretically explains that simple pruning strategies in some networks are also effective.\n\nQuality: The theoretical proof is quite sufficient.\n\nClarity: well written. \n\nSignificance: Moderately significant. This paper does theoretical derivation and experimental verification on the convolutional layer and the fully connected layer.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1.\tThe theoretical framework proposed in this article is not applied to the Resnet layer, which is widely used in recent works.\n2.\tThis paper only experimented on the mnist and cifar10 datasets, which seems relatively small for pruning experiments.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "TsfOvJr8eHs", "reviewer": "Reviewer_9G5Z", "summary": "This paper gives a theoretical characterization of the underlying cause that makes the neural networks amenable to common compression schemes in the over-parameterized regime. It is done by connecting the dynamics of the learning algorithms such as SGD to the heavy tails of the weights of a network, which leads to better compressibility. The main contribution is to provide sufficient conditions for the compressibility from the limiting distribution of SGD, and show how the compressibility of a network can lead to better generalization. \n", "questions": "", "limitations": "", "rating": 6, "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": "The paper is very well written, and is addressing an important topic of the field of why and when a pruning method is useful. It also makes several technical contributions by borrowing classical results to prove new theorem. However, the following points need to be considered: \n\nMy main concern is that the main result is based on a condition / conjecture (Definition 1) that seems to be too ideal. The remark on l.163  is not exact: note that [DBDFS20] proved that a similar form of (4)  indeed holds … I think that it remains still an open question. In DBDFS20, L=2, and W_L is fixed, only W_1 is considered to be learnt by SGD. Thus it is very hard to believe why (4) holds in more complicated cases such as the heavy tails. Such kind of details needs to be mentioned so that your readers have a clear view of the current state-of-the-art. \n\nAbout the generalization bounds, what are the contributions compared to the work mentioned on line 275? Are you using a very different technique to prove the similar results? How similar the Theorem 4 compared to the existing results?\n\nThe assumption on SGD in Definition 1 is for eq. (2), however, in the reference GSZ20, it seems that ergodic averaging SGD is proved to converge to a stable distribution (l.340). Is the SGD limit of (2) also converging to a heavy-tailed distribution? Why in the numerical results, the ergodic averaging SGD is chosen rather than (2) for evaluation? \n\nTheorem 2 eq. (5), the w_l should be W_l as the norm ||. || is for Frobenius norm, thus there is a typo? It would be good to give some intuition why there is division by 2 in the condition p>=max_l alpha_l / 2. This is not the case for Theorem 1 and 3. \n\nWhich p norm is taken in Figure 3 to compute the compression error?\n\nline 323, what it means to be ‘consistent’ with the results of … ?\n\nIn Figure 1-7, sometimes write Mean estimated tail index, sometime write estimated tail index, are they the same? \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "2WiBW14mn4", "reviewer": "Reviewer_uErr", "summary": "This paper analyze the compressibility of over-parameterized neural networks using the heavy-tail property of SGD. The authors show that when the network weights are approximately sampled from a heavy-tailed distribution, the weights are more compressible. The authors also provide a generalization guarantee showing that more compressible networks have smaller generalization gap.", "questions": "", "limitations": "", "rating": 7, "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": "I think overall this is a good paper. I like the connection between the heavy-tail property of SGD on large network and the compressibility of the network (the l_p compressibility from the compressed sensing literature). The results seem to be new in the literature and I believe the results will strengthen our understanding of neural network compression.\n\nThe paper is clearly written. The notation is slightly heavy (which happens to most neural network theory papers) but mostly clearly defined. I am able to follow most parts of the paper.\n\nI have some concerns on the generalization bound in Theorem 4. It seems to say that if the network has smaller kappa (more compressible), then its generalization gap will be smaller. However, this is only an upper bound for the population risk of the compressed network (R_0(\\hat{w})). When kappa decreases, the upper bound decreases, but it does not necessarily mean R_0(\\hat{w}) also decreases. The authors should either prove a lower bound or clearly state this limitation in the paper.\n\nMinor:\n\nLine 85: Y is defined as a discrete set of integers {1, …, d_Y} on line 81. So f_w(x) should be a function that maps from X_B to R^{d_Y} rather than Y; similar thing on line 93.\n\nLine 212-213: “how would the smallest kappa_l would differ…” it seems to be a grammar error—two “would”.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper mentioned a few possible future directions which can be considered as resolving the limitations of the current work.\nI did not observe immediate societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Four reviewers recommend this paper to be accepted. The paper provides result addressing why and when pruning is possible. A concern is that the main result is based on a condition that might be too ideal. Taking the discussion into consideration, I find that the manuscript makes valuable contributions outweighing its limitations. Hence I am recommending the submission for publication. I ask the authors to implement the improvements promised in their responses and to carefully consider the reviewers comments in the preparation of the final manuscript.
Decision: Accept (Poster)