Emergence of heavy tails in homogenized stochastic gradient descent
Authors: Zhe Jiao
Martin Keller-Ressel
Venue: NeurIPS 2024 poster (2024)
Keywords: stochastic gradient descent
heavy tails
gradient noise
Pearson diffusion
tail index
Primary area: optimization
TL;DR: Heavy tailed parameter distributions can emerge from locally Gaussian gradient noise, as we show both theoretically and empirically.

Abstract: It has repeatedly been observed that loss minimization by stochastic gradient descent (SGD) leads to heavy-tailed distributions of neural network parameters. Here, we analyze a continuous diffusion approximation of SGD, called homogenized stochastic gradient descent (hSGD), and show in a regularized linear regression framework that it leads to an asymptotically heavy-tailed parameter distribution, even though local gradient noise is Gaussian. We give explicit upper and lower bounds on the tail-index of the resulting parameter distribution and validate these bounds in numerical experiments. Moreover, the explicit form of these bounds enables us to quantify the interplay between optimization hyperparameters and the tail-index. Doing so, we contribute to the ongoing discussion on links between heavy tails and the generalization performance of neural networks as well as the ability of SGD to avoid suboptimal local minima.

Emergence of heavy tails in homogenized stochastic gradient descent
Zhe Jiao School of Mathematics and Statistics Northwestern Polytechnical University Xi'an 710129, China zjiao@nspu. edu. cn
Martin Keller-Ressel"
Institute of Mathematical Stochastics
Technische Universität Dresden
01217 Dresden, Germany
hartin.kellen ressel ressel@tu-dresseeeeeeeeeeeeeeeee @eteeeeeedeee...eeee
Abstract
It has repeatedly been observed that loss minimization by stochastic gradient de- scent (SGD) leads to heavy-tailed distributions of neural network parameters. Here, we analyze continuous diffusion approximation of SGD, called homogenized stochastic gradient descent, and show in regularized linear regression framework that it leads to asymptotically heavy-tailed parameter distribution, even though local gradient noise Gaussian. We give explicit upper and lower bounds on the tail-index of the resulting parameter distribution and validate these bounds in numerical experiments. Moreover, the explicit form of these bounds enables us to quantify the interplay between optimization hyperparameters and the tail-index. Doing so, we contribute to the ongoing discussion on links between heavy tails and the generalization performance of neural networks well as the ability of SGD avoid suboptimal local minima.
Introduction
Stochastic gradient descent (SGD) is the cornerstone of optimization in modern deep learning (cf. (Bottou et al.) (0188). In contrast to deterministic methods, it introduces stochasticity to the optimization procedure and therefore has be analyzed from a probabilistic viewpoint. For instance, it has been observed by |Mattn and Mahoney (2019). Simsekli et al. 2019). Hodgkinson and Mahoney [02TT. GGurbuzbalaban al. [2021] and others, that the distributions of neural network parameters under loss minimization by SGD are typically heavy-tailed. This heavy-tailed behavior has been linked to the generalization performance of neural networks: (Simsekli al. 2019) give evidence that the extreme realizations of heavy-tailed random variables allows SGD to escape local minima of [202T] argue for negative correlation between the parameter distributions 's tail-index and the network's generalization performance| For these reasons, is important to understand the origin and effects of heavy-tailed behavior of neural network parameters in SGD. An important step in this direction has been taken in (Gurbuzbalaban et al. [222]] where the tail behavior of SGD iterates is characterized in dependence on optimization parameters, dimension and Hessian curvature at the loss minimum. One limitation of (Gurhuzbalabaa hababan et al.) 2021
the loss landscape, and Hodgkinson and Mahoney
that this link is described only qualitatively, but not quantitatively. Here, we provide an alternative approach through analyzing homogenized stochastic gradient descent, diffusion approximation of SGD introduced [Paquette et al., [022bb Mori et al. 20022.. Leveraging Itô calculus for diffusion processes, we are able to provide more precise bounds and estimates of the tail behavior of SGD iterates, which we subsequently validate numerical experiments.
"Center for scalable data analytics and artificial intelligence (ScaDS.ai). Leipzig/Dresden, Germany. "The tail-index a quantitative measure heaviness of tails; see Section 2.4 See also [Raj et al. (2023) Benjamin and Simsekli 2024) for further results on the connection between generalization and heavy tails.
with smaller tail index indicating increased
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

1.1
Our contribution
Our contribution to the analysis of heavy-tailed phenomena in SGD can be summarized as follows:
We introduce a new method, namely comparison results in convex stochastic order for homogenized stochastic gradient descent. These comparison results, given in Section allow us to link SGD to the well-studied class of Pearson Diffussioss (cf. [Forman and Sørensen 2008]) and then to obtain bounds for their tail-index.
Contrary to Gurbuzbalaban et al., 202T], who describe the tail-index only implicitly (ob- serving phase-transitions between different regimes) our tail-index bounds are fully explicit. Moreover, their explicit form is validated in numerical experiments in Section 4
Our results suggest (skew) Student---distributie neural networks under SGD, in contrast to the earlier work of [Gurbuzbalaban al. 2021 where a-stable distributions have been suggested. This proposal is validated by numerical experiments and statistical test in Section 4
as surrogate for parameter distributions in
Finally, results challenge the claim that the 'observed heavy-tailed behavior of SGD in practice camnot be accurately represented by an SDE driven by a Brownian motion' put forward in (Simsekli al., 2020J. Our modeling approach is based on hSGD driven by Brownian motion which asymptotically exhibits heavy-tailed behavior with a tail-index that, in experiments, closely matches the empirical tail index of SGD iterates real data.
SDE
2 Background
2.1 Empirical risk minimization
The general framework for training deep neural networks is to solve the problem of empirical risk minimization
min aERd
L(x)
(z)
(ERM)
72
where L, denotes the loss induced by the data point a, E Rd with label/response b, E I, given the model's parameter vector E Idd For our theoretical and numerical analysis of heavy-tailed phenomena we focus on the specific case of regularized linear regression. Hence, as in Guubbuzbalaban et al. 2021 we assume a quadratic structure of (ar)). setting
(x(x) (a, 6.)²
Including a regularization term weighted by d 2 0, we arrive at the objective function
8 2
Σ
8 |
(z) L(x)
(8-ERM)
2n
which is the loss function of ridge regression (cf. [Hastic et al. 2009 D. We arrange the training
data into design matrix A ga and label vector b E R", whose i-th row are given by a, and 6;
respectively, allowing the write (-ERM) as s
1
(x² = - Ar 612
|
2n
2n
with gradient given by (z) = 3 (AT(Ar
(Ar - b) + 6z).
2.2 Stochastic gradient descent
The standard approach solve the problem of empirical risk minimization in deep learning is to use stochastic gradient descent (SGD) or any of its generalizations involving momentum, adaptive learning rates, gradient rescaling, etc. (cf. [Goodfellow et al. 2016, 20 Bottou al. 2018)). As first step, we consider plain SGD with constant learning rate 7, which can be written in recursive form as
Tb+1 Ik
V (Ix),
(SGD)

---

where VL (zx) =
B Eier, L (x) and S2 is batch of size B >> sampled uniformly and independently from {1, 11,,,., n). It will be convenient to rewrite (SGD) as
2k+1 = Th VV + yE (x));
(1)
where the gradient noise is given by
E(Tx) = - L (zx) vL(zz)].
(2)
Note that the gradient noise is unbiased (i.e. [x(x)) 0) with covariance matrix given by
C(x) = (<<))=\((()))(
1 n E=1
VL(()VVL(())
VL(x)VL(x))
The theoretical properties of SGD can now either analysed directly through the stochastic re- currence (T) (cf. [Bottou et al. 2018)) or through continuous diffusion approximation, known in the general case as stochastie modified equation, cf. [Mandt al.) 2016 Li et al., [017]. This approximation is obtained by recognizing ① as the Euler-Maruyama approximation (in the small learning-rate regime) of the stochastic differential equation (SDE)
dX, - (Xt)dt + VV C(X))dW,
(SME)
driven by d-dimensional Brownian motion (W)) ef. Thm. in [Li [Li al. further simplification is to assume that the covariance matrix C(x) is constant, yielding the Ornstein- Uhlenbeck- caannbbekkaprooxmmatiin (also known as Langevin equation) of SGD, cf. [Mandt al. 2016 Li
2017 A common
ct al. 2017].
2.3 Homogenized Stochastic Gradient Descent
Our analysis of SGD is based homogenized stochastic gradient descent (hSGD), introduced concurrently in [Paquette al. [202aa] and [Mori et al. 2022], which is another approximation of (SME). In contrast to the Ornstein- Ormsten-Uhllnbeect fhlenbeck-approxiieg noise is assumedd constant, hSGD uses the more elaborate 'decoupling approximation"
where the covariance matrix of gradient
C(x)
2
2
Lz)
B
see [Paquette et al. 2022a and Mori et al. 2022 for a derivation. Hence, in our notation, hSGD for penalized empirical risk minimization is given by
dx, = = + V [(xx)V==((x)dd
(hSGD)
the regime where n and d are simultaneously large, and under certain assumptions on the distribu- tion of the data A and b, [Paquette al. 2022a| provide approximation guarantees of the following form: For any given T 0 and D 0, there is a > 0, such that
P sup 0SETT
R( R((((n)) R(X,) d d/ S Cdd
(3)
for quadratic statistics R. Rdd + It and when n 2 d' for some > O; cf. Thm. 1.3 in [Paquette al. 2022aa for details. Further empirical evidence for the approximation quality of hSGD with respect to SGD can is also given in [Paquette et al. [2022a] Mori et al. 2022], altogether providing a sufficient basis for analyzing the properties of SGD through hSGD.
Furthermore, the stochastic differential equation (hSGD) can be simplified by using the reduced singular value decomposition (SVD) of the design matrix A. In detail, let rank(AA) & d, and let A = PΣQ be the reduced SVD of A, where Q is d-by-r and satisfies Q QTQ I,, P is n--b-rr and satisfies p I,, and
= diyg(Ay}.
> Ao >
X,
the diagonal matrix of non-zero singular values A. We distinguish the following two cases of hSGD:
3 Full derivation given Supplement A.1
"We remark that Paquette et al. 2022a assume a batch size of B = 1; the derivation of Mori et al. 2022
however, does not restrict B.

---

Underparametrized hSGD: Ar = b has no exact solution,
Overparametrized hSGD: Ax has an exact solution,
and impose the following assumption:
Assumption 2.1. In the overparametrized case, we require ó > O, i.e. the loss function must be regularized.
It is easily verified that æ, QE-iQTpp b is the unique global minimum of the unregularized loss in the underparametrized case and the global minimum of smallest norm in the overparametrized case.
We set Y (== Q Xx Q æ, and obtain the following system of SDE for the 'centered principal components' (Y YJ" of (SSGD)
dY; =- [( +6) Y -das] dt + Ary
1
Σ (2 + dBj
(4)
n
B
with
a a=
= (a)aa
8
and (B2) r-dimensional Brownian motion, obtained as an orthogonal transformation B, Q W. of the d-dimensional Brownian motion (W))-20 Note that PP b the projection of onto the column space of A. Thus, in the overparametrized case, PP the underparametrized case PP b * b and hence 3 > 0. Here, our main objective is to use (hSGD) to study the distributional properties, in particular the tail behavior, of SGD iterates.
and hence 3 O, whereas in
2.4 Heavy-Tailed Distributions
We collect some relevant definitions related to heavy-tailed distributions and their tail index (cf. [Resnick] 2007 Foss et al. 201T)).
Definition 2.2 (See Def. 1.1 in Foss et al. [201]]. A distribution function F(z) is said to be heavy-tailed (at the right end) if and only
1 1- F(2)
lim sup
oo, for all > 0.
-
2
real-valued random variable said be heavy-tailed if distribution function is heavy-tailed.
Definition 2.3. An Rd valued random vector is heavy-tailed if af is heavy-tailed for some vector E gd-1 (u E Rd |u| = =1.
Definition 2.4. The tail-index of an valued random vector X is defined as
= sup (p 2 B[| oc} [0, oo).
In particular, finite tail-index oc implies heavy-tailedness of X, and lower values of 1) signify increased heaviness of tails and more extremal behavior. tail index of 7 2, for example, implies infinite variance and < implies non-existence of even the mean of X. Examples of heavy- tailed distributions are the lognormal distribution, the Studenn---distiibutionn the Pareto (power-law) distribution, and a-stable distributions.
Finally, introduce definition related the asymptotic behavior of stochastic processes.
Definition 2.5. Let X (Xt)ı20 be stochastic process. The asymptotic tail-inder of X is defined
as
= (up 2 0: lim [(P) < oo)-
(5)
2-+00
Fuull derivation given Supplement A.2

---

2.5 Pearson Diffusions
To analyze its tail behavior, we perform a further rescaling of 4 by setting, for i (I,...,r).
z - { (a)))(
B = 0,
nAglogl
β = 0,
{
0,
3 = 0,
d VD
Yi
B 0,
F4 =
B 0,
x =
1, 3 > 0,
(B(X++0)
(6)
2 (> 8) 0
0,
and 6; 2n (2 + +5)
> 0.
This recasts the system
4 to
dz, 0 p:)dt + (0 (| + x)dB;;
with 2 2 = E. (Z)) These SDEs now have clear structural resemblance the system of independent one-dimensional SDEs
=2;= pi)dt + V 22,00, + x)dB;
(8)
with the only difference given by the coupling of 7 through the Zz -temr in the diffusion coeffi- cient [ The components of (8) are independent Pearson diffasions. Pearson diffusions are a flexible class of SDEs with unified theory for statistical inference and with stationary distributions known as Pearson distributions (cf. [Forman and Sørensen 2008)). In more detail, we obtain from [Forman and Sørensen 2008 the following properties:
Underparametrized hSGD (3 0): 2; is R-vuue and the stationary distribution of 2; is called Pearson's 's type IV distribution (or skew Student l-distribution) and has the unnormalized density
(u( x
1
u Von
+ 14
2
exp {niles arrctan
(vi. + ps)
with v; = o; 1
Overparametrized hSGD (3 = 0): 23 is co)-vv)alleed and the stationary distribution of 2; is called Pearson's 's type V distribution (or inverse Gamma distribution) and has the unnormalized density
pel2ss
(((u) x u - exp
(10)
u
with 2/ = -, +1 1.
In both cases, the stationary distribution is heavy-tailed with tail-inder given by vi, thus providing first connection between the SDF-approach and the emergence of heavy-tails. This connection will be quantified and made rigorous in Section
2.6 Comparison to existing literature
We compare our approach to studying the distributional properties of SGD through (hSGD) with other continuous-time upproximations: The wwwpee--uuhenbecc--pppiiiieeeee the additional assumption that the covariance matrix C(z) constant. Thus, gradient noise is approximated by Gaussian noise and the Gaussian noise enters (SME) additively. The o-stable of [Gurbuzbalaban
uses (SME) under
al.) 2021 instead presumes (based on generalized central limit theorem) that gradient noise is non- Gaussian and follows an o-stable law. Moreover, the noise assumed state-independent, and therefore also enters additively. In (hSGD), gradient noise is locally (i.e., conditionally on the state X₂) Gaussian, but state-dependent. The diffusion term in 7 reveals that the noise enters the SDE both multiplicatively (through the Zell-term) and additively (through the constant x). Moreover, X 0 in the overparametrized case, such that we observe a phase transition from a mix of additive and multiplicative noise in the underparametrized case, to purely mulitiplicative noise in the overparametrized case. We note that the importance of multiplicative noise in models of SGD dynamics is discussed in great detail in [Hodgkinson and Mahoney 2021 We provide summary of the comparison of these approaches in 1
"Existence and uniqueness of the solutions to these SDEs follows from standard results, cf. Karatzas and Shreve 2014 Ch. 5. Thm. 2.5] Oksendal 2013).
5

---

Table 1: Comparison of continuous-timg time models of SGD
Model
local gradient noise
global parameler distribution
tail-index
Gaussian OU
Gaussian additive
Gaussian
400
o-stable OU
Mon-Gaussian additive
Non-Gaussian (a-stable)
(0,2)
homogenized SGD
Gaussian additive/multiliicaiive
Non-Gaussian (with Student-t as proxy)
(1, 0c)
3 Theoretical results
3.1 Moment comparison
Our first result shows that the decoupled Pearson diffuusions (8 are lower bounds, in convex stochastic order D
to the coupled hSGD process (7). In particular, a comparison result for moments holds.
Theorem 3.1. For 1,,.. d, let (Zi) be the components of the rescaled (hSGD) from and 122 be the independent Pearson diffusion from (8). Then for any 3 0 and convex function
g I + R il holds that
[[g(2,)) 2 Elg 2;)
(11)
In particular this implies the ordering of p-moments
1 N 1
(12)
for all p 2 1.
Note that finiteness of the expectations does not need be assumed, i.e., the inequalities also hold if one of the expectations takes the value +o0. Comparison results for SDEs generally require two conditions (cf. [Bergenthum and Rüschendorf 2007 ): An ordering between the drift- and diffusion- coefficients of the two SDEs, and the -propagation-ff-ordke -property -properrryy for one of the processes. that the drift coefficients are identical, while the diffusion coefficients satisfy the required ordering condition (1x| + x) 2 20.6. + x) for any 2 E R". The propagation-of-orte property of 2 and the full proof of Theorem 3.1 are provided in Supplement A.3
Comparing (7) and (8),
3.2 Upper and lower bounds for the asymptotic tail index
Since the process (Z))220 a linear transformation of the hSGD process (X- is clear that the tail behaviour of their marginal distributions - in particular the finiteness of p-moments is identical. Hence, an application of Thm. [3.1 provides an upper bound on the asymptotic tail index of (hSGD):
Theorem 3.2. The asymptotic tail index 1 of (SSDD) has the upper bound
S n = BnB(A + +
(13)
711
Under conditions on the learning rate 7, a complementary lower bound can be derived from existing results on moment stability of SDEs, see Thm. 5.2 in [Li al. 2019) and Supplement(A.55 details:
Theorem 3.3. Suppose that the learning rale satisfies
2n (X3 + 8)
イ<ク=
X X
then the asymptotic tail index 17 of (SGDD) has the lower bound
2nB(X² +8)
Σm 1
N n, = 1+
(14)
711
X
3.3 Wasserstein convergence
Theorems 3.2 and 3.3 results the asymptotic tail index, raising the question how fast con-
vergence to the stationary distribution takes place. The next result shows that, under a suitable assumption the learning rate, convergence takes place exponentially fast in 2- Wasserstein distance:
See e.g. Shaked and Shanthikumar 2007

---

Theorem 3,4. Suppose that the learning rate satisfies
nB
X
7 95
2
X
+
i=1
Then the equation
X
nB
+ np/"
27
has a unique positive solution p. > 0, and the marginal distribution ne of the hSGD process X converges in 2- Wasssesstein distance W2 to its unique invariant distribution æ. Moreover, there exists C > O, such that
We( T) S Ce Tp-.
We remark that if the conditions of Theorem 3.4 are satisfied, then the asymptotic tail-index 1j is necessarily greater than two, such that second moments and in particular the 2-Wasserstein distance are well-defined and finite.
3.4 Discussion of theoretical results
We compare our results to Gurbuzbalaban et al. [2021]. who analyse the distributional properties of SGD directly through the stochastic recurrence (T) under the assumption of an isotropic Gaussian data distribution. In our setting, the data distribution is arbitrary, since all results are given conditional on the data matrix A. On the other hand, we analyse SGD only through its diffusion approximation hSSD rather than directly. However, in contrast to (Gurbuzbalaban et al.) [202]], we obtain the quantitutive and explicit tail-index bounds (13) and (14). whereas Gurbuzbalaban et al. [202] only
describe the tail index through an implicil equation and derive qualitative results its behaviour.
Parameter Dependency. Some interesting observations can be made when consider the dependency of 1) on several meta- vetaa-parmmeters of the stochastic gradient descent procedure:
Corollary 3.5. The upper and lower bounds of the tail-index are increasing in the regularization purameter and batch size B, and are decreasing in the learning rate 7y and the first singular value A of the data matrix A.
This result agrees with Theorem 4 in Gurbuzbalaban et al. 2021 obtained under the assumption of an isotropic data distribution a; ~ ((, olIa), in all aspects, except the dependency on dimension d. While Gurbuzbalaban et al. [222]] report decreasing dependency on d, our tail-index bounds do not explicitly depend on dimension d. Nevertheless, the two results can reconciled as follows: Under the assumptions in (Gurbuzbalaban et al. 2021], the data matrix A = (a.) is random with E(AT A) = LaLa. and the product matrix W == A A follows the so-called Wishart ensemble (cf. [Wishart 1928) ). Moreover, from Theorem 1.1 in Johnstone 2001] it follows that for large d the maximum eigenvalue of W is
(+++1) d nd
(+= +1
x 0²
d V
(15)
where the ratio --r Tracy-Widae Widom distribution of order 1 (cf. [Craig and Harold 1996)). From [15), we can calculate the average of X2 as
1 and the distribution function of the random variable v is the well-known
E [A = 0²(
Vr + 021-////000000
o'n vd)²
and X fluctuates around this expectation over a narrow region of width O(d)). Substituting Af by its expectation in (13) and (14) we now that 77- and 17* increase in both variance o² and d, consistent with Guurbuzbalaban et al. 2021].
Distributional properties. From Theorem 3.1 we see that the skew Student-t distribution provides an asymptotic lower bound in convex order for the marginal distribution hSGD. Empirically (see Section 4 we see that skewness is negligible and furthermore, that the Student-t-distribution not only provides a lower bound, but in fact a very good to the parameter distribution of SGD in general, surpassing the fit of the a-staele distribution proposed in [urbuzbalabaan et al. 2021]. For this reason, we propose to use the Student--ddisrributtin, rather than o-stlble distribution, as proxy for the parameter distribution in SGD.
7

---

Experiments
Based on the upper and lower bounds in Theorems 3.2 and 3.3 we present some experiments to illustrate the tail behavior of SGD and the factors influencing the tail index. The procedure of our experiments contains the following steps.
1. Given [data]6], we transform the data to be on a similar scale by the linear scaling
data min min (data)
A max [data] min (daaa)
2. Let K be the iteration number of SGD. We apply (SGD to solve (RM). The final state ØK RR is random vector.
3. Repeat the second step 1000 times for different initial points and obtain 1000 different samples of zg-
4. For further distributional analysis we project æ via y qi тK on the dominant direction, given by the first right singular vector qi of A. Then we utilize the 1000 samples to obtain the empirical complementary cumulative distribution function (ccdf) of y.
4.1 Datasets
Synthetic data. We first validate our results in the same synthetic setup used in (Gurbuzbalaban et al. 2021). All data points are drawn from isotropic Gaussian distributions, precisely, the i-th row of X Rxxd contains X Rd (O, Ta)- Then given Ted ~ (0, 37&) we draw the response vextor E Rº" with components 6, ~ (xxxx,)) We set the number of the synthetic data to be 2000 through our experiments.
Real data. In our second setup we conduct our experiments on the handwritten digits dataset from the Scikit-learn python package (cf. (Pedregosa al. 2011) using random feature model proposed in Rahiii and Recht 2007] and a three-layer neural network. The digits dataset contains n = 1797 images of handwritted digits in 8 x 8 pixel format. The pixels are stacked into vectors of length Wi = 82 = 64 resulting in a raw data matrix y E RRxxe and the class label h; = (0, 1, ...,,..999 is used response vector. For the random feature model, choose dimension and draw random weight matrix W E Reaxd having standard Gaussian entries. The feature matrix W E Raxd is given by
VW m
Z=
E RRnd
where (-) is rescaled ReLu activation function. The neural-network model uses 64 neurons in each hidden layer and sigmoid activation functions. The precise parameter values used for the figures are reported in Tables 4 and 5 in the supplement.
4.2 Empirical results
To verify the heavy-tailed behavior y as well as our tail indl- bounds from Theorems 3.2 and 3.3 and the distributional approximation suggested by (9), we use MLE-estimation to fit our centered data as
y mean (y) st(v).
where t(v) denotes a Student---distributiee with parameter and K a fitted scaling factor The QQ-plots in Figures 2 (a)-(c) show that the fiieentt--istributtion provides very good fit to the empirical data, validating our use Pearson diffusions to approximate SGD. comparison, it can be seen in Figure (d)- that the fitted o-stable distribution overestimates the heaviness of tails, in particular for the random feature model on real data. We complement these figures by Kolmogorov- Smirnov tests (cf. Chapter 4.4 in [Corder and Foreman, 2014)) testing for the goodness-of-ff of the Student---distribution and the o-stable distribution respectively: see Tables []3 detailed results. In all three settings, the hypothesis of Student---distribution is accepted, while the a-stable distribution is rejected.
'Eq. 9 actually implies skew Student-f-distribution but we use symmetric one to avoid the estimation of an additional parameter μ.

---

Quanches of
Quaettes
Quentres
Quaritles distrriuution
Quantiles disttribbt
(a)
(b)
(c)
0.1
0.4-
Quamies of
Owantiees of
Quandiee
0.
-12
62
-55
Ouantiles of o-steble distr
-22
-13 C1
esstable distibution
Quantiees o-stable dittibution
-11
02
(d)
(e)
(f)
105
30P
Fxg
10:3
logF(x)
10
log
10
10n'1
t(n')
22n4 t/n-)
30a4
10"0
log
log
log
g
(h)
Figure Results for linear regression/random feature model trained on datasets X. V, and Z. (c)-(c) Quantile- Quantill plots of fitted
against empirical SGD iterates; (d)- (f) countile-Quantile plots of fitted a-stable distribution against empirical SGD iterates; (g)-(i) Comparison between ecdf of empirical data and Student-f-distributiio parameterized by upper tail-index bound 17" and lower bound !/--
Moreover, in Figure (g)-(i) plot (in doubly logarithmic coordinates) the empirical cedf of the SGD iterates z, together with the cedf of the Student---diisriibuiion parametrized by our lower and upper bound тІ- and 17", between upper and lower bound, validating Theorems 3.2 and 3.3 Additionally, we once more
be seen that the empirical cefd, including its tail, is nicely sandwiched
confirm the heavy-tailed behavior of SGD iterates already observed in [Simsekli et al. 2019
Hodgkinson and Mahoney] 2021 Gurbuzbalaban et al. 2021
Table 2: Kolmogorov-Smimov test of theoretical distributions against observed SGD iterates of the linear regression/random feature model. The null hypothesis Hg that two distributions identical, the alternative H1 is that they are not identical.
Distribution
Dataset
In Fig.
K-S statistic
p-vulue
decision
Student-f
X
(a)
0.029
0.795 > 0.05
accept Ho
Student-f
y
(b)
0.039
0.433 > 0.05
accept Ho
Student-4
(c)
0.030
0.759 > 0.05
accept Hg
a-stable
X
(d)
0.084
0.002 < 0.05
reject Ho
a-stable
y
(e)
0.067
0.022 0.05
reject Ho
a-stable
2
(f)
0.070
0.015 < 0.05
reject Ho

---

Quantiies of
Quantiee
Quenties
Quantiess distribbttion
Quantiles Eddtributton (b)
Quarchee distribbttoo
(a)
(c)
Quantites of
Quanites
Qhuetiee
Quanties a-bable dietnbuttinn
Quantiee o-stable dieribution
Querles of a-enate disrtbuttonn
(d)
(e)
(f)
Figure 2: Results for three-layer neural network model trained on datasets X, D and Z. (a)-(c) Quantile-uuantile plots of fitted Student-t-distributiinn against empirical SGD iterates of second layer; (f)-(f) Quantile- Quantile-uanntie plots of fitted q-stable distribution against empirical SGD iterates of second layer.
Table 3: Kolmogorov-Smirnox test of theoretical distributions against observed SGD iterates from the second layer of the three-layer neural network model. The null hypothesis Ho is that two distributions identical, the alternative H1 is that they are identical.
Distribution
Dataset
In Fig.
K-S statistic
p-value
decision
Student-t
X
(a)
0.011
0.208 > 0.05
accept Hg
Student-t
y
(b)
0.061
0.871 > 0.05
accept Hn
Student-t
2
(c)
0.060
0.883 > 0.05
accept Hu
a-stable
X
(d)
0.078
0.001 0.05
reject Ho
a-stable
y
(e)
0.084
0.035 < 0.05
reject Ho
a-stable
2
(f)
0.070
0.015 0.05
reject Ho
Conclusion and Limitations
This study delves into the phenomenon of heavy tails emerging in the parameters of homogenized stochastic gradient descent applied regularized linear regression. By establishing connection between hSGD and Pearson diffusions, we have been able to derive both explicit upper and lower bounds for the tail index of the parameter distribution. Our results reveal that heavy tails can emerge even in the presence of locally Gaussian gradient noise and provide insights into the influence of optimization hyperparameters on the tail index. However, it is essential recognize that our analysis relies on the approximation of SGD by hSGD and is limited to the setting of linear regression with quadratic loss. Another limitation (see (4h is that the tail-index hSGD lower-bounded by one, and thus hGSD can not be used to analyse 'ultra-heavy tails' with tail-index и < 1. Future work will be devoted to extending our results to non-linear models and to providing tighter connection between the behaviour of hSGD and the discrete- time SGD algorithm.
10

---

Acknowledgments and Disclosure of Funding
Zhe Jiao's research is supported by the National Natural Science Foundation of China (12272297). Martin Keller-Ressel acknowledges support from the Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI) Lepizig/Dresden, Germany.
References
J. Anderson. A secular equation for the eigenvalues of diagonal matrix perturbation. Linear algebra and its applications, 246:49-70, 1996.
D. Azagra. Global and fine approximation of convex functions. Proceedings of the London Mathe- matical Society, 107(4):799-822 824, 2013.
Beesack. Comparison theorems and integral inequalities for Volterra integral equations. Proceed- ings of the American Mathematical Society, 20(1):61-66, 1969.
D. Benjamin and U. Simsekli. Generalization bounds for heavy-tailed SDEs through the fractional Fokker-Plann Planck equation. ICML, 2024.
Bergenthum and L. Rüschendorf. Comparison of semimartingales and Lévy processes, The Annals of Probability, 35(1):228 254, 2007.
L. Bottou, E. F. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311, 2018.
G.W. Corder and D.I. Foreman. Nonparametric Statistics: A Step-by-Stey Approach. Wiley, 2014.
A. Craig and W. Harold. On orthogonal and symplectic matrix ensembles. Communications in Mathematical Physics, 177:727-754, 1996.
C. Cuchiero, M. Keller-Ressel, and J. Teichmann. Polynomial processes and their applications to mathematical finance. Finance and Stochastics, 16:711-740, 2012.
D. Filipović and M. Larsson. Polynomial diffusions and applications finance. Finance and Stochastics, 20:931-9722 2016.
J. Forman and M. Sørensen. The Pearson diffusions: class of statistically tractable diffusion processes. Scandinavian Journal of Statistics, 35:438-466 2008.
S. Foss, D. Korshunov, S. Zachary, et al. An introduction to heavy-tailed and subexponential distributions, volume 6. Springer, 2011.
M. Friesen, Jin, and B. Rüdiger. Stochastic equation and exponential ergodicity in Wasserstein distances for affine processes. The Annals of Applied Probability, 30(5):2165-2195 2020.
I. Goodfellow, Y. Bengio, and A. Courville. Deep learning. MIT Press, 2016.
M. Gurbuzbalaban, U. Simsekli, and L. Zhu. The heavy-tail phenomenon in SGD. In International Conference on Machine Learning, pages 3964-3975, 2021.
Hastie, R. Tibshirani, and Friedman. The Elements of Statistical Learning. Springer, 2009.
Hiriart-Urruty and C. Lemaréchal. Convex analysis and minimization algorithms I: Fundamentals. Springer, 1996.
I. Hodgkinson and M. Mahoney. Multiplicative noise and heavy tails in stochastic optimization. In International Conference Machine Learning, pages
2021.
R. Horn and Johnson. Matrix analysis. Cambridge university press, 2012.
I. M. Johnstone. On the distribution of the largest eigenvalue principal components analysis. The Annals of Statistics, 29(2):295-327, 2001.
I. Karatzas and S. Shreve. Brownian motion and stochastic calculus. Springer, 2012.
11

---

I. Karatzas and S. Shreve. Brownian motion and stochastic calculus, volume 113, springer, 2014.
P. E. Kloeden and E. Platen. Numerical Solution of Stochastic Differential Equations. Springer, 1999.
Q. Li, I. Cheng, and W. E. Stochastic modified equations and adaptive stochastic gradient algorithms. In International Conference on Machine Learning, pages 2101-2110. PMLR, 2017.
X. Li, X. Mao, and G. Yin. Explicit numerical approximations for stochastic differential equations in finite and infinite horizons: truncation methods, convergence in p-th moment and stability. IMA journal of Numerical Analysis, 39:847-892, 2019.
S. Mandt, M. Hoffman, and D. A. Blei. A variational analysis of stochastic gradient algorithms. In International Conference on Learning Representations, 2016.
C. Martin and M. Mahoney. Traditional and heavy tailed self regularization in neural network models. In International Conference on Machine Learning, pages 4284-4293, 2019.
T. Mori, Z. Li, K. Liu, and M. Ueda. Power-law escape rate of SGD. In International Conference Machine Learning, pages 15959-15975, 2022.
A. Müller and D. Stoyan. Comparison Methods for Stochastic Models and Risks. Wiley, 2002.
B. Oksendal. Stochastic differential equations: an introduction with applications. Springer Science
& Business Media, 2013.
C. Paquette, E. Paquette, B. Adlam, and Pennington. Homogenization of SGD in high-dimensions: Exact dynamics and generalization properties. Advances in Neural Information Processing Systems, 35:35984-35999, 2022a.
C. Paquette, E. Paquette, B. Adlam, and J. Pennington. Implicit regularization or implicit condi- tioning? exact risk trajectories of SGD in high dimensions. Advances in Neural Information Processing Systems, 35:35984-3599 -59999, 2022b.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, Thirion B., O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and É. Duchesnay. Scikit-learn: Machine learning in python. Journal of Machine Learning Research, 12(85):2825-2830, 2011.
A. Rahimi and B. Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, 2007.
A. Raj, L. Zhu, M. Gurbuzhalaban, and U. Simsekli. Algorithmic stability of heavy-tailed SGD with general loss functions. In International Conference on Machine Learning, pages 28578-28597 PMLR, 2023.
I. Resnick. Heavy-tail phenomena: probabilistic and statistical modeling. Springer, 2007.
M. Shaked and G. Shanthikumar. Stochastic orders. Springer, 2007.
U. Simsckli, L. Sagun, and M. Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning, pages 5287-5837, 2019.
U. Simsekli, O. Sener, G. Deligiannidis, and M. A. Erdogdu. Hausdorff dimension, heavy tails, and generalization in neural networks. In Advances in Neural Information Processing Systems, pages 1138-5151, 2020.
V. Strassen. The existence probability measures with given marginals. The Annals of Mathematical Staristics, 36:432-433 1965.
J. Wishart. The generalized product moment distribution in samples from normal multivariate population. Biometrika, 20A(1/2):32-52, 1928.
12

---

A Supplementary material
A.1 Derivation of covariance matrix
Consider the minibatch stochastic gradient
(=*(x)= B
(()
Σ Lz)z)
1
Σ VL((z),
B
JES
iESt
where B is the batchsize and the random set S2 .......
.i} consists of B independently nn.
identically distributed random integers sampled uniformly from
Let (L( + Eien, (L. It can be rewritten as
" Σ :=1
vi+(2)
VL,()))
where the random variable = if I-multille i's sampled in Stg with 0 < 1 < B. The probability
of s; = is given by the multinomial distribution (p(s; = 1) = (H)) have
1 B- Moreover, we
13
B n²
B(B 1)
Bn + B(B 1)
[ss
E[stsy]
[[sss:]
n²
n²
We can also compute
[[Vin(+)] = B
Σ
V Li (T) v
(16)
1=1
and
E
(Zx)
E
LL,(t) 818j
(zy()) [[(s8)))
B
B
B(B B(B-1) 1)
VL(())V,(())
B
n²
(17)
Bn B(B 1)
B(B B(B-1) 1)
VL(C)VL((>)))
n²
n²
B 1 1
B n VL
Combining (6 with gives
C(x) = E
Fz( (x) v(())|( - [[())]+}
E [V V 1 [
Vixa<) - V
B VL(O)VL(O) + [LOOVV(00T
1
A.2 Transformation of hSGD
By multiplying both sides of hSGD by Q we obtain
d x.) = - VI.0 TV. X dt + TT /
2
B (xx.) dw,
(18)
(AX, =-70- [TTXX - 6)
oxe dt ?
1
AXx - AdW.
n B
13

---

Due to
Q' [A" (AX, 6) +0XI = (20² +1,) Q EP
and
AA, - 612 = - 1IQTX, - Q"VATA==Q"
18 can be reformulated as
d(Q' T X,) = 2 81,) Q X, EP b) dt
n
(19)
? 1
n EQTX, -T (Q Wi).
Let := QTW,, Wi, which an r-dimensional Brownian motion, due to Q _ Q 1,. From 19
follows that Y = Q Xx Q x+ satisfies
n [(E² + 51,) Yo a] dt + ? n Y E2Y, + BJEAB
dY,
(20)
with
a : - B b==b'aT, - PP 20
Reading
component by component, we obtain
A.3
Proof of Theorem
We write the SDEs and 8 in the form
dzp by (Z) dt (Z))dB - bx())d (2;
where
6((2,) = -0; pi), 20;0
and = + x).
While the drift coefficients are identical, the diffusion coefficients satisfy the inequality (2(2) 2 (2) for all 2 E R" and 1, ,,...,r. r. Note that all coefficients are Lipschitz continuous and of bounded growth, such that the standard assumptions for uniqueness and existence of strong SDE solutions are satisfied. Moreover, the SDEs for 2; are decoupled and each is Markov diffusion with generator given by
bz)0,, + ōx(x)²
2 ONZ.
where x denotes the scalar state variable of 2i, Let (RR denote the subspace of C -funnctions for which all derivatives up to order have polynomial growth. Suppose that C/, (IR). From Theorem 4.8.6 in [Kloeden and Platen 1999 the backward functional
xt,,x) Eig (lg(22 x], [
satisfies the backward Kolmogorov equation
0,9.(t.)) (t, =0 t<T, (T = g(z).
(21)
with å,g, continuous and Gt, E C*,, for each & E [0, We now provide a Lemma showing the propagation-of ofrdrerr property of Ž:
Lemma A.1. Ifg E C|((R) convex, so is Ge(t, for all E [0, 7] and i = 1,...,
Proof. For better readability we suppress the superscript and subscript in the SDE
dži = b, (2;))tt + à. (Z():
14

---

and consider its Euler- Maler-maruyama approximation
2k Z.., + +b(2,,,,)tt + 8 ( -B,)
with 1 T-I + L 10,1, ... K} and Alj _x- = A. Using Theorem 9.7.4 in [Kloeden
and Platen [999] we have
2x(t,z) (lg(( x) - -(t,,), te [0,7].
(22)
Let A be transition operator given by
AS S Ab(S) WSSW
with W (0) We will show that A satisfies the convex-ordering property
Bh(Si) EA(S2) EA(AS)) & (4(()))
(23)
for any convex function h())- Let S1, S2 be random vectors which independent of W and satisfy ()) & () Due to Strassen's theorem in [Strassen 1965), we can also assume that E(Sa Si) Sj. follows from conditional Jensen's 's inequality that
Eh(AA))) RA(S2 2M (S2)WW
= ES + ( + (S:)))
(24)
{[, (5)) A + ((((()))))))
= E[M(S + AMS)) ((((S))))))
Here, the linearity of 6()) implies B(b(S2)[s)) = 6(8)). Note that the function f(z) v x²2 x
convex. Similarly, (-) is convex. Using conditional Jensen's inequality again gives
((1) ((G(S)))S)) ((B(S2|S)) 6(1).
(25)
Due to
S1 + B((()))))) ~ [(,, S + Ab(S)) + W ~ NN,
with = |BS) + (S))) by Theorem 3.4.7 in Müller and Stoyan 2002].
25 implies that
[S + Ab(S)) + ((((S))(S))W) > E[ + (MS)) + (() ())))))] EA(SS)).
Combined with 24 we have proved the convex-ordering property 23
By the Markov property of the Euler-Maruyama approximation we have
(x(1,x) (A x)].
Let Z be Bernoulli random variable which takes the value 21 RR with probability p (0, 1) and the value 21 E IR with probability - Then E(Z) = p2d + (1 - 22.2. Then we have
(E())) = h(p21 + (1 - 2))2) < ph(2) (21) + (1 - (22(22) Eh(Z).
Using the convex-ordering property 23 of the operator we obtain
(t (t p21 + (1 p222) = (x, (t) E & B[g(A*2) Gx Z)
(26)
due to g is convex. Take expectation on both sides of 26 gives
(x p21 + (1 - 2)22) < [t Z)] = pР (t, 21) + +1 (t,
which means 9x (L,-) is convex. The approximation property 22 implies the convexity of (l,,))
Next, we need technical result that shows that each process Gi(z, Zi)eeoo of 'class (D)
Lemma A.2. For each 1, the process (t, (0)77 is of class (D)-
A stochastic process (Xt)rer is of class (D), if the set (X, is 4-valued stopping time) is uniformly
integrable (cf. Definition 4.8 in Karatzas and Shreve 2012
15

---

Proof. Since the solution to (8) is polynomial process (see example 3.6 in Cucchiero et al. 2012 follows from Theorem 3.1 in
Filipovié and Larsson 2016 that
Gi(L 22) - Elg 22 ) 12; - 2
where
0
x 1gi
0
2go
3 x 2gi
0
0 0 2 (g2 + gs)
3go
3 (g2 + 2gs)
p(p - 1)gi
Pgo
0
82 + (p 1)gs)
with
0ptin
81 = -000x
E2 0,,
83 0,0i
and P(Z))= (0,1, Z,, (2))) (. (Z Then there a constant Or that depends on T such that
(1, 21) < Cr +1 (2)1)).
Let Tn be a localizing sequence for ((t, yc). Then we have
[ A Tu. Zinr 31 & Cr(1 ZiAra PT),
which implies
g A Tni Z EAT )1 & Cr(11+ + ZiAT (22))
(27)
Taking Fo-condition both sides of
(7 gives
E (1 Ta, ZeA
)1
& Cr
(1 E Z ZATA 22)
Cr 1+
sup ZeAta (pp
< CTe
Here, the last inequality holds based on Lemma 2.17 in Cuchiero al. 2012). Thus, we complete the proof of this lemma.
We are now prepared to give the proof of Theorem 3.1
Proof. Let g be convex function and assume for now that g CR)... Define the local martingale
L = 1' 0,Gr(s, (Z).
Using Itô's formula the first step and (21 in the second step, we have
G(tt, 9,(0,
L. 0s Z:)dds f (b:(Z))a, e.(Z)) 0zz) Gi(s, Z:)ds L
/' (, Z.)ds {'' (bi(Z))0,+ + o 0wz) gi(s, Zt)ds L,
(28)
2 / [o7(2.)
-2((2))=?((2)))))) 6?(2)))0. 9. Z)dds + Lr.
By (.((,.) E (TR) and Lemma A.I we obtain I. > for all i e (1,..., d). Thus, due to the ordering of of and 0² the first term in the right hand side of (28 is nonnegative. Since L is
16

---

continuous local martingale with zero initial data, it follows that Gi Z.) (0 Zo) is local submartingale.
Let Tu be a localizing sequence for (t, Zz). For all E [o, T), we have
Gi(t A ZeAr.) - (0, Zo)
0... (t, Z,) G0
(29)
Since Gi(1, 24) is a process of class (D) or locally I," 1.--bounded, > 1, it follows that Gi(l A Tni Zer, (0, Zo) is uniformly integrable. Combining almost-sure convergence with the uni- formly integrable property, it implies that the convergence (29) also takes place in L', and therefore, (t, 2,) (0, Zo) is submartingale. By taking expectations both sides of (88 and using the fact that Zo Zo. we obtain the comparison result
Eg(ET) = (T, 23) > g(o, zb) = E[g((;))
(30)
for all convex g (R).
Now let g be arbitrary convex function R. From Theorem 3.1.4 in (Hiriart-Umutty and Lemaréchal 1996] we can find, for each n E N a convex Lipschitz function 9h. such that 9n in [-n, vi and
In S 9 R
\ n2 n]. By [Azagra 2013 we can find further smooth convex functions 9r. CLi (R) such that DT A/4 S In S In on all of I.. It follows that the sequence Jn converges pointwise to from below. We observe that Lip (IR) C (R.) and equation (TT) now follows from (30) by monotone
convergence. Finally, equation
12
follows by choosing the convex function g(z;) |2...
A.4 Proof of Theorem 3.2 (upper bound)
From X, QY + 3.. the triangle inequality and the unitary invariance of the Euclidean norm, it follows that [V]| & [xl
+ [.a. Thus, we have
gm/2
E
B| < B(P) < 2" (E[ (x,1))
(31)
X
Now, p vi. By Theorem 3.1
Fatou's 's Lemma, and the properties of the distribution
(0
lim sup E 7
|
lim inf B[ [P)
lim inf E 11222 2 TE| 2
t-000
t-
Together with 31) this implies that also
sup B[[X,
t-+00
and it follows from (5) that the tail index satisfies 17 S p for all p > v1. Finally, the parameter v1 in
the limit distribution of 2! is given by 11 = 1 1 oe where Φi can be found (6). Thus, we obtain
Theorem B.2
A.5
Proof of Theorem 3.3 (lower bound)
For better readability, we rewrite (hSG)) in the form
dX. = F(X,) + G(X))dB
(32)
with
F(X)= = - - -) ox,], G(X,) = 7 / |Xx - ATAA
Our goal is to show that
2x T F2x) (G(]) - (2- 200-p)=2TGG G()) < -Ci (1+ + (x|2)
lim sup +2/
(33)
x
for all p (0, 7z), where C₁ is positive constant and
7 = 2n(27 nz)
Dd
Σi=
X?
> 0.
741
X
17

---

Under condition (33) it follows directly from Theorem 5.2 in [i et al. 2019 that the solution X, of the SDE (2 satisfies
sup
||X,
12 & C2
cE0000
with C2 a positive constant, showing Theorem 3.3 In order to show (33) let
x A Ax
M(x)
x E Rd (0)
x
denote the Rayleigh-quotient of A A. From Chapter I in [Horn and Johnson 2012 we have that the range of (x) equal the line segment [AZ. Ai), i.e.,
(M(x): : x Rd [0}} = [AE, A
(34)
Evaluating the condition 33 we have
(1 + [x]3) 2x F(z)]
|x|1
(1 [x|²) 1-22 x2 T [A"(Ar b) + 8x]}
|x
(1 + [x] 1-2 (AT A + 5I,)x +2, A27xTATT)
|x]4
TAATTAAAAA A + 81,)a
2
+ 81,)x
2 +
{21 TAT
+
|x|
x
x
and
(1 |+|
(2 p)x)+
|
(1+ (x|²)
Ar A
(2 p) . 2 Ví A
xx/4
(1 + (o 2 Ax 812
AT
(2 2)
Ax b/2 T 2
|
Ar
6131
AT A
Ax
6/21v
V AT
RBB
|
|x0
(2
Ar
6/2
T
AT Ar
|0|2
|a|2
With 2 tr(AAT A) and the positive constant given below, we obtain
(1 + (x( 2xx F(x) + [G(z) - (2- (())
lim sup 1x|
|x]
A + 81,)x
Ax
612
AT ATA
lim sup |x|
nFB
|z|
1x|/
(2 p) n
Ax
2 x
A Ar
(35)
|
[x
x/2 lim inf
(n + +
(O(ATA)M(N (2 (2-))MM())
n²B B
7
7/2
inf
q(m, p),
n² B
mx
18

---

where
(m. = 2mB(mm +0
7 -tr((AAA)))) A)m + (2 - p)m²
(36)
Set
0 = 2+ 2n + 6)
Σラ 1= x
7x1
X
Note that due to the assumption 7 < we have 0 > 2. We claim that
inf g(m, p) 9) =0 mE(A?AA]
(37)
for all p (2, First, note that + (m, p) is concave for any P E [2, d) such that its minimum must be attained at one the boundary values m {12, A Second, note that p H q(m, p) is
strictly decreasing for any (0, oo), such that for 37 it is sufficient to show
(\,, 2 q(A 0) = 0.
(38)
Using the assumption 7 we obtain
0) = Bn
? (2 + - tatttttAAAA" A)A A) + 2nB
(x + 8) tr
(22 02
2 tr(AATA) A)
(AP + \ - x²
For 0 the right hand side vanishes and 338 shown. Differentiation shows that the right hand side is increasing in 6, such that (38) holds for all 5 0. Altogether, have shown that the right hand side of (35) strictly negative. Thus, the SDE (32) satisfies the Assumption 5.1 in [Li et al.
2019 Based on Theorem 5.2 in Li et al. 2019], the solution X, of the SDE (32) satisfies
sup 0g
X| <
for all E (). Therefore, the lower bound, denoted by 17s, for the asymptotic tail index X2 is
(A +
Σ
= 0==
A.6 Wasserstein convergence
Lemma A.3. Let Z and Ž be two strong solutions of
7
with possibly different initial conditions
Zo, Zo E R., Suppose that
9< nB
(39)
2
X +
Then the equation
Σ
X
nB
(40)
X + np/r
27
1=1
has unique positive solution p. 0 and there exist constants C, C' independent of Zo. Zo. such that
2,1 2
< Ce Ce- 24p, 2 2o 2
E
2
and
E [
< C²e -21p.
17o12
Proof. We set (H1,..., M.r). ). θ diag(f1..... 0r), (2 0z,... 26,0,), and transform Z into V/ = e (2r p1). Applying Ito's formula, we see that V can be written as
V, = Zo + ('" 0. diag(w dh (22 dB..
(41)
19

---

The same representation holds for V in relation to Z. Setting d(z,2') = / - +
we estimate
Vi
Vi
S 2o
(1
2) + +
( 2, 2,)d (.)
21
for each i = I...r. Using Ito isometry and the Lipschitz property d(z, z²) S 12 - 2/1. we obtain
IЕ Vi
v 2
4
{ Z Zij
vi !'" 28.8 11 11. 43' 2| ds
Introducing D, = (D),.... D where Dj =
E
zi 2: and M = f1 (vx)).s where
1 (I,..., 1), we can combine these inequalities into the vector-valued inequality
[ 200 220 MD,ds
Dr S 4 20t 20t Do t
Now, consider the comparison equality
261 Do -201 ( 200 M MD,ds
D. - 261
Differentiation shows that
d - D. - -2
di
Applying the comparison result of Beesack 1969] we obtain
E [Z. 1 = 1 D. S1 = =1=e -21(0) 21(0-2M) Do-
Hence,
E ||z, - z Ce -2p 2 Z/!
where Pa is the smallest Eigenvalue of ④ 2MM
Now, M 11 T i... 2.M can be considered a rank-one perturbation of the diagonal matrix O. By Anderson 1996). the Eigenvalues Pl....,Pt Pr of θ 2M are solutions of the secular equation
2 = 0.
F(p) :
(42)
0:
1=0
Moreover, they interlace the diagonal values of θ, ie.. we have p. = P1 <
<...< < θ,.
Therefore, all Eigenvalues of è - 2M are positive, except for p. which may be either positive negative. On (-o0, f2) the function is strictly decreasing from 1 to -oc, such that its root satisfies p. > 0 if and only F(O) > 0. Rewriting this condition in terms of (6) yields (39; doing
the same for the secular equation 422 yields (40). This completes the proof for the estimate of
E 2.
3 the proof for E I. is completely analogous.
We are now prepared for the proof of Theorem 3.4 which uses some key ideas from Friesen et al. 2020
Proof. Let (Z)120 be the unique strong solution of 7 and denote by pr(2, dC) its Markov transition kernel. Moreover, for any Borel measure μ on IR' set
P.p(dC) = f (()dd))
Note that Pi+. = P.P, = P.P. by the Markov property of Z. Denote by Pg the set of all Borel measures on IR" with [1 < cc. From Lemma A.3 we see that under condition (39 P maps Pa into Py for any 2 O. Moreover, the contraction estimate in Lemma A.3 implies that
(2 P(dx) S Ce tp- 17-12- -21 2'1
20

---

with òz. dgr the Dirac measures in and z' respectively. Using the convexity of the 2- Wasserstein distance (cf. Sec. A.2 in [Friesen et 2020 now follows that
Wa P.v) Ce Ce-te-We (2(11),)
for any ,4, in Pz.
Let P2- For any n, h No. we have
W2 PAP) Wa Pap) Ce W2(Pan,)),
which shows that meNN) is Cauchy sequence in (P2, W2). In particular there exists limit P2 such that nim Wa(Pn π O. Next, show that π an invariant measure for Z. Indeed, for any h > 0 and & N. we can estimate
(2(PPT, ) & (P,T PaPP + W (PPPP PAP) + W2(PAA, x) &
< hp- W2( PEP) + Ce Kp- W2 μ1 WA(TT, Paμ).
where the right hand side tends to zero as - oc. Finally, we show that the invariant measure æ is unique. Suppose that there is another invariant measure πt' P2. Then
W2(T, n = W2 P.T S Ce-
np, W2(TT,'),
which tends to zero as + co. Together, this shows that under the conditions of Lemma A.3 Z converges W3-distance its unique invariant distribution म, and hence completes the proof of Theorem 3.4
A.7 Parameter Values
Table 4: Parameters used for Figure I
Figure
data
d
K
7
8
B
A1
17+
(a), (d), (g)
X'
200
1000
0.015
0.037
319.83
3.56
3.61
(b), (e), (h)
y
64
10000
0.100
0.133
137.07
2.48
2.91
(c), (f), (i)
Z
200
10000
0.200
0.304
0
1
93.49
2.70
3.06
Table 5: Parameters used for Figure 2
Figure
data
d
(a), (d), (g)
X'
200
3000
0.1
(b), (e), (h)
y
64
3000
0.1
0
1
(c), (f), (i)
2
200
3000
A.8 Experimental configuration
The computing device that we use for calculating our examples includes a single Intel Core i7- 10U CPU with 16GB memory. Our code is available https: //t:::///ttttbttt www.uueb..oommeeeeeeeeee iao hSGD
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: see the Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: see the Sections Dections2.6.art and 3.4
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
22

---

Justification:
See the Supplement A. A.6 for all the proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yss]
Justification:
The experiments in the paper are reproducible; code will be released.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
23

---

Answer: [Yes]
Justification:
See the Supplement A.8
A.88
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
lc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
http:///.....ciideoe/deeeeeaaaaa CoodeSubeeiieeeeeeeeee ssi asionnolle onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See the Supplement A.7
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: see the Table 2
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
See the Supplement A.8
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //tp::///euis..eeeeee
Answer: [Yes]
Justification:
The research in this paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
25

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
See the Supplement A.8
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppawpptheeee throdee.etecce...... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
26

---

Answer: [Yes]
Justification:
See the Supplement A.8
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "ecWtcvaevS", "reviewer": "Reviewer_ya3E", "summary": "This manuscript studies homogenized SGD (hSGD) to characterize the tail behavior of SGD iterates for solving the ridge regression problem. By comparing the homogenized diffusion with a known diffusion process called Pearson diffusion, the authors provide a lower bound on the tail index of the iterates of homogenized SGD. They analyze how hyperparameters contribute to this lower bound, offering a qualitative analysis of hyperparameter choices and their impact on the distributional limit of SGD iterates.\n\nOverall, the paper makes a solid contribution and offers a more in-depth analysis of the heavy-tail phenomena in SGD compared to existing work. However, there are a couple of important points that need clarification:\n\n1. Is it the case that the marginals of hSGD and SGD have the same distribution? Theorem 1.3 in [1] suggests this holds for certain quadratic statistics, explained through the concentration of measure. However, if this comparison relies on the concentration of measure, the overall distributions of the two random variables can differ significantly despite overlapping in certain statistics. Therefore, I suggest the authors clarify this aspect.\n\n2. The comparison between the diffusion in (6) and (7) may be somewhat loose, especially given that the ratio between their interaction terms can be high. While the authors use experiments to suggest otherwise, the theoretical analysis does not clearly establish this. Could the authors extend their discussion on how tight or loose this comparison is in high dimensions?\n\n[1] Paquette, C., Paquette, E., Adlam, B., & Pennington, J. (2022). Homogenization of SGD in high-dimensions: Exact dynamics and generalization properties.", "questions": "See the Summary part", "limitations": "I am not convinced that the theoretical results presented in this paper are directly applicable to analyzing the iterates of SGD. Therefore, I am currently leaning towards suggesting a Borderline Reject. I look forward to receiving further clarification, which may lead to a reconsideration of my evaluation.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "See the Summary part", "weaknesses": "See the Summary part", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and your assessment of our paper. Regarding the two points raised, we have the following reply:\n\n1. **Difference between hSGD and SGD**: In general, the marginals of hSGD and SGD do not have the same distribution. However, as we mention in line 91f, reference [1] provides quantitative and _non-asymptotic_ approximation guarantees to control the difference between quadratic statistics of the iterates of hSGD and SGD. These quadratic statistics include linear projections as a special case, such that they can be applied e.g. to the projection of $X_t$ onto the dominant singular vector $q_1$ of $A$, which is the relevant direction used to determine the tail-index in Theorems 3.2 and 3.3. \nMoreover, the mentioned drawback (difference of distribution between exact SGD and its approximation) is shared by hSGD with *all* other continuous diffusion approximations, such as the Ornstein-Uhlenbeck/Langevin approximation of [2] and [3] or the alpha-stable OU approach of [4], such that our paper is by far not unique in taking this approximation step.\n\n\n2. **Comparison between diffusions (6) and (7)**: Yes, we agree that we have no theoretical control over the ‘closeness’ of the diffusions (6) and (7) in general. However, as outlined in section 3.1. the solution of (7) provides a *lower bound in convex order* to the solution of (6), which is precisely what is needed to control the tail-index of (6) from above. Thus, it is primarily the _comparison principle_, not the `closeness' that makes (7) useful in relation to (6). \nMoreover, the experiments in 4.2 (and the performed statistical tests) suggest that the stationary distribution of (7) -- the skew Student-t distribution -- is typically a good proxy for the stationary distribution of (6), notwithstanding the lack of rigorous justification.\n\nWe hope that your concerns have been addressed in a satisfactory manner and are available for further clarification.\n\n[1] Paquette, C., Paquette, E., Adlam, B., & Pennington, J. (2022). _Homogenization of SGD in high-dimensions: Exact dynamics and generalization properties._\n\n[2] S. Mandt, M. Hoffman, and D. A. Blei. _A variational analysis of stochastic gradient algorithms_. In International Conference on Learning Representations, 2016. \n\n[3] Qianxiao Li, Cheng Tai, and E Weinan. _Stochastic modified equations and adaptive stochastic gradient algorithms._ In International Conference on Machine Learning, pages 2101–2110. PMLR, 2017.\n\n[4] Umut Simsekli, L. Sagun, and Mert Gurbuzbalaban. _A tail-index analysis of stochastic gradient noise in deep neural networks._ In International Conference on Machine Learning, pages 5287–5837, 2019.", "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": "", "extra_scores": {}}, {"review_id": "WPcisHDs96", "reviewer": "Reviewer_BR2r", "summary": "This paper provides another perspective of the emergence of heavy tails in SGD to the recent literature. Unlike the previous literature, the paper assumes that the SGD can be adequately approximated by homogenized SGD, which is a Brownian-motion driven SDE with a given state-dependent diffusion term. \n\nThe paper restricts the study to the quadratic loss. \n\nThe tail-index bounds are fully explicit. \n\nThe paper introduces a comparison method based on convex stochastic order for homogenized SGD. This allows linking SGD to Pearson diffusions in the literature and then obtain bounds for the tail-index. The results suggest that one can use skew student-$t$-distributions as proxy for parameter distributions in neural networks under SGD, in contrast to the $\\alpha$-stable distributions that are commonly used in the literature.", "questions": "(1) Your definition in Definition 2.2. for heavy-tailedness  basically says a random variable is heavy-tailed if its tail is heavier than any exponential distribution. But your definition for tail-index in Definition 2.4. is about polynomial decay. I think there is some disconnect here. For example, consider $1-F(x)=e^{-\\sqrt{x}}$ for any $x\\geq 0$. Then, according to your definition, the tail-index is infinity even though it is heavy-tailed. That makes me wonder whether it is better to change your definition of heavy-tailedness. For example, can you say it is heavy-tailed if the tail-index is finite?\n\n(2) The analysis is for quadratic loss. Since your main results are the upper and lower bounds for the asymptotic tail-index,  would it be possible to extend your analysis beyond the quadratic loss?\n\n(3) It seems you did not provide any discussions on the theoretical result Theorem 3.4. For example, it might be worth mentioning how the convergence rate $\\rho_{\\ast}$ depends on the model parameters.\n\n(4) You description that Gurbuzbalaban et al. [2021] only describe a phase transition of the asymptotic tail-index $\\eta$ from $\\eta<2$ to $\\eta>2$, without giving quantitative estimates of $\\eta$ is not that accurate. There, they obtained a semi-explicit formula for the tail-index $\\eta$, and when the input data is Gaussian, the tail-index $\\eta$ becomes even more explicit, without the necessity to rely on upper and lower bounds.\n\n(5) In your equations (SME) and (hSGD), the $d$-dimensional Brownian motion is denoted as $W_{t}$. But later, in equation (3), $B_{t}$ is used to denote the $d$-dimensional Brownian motion. If they are the same, it is better to use the same notation. If they are different,\nyou should make the relation between $W_{t}$ and $B_{t}$ more transparent.", "limitations": "I did not see many discussions on the limitations, which should be mentioned in the summary. In fact, there is not even a conclusion section of the paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) The idea of using homogenized SGD as a proxy and then obtain upper and lower bounds for the asymptotic tail-index is new.\n\n(2) The upper and lower bounds are explicit.\n\n(3) It provides a new perspective to a recently popular topic in the literature that is the emergence of heavy tails in SGD.\n\n(4) The analysis is rigorous, and the paper comes up with some comparison method and compares the homogenized SGD with Pearson diffusion.\n\n(5) Wasserstein convergence is also obtained.", "weaknesses": "There are a few weaknesses of the paper.\n\n(1) Unlike Gurbuzbalaban et al. (2021) in the literature, the paper does not tackle the tail-index of SGD directly, but only the tail-index of homogenized SGD, which is an approximation of the SGD.\n\n(2) Even though an approximation of the SGD is used, and only the quadratic loss is considered, the results for the tail-index only concern upper and lower bounds. Despite being semi-explicit in Gurbuzbalaban et al. (2021), the tail-index in Gurbuzbalaban et al. (2021) is exact. \n\n(3) Since only the upper and lower bounds are obtained for the tail-index, it is natural to ask whether the analysis can be extended beyond the quadratic loss. This is a very reasonable question because upper and lower bounds should be used when it is impossible to obtain the precise tail-index. One expects that it is impossible to obtain the precise tail-index for the non-quadratic loss. But since comparison method is used in this paper, it is natural to ask whether it is possible to compare the non-quadratic loss with quadratic loss to obtain upper and lower bounds for the tail-index beyond the quadratic loss. In my view, that will make the paper much stronger.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and your assessment of our paper. To your questions we have the following replies:\n\n**Question (1)**: Our definition of `heavy-tailed' follows the standard definition from the literature on heavy tailed distributions, see e.g. Def. 2.2. in [1]. As we write in l126 a finite tail-index implies heavy-tailedness. The opposite is not true, as evident from your example; several other such examples are known in the literature, e.g. the lognormal distribution.\n\n**Question (2)**: _Thank you, this was an excellent question/suggestion!_ We have looked at the case of a general strongly convex loss with Lipschitz gradient and at least the proof of the lower tail bound can be adapted, i.e. heavy tails can be shown! As similar questions have also been raised by other reviewers we give a longer answer in the authors' rebuttal above.\n\n**Question (3)**:  We agree that it should be possible to determine the dependence of $\\rho_*$ on the model parameters by implicit differentiation of the equation in line 222. However, $\\rho_*$ is only an upper bound for the rate of convergence, not necessarily the true rate of convergence. Hence, analysing these dependencies may be misleading and we would refrain from doing so in the paper. \n\n**Question (4)**: We are not sure what you mean by `semi-explicit’. Could you clarify and maybe point to the concrete result in Gürbüzbalaban et al. [2021] that you are referring to? Taking your answer into account, we will try to make the comparison of our results to Gürbüzbalaban et al. [2021] more balanced.\n\n**Question (5)**: The two processes $W_t$ and $B_t$ are different Brownian motions related by an orthogonal transformation $Q$ as can be seen in l380 in the appendix. We will add a line in the main part of the paper to clarify. \n\n**Discussion of Limitations**: We have omitted a Conclusions/Limitations section from the submission due to space constraints. We will add such a section in the revised paper (which allows one page more).\n\nWe hope that we have addressed your questions in a satisfactory manner and are available for further discussion.\n\n[1] S. Foss, D. Korshunov, S. Zachary. _An Introduction to Heavy-Tailed and Subexponential Distributions_.  Springer 2013", "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": "", "extra_scores": {}}, {"review_id": "GNh1nQd0hT", "reviewer": "Reviewer_qGrH", "summary": "The paper builds up on the theory of heavy tails in Stochastic Gradient Descent (SGD), clearing some aspects of the distribution of the parameters learned during training. Leveraging a combination of the works on homogeneized SGD and diffusion, the author(s) are able to shed light on the role of noise and the distributional properties of parameters. \nMore in depth, they relate homogeneized SGD to a \"coupled\" Pearson diffusion, that can be put in comparison (convex stochastic order) with the standard one. Thanks to this, an explicit description of heavy-tailedness via the asymptotic tail index is obtained. One side of the bound is automatic, the other requires an assumption on the learning rate. After establishing the asymptotic behavior, the speed of convergence to it is explored; subject to an assumption on the learning rate, the author(s) prove that it can happen exponentially fast in Wasserstein distance. To validate their arguments, statistical tests for the parameter distribution are proposed in one case.", "questions": "What ensures that the solutions are strong? \n- (more of a curiosity) Do you have any comments on a possible regime/example in which the lower bounds on the learning rate $\\gamma$ obtained in Theorems 3.3-3.4 give a nice interpretation? \n- In the experiments, you analyze the first eigen-component of $\\mathbf{Q}$ via the projected quantity $\\mathbf{q}_1^\\top \\mathbf{x}_K$, what happens to the analogues for $\\mathbf{q}_2, \\ldots$? Do you observe that the theory works less? Maybe it would be interesting to see other experiments. \n- Can you somehow validate Theorem 3.4 with an experiment? The parameter $\\rho_{\\star}$ is the solution of an equation, you have an explicit bound on the learning rate that if verified would make you expect to have a certain exponential convergence, do you see it in a simulation? \n\nThe paper is technically solid, and of interest to the community. Subject to fixing the typos and potentially extending the experimental section, I believe it is very good. Therefore, count my score as \"waiting for engagement\".  Dear author(s), please do. I will be glad to raise my scores.", "limitations": "None.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The overall exposition is clear and to the point. \n- On a related note, the structure is pedagogical: my impression is that any reader at any level could take something from spending time on the paper. This is important. \n- The observation that gaussian noise is sufficient to have a heavy-tailed distribution is very valuable. \n- Asymptotic results are paired with practical convergence at the cost of assumptions that are not absurd. \n- The work connects recent works on the distribution of SGD parameters and well-developed theory of diffusions. \n- The experiment proposed to validate one of the results is a theoretically grounded suggestion for modelling parameter distribution, and not just a heavy-tailed educated guess. \n- The coupled-Pearson diffusion link sheds a new light on the interpretation of the dynamics. \n- The idea of using convex stochastic order is simple and effective to obtain just what is needed. Such point is probably the part I appreciated the most. \n- In general, a nice and useful read.", "weaknesses": "(more of a subtlety) The convex stochastic order bound works for $p\\geq 1$ only, Theorem 3.2 does not explicitly state this. One might ask: what if we have a distribution with asymptotic index less than one? Then Theorem 3.1 does not work, but the truth is that for both cases of the Pearson diffusion we have that the tail index is $\\nu_i\\geq 1$ . Maybe this should be made more explicit? Can you give more clarifications? \n- The diffusion approximation is backed on an approximation of the covariance done to match the moments. Crucially, it makes the problem tractable. The works about hSGD, as the author(s) mention themselves in lines 91-97 are subject to \"certain assumptions\" and \"further empirical evidence\". This justifies their paper, to the extent that they trust the same setting, as it does not qualify for a full mathematical proof. For the same reason, the present submission misses a set of assumptions, while proving theorems. In general, I agree with this exploratory perspective, but maybe it needs to be mentioned more explicitly and not just briefly stated (related to the note on Limitations just below).\n- A proper, explicit discussion of limitations is missing. Section 2.6 is a comparison with literature, section 3.4 is a reconciliation with a specific work. As a reader -- and this is a personal opinion -- I would be very happy to hear why and when your work might/does not work.  \n- The experiments show only one of the two scenarios (inverse Gamma type distribution is not shown). \n- Figure 1, subfigures (g)-(h)-(i) should show upper and lower bounds on the ccdf but have some inconsistency. I understand that this might be due to the experimental setting, but Figure (g) clearly has the lower bound (blue) above the lower upper bound (green), with the true distribution even below. Maybe you can clarify this aspect?\n- Theorem 3.4 is not backed by experiments. \n- Overall, I would be glad to see more validation of the theory. \n\n\n#### Typos\nThese are not weaknesses, but I am adding them here since there is no dedicated box. Please note that some are very pedantic, but I want to be constructive and give you all that I saw. \n- The notation for $L, L_{\\Omega_k}, L^{\\mathrm{reg}}, L^{\\mathrm{reg}}_{\\Omega_k}$ is possibly confusing: if I look at equations (SGD), (1) and (2) it looks like there is something off, but then checking the original formulation of the works cited it is possible to understand why this is the case. Maybe a clarification sentence would be helpful to the reader. \n- Related to the point above, If we also take into account appendix A.1, there we also need to take care of $L, f$. Maybe too many redundant symbols do not help an inexperienced reader. \n- (line 74-75) The standard notation for vectors is to take them as columns, the fact that $C(x) = \\mathbb{E}[\\epsilon(x)^\\top\\epsilon(x)]$ on the top of my head makes me think it is a scalar. At the same time, I understand that this is a matter of canonical choice. \n- (line 100) The matrix $Q$ is stated to be \"$r$-by-$d$\" but according to $A = P\\Sigma Q^\\top$ with $\\Sigma$ in $r$-by-$r$ it should be the opposite. \n- (line 113) is the power in the covariance $\\Sigma$ appearing in $\\alpha$ right? I have not thouroughly checked this. \n- (line 121, Def. 2.2) $\\limsup_{t\\to\\infty}$ is taken, but there is no $t$, also $F(x)$ appears in the equation. I believe you wanted to write the limit supremum of $z\\to\\infty$, $1 - F(z)$ at the  numerator, and $e^{-sz}$ at the denominator? \n- (line 125, Def. 2.4) you take the modulus of a vector in the definition of tail index. Later in equation (6) you take the norm of $Z_t$, where $Z_t$ is a vector. In one way or the other I would like to point out the inconsistency of notation for norms of vectors. \n- (Figure 1, subfigs. g, h, i and caption) in the legend, you have $t(\\eta_i)$, in the caption, you use the notation $\\eta_*, \\eta^*$, the two are intuitively bijected, but maybe you can fix the legend to be consistent with the paper?  \n- secondary, but related to the point above: the legend in the subfigures is very small and redundantly repeated. If you have space left from the submission page limit, and time in these busy times, could you please build a common legend in a separate subfigure? I am guessing here, but it looks like this is Matplotlib, and there are quick ways to extract a legend as a png from a figure, and add it to the text. This is more of an aesthetic aspect, please take it as a random idea rather than a request. \n- (lines 419-420) The sterile comment is that the \"class (D)\" TeX typesetting is wrong, there is a specific command for quotations. The constructive one is that you may want to remove the hat from the $\\hat{Z}_t^i$ in line 419 \n- (lines 446-447) the function $\\tilde{g}_n$ is bounded by $g$ in the same way in the two intervals. \n- (between line 454-455) in the last inequality, you are missing an $\\mathbb{E}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your extensive comments and for your detailed reading of our paper. Regarding the mentioned Weaknesses, Typos and Questions, our replies are as follows: \n\n* **Case of tail-index < 1**: Our results should be interpreted as follows: By Theorem 3.2. hSGD will _always_ have an asymptotic tail-index of at least one. Thus, if SGD produces (empirically) a distribution with tail-index $\\alpha < 1$, it is not Theorem 3.2. which breaks down, but the approximation of SGD by hSGD becomes too weak to track the tail-index. We can add a remark to this effect in the revised version.\n\n* **Limitations**: We have omitted a Limitations/Conclusions section from the submitted version due to space constraints. We will include such a section in the revised version (which allows one additional page). The following Limitations will be addressed: (1) Need for results beyond [1] to control the 'gap' between hSGD and discrete SGD, (2) extension of results to non-quadratic and non-convex losses, (3) Current results cannot be applied to 'extremely heavy tails' with tail index $\\alpha < 1$. \n\n* **Small inconsistencies in Figure 1.(g)**: The tail bounds relate to the tail behaviour of distributions, such that a different ordering of cumulative distribution functions in the ‘bulk’ of the distribution is not prohibited. Moreover, numerical effects and finite sample effects can contribute to differences between experiment and theory\n\n* **More validation/theory**: In the paper, our focus was on giving a clear exposition of the theory and the new method (comparison in convex order). Thus, we have limited our experiments to the validation of the tail bounds and the distributional properties. Our view is that Theorem 3.4 is not a ‘main result’ of the paper, but rather provides the justification of applying asymptotic tail bounds to non-asymptotic marginal distributions. \n\n* **Typos**: All typos have been fixed, thanks. Selected comments:\n     - _notation in equations (SGD), (1) and (2)_: As the gradient noise is the difference of the two terms $\\nabla L^\\mathrm{reg}_{\\Omega_k}$ and $\\nabla L^\\mathrm{reg}$, the regularization terms cancel and $L^\\mathrm{reg}$ can be replaced by $L$ in (2); is that what you are referring to? If yes, we will add clarifying remarks.  \n    - _notation for covariance matrix $C(x)$_: Agreed, we will treat gradients as column vectors and switch transpose signs accordingly. \n    - _Expression for $\\alpha$ in line 113_: We have re-checked and it is correct.\n    - _Notation for vector norms_: Thanks, we will use $\\||.\\||$ throughout.\n\n* **Strong solutions of SDEs (6) and (7)**: As pointed out in line 388f, both drift and diffusion coefficients are Lipschitz, such that the existence of unique strong solutions follows from standard results, such as Thm. 2.5 in Chapter 5 of [2]\n\n* **Interpretation of learning rate bounds in Theorems 3.3. and 3.4**: One observation is that inserting the upper bound $\\overline{\\gamma}$ of the learning rate in Theorem 3.3. into (13) yields a lower bound of $\\eta_* = 2$. In other words, Theorem 3.3. breaks down exactly for tail-indices $\\eta < 2$. Another observation (can be shown similar to the proof of Theorem 3.4) is that if the learning rate satisfies $\\gamma > \\gamma'$ then the second moment of the hSGD process $X_t$ diverges (i.e. also 2-Wasserstein distance diverges).\n\n* **Extension of experimental section**: On request of other reviewers, we will add an experiment on a non-linear mode (2-layer NN). Adding further experiments, e.g. on Wasserstein convergence or properties of other projections $q_i^\\top x_K$, is out of scope both due to time- and space-constraints, we are afraid. But it could be considered in our future work.\n\nWe hope that we have addressed your comments in a satisfactory manner and remain available for further discussion.\n\n\n[1] Paquette, C., Paquette, E., Adlam, B., & Pennington, J. (2022). Homogenization of SGD in high-dimensions: Exact dynamics and generalization properties.\n\n[2] Karatzas, Ioannis, and Steven Shreve. Brownian motion and stochastic calculus. Vol. 113. springer, 2014.", "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": "", "extra_scores": {}}, {"review_id": "Ve1h8aOXnv", "reviewer": "Reviewer_G3NM", "summary": "This paper analyses the emergence of heavy-tails in homogenized SGD applied on linear models with quadratic loss. Following other works, the authors model SGD through homogenized SGD and show theoretically and empirically that such an equation converges naturally to heavy-tailed distributions, despite the fact that the noise appearing in the SDE is Gaussian. The proof technique is based on known properties of Student-t-distributions, which appear in the study of similar equations, and a comparison result for moments. This allows the authors to derive analytic upper and lower bounds of the tail index that they were able to successfully confront with numerical experiments. These numerical experiments suggest that Student-t-distributions may better described the distribution of SGD iterates than previously used stable distributions.", "questions": "- In the equation just after line 93, what is $D$?\n\n - Can you elaborate on how big the right-hand side of Equation (12) can be in practice? In particular, the ratio $n/\\gamma$ (number of data points over learning rate) seems to be huge. What are the conditions for the tail index to be small (ie, the distribution has very heavy tails)? In particular, it would be beneficial to present the analytical values found in Table 3 in the main part of the paper (they are only presented in the appendix).\n\n - Theorem 3.4: in order for the 2-Wasserstein distance to make sense, isn't the fact that the tail index is greater than 2 necessary? Does that follow from the assumptions of this theorem?\n\n - In Figure 1, you compare the Student-t-distribution and $\\alpha$-stable distributions to the experimental data. How was the tail-index $\\alpha$ (used for the $\\alpha$-stable distributions) estimated?\n\n**Other remarks**\n\n - In the introduction, you mention that some authors argue for a negative correlation between the tail-index and the generalization error. However, a lot of recent works have argued that different behaviors can happen in many settings, see in particular https://arxiv.org/abs/2006.09313, https://arxiv.org/abs/2402.07723 and https://arxiv.org/abs/2301.11885.", "limitations": "Several limitations were discussed in the paper. However, it should be clear from the abstract and introduction that the analysis is restricted to linear models. Moreover, a discussion on the potential extensions of the theoretical (and empirical) result to vanilla SGD and non-linear models would be very interesting.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Showing that heavy tails can arise even in the presence of Gaussian-type noise is an original contribution, which may illuminate some aspects of the presence of heavy tails in machine learning.\n\n- As opposed to previous works, analytical bounds are derived on the tail-index. These bounds are directly computable from the optimization hyperparameters.\n\n - The authors confirmed previous experimental findings regarding the emergence of heavy tails in SGD. Moreover, their results suggest that Student-t-distributions could be used to model SGD noise, as opposed to previously used $\\alpha$-stable distributions.", "weaknesses": "- The paper has no conclusion, it could improve the paper to add a few lines of conclusion to discuss limitations and future works.\n\n - As it is explained in Section 2.1, the analysis is entirely limited to the case of linear regression with quadratic loss. However, this is never mentioned neither in the title, abstract, or introduction (including the claimed contributions) of the paper. The claim that the paper analyses ``heavy-tailed phenomena in SGD'' may therefore be too strong. It should be mentioned that all results were obtained for linear regression.\n\n - A weakness related to the previous point is that there should be more discussion on whether this analysis can extend to more complex settings, ie, outside of the linear regression settings, instead of just saying that all models are approximately quadratic near a local minimum. It is understandable that it is hard to extend the theoretical analysis to this setting, but  it would largely enhance the paper to perform similar experiments as in Figure 1, but with a simple non-linear model, like a 2-layers neural network.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your review and the comments on our paper. Below we comment on the Weaknesses and answer to the Questions posed in your review: \n\n* **Lack of Conclusions Section**: In our submission we have omitted a Conclusions section due to space limitations. We will include such a section (discussing future work and current limitations) in the revised version, which allows an additional page.\n\n* **Results limited to quadratic loss**: We _do_ mention this limitation in the paper's abstract, writing `... and show in a _regularized regression framework_ that it leads to an asympotically heavy tailed parameter distribution…'. In line58 we again mention the limitation to quadratic loss, and we will also address in the the new limitations section. \n\n* **Results on more complex models**: We have performed experiments on a 2-layer NN, this results will be included in the revised version.\n\n* **Question 1**: We will insert just above the equation in line 93:  `For any given $T>0$ and $D > 0$ there is a $C> 0$, such that...'  \n\n* **Question 2**: We think it is difficult to give general conditions leading to a small tail-index in _absolute_ terms, because the leading singular value $\\lambda_1$ affecting the tail-index will be highly data-dependent. Instead we provide insight into the _relative change_ of the tail-index when hyper-parameters are modified, see Corollary 3.5. In the current version Table 3 was moved to the appendix due to space constraints; if space allows we will move Table 3 to the main part of the paper in the revised version.\n\n* **Question 3**: Yes, if the conditions of Theorem 3.4. are satisfied, then the tail index must be greater than 2. We will add a remark on this. In fact, it is also possible to show that if $\\gamma > \\gamma’$ then the tail-index must be smaller than 2. Thanks for pointing this out.\n\n* **Question 4**: In our experiments, we use the Python module statsmodels for qqplots and distribution fitting, which uses a maximum-likelihood-based method to estimate the distributions' parameters. \n\n* **Other Remarks**: Thanks for pointing out these interesting new results. We will make sure to add a remark in the introduction and cite the mentioned papers. We will also mention in the Conclusion that the link between tail-index and generalization error in the hSGD framework warrants further research.\n\n* **Limitations**: We will add a conclusions/limitations section to the revised version. Regarding extensions to non-linear models, see the general author rebuttal above.", "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": "", "extra_scores": {}}]

Author rebuttal:
Several reviewers have raised the question if and how our results can be **extended beyond the quadratic loss/to non-linear models**. We think that such an extension is possible along the lines of the method introduced in the paper (and we do have some preliminary results) in the following cases:

(1) For a general (non-convex) smooth loss in the _one-dimensional case_. Here, the stochastic differential equations (6) and (7) will coincide but take a more general form due to the general loss function. Nevertheless, the SDE's stationary distribution and its tail behaviour can be analysed through the SDEs 'speed measure' and 'scale function', see e.g. Chapter V.28 in [1], which in turn can be linked to the loss landscape.

(2) Motivated by the comments of reviewer BR2r in particular, we have looked at the case of a _strongly convex_ loss with _Lipschitz gradient_ (aka $\beta$-smooth) in arbitrary dimension.  Using the standard inequalities (such as the Polyak-Łojasiewicz inequality) satisfied by strongly convex, $\beta$-smooth functions, we can now show that the comparison principle of Theorem 3.1. between hSGD and a Pearson diffusion still holds with $p \ge 2$ for such loss functions and are confident that also Theorem 3.2 can be adapted. This in particular would show that parameter distributions under hSGD are heavy-tailed for all strongly convex, $\beta$-smooth losses. 

In the revised version of the paper, we will add a conclusions/future work section where we outline these two possibilities of extending the results.

On the empirical side, we have extended the experiments described in section 4.2. to a simple non-linear model (2-layer neural network) and have plotted the corresponding weight distribution in the second layer as QQ-plots (see attached pdf). As for the linear models, the QQ-plots show that the Student-t-distribution (suggested by our theory) provides a better fit than the alpha-stable distribution that has previously been proposed in the literature.

[1] Rogers, L. Chris G., and David Williams. Diffusions, Markov processes, and martingales: Itô calculus. Vol. 2. Cambridge university press, 2000.

Meta-review: All the reviewers agreed that the paper has significant contributions to heavy tails arising in stochastic optimization. However, they also flagged that the paper is somewhat overselling its contributions since the quadratic loss is not mentioned in early in the paper and there is no formal link to original SGD. 

I recommend an acceptance by trusting the authors that they will incorporate all the promised changes one by one, especially

* Mentioning linear regression or quadratic loss starting from the abstract
* Making it crystal clear that the results only hold for hSGD not SGD and mentioning that the formal link is still missing.
Decision: Accept (poster)