Implicit Compressibility of Overparametrized Neural Networks Trained
  with Heavy-Tailed SGD
Neural network compression has been an increasingly important subject, not
only due to its practical relevance, but also due to its theoretical
implications, as there is an explicit connection between compressibility and
generalization error. Recent studies have shown that the choice of the
hyperparameters of stochastic gradient descent (SGD) can have an effect on the
compressibility of the learned parameter vector. These results, however, rely
on unverifiable assumptions and the resulting theory does not provide a
practical guideline due to its implicitness. In this study, we propose a simple
modification for SGD, such that the outputs of the algorithm will be provably
compressible without making any nontrivial assumptions. We consider a
one-hidden-layer neural network trained with SGD, and show that if we inject
additive heavy-tailed noise to the iterates at each iteration, for any
compression rate, there exists a level of overparametrization such that the
output of the algorithm will be compressible with high probability. To achieve
this result, we make two main technical contributions: (i) we prove a
'propagation of chaos' result for a class of heavy-tailed stochastic
differential equations, and (ii) we derive error estimates for their Euler
discretization. Our experiments suggest that the proposed approach not only
achieves increased compressibility with various models and datasets, but also
leads to robust test performance under pruning, even in more realistic
architectures that lie beyond our theoretical setting.
Yijun Wan, Melih Barsbey, Abdellatif Zaidi, Umut Simsekli
# Implicit Compressibility of Overparametrized Neural Networks Trained with Heavy-Tailed SGD

###### Abstract

Neural network compression has been an increasingly important subject, due to its practical implications in terms of reducing the computational requirements and its theoretical implications, as there is an explicit connection between compressibility and the generalization error. Recent studies have shown that the choice of the hyperparameters of stochastic gradient descent (SGD) can have an effect on the compressibility of the learned parameter vector. Even though these results have shed some light on the role of the training dynamics over compressibility, they relied on unverifiable assumptions and the resulting theory does not provide a practical guideline due to its implicitness. In this study, we propose a simple modification for SGD, such that the outputs of the algorithm will be provably compressible without making any nontrivial assumptions. We consider a one-hidden-layer neural network trained with SGD and we inject additive heavy-tailed noise to the iterates at each iteration. We then show that, for _any_ compression rate, there exists a level of overparametrization (i.e., the number of hidden units), such that the output of the algorithm will be compressible with high probability. To achieve this result, we make two main technical contributions: (i) we build on a recent study on stochastic analysis and prove a 'propagation of chaos' result with improved rates for a class of heavy-tailed stochastic differential equations, and (ii) we derive strong-error estimates for their Euler discretization. We finally illustrate our approach on experiments, where the results suggest that the proposed approach achieves compressibility with a slight compromise from the training and test error.

## 1 Introduction

Obtaining compressible neural networks has become an increasingly important task in the last decade, and it has essential implications from both practical and theoretical perspectives. From a practical point of view, as the modern network architectures might contain an excessive number of parameters, compression has a crucial role in terms of deployment of such networks in resource-limited environments O'Neill (2020); Blalock et al. (2020). On the other hand, from a theoretical perspective, several studies have shown that compressible neural networks should achieve a better generalization performance due to their lower-dimensional structure Arora et al. (2018); Suzuki et al. (2020, 2020); Hsu et al. (2021); Barsbey et al. (2021); Sefidgaran et al. (2022).
Despite their evident benefits, it is still not yet clear how to obtain compressible networks with provable guarantees. In an empirical study Frankle and Carbin (2018), introduced the 'lottery ticket hypothesis', which indicated that a randomly initialized neural network will have a sub-network that can achieve a performance that is comparable to the original network; hence, the original network can be compressed to the smaller sub-network. This empirical study has formed a fertile ground for subsequent theoretical research, which showed that such a sub-network can indeed exist (see e.g., Malach et al. (2020); Burkholz et al. (2021); da Cunha et al. (2022)); yet, it is not clear how to develop an algorithm that can find it in a feasible amount of time.

Another line of research has developed methods to enforce compressibility of neural networks by using sparsity enforcing regularizers, see e.g., Papyan et al. (2018); Aytekin et al. (2019); Chen et al. (2020); Lederer (2023); Kengne and Wade (2023). While they have led to interesting algorithms, the resulting algorithms typically require higher computational needs due to the increased complexity of the problem. On the other hand, due to the nonconvexity of the overall objective, it is also not trivial to provide theoretical guarantees for the compressibility of the resulting network weights.

Recently it has been shown that the training dynamics can have an influence on the compressibility of the algorithm output. In particular, motivated by the empirical and theoretical evidence that heavy-tails might arise in stochastic optimization (see e.g., Martin and Mahoney (2019); Simsekli et al. (2019); Simsekli et al. (2019); Simsekli et al. (2020); Zhou et al. (2020); Zhang et al. (2020); Camuto et al. (2021)), Barsbey et al. (2021); Shin (2021) showed that the network weights learned by stochastic gradient descent (SGD) will be compressible if we assume that they are heavy-tailed and there exists a certain form of statistical independence within the network weights. These studies illustrated that, even _without_ any modification to the optimization algorithm, the learned network weights can be compressible depending on the algorithm hyperparameters (such as the step-size or the batch-size). Even though the tail and independence conditions were recently relaxed in Lee et al. (2022), the resulting theory relies on unverifiable assumptions, and hence does not provide a practical guideline.

In this paper, we focus on single-hidden-layer neural networks with a fixed second layer (i.e., the setting used in previous work De Bortoli et al. (2020)) trained with vanilla SGD, and show that, when the iterates of SGD are simply perturbed by heavy-tailed noise with infinite variance (similar to the settings considered in Simsekli (2017); Nguyen et al. (2019); Simsekli et al. (2020); Huang et al. (2021); Zhang and Zhang (2023)), the assumption made in Barsbey et al. (2021) in effect holds. More precisely, denoting the number of hidden units by \(n\) and the step-size of SGD by \(\eta\), we consider the _mean-field limit_, where \(n\) goes to infinity and \(\eta\) goes to zero. We show that in this limiting case, the columns of the weight matrix will be independent and identically distributed (i.i.d.) with a common _heavy-tailed_ distribution. Then, we focus on the finite \(n\) and \(\eta\) regime and we prove that for _any_ compression ratio (to be precised in the next section), there exists a number \(N\), such that if \(n\geq N\) and \(\eta\) is sufficiently small, the network weight matrix will be compressible with high probability. Figure 1 illustrates the overall approach and precises our notion of compressibility.

To prove our compressibility result, we make two main technical contributions. We first consider the case where the step-size \(\eta\to 0\), for which the SGD recursion perturbed with heavy-tailed noise yields a _system_ of heavy-tailed stochastic differential equations (SDE)
with \(n\) particles. As our first technical contribution, we show that as \(n\to\infty\) this particle system converges to a mean-field limit, which is a McKean-Vlasov-type SDE that is driven by a heavy-tailed process Jourdain et al. (2007); Liang et al. (2021); Cavallazzi (2023). For this convergence, we obtain a rate of \(n^{-1/2}\), which is faster than the best known rates, as recently proven in Cavallazzi (2023). This result indicates that a _propagation of chaos_ phenomenon Sznitman (1991) emerges1: in the mean-field regime, the columns of the weight matrix will be i.i.d. and heavy-tailed due to the injected noise.

Footnote 1: Here, the term chaos refers to statistical independence: when the particles are initialized independently, they stay independent through the whole process even though their common distribution might evolve.

Next, we focus on the Euler discretizations of the particle SDE to be able to obtain a practical, implementable algorithm. As our second main technical contribution, we derive _strong-error_ estimates for the Euler discretization Kloeden et al. (1992) and show that for sufficiently small \(\eta\), the trajectories of the discretized process will be close to the one of the continuous-time SDE, in a precise sense. This result is similar to the ones derived for vanilla SDEs (e.g., Mikulevicius and Xu (2018)) and enables us to incorporate the error induced by using a finite step-size \(\eta\) to the error of the overall procedure.

Equipped with these results, we finally prove a high-probability compression bound by invoking Gribonval et al. (2012); Amini et al. (2011), which essentially shows that an i.i.d. sequence of heavy-tailed random variables will have a small proportion of elements that will dominate the whole sequence in terms of absolute values (to be stated formally in the next section). This establishes our main contribution. Here, we shall note that similar mean-field regimes have already been considered in machine learning (see e.g., Mei et al. (2018); Chizat and Bach (2018); Rotskoff and Vanden-Eijnden (2018); Jabir et al. (2019); Mei et al. (2019); De Bortoli et al. (2020); Sirignano and Spiliopoulos (2022)). However, these studies all focused on particle SDE systems that either converge to deterministic systems or that are driven by Brownian motion. While they have introduced interesting analysis tools, we cannot directly benefit from their analysis in this paper, since the heavy-tails are crucial for obtaining compressibility, and the Brownian-driven SDEs cannot produce heavy-tailed solutions in general. Hence, as we consider heavy-tailed SDEs in this paper, we need to use different techniques to prove mean-field limits, compared to the prior art in machine learning.

Figure 1: The illustration of the overall approach. We consider a one-hidden-layer neural network with \(n\) hidden units, which results in a weight matrix of \(n\) columns (first layer). We show that, when SGD is perturbed with heavy-tailed noise, as \(n\to\infty\), each column will follow a multivariate heavy-tailed distribution in an i.i.d. fashion. This implies that a small number of columns will have significantly larger norms compared to the others; hence, the norm of the overall weight matrix will be determined by such columns Gribonval et al. (2012). As a result, the majority of the columns can be removed (i.e., set to zero), which we refer to as compressibility.
To validate our theory, we conduct experiments on single-hidden-layer neural networks on different datasets. Our results show that, even with a minor modification to SGD (i.e., injecting heavy-tailed noise), the proposed approach can achieve compressibility with a negligible computational overhead and with a slight compromise from the training and test error. For instance, on a classification task with the MNIST dataset, when we set \(n=10\)K, with vanilla SGD, we obtain a test accuracy of 94.69%, whereas with the proposed approach, we can remove 44% of the columns of the weight matrix, while maintaining a test accuracy of 94.04%. We provide all the proofs in the appendix.

## 2 Preliminaries and Technical Background

**Notation.** For a vector \(u\in\mathbb{R}^{d}\), denote by \(\|u\|\) its Euclidean norm, and by \(\|u\|_{p}\) its \(\ell_{p}\) norm. For a function \(f\in C(\mathbb{R}^{d_{1}},\mathbb{R}^{d_{2}})\), denote by \(\|f\|_{\infty}:=\sup_{x\in\mathbb{R}^{d_{1}}}\|f(x)\|\) its \(L^{\infty}\) norm. For a family of \(n\) (or infinity) vectors, the indexing \(\cdot^{i,n}\) denotes the \(i\)-th vector in the family. In addition, for random variables, \(\stackrel{{\rm(d)}}{{=}}\) means equality in distribution, and the space of probability measures on \(\mathbb{R}^{d}\) is denoted by \(\mathcal{P}(\mathbb{R}^{d})\). For a matrix \(A\in\mathbb{R}^{d_{1}\times d_{2}}\), its Frobenius norm is denoted by \(\|A\|_{F}=\sqrt{\sum_{i=1}^{d_{1}}\sum_{j=1}^{d_{2}}|a_{i,j}|^{2}}\). Without specifically mentioning, \(\mathbb{E}\) denotes the expectation over all the randomness taken into consideration.

### Alpha-stable processes

A random variable \(X\in\mathbb{R}^{d}\) is called \(\alpha\)_-stable_ with the stability parameter \(\alpha\in(0,2]\), if \(X_{1}\), \(X_{2}\), \(\ldots\) are independent copies of \(X\), then \(n^{-1/\alpha}\sum_{j=1}^{n}X_{j}\stackrel{{\rm(d)}}{{=}}X\) for all \(n\geq 1\)Samoradnitsky (2017). Stable distributions appear as the limiting distribution in the generalized central limit theorem (CLT) Gnedenko and Kolmogorov (1954). In the one-dimensional case (\(d=1\)), we call the variable \(X\) a symmetric \(\alpha\)-stable random variable if its characteristic function is of the following form: \(\mathbb{E}[\exp(i\omega X)]=\exp(-|\omega|^{\alpha})\) for \(\omega\in\mathbb{R}\).

For symmetric \(\alpha\)-stable distributions, the case \(\alpha=2\) corresponds to the Gaussian distribution, while \(\alpha=1\) corresponds to the Cauchy distribution. An important property of \(\alpha\)-stable distributions is that in the case \(\alpha\in(1,2)\), the \(p\)-th moment of an \(\alpha\)-stable random variable is finite if and only if \(p<\alpha\); hence, the distribution is heavy-tailed. In particular, \(\mathbb{E}[|X|]<\infty\) and \(\mathbb{E}[|X|^{2}]=\infty\), which can be used to model phenomena with heavy-tailed observations.

There exist different types of \(\alpha\)-stable random vectors in \(\mathbb{R}^{d}\). In this study we will be interested in the following three variants, whose characteristic functions (for \(u\in\mathbb{R}^{d}\)) are given as follows:

* **Type-I.** Let \(Z\in\mathbb{R}\) be a symmetric \(\alpha\)-stable random variable. We then construct the random vector \(X\) such that all the coordinates of \(X\) is equated to \(Z\). In other words \(X=\mathbf{1}_{d}Z\), where \(\mathbf{1}_{d}\in\mathbb{R}^{d}\) is a vector of ones. With this choice, \(X\) admits the following characteristic function: \(\mathbb{E}\left[\exp(i\langle u,X\rangle)=\exp(-|\langle u,\mathbf{1}_{d} \rangle|^{\alpha})\right]\);
* **Type-II.**\(X\) has i.i.d. coordinates, such that each component of \(X\) is a symmetric \(\alpha\)-stable random variable in \(\mathbb{R}\). This choice yields the following characteristic function: \(\mathbb{E}\left[\exp(i\langle u,X\rangle)=\exp(-\sum_{i=1}^{d}|u_{i}|^{\alpha})\right]\);
* **Type-III.**\(X\) is rotationally invariant \(\alpha\)-stable random vector with the characteristic function \(\mathbb{E}\left[\exp(i\langle u,X\rangle]=\exp(-\|u\|^{\alpha})\). Note that the Type-II and Type-III noises reduce to a Gaussian distribution when \(\alpha=2\) (i.e., the characteristic function becomes \(\exp(-\|u\|^{2})\)). Similar to the fact that stable distributions extend the Gaussian distribution, we can define a more general random process, called the _\(\alpha\)-stable Levy process_, that extends the Brownian motion. Formally, \(\alpha\)-stable processes are stochastic processes \((\mathrm{L}_{t}^{\alpha})_{t\geq 0}\) with independent and stationary \(\alpha\)-stable increments, and have the following definition:
* \(\mathrm{L}_{0}^{\alpha}=0\) almost surely,
* For any \(0\leq t_{0}<t_{1}<\cdots<t_{N}\), the increments \(\mathrm{L}_{t_{n}}^{\alpha}-\mathrm{L}_{t_{n-1}}^{\alpha}\) are independent,
* For any \(0\leq s<t\), the difference \(\mathrm{L}_{t}^{\alpha}-\mathrm{L}_{s}^{\alpha}\) and \((t-s)^{1/\alpha}\mathrm{L}_{1}^{\alpha}\) have the same distribution,
* \(\mathrm{L}_{t}^{\alpha}\) is stochastically continuous, i.e. for any \(\delta>0\) and \(s\geq 0\), \(\mathbb{P}(\|\mathrm{L}_{t}^{\alpha}-\mathrm{L}_{s}^{\alpha}\|>\delta)\to 0\) as \(t\to s\). To fully characterize an \(\alpha\)-stable process, we further need to specify the distribution of \(\mathrm{L}_{1}^{\alpha}\). Along with the above properties, the choice for \(\mathrm{L}_{1}^{\alpha}\) will fully determine the process. For this purpose, we will again consider the previous three types of \(\alpha\)-stable vectors: We will call the process \(\mathrm{L}_{t}^{\alpha}\) a Type-I process if \(\mathrm{L}_{1}^{\alpha}\) is a Type-I \(\alpha\)-stable random vector. We define the Type-II and Type-III processes analogously. Note that, when \(\alpha=2\), Type-II and Type-III processes reduce to the Brownian motion. For notational clarity, occasionally, we will drop the index \(\alpha\) and denote the process by \(\mathrm{L}_{t}\).

### Compressibility of heavy-tailed processes

One interesting property of heavy-tailed distributions in the one-dimensional case is that they exhibit a certain compressibility property. Informally, if we consider a sequence of i.i.d. random variables coming from a heavy-tailed distribution, a small portion of these variables will likely have a very large magnitude due to the heaviness of the tails, and they will dominate all the other variables in terms of magnitudes Nair et al. (2022). Therefore, if we only keep this small number of variables with large magnitude, we can 'compress' (in a lossy way) the whole sequence of random variables by representing it with this small subset. Concurrently, Amini et al. (2011); Gribonval et al. (2012) provided formal proofs for these explanations. Formally, Gribonval et al. (2012) characterized the family of probability distributions whose i.i.d. realizations are compressible. They introduced the notion of \(\ell_{p}\)-compressibility - in terms of the error made after pruning a fixed portion of small (in magnitude) elements of an i.i.d. sequence, whose common distribution has diverging \(p\)-th order moments. More precisely, let \(X_{n}=(x_{1},\ldots,x_{n})\) be a sequence of i.i.d. random variables such that \(\mathbb{E}\left[|x_{1}|^{\alpha}\right]=\infty\) for some \(\alpha\in\mathbb{R}_{+}\). Then, for all \(p\geq\alpha\) and \(0<\kappa\leq 1\) denoting by \(X_{n}^{(\kappa n)}\) the \(\lfloor\kappa n\rfloor\) largest ordered statistics2 of \(X_{n}\), the following asymptotic on the relative compression error holds almost surely:

Footnote 2: In other words, \(X_{n}^{(\kappa n)}\) is obtained by keeping only the largest (in magnitude) \(\kappa n\) elements of \(X_{n}\) and setting all the other elements to \(0\).

\[\lim_{n\to\infty}\frac{\|X_{n}^{(\kappa n)}-X_{n}\|_{p}}{\|X_{n}\|_{p}}=0\]
Built upon this fact, Barsbey et al. (2021) proposed structural pruning of neural networks (the procedure described in Figure 1) by assuming that the network weights provided by SGD will be asymptotically independent. In this study, instead of making this assumption, we will directly prove that the network weights will be asymptotically independent in the two layer neural network setting with additive heavy-tailed noise injections to SGD.

## 3 Problem Setting and the Main Result

We consider a single hidden-layer overparametrized network of \(n\) units and use the setup provided in De Bortoli et al. (2020). Our goal is to minimize the expected loss in a supervised learning regime, where for each data \(z=(x,y)\) distributed according to \(\pi(\mathrm{d}x,\mathrm{d}y)\);3 the feature \(x\) is included in \(\mathcal{X}\subset\mathbb{R}^{d}\) and the label \(y\) is in \(\mathcal{Y}\). We denote by \(\theta^{i,n}\in\mathbb{R}^{p}\) the parameter for the \(i\)-th unit, and the parametrized model is denoted by \(h_{x}:\mathbb{R}^{p}\rightarrow\mathbb{R}^{l}\). The mean-field network is the average over models for \(n\) units:

Footnote 3: Note that for finite datasets, \(\pi\) can be chosen as a measure supported on finitely many points.

\[f_{\Theta^{n}}(x)=\frac{1}{n}\sum_{i=1}^{n}h_{x}(\theta^{i,n}),\]

where \(\Theta^{n}=(\theta^{i,n})_{i=1}^{n}\in\mathbb{R}^{p\times n}\) denotes the collection of parameters in the network and \(x\in\mathcal{X}\) is the feature variable for the data point. In particular, the mean-field network corresponds to a two-layer neural network with the weights of the second layer are fixed to be \(1/n\) and \(\Theta^{n}\) is the parameters of the first layer. While this model is less realistic than the models used in practice, nevertheless, we believe that it is desirable from theoretical point of view, and this defect can be circumvented upon replacing \(h_{x}(\theta^{i,n})\) by \(h_{x}(c^{i,n},\theta^{i,n})=c^{i,n}h_{x}(\theta^{i,n})\), where \(c^{i,n}\) and \(\theta^{i,n}\) are weights corresponding to different layers. However, in order to obtain similar results in this setup as in our paper, stronger assumptions are inevitable and the proof should be more involved, which are left for future work.

Given a loss function \(\ell:\mathbb{R}^{l}\times\mathcal{Y}\rightarrow\mathbb{R}^{+}\), the goal (for each \(n\)) is to minimize the expected loss

\[R(\Theta^{n})=\mathbb{E}_{(x,y)\sim\pi}\left[\ell\left(f_{\Theta^{n}}(x),y \right)\right]. \tag{1}\]

One of the most popular approaches to minimize this loss is the stochastic gradient descent (SGD) algorithm. In this study, we consider a simple modification of SGD, where we inject a stable noise vector to the iterates at each iteration. For notational clarity, we will describe the algorithm and develop the theory over gradient descent, where we will assume that the algorithm has access to the true gradient \(\nabla R\) at every iteration. However, since we are already injecting a heavy-tailed noise with _infinite variance_, our techniques can be adapted for handling the stochastic gradient noise (under additional assumptions, e.g., De Bortoli et al. (2020)), which typically has a milder behavior compared to the \(\alpha\)-stable noise4.

Footnote 4: In Simsekli et al. (2019) the authors argued that the stochastic gradient noise in neural networks can be modeled by using stable distributions. Under such an assumption, the effect of the stochastic gradients can be directly incorporated into \(\mathrm{L}_{t}^{\alpha}\).

Let us set the notation for the proposed algorithm. Let \(\hat{\theta}_{0}^{i,n}\), \(i=1,\ldots,n\), be the initial values of the iterates, which are \(n\) random variables in \(\mathbb{R}^{d}\) distributed independently according to a given initial probability distribution \(\mu_{0}\). Then, we consider the gradient descent updates
with stepsize \(\eta n\), which is perturbed by i.i.d. \(\alpha\)-stable noises \(\sigma\cdot\eta^{1/\alpha}X_{k}^{i,n}\) for each unit \(i=1,\ldots,n\) and some \(\sigma>0\):

\[\begin{cases}\hat{\theta}_{k+1}^{i,n}=\hat{\theta}_{k}^{i,n}-\eta n\left[ \partial_{\theta^{i,n}}R(\Theta^{n})\right]+\sigma\cdot\eta^{1/\alpha}X_{k}^{ i,n}\\ \hat{\theta}_{0}^{i,n}\sim\mu_{0}\in\mathcal{P}(\mathbb{R}^{d}),\end{cases} \tag{2}\]

where the scaling factor \(\eta^{1/\alpha}\) in front of the stable noise enables the discrete dynamics of the system homogenize to SDEs as \(\eta\to 0\). At this stage, we do not have to determine which type of stable noise (e.g., Type-I, II, or III) that we shall consider as they will all satisfy the requirements of our theory. However, our empirical findings will illustrate that the choice will affect the overall performance.

We now state the assumptions that will imply our theoretical results. The following assumptions are similar to (De Bortoli et al., 2020, Assumption A1).

**Assumption 1**.:
* Regularity of the model: for each \(x\in\mathcal{X}\), the function \(h_{x}:\mathbb{R}^{p}\to\mathbb{R}^{l}\) is two-times differentiable, and there exists a function \(\Psi:\mathcal{X}\to\mathbb{R}_{+}\) such that for any \(x\in\mathcal{X}\), \[\|h_{x}(\cdot)\|_{\infty}+\|\nabla h_{x}(\cdot)\|_{\infty}+\|\nabla^{2}h_{x}( \cdot)\|_{\infty}\leq\Psi(x).\]
* Regularity of the loss function: there exists a function \(\Phi:\mathcal{Y}\to\mathbb{R}_{+}\) such that \[\|\partial_{1}\ell(\cdot,y)\|_{\infty}+\|\partial_{1}^{2}\ell(\cdot,y)\|_{ \infty}\leq\Phi(y)\]
* Moment bounds on \(\Phi(\cdot)\) and \(\Psi(\cdot)\): there exists a positive constant \(B\) such that \[\mathbb{E}_{(x,y)\sim\pi}[\Psi^{2}(x)(1+\Phi^{2}(y))]\leq B^{2}.\]

Let us remark that these are rather standard smoothness assumptions that have been made in the mean field literature Mei et al. (2018, 2019) and are satisfied by several smooth activation functions, including the sigmoid and hyper-tangent functions.

We now proceed to our main result. Let \(\hat{\Theta}_{k}^{n}\in\mathbb{R}^{p\times n}\) be the concatenation of all parameters \(\hat{\theta}_{k}^{i,n}\), \(i=1,\ldots,n\) obtained by the recursion (2) after \(k\) iterations. We will now compress \(\hat{\Theta}_{k}^{n}\) by pruning its columns with small norms. More precisely, fix a compression ratio \(\kappa\in(0,1)\), compute the norms of the columns of \(\hat{\Theta}_{k}^{n}\), i.e., \(\|\hat{\theta}_{k}^{i,n}\|\). Then, keep the \(\lfloor\kappa n\rfloor\) columns, which have the largest norms, and set all the other columns to zero, in all their entirety. Finally, denote by \(\hat{\Theta}_{k}^{(\kappa n)}\in\mathbb{R}^{p\times n}\), the pruned version of \(\hat{\Theta}_{k}^{n}\).

**Theorem 3.1**.: _Suppose that Assumption 1 holds. For any fixed \(t>0\), \(\kappa\in(0,1)\) and \(\epsilon>0\) sufficiently small, with probability \(1-\epsilon\), there exists \(N\in\mathbb{N}_{+}\) such that for all \(n\geq N\) and \(\eta\) such that \(\eta\leq n^{-\alpha/2-1}\), the following upper bound on the relative compression error for the parameters holds:_

\[\frac{\left\|\hat{\Theta}_{\lfloor t/\eta\rfloor}^{(\kappa n)}-\hat{\Theta}_{ \lfloor t/\eta\rfloor}^{n}\right\|_{F}}{\left\|\hat{\Theta}_{\lfloor t/\eta \rfloor}^{n}\right\|_{F}}\leq\epsilon.\]

This bound shows that, thanks to the heavy-tailed noise injections, the weight matrices will be compressible at _any_ compression rate, as long as the network is sufficiently over-parametrized and the step-size is sufficiently small. We shall note that this bound also enables us to directly obtain a generalization bound by invoking (Barsbey et al., 2021, Theorem 4).
## 4 Proof Strategy and Intermediate Results

In this section, we gather the main technical contributions with the purpose of demonstrating Theorem 3.1. We begin by rewriting (2) in the following form:

\[\begin{cases}\hat{\theta}^{i,n}_{k+1}-\hat{\theta}^{i,n}_{k}=\eta b(\hat{\theta }^{i,n}_{k},\hat{\mu}^{n}_{k})+\sigma\cdot\eta^{1/\alpha}X^{i,n}_{k}\\ \hat{\theta}^{i,n}_{0}\sim\mu_{0}\in\mathcal{P}(\mathbb{R}^{d}),\end{cases} \tag{3}\]

where \(\hat{\mu}^{n}_{k}=\frac{1}{n}\delta_{\hat{\theta}^{i,n}_{k}}\) is the empirical distribution of parameters at iteration \(k\) and \(\delta\) is the Dirac measure, and the drift is given by \(b(\theta^{i,n}_{k},\mu^{n}_{k})=-\mathbb{E}[\partial_{1}\ell(\mu^{n}_{k}(h_{x }(\cdot),y)\nabla h_{x}(\theta^{i,n})]\), where \(\partial_{1}\) denotes the partial derivative with respect to the first parameter and

\[\mu^{n}_{k}(h_{x}(\cdot)):=\int h_{x}(\theta)\mathrm{d}\mu^{n}_{k}(\theta)= \sum_{i=1}^{n}h_{x}(\theta^{i,n}_{k})=f_{\Theta^{n}_{k}}(x).\]

It is easy to check that \(b(\theta^{i,n}_{k},\mu^{n}_{k})=-n\partial_{\theta^{i,n}}R(\Theta^{n})\). By looking at the dynamics from this perspective, we can treat the evolution of the parameters as a system of evolving probability distributions \(\mu^{n}_{k}\): the empirical distribution of the parameters during the training process will converge to a limit as \(\eta\) goes to \(0\) and \(n\) goes to infinity.

We start by linking the recursion (2) to its limiting case where \(\eta\to 0\). The limiting dynamics can be described by the following system of SDEs:

\[\begin{cases}\mathrm{d}\theta^{i,n}_{t}=b(\theta^{i,n}_{t},\mu^{n}_{t}) \mathrm{d}t+\sigma\mathrm{d}\mathrm{L}^{i,n}_{t}\\ \theta^{i,n}_{0}\sim\mu_{0}\in\mathcal{P}(\mathbb{R}^{d}),\end{cases} \tag{4}\]

where \(\mu^{n}_{t}=\frac{1}{n}\delta_{\theta^{i,n}_{t}}\) and \((\mathrm{L}^{i,n}_{t})_{t\geq 0}\) are independent \(\alpha\)-stable processes such that \(\mathrm{L}^{i,n}_{1}\stackrel{{(\mathrm{d})}}{{=}}X^{i,n}_{1}\). We can now see the original recursion (2) as an Euler discretization of (4) and then we have the following strong uniform error estimate for the discretization.

**Theorem 4.1**.: _Let \((\theta^{i,n}_{t})_{t\geq 0}\) be the solutions to SDE (4) and \((\hat{\theta}^{i,n}_{k})_{k\in\mathbb{N}_{+}}\) be given by SGD (2) with the same initial condition \(\xi^{i,n}\) and \(\alpha\)-stable Levy noise \(\mathrm{L}^{i,n}_{\cdot}\), \(i\)=1,...,n. Under Assumption 1, for any \(T>0\), if \(\eta k\leq T\), there exists a constant \(C\) depending on \(B,T,\alpha\) such that the approximation error_

\[\mathbb{E}\left[\sup_{i\leq n}\|\theta^{i,n}_{\eta k}-\hat{\theta}^{i,n}_{k}\| \right]\leq C(\eta n)^{1/\alpha}.\]

In comparison to the standard error estimates in the Euler-Maruyama scheme concerning only the stepsize \(\eta\), the additional \(n\)-dependence is due to the fact that here we consider the supremum of the approximation error over all \(i\leq n\), which involves the expectation of the supremum of the modulus of \(n\) independent \(\alpha\)-stable random variables.

Next, we start from the system (4) and consider the case where \(n\to\infty\). In this limit, we obtain the following McKean-Vlasov-type stochastic differential equation:

\[\begin{cases}\mathrm{d}\theta^{\infty}_{t}=b(\theta^{\infty}_{t},[\theta^{ \infty}_{t}])\mathrm{d}t+\mathrm{d}\mathrm{L}_{t}\\ [\theta^{\infty}_{0}]=\mu\in\mathcal{P}(\mathbb{R}^{d}),\end{cases} \tag{5}\]
where \((\mathrm{L}_{t})_{t\geq 0}\) is an \(\alpha\)-stable process and \([\theta_{t}^{\infty}]\) denotes the distribution of \(\theta_{t}^{\infty}\). The existence and uniqueness of a strong solution to (5) are given in Cavallazzi (2023). Moreover, for any positive \(T\), \(\mathbb{E}\left[\sup_{t\leq T}\|\theta_{t}^{\infty}\|^{\alpha}\right]<+\infty.\) This SDE with measure-dependent coefficients turns out to be a useful mechanism for analyzing the behavior of neural networks and provides insights into the effects of noise on the learning dynamics.

In this step, we will link the system (4) to its limit (5), which is a strong uniform propagation of chaos result for the weights. The next result shows that, when \(n\) is sufficiently large, the trajectories of weights asymptotically behave as i.i.d. solutions to (5).

**Theorem 4.2**.: _Following the existence and uniqueness of strong solutions to (4) and (5), let \((\theta_{t}^{i,\infty})_{t\geq 0}\) be solutions to the McKean-Vlasov equation (5) and \((\theta_{t}^{i,n})_{t\geq 0}\) be solutions to (4) associated with same realization of \(\alpha\)-stable processes \((\mathrm{L}_{t}^{i})_{t\geq 0}\) for each \(i\). Suppose that \((\mathrm{L}_{t}^{i})_{t\geq 0}\) are independent. Then there exists \(C\) depending on \(T,B\) such that_

\[\mathbb{E}\left[\sup_{t\leq T}\sup_{i\leq n}|\theta_{t}^{i,n}-\theta_{t}^{i, \infty}|\right]\leq\frac{C}{\sqrt{n}}\]

It is worth mentioning that the \(O(1/\sqrt{n})\) decreasing rate here is better, if \(\alpha<2\), than \(O(1/n^{\alpha})\) in the litterature on the propagation of chaos Cavallazzi (2023) with classical Lipschitz assumptions on the coefficients of SDEs. The reason is that here, thanks to Assumption 1, we can take into account the specific structure of the one-hidden layer neural networks.

Finally, we are interested in the distributional properties of the McKean-Vlasov equation (5). The following result establishes that the marginal distributions of (5) will have diverging second-order moments, hence, they will be heavy-tailed.

**Theorem 4.3**.: _Let \((\mathrm{L}_{t})_{t\geq 0}\) be an \(\alpha\)-stable process. For any time \(t\), let \(\theta_{t}\) be the solution to (5) with initialization \(\theta_{0}\) which is independent of \((\mathrm{L}_{t})_{t\geq 0}\) such that \(\mathbb{E}\left[\|\theta_{0}\|\right]<\infty\), then the following holds_

\[\mathbb{E}\left[\|\theta_{t}^{\infty}\|^{2}\right]=+\infty.\]

We remark that the result is weak in the sense that details on the tails of \(\theta_{t}\) with respect to \(\alpha\) and \(t\) are implicit. However, it renders sufficient for our compressibility result in Theorem 3.1.

Now, having proved all the necessary ingredients, Theorem 3.1 is obtained by accumulating the error bounds proven in Theorems 4.1 and 4.2, and applying (Gribonval et al., 2012, Proposition 1) along with Theorem 4.3.

## 5 Empirical Results

In this section, we validate our theory with empirical results. Our goal is to investigate the effects of the heavy-tailed noise injection in SGD in terms of compressibility and the train/test performance. We consider a single-hidden-layer neural network with ReLU activations and the cross entropy loss, applied on classifications tasks. We chose the Electrocardiogram (ECG) dataset Yanping and Eamonn, MNIST, and the CIFAR10 datasets. By slightly streching the scope of our theoretical framework, we also train the weights of the second layer instead of fixing them to \(1/n\).
For SGD, we fix the batch-size to be one tenth of the number of training data points, the step-size is chosen to be small enough to approximate the continuous dynamics given by the McKean-Vlasov equation in order to stay close to the theory, but also not too small so that SGD converges in a reasonable amount of time. As for the noise level \(\sigma\), we have tried a range of values for each dataset and \(n\), and we chose the largest \(\sigma\) such that the perturbed SGD converges. Intuitively, we can expect that smaller \(\alpha\) with heavier tails will lead to lower relative compression error. However, it does not guarantee better test performance: one has to fine tune the parameters appropriately to achieve a favorable trade-off between compression error and the test performance. We repeat all the experiment 5 times and report and average and the standard deviation. For the noiseless case (vanilla SGD), the results of the different runs were almost identical, hence we did not report the standard deviations. All the experimentation details are given in Appendix C and we present additional experimental results in Appendix D.

In our first experiment, we consider the ECG500 dataset and choose the Type-I noise. Our goal is to investigate the effects \(\alpha\) and \(n\) over the performance. Tables 1-2 illustrate the results. Here, for different cases, we monitor the training and test accuracies (over 1.00), the pruning ratio: the percentage of the weight matrix that can be pruned while keeping the 90% of the norm of the original matrix5, and training/test accuracies after pruning (a.p.) the network with the specified pruning ratio.

Footnote 5: The pruning ratio has the same role of \(\kappa\), whereas we fix the compression error to 0.1 and find the largest \(\kappa\) that satisfies this error threshold.

The results show that, even for a moderate number of neurons \(n=2\)K, the heavy-tailed noise results in a significant improvement in the compression capability of the neural network. For \(\alpha=1.9\), we can see that the pruning ratio increases to 39%, whereas vanilla SGD can only be compressible with a rate 11%. Besides, the compromise in the test accuracy is almost negligible, the proposed approach achieves 95.3%, whereas vanilla SGD achieves 95.7% accuracy. We also observe that decreasing \(\alpha\) (i.e., increasing the heaviness of the tails) results in a better compression rate; yet, there is a tradeoff between this rate and the test performance. In Table 2, we repeat the same experiment for \(n=10\)K. We observe that the

\begin{table}
\begin{tabular}{|c|c|c|c|c|c|} \hline \(\alpha\) & Train Acc. & Test Acc. & Pruning Ratio & Train Acc. a.p. & Test Acc. a.p. \\ \hline \hline no noise & 0.974 & 0.957 & 11.45 & 0.97 & 0.954 \\ \hline
1.75 & \(0.97\pm 0.007\) & \(0.955\pm 0.003\) & \(48.07\pm 7.036\) & \(0.944\pm 0.03\) & \(0.937\pm 0.022\) \\ \hline
1.8 & \(0.97\pm 0.007\) & \(0.955\pm 0.003\) & \(44.68\pm 5.4\) & \(0.95\pm 0.025\) & \(0.963\pm 0.016\) \\ \hline
1.9 & \(0.966\pm 0.008\) & \(0.959\pm 0.01\) & \(39.37\pm 2.57\) & \(0.962\pm 0.012\) & \(0.953\pm 0.005\) \\ \hline \end{tabular}
\end{table}
Table 1: ECG5000, Type-I noise, \(n=2\)K.

\begin{table}
\begin{tabular}{|c|c|c|c|c|c|} \hline \(\alpha\) & Train Acc. & Test Acc. & Pruning Ratio & Train Acc. a.p. & Test Acc. a.p. \\ \hline \hline no noise & 0.978 & 0.963 & 11.46 & 0.978 & 0.964 \\ \hline
1.75 & \(0.978\pm 0.001\) & \(0.964\pm 0.001\) & \(52.59\pm 6.55\) & \(0.95\pm 0.03\) & \(0.954\pm 0.022\) \\ \hline
1.8 & \(0.978\pm 0.001\) & \(0.964\pm 0.001\) & \(52.59\pm 6.55\) & \(0.95\pm 0.03\) & \(0.954\pm 0.022\) \\ \hline
1.9 & \(0.978\pm 0.001\) & \(0.964\pm 0.001\) & \(40.85\pm 2.89\) & \(0.96\pm 0.021\) & \(0.958\pm 0.013\) \\ \hline \end{tabular}
\end{table}
Table 2: ECG5000, Type-I noise, \(n=10\)K.
previous conclusions become even clearer in this case, as our theory applies to large \(n\). For the case where \(\alpha=1.75\), we obtain a pruning ratio of \(52\%\) with test accuracy \(95.4\%\), whereas for vanilla SGD the ratio is only \(11\%\) and the original test accuracy is \(96.3\%\).

In our second experiment, we investigate the impact of the noise type. We set \(n=10\)K and use the same setting as in Table 2. Tables 3-4 illustrate the results. We observe that the choice of the noise type can make a significant difference in terms of both compressibility and accuracy. While the Type-III noise seems to obtain a similar accuracy when compared to Type-I, it achieves a worse compression rate. On the other hand, the behavior of Type-II noise is perhaps more interesting: for \(\alpha=1.9\) it both increases compressibility and also achieves a better accuracy when compared to unpruned, vanilla SGD. However, we see that its behavior is much more volatile, the performance quickly degrades as we decrease \(\alpha\). From these comparisons, Type-I noise seems to achieve a better tradeoff.

In our next experiment, we consider the MNIST dataset, set \(n=10\)K and use Type-I noise. Table 5 illustrates the results. Similar to the previous results, we observe that the injected noise has a visible benefit on compressibility. When \(\alpha=1.9\), our approach doubles the compressibility of the vanilla SGD (from \(10\%\) to \(21\%\)), whereas the training and test accuracies almost remain unchanged. On the other hand, when we decrease \(\alpha\), we observe that the pruning ratio goes up to \(44\%\), while only compromising \(1\%\) of test accuracy. To further illustrate this result, we pruned vanilla SGD by using this pruning ratio (\(44\%\)). In this case, the test accuracy of SGD drops down to \(92\%\), where as our simple noising scheme achieves \(94\%\) of test accuracy with the same pruning ratio.

Our last experiment is a negative result that might be useful for illustrating the limitations of our approach. In this case, we consider the CIFAR10 dataset, set \(n=5000\), use Type-I

\begin{table}
\begin{tabular}{|c|c|c|c|c|c|} \hline \(\alpha\) & Train Acc. & Test Acc. & Pruning Ratio & Train Acc. a.p. & Test Acc. a.p. \\ \hline \hline \(1.75\) & \(0.97\pm 0.007\) & \(0.957\pm 0.005\) & \(33.48\pm 7.33\) & \(0.969\pm 0.008\) & \(0.957\pm 0.011\) \\ \hline \(1.8\) & \(0.97\pm 0.007\) & \(0.956\pm 0.007\) & \(26.81\pm 4.72\) & \(0.963\pm 0.008\) & \(0.952\pm 0.008\) \\ \hline \(1.9\) & \(0.97\pm 0.005\) & \(0.955\pm 0.005\) & \(17.59\pm 1.56\) & \(0.968\pm 0.004\) & \(0.954\pm 0.96\) \\ \hline \end{tabular}
\end{table}
Table 4: ECG5000, Type-III noise, \(n=10\)K.

\begin{table}
\begin{tabular}{|c|c|c|c|c|c|} \hline \(\alpha\) & Train Acc. & Test Acc. & Pruning Ratio & Train Acc. a.p. & Test Acc. a.p. \\ \hline \hline \(1.75\) & \(0.986\pm 0.003\) & \(0.982\pm 0.005\) & \(52.13\pm 27.78\) & \(0.865\pm 0.261\) & \(0.866\pm 0.251\) \\ \hline \(1.8\) & \(0.985\pm 0.003\) & \(0.980\pm 0.005\) & \(39.9\pm 21.55\) & \(0.971\pm 0.025\) & \(0.972\pm 0.023\) \\ \hline \(1.9\) & \(0.982\pm 0.003\) & \(0.976\pm 0.006\) & \(20.95\pm 6.137\) & \(0.982\pm 0.004\) & \(0.977\pm 0.006\) \\ \hline \end{tabular}
\end{table}
Table 3: ECG5000, Type-II noise, \(n=10\)K.

\begin{table}
\begin{tabular}{|c|c|c|c|c|c|} \hline \(\alpha\) & Train Acc. & Test Acc. & Pruning Ratio & Train Acc. a.p. & Test Acc. a.p. \\ \hline \hline no noise & \(0.95\) & \(0.9487\) & \(10.59\) & \(0.9479\) & \(0.9476\) \\ \hline \(1.75\) & \(0.95\pm 0.0001\) & \(0.9454\pm 0.0005\) & \(44.42\pm 7.16\) & \(0.944\pm 0.0025\) & \(0.9409\pm 0.0019\) \\ \hline \(1.8\) & \(0.95\pm 0.0001\) & \(0.9457\pm 0.0007\) & \(34.49\pm 5.07\) & \(0.9453\pm 0.0015\) & \(0.9397\pm 0.0036\) \\ \hline \(1.9\) & \(0.95\pm 0.0001\) & \(0.9463\pm 0.0004\) & \(21.31\pm 1081\) & \(0.9478\pm 0.0008\) & \(0.9444\pm 0.0009\) \\ \hline \end{tabular}
\end{table}
Table 5: MNIST, Type-I noise, \(n=10\)K until reaching \(95\%\) training accuracy.
noise. We compute the pruning ratio and accuracies as before and we illustrate the results in Table 6. We observe that the injected noise does not bring an advantage in this case: vanilla SGD achieves a better pruning ratio when compared to the case where \(\alpha=1.9\). On the other hand, the noise injections result in a significant drop in the training accuracy, and the situation becomes even more prominent when we decrease \(\alpha\). This might indicate that the injected noise might complicate the training process.

Following the arguments of Barsby et al. (2021), we suspect that, in this case, vanilla SGD already exhibits some sort of heavy tails and the additional noise might not be as beneficial as it was in the other cases. Although neural SGD can achieve similar compressibility, this regime is not easily controllable, and our paper is able to provide a more practical guideline for achieving compressibility along with theoretical guarantees.

## 6 Conclusion

We provided a methodological and theoretical framework for provably obtaining compressibility in mean-field neural networks. Our approach requires minimal modification for vanilla SGD and has the same computational complexity. By proving discretization error bounds and propagation of chaos results, we showed that the resulting algorithm is guaranteed to provide compressible parameters. We illustrated our approach on several experiments, where we showed that, in most cases, the proposed approach achieves a high compressibility ratio, while slightly compromising from the accuracy.

The limitations of our approach are as follows: (i) we consider mean-field networks, it would be of interest to generalize our results to more sophisticated architectures, (ii) we focused on the compressibility; yet, the noise injection also has an effect on the train/test accuracy. Hence, an investigation of the noise injection on the training loss needs to be performed to understand the bigger picture. Finally, due to the theoretical nature of our paper, it does not have a direct negative social impact.

## Acknowledgements

The authors thank Alain Durmus for fruitful discussions. U.S. is partially supported by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANR-19-P3IA0001 (PRAIRIE 3IA Institute) and by the European Research Council Starting Grant DYNASTY - 101039676.

\begin{table}
\begin{tabular}{|c|c|c|c|c|} \hline \(\alpha\) & Train Acc. & Test Acc. & Pruning Ratio & Train Acc. a.p. & Test Acc. a.p. \\ \hline \hline no noise & 0.9514 & 0.5636 & 25.1 & 0.8289 & 0.5214 \\ \hline
1.75 & 0.9503 & 0.5626 & 21.74 & 0.8196 & 0.52 \\ \hline
1.9 & 0.95 & 0.5755 & 16.56 & 0.8870 & 0.5641 \\ \hline \end{tabular}
\end{table}
Table 6: CIFAR10, Type-I noise, \(n=5\)K until reaching 95% training accuracy.