Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance
Authors: Hongjian Wang
Mert Gurbuzbalaban
Lingjiong Zhu
Umut Simsekli
Murat A Erdogdu
Venue: NeurIPS 2021 Poster (2021)
Keywords: SGD
heavy tailed noise
infinite variance
Polyak-Ruppert averaging

Abstract: Recent studies have provided both empirical and theoretical evidence illustrating that heavy tails can emerge in stochastic gradient descent (SGD) in various scenarios. Such heavy tails potentially result in iterates with diverging variance, which hinders the use of conventional convergence analysis techniques that rely on the existence of the second-order moments. In this paper, we provide convergence guarantees for SGD under a state-dependent and heavy-tailed noise with a potentially infinite variance, for a class of strongly convex objectives. In the case where the $p$-th moment of the noise exists for some $p\in [1,2)$, we first identify a condition on the Hessian, coined `$p$-positive (semi-)definiteness', that leads to an interesting interpolation between the positive semi-definite cone ($p=2$) and the cone of diagonally dominant matrices with non-negative diagonal entries ($p=1$). Under this condition, we provide a convergence rate for the distance to the global optimum in $L^p$. Furthermore, we provide a generalized central limit theorem, which shows that the properly scaled Polyak-Ruppert averaging converges weakly to a multivariate $\alpha$-stable random vector.
Our results indicate that even under heavy-tailed noise with infinite variance, SGD can converge to the global optimum without necessitating any modification neither to the loss function nor to the algorithm itself, as typically required in robust statistics.
We demonstrate the implications of our results
over misspecified models, in the presence of heavy-tailed data.

Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance
Hongjaan Wang" Carnegie Mellon University hj juwangecmu. edu
Mert Gürbizbalaban Rutgers University mg13660rutgers.om edu
Lingjiong Zhu Florida State University zhuCmath. fsu. edu
Umut Şimşekli
Murat A. Erdogdu
INRIA & ENS PSL Research University umut.
University of Toronto & Vector Institute erdogdušcs toronto.
Abstract
Recent studies have provided both empirical and thcoretical evidence illustrating that heavy tails can emerge in stochastic gradient descent (SGD) in various scenar- ios. Such heavy tails potentially result in iterates with diverging variance, which hinders the use of conventional convergence analysis techniques that rely on the existence of the second-order moments. this paper, we provide convergence guarantees for SGD under state-dependent and heavy-tailed noise with poten- tially infinite variance, the p-th moment of the noise exists for some p E [1,2), we first identify condition on the Hessian, coined 'p-positive (semi-) )definitenes'' that leads to an interesting interpolation between the positive semi-definite cone (p 2) and the cone of diagonally dominant matrices with negaavgae diagonal entries (p = 1). Under this condition, provide convergence rate for the distance the global optimum in L Furthermore, we provide generalized central limit theorem, which shows that the properly scaled Polyak-Ruppert Ruppert averaging converges weakly to multi- variate a-stable random vector. Our results indicate that even under heavy- tailed noise with infinite variance, SGD can converge the global optimum without necessitating any modification neither to the loss function nor to the algorithm itself, typically required in robust statistics. We demonstrate the implications of our results over misspecified models, in the presence of heavy-tailed data.
a class of strongly convex objectives, In the case where
Introduction
We consider the unconstrained minimization problem
minimize fxx),
(1.1)
#ER"
using the stochastic gradient descent (SGD) algorithm. Initialized at zy E IR", the SGD algorithm is given by the iterations,
x = 7++1 (ax;) + (x.)) 1 = 0, 1,2,
(1.2)
where (Ti h denotes the step-size sequence, and { a martingale difference sequence adapted to a filtration (Fi teN, characterizing the noise in the gradient (the sequence {x,, heN is also adapted to the same filtration, we assume Ty is Feamuubura.l.). Our focus on the case where the noise is state dependent, and its variance is infinite, i.c., 11
Work partially conducted while affiliated with Vector Institute.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Many problems in modern statistical learning can be written in the form (1.1), where f(x) typically corresponds to the population risk, that is, f(x) := Ez~y( 2)] for a given loss function and an unknown data distribution v. In practice, one observes independent and identically distributed (i.i.d) samples 2; ~ v for i E [m]. and estimates the population gradient V f(:)) with a noisy gradient at each iteration, which is based on an empirical average over a subset of the samples (zi)ee()) Due to its simplicity, superior generalization performance, and well-understood theoretical guarantees, SGD has been the method of choice for minimization problems arising in statistical machine learning,
Starting from the pioneering works of Robbins and Monro [1951], Chung [1954], Sacks [1958], Fabian [1968], Ruppert [1988], Shapiro [1989], Polyak and Juditsky [1992], theoretical properties of the SGD algorithm and its variants have been receiving a growing attention under different scenarios. Recent works, for example Tripuraneni et al. [2018], Su and Zhu [2018], Duchi and Ruan [2021]. Toulis and Airoldi [2017], Fang et al. [2018], Anastasiou et al. [2019], Yu al. [2020] established convergence rates for SGD in various settings. By building on the analysis of Polyak and Juditsky averaging, these works led to novel methodologies to compute confidence intervals using SGD. However, a recurring assumption in this line of work is the finite noise variance, which may be violated frequently in modern frameworks.
[1992] to prove a central limit theorem (CLT) for the
Heavy-tailed behavior in statistical methodology may naturally arise from the underlying model, or through the iterative optimization algorithm used during model training. In robust statisties, one often encounters heavy-tailed noise behavior in data, which in conjunction with standard loss functions leads to infinite noise variance in SGD, Very recently, heavy-tailed behavior is shown to emerge from the multiplicative noise in SGID, when the step-size is large and/or the batch-size small [Hodgkinson and Mahoney, 2021, Gürbüzzbalaban et al., 2021]. On the other hand, there is strong empirical evidence in modern machine learning that the gradient noise often exhibits a heavy-tailed behavior, which indicates an infinite variance. For example, this is observed in fully connected and convolutional neural networks [Şimşekli et al., 2019, Gürbüzbalaaan and Hu, 2021] as well as recurrent neural networks [Zhang et al., 2020]. Thus, understanding the behavior of SGD under infinite noise variance becomes extremely important for at least two reasons. A computational complexity reason: modern machine learning and robust statistics frameworks lead to heavy-tailed behavior in SGD; thus, understanding the performance of this algorithm in terms of precise convergence rates as well as the required conditions on the step-size sequence as a function of the "heaviness" of the tail become crucial in this setup. A statistical reason: many inference methods that rely on Dolyak-Rupper averaging utilize a CLT which holds under finite noise variance (see e.g. online bootstrap and variance estimation approaches [Fang al., 2018, Su and Zhu, 2018, Chen et al., 2020J). Using the same methodology in the aforementioned modern frameworks (under heavy-tailed noise) will ultimately result in incorrect confidence intervals, jeopardizing the statistical procedure. Thus, establishing the limit distribution in this setting is of great importance.
In this work, we study the behavior of the SGD algorithm with diminishing siep-sizes for a class of strongly convex problems when the noise variance is infinite. We establish the convergence rates of the SGD iterates towards the global minimum, and identify sufficient condition the Hessian of f. which interpolates between the positive semi-definite cone and the cone of diagonally dominant matrices (with non-negative diagonal entries). We further study the Ruppert averaging of the SGD iterates, and show that the limit distribution is a multivariate o-stable distribution. We illustrate our theory on linear regression and generalized linear models, demonstrating how to verify the conditions of our theorems. Perhaps surprisingly, our results show that even under heavy-tailed noise with infinite variance, SGD with diminishing step-sizes can converge to the global optimum without requiring any modification neither to the loss function nor to the algorithm itself, as opposed to the conventional techniques used in robust statistics [Huber, 2004]. Finally, we argue that our work has potential implications in constructing confidence intervals in the infinite noise variance setting.
2 Preliminaries and Technical Background
Notational Conventions. By N, N+ and R we denote the set of non-negative integers, positive integers, and real numbers, respectively. For m E N+, we define [m] = {1...., m). We use italic letters (e.g. x, 5) to denote scalars and scalar-valued functions, sigu(x) to denote the sign of xr bold face italic letters (e.g. æx, {) to denote vectors and vector-valued functions, and bold face upper case letters (e.g. A) to denote matrices. We use |x and ||œ||p to denote the 2-norm and p-norm of a vector Φ;; ||||| and ||A||p the operator 2-norm and operator p-norm of a matrix A. The transpose
2

---

of a matrix A and a vector a (viewed as a matrix with I column) are denoted by A and x². If {A, JEE is sequence of matrices and k > L, the empty product I Ti= Ag is understood to be the identity matrix I. For two sequences of real numbers {at hes. {be Hen, we write d = (b,) if lim su l/ [bg] < oo, de = o(b;) if lim sump l (ul 0, a = (b),) if both d2 = (b))) and b, = (aa)) hold, and dt x by if lim | exists and is in (0, oo). If a = (bbtt) for any > 0, we say a, = (b,)). Sufficiently large or sufficiently small positive constants whose values do not matter are written as C, Co, Ci...., sometimes without prior introduction. If X1, X X2.... is sequence of random vectors taking value in I and is probability measure on R", we write
X,
D
1a if (Xt) converges in distribution (also called 'weak convergence") ) to μ..
11000
Stochastic Approximation. In the SGD recursion (1.2), we can replace ff with an arbitrary continuous function R: _ - R", and consider the same iterations that stochastically approximate the zero x' of R.
3++1 2t M++1 [[x,)) + Eet1 (xt)).
(2.1)
This is called the stochastic approximation process [Robbins and Monro, 1951]. which is a predecessor of stochastic gradient descent (SGD) and describes a larger family of iterative algorithms (see e.g. [Kushner and Yin, 2003, Chapters 2 and 3)). Theoretical investigation of the recursion (2. 1) has been active ever since its invention, especially under finite noise variance assumption: Robbins and Monro [1951] prove that the recursion (2.1) can lead to the T,2 convergence lime-+so El x:" =²1²] = 0: Chung [1954] further calculates an exact convergence rate (see (3.6) in Section 3); Blum [1954] presents an elegant proof that the convergence of T, to x can hold almost surely. The asymptotic distribution of (2.1) can be attributed to [Chung, 1954, Theorem 6]. which states that the expression
71 -1/1 (a: (x, - x²)) converges weakly to a normal distribution. In their seminal works, Polyak and Juditsky [1992] and Ruppert [1988] independently introduce the concept of 'averaging the iterates",
2o + -1
Ft
showing the striking result that Vi x²) converges weakly to fixed normal distribution regardless of the choice of the step-size {1x wtheN as long as it satisfies mild conditions. Recently optimization algorithms that can handle heavy-tailed noise sequence (Erhew have been proposed [Davis et al., 2019, Nazin et al., 2019, Gorbunov et al., 2020]; however, they still rely on a uniformly bounded variance assumption, hence do not cover setting.
Compared with the copious collection of theoretical studies on stochastic approximation algorithms with finite variance as mentioned above, papers that study stochastic approximation under infinite noise variance are extremely scarce; we shall summarize only a few papers known to us. Krasulina [1969] is the first to consider such problems, proving almost sure and L convergence for the one-dimensional stochastic approximation process without variance. The weak convergence of the iterates (without averaging) t t (x: - x²) is also considered by Krasulina [1969], but only for the fastest-decaying step-size "/- = 1/t. Goodsell and Hanson [1976] discuss how æ; -> x= in probability can imply x; - x almost surely, when no finite variance is assumed, and Li [1994] provides necessary and sufficient condition for almost sure convergence of æ, - x², stating that faster-decaying step-size 7/- o(t-1/p) is required when moments of lower orders B(|E,P") are not in place. Anantharam and Borkar [2012] show that although step-size that decays slower than t-p cannot yield almost sure convergence, L convergence can still hold under what they call the 'stability assumption', ; but their analysis technique provides [2019] and Zhang et al. [2020] considered SGD with heavy-tailed noise &, having uniformly bounded p-th order moments. Besides not being able to handle dependee noise due to this uniform moment condition, Şimşekli et al. [2019] imposed further conditions on R = V f such as global Hölder continuity for non-convex f. whereas Zhang et al. [2020] modified SGD with 'gradient clipping', in order to be able to compensate the effects of the heavy-tailed noise.
convergence rate. Recently, Şimşekli et al.
Finally, we shall mention that class of stochastic recursions similar to (2.1) have been considered in the dynamical systems theory [Mirek, 2011, Buraczewski al., 2012, 2016], for which generalized central limit theorems with a-stable limits have been established. However, such techniques typically require R to be (asymptotically) linear and the step-sizes to be constant as they heavily rely on the theory of tine-homogeneou Markov processes. Hence, their approach does not readily generalize to the setting of our interest, i.e., non-linear R and diminishing step-sizes, where the latter crucial for ensuring convergence towards the global optimum.
3

---

Stable Distributions. In probability theory, random variable X is stable if its distribution is non-degenerate and satisfies the following property: Let X, and X2 be independent copies of X. Then, for any constants a, h > 0, the random variable ax1 + 2x22 has the same distribution as c. + d for some constants > and d (see e-g. [Samorodnitsky and Taqqu, 1994])- The stable distribution also referred to as the o-stable distribution, first proposed by Lévy [1937], where E (0. 2] denoting the stability parameter. The case a = 2 corresponds to the normal distribution, and the variance under this distribution is undefined for any < 2. The multivariate a-stable distribution dates back to Feldheim [1937], which is multivariate generalization of the univariate a-stable distribution, which is also uniquely characterized by its characteristie function. In particular, an -aaluel random vector X has a multivariaae a-stable distribution, denoted as X ~ S(a, A, 6) if the joint characteristic function of X is given by
E E(exp(iul T x)] =cxp
/ [Iu's] + inl'ss, ad)) + in iu'd).
Joes,
for any u E R", and 0- < < 2. Here, is the tail-index. A is finite measure on S2 known as the spectral measure, 8 E R" is a shift vector, and v(y. a) := sign(y) aa(Taa2))ly) for a + 1 and (3, a)
(2/ log lyl for S2 = (s E R" | = 1.. Stable distribution also emerges as the limit distribution in the Generalized Central Limit Theorem (GCLT) [Gnedenko and Kolmogorov, 1954], which states that for sequence of i..dd random variables whose distributions have a power-law tail with index O < a < 2, the o-stable distribution as the number of summands go to co.
for any y E I. and S2 denotes the unit sphere in IR; i.e.
normalized converges
Domains of Normal A Attraction of Stable Distributions. Let X 1, 1..X2x X2.... X₁ be an i..d. sequence of random vectors in _ with a common distribution function F(x).. If there exists some constant a > 0 and a sequence by E R"" such that
X1 XI....+XX
D
at//a
F4.
(2.2)
then F(x) is said to belong to the domain of normal attraction of the law μ., and is the characteristic exponent of μ [Gnedenko and Kolmogorov, 1954, page 181]. If μ1 is an a-stable distribution, then we say F(x) belongs to the domain of normal attraction of a-stable distribution. For example, the Pareto distribution belongs to the domain of normal attraction of an a-stable law. In Section in the supplementary document, provide more details as well as sufficient and necessary conditions for being in the domain of normal attraction of an a-stable law.
3 Convergence of SGD under Heavy-tailed Gradient Noise
In this section, we identify sufficient conditions for the convergence of SGD under heavy-tailed gradient noise, and derive explicit rate estimates. In the standard setting when the noise variance is finite, it is sufficient to assume Hessian is uniformly positive definite in order to achieve contraction in the subsequent SGD iterations (see for example Polyak and Juditsky [1992], Tripuraneni et al. [2018], 8]. Su and Zhu [2018], 8]. Duchi and Ruan [2021], Toulis and Airoldi [2017], Fang et al. [2018], Anastasiou et al. [2019]], When the noise variance infinite with a finite p-th moment for p E [1. 2). a stronger notion of positive definiteness is required in our analysis to achieve such contraction, which leads to an interesting interpolation between the positive semi-definite cone (as + 2), and the cone of diagonally dominant matrices with non-negative diagonal entries (p 1).
3.1 p-Positive Definiteness
First, we introduce the signed power of vectors which will be used to define family of matrices.
For vector e = (v. ,..,, ) E R and q 3 0, the signed power of is defined as
T
v (a) == (v)
..... { \10)))
(3.1)
Denoting the n--dimensional &p unit sphere with Sp = fo E R" ||l||p 1}. and the set of n x n symmetric matrices with S, we define the following subset S.
Definition (p-positive definiteness). Let p > and Q be a symmetric matrix. We say that Q is p-positive definite for all Sp, we have v QQ((-1) > Similarly, we say that Q is p-positive
semi-definite for all v E Sp, we have we Qu Op(e-13 > O.

---

It is not hard to see that the set of p-positive semi-definite matrices (p-PSD) defines closed pointed cone, which we denote by $ with interior as the set of p-positive definite matrices (p- (p-PD), denoted by + We are mainly interested in the case 1 < p < 2. Note that S coincides with the standard PSD cone, and we show in Section A.2 that $ is exactly the cone of diagonally dominant matrices with non- negative diagonal entries, denoted by D+. For any p E []. these cones satisfy the following
cones
D cone: p p=
p PSD cone: pE (1,
D+ = S C
PSD cone: p=2 2
Figure 1 is hypothetical illustration of the inclusion rela- tionship between these cones.
Figure I: Geometry p-PSD matrices. B. cone refers to the cone of diagonally dominant matrices with non non-negative di- agonal entries. Their inclusion relation- ship given in Propositions 13 and 14.
Similar to the uniform PD condition on the Hessian, which is commonly used in classical analysis (i.e. strong convexity), we also define a uniform version of Definition 1. We recall that every operator norm || Ilp induces the same topology on the set of n n-dimensional matrices, which is just the usual topology on R=X*, Further, the set of X is a closed set.
symmetrie matrices S, the of zeros of the continuous function X Hence for set .M C S, denoting its topological closure with M, also have M C S. We are interested in the case where M is a bounded set.
Definition (uniform
Let p 2 and M S be a non-emply set of symmetric matrices. We say that M is uniformly p-PD if for all Q E M, we have Q S +++
Notice that M is uniformly 2-PD and only if the eigenvalues of the symmetric matrices in the set M are all lower bounded by positive real number. Notice also that finite subset of symmetric matrices is uniformly p-PD and only if each element of the set is p-PD.
p-PSD cone emerges naturally when analyzing SGD algorithm in the heavy-tailed setting, interpolat- ing between the standard PSD cone the cone of diagonally dominant matrices with non-negative diagonal entries. To the best of our knowledge, we are the first to study such families of matrices and their application in stochastic optimization. For further details about these cones, we refer interested reader to Section A.2 in the supplementary document.
We make the following uniform smoothness and curvature assumptions on the objective function. Assumption 1. The set of matrices 2 f(xx) : x [" is bounded and uniformly p- p-PD.
3.2 Rate of Convergence in L.
We fix probability space (Ω, IP) with filtration {Fihee, and we let æo be Fo-measurable. We make the following assumption on the gradient noise sequence. Assumption 2. The gradient noise sequence {ErheeN admits the following decomposition
(x+) = -m+)((x)) + Sc+1:
(3.2)
where (Cihee is an i.i.d. sequence with E[C,] = O, and Eils, oo for some p. and {mehent is martingale difference sequence, and both sequences adapted to the filtration [Fihee..
Further, the state dependent component of the noise satisfies, for some K > O,
E | (2:))
Fi] < K (1+|2x113)
(3.3)
We call m, the state-dependent component of the gradient noise, which naturally has state- -etende conditional second moment. The variance this component can be arbitrarily large depending on the state It. The heavy-tailed noise behavior is due to Ç,, which may have an infinite variance for p < 2 (i.e., the second moment is undefined). Compared to recent works on SGD with heavy-tailed noise, our noise model in Assumption 2 is significantly more general. For instance, the noise model in the recent work Zhang al. [2020] assumes TE. [ (m)) S ae for all æ,, where a does not depend on x. Therefore, this noise model cannot handle state-dependent noise, and does not even hold in the
5

---

linear regression example given in Section 5 (as the moments of the noise must scale with the norm of æ). On the contrary. in many instances of stochastic approximation methods subject heavy-tailed noise with long-range dependencies, one can verify that the noise admits the decomposition (3.2). We shall show in Section that the noise model (3.2) arises in practical applications such as linear regression and generalized linear models subject to heavy-tailed data (see also Anantharam and Borkar [2012] for a detailed discussion on this noise model).
In our first result, assuming that the objective function f has a uniformly p-PD Hessian and the noise sequence {E: IeN+ has infinite variance but satisfies Assumption 2. we establish an asymptotic convergence rate in L" for the SGD algorithm to the unique minimizer x="
Theorem 3. Suppose Assumptions I and hold for some 1 p Th x t with E (0, 1), the error of the SGD iterates {#e heN from the minimizer x² satisfies
For step-size satisfying
Bl|a, - x= = O 10:==00(0000 (1-0lo-1)).
(3.4)
Consequently, we have sup+EN+ E| |P] < 80.
The proof of Theorem 3 is provided in Section B in the supplementary document. We observe that the convergence rate of SGD depends on the highest order finite moment p of the noise sequence, and faster rates are achieved for larger values of p. The fastest convergence rate implied by our result is near Ot I+ which is achieved for p = 1. However, SGD converges even for very slowly decaying step-size sequences as P gets closer O.
If the noise sequence has further integrability properties with a finite p-th moment for all p E [4, o) for some q and if uniform p-PD condition (i.e. Assumption 1) holds, then faster rates achievable. In particular, the following result is an interesting consequence of Theorem 3, and its proof is provided in Section B in the supplementary document.
Corollary 4. For constants q: a satisfying 1 < q < a & 2, suppose that Assumptions I and 2 hold for every p [g, a). For step-size satisfying "It = P with p (0, the error of the SGD iterates {ar hee from the minimizer x² satisfies
Ell, x 91
Ô t Pa -=
(3.5)
Remark. The additional integrability assumption yields faster rates for any feasible step-size sequence since p(ax 1)/a > p 1 for E (1,2).
Let us briefly compare our results stated above to those in the setting where the noise sequence has finite variance. A classical convergence result that goes back to Chung [1954, Theorem 5)2 states that
Elix, x
[7] - == (
(3.6)
where r > 2 is an integer such that the r-th moment exists for the stochastic approximation process, and this is achieved for strongly convex objective functions in one dimension (whose second derivative {ff" (x) x E RR} satisfies the uniformly 2-PD property) with a step-size choice " x t for some p (1/2, 1). We point out that our rate (3.5) recovers the rate implied by (3.6) when = 2, and extends it further to the case <r<2 2.
In the presence of heavy-tailed noise, the folklore is to modify SGD (e.g., clipped gradients) in order to tame the heavy-tails, which considerably simplifies the problem and makes it amenable to classical analysis tools. For instance, to motivate modifying SGD in this regime, in [Zhang et al., 2020, Remark 1] authors prove that fx;))) |3] = xo for vanilla SGD and argue that SGD diverges in this setting. On the contrary, our results show that, without any modifications, SGD can still converge to the optimum in LP, even when it does not converge in L since the second moment is not defined.
Stable Limits for the Polyak-Ruppers Averaging
In this section, we establish the limit distribution of the Polyak-Rupper averaging under infinite noise variance, extending the asymptotic normality result given by Polyak and Juditsky [1992] to atstlble distributions. Let us fix an a E (1, 2] and assume the following throughout this subsection.
"This result, like many other similar studies in the 1950s, concerns only the one- -ie-dimensional case. But they generalize easily higher dimensions.

---

Assumption 3. The gradient noise sequence (Ethen admits the following decomposition
E (2t) = mc+1 + Sc+1:
(4.1)
where (Cr)een+ is an i.i.d. sequence with Eiç,] = O. which is in the domain of normal attraction of an n--imensional symmetric o-staale distribution μ4, i.e.
S1 +.. Se D
t1/a
μ.
(4.2)
The state dependent component {mihee is a martingale difference sequence with a second-moment satisfying (3.3), and both sequences are adapted to the filtration {Fe)reN.
The above assumption is arguably more stringent than Assumption and implies that E I'] < oo for all p E [1, a): thus, Assumption 2 is satisfied for any [1, a). The condition (4.2) is a special case of (2.2) which holds if, for example, S," have power-law tails (i.e. Paretian tail) with index a.
Denoting the Polyak-Ruppert averaging by Te == 2 (20 + + æt-1),, we are interested in the asymptotic behavior of
11-1/a [ x²) (xo + x(-1) - tæ
11/a
for a E (1, 2]. In the special case when 2, it known that this limit converges to multivariate normal distribution (which is a 2-stable distribution), a result proven in the seminal work by Polyak and Juditsky [1992]. Similarly, we begin with result that considers quadratic objective where the function V fxx is lincar in æ. and then building on this result, we establish the limit distribution of Polyak-Rupper averaging also in the
general non-linear case.
Theorem (linear case). Suppose the function V f (x) is affine, i.e ff(x) = Ax for real matrix A Raxn and a real vector T.. and there exist scalars p. P satisfying
a + ap
max
<pEa,
such that A is p-PD and p E (0, If the noise sequence satisfies Assumption 3 for the same parameter then for the step-size satisfying " xtx, the normalized average t'-1/a ( x²) converges weakly to an n n-dimensional a-stable distribution.
The above theorem states that Polyak- averaging for any step-size sequence with index E (0, 1] converges weakly to an a-stable limit. Thus, in the linear case, the size of this feasible interval is the same in both heavy- and light-tailed noise settings (see e.g. Polyak and Juditsky [1992] and Ruppert [1988]). Notably, a-stable limit of the averaged iterates does not depend on the index ie., limit distribution does not depend on how fast the step-size decays long p 10.
The next result generalizes Theorem 5 to the setting where V (x) is non-linear.
Theorem (non-linear case). Let 1 1/p q a and suppose Assumption 1 holds for every E [g, a). Assume further that the gradient V (x) can be approximated using the Hessian matrix
2 ((x") around the minimizer xx as
f((x) f=((x"(z==t) - x²) < x²1²
(4.3)
If the noise sequence satisfies Assumption 3, for the step-size satisfying x t_,,, the normalized average 1111/a (x, x²) converges weakly to an n-dimensional a-stable distribution.
The condition (4.3) is standard (see e.g. Polyak and Juditsky [1992, Assumption 3.2]), which simply imposes a local linearity condition on the gradient of the objective function f. with an order-g polynomial error term. This assumption holds, for example, whenever the Hessian is Lipschitz continuous. We notice that the size of the feasible interval is E (1/a, 1), which is smaller this time compared to the light tailed case; Polyak and Juditsky [1992, Theorem 2] allows p (1/2,
The above theorem establishes that, when the noise has diverging variance, the Polyak-Ruppert averaging admits an a-stable limit rather than standard CLT. This result has potential implications in statistical inference in the presence heavy-tailed data. Inference procedures that take into account the computational part of the training procedure (instead of drawing conclusions for the minimizer
7

---

of the empirical risk) rely typically on variations of admit [Fang al., 2018, Su and Zhu, 2018. Chen et al., 2020]. The above theorem simply states this CLT does not hold under heavy-tailed gradient noise. Therefore, many of these procedures require further adaptation, if the gradient has undefined variance. Finally, Dolyak-Ruppert averaging achieves the Cramér-Rao lower bound [Polyak and Juditsky, 1992, Gadat and Panloup, 2017], which a lower bound on the variance of an unbiased estimator. However, is not clear what this type of optimality means when the variance is not defined. These are important directions that require thorough investigations, and they will be studied elsewhere.
averaging and the CLT they
well-known that
Examples in the Presence of Heavy-tailed Noise
In this section, we demonstrate how the stochastic approximation framework discussed in our paper covers several interesting examples. More specifically, we verify the assumptions required for Theorems 5, and 6, for linear regression and generalized linear models (GLMs), where the heavy-tailed noise behavior may naturally arise due to heavy-tailes data.
5.1 Ordinary Least Squares
Let us first consider the following linear model,
- 2222 B, +e,
where 3n E Ra is the true coefficients, IR is the response, the random vector x E R denotes the covariates with positive-defmitt covariance E[ and a finite fourth moment E[|z|*] oc, and é is the noise with zero conditional mean B[{|2] 0. In the classical setting, the noise is assumed to be Gaussian whose variance well-defined. In this case, the population version of the maximum likelihood estimation (MLE) problem corresponds to minimizing
f(x) - (v- ".
(5.1)
2
(where the expectation is over the (y, 2) pair), or equivalently solving the following normal equations
( = [= x E[ O.
(5.2)
We easily observe that the true coefficients Bo is the unique zero of the above equation, i.c., x' = Ba.
given access to stream of i.id. drawn instances of the pair (y, 2). denoted by {yt, zt heeN . In large-scale settings, one generally runs the following stochastic approximation process, which is simply online SGD the population MLE objective fax):
Now, suppose
= -: Y/t (z.z, - 2.
(5.3)
Manifestly, (5.3) special case of (2.1), where the gradient noise admitting the decomposition
&, = C, + m2, for an i..dd component C, and state-dependent component m. (cf. (4.1)).
{ C, = E syy Zzye
(5.4)
m: == x - E 2z )
In the presence of heavy-tailed noise, for example when the noise has infinite variance, the population MLE objective (ax) may not be even finite, and one should resort to methods from M-estimation and choose suitable loss function within robust statistics framework [Huber, 2004, Van der Vaart, 2000]. However, the iterations (5.3) may still be employed to estimate the true coefficients 3o (potentially due model misspecification), should be seen as solving the root-finding problem (5.2) via stochastic approximation (2.1), rather than minimization problem stated in (5.1).
we demonstrate below. Note that in this case, iterations (5.3)
First, we verify Assumption 2. component (C, exhibits the heavy-tailed behavior since it contains y/1 2, 9,0 c₁. Assume that this component has the highest order finite moment p satisfying < < 2, i.e., E||C, < oc. Further, the state dependent component m, defines martingale difference sequence, and the condition (3.3) is met since the covariates z have finite fourth moment, i.e.,
We observe from the decomposition given in (5.4) that the i.i.d.
E m 2
x < C 12
8

---

Hence, Assumption 2 is satisfied. Next. assuming that the second moment of the covariates v² f(x) [[ is p-PD, one can guarantee that Assumption I is satisfied. Therefore, the convergence results of our theorems hold. Finally, we note that p-PD assumption is always satisfied if B| is diagonally dominant, but the condition for > is weaker.
5.2 Generalized Linear Models
Generalized linear models (GLMs) play erucial role in numerous problems in statisties, and provide a miscellancous framework for many regression and classification tasks, with many applications [Mc- Cullagh and Nelder, 1989, Nelder and Wedderburn, 1972]. In this section, we consider minimizing the objective function arising from GLMs, for which there are many methods available (see e.g.
Erdogdu [2015, 2016] and the references therein). However, we restrict ourselves to the misspecified and online setting. That is, the minimization problem corresponds to GLM, but the model is misspecified so that the response can be heavy-tailed.
For a response E I and random covariates 2 E R,, the population version of an lz-regularized MLE problem in the canonical GLM framework reads
X minimize f(x) E ( 2) yee 2 + gl0 for A >> 0.
(5.5)
Here, sh R R referred as the cumulant generating function (CGF), and it is convex. Notable examples include (xx) = x.² /2 yielding linear regression, rb(xr) = log(1 + e²) yielding logistic regression, and (z)) ex yielding Poisson regression. Gradient of the objective (5.5) given by
f(x) E 2 (zTx²)
2
E(zy] + Aæ.
(5.6)
We define the unique solution of the population GLM problem as the unique zero of (5.6), which we denote by x². To reiterate, we do not assume a model on data, allowing for model misspecification; we simply consider the resulting optimization problem similar to Erdogdu al. [2016, 2019]. As in the previous section, we assume that the covariates have finite fourth moment and the response y1 is contaminated with heavy-tailed noise with infinite variance. In this setting, the objective function always well-defined, even if the response has infinite variance.
We are given access to a stream of i.i.d. drawn instances of the pair (y,z), and we solve the above non-linear problem using the following stochastic process,
z), denoted by {ye, ZeJENN.
at Tt-1 70 (z/V/ (z) x=-1) Ziye Xxx-1),
with gradient noise admitting the decomposition E. C. + m. where
C2 [E[zy] Ze3/es m, = z x2] E((z (=]T(-1)]
In what follows, we verify our assumptions for a CGF satisfying [w((x)] & C(1 + [=]),, (0(x) > 0, and (x)) L for all x R. These assumptions can be easily verified for any second-order smooth CGF that grows at most quadratically (e.g. if the misspecified model is binomial with number of trials, we have (zxx)= = k log(1 1 + e)) Ç,'s are i.i.d. and contain the entire heavy-tailed part of the gradient noise. Assume that this component has the highest defined moment order I < P < 2, i.c., E] < oc. Further observe that the state dependent component defines martingale difference sequence and satisfies the condition (3.3) since the covariates z have finite fourth moment, and |x/| grows at most linearly. Therefore, Assumption 2 is satisfied.
We note that the Hessian of the objective f is given as
f(x) B[zz vO" (2Txx) + AI.
Since x/ (x) > O, f(x) is clearly PD for all À > For sufficiently large X, this matrix can also be made diagonally dominant, which implies the p-PD condition for any p > 1, further implying Assumption 1. We further note that if v² is Lipshitz (e.g. for the binomail CGF), then (4.3) holds for g = globally; thus holds for any q < locally. Therefore, for an appropriate step-size sequence, our convergence results the SGD can be applied to this framework.

---

Conclusion
In this paper, we considered SGD subject state-dependent and heavy-tailed noise with potentially infinite variance, when the objective belongs to a class of strongly convex functions (termed as p-PD condition). We provided asymptotic L" convergence rates for vanilla SGD, demonstrating that SGD without any modifications can be still used in the presence of heavy-tailed noise. Furthermore, we provided generalized central limit theorem for the Dolyak-Rupped averaging, i.e., we proved that the averaged iterates converge to a multivariate a-stable distribution.
We emphasize that p-PD condition is sufficient condition, and further investigation is needed this condition can be replaced with the standard strong convexity assumption. We also highlight that non-asymptotic L rates the current setting should be achievable, which will be studied elsewhere. Finally, while we leave it for future study, we emphasized the importance of adapting existing statistical inference techniques that rely on the averaged SGD iterates when the gradient noise is heavy-tailed, which arises naturally in modern statistical learning applications.
Acknowledgements
MAE is partially funded by CIFAR AI Chairs program, and CIFAR AI Catalyst grant, NSERC Grant [2019-06167]. MG's research is supported in part by the grants Office of Naval Research Award Number N00014-21-1-22444
National Science Foundation (NSF) CCF--184888, NSF DMS- 2053485, NSF DMS-1723085. LZ is grateful to the partial support from NSF DMS-2053455 and Simons Foundation Collaboration Grant. UŞ's research is supported by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d' l'avenir" program, reference ANR-19-P3IA-00N (PRAIRIE 3IA Institute).
References
V. Anantharam and V. Borkar. Stochastic approximation with long range dependent and heavy tailed noise. Queueing Systems, 71(1-2):221-244 2012.
A. Anastasiou, K. Balasubramanian, and M. A. Erdogdu. Normal approximation for stochastic gradient descent via non- -on-asymptotic rates of martingale CLT. In Conference on Learning Theory, pages 1 11-1177, 2019.
J. R. Blum. Approximation methods which converge with probability one. The Annals of Mathemati- cal Statistics, 25(2):382-386, 1954.
D. Buraczewski, E. Damek, and M. Mirek. Asymptotics of stationary solutions of multivariate stochastic recursions with heavy tailed inputs and related limit theorems. Stochastic Processes and their Applications, 122(1):42-66 67, 2012.
D. Buraczewski, Damek, and T. Mikosch. Stochastic Models with Power-Law Tails. Springer, 2016.
X. Chen, J. D. Lee, X. T. Tong, and Y. Zhang. Statistical inference for model parameters in stochastic gradient descent. The Annals of Staristics, 48(1):251-273, 2020.
Y. Cherapanamjeri, N. Tripuraneni, L. Bartlett and I. Jordan. Optimal mean estimation without variance. arXiv preprint arXiv:2011. 2020.
K. I.. Chung. On a stochastic approximation method. The Annals of Mathemutical Statistics, 25(3): 463-483, 1954.
D. Davis, D. Drusvyatskiy, L. Xiao, and J. Zhang. From low probability to high confidence in stochastic convex optimization. arXiv preprint arXiv: 1907.33777 2019.
J. Duchi and F. Ruan. Asymptotic optimality in stochastic optimization. The Annals of Statistics, 49 (1):21-48, 2021.
M. A. Erdogdu. Newton-stein method: second order method for glms via stein's 's lemma. Advances 2015.
in Neural Information Processing Systems,
10

---

M. A. Erdogdu. Newton-stein method: An optimization method for glms via stein's 's lemma. The Journal of Machine Learning Research, 17(1):76657716, 2016.
M. A. Erdogdu, L. H. Dicker, and M. Bayati. Scaled least squares estimator for glms in large-seale problems. Advances in Neural Information Processing Systems, 29:3324-3332, 2016.
M. A. Erdogdu, M. Bayati, and H. Dicker. Scalable approximations for generalized linear problems. The Journal of Machine Learning Research, 20(1):231-275, 2019.
V. Fabian. Stochastic approximation of minima with improved asymptotic speed. The Annals of Mathematical Statistics, 38(1):191-200, 1967.
V. Fabian. On asymptotic normality in stochastic approximation. The Annals of Mathematical Statistics, 3944)11327 1968.
Y. Fang, J. Xu, and L. Yang. Online bootstrap confidence intervals for the stochastic gradient descent estimator. The Journal of Machine Learning Research, 39(5)33033-3073, 2018.
N. Farsad, W. Guo, C. B. Chac, and A. Eckford. Stable distributions as noise models for molecular communication. 2015 IEEE Global Communications Conference, GLOBECOM 2015, 2015.
E. Feldheim. Étude de stabilité des lois de probabilité. PhD thesis, Faculté des Sciences de Paris, Paris, 1937.
W. Feller. An Introduction to Probability Theory and Its Applications. Wiley, New York, 2nd edition, 1971.
A. Fiche, J. C. Cexus, A. Martin, and A. Khenchaf. Features modeling with an a-stable distribution: Application to pattern recognition based on continuous belief functions. Information Fusion, 14 (4):504-520) 2013.
S. Gadat and F. Panloup. Optimal non-asymptotic bound of the Ruppert-Polyak averaging without strong convexity. arXiv preprint arXiv: 0334442, 2017.
J. L. Geluk and L. de Hann. Stable probability distributions and their domains of attraction: A direct approach. Probability and Mathematical Statistics, 20: 169-18888, 2000.
B. Gnedenko and A. Kolmogorov. Limit Distributions for Sums of Independent Random Variables. Addison-Wesley, Wesley, Cambridge, MA, 1954. Translated by Kai Lai Chung.
C. Goodsell D. Hanson. Almost sure convergence for the Robbins-Monro process. The Annals of Probability, 4(6):890-901, 1976.
E. Gorbunov, M. Danilova, and A. Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. In Advances in Neural Information Processing Systems, volume 33, 2020.
M. Gürbüzbalaban and Y. Hu. Fractional moment preeentiirreeeigggggg initialization schemes for training culle-coneected neural networks. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130, pages 2233 2241. PMLR, 2021.
M. Gürbüzbalaban, U. Şimşekli, and L. Zhu. The heavy-tail phenomenon in SGD. In International Conference on Machine Learning, pages 3964-3975, 2021.
L. Hodgkinson and M. W. Mahoney. Multiplicative noise and heavy tails in stochastic optimization. In International Conference on Machine Learning, pages 4262-4274, 2021.
Huber. Robust Statistics, volume 523. John Wiley & Sons, 2004.
T. P. Krasulina. On stochastic approximation processes with infinite variance. Theory of Probability
& Its Applications, 14(3):522-526, 1969.
H. Kushner and G. G. Yin. Stochastic Approximation and Recursive Algorithms and Applications, volume 35, Springer Science & Business Media, 2003.

---

P. Lévy. Théorie de I' I'addition des variables aléatoires. Gauthiers- Suathiers-Villars, Paris, 1937.
G. Li. Almost sure convergence of stochastic approximation procedures. Statistica Sinica, 4(1): 361-372, 1994.
McCullagh and J. A. Nelder. Generalized Linear Models. Chapman and Hall, 2nd edition, 1989.
M. Mirek. Heavy tail phenomenon and convergence to stable laws for iterated Lipschitz maps. Probability Theory and Related Fields, 151(3):705-734, 2011.
A. V. Nazin, S. Nemirovsky, A. Tsybakov, and A. Juditsky. Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 8009):1607-1627, 2019.
A. Nelder and R. W. Wedderburn. Generalized linear models. Journal of the Royal Statistical Society: Series A (General), 135(3):370-384, 1972.
J. Neveu.
Martingales, volume 10. North-Hollane Amsterdam, 1975.
B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4))838-855, 1992.
H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3):000-407 1951.
D. Ruppert. Efficient estimations from slowly convergent Robbins-Monn process. Technical report, Comelll University Operations Research and Industrial Engineering, 1988.
J. Sacks. Asymptotic distribution of stochastic approximation procedures. The Annals of Mathematical Statistics, 29(2):373-4055 1958.
G. Samorodnitsky and M. S. Taqqu. Stable Non-Gaussian Random Processes: Stochastic Models with Infinite Variance. Chapman & Hall, New York, 1994.
K. Sarafrazi and M. Yazdi. Skewed alpha-stable distribution for natural texture modeling and segmentation in contourlet domain. Eurasip Journal on Image and Video Processing, 2019(1): 1-12, 2019.
A. Shapiro. Asymptotic properties statistical estimators stochastic programming. The Annals of Statistics, 17(2):841-858, 1989.
U. Şimşekli, M. Gürbüzbalaban, T. H. Nguyen, G. Richard, and L. Sagun. On the heavy-tailed theory of stochastic gradient descent for deep neural networks. arXiv preprint arXiv: 1912.000/ 2019.
U. Şimşekli, I.. Sagun, and M. Gürrbüzhalaban. tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference Machine Learning, pages 5827-5837, 2019.
W. Su and Y. Zhu. Statistical inference for online learning and stochastic approximation via hierar- chical incremental gradient descent. arXiv preprint (a0i::v880.0483 2018.
P. Toulis and E. M. Airoldi. Asymptotic and finite-sample properties of estimators based stochastic gradients. The Annals of Statistics,
2017.
N. Tripuraneni, N. Flammarion, F. Bach, and M. I. Jordan. Averaging stochastic gradient descent on Riemannian manifolds. In Proceedings of the 3 Conference Learning Theory, 2018.
A. W. Van der Vaart. Asymptotic Statistics, volume 3. Cambridge University Press, 2000.
L. Yu, K. Balasubramanian, Volgushev, and M. A. Erdogdu. An analysis of constant step size
SGD in the non non-convex regime: Asymptotic normality and bias. arXiv preprint arXiv:2006.07904, 2020.
Zhang, P. Karimireddy, A. Veit, Kim, S. Reddi, S. Kumar, and S. Sra. Why are adaptive methods good for attention models? In Advances in Neural Information Processing Systems, volume 33, 2020.
12


Reviews:
[{"review_id": "fLIdkjZKkRq", "reviewer": "Reviewer_2Gbm", "summary": "The authors analyze SGD for a class of strongly-convex functions and under (possibly) infinite noise variance, i.e., the pth moment of the noise exists for $p \\in [1,2)$, but noise variance is not assumed to be bounded. Such noise behavior is defined as heavy-tailed. Additionally, the noise is assumed to be state-dependent such that the noise vector has a component whose variance is bounded by a function of the query point (iterates). For standard analysis of SGD, noise vectors are assumed to be independent of query points and of each other.\nSpecifically, for a class of strongly convex functions (denoted as p-positive definite (p-PD), p=2 being positive definite Hessian) and under heavy-tailed noise, the authors:\n\n-\tQuantify the convergence rate with respect to (w.r.t.) distance to unique optimum in $L^p$, which approaches the optimal rate in strongly convex setting as $p \\rightarrow 2$. This result is achieved for SGD without any modifications and under state-dependent noise model.\n-\tProve that normalized Polyak-Ruppert average (uniform average) converges weakly to an $\\alpha$-stable distribution, under additional assumptions on the noise and the Hessian. Central Limit Theorem (CLT) does not hold under heavy-tailed noise model.\n\nIn order to reinforce the setting they consider and verifiability of their assumptions in practice, authors discuss about the real-world examples that admit heavy-tailed noise and satisfy p-PD assumption.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work tries to extend SGD for heavy-tailed noise for a class of strongly-convex problems satisfying p-PD condition. This condition could be interpreted as a generalization of positive definiteness of Hessian and interpolates between diagonally dominant matrices with non-negative diagonal and positive definite matrices. They also consider a more general noise model where they assume there exists a component of the noise vector that grows with the norm of the query point. In my opinion, these are the main novelties of this paper that builds onto existing work and approaches.\n\nIn that perspective, to the best of my knowledge, they adequately cite related work and explain the differences/similarities between their work and the prior ones while emphasizing their improvements.\n\nAuthors provide a set of main convergence results as well as limit behavior of the sequence generated b SGD. These results are proven in the supplementary material, however, the implications of these results are provided in the main text through intuitive remarks and technical discussions following the main theorems. Authors also try to verify their setting and validity of the assumptions via particular examples; least squares and generalized linear models.\n\nOverall, the paper is written in a clear way. Problem setting, as well as the assumptions accompanying it are clearly stated and discussed in comparison to existing work. Main contributions are presented to the reader in a separate paragraph at the end of introduction. Main results are organized in a proper way and it is easy to follow the core contributions. Assumption 1 is not defined but referred to several times in the appendix. It is possible to deduce what was meant by Assumption 1 from the context, but it should be defined and referenced clearly. \n\nRelying on the existing results, behavior of stochastic methods under heavy-tailed noise has attracted attention again recently and has been studied in different contexts. \n\n[Zhang et al., 2020] considers heavy-tailed noise without state-dependence. Under $L$-smoothnness, they prove convergence rates for non-convex functions. Under heavy-tailed $\\text{\\bf stochastic gradients}$ rather than heavy-tailed noise, they show comparable convergence rate for strongly-convex functions. This paper focuses on a class of strongly-convex functions and show convergenve rates under state-dependent heavy-tailed noise. Given the results proposed by [Zhang et al., 2020], this work provides a nice generalization on the heavy-tailed noise model, but its impact is comparatively limited in terms of convergence analysis.\n\n[Simsekli et al., 2019] considers nonconvex problems under heavy-tailed stochastic gradients. With Holder smoothness assumption on the gradient of the objective, they show convergence rates to first-order stationary points. The setting of this paper and [Simsekli et al., 2019] do not overlap and we might say the results are complementary.\n\nAs for the limiting behavior of the normalized average iterate, given the results by [Polyak and Juditsky, 1992], Assumption 3 and assumption in Eq. (4.3), Theorem 5 and 6 provide some nice results, but their significance is limited in my opinion.\n\nPlease find some of my particular comments below:\n- The authors say that Eq. (4.3) is a standard assumption. I do not completely agree with this statement. Authors also state that this condition holds for Hessian Lipschitz objective, but Hessian-Lipschitzness is a rather strong assumption already.\n- For proving $\\alpha$-stability results, it is assumed that i.i.d. component of the noise is assumed to be in the domain of normal attraction of\nan $\\alpha$-stable distribution. In my opinion, this makes the results of Theorem 5 and 6 less interesting from a theoretical point of view.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They address some limitations of their results in comparison to prior work. The authors do not mention potential negative societal impact of their work. Given that this is a theory paper, the authors might have thought that it is less likely to have foreseeable negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "YW4pokOo4ae", "reviewer": "Reviewer_b6Pg", "summary": "Previous theoretical analysis of SGD algorithms for convex functions have in general assumed the finitness of the second moment of the stochastic gradient.  The current paper provides convergence rates and generalized central limit theorems under alternative assumptions on the stochastic gradient and the hessian matrices. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper defines the concept of $p$-positive definitness for square symmetric matrices, for $p\\ge1$. This concept generalizes the concept of positive definite matrices, and the two concepts are the same when $p=2$. Assumption 1 says that the Hessian matrices are uniformly $p$-positive definite. Assumption A2 says that the gradient noise is the sum of two components, the second of which has a finite $p$ moment. Theorem 3 shows convergence results for the SGD algorithm under Assumptions A1 and A2 for a suitable step-size. Under certain assumptions, Theorems 5 and 6 prove central limit theorems for a normalized average of iterates. The paper uses SGD without any modification. \n\nTheorem 3 in the paper is in the same spirit as Theorem 4 of Zhang et al Neurips 2020. While Theorem 3 in the paper requires $p$-positive definitness assumptions on the Hessians and certain assumptions on the stochastic gradients, Theorem 4 in Zhang et al requires a strong-convexity assumption and the unifom finiteness of moments of the stochastic gradients. \n\nThe results in the paper are interesting and new to me. On the negative side, the paper contains no numerical experiments, and it is not clear whether the $p$-positive definitness assumption holds in practical applications. Below are more detailed comments or questions.\n\n--In Assumption A2, is $\\\\{m_t\\\\}$ a martingale difference sequence with respect to $\\\\{\\cal F_t\\\\}$?\n\n--The definition of the domain of normal attraction in (4.2) does not coincide with the definition in (2.2).\n\n--line 273: why does Assumption A3 imply that $E[|\\xi_t|^p]< \\infty$?\n\n--line 340: The calculation of $E[|m_t|^2|x_{t-1}]$ involves  $E[||z_t||^2z_tz_t^T]$. So $E[|m_t|^2|x_{t-1}]$ is not always finite if the second moment of $z$ is finite.\n\n--line 358: for logistic regressions, $y_t$ is binary in practice, and has finite second moment.\n\n--line 112 : typo in \"the only a few\"\n\n\n----After feedback, I increased my score----", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I am not aware of negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "I am not aware of ethical concerns regarding the paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "DolqwObfc2V", "reviewer": "Reviewer_DYic", "summary": "This paper concerns the convergence rate of SGD with heavy-tail noise. In particular, the considered gradient noise consists of a finite-variance part (corresponds to the multiplicative noise in SGD for least square) and an infinite-variance part (corresponds to the additive noise in SGD for least square). The main results can be viewed as a law of large number and a central limit theorem in the absence of finite-variance. First the authors show that when the loss is \"strongly convex\" and \"smooth\" in the $p$-PD sense and the heavy-tail part noise has finite $p$-moment, SGD (with decaying stepsize) iterates converges to the correct optimum, and the convergence rate is justified in the p-norm sense. Moreover, if the heavy-tail noise is the domain of normal attraction of some stable distribution, then the properly normalized SGD iterates also converges to the stable distribution. Finally, the heavy-tailed noise model is justified from two linear model examples.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Pros:\n+ The paper is organized well and is particularly clear in its math (as a CS paper).\n+ The presented convergence rate and CLT for SGD with heavy-tailed noise are novel in machine learning to my knowledge. I am not sure how novel these are in probability theory. \n+ Technically, the introduced p-PD notions could be interesting tools for ML people to know. Again, not sure whether or not these are interesting for probability theorists.\n\n\n# Cons:\n- Several important quantities are hidden in the rate in Thm3, e.g., dependence on $x_1$, condition numbers (as the hessian is assumed to be uniform $p$-PD), dimension factors, the noise $p$-moment bound, etc. This limits the importance of the theorem. The presented rate is interesting assuming the above are all constants, but more discussions on the roles of these quantities could make the result even more interesting & inspiring.\n- Could you comment on SGD with constant, large stepsize and with iterate-averaging/tail-averaging? In the finite-variance cases such SGD setup achieves optimal rate & I am wondering how it would be in the infinite-variance cases. Is there essential difference other than switching to a different norm?\n\n# Small issues:\n* Eq below l.145. $delta$ could be boldface.\n* l.322. coefficients -> coefficient.\n* Eqs below l.652. The first inequality is not rigorous as $x^b_t$ depends on $x_t$. I believe this is easily fixable and should not affect the correctness of the final claim. Please confirm.\n\n# Overall:\nAs an ML person who has limited probability background, I think this paper is clear and clean, and is a good reading for understanding SGD in the heavy-tail noise cases. However I am not sure how novel the results to probability theorists. On the one hand, the two main results, Thm3 and Thms 5/6, seem to be applications of developed large number thm and CLT from existing (and quite old) probability papers (perhaps with a little bit standard optimization tricks) --- I could miss some points here and please correct me if so. Thus I am not sure how probability theorists view these results. On the other hand, the effects of initialization, condition numbers, dimension factors, noise bound are very important for rates for ML problems, but these are all hidden in the presented result. Thus the current version is a bit unsatisfactory. It is very hard for me to make a decision, currently I lean slightly to a weak acceptance.\n\n\n\n\n\n\n\n-----\nPost-Rebuttal: I tend to maintain my original evaluation for this paper after discussions with the authors. The contribution is solid in my perspective. But there are also several technical dissatisfactions about the current results (e.g., unable to track important constants like condition number).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "00wWYjLMRM", "reviewer": "Reviewer_vEYC", "summary": "The paper considers the convergence theory of SGD under assumptions that does not imply finite variance of the noise of the stochastic gradient for a class of strongly convex functions. A convergence rate is proven for an existing moment of the iterates of SGD and a CLT is proven for the averaged of the iterates (towards an alpha stable distribution). \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This work studies the convergence of SGD in the case where the noise has infinite second moment. While this covers interesting practical cases, this is in contrast with most of the works on the convergence of SGD.\n\nQuality: The convergence results are discussed in details and the paper is well written, although technical. A good literature review is provided for stochastic approximation under assumptions that do not imply finite variance of the noise. Besides, a CLT is provided for the average of the iterates, towards an alpha stable distribution. My main concern is wrt to the assumptions made in theorems. First, the work is limited to strongly convex functions and second the assumptions made on the noise do not seem easy to check. I must admit that a real effort is made to prove that the assumptions are satisfied for Ordinary Least Square and Generalized Linear Models, but this still relies on some hypotheses.\n\nClarity: The work is technical and more effort should be made on clarifying the paper. The intro and literature review are quite technical. The choice of alpha stable distribution in Assumption 3 is not really justified. It seems specific. Why this choice? Do we know the parameters of the alpha stable distribution? Specific questions:\n- Th 5: Alpha is given by assumption 3, am I correct? Do we know alpha easily?\n- l.290: \"Indices\"?\n- Could you explain how to obtain 5.3 and l.363 ?\n\nSignificance: The work considers the infinite variance noise, which an important setting is practice. However it still requires some assumptions, so the work is not that general.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some limitations are discussed. Another limitation is that this work relies on a lot of modelization/assumptions about the noise. Even if it is proven that this work covers OLS and GLM, I am not sure that it can go beyond.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper examines the convergence of stochastic gradient descent in strongly convex minimization problems. The novelty of the analysis is that the authors do not assume that the variance of the gradient queries is finite; instead, they consider "heavy-tailed" gradient noise models with bounded moments for some $p\in[1,2)$ - but not necessarily for $p=2$ or higher.

This paper received almost universally positive reviews during the review phase, and the only "weak reject" recommendation was changed to a "weak accept" after the authors addressed the reviewer's concerns. As a result, during the committee discussion, a consensus was reached early on to make an "accept" recommendation.
Decision: Accept (Poster)