Approximate Heavy Tails in Offline (Multi-Pass) Stochastic Gradient Descent
Authors: Krunoslav Lehman Pavasovic
Alain Durmus
Umut Simsekli
Venue: NeurIPS 2023 spotlight (2023)
Keywords: SGD
heavy-tails
wasserstein convergence

Abstract: A recent line of empirical studies has demonstrated that SGD might exhibit a heavy-tailed behavior in practical settings, and the heaviness of the tails might correlate with the overall performance. In this paper, we investigate the emergence of such heavy tails. Previous works on this problem only considered, up to our knowledge, online (also called single-pass) SGD, in which the emergence of heavy tails in theoretical findings is contingent upon access to an infinite amount of data. Hence, the underlying mechanism generating the reported heavy-tailed behavior in practical settings, where the amount of training data is finite, is still not well-understood. Our contribution aims to fill this gap. In particular, we show that the stationary distribution of offline (also called multi-pass) SGD exhibits ‘approximate’ power-law tails and the approximation error is controlled by how fast the empirical distribution of the training data converges to the true underlying data distribution in the Wasserstein metric. Our main takeaway is that, as the number of data points increases, offline SGD will behave increasingly ‘power-law-like’. To achieve this result, we first prove nonasymptotic Wasserstein convergence bounds for offline SGD to online SGD as the number of data points increases, which can be interesting on their own. Finally, we illustrate our theory on various experiments conducted on synthetic data and neural networks.

Approximate Heavy Tails in Offline (Multi-Pass) Stochastic Gradient Descent
Krunoslav Lehman Pavasovic
Inria Paris, CNRS, Ecole Normale Supérieure, PSL Research University Paris, France
krunoslav wew.yy.eemmappppp wew..aan.ppaasssiiiiiiir.....e
Alain Durmus
CMAP, CNRS, Ecole Polytechnique, Institut Polytechnique Paris
Paris, France
alain, durmms@@polytecchiique edu
Umut Şimşekli
Inria Paris, CNRS, Ecole Normale Supérieure, PSL Research University
Paris, France
umut. wwtsssiiinneeiiia.........
Abstract
A recent line of empirical studies has demonstrated that SGD might exhibit a heavy-tailed behavior in practical settings, and the heaviness of the tails might correlate with the overall performance. this paper, we investigate the emergence of such heavy tails. Previous works on this problem only considered, up to our knowledge, online (also called single-pass) SGD, which the emergence of heavy tails in theoretical findings is contingent upon access an infinite amount of data. Hence, the underlying mechanism generating the reported heavy-tailed behavior in practical settings, where the amount of training data is finite, is still not well- understood. Our contribution aims to fill this gap. In particular, we show that the stationary distribution of offline (also called mulli-pass)) SGD exhibits 'approximate" power-law tails and the approximation error is controlled by how fast the empirical distribution of the training data converges to the true underlying data distribution in the Wasserstein metric. Our main takeaway that, as the number of data points increases, offline SGD will behave increasingly 'power-law-like, To achieve this result, we first prove nonasymptotic Wasserstein convergence bounds for offline SGD to online SGD as the number of data points increases, which can be interesting on their own. Finally, we illustrate our theory on various experiments conducted on synthetic data and neural networks.
Introduction
Many machine learning problems can be cast as the following population risk minimization problem:
minimize æ F(x) (x, 2)) Z ~ pz
(I)
where x E Rd denotes the model parameters, M4 is the data distribution over the measurable space (Z, Z) and f IRd x Z + E is a loss function. The main difficulty in addressing this problem is that μ3 is typically unknown. Suppose we have access to an infinite sequence of independent and
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

identically distributed (i..d.) data samples D : ZZ,.Zz.... Zz.... from Mę. In that case, we can resort the online stochastic gradient descent (SGD) algorithm, which based on the following recursion:
X++1 Xx " Σ
Vs(Xx; Zi),
where & denotes the iterations, 94 := {b(k: - -, 1) +2 bkb is the batch of data-point at iteration k, 1) denotes the step size, denotes the batch size such that [Ωtz] = b, and Z; with E S2g, denotes the i-th data sample at the k-th iteration. This algorithm is also called "single-pass" SGD, as sees each data point Z; in the infinite data sequence 'D only once.
While drawing i..d. data samples at each iteration is possible in certain applications, in the majority of practical settings, we only have access to a finite number of data points, preventing online SGD use. More precisely, we have access to a dataset of n i.idd points D, == {Z,,..., Znn) and given these points the goal is then to minimize the empirical risk F(n,, given as follows:
minimize x + ((() == Σ f(x, Z,) over R
(3)
To attack this problem, one of the most popular approaches is the offline version of (2), which is based on the following recursion:
((() k+1 = x(() " E vf(x(") Z.),
where (2(") C {1....,n) denotes the indices of the (uniformly) randomly chosen data points at iteration with [2(")] = n and _(m) emphasizes the dependence on the sample size n. Analogous to the single-pass regime, this approach is also called the multi-pass SGD, as it requires observing the same data points multiple times.
Despite its ubiquitous use in modern machine learning applications, the theoretical properties of offline SGD have not yet been well -sllllstablished. Among plethora of analyses addressing this question, one promising approach has been based on the observation that parameters learned by SGD can exhibit heavy tails. In particular, I$GN+ 19] have empirically demonstrated heavy-tailed behavior for the sequence of stochastic gradient noise:
(x --' Eiend V Z:)
k21
Since then, further studies have extended this observation to other sequences appearing in machine learning algorithms [7FM 20, MM19, ZLMU222. These results were recently extended by [BSE+2]] 221, who showed that the parameter sequence (x(")) )x2)) itself can also exhibit heavy tails for large 7 and small b. These empirical investigations all hinted a connection between the observed heavy tails and the generalization performance of SGD: heavier the tails might indicate better generalization performance.
Motivated by these empirical findings, several subsequent papers theoretically investigated how heavy- tailed behavior can emerge in stochastic optimization. In this context, [GSZ21] have shown that when online SGD is used with quadratic loss (i.e., f(x, (a, v)) 2- (a ))²), the distribution of the iterates (Xx) ):20 can converge to a heavy-tailed distribution, even with exponentially light-tailed data (e.g., Gaussian). More precisely, for fixed step-size 7) > 0, they showed that, under appropriate assumptions, there exist constants c E R4 and a > 0, such that the following identity holds:
lim t (| > t) c, (+00
(5)
where Xoo π and π denotes the stationary distribution of online SGD (2). This result illustrates that the distribution of the online SGD iterates follows a power-law decay with the tail index a: PP xl t) z - for large Furthermore, a depends monotonically on the algorithm
'erre we deliberately choose the same notation Z, for both infinite and finite data regimes to highlight the fact that we can theoretically view the finite data regime from the following perspective: given an infinite sequence of data points D. the finite regime only uses the first elements of D. which constitute D,..

---

1000
-030
1402
Frequency
Frequency
Linear regression parameter norms ||i||
022
Neural network norms
0re
|||]|
Figure Left: histograms of the parameter norms for Gaussian data linear regression. Right: histograms of NN parameter norms for the first layer, trained on MNIST. Norms exceeding the μ 2o
threshold are marked with red asterisk.
hyperparameters 7/. b, and certain properties of the data distribution Pz- This result is also consistent with [DMN 21, Example 1], which shows simple instance from linear stochastic approximation such that for any fixed step-size there exists Pe > 0 such that for any p. 2 Pe- lim x|||XX ||]] +oo. In a concurrent study, [HM21] showed that this property is, in fact, not specific for quadratic problems and can hold for more general loss functions and different choices of stochastic optimizers, with the constraint that i.i.d. data samples are available at every iteration".
Another line research has investigated the theoretical links between heavy tails and the generaliza- tion performance of SGD. Under different theoretical settings and based on different assumptions, (SSDE20, BSE+ 21, LW$22, RBG+ HSKM22, RZG$23] proved generalization bounds (i.e., bounds on (x) - F(z))) illustrating that the heavy tails can be indeed beneficial for better performance. However, all these results rely on exact heavy tails, which, our current knowledge. can only occur in the online SGD regime where there is access to an infinite sequence of data points. Hence the current theory (both on the emergence of heavy tails and their links generalization performance) still falls short in terms of explaining the empirical heavy-tailed behavior observed in offline SGD as reported in [$GN+ 19, MM19, ZFM 20, BSE+211 21].
Main problematic and contributions. Although empirically observed, it is currently unknown how heavy-tailed behavior arises in offline SGD since the aforementioned theory [GSZ21, HM21] requires infinite data. Our main goal in this paper is hence to develop a theoretical framework to catch how and in what form heavy tails may arise in offline SGD, where the dataset finite.
We build our theory based on two main observations. The first observation is that, since we have finitely many data points in offline SGD, the moments (of any order) of the iterates x(m) can be bounded (see, e.g., [CGZ.19]), hence in this case we cannot expect exact power-law tails the form of (5) in general. Our second observation, seen as the first n elements of the infinite sequence D, as n increases the offline SGD recursion (4) should converge to the online SGD recursion (2) in some sense. Hence, when online SGD shows heavy-tailed behavior (i.e., the case where n > -o0,, as we increase n, we can expect that the tail behavior of offline SGD should be more and more 'power-law-like.
the other hand, is that since the finite dataset D, be
To further illustrate this observation, as preliminary exploration, we run offline SGD a 100-dimensional linear regres- sion problem, well as classification problem on the MNIST dataset, using a fully-comnected, 3-layer neural network.
n 0.01
0.025
n- 0.04
2.0
2.0
Online
1.5
1.5
1.5
0.5
0.5
0.5
10
100
500
1.0
20
50
100
10
20
50
100
500
1
In Figure 1, we plot the histograms of the parameter norms after 1000 (and 5000
Figure Estimated tail indices
resp.) iterations. We observe the following consistent patterns: (i) the means and standard deviations of the parameters' estimated stabilizing distributions increase with n, and (ii), the quantity and mag- nitude of the parameters far from the bulk of the distribution increase with n. In other words, as we increase the number of samples in offline SGD, the behavior of the iterates becomes heavier-tailed.
We will present these results more detail in Section "The exact experimental details can be found in Section 4.
3

---

As another example, we utilize the tail tall-estimator from [GSZ21]* to compare the estimated tail indices for offline and online SGD. The results are plotted in Figure 2 and correspond 10 random initializations with different step-sizes (for further details, see Tail estimation). We observe that, as increases, the estimated tail indices for offline SGD (shown green) get closer to the true tail index corresponding to online SGD (the horizontal blue line).
Our main contribution in this paper is make these observations rigorous and explicit. In particular, we extend the tail estimation results for online SGD [GSZ21, HM21J to offline SGD, and show that the stationary distribution of offline SGD iterates will exhibit 'approximate" heavy tails. Informally, for both quadratic and a class of strongly convex losses, we show that, with high probability, there exist constants C1 C2. such that for large enough we have the following tail bound:
C1 1 (W((e) (3)) & P
C2 to
+ W Wi((e. udd))
t)
S
(6)
to
where a is the tail index of online SGD as given in (5), X(a)
~ n (n) denotes a sample from the stationary distribution (1))) of offline SGD (4), p (m) n Σ == 82, denotes the empirical measure
of the data points in the data sample D, = [7,,.... 7 and W denotes the Wasserstein-1 distance
(to be defined formally in the next section).
Our result indicates that the tail behavior of offline SGD mainly driven by two terms: (i) a persistent
term (c/t*) that determines the power-law decay, and (ii) a vanishing term W (12, /42 ( /t, as we
take - In other words, compared (5), we can see that, with nigh-probability.. x exhibits an approximate power-law decay behavior, with a discrepancy controlled by Wi (Ma, u2 (7))
Fortunately, the term W1 (Hs, (n)) has been well-studied in the literature. By combining our results with Wasserstein convergence theorems for empirical measures [FG15], we further present nonasymp- totic tail bounds for offline SGD. Our main takeaway is as follows: as n increases, offline SGD will exhibit approximate power-laws, where the approximation error vanishes with a rate given by how fast the empirical distribution of the data points 142
(16) converges to the true data distribution (hg as n. - co.
To prove our tail bounds, an intermediate step, we prove nonasymptotic Wasserstein convergence re- sults for offline SGD the form: Wi (T, (x)) z W (1( (e (")), with high probability, recalling that t and (x) respectively denote online and offline SGD stationary distributions. These results, we be- lieve, hold independent interest for the community. Finally, we support our theory with various exper-
iments conducted on both synthetic quadratic optimization problems and real neural network settings.
Preliminaries and Technical Background
2.1 Notation and preliminary definitions
We let la denote the d x d identity matrix. We denote [n]] = (1,...,,),, m)) Pn, = (IC = b). For a vector x E Rdd ||>||| denotes the Euclidean norm of x, and for matrix A, the norm ||||| =
=1 || Axr| denote its spectral norm. We denote with mmin (A), Omax singular values of A, respectively. P (Rd) is the set of all probability measures on Rd and (XX de- notes the probability law of a random variable X. We denote the set of all couplings of two measures and v with [(u, v). Finally, for two functions (n) and g(n) defined on R.,, we denote f = O(g). there exist constants E R4, no N. such that f(n) S cg(n), Vn > no- The Dirac measure concen- trated at æ is defined as follows: for a measurable set E, 8, = 1 a E E, 85 (E) O, otherwise.
(rmax(A) (A) the smallest and largest
For p oo), the Wasserstein-p distance between two distributions μ and Fd is defined as:
1/p
v) = inf yer(p.))
(fl
vll dy(2,,
We correspondingly define the Wasserstein-p distance between two distributions j and is on Rddxd as
1/p
W up(n,) inf 7ET(u.))
'The justification for the estimator choice can be found in the appendix, Sec. E.
4

---

2.2 Heavy tails in online SGD
We first formally define heavy-tailed distributions with a power-law decay, used throughout our work. Definition 1 (Heavy-tailed distributions with power-law decay). A random vector X said to follow distribution with a power-law decay if sim [(] X 2 1) = Co. for constants Co > 0 and a > O, the latter known as the tail index.
The tail index a determines the thickness of the tails: larger values of imply lighter tail.
Recently [GSZ21] showed that online SGD might produce heavy tails even with exponentially light- tailed data. More precisely, they focused on a quadratic optimization problem, where 2 = =(a.0) q) E
Id+1 and f(z, 2) = 2- (a" x q)². With this choice, the online SGD recursion reads as follows:
" Σ (ara) Xx= asq;) = (Ie -1JA + nab+1
XR+1 X
iE0x+1
where (Zz)x21 (aks g6)221 A :- b= - a,a," and b := b- EiEn, a:q.
In this setting, they proved the following theorem.
Theorem 1 ([GSZ2I]). Assume that (ak.9k)ks 9k)221 are i.i.d. random variables such that a1 N(0, o² Ia). with o² > 0 and qs has continuous density with respect to the Lebesgue measure on with all its moments being finite. addition suppose that Eloog || La - < 0. Then, there exists unique a > 0 such that Ei[] Ta -n [|]] 1 and the iterates (Xx) in (7) converge in distribution to a unique stationary distribution πt such that if x a and a e N:
lim L'P (1 1) c, with E R
(8)
The authors of [GSZ21] also showed that the tail index a is monotonic with respect to the algorithm hyperparameters/ 7 and b: larger v or smaller indicates heavier tails, i.e., smaller a².
In a concurrent study, [HM21] considered a more general class of loss functions and choices of stochastic optimization algorithms. They proved a general result, where we translate it for online SGD applied on strongly convex losses in the following theorem.
Theorem 2 ([HM21))- Assume that for every = E Z, f(,,)) is twice differentiable and is strongly convex. Consider the recursion in (2) with sequence of i.d.d random variables (Zw) Zz))221 and let R and r be two non-negative functions defined as: for any 2 Z,
R(z)= == SuPZER" || V= f(x, 2) and r(2) == lim inf ||||| -0 Owin (Ia V f(r,
inf
Further assume that ([) + [ II] < +00 for some x² Rdd E[log R(Z1) < 0, and P(r(Zz) > 1) > 0. Then, the iterates (Xx)k21 in (2) admit a stationary distribution æ. Moreover,
there exist a, 3 > 0 such that [[[(Z)n] = [[) = 1, and for any E > 0:
lum t (o1 > 1) > 0, and lim sup 8 "1|Xx00 > f) < +00 10000
1+0
where Xoc n.
The result illustrates that power laws can arise in general convex stochastic optimization algorithms. We note that in general, Theorem 2 does not require each [(; z) be strongly convex, in fact, it can accommodate non-convex functions as well. However, we are not aware of any popular non-convex machine learning problem that can satisfy all the assumptions of Theorem Nevertheless, for better illustration, in Section F, we show that an lz-regularized logistic regression problem with random regularization coefficients falls into the scope of Theorem 2.
The two aforementioned theorems are limited to the online setting, and it is unclear whether they apply finite number of data points n. In the subsequent section, aim to extend these theorems to the offline setting.
'Without the Gaussian data assumption, [GSZ21] proved lower-bounds over a instead of the exact identifi- cation of as given in (8). We also note that the condition a & is not required in [GSZ21]: without such a condition, one can show that, for any u E d with ||u = 1, lim P (u X > t) has non-trivial limit. For the clarity of the presentation, we focus on the tails of the norm [|x,o],, hence use non-integer a, which leads to (8) (for the equivalence of these expressions, [BDM* 16, Theorem C.2.
5

---

Main results
3.1 Quadratic objectives
We first focus the quadratic optimization setting considered in Theorem 1 as its proof is simpler and more instructive. Similarly as before, let (a,, 4)s21 be i..d. random variables in Rd+1, such that (a,4)). Following the notation from (4), we can correspondingly define the offtine SGD recursion as follows:
x x
Σ
(aaa x -aa)) = (na-nA x +nb
(9)
AED h1l
where A (n) = b-bb-11 Eien a:a!
bg (n) b (n agqi and (2 is defined in (4). Now,
(A k by 1:21 are i.i.d. random variables with respect to the empirical measure:
(1)) (z)
[m] PA,b =
Σ 8 (A!") _b(')
(10)
where we enumerate all possible choices of minibatch indices Pn {1 C [1.....,n] |1| bb as (n) ) are i.i.d. random variables defined as follows:
Pnb= s/m)
S
(m)
and (A, b(())(C)
A
1 Σ aza
D
aj9j JES!")
Σ
(11)
b
JES
We denote by PA.b the common distribution of A (n) but only b.
b Note that it does not depend on
With these definitions at hand, we define the two marginal measures of PA.b and A with μA.
(n)
(n)
Hbb. and A Mbb respectively. Before proceeding to the theorem, we have to define Wasserstein ergodicity. A discrete-time Markov chain (Yx))20 is said to be (Wasserstein-l) geometrically ergodic it admits a stationary distribution Ny and there exist constants 2 0 and p E (0, 1), such that
W1 W1(2 TT) ce p for any 0.
(12)
The chain is simply called (Wasserstein-l) ergodic if lim W (2( TY) = 0.
We can now state our first main contribution, an extension of Theorem the offline setting:
Theorem 3. Let n 2 and en E [0, 1] be the probability that (x(("))²2 not ergodic (in the Wasserstein sense) with a stationary distribution (n) having finite q-th moment with > 1. Assume that the conditions of Theorem 1 hold with a > 1. Then, for any >> there exist constants G1 62. and to > O such that for all Ç E (0, 1], t > to, with probability larger than 1 - En the following inequalities hold:
c
Ci
log C2 [
S <PIIX
1)
S
2
c
+
20
C2 log
(13)
2a
ta
tn
ta
tn-/2
where c is given in (8).
This result shows that whenever the online SGD recursion admits heavy tails, the offline SGD recur- sion will exhibit 'approximate' heavy tails. More precisely, as can be seen in (13), the tails will have a global power-law behavior due to the term t- where a is the tail index determined by online SGD, On the other hand, the power-law behavior is only approximate, as we have an additional term, which vanishes at a rate (n -1/2). Hence, as n increases, the power-law behavior will be more prominent, which might bring an explanation for why heavy tails are still observed even when n is finite.
To establish Theorem 3, as an intermediate step, we show that  (n) converges to π Wasserstein-1 metric. The result is given in the following theorem and can be interesting on its own.
SSinee we are assuming Gaussian data, c, will converge to zero with an exponential rate. However, we do not focus explicit calculations of this quantity as it is rather orthogonal problematic.

---

Theorem 4. Under the setting of Theorem foror p.g > 0 with 1/p 1/1-111111110 d/2, a, the following holds with probability larger than
Cn²
5A W WI( x (1)) S cD
"
W Wp(uAAb:A'.b)
(m)
(14)
where co = " +
(19)
with x²") T()), and ò Elll La -
This result shows that the stationary distribution of offline SGD will converge to the one of online SGD as n + oo, and the rate of this convergence determined by how fast the empirical distri- bution of the dataset converges to the true data distribution, as measured by Wp Wp(AA,b, B.l.b.AAAA (A,)). Once (14) is established, to obtaín Theorem 3, we use the relationship that (I, 2 Ioeh [P([] > t) P(ll-xooll > f)] dt (see Lemmas 1 and 3 in the Appendix). Finally, by exploiting the assumptions made on μAA.b in Theorem I, we can
Wi (1 I)), xl)xx)))
invoke [FG15] (see Lemma 2 in Section A. and show that Wp(UA,b, / A.b behaves as On 112)..
(n)
3.2 Strongly convex objectives
We now focus on more complex loss functions, as in Theorem 2. For simplicity, we consider b = 1. The general case, while similar, would complicate the notation and, in our opinion, make our results more difficult to digest. We start by rewriting offline SGD with respect to an empirical measure u²"); [n)
x k+1 = x(x) - TV 2/411
(15)
where (2(")) are i.idd random variables associated with the empirical measure defined for any E Z as:
(A)= = -- Ej= S220 (A).
(16)
We first make the following assumption.
Assumption 1. (a) There exists L > 0 such that for any z E Z and x E Rd. (b) The data distribution μl has finite q-th moments with some q 2 1.
of(z,221 & A[||=] + +)[[l= - x' D).
Assumption 1-(a) is a Lipschitz- like condition that is useful for decoupling and 2, and is commonly used in the analysis of optimization and stochastic approximations algorithms; see, e.g., [BWMP12]. We can now state our second main contribution, an extension of Theorem 2 to the offline setting.
Theorem 5. Let (x2) and (x(")) )z2 z be defined as in (2) and (4) with = 1 and n 2 1. Assume hold. Further assume that R(Z, ((Z)) is non-
Assumptioo I and the conditions of Theorem 2 with deterministic (see Theorem 2), (X))220 is geometrically ergodic and 6, E [0, 1] is the probability that (x(²²) )u20 is not ergodic (in the Wasserstein sense). Then, for every > there exist constants Cco CB. and to 2 0, such that for all t > to, the following inequalities hold with probability larger than 1 cn
Co
C W Wi(ue, m())))
23-c
CB
2c W WWi
Vn,
20++ jatt
BB-t
where c (" (m) []] + 1) 5R) with ōn -[((Z))) and x(() (n))
This theorem shows that the approximate plwer-laws will also be apparent for more general loss functions: for large enough n, the tails of offline SGD will be upper- and lower-bounded by two power-laws with exponents a and /3. Note that the ergodicity of (Xx)a20 can be established by using similar tools provided in [DDB20]. On the other hand, the assumption on R(Zz) being non- deterministic and E [[T))(2)] form of contraction on average, hence the strong convexity condition is needed.
with 3 > 1 jointly indicate that ôR E[R(Z,) 1, which is
Similarly to Theorem 3, in order prove this result, we first obtain a nonasymptotic Wasserstein convergence bound between (11) and n, stated as follows:
7

---

Online SGD, /7
Offiine SGD, /?= 0.01
Sample Quantiles
Semple Quantiles
1020
Gaussian Quantiles
Gaussian Quantiles
Figure 3: QQ-plots of ID linear regression experiment. Left: Online SGD exhibits heavy-tails. Right: Offline SGD with varying n; larger exhibits heavier tails.
Theorem 6. Under the setting of Theorem 5, the following holds with probability greater than Exp
WI(n, n (1)) S coL. 1 1 8R
Wi Wi(Hz, )
with co B1|lX]" [] + where x T()).
The convergence rate implied by Theorem is implicitly related to the finite moments the data- generating distribution μlz. Using the results of [FG15] (Lemma in the Appendix), we can determine the convergence rate т, where with high probability it will hold that WI(T, π (1)) On with r E (0, 1/2]. Let the data have finite moments up to order q. Then, for example, q 4d, we get r 1/2, i... the fastest rate. As another example: if d > 2 and 3, we obtain rate In other words, the moments of the data-gennrating distribution determine whether we can achieve dimension-free rate or fall victim to the curse of dimensionality. Thus, if the data do not admit higher-order moments, our results show that we need large number of data points be able to observe power-law tails in offline SGD.
1/d.
4 Experiments
In this section, we support our theoretical findings on both synthetic and real-world problems. Our primary objective is to validate the tail behavior of offline SGD iterates by adapting previous online SGD analyses [GSZ21, SSG19), in which the authors investigated how heavy-tailed behavior relates to the step size y) and batch size b, their ratio n/b".
4.1 Linear regression
Experimental setup.
Batch
Batch size:
Batch 20
In the linear regression examples, we examine the case with a quadratic loss and Gaussian data. In this simple scenario, was observed that online SGD could exhibit heavy- tailed behavior [GSZ21]. The model can sum- marized follows: with initial parameters Xo N (0, o La), features a, N (0, La). and targets
0.4
6393
158
352
10
20
50
100
200
500
10
50
200
500
10
20
50
100
200
500
n
Figure 4: Estimated tail indices difference
V: a; X, N (a, X,, o3), for 1,..., n. and a,, a. σy 0. In our experiments, fix 100. and simulate the statistical model to obtain {a; y1 ==1-
G. o, 3, use either
In order to examine the offline version of the model (i.e., for offline SGD), we utilize a finite dataset with points rather than observing samples each iteration. We then analyze the same experimental setting with an increasing number of samples n and illustrate how similar heavy-tailed behavior emerges in offline SGD.
The code scripts for reproducing the experimental results be accessed
ht.

---

MNIST data
CIFAR10 data
Layen.1
L 2
Layer
Layor:
Layer
Layer
Dala %:
0.25
15
0,50
0.75
1.00
1.0
0.00
0.02
0.04
0.00
0.02
0.04
0.05
0.02
0.04
0.00
0.02
0.04
0.00
0.02
0.04
0.00
0.02
0.04
r/b
ryb
4/b
g/b
///b
n/b
Figure 5: Estimated tail indices for 3-layer fully connected NN
Preliminary tail inspection. We begin by analyzing how the tail behavior differs between online and offline SGD (with varying n in the latter). Specifically, in Figure 3. we depict a 1-dimensional linear regression task by analyzing the QQ-plots of the estimated stabilizing distributions after 1000 iterations. We observe that online SGD with a sufficiently large 1) exhibits heavy, non-Gaussian tails, underscoring the prevalence of heavy tails even in such simple scenarios. Furthermore, we also observe that offline SGD exhibits increasingly heavier tails as the sample size n increases, as our theoretical results suggest.
Tail estimation. We now set d 100 and run the corresponding offline and online SGD recursions. We then use a tail-index estimator [MMO15], which assumes that the recursions both converge to an exact heavy-tailed distribution. While this is true for online SGD due to Theorem 1, offline SGD will only possess approximate heavy-tails, and the power-law behavior might not be apparent for small n. Hence, for small n, we expect the estimated tail index for offline SGD will be inaccurate and get more and more accurate as we increase n.
We illustrate this in Figure 2, in which we plot the range of estimated offline SGD tail indices (marked in green) corresponding to 10 random initializations, while varying n and rj. We can see that, across all learning rates, the variance of the tail estimation decreases increases and that the estimated values get closer to the estimated tail index for online SGD (marked as the horizontal blue line).
Further analyses. We now run online and offline SGD recursions, varying 1) from 0.001 to 0.01, from 1 to 20, and n from to 500. Each hyperparameter configuration is run 1600 times with distinct initializations, yielding 1600 estimated samples from the stationary distributions, used to estimate the tail indexes. In order to estimate the tail-indexes a (online SGD) and (x) (offline SGD) of the respective stationary distributions, we follow the procedure explained in [GSZ21]. Finally, in Figure 4, we plot the absolute difference of the estimated indexes, (a!") - â].
We find that larger number of data samples leads smaller discrepancy between the online and offline approximations across all batch sizes and step sizes 17. This trend is consistently observed. Moreover, observe that larger values of lead smaller discrepancy on average, across all The conclusion here is that, as n increases, the power-law tails in offline SGD become more apparent and the estimator can identify the true tail index corresponding to online SGD even for moderately large n, which confirms our initial expectations.
4.2 Neural networks (NN)
To test the applicability of our theory in more practical scenarios, we conduct second experiment using fully connected (FC) NNs (3 layers, 128 neurons, ReLU activations), as well larger architec- tures, such as LeNet (60k parameters, 3 convolutional layers, 2 FC [LBBH98), and AlexNet (62.3M parameters, convolutional layers, 3 FC (SH17) The models are trained for 10, 000 iterations using cross-entropy loss on the MNIST and C1FAR-10 datasets. We vary the learning rate from 10-4 of the training data.
4 to 10-1, and the batch size b from to 10, with offline SGD utilizing 25%, 50%, and 75%
We proceed similarly to the linear regression experiment and again replicate the method presented in [GSZ21]: we estimate the tail index per layer, and plot the corresponding results, with different colors representing different data proportions (1.00 indicates the full data set). The results for the fully connected network are presented in Figure 5 (on CIFAR-10 & MNIST), LeNet (on MNIST)
For completeness, LeNet further uses subsampling layers.

---

2,5
Leyer:
Leyer:
Layer. 3
Layer
Layer: 5
Data
2.0
0.25
8
0.50
1.5
++
0.75
1.00
1.0
0.00
0.02
0.04
0.00
0.02 W/b
0.04
0.00
0.02 n/b
0.04
0.00
0.02
0.04
0.00
0.02 r/b
0.04
//b
r/b
Figure 7: Estimated tail indices, LeNet, MNIST
in Figure and AlexNet (on CIFAR- 10) in Figure 6. The LeNet CIFAR- 10 and AlexNet MNIST results can be found in the Appendix D.
Our observations show that the estimated ((m) has strong correlation with á: using reasonably large proportion of the data enables to estimate the tail index that is measured over the whole dataset. Moreover, although the dependence of a((n) on T//b varies between layers, the measured (n)'ss correlate well with the ratio n/bb across all datasets and NN architectures While our theory does not directly cover this setup, our results show that similar behavior is also observed in more complicated scenarios.
Layer:
Layer:
Layer:
Layer:
2.5
2.0
Data %:
1.5
0.25
Layer: 5
Layer: 6
Layer: 7
Layer:
2.5
0.75
2.0
1.00
1.5
0.000
0.025 n/b
0,000
0.025 n/b
0,000
0.025 n/b
0,000
0.025
n/b
Figure 6: Estimated tail indices, Alex CIFAR-10
5 Conclusion
We established relationship between the data-generating distributions and stationary distributions of offline and online SGD. This enabled us to develop the first theoretical result illuminating heavy-tailed behavior in offline SGD. We extended previous results encompassing both quadratic losses, as well as more sophisticated strongly convex loss functions. Through an experimental study, we validated our theoretical findings in a variety of settings.
Limitations. There are two main limitations to our work. Firstly, our analysis focuses predominantly on the 'upper' tails of the distributions. Studying the bulk of the distribution of the iterates may reveal new findings. For example, research in this direction could connect our findings learning theory by leveraging existing generalization bounds (e.g.. see Corollary 2 in [HSKM22] for link between 'lower' tails and generalization error). Secondly, it would be of great interest to extend our results to the non-convex deep learning settings. Finally, since this is theoretical paper studying online and offline SGD, our work contains no direct potential negative societal impacts.
Acknowledgments. We thank Benjamin Dupuis for the valuable feedback. AD would like to thank the Isaac Newton Institute for Mathematical Sciences for support and hospitality during the programme The mathematical and statistical foundation of future data-driven engineering when work on this paper was undertaken. Umut Şimşekli's 's research is supported by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d' l'avenii" program, reference ANR-19 1-03 (PRAIRIE 3IA Institute) and the European Research Council Starting Grant DYNASTY 101039676.
"hhe monotonic relation between the tail exponent and the n/6 ratio line with findings from [GSZ21], although new findings (see Sec.6.6 in [ZLMU22]) point out that a mere dependence on this ratio has been found broken. We believe that for other ranges of the parameters (outside of the ones originally used in [GSZ2I]). different behavior could be observed.
10

---

References
[BDM* 16] Dariusz Buraczewski, Ewa Damek, Thomas Mikosch, et al. Stochastic models with power-law tails. The equation X= AX+ B. Cham: Springer, 2016.
[Bog06] VI Bogachev. Measure theory (second volume), 2006.
21] Melih Barsbey, Milad Sefidgaran, Murat A Erdogdu, Gael Richard, and Umut Simsekli. Heavy tails in sgd and compressibility overparametrrized neural networks. Advances in Neural Information Processing Systems, 34:29364-2999 29378, 2021.
[BMMP12] A. Benveniste, S.S. Wilson, M. Metivier, and P. Priouret. Adaptive Algorithms and Stochastic Approximations. Stochastic Modelling and Applied Probability, Springer Berlin Heidelberg, 2012.
[CGZ19] Bugra Can, Mert Gurbuzbalaban, and Lingjiong Zhu. Accelerated linear convergence of stochastic momentum methods in wasserstein distances. In International Conference Machine Learning, pages 891-901. PMLR, 2019.
[DD220] Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and markov chains, 2020.
[DMN+21] 21] Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, Kevin Scaman, and Hoi-To Wai. Tight high probability bounds for linear stochastic approximation with fixed stepsize. Advances in Neural Information Processing Systems, 34:30063-30074, 2021.
[FG15] Nicolas Fournier and Arnaud Guillin. On the rate of convergence in wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162(())707-738, 2015.
[GSZ21] Mert Gurbuzbalaban, Umut Simsekli, and Lingjiong Zhu. The heavy-tail phenomenon in sgd. In International Conference on Machine Learning, pages 3964-3975. PMLR, 2021.
[HM21] Liam Hodgkinson and Michael Mahoney. Multiplicative noise and heavy tails in stochastic optimization. In International Conference on Machine Learning, pages 4262-4274. PMLR, 2021.
[HSKM22] Liam Hodgkinson, Umut Simsekli, Rajiv Khanna, and Michael Mahoney, Generalization bounds using lower tail exponents in stochastic optimizers. In International Conference on Machine Learning, pages 8774-8795. PMLR, 2022.
[KSH17] Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convolutional neural networks. Communications of the ACM, 60(6):84 90, 2017.
[LBBH98] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278 2324, 1998.
[LW$22] Soon Hoe Lim, Yijun Wan, and Umut Şimşekli. Chaotic regularization and heavy-tailed limits for deterministic gradient descent. arXiv preprint arXiv:2205./1336 2022.
[MM19] Charles H Martin and Michael W Mahoney. Traditional and heavy-tailed self regular- ization in neural network models. arXiv preprint arXiv: (t0:://90000000 00276,, 2019.
[MM015] Mohammad Mohammadi, Adel Mohammadpour, and Hiroaki Ogata. On estimating the tail index and the spectral measure of multivariate a-stable distributions. Metrika, 78(5):549-561, 2015.
[PZ19] Victor M Panaretos and Yoav Zemel. Statistical aspects of wasserstein distances. Annual review of statistics and its application, 6:405 431, 2019.
[RBG+22] Anant Raj, Melih Barsbey, Mert Gürbüzbalaban, Lingjiong Zhu, and Umut Şimşekli. Algorithmic stability of heavy-tailed stochastic gradient descent on least squares. arXiv preprint arXiv:2206.013 2022.

---

[RZG$23] Anant Raj. Lingjiong Zhu, Mert Gürbüzbalaban, and Umut Şimşekli. Algorithmic sta- bility of heavy-tailed sgd with general loss functions. arXiv preprint arX1v:2301.11885. 2023.
[SCW20] James Stewart, Daniel K Clegg, and Saleem Watson, Calculus: early transcendentals. Cengage Learning, 2020.
I$GN+ 19] Umut Şimşekli, Mert Gürbüzbalaban, Thanh Huy Nguyen, Gaël Richard, and Levent Sagun. On the heavy-tailed theory of stochastic gradient descent for deep neural networks. arXiv preprint arXiv: 1XXiv:992,,0018, 2019.
[SSDE20] Umut Simsekli, Ozan Sener, George Deligiannidis, and Murat A Erdogdu. Hausdorff dimension, heavy tails, and generalization in neural networks. Advances in Neural Information Processing Systems, 33:5138-511 2020.
[SSG19] Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise deep neural networks. In International Conference on Machine Learning, pages 5827-5837. PMLR, 2019.
[Vi109] Cédrie Villani. The wasserstein distances. In Optimal transport, pages 93-111. Springer, 2009.
[ZFM 20) Pan Zhou, Jiashi Feng, Chao Ma, Caiming Xiong, Steven Chu Hong Hoi, et al. Towards theoretically understanding why sgd generalizes better than adam in deep learning. Advances in Neural Information Processing Systems, 33:21285-21296,, 2020.
[ZLMU22] Liu Ziyin, Kanggiao Liu, Takashi Mori, and Masahito Ueda. Strength of minibatch noise in sgd, 2022.
12

---

Approximate Heavy Tails in Offline (Multi-Pass) Stochastic Gradient Descent
APPENDIX
The organization of the appendix is as follows:
In Section A, we provide the background material required for the proof methodology.
In Section B, we present technical results used to conclude the results of our work.
In Section C, we give the proofs of Theorems 3-6.
In Section D, we provide additional experimental results.
Section E, we justify the tail estimator choice.
A Additional Technical Background
A.1 Existing results
Lemma (Explicit solution of Wasserstein distance (PZ19]). Let pl, E P(R) be two probability measures on IR, and denote their cumulative distribution functions by F1(x) and F2(1) respectively. Then, the Wasserstein-P distance between fan and μzz has explicit formula:
Wp (11.H22 = (L (T -3))
1/p
dg
where FT1 and F-1 denote the quantile functions. In the case when p by applying the change of variables, one can obtain the following:
W1 (W1,H22 = / |F((z) - F2(x:) dx.
Now, for 9 > 0, 0,7 > 0 and μ E (R2.. let:
M₂(u)= := / [z]'m(dx) and (a)( := =/- e p(dx).
Furthermore, consider an i.idd sequence (Xx)a21 of p-distributed random variables and, for n 2 1, define the empirical measure by:
X
We can now proceed to state the following result.
Lemma 2 ([FG15)). Let μ E P (IR)) and let p >> O. Assume one of the three following conditions:
(1) a > p,7 > 0, E (u) < 00,
( (0,p). > 0, Ea,7 < 0o.
(3) > 2p, Mg
Then for all n 2 1, all x E (0)
W ( 11) 2 x) S <a(n,))) + b(n,2))
where
exp
(-enx²)
ifp > d/2
a(n,z) C exp
(-en(x// log(2 1/2))²
ifp d/2 ifp E d/2)
exp (-cnx"/9)
and
exp (-enxxr/p) 1 (2>1}
under (1),
b(n,v)=C exp (((()))))))))))))))))))) (a-E)/)) 1 ((si) + exp (-c(nz)o/1) 1 (x>1)
Ve (0, a.) under (2),
n((x))(9-<))
We E (0, q) under (3).
The positive constants C and e depend only on p, and either on a, Y, (p) (under (1)) or on a, 7i (p), (under (2)) q, My( (H), (under (3)).
13

---

B Technical Lemmas
Lemma 3. Let X and Y be two random vectors in R.. Then, we have
W1(2(X), (2))))))))
(17)
Proof. By the definition of the Wasserstein distance, we have that
inf [ jxax
(1() TET(2(X),
||x (),d>(a,
(18)
| w/|dy" (x,, v),
(19)
JR
where 7 is the coupling that attains the infimum (the proof of the existence of such coupling for any Wasserstein-p distance, where p 2 can be found in, e.g. [Bog06, Theorem 8.10.45)). Then, by the reverse triangle inequality, we have
(x)
>| 11lll (2,
(20)
JRd XRd
|r - vl d (z,, v):
(21)
JR xR+
where 7 R2d x TRd F x R is the map (2r + (1|=]). ||/ll) and T#7 * is the pushforward
measure such that for measurable set B R4 1R,, we have 7 (B) 7 7 (B)) As T is a coupling between ||X] and || we have that
inf W1 (1() (I x4x2,
l ye d)(
(22)
(23)
This concludes the proof.
C
Proofs
This section contains the proofs our theoretical findings.
C.1 Proof of Theorem 4
Proof. First, note that the unique stationary distributions of (X))220 and (x(")) k20 are denoted respectively by ı and (")), Denote by En the event on which (x(")) )az0 has stationary distribution (n) such that )(E.)) 2 in the Wasserstein sense). Given En, let (Ak; A (1)) )x21 and (bx, bj Ja21 the sequences of i..d. optimal couplings for μa and y' /bb and Hib (m) respectively. Therefore, by construction, for any & E N. E| - A WI(HA, (()), and E|[[b; - b
(where E [0, 1] is the probability that (x )xzo is not ergodic,
(m) ||] WI(Mb, ())). Based
on these two sequences, we consider the processes (Xa)a20, (X )220 (Ye)a20 defined by the recursions:
X4+1 = (la-nA++1)a + + where Xo ~ n
(Ta ( k+1 (x(")) + +/bbb))
(n)
(n) where x-")) (x))
2. x
3. Yet1 = (Ia-nAx+1)* Y + 7/b+11 where Yo = =
Note that (Xx)x20 corresponds the online SGD recursion (7), and (Xx")) )=20 to the offline SGD recursion (9). In addition, since these two Markov chains are started at stationarity, we have:
W, (T, (")) W (Z 2xx())
w, (
Vk.
14

---

With these definitions at hand and this observation, using triangle inequality, we can obtain:
WI(n, (1(2((s),
S +
Now, by [GSZ21, Theorem 8), we have that Y& is geometrically ergodic with respect to its stationary distribution n, i.e., there exist constants Cp > 0. P E (0, 1) such that the following inequality holds:
m)( S ( me pk for any 2 0.
(24)
Therefore, we have:
W1 WI(T,T((1) S (T, (1
as (xx) = terms, we get W (T,, )1 - pk) V (1(E(()), implying:
S W (Y))). Rearranging the above
Wi(T, S (1 -g (1--)
(25)
To bound the right-hand side of (25), we consider the following difference by using the recursion definitions:
Yk+1
x k+1
Yx 7/44 YE + 1/44111 x(") + A (n) x(") - -yb (m) 1+1
(26)
(I - x(() - A (a)
k41 1+1 x (bb+1 b(()). (27)
Writing out the recursion, we can obtain:
Y++1
k+1 (Yo -x("))
(n)
(La An411)
i=0
k+1
X (1) (A
1+1)
(n)
II j=i+2
(La nA,)
k+1
+
(bi+1 - b (2)
II j=1+2
(Ta -
1=0
where for any sequence (a:).20. we let II; a, = when Now, taking the norm of both sides, using the triangle inequality, and taking expectations given En, obtain:
B[|l Yk41 x(22 III < E|I x(())
(la A
+ n
|x (x. A11
A
(n)
II (L--
(28)
j=i+2
k+1
+ 1
[[bb411
b(a))
II
0
j=
15

---

We shall now analyze each of the three summands separately. For the first term in (28), as we start with Yo- =xO") equals zero. For the second term in (28), we have:
&
h-1
n
(A,+1 A
(+1)
(2)
II (L.
-Al)l
())
k+1
B|||X (Ai+1 A
(1)
(n)
II (Le Ab)Al
2m0
(b)
X|||X (m)
(A:+1
A (2)
-1
(c)
< 17
[BI 10 (9)
2 - II -
1=0
where (a) follows from the linearity of expectation, (b) follows as A...... A.-1 are i.i.d and independent from Ag...., A , and (c) is obtained by applying the Hölder's 's inequality, where
and q are such that 1/p+ 1/q 1, with p. 9 E (1.+) q a and p d/2 (used later in the proof), where ar is the tail index.
As the chain (x(")) )x20 starts from its stationary distribution x (1)), have that (B[II 19)) (+)
k+1 (E[IIxX))) (*) ([)) Vi. Using the fact that (A, A, Y=1 are i..dd random variables (the randomness
arises from the empirical measure P B
L A | and 1, we have that:
AΛ = Ell La A |I] < 1.
(29)
Therefore, we can obtain the following bound:
R+1
n
X (n)
(A:+1
(n)
II
(Ta A1)
1=0
f=1+2
(B[II
A 1PT) Σ
EE-1 La
E
A
S (EIII (E]]IA) A
11)
1- 5A
where the last equality follows from (29) and the power series sum formula. Using the same arguments, we can bound the third term in (28):
1+1
[[(b+11 (())
II (La-nA,)ll < nB bfn) |1] 1 1-
1
j=i+2
Combining the above, we can obtain that:
E| Yk41 x (m)
< n7 [E|IIx) (x)
(m) ( (EIIAA - 1n PPT)
1
+ rE[[ [1 - b("h (n) ||]
1- 6
1- 8
17
(19) - A 1P))
+ BBllb - b,"h (m))))
1 5,
(1[1)x[(1119) (B]IIA, A (P)) (B[llb: bbah (1) (p))
1 8A
(E[])x((*119) W (o(AA (m)) + Wp(mb.H(.)
(30)
1 8A
1)
(((E]))X(()) [1)) + 1)W (.W.(AAD.P... Rb))
(31)
1 5A
where the penultimate inequality follows from Jensen's inequality: it implies that W Wp v) < W w),,,v), for p S q (see, e.g.. [Vi109]). The last inequality follows as (p(AA.Ha) (n)) S (n) W (b) and W Wp(Mb, (()) S Wp(HA,b, (n)). Together with (25), we have:
16

---

Wi WI (m) (
"0 19)
1)(1 -pe-- " W Wp(HAbb,/AAb)
(m)
By taking the limit as k + oo, we can conclude the proof of Theorem 4.
C.2 Proof of Theorem
Proof. Using results from Theorem 4, we now proceed to bound the Wasserstein-p distance between the probability laws of A₁ and (""). Reminiding ourselves that each element in the i.i.d. sequence (ax)k2) follows N(0, T²Ta), we denote this measure with Pa- Correspondingly, we denote its
empirical measure with jAo (xt)
= nn Σ)=1 Say Given E,, we let (ak. 0x (nt) )k21 be the sequence
of i.i.d. optimal couplings for Ha and pa so that by construction, for any &o E N, (Billox
a (10))))) W20 pba)). Now:
Wp(mA,PA (w) s (Bll E
Caa
1
Laaa
asa 1'7)
b
iE
jEN(")
b(Bill(aaa T (n) (n)T (1P)))/
di
(Blllaaa a111 (n)) + ta (x)T a di
(n) 111) (P)))
s (B[laaaa 0iai "ia|")] (n)T 11') 1/8 + (Blllaia))) Tn) "l"0 (n)T 1 T
(n)
(B[[|a]||)|) ai" (PT) 1/1 + (Billa, (n) ||]|a at (r)) 1/2
||]||11)3)))// + (Eilla) (m) 1 (Billa: - a | 12)))//22
where (a) follows from Minkowski's inequality and the fact that (0x) are i.i.d. random variables, well (a (a(")) )221 Inequality (b) follows due Minkowski's inequality, and (c) follows using the generalized Hölder's inequality with 1/2p + 1/2p = 1/pp
Now, we can proceed utilize Lemma 2 and (30). In order to apply Lemma 2 to the difference of measures between A and A (m) (i.e., between a and aj (*)), as E [19//// | < oo for all y < a, we require and 1/p + 1/q (due to Hölder's inequality).
First, we select p large and q small enough for both g < and p d/2. Now, in order satisfy the requirements of Lemma 2, set 6"
V nCI
log
1cr Ç This choice allows us obtain that, with 222 W2p par)) E". Therefore, we
probability greater than 1 C/2, (Billa) (n)
have that, with probability greater than 1 - 2/2:
1
4c Onn11/2)
where the positive constants C1 and depend only on p. d, May- Therefore, with probability greater than C/2: (Billa) af(h) 11
log
nC1
<
(B]IAA - A A 12)a/ < ((B|]ai||30)) + (Bllla (n) 1010))))))))
1121))
4cr nC log
= C2n 1/2
C3 log
(32)
5"
with C2 = V J ( 1221) + (Eilla) (m) 1(27)) and C3 = 4c
In order bound | blm) 1 V/, can apply Lemma 2 again obtain constants C4 and cs such that, with probability greater than 1 - 2/2:
[b b 1P < Can 1/2 log C
On 11/2).
(33)
17

---

Using (32), (33) with Theorem 4 (see (25) and (30)), and denoting C. = C2 C2(B[IX]] +2 C₁
and e7 = max(c3. C3. 6s) we can obtain, with probability greater than 1 - Ç:
WI(T,
7 - --o Co
log
C7
n 1/2
(34)
Therefore, we obtain that, with probability greater than 1- Ç. W (T,, n (1) -0 (12
WI(T,, Due to [GSZ21] we have sim P X=x1 > 1) E (0, oo). Now, let O. Then, there exists to s.t. for all I. 2 lo. [|S X > 1) S for some E (0, oo). From (34), we know that with
probability greater than - Ç. there exist constants éi 62 such that WI(T, (1)) S Ei Vlog 2n
Now, using Lemma 3, we can obtain that, with probability greater than 1 En Ç:
é log 6 1
< 1/22 2 W1 WI(T, (!))
| > - P( > 6) | de
| > 8) 1 > E) dt.
where we have used that lim Xo] > t) = 0 and lim P( P(| (() | > t) = 0. in order to
select t' and t" large enough for the last inequality hold. Now, we have that
l C-E di
[" P( > 1) di
o( > 1) - P( 1) di 2
1r ta
"
(c (c-c) (t" -("--'")((IX("" > t').
2 (t" - t)
(tr)aa
Therefore, by choosing t" = 2t', we can obtain:
P P t') c-c Gi
6 Ç
log
(35)
(1)aa 1/2
Similarly, for any > O and / >> lo, we have X > 1) - e + e, and using similar arguments we obtain:
G v log &
2 /" P(I > 1) f) dt 1" c+c
dt
S n//22 v
_ to
2 (1" -') > 1n) - -I"" - 1') c+c
(1)pa
Finally, choosing as before t" = 2t', we can obtain:
c+ &
log E2
P( 2t)
(36)
(t')a
1/21/2
Substituting for 7- 26', we can obtain:
2 c
20 1/2
PIXS 1)
log C
(37)
aa
Combining (35) and (37), we obtain that with probability greater than 1 1- En, for any e >>> 0 and
t t> lo:
1 c-- ci
P(I| 1)
log
and
(38)
2a 1or
l/?
tn
P( ( > 1)
2a
C+E
+
2c
2 log
(39)
ta
1n-
This concludes the proof of Theorem 3.
18

---

Proof of results in Section 3.2
Let us now consider setting where f(;, 2) is not necessarily quadratic function. As before, we assume the data comes from an unknown data distribution /zz on Rd+1 Furthermore, with (2 (n) )x21,
denote the i..d. random variables associated with the empirical measure μ (n) n-- Σド= 6 2()) as defined in (15). We consider the case b = 1 for simplicity.
C.3 Proof of Theorem
Proof. First, we utilize the tail index limits from [HM21] in the strongly convex setting from Theorem
2. We use a and &3 in order to construct the proof and provide the same argument as in Section 3.1.
Denote by E,, the event on which (x (x("))
& 222 has a stationary distribution x ((n) such that P(F..) 2
1 En- Given E,, let (Z 2((x) Therefore, by construction, for any k E N. [BIl - nnd II] W1 (M2, )) Based on this sequence, we consider the processes (Xx))200 (X )a20. (Yx 2220 defined by the recursions:
1:21 be the sequences of i.idd. optimal couplings for μı, and vla))
1. X8+1 Xx -X/ R. ZR+1), where Xo
2. x(n) 1+1 = x - -n (m) 2004)) ). where x(") ~ T (n),
3. Ve+1 = YE SVV,, 11) where Yo = =x(")
with the unique stationary distributions of (Ne) and (x(")))20 )x20 being denoted by and (n) respectively. Note again that (Xx)a20 corresponds to the online SGD recursion (2), and (x ) to the offline SGD recursion (4), both with b = 1. Under our assumptions, by the definition of geometric ergodicity, there exist constants Cp > O and p E (0, 1) such that the following inequality holds:
W (2I( S (c
de pk. for any k 2 0.
(40)
Analogously to (25), we can conclude:
Wi(n, (*) (1 cpe -
(41)
The proof then utilizes Taylor's expansion with the remainder part in integral form (see, e.g., (SCW20]) in the following way:
(V(E,, - V((x("), ,) H x("))
(42)
with H!! = So V2 22f(Y, u(Ya x(()), 2) du. Therefore:
Y k+1 = Y2 x("") - 17 (V](V,. Ze+1) - V -1711)
Ykx x(m)) (m)
(V)(Y, Zx+1) - vx(x
(x) k -x++1) + vf(x(() (n) Zx+1) - Vf(X (2(21) (n)
YY= X (n) (m)
k,t (Yr- -x(x)) (VS(x(")) (n) (Z+z)) VS(X (
(I. n (m) )(r x(())) -n 17 (vf(X(") Zz41) - ( 2
Now, taking the norm of both sides and using the triangle inequality together with Assumption 1, we obtain the following:
Y x(()
< | Ia H (n)
k. |11| x((0) 1 ((X
$ || la ((()
k, |11|/ - x("))
(n)
1 " 1)1l 2(n) 1|.
19

---

Now,
|| la 11 ( V2i(y u(v- - x) dull =
La 11= /2v
u(y - x), z) dull
0
Ta V/ f2y
uly - x), 2) || du
SUPPER
V (r, 2) du
R(z);
(43)
where again R(z) supxezd (2 2)
This allows us to conclude the following:
|| -x(1) || & R(Zx+1)]|V x( +| n x + 1) -2441
Denoting ((d0) = x
|1) || 1, we have:
|Y4+1 x (m)
b+1l S R(Z x( 10 BL (1) | -
R[(Z++ (R(Z++))B(Zz)) YK-1 x + nLR( /B
(m) || 2 + +nLBB
(1)) 12 ((1)
$ 11 x 1+1
k.
R(Z,) + n Σ B 1
||
2/11 II R(Z,+1),
jmi+1
where again, for any sequence (a,)220, I1, 44 1, for j k. Furthermore, as > and [] = 1, we have:
: E[R[I] < 1.
(44)
Now, we can take the expectation given En and use that Ri ((.,)...., (R(2k-1) 1). and B6n)) ..... B(a))
are i.i.d. Furthermore, using (43), (44), and proceeding as the proof of Theorem 4, we can obtain:
(1) E[[|Y++1- k+1 |II
< XEIII (m)
I) (1) 1
8R
Finally, denoting [|[| " [
Co. we obtain that, with probability larger than 1 Gn
Wi (n)) v coL(1 epe pk)cpp))p-)) 7
Wi(Hz,
1- ÖR Taking the limit as l co, conclude the proof of Theorem 6.
C.4
Proof of Theorem 5
Proof. Due [HM21] we know that there exist a, such that 3 a and:
lim sup teP oz > t) O, and lim sa 8P (o) || > < toc. t0000
(45)
t-000 Using Lemma 3, we can obtain:
WI(T,((1)) >
X( > 6) P( > t) dt
PP[ || > t) PI (m) > t) | dt,
where we have used that lim x t) and lim P ( (m) t) in order to
select t' and t" large enough for the last inequality to hold. Now, using Theorem 2, we can obtain:
|P|||= > t) P(I > t) > '" Ca di f P((IX(") > t) de
tote
2 (t" 1') (1"raatee (t" - (')P((IX!)) 1'),
Co
(46)
20

---

for some constant Ca. Therefore, by choosing t" = 2t', we can obtain:
P|
Ca
Wi W (T, (n))
(2
t'
Using similar arguments, obtain:
/' P(I 1) dt ft c3
W1( 2
18-r dt
2 (L" - 1'P((I) > 1") - (1" - 1rpppppe
Cp
for constant cp. Choosing (" = 21' and substituting 1 = 1', we obtain:
20
- E) - WI(T, (()) + 88-c
(47)
Using Theorem 6 and (46)-(47), we can conclude the proof of Theorem
21

---

2,5
Leyer:
Leyer:
Layer 3
Layer 4
Layer:
2.0
0.25
0.50
1.5
0.75
1.0
1.00
0.00
0.02
0.04
0.00
0.02
0.04
0.00
0.02
0.04
0.00
0.02
0.04
0.00
0.02
0.04
n/b
W/b
n/b
n/b
r/b
Figure 8: Estimated tail indices, LeNet, CIFAR-10
Layer:
Layer:
Layer:
Layer:
2
0.25
Layer: 5
Layer:
Layer: 7
Layer: 8
0,50
0.75
18
2
1.00
0.000
0.025 n/b
0.000
0.025 n/b
0.000
0.025 n/b
0.000
0.025 n/b
Figure Estimated tail indices, AlexNet, MNIST
D Further experimental results
In this section, we present the remaining experimental findings.
D.1 Neural Network Experiments
First, we showcase the remaining plots from Section 4. As outlined in 4.2, we conducted model training for 10, 000 iterations, utilizing the cross-entropy loss and employing the MNIST and CIFAR- 10 datasets. The learning rates ranged from 10-4 to 10-1, while the batch sizes varied between 1 and 10. We employed offline SGD with subset of the data amounting to 25%, 50%, and 75%. In Figure 8, we exhibit the estimated tail indices for the LeNet architecture with the CIFAR-10 10 dataset, while Figure shows the estimated tail indices for the AlexNet architecture implemented with the MNIST dataset.
The inclusion these plots serves the purpose of completeness, as the overall conclusions remain unchanged; strong correlation between ((m) and â is exhibited, well as notable correlation between å (s) and the ratio n//b. These conclusions hold true across all datasets and neural network architectures, providing further substantiation for our theoretical propositions.
D.2 Further tail examination
From [GSZ21], we have that P (I|-x >) = t- the log-log tail histogram of the stationary distribution should follow linear line with slope -a in the tails (for large (). We first examine the histograms of the estimated stationary distributions for both linear regression setting (as in Sec. 4.1) and the NN setting (as in Sec. 4.2), analyzing their behavior as the number of samples increases. These are depicted in Figures 10-11. Then, we re-run the experiments and examine the histograms log-log scale cases, as n increases, we observe that this heavy-tailed phenomenon becomes increasingly apparent, and the tails follow clearer linear trend. The linear behavior in the tails can be observed in Figures 12-13.
whether the linear slope -a becomes more apparent. For both
In the entirety of our experiments, encompassing diverse learning rates and layers within both the linear regression and NN settings, consistent observation emerges: an increase in the number of samples employed in offline SGD leads to convergence of behavior towards that of online SGD. As previously mentioned in Section 1, while we do not anticipate an exact power-law tailed behavior, it is noteworthy that the tails exhibit progressively more characteristics resembling power-law
22

---

distribution. Specifically, the log-log plots demonstrate linear trend in the tails. This empirical observation aligns with our theoretical findings, again reinforcing the consistency between the two.
1000
0.2
100
0.2
100
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2,00
Figure 10: Histograms of the parameter norms for linear regression with Gaussian data
First layer
10
0.75
10
1.75
Second layer
10
10
0.75
1.0
10²
10
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
Third layer
10²
19
10
10"
10"
1.0
10
10
0.00
0.25
0.50
0.75
1.00
1:25
1.50
1.75
2:00
Figure 11: Histograms of the weight norms for FC on MNIST dataset
250
1000
10
10-1
107
20-2
10-1
10"
10-2
10-1
Figure 12: Log-log histograms of the parameter norms for linear regression with Gaussian data
23

---

First layer
Second layer
Third layer
10
Mu
% 0.5
10
% 0.75
10
% 1.0
n= 0.015
10
% 0.5
10
% 0.75
10
% 1.0
% 0.5
10
%
10
% 1.0
n= 0.04
10
% = 0.5
10
%
10
% 1.0
10
10
10
10
10"
10
10"
n
0.045
Figure 13: Log-log histograms of the weight norms for FC on MNIST dataset
24

---

E Estimator choice justification
Analytical computation of the true tail exponent, even in the linear regression setting, is, our knowledge, unfortunately not possible. There- fore, estimator choice is required. In this section, we provide our rationale for selecting the tail estimator from [MM015] by highlight- ing its strengths.
2
Estimate (&)
The main arguments are as follows: (i) the es- timator's theoretical framework established through its convergence in distribution to the true tail index (via a Central Limit Theorem re- sult, detailed in Theorem 2.3 [MMO15]), which further complemented by its demonstrated asymptotic consistency (as per Corollary 2.4 [MMO15]. (ii) The estimator has already been used in various articles and its qualities have been thoroughly examined. For example, this can be observed in Figure 14 (taken from [SSG19]), which, in our opinion, contains convincing estimation results (e.g., small error bars regardless of the magnitude of the true tail index).
0.5 0.5
1.5
True
Figure 14: Evaluation of the estimator from [MMO15]. Figure directly taken from [SSG19].
F Strongly Convex Problem Example
Consider the following one- mee-dimeniioal logistic regression where the regularization parameter Exp(p), i... follows an Exponential distribution with mean 1/μ its probability density function is as follows:
f(): ' A/P A A 0
x<0 0
As before, let (a;, g:)s21 be i.i.d. random variables in R such that z; (a;,q:) In this scenario, where a ~ N(O, x²) and y E {0, 1}, ), the loss function equals:
1
y) (1 (1--))_(1-o00+
ax 1 + A11==11
)
((x, = -yln
C--ax nar +
Now, the second derivative of the loss with respect the parameter equals (=( (ca=
Note that [ 2) 2² / ///44 Vz X. In the SGD case, from [HM21], have r(2)
lim inl | mmin (1~~> =)) and R(z) sup, V =)||- In other words, as we are the one-dimensional setting, we have:
a 20
r(2) lim inf
1 - 71
7A/, and
+00
(eav + 1)2
R(2) sup
1 >>
a e
max (1-7-,111-~1-7
72 1
a²
(ear 1)
Now, we require (r(( > 1)> and R[R(Z,) 1. As Far((p), we have that (P(((2))
1) > 0. For the latter condition, we can calculate the required expectation:
25

---

1/- (1 - (1-3A)pe-ml aa dd+ +
E >>
(7) 1) aA dd
(7 11) - -70 -0
c
y0
270 7 7- +1.
1
Furthermore, we have:
x²
x²
E
7 4
E
(1-7
(1
4 - 7Alue- 11 dd+ + E
( + - 1)me ndd
YP
1-222
22
+1 ?
yx
=
E
C7
4
20 x
27 11 x=a
yz²
B7
+
11
V2T02
2/
1 0²
7( /
++1
nV2 - G2P
We can see that, for example, both expressions are less than in modulus for = 0.1, o² 1, and 7 0.1. is important to highlight that the aforementioned calculations necessitate the condition 2 > 0, or cquivalently o² f < 2. This condition can be interpreted as stability criterion, indicating that the mean of the penalization term must increase as the variance of the data grows. In other words, larger variance necessitates higher mean value for X.
26


Reviews:
[{"review_id": "plgtdMfOH9", "reviewer": "Reviewer_VaqK", "summary": "This paper considers offline SGD and proves an approximate power-law tail behavior of the stochastic gradient for strongly convex objectives, confirming the heavy-tail heuristic encountered in practices. Explicit tail estimations are obtained, and as a intermediate result, nonasymptotic Wasserstein convergence results for offline SGD are proved.", "questions": "I have no additional questions.", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper provides a good analysis of the behavior of offline SGD, and contributes to our understanding of heavy-tail phenomena in SGD training.\n2. I have gone over the proofs and believe it's basically correct.\n3. The paper is well-written and comfortable to read.", "weaknesses": "I do not see apparent weaknesses in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your encouraging feedback and for taking the time to understand the paper clearly and go through the mathematical proofs. If any questions arise regarding our work, we remain at your disposal. "}, {"review_id": "qjBfwvS04a", "reviewer": "Reviewer_rBYn", "summary": "In this paper, the authors study the heavy-tail distribution for the parameters in offline stochastic gradient descent algorithm (SGD). Theoretical results are provided for a quadratic loss and a strongly convex problem, while numerical results cover more realistic cases such as fully connected NN or CNN. In the theoretical part of the paper, the authors link the tail of the distribution of the offline SGD to the online one. To be more specific, the authors show that the qualitative difference between the online and the offline tail is bounded by the Wasserstein distance between the generating and empirical distribution of the data. The author further bound the Wasserstein distance between the distribution of the online and the offline parameters by the same distance. The theoretical result is qualitatively supported by the numerical experiment.", "questions": "I believe that it would be nice if the authors could include results, expressed in numbers, which characterizes the difference between the experimental tail and a real power-law tail.", "limitations": "The authors adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Originality and significance: the authors extend the analysis of heavy tail in SGD from the online settings to offline settings. Personally, I find it really interesting of having a quantitative non-asymptotic bound of the difference between the two cases. It could make the existing and future online SGD analysis more relevant.\n* Quality: In my personal opinion, the authors perform convincing theoretical and numerical analysis.\n* Clarity: The paper is well written. The authors present their results in a self-contained way, with multiple examples and intuitions helping illustrating the idea behind their main results. And I appreciate that the code is attached to the paper.", "weaknesses": "It appears to me that the fig.1 and fig.3 are not as convincing as the rest of the paper. The axes are unlabeled in these figures. The fact that the distribution has a heavy tail is not very obvious in these figures. For example, to my eye, the n=250 histogram is more power-law comparing to the n=1000 histogram.\n\nThe weaknesses and questions are well addressed by the authors in their rebuttal. The authors provided detailed explanations and additional figures.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the encouraging feedback and valuable comments you provided. Moving forward, we will address your primary concern:\n\n> It appears to me that the fig.1 and fig.3 are not as convincing as the rest of the paper. The axes are unlabeled in these figures.\n\nWe have taken your feedback into account and therefore carefully labeled all the plots, aiming to improve the clarity and interpretability of the paper.\n\n>  The fact that the distribution has a heavy tail is not very obvious in these figures. For example, to my eye, the n=250 histogram is more power-law comparing to the n=1000 histogram.\n\nIn reference to the histograms in Figure 1,  our assertion is that with an increase in the number of data samples $n$ in offline SGD, the distributions exhibit characteristics of heavy-tailed distributions more predominantly. Specifically, we focus on a characteristic property of heavy-tailed distributions: as the tails get heavier, it becomes more likely to observe samples that can be far from the bulk of the distribution (this can be viewed as outliers in a sense).\n\nAccordingly, in Figure 1, we assert that the number of samples located far from the bulk of the distribution increases as the number of available samples $n$ increases. \n\nHowever, your argument regarding the clarity of the results remains valid. Therefore, we have re-run the experiments and introduced a new set of plots. In Figure 1, we highlighted the mean and mean+2std. of the distribution, as well as marked the samples which exceed the mean+2std threshold. With this, our aim is twofold: firstly, it can be observed that the mean and the std. of the distributions increase as $n$ increases. Secondly, it can be observed that the number of samples that exceed the mean+2std threshold increases, as well as their distance from the threshold. The added figures can be found in the attached PDF file in our response to all reviewers (Fig. 2(a)-(b)).\n\nRegarding Figure 3, we have conducted another set of experiments to provide a clearer analysis of the distributions’ tails. The corresponding plots can also be found in our response to all reviewers (attached PDF, Fig. 1). Specifically, we have run a 1-dimensional linear regression experiment for both offline and online SGD and plotted the corresponding QQ plots of the (estimated) stabilizing distributions. From this, one can observe that:\n* Online SGD with a sufficiently large learning rate exhibits heavy, non-Gaussian tails.\n* Offline SGD exhibits increasingly heavier tails as the sample size $n$ increases.\n\nWe hope that these new experiments offer further evidence supporting the notion that the distribution's tail becomes heavier as the number of available samples increases. \n\n>I believe that it would be nice if the authors could include results, expressed in numbers, which characterizes the difference between the experimental tail and a real power-law tail.\n\nAnalytical computation of the true tail exponent, even in the linear regression setting, is unfortunately not possible to our knowledge. As we cannot compute the tail exponent, we utilize the estimator from [1], which has been demonstrated to be an asymptotically consistent estimator (as indicated in their Corollary 2.4 in their paper): meaning that as the number of samples we use in the estimator grows, the estimated alpha value will converge to its true value. \n\nAs the same estimator has been already used in various articles, some of its qualities have already been demonstrated. We invite you to see [2], Figure 3(b), where the authors empirically demonstrate the accuracy of the estimator on a synthetic task, which we believe is encouraging. In our response to all the reviewers, we have included the aforementioned figure (see Fig. 2(c)), as well as further justification of the estimator choice.\n\nWe hope the new experiments and plots have effectively addressed your concerns and we remain at your disposal if there will be further questions. \n\n[1] Mohammad Mohammadi, Adel Mohammadpour, and Hiroaki Ogata. On the tail index and the spectral measure of multivariate α-stable distributions. Metrika,381 78(5):549–561, 2015\n\n[2] Simsekli, Umut, Levent Sagun, and Mert Gurbuzbalaban. \"A tail-index analysis of stochastic gradient noise in deep neural networks.\" International Conference on Machine Learning. PMLR, 2019.\n"}, {"review_id": "fplG6k5Tr9", "reviewer": "Reviewer_t9h8", "summary": "This manuscript considers the problem of multi-pass stochastic gradient descent with a finite batch-size and strongly convex objective. The key result is to show that when the stationary distribution of the parameters is heavy-tailed in the infinite data (one-pass) limit, then the stationary distribution of the finite batch limit is approximately heavy-tailed, in the sense of having a heavy-tailed component plus a correction depending on the 1-Wasserstein distance between empirical and population data distribution (hence decaying at worst as $\\sim n^{-1/2}$). The authors also present numerical experiments that suggest the relevance of this theoretical result to more practical settings.\n", "questions": "- **[Q1]**: As a reader who is not very familiar with this line of work ([HM21, HSKM22, MM], etc.) I wonder how to conciliate these results to the classical literature [Fabian 1968, Kushner 1981, Pflug 1986] showing asymptotic normality of the stationary distribution under certain conditions. For instance, considering online SGD in the simple least-squares setting. Since the gradient is proportional to the residual $r_{i} = y_{i}-\\langle a_{i}, x\\rangle$:\n$$\n  x^{k+1}  = x^{k} + \\gamma r_{k} a_{k}\n$$\n\nif the residuals are Gaussian close to the minimum (e.g. $y_{i}=\\angle a_{i}, x_{\\star}\\rangle + z_{i}$ for some $x_{\\star}$ and $z_{i}\\sim\\mathcal{N}(0,\\sigma^2)$), won't the stationary distribution be Gaussian? What I am missing?\n\n- **[Q2]**: Theorems 2 and 3 have an explicit dependence on the sample size $n$, but how do they depend on the batch size b?\n\n**Minor comments**\n\n- The following sentences are strong and misleading:\n> *Previous works on this problem only considered, up to our knowledge, online (also called single-pass) SGD, which requires an infinite amount of data.*\n\n> *However, all these results rely on exact heavy tails, which, to our current knowledge, can only occur in the online SGD regime where there is access to an infinite sequence of data points.*\n\nWhile it is true that in one-pass SGD the maximum number of steps is limited by the availability of data, this doesn't necessarily means that it requires an infinite amount of data. Note that the number of steps required generically depend on the task under consideration, and in some practical scenarios where data is abundant only a few epochs are required, see e.g. Table 2.2. of [[Kaplan et al. 2020]](https://arxiv.org/pdf/2005.14165.pdf). The authors even acknowledge this fact in L29-30.\n\n- Please add the details of the plots in the caption in Fig. 2 & 5: the reported tail indices correspond to what simulation?\n\n- L128: You mean $[n] = \\{1,\\cdots, n\\}$?\n\n**References**\n\n[[Fabian 1968]](https://projecteuclid.org/journals/annals-of-mathematical-statistics/volume-39/issue-4/On-Asymptotic-Normality-in-Stochastic-Approximation/10.1214/aoms/1177698258.full) Vaclav Fabian. *On Asymptotic Normality in Stochastic Approximation*. Ann. Math. Statist. 39 (4) 1327 - 1332, August, 1968. https://doi.org/10.1214/aoms/1177698258\n\n[[Kushner 1981]](https://epubs.siam.org/doi/10.1137/0319007) Harold J. Kushner and Hai Huang. *Asymptotic Properties of Stochastic Approximations with Constant Coefficients*. SIAM Journal on Control and Optimization, 19(1), 1981\n\n[[Pflug 1986]](https://epubs.siam.org/doi/10.1137/0324039) Georg Ch. Pflug. *Stochastic minimization with constant step-size: Asymptotic laws*. SIAM Journal on Control and Optimization, 24(4):655–666, 1986\n", "limitations": "I have discussed some of the limitations in the \"Weaknesses\" part.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Understanding SGD in its different flavours is an important problem in theoretical machine learning, and results on multi-pass SGD are scarce compared to the one-pass case. Therefore, the contribution is timely and significant. The technical part is sound. Moreover, the paper is well-written and the thread is relatively easy to follow: the motivation and goals are clearly stated and the main result addresses them. Finally, the numerical simulations supporting a broader scope of applicability are nice.", "weaknesses": "There are two immediate shortcomings of the work. First, the setting is rather restricted (strongly convex goals). Second, while the authors cite related literature connecting heavy-tails with generalization, this is not explicitly explored in the context of the paper. Overall, one question that remains in the end of the reading is: the stationary distribution of the weights are approximately heavy-tailed, but so what?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your in-depth review of the paper and the feedback you shared. In the following, we aim to respond to your concerns.\n\n> First, the setting is rather restricted (strongly convex goals)\n\nWe agree that considering strongly convex objective functions may seem restricted. However, this setting is in general privileged and considered interesting to study local SGD behaviour, even in the non-convex setting. As a result, analyses of stochastic optimization algorithms in strongly convex settings still attract significant attention, especially in under-examined contexts, such as ours. \n\nThat being said, we believe that it is possible to extend our results to non-convex settings, where loss functions satisfy the so-called “dissipativity” property. This condition would essentially let us obtain contractions in the Wasserstein distance and would include several practical settings such as NNs [4] and functions strongly convex outside a bounded region (see [3, Sec. 4] for more examples). However, we leave analyses of such objectives as future work as it would make the paper much more technical and jeopardize the clarity of our main message. We will mention this future direction explicitly in the next version of the paper. \n\n> The question remains: the stationary distribution of the weights are approximately heavy-tailed, but so what?\n\nThis is a fair question. As you mentioned, the connection between heavy tails and generalization has been established in certain “sterile” settings; however, an explicit connection for heavy tails in the sense of Thm. 1 and 2 is yet to be developed. Nevertheless, there has been empirical evidence that the tail exponents given in Thms. 1 and 2 may have direct links to generalization, (see [5, Fig. 2]). Hence, we believe that our results will play a key role in understanding generalization error of **offline** SGD, once the link between the tail exponent of **online** SGD and generalization is made explicit – which seems to be an easier task as several quantities can be computed more easily in the online setting. \n\n> [Q1]: … I wonder how to conciliate the results to the classical literature showing asymptotic normality of the stationary distribution... \n\nYou are right in your comment: **if the step-size is small enough**, the tail index $\\alpha$ will be larger than 2, hence admitting a finite variance. In such cases, one can show that the (properly) averaged iterates will converge to a Gaussian law, which is the main message of the papers you mentioned. However, there is a caveat: \n1) If the step-size is large enough, $\\alpha$ can be strictly smaller than 2, and the averaged iterates will converge to an $\\alpha$-stable law, where the studies you mentioned cannot be applied. This has been proven in [1, Corollary 11].  \n2) Even when $\\alpha>2$, the iterates will have a power-law distribution, but the behavior can vastly differ to a Gaussian.\n\nGiven the surge of interest in large step-sizes and edge-of-stability, we believe that point 1) has significance and illuminates under-explored settings considered in modern practical ML settings. We will mention this point more clearly in the next version. \n\n> [Q2]: Theorems 2 and 3 have an explicit dependence on the sample size n, but how do they depend on the batch size b?\n\nFirstly, due to Thm. 1 the tail index strictly increases in batch size $b$ (see Thm. 4 [1]). Furthermore, Thm. 2 establishes that reducing $b$ leads to heavier tail exponents (see Sec. 4 [2]).\n\nConcerning our presented results, the linear regression bound error terms (see Thm. 3) do not depend on $b$. This arises from the quadratic loss (i.e., linear derivative), linearity of expectation, and Minkowski's inequality (see Appendix C2 (L496) in the supplement).\n\nFor Thm. 5, in order to maintain clarity and facilitate a better understanding of the proofs, we have set $b=1$ (as emphasized in L218). We believe increasing $b$ would introduce further notational complexity, potentially compromising the overall presentation.\n\n> While in one-pass SGD the maximum number of steps is limited by data availability, this doesn't necessarily mean it requires an infinite amount of data.\n\nWe agree with you: in terms of convergence analysis, an infinite amount of data might not be needed for SGD to find a local minimum. However, to provide a rigorous theoretical analysis of SGD’s tail exponent, existing theory, unfortunately, requires an infinite amount of data.\n\nNonetheless, your concern is valid: the original sentence might have appeared too assertive. Therefore, we will reword it to highlight that the emergence of heavy tails in theoretical findings is contingent upon access to an infinite amount of data.\n\n> Please add the details of the plots in the caption in Fig. 2 & 5: the reported tail indices correspond to what simulation?\n\nFigures 2 and 5 align with the experiments emphasized on L268. However, it appears certain plots lacked clarity; therefore, we nomenclated the relevant paragraph, referencing it in the corresponding figures. Additionally, we provided further details to the plots. Finally, we provided new sets of plots to Fig. 2 and 3. The new figures and findings can be found in the PDF attached to our general response.\n\nWe hope these efforts will enhance the lucidity of our results.\n\n> L128: You mean [n]=1,⋯,n ?\n\nYou are right. To make it more visible, we will update it as $[n] = ${$1, \\dots, n $}.\n\n[1] Gurbuzbalaban, et al. The heavy-tail phenomenon in SGD, ICML 2021\n\n[2] Hodgkinson and Mahoney. Multiplicative noise and heavy tails in stochastic optimization, ICML 2021\n\n[3] Erdogdu et al. \"Convergence of Langevin Monte Carlo in chi-squared and Rényi divergence.\" AISTATS, 2022\n\n[4] Akiyama, and Suzuki. \"Excess Risk of Two-Layer ReLU Neural Networks in Teacher-Student Settings and its Superiority to Kernel Methods.'' arXiv:2205.14818 \n\n[5] Raj, Anant, et al. \"Algorithmic stability of heavy-tailed stochastic gradient descent on least squares.\" ALT, 2023\n"}, {"review_id": "jnyklgSWWW", "reviewer": "Reviewer_dWGg", "summary": "This paper investigates the approximate heavy-tailed behavior of stochastic gradient descent (SGD) in local minima in practical settings and its correlation with overall performance. It shows that the stationary distribution of offline SGD exhibits approximate power-law distribution, and the approximation error is controlled by how fast the empirical distribution of the training data converges to the true underlying data distribution in the Wasserstein metric. The main contribution is to fill the gap in understanding the underlying mechanism generating the reported heavy-tailed behavior in practical settings, where the amount of training data is finite. The paper also proves nonasymptotic Wasserstein convergence bounds for offline SGD to online SGD as the number of data points increases. The theory is verified with experiments", "questions": "- In Line 267, the authors state that the tail indices depend on the ratio of the step size $\\eta$ to the batch size $b$. However, a mere dependence on the ratio $\\eta/b$ has been found broken in online SGD with a large $\\eta$ as discussed in Sec.6.6 of Ref.[1]. A modification that is linear in the batch size $b$ is found for a simple 1-dimensional example. Could the authors elaborate on this result?\n\n- Still in Sec.6.6 of Ref.[1], the tail index is estimated with an explicit expression in terms of $\\eta$ and $b$ for a 1D example. Is it possible to compare the estimated tail indices predicted by your theorem with the explicit expression given in Ref.[1]?\n\n[1] **Strength of Minibatch Noise in SGD**, Liu Ziyin, Kangqiao Liu, Takashi Mori, Masahito Ueda, *ICLR 2022*", "limitations": "The authors adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- **Originality**: The paper investigates the heavy-tailed behavior of SGD in practical settings where the amount of data is finite, which has not been well understood before. It proves a nonasymptotic Wasserstein convergence bound for offline SGD which reduces to online SGD as the number of data points increases. The difference from a true heavy-tailed distribution with a finite number of data is given by the Wasserstein distance.\n- **Quality**: The paper provides rigorous theoretical analysis and proof to support its claims. It also conducts experiments to verify its theory.\n- **Clarity**: The paper is well-written and easy to follow, with clear explanations of technical terms and concepts. The authors also provide many clear schematic illustrations to help readers understand their concepts and results.\n- **Significance**: The theory of this paper is of both theoretical interest and direct practical significance. The results are easy to understand and bounds on the distance from a true heavy-tailed distribution are given explicitly with a clear form. ", "weaknesses": "- Possible evaluation method for the values of estimated tail indices is not provided. In Figure 5, the estimated tail indices depend on the step size $\\eta$, the batch size $b$, or their ratio $\\eta/b$, and of course the number of data $n$. It will be strong if an evaluation method for the tail indices, even approximately, can be provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to invest in our paper and for the encouraging feedback. In the following, we try to address your remaining concerns. However, before proceeding, we would also like to thank you for pointing out the interesting and relevant paper. We apologize for not including it previously (the paper escaped our notice) - we will properly cite it in the next version and add it to the related work section.\n\n> Possible evaluation method for the values of estimated tail indices is not provided. In Figure 5, the estimated tail indices depend on the step size $\\eta$, the batch size $b$, or their ratio $\\eta/b$, and of course the number of data $n$. It will be strong if an evaluation method for the tail indices, even approximately, can be provided.\n\nAs the analytical computation of the true tail exponent is not possible, we were unfortunately not able to perform such an evaluation. Instead, we utilized an estimator from [1], previously employed in [2, 3], which has been demonstrated to be asymptotically consistent (as per Corollary 2.4), ensuring that as the number of samples it uses increases, the estimate will converge to its true value. Furthermore, an empirical evaluation of this estimator has already been undertaken in [3] (we invite the reader to examine their Figure 3(b), which can also be found in the attached PDF in the response to all reviewers), which shows encouraging results. We will mention this in the next version clearly.\n\n> In Line 267, the authors state that the tail indices depend on the ratio of the step size $\\eta$ to the batch size $b$. However, a mere dependence on the ratio $\\eta/b$ has been found broken in online SGD with a large $\\eta$ as discussed in Sec.6.6 of Ref.[1]. A modification that is linear in the batch size $b$ is found for a simple 1-dimensional example. Could the authors elaborate on this result?\n\nWhile prior studies on heavy-tailed phenomena have explored the tail relationship with the ratio $\\eta/b$, you are absolutely correct in pointing out that this dependence may not exhibit a monotonic behavior. In our experiments, we prioritized replicating the NN experimental setup outlined in [2] in order to conduct a comparative analysis between offline SGD with varying $n$ and its online counterpart.\n\nHowever, the validity of your remark remains: we suspect that the reason why we still observe a monotonic relation between the tail exponent and the eta/b ratio might be that the range that we used for $b$ is too restrictive that the discrepancy result you mentioned does not kick in. We will mention this as a footnote and cite the corresponding part of the paper you mentioned. Nonetheless, our primary focus is to convey the increasing similarity in behavior between offline and online SGD (with the increase in sample size $n$), and we would prefer to avoid the discussion about the monotonicity of the tail exponent with respect to the $\\eta/b$ ratio.\n \n> Still in Sec.6.6 of Ref.[1], the tail index is estimated with an explicit expression in terms of $\\eta$ and $b$ for a 1D example. Is it possible to compare the estimated tail indices predicted by your theorem with the explicit expression given in Ref.[1]?\n\nAlthough the expression discovered in [4] is highly captivating, particularly due to its correction term (which is absent in the analysis of [2]), it is important to emphasize that our theoretical findings are strictly orthogonal to estimating the tail index $\\alpha$ or the behavior of $\\alpha$ with respect to $\\eta$, $b$, and their ratio. This relation was established in an earlier paper by Gurbuzbalaban et al [2]. Rather, our analysis focuses on characterizing the dissimilarities in behavior between online and offline SGD. In this respect, our theorems do not predict the tail index directly; they say the tail behavior of offline SGD will become increasingly power-law. Hence, the comparison of their estimate and the article you mentioned would be rather unrelated to our problematic (yet interesting in its correct scope), and we would like to avoid it in order not to convolute our message. \n\nIf you have any remaining questions, we look forward to them and remain at your disposal.\n\n\n[1] Mohammad Mohammadi, Adel Mohammadpour, and Hiroaki Ogata. On the tail index and the spectral measure of multivariate α-stable distributions. Metrika,381 78(5):549–561, 2015\n\n[2] Mert Gurbuzbalaban, Umut Simsekli, and Lingjiong Zhu. The heavy-tail phenomenon in SGD, ICML 2021\n\n[3] Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks, ICML 2019\n\n[4] Strength of Minibatch Noise in SGD, Liu Ziyin, Kangqiao Liu, Takashi Mori, Masahito Ueda, ICLR 2022\n"}]

Author rebuttal:
We want to extend our gratitude to the reviewers for their insightful feedback. In the following, we outline the modifications implemented in response to their input.

**In response to the clarity of the presented figures**:
* Every plot has been carefully labeled and experimental paragraphs nomenclated with the intention of improving the manuscript’s clarity and readability
* We have included new experiments and figures (see Fig. 1 and Fig. 2(a)-(b) in the attached PDF file), emphasizing even further how the tail heaviness of offline SGD iterates increases as the number of samples $n$ increases

More specifically, we have added the following two figures.

Fig. 1 depicts a 1-dimensional linear regression task, connecting how the tail behavior differs between online and offline SGD (with varying $n$). To be precise, the depicted QQ plots of the corresponding (estimated) stabilizing distributions convey the following:
* Online SGD with a sufficiently large learning rate exhibits heavy, non-Gaussian tails.
* Offline SGD exhibits increasingly heavier tails as the sample size $n$ increases

Fig. 2(a)-(b) corresponds to offline SGD applied to a 100-dimensional linear regression task and a NN classification task utilizing a 3-layer fully-connected NN on the MNIST dataset. In both experiments, the following consistent patterns emerge:
* The means and standard deviations of the parameters’ estimated stabilizing distributions in offline SGD increase with $n$
* The quantity and magnitude of the parameters far from the bulk of the distribution increase with $n$

**In response to the validity of the chosen tail estimator**:
* We will add a paragraph in the Appendix that highlights the main strengths of the estimator and justifies our choice for its selection. The main arguments are as follows:
    * The estimator's theoretical framework is established through its convergence in distribution to the true tail index (via a Central Limit Theorem result, detailed in Theorem 2.3 [1]), which is further complemented by its demonstrated asymptotic consistency (as per Corollary 2.4 [1]).
    * The estimator has already been used in various articles and its qualities have been thoroughly examined. This can be observed in Figure 2.(c) in the attached PDF (taken from [2]), which, in our opinion, contains convincing estimation results (e.g., small error bars regardless of the magnitude of the true tail index).

We hope that the aforementioned points convince the reviewers as well as future readers of the estimator choice, a decision that has been endorsed both by our research and preceding academic studies [2,3].

**In response to the remaining points, we**:
* Carefully emphasized that the claims of our paper are predominantly related to offline SGD, in contrast to previous works that consider online SGD
* Included new references and further insights into related work
* Fixed smaller technical notation
* Further elaborated on certain aspects, such as:
    * Extending our results to the non-convex settings with “dissipative” loss functions
    * The significance of our contribution towards linking heavy tails and generalization
    * Discussed potential connections between the true step size and parameters such as $\eta$, $b$, and $n$

[1] Mohammad Mohammadi, Adel Mohammadpour, and Hiroaki Ogata. On the tail index and the spectral measure of multivariate α-stable distributions. Metrika,381 78(5):549–561, 2015

[2] Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks, ICML 2019

[3] Mert Gurbuzbalaban, Umut Simsekli, and Lingjiong Zhu. The heavy-tail phenomenon in SGD, ICML 2021


Meta-review: The reviewers all gave the paper strong scores, and it is a new perspective on a fundamental well-studied topic.
Decision: Accept (spotlight)