An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias
Authors: Lu Yu
Krishna Balasubramanian
Stanislav Volgushev
Murat A Erdogdu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Constant Step Size SGD
Non-convex optimization
Polyak-Ruppert averaging
CLT

Abstract:  Structured non-convex learning problems, for which critical points have favorable statistical properties, arise frequently in statistical machine learning. Algorithmic convergence and statistical estimation rates are well-understood for such problems. However, quantifying the uncertainty associated with the underlying training algorithm is not well-studied in the non-convex setting. In order to address this shortcoming, in this work, we establish an asymptotic normality result for the constant step size stochastic gradient descent (SGD)  algorithm---a widely used algorithm in practice. Specifically, based on the relationship between SGD and Markov Chains  [DDB19], we show that the average of SGD iterates is asymptotically normally distributed around the expected value of their unique invariant distribution, as long as the non-convex and non-smooth objective function satisfies a dissipativity property. We also characterize the bias between this expected value and the critical points of the objective function under various local regularity conditions. Together, the above two results could be leveraged to construct confidence intervals for non-convex problems that are trained using the SGD algorithm.

An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias
Lu Yu
Krishnakumar Balasubramanian
University of Toronto & Vector Institute
University of California, Davis
stat. yu@mail gentyyy@mail.uuoronee... wtwronto..coomm
kbala@ucdavis..ok
Stanislav Volgushev University of Toronto
Murat A. Erdogdu
University of Toronto & Vector Institute erdogdu@cs. toronto edu
staaiislav.volguseeetttoooooo ca
Abstract
Structured non-convex learning problems, for which critical points have favorable statistical properties, arise frequently in statistical machine learning. Algorithmic convergence and statistical estimation rates well-understood for such problems. However, quantifying the uncertainty associated with the underlying training al- gorithm not well-studied the non-convex setting. In order to address this short-coming, in this work, we establish an asymptotic normality result for the constant step size stochastic gradient descent (SGD) algorithm widely used algorithm in practice. Specifically, based on the relationship between SGD and Markov Chains [1]. we show that the average of SGI) iterates is asymptotically nor- mally distributed around the expected value of their unique invariant distribution, as long as the non-convex and non-smooth objective function satisfies dissipa- tivity property. We also characterize the bias between this expected value and the critical points of the objective function under various local regularity conditions. Together, the above two results could be leveraged to construct confidence intervals for non non-convex problems that are trained using the SGD algorithm.
1 Introduction
Non-convex learning problems are prevalent in modern statistical machine learning applications
such as matrix and tensor decomposition [2, 3, 4, 5, 6, 7, 8), deep neural networks [9, 10, 11]. and robust empirical risk minimization [12, 13, 14]. Developing theoretically principled approaches for tackling such non-convex problems depends critically on the interplay between two aspects. From a computational perspective, variants of stochastic gradient descent (SGD) converge to first- order critical points [15, 16] local minimizers [17, 2. 18, 19] of the objective function. From a statistical perspective, oftentimes these critical points or local minimizers have nice statistical properties [20, 3, 12, 21, 22, 5]; also [23] for counterexample. For the purpose of uncertainty quantification in such non-convex settings, studying the fluctuations of itcrative algorithms used for training becomes extremely important. In this work, focus the widely used constant step size SGD, and develop results for quantifying the uncertainty associated with this algorithm for a class of non-convex problems.
consider minimizing non-smooth and non-convex objective function f: Rd R.
min f(0).
BER
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The iterations of SGD with a constant step size vy >> 0, initialized at 0g²) = 0g E
Rdd, are given by
(n) x+1 = و - - (V ) + (0( k 2 0,
(2)
where {Ex is a sequence of random functions from Rd IR corresponding to the stochasticity in the gradient estimate. Several problems in machine learning and statistics are naturally formulated as the optimization problem in (I), where the function f(0) is given by
f(0) 1 F F Z) dP(
(3)
for an unknown distribution over the random variable Z E IR. The function F(O, Z) is typically the loss function composed with functions from the hypothesis class parametrized by 0 E TR.. In online SGD with batch size b, at each iteration k. independent samples 2j ~ P()) are used to estimate the true gradient with &o2 Ej=1 VF(O 7) Σz). The above iterates are indeed special case of the iterates in (2), with the noise sequence (1x+1 ) given by
Ex+1 (0(m) =
= i Σド |F((O (1) Zz) {(((())
(4)
Although proposed in the 1950s by [24], SGD has been the algorithm of choice for training statistical models due to its simplicity, and superior performance in large-scale settings [25, 1, 26, 27]. However, the fluctuations of this algorithm is well-understood only when the objective function f is strongly convex and smooth, and the step size 7) satisfies a specific decreasing schedule so that the iterates asymptotically converge to the unique minimizer [28, 29, 30J. On the other hand, it is well-known that the SGD iterates in (2) can be viewed as a Markov chain which allows them to converge to a random vector rather than single critical point [1]. Building on this analogy between SGD and Markov chains, the aforementioned shortcomings can be alleviated by simply relaxing the global smoothness as well as the strong convexity assumptions to the tails of the objective function f. which allows for flexible non-convex structure around the region of interest. Similar kinds of tail relaxations have been successfully employed in the diffusion theory when the target potential is non-convex [31, 32, 33], but they are not studied in the context of non-convex optimization when the algorithm is SGD. In this work, we study the fluctuations and the bias of the averaged SGD iterates in (2), around the first-order critical points of the minimization problem (1). Our contributions can be summarized as follows.
For a non-convex and non-smooth objective function f with tails growing at least quadratically, we establish the uniqueness of the stationary distribution of the constant step size SGD iterates in Proposition 1, and the asymptotic normality of Polyak-Rupppe Ruppert averaging in Theorem 2.1. To the best of our knowledge, these are the first uniqueness and normality results for the SGD algorithm when the objective function is non-convex (even not strongly convex) and non-smooth. We further show in Theorems 3.1 and 3.2 that, with additional local smoothness assumptions on the non-convex objective function f. we can establish a control over the bias in terms of the step size. We further characterize the bias when the objective is (not strongly) convex in Theorem 3.3, providing a thorough bias analysis for the constant step size SGD under various settings that are frequently encountered in statistical learning.
Our results provide algorithm-depennent guarantees for uncertainty quantification, and they could be leveraged to obtain confidence intervals (CIs) for non-convex and non-smooth learning problems. This is contrary to the majority of the existing results in statistics, which only establish normality results for the true stationary point of the non-convex objective function; see for example [12, 34). While being useful, such results completely ignore the computational hardships associated with non-convex optimization; hence, their practical implications are limited. On the other hand, in the optimization and learning theory literature, a majority of the existing results establish the rate of convergence of an algorithm to a critical point, and do not quantify the fluctuations associated with that algorithm. Our work bridges these separate lines of thought by providing asymptotic normality results directly for the SGD algorithm used for minimizing non-convex and non-smooth functions.
More Related Works Establishing asymptotic normality results for the SGD algorithm began with the works of [35, 36, 37, 38, 39), with [28] providing a definitive result for strongly convex objectives. In particular, [28] and [38] established that the averaged SGD iterates with an appropriately chosen decreasing step size is asymptotically normal with the variance achieving the Cramer- Rao lower

---

bound for parameter estimation. Recent works, for example [40, 41, 29, 42, 43, 44]. leverage the asymptotic normality analysis of [28], which leads to computing CIs for SGD. The benefits of constant step size SGD for faster convergence under overparametrization has also been demonstrated in the works of [45, 46, 47, 48]. The use of Markov chain theory to study constant step size stochastic approximation algorithms has been considered in several works [49, 50, 51, 25, 52, 53]. Recently, [I. 54] investigated the asymptotic variance of the constant step size SGD. We emphasize here that most of the above works assume strongly convex and smooth objective functions.
The non-linear autoregressive (NLAR) process [55, 56, 57] a specification of our general frame- work (2) with the noise sequence hEu being a collection of i.id mean-zero random vectors with continuous density supported on I However, the methodology for establishing the geometric ergodicity of NLAR [55, 56, 57, 58] by no means straightforward to carry over to the optimization setting, and does not generalize immediately to the state-dependent noise setup considered in our paper (see Assumption 2.3). In contrast, we establish the geometric ergodicity under easily verifiable assumptions on the objective function using tools from Markov chain theory. Moreover, additional steps are needed to go from geometric ergodicity to CLT results (especially the chain starts with an arbitrary initial distribution), while we directly obtain a CLT result by explicitly leveraging the Markov chain structure.
Furthermore, there exists a vast literature on analyzing Langevin diffusion-based sampling algorithms which relies on the much simpler i.i.d. Gaussian noise sequence. We refer the interested reader to [59, 60, 32, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70] and the references therein, for details.
Finally, recent work [71] establish the trade-off between the stability, statistical accuracy, and computational efficiency for the non-convex optimization algorithms.
Notation. For b E R. denote by a V b and a A b the maximum and the minimum of a and b, respectively. We use || | to denote the Euclidean norm Rd, We denote the largest eigenvalue of the matrix A as Amax(A) and the smallest one as Amin ( (A). Let FR, IP) represent probability space, and denote by (IR"), the Borel o-field of (R.. Let Pk (E ;= {V : Sa. [[]])=((d0) < co} denote the set of probability measures with finite k-th moments. For a probability distribution a and a function g on X. we define (g)) == Sx (z)) and C2(T) = {g X - IR (Tg)) < oo).
2 Central Limit Theorem for The Constant Step Size SGD
In this section, we establish an asymptotic central limit theorem (CLT) for the averaging of the constant step size SGD iterates given in (2) when the objective function is potentially non-convex, non-smooth, and has quadratically growing tails. More specifically, we first prove that there exists unique stationary distribution T. E PP2 (IR") for the Markov chain defined by the SGD algorithm when the objective function is dissipative (see Assumption 2.2) with gradient exhibiting at most linear growth (see Assumption 2.1). Furthermore, under the same conditions, we prove that a CLT holds for the follows, we list and discuss the main assumptions required to establish CLT for the SGD iterates, and compare them to those existing in the literature.
averaging, and it is independent of the initialization. In what
Assumption 2.1 (Linear growth). The gradient of the objective function I has most linear growth. That is, for some I 2 O, we have [[V] < IL(1 + [1@1)) for all 0 E TRd
Majority of the results on SGD focus on smooth functions with gradients satisfying V f(')) < ||0 - 6']l for all 0, 6' E IRd: see e.g. [28, 1]. The above condition allows for non- non-smooth objectives, and is a significant relaxation of the standard Lipschitz gradient condition. Assumption 2.2 (Dissipativity). The objective function f is (a, 3)ddissipative. That is, there exists positive constants a, B such that (0, (f) 2 a aI|00]
B for all 0 eeD Rdd
The dissipativity assumption has its origins in the analysis of dynamical systems, and is used widely in the analysis of optimization and learning algorithms [72, 31, 33, 73]. It also recently have been used in Bayesian analysis [74]. This assumption could be viewed as a relaxation of strong convexity since it restricts the quadratic growth assumption to the tails of the function f, enforcing no local growth around the first-order critical points. A canonical example for this condition is the sum of quadratic and any non-convex function with bounded gradient. For example, consider the function
+ x² + 10 sin(z) which is clearly non-convex and (1, 2d)ddisiiaa It is worth mentioning
3

---

that many non-convex problems that arise in statistical learning such as phase retrieval [53] satisfy Assumption 2.2. We provide examples in Section 4.
Assumption 2.3 (Noise sequence). Gradient noise sequence 15r is a collection of Li.d. random fields satisfying [[)] O and 11/2[15 (0)]l S T.g(1 + [[01)) for any 0 E TR and positive constant Lg. Moreover, for each 0 E Re the distribution of the random variable & (0) can be decomposed as 11,0 + 122,0 where P1,0 has a density, say ps. with respect to Lebesgue measure which satisfies infsec po (1) > 0 for any bounded set C and any t E IR...
Assumption 2.3 as formulated above is stronger than what is needed in the proofs. It can easily be seen that the lower bound on the density ps is only required to hold for specific set whose form depends on and various constants from Assumptions 2.1 2.1.2.3. The form of this set is complicated, and an exact expression is given in the Appendix see (12). We also emphasize that Assumption 2.3 does not specify any explicit parametric form for the distribution of the noise sequence contrary to recent works in non-convex settings where dissipitavity condition has been heavily utilized [31, 73, 33].
We now establish the existence and uniqueness of the stationary distribution of the SGD iterates.
Proposition 2.1 (Ergodicity of SGD). Let the Assumptions 2. 1-3. hold, and the step size satisfy
0 D<<<> / [/2 +3L2
(a) SGD (2) admits a unique stationary distribution xn E (2 depending on the step size n7.
(b) For test function a Rd - IR satisfying ((0) S L1 + 1101), V0 E R2 and some L& > O,
and for any initialization 0 = Oo E IR of the SGD algorithm, there exists p E (0, 1) and k (both depending 17) such that we have
E B[ (,) S x (1+ 116,17), where (0) = (()))dT((
The uniqueness of the stationary distribution of the constant step size SGD has been established in [1] for strongly convex and smooth objectives. In Proposition 1. relax both of these assumptions allowing for non-convex and non-smooth objectives. Our proof relies on V-uniform ergodicity [75), which is fundamentally different from the ergodicity analysis in [1]. Under the dissipativity condition (quadratic growth of f). geometric ergodicity in Proposition 2.1 is not surprising; yet, it is worth highlighting that the function as well as the noise sequence require significantly less structure than what was assumed in the literature. The above step size assumption is almost standard and it is required to obtain uniform bound on the moments of SGD iterates. We highlight that similar the gradient descent algorithm, the step size depends on quantity that serves as surrogate condition number in our setting, namely, L/a. Note that o depends on 7) and will typically be converging to one if 17 + 0. Thus convergence in Proposition (b) can be expected to be slower when becomes smaller. However, smaller r) leads to better control of the asymptotie bias (under additional regularity assumptions), see Theorems 3.1-3.3. Both of those statements (slower convergence for smaller 17 but smaller bias eventually) are confirmed in our numerical experiments, see Figure 1(d.h).
Next, we state our first principal contribution, a central limit theorem for the averaged SGD iterates starting from any initial distribution, for a non-convex objective. For a test function Φ Rd - RR we denote the centered partial sums of é evaluated at the SGD iterates with S,, (o), i.e..
(x) = Ei=o ((((2) - where Ty(d) = (())dx,((x)
Theorem 2.1 (CLT). Let the Assumptions 2.1-2.3 hold. For a step size n and a test function satisfying the conditions in Proposition 2.1, we define o² (d) == limm n LI,, (0)]. Then,
n (,,() L 02.
The above result characterizes the fluctuations of test function & averaged across SGD iterates, even when the objective function is both non-convex and non-smooth. The asymptotic variance in the above CLT can be equivalently stated in another compact form. If we define the centered test function
as (()) = ((0) (1). the asymptotic variance can be written as
22 (bb (hr) T., (h?), where h = Ei B B[A

---

Indeed, this is the variance we compute at the end of our proof in Section A. However, the expression in Theorem 2.1 is obtained by simply applying [58, Thm 21.2.6]. For the case of strongly convex functions with decreasing step size schedule, it is well-known from the works of [28, 38] that the limiting variance of the averaged SGD iterates achieves the Cramer- lower bound for parameter estimation; see also [76, 30] for non-asymptotic rates in various metrics. The question of providing lower bounds for the limiting variance of the critical points in the non-convex setting is extremely subtle, and is often handled on case-by-case basis. We refer the interested reader to [77, 78, 12].
There are several important implications of the above CLT for constructing CIs in practice. First note that, following the standard construction in inference, one can write the distribution of the sample mean approximately as n (,) (O n o2 T., (o)). Here, one needs to estimate the population quantity, the asymptotic variance o (ø), for the purpose of obtaining Cls. In Section 5, we discuss three strategies for estimating this quantity, which could be eventually used for inference in practice. A theoretical analysis of the proposed approaches in Section 5 is beyond the scope of this work.
3 Bias of the Constant Step Size SGD
Proposition (b) shows that the expectation of test function evaluated at the k-th iterate converges exponentially fast to the expected value of the stationary distribution Ty. Therefore. complete characterization of the properties of the SGD requires a control over the asymptotic bias [, =(0)) for critical point 0*. It turns out that this bias behavior is intimately related to the local properties of the objective around its critical points. Therefore, under the mild assumptions that yield the CLT, one cannot expect a tight control over the bias. This section contains three types of bias analyses under different local growth conditions on the objective function f. characterizing the bias behavior in various non-convex and convex settings. We further note that without local regularity conditions, is still possible to show that the SGD iterates (2) move towards compact ball containing all critical points exponentially fast; formal statement of this result along with a corresponding discussion is provided in Proposition B.I, which is deferred to Appendix B. Throughout this section, make slightly stronger assumption on the noise sequence.
Assumption 3.1 (Fourth moment of the noise). Gradient noise sequence {Ck]k21 satisfies Assump- tion 2.3, and I8 (0) < Le + [[0][²), for any 0 Rd where Lę is as in Assumption 2.3.
Localized Dissipativity Condition: We now introduce the generalized dissipativity condition which, in addition to the quadratic tail growth property enforced in Assumption 2.2, imposes a local growth within some compact region, around the unique critical point 6*
Assumption 3.2 (Localized dissipativity). The objective function f satisfies
Sale 1- - 3 g 0-1)) |00 0- < R,
||0 - 00 2 R
(V) 0 0-) 2
where 6* E TR. is the unique minimizer of f, R= 5 + a convex function with g(0) = O whose inverse exists.
v
a with ē E (0), g: 00) + 10, oo)
If g(x) = x², the objective function is locally strongly convex. However, the above assumption covers a wide range of objectives with different local growth rates depending on the function g. Next, we show that the above assumption along with the assumptions leading to the CLT is sufficient to establish an algorithmic control over the bias with a sufficiently small step size.
Theorem 3.1. Let the Assumptions 2.1, 3.1, and 3.2 hold. Then SGD iterates with step size satisfying 0 < 1) < Ct,a for Ct, in (16) admit the stationary distribution ((r) ~ Tr, which satisfies
E E[ 10]] S nn
Further, for a test function @= Rdd + IR that is L. Lipschiiiz the bias satisfies
TT, (0) - ((0)) I < Lg (Cn/5 + g-
where
C C3=3(332 + +3L 1/2 (1/++3///)))))))) (1 + 100^)2).
(5)
5

---

-0(0)) < (n)) If local growth is quadratic, i.e. g(x) = x², the growth is locally slower than the linear case; thus, we get the bias control (6) - p(0*) I (1))/2), which is worse in step size dependency; it reduces to the bound derived in [1, Lemma 10]. We highlight that [79] proves the following lower bound: lim inf Bi10g" - 1- 2 cn/1/2 for some c > under the assumption of Lipsehitz gradients. This is in line with our findings since Lipschits gradients imply g(x) S x² for small x.
If the local growth is linear, i.e. g(x) I, we obtain the bias [T,(
Generalized Lojasiewicz Condition: In this section we work with a generalization of the commonly used Lojasiewizz condition in optimization.
Assumption 3.3 (Generalized Lojasiewiez condition). The finction f has critical point 8" and it satisfies
|<011 (2(5(0) - f(0))
10 - 0- 2 R
( f((*)
|00 - 8 < R,
where y, R > O, and g: [0, oo) + 10, oc) is convex function with g 0 whose inverse exists.
In the case g(z) = x with K E 2), for example, the above condition termed as the Lojasiewicz inequality [80], and for = 1, it reduces to the well-known
(PL) inequality [81].
Note that this inequality implies that every critical point is a global minimizer; yet, it does not imply the existence of a unique critical point.
The next result establishes an algorithmically controllable bias bound in terms of the step size.
Theorem 3.2. Let the Assumptions 2.1.2.2, 3.1, and 3.3 hold, and the Hessian satisfies V f(0)] 1 7(1 + |001), 40 Rd and some L. O. Then, the SGI) iterates with a step size satisfying 0 < 17 CL A LL for CL.a: cLa in (16) have the stationary distribution Tn.
(π( - f(0") و
2M
+ 2-
2Mn
2-
where M 1
3
1/2 + 31
1/4 )² m + m3/4 + [100| (d0) (d0)) with
m = (B 6L
+3L + 16) ||0| TT (dB) 16L 2L 128L + SL. 3/2]
1/2
Additionally, if the test function is given as o = 3o f for a L3
o, it holds that
(T)(0) - x(0)) - L { 2M ing +
2MH 2-67
For smooth objectives with Lipschitz gradient, [81] provides linear rate under the PL-inequality (see also [82, Lemma 2)), which yields the asymptotic bias [T) ((0)) S O(n). The above result recovers their findings a special case, and provides considerable generalization.
Convexity: To make the analysis of constant step size SGD complete, we digress from the main theme of this paper and consider this algorithm in the (non-strongly) convex regime, for which there no bias characterization known to authors. We show that, under the convexity assumption, one can achieve the same bias control as in the case of PL-inequality.
Theorem 3.3. Let the Assumptions 2. 2,2., and 3.1 hold for convex function f. Then, the SGD iterates with a step size 0 1) CL,a for CLa in (16) admit the stationary distribution Ty and for minimizer 6* it satisfies
n. (, f(0)==(0))
for C in (5). Further, if the test function is given as 6- = 30 f for Lis-iicccttttffattioo Φ. then,
(w) - -00) S LgCny
Convexity implies that any critical point 6" is global minimizer, which is similar to the PL-inequality; yet, it does not imply unique minimizer unlike strong convexity. The resulting step size dependency of the bias is the same as in the case of PL.iiequullty, which is because both of these conditions assert a similar gradient- based domination criterion on the sub-optimality. That is, we have the convex case (V f(0), 0 - 0r) 2 f(0) - f(0)), and in the case of PL-inequality y -1]((() 2
- f(0)-f(0)

---

4 Examples and Numerical Studies
We now demonstrate the asymptotic normality and bias in non-convex optimization with two examples arising in robust statistics for which our assumptions can be verified. We consider the online SGD setting with the update rule: 0/7 T z Σ F Zz)), for k 2 0. with independent samples 2j ~ P(Z) used to estimate the true gradient in each iteration & and also the semi- stochastic setting, where the noise sequence (5)(0))k21 is independent of f and is simply sequence of i..d. random vectors- such a setting helps verifying our assumptions more explicitly.
be
4.1 Regularized MLE for heavy-tailed linear regression
While the least-squares loss function is common in the context of linear regression, it is well- documented that it suffers from robustness issues when the error distribution the model is heavy-
tailed [83]. Indeed in fields like finance, oftentimes the Student's t-distribution is used to model
the heavy-tailed error [84]. In this case, defining the random vector := (X, Y). the stochastic optimization problem in (3) is given by the expectation of the function F(Z,0) 0) == log(1 (1 (Y
(X, 0)) + 2 ||012, which is non-convex (as a function of 0) for small penalty levels À > 0. Correspondingly, given n independent and identically distributed samples (x, y1), the finite-sum version of the optimization problem corresponds to minimizing the following objective function
f(0) = 2m Σ log + (yi - (xs: 0))²) + 1110
(6)
We consider the sinite-sum setup and we verify our assumptions and empirically demonstrate our results on CLT well the bias in clean manner.
4.1.1 Semi-stochastic Gradient Descent
In the experiments, X := (XI....,Xm) Xm) E Rmdd represents a fixed design matrix generated from Xij ~ Bernoull(++1)//44 and = (yI,..., ,m.) E Rmm represents the response vector iid generated according to the linear model y/: = (x,, dmw)) + E with (Ouue); ~ Unif(0, 1), and e is Student-t distributed (df = 10) noise. We choose function (0)) = ||0|] unless stated otherwise.
5000, d = 10, and the Lipschitz test
Asymptotic normality: Fig. 1-(a.b.c.d) demonstrates the normality and the bias of SGD with heavy- tailed gradient noise distributed as Student-t (df = 5). Each plot has two density curves where red and blue curves in Fig. I-(a,b) respectively correspond to initializations with 0g = (L....,)) 1)" and % (1.5.... 1.5)T with step size 1) 0.3; green and orange curves in Fig. 1-c correspond to step sizes 17 0.2 and n/ = 0.3 with initialization tn. All experiments are based on 4000 Monte Carlo runs. We observe in Fig. 1-a that different initializations have an early impact on the normality when the number of iterations is moderate. However, when SGD is run for longer time, this effect removed as in Fig. 1-b. Lastly, Fig.1-c I-c demonstrates the effect of step size on the normality, where the means are different for different step sizes as they depend on the stationary distribution Ty. Indeed, the above results are not surprising as can verify that the assumptions of Theorem 2.1 are satisfied.
Lemma 4.1. The objective function (6) satisfies Assumptions 2 and 2.2. Further, Assumption 2.3 is also satisfied with the Student-t distributed (df = 10) noise.
Bias: In order to demonstrate the bias behavior without speculation, one needs the global minimum 0 of the non-convex problem. Therefore, we simplify the problem (6) to another non-convex problem
f(0)= 1/2 log(1 + [1012) + 1101
Notice that the general structure is the same, with no data, and H" is known, i.e. 0* g==0 0. We choose the test function 6(0) 6o f()), where x(z) 1/(1 -=) is Lipschitz. Fig. 1-(d) demonstrates how the bias (Ø) x(0*) changes over iterations, where different curves correspond to different step sizes. We notice that larger step size provides fast initial decrease; yet the resulting asymptotic bias is larger which aligns with our theory- indeed, a smaller asymptotic bias for a smaller step size v is predicted by Theorem 3.2 while slower convergence can be expected given the discussion after Proposition 2.1. The following lemma proves that our assumptions are satisfied for this objective.
Lemma 4.2. The objective function (7) is non-convex when X is sufficiently small, and it satisfies Assumptions 2. 1,2., and 3.3. Further, Assumption 3.1 is also satisfied for this example.
7

---

Iterations-3000
Iterations-3000
D63 500
$,0000
000
010
R.04
0.
0.00
0.00
0.00
60
00
F00
555
250
111 (.(4)
Persttone H4
64
D4
0010
0,15
Dentity
0.04
D104
0044
0.02
0022
30
40
50
70
230
250
270
200
250
0.00
1003
(. (H)
1/9
n /,11/8, [0]
2M
Figure First and second rows correspond to non-convex examples in Sections 4.1.1 and 4.2.1, n respectively. Figures (a.b), (c.f) show the density of n S,1 - k=1 o(0(") with different initializations (red, blue) for different number of iterations. Figures (c.g) show the same density with different step sizes. Figures (d.h) show the evolution of bias against iterations.
4.1.2 Online Stochastic Gradient Descent
For our online SGD experiments, we use by = 2, for all i obtain the stochastic gradient. We also experimented with mg 1, 10, 50 and observed similar behavior. The distribution of the random vector = (X,Y)
1) E Rd+1, as follows: Each coordinate of the vector X Rd, is generated as Bernoulli+#1)/ (=t and given vector X, the response Y E is generated according to the linear model = (X, 2mm)+ with each coordinate of Orme IR generated from Unif(0, 1), and fixed, and R is Student-t (df 10) noise. We choose d = 10, and set a burn-in period of size 100. Asymptotic normality: Fig. c-(a,b,c) demonstrates the normality of online SGD. Each plot has two density curves where red and blue curves in Fig. (a respectively correspond to initializations with 0g = (I...., 1)" and 0g (2.5, ..,, 2.5) with step size == 0.3; green and orange curves in Fig. 2-c correspond to step sizes 7) = 0.2 and ry' = 0.3 with initialization 9g- All experiments are based on 4000 Monte Carlo runs. We observe in Fig. 2-a that different initializations have early impact on the normality when the number of iterations moderate. However, when SGD is run for a longer time, this dependence is removed in Fig. 2-b. Lastly, Fig.2-c demonstrates the effect of step size on the normality, where the means are different for different step sizes as they depend on the stationary distribution म.. Indeed, all these observations
predicted by our theory.
4.2 Regularized Blake-Zisserma MLE for corrupted linear regression
While the above example based linear-regression with heavy-tailed noise, now consider the case of heavy-tailed regression with corrupted noise. this setup, the noise model in lincar regression is assumed to be Gaussian, but fraction of the noise vectors assumed be corrupted in the sense that they are drawn from a uniform distribution. Such a scenario arises in visual reconstruction problems;
for example [85, 33] for details. In this case, defining the random vector Z = (X,Y), the stochastic optimization problem in (3) is given by the expectation of the function F(Z,0) 0) == log ( (Y--(- 0)) + = ,, for v > Similar the previous case, we also consider the finite-sum version: Given independent and identically distributed samples (x;, Bi), corresponds to minimizing the following objective function
f(0) = Σ
m i== log V + e (v- (x:. (wi-(x; 03)) + 11013 v >> 0.
(8)
4.2.1 Semi-stochastic Gradient Descent
the experiments, we use the same setup and parameters in Section 4. 1. Fig I-(e.f.g) demonstrates the asymptotic normality of the SGD with heavy-tailed gradient noise Student-I(df = 6). The experimental setup the same as the previous example with the same values for Oo, %- 1), 1/'. We observe the early impact of initialization in Fig 1-a, the clear normality in Fig. 1-b, and the effect of step size on CLT in 1-g.1-c. These observations also align with our theory since this objective also satisfies our assumptions.
Asymptotic normality:
8

---

Viteretions=200
Reeatiion==3000
Viterationn=1000
Fc4.1
0.8
0.6
6 0.6
Densiy
0.4
0.4
0.4
0.0
(1))(())
23
24
25
26
27
22
25
24
25
26
2010
Munner
(013 1907
Hamber
[0]
000
Ex with
1.5
B4
9g
6g
65 1.0
Density
1.0
0.8
0.5
0.5
0.
2.5
0.0
12.0
12.5
0.0
(x))
(.())
Mumber of 1er0i211
Narber of bardorr
(7
Serted
Lorgetan Dertice Sabrersiigg
Figure 2: Left: First and second rows correspond to non-convex examples in Sections 4.1.2 and 4.2.2, respectively. Figures (a.b), (d.e) show the density of n 1n11/2 (6) = - Ex= x( with dif- ferent initializations (red, blue) for different number of iterations. Figures (c.f) show the same density with different step sizes. Right: Coverage probabilities for Subsampling quantile, Subsampling var, and Long-run functions of the number of iterations. Subsampling quantile method outmatches the others in terms of coverage probability and achieves the nominal level with larger iterations.
Lemma 4.3. The objective function (8) satisfies Assumptions 2.1, 2.2. Further, Assumption 2.3 is also satisfied with the Student-r (df 10) noise.
Bias: Similar to the previous example, we simplify the problem so that we can compute the bias Tr (Ø) o(0)). We consider the function
((0) == - log (u + -111 + 1010, 0.
We observe in Fig.1-h 1-h that smaller step sizes lead to smaller asymptotic bias. One can verify that this can be predicted from Theorem 3.1.
Lemma 4.4. The objective function (9) is non-convex when X is sufficiently small, and it satisfies Assumptions 2.1 and 3.2. Further, Assumption 3.1 is also satisfied for this example.
4.2.2 Online Stochastic Gradient Descent
Asymptotic normality: In the experiments, we use the same setup as in Section 4.1.2. Fig. 2-(d.e,f) demonstrates the normality of online SGD, Each plot has density curves where red and blue curves in Fig. 2-(d.e) respectively correspond initializations with 9g (l...., 1) and 6" (1.5, .1....... 1.5) with step size 17 0.3: green and orange curves in Fig. 2-c correspond to step sizes r 0.2 and ny' 0.3 with initialization 0g All experiments are based on 4000 Monte Carlo runs. We observe in Fig. 2-d that different initializations have an early impact on the normality when the number of iterations are moderate. However, when SGD is run for a longer time, this effect is removed as in Fig. 2-e. Lastly, Fig. 2-f demonstrates the effect of step size on the normality, where the means are different for different step sizes as they depend on the stationary distribution n..
Discussions
By leveraging the connection between constant step size SGD and Markov chains [1], we provided theoretical results characterizing the fluctuations and bias of SGD for non-convex and non-smooth optimization which arises frequently in statistical learning.
Estimating the Asymptotic Variance: As discussed in Section 2, in order to use the established CLT to compute Cis in practice, the population expectation Tr, (Φ) and asymptotic variance o² (o) have to be estimated. We suggest the following three ways to do so:
Estimate them based sample average of single trajectory of SGD iterates, i.e., the mean
(Ø) is estimated as n Σ (((()) and the asymptotic variance o2, (Ø) can be estimated by
adopting the online approach of [86] to the constant step size setting. The variance o (Ø) can

---

also be estimated by the Newey-Wert Westt long-run run variance estimation [87, 88] or empirical variance estimation based on sub-sampling [89, Sections 4.2 and 4.6] for single trajectory.
First run N parallel SGD trajectories and compute the average of each trajectory. to obtain N independent observations from the stationary distribution "y.. Next, use the N observations to compute the sample mean and the sample variance estimators for (T( and o (Ø).
Leverage the online bootstrap and variance estimation approaches proposed in [43, 41, 90] for the constant step size SGD setting in order to obtain estimates for (() and o (o).
As a confirmation of the practicability of constructing Cls, we provide preliminary experimental results for constructing CIs with minibatch SGD. We consider the data generation setup described in Sections 4.1 and 4.2 with step size 0.3, and run online SGD with batch size 2. In each run, the first 200 values are discarded. CIs are constructed for each trajectory based sub-sampling with empirical CDF (Subsampling quantile) and variance estimation (Subsampling var) [89, Sections 4.2 and 4.6]. and Newey-War Westt long-run variance estimation (Long-run var) with data-driven bandwidth selection [87, 88]. Empirical coverage results as a function of iteration numbers (nominal level 95%. 4000 Monte Carlo replications) for the three methods and different initializations (fp = (1, 1)T
and 0g (1.5,... 1.5)T) are reported in Figure 2 (right). A non-asymptotic justification of the relative merits of the above variance estimation approaches are left as future work.
Acknowledgements
MAE is partially funded by NSERC Grant [2019-06167], Connaught New Researcher Award, CIFAR Al Chairs program, and CIFAR AI Catalyst grant. KB is partially supported by seed grant from the Center for Data Science and Artificial Intelligence Research, UC Davis. SV is partially supported by a discovery grant from NSERC of Canada and a Connaught New Researcher Award. The authors thank Yichen Zhang for helpful comments earlier version of this manuscript.
References
[1] Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and markov chains. The Annals of Statistics (lo appear), 2019. (Cited on pages 1, 2, 3, 4, 6, 9, and 16.)
[2] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. In Conference on Learning Theory, pages 797- 842, 2015. (Cited page 1.)
[3] Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. In Advances Neural Information Processing Systems, pages 2973-2981 2016. (Cited on page 1.)
[4] Dong Xia, Ming Yuan, and Cun-Hui Zhang. Statistically optimal and computationally efficient low rank tensor completion from noisy entries. The Annals of Statistics (to appear), 2019. (Cited on page 1.)
[5] Yuejie Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions on Signal Processing, 67(20):5239-526, 2019. (Cited on page 1.)
[6] Changxiao Cai, Gen Li, H Vincent Poor, and Yuxin Chen. Nonconvex low-rank tensor comple- tion from noisy data. In Advances in Neural Information Processing Systems, pages 1861-1872, 2019. (Cited on page 1.)
[7] Murat A Erdogdu, Yash Deshpande, and Andrea Montanari. Inference in graphical models via semidefinite programming hierarchies. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 416-424 2017. (Cited on page 1.)
[8] Murat A Erdogdu, Asuman Ozdaglar, Pablo A Parrilo, and Nuri Denizcan Vanli. Conver- gence rate of block-coordinatte maximization borer-monteiro method for solving large sdps. Mathematical Programming, pages 1-39, 2021. (Cited page
10

---

[9] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016. (Cited on page 1.)
[10] Prateek Jain and Purushottam Kar. Non-convex optimization for machine learning. Foundations and Trends@ in Machine Learning, 10(3-4)114233388 2017. (Cited on page 1.)
[11] Wesley J Maddox, Pavel Izmailov, Timur Garipov, Dmitry P Vetrov, and Andrew Gordon Wilson. A simple baseline for bayesian uncertainty in deep learning. Advances in Neural Information Processing Systems, pages 13132-13143, 2019. (Cited page 1.)
[12] Po-Ling Loh. Statistical consistency and asymptotic normality for high- nigh-dimensional robust m-estimators. The Annals of Statistics, 45(2):866-883) 886,, 2017. (Cited on pages 1, and 5.)
[13] Guillaume Lecué, Matthieu Lerasle, and Timothée Mathieu. Robust classification via mom minimization. arXiv preprint arXiv: 03106, 2018. (Cited page 1.)
[14] Song Mei, Yu Bai, and Andrea Montanari. The landscape of empirical risk for nonconvex losses. The Annals of Statistics, 46(6A):2747-2774, 2018. (Cited on page 1.)
[15] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal Optimization, 23(4):2341 2013. (Cited on
page 1.)
[16] Cong Fang. Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non- convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pages 689-699, 2018. (Cited on page 1.)
[17] Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical Programming. 108(1):177-200 2006. (Cited on page 1.)
[18] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In Proceedings of the 34th International Conference on Machine Searning-Volume 70, pages 1724-1732. JMLR. org, 2017. (Cited on page 1.)
[19] Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael Jordan. Stochastic cubic regularization for fast nonconvex optimization. In Advances in neural information processing systems, pages 2899-2908, 2018. (Cited on page 1.)
[20] Kenji Kawaguchi. Deep learning without poor local minima. In Advances in neural information processing systems, pages 586-594, 2016. (Cited on page 1.)
[21] Song Mei, Theodor Misiakiewiez, Andrea Montanari, and Roberto Imbuzeiro Oliveira. Solving sdps for synchronization and maxcut problems via the grothendieck inequality. Conference on Learning Theory, pages 1476-1515, 2017. (Cited on page 1.)
[22] Andreas Elsener and Sara van de Geer. Sharp oracle inequalities for stationary points of nonconvex penalized m-estimators. IEEE Transactions on Information Theory, 65(3):1452- 1472, 2018. (Cited on page 1.)
[23] DA Freedman and P Diaconis. On inconsistent m-estimators. The Annals Statistics, 10(2):454- 461, 1982. (Cited page 1.)
[24] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951. (Cited page 2.)
[25]
Fort and Gilles Pages. Asymptotic behavior of a markovian stochastic algorithm with constant step. SIAM journal on control and optimization, 37(5):1456-14955 1999. (Cited on pages and 3.)
[26] Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. Advances in Neural Information Processing Systems, pages 4148-4158 2017. (Cited page 2.)

---

[27] Lukas Balles and Philipp Hennig. Dissecting adam: The sign, magnitude and variance of stochastic gradients. In International Conference on Machine Learning, pages 404 413, 2018. (Cited on page 2.)
[28] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838-855 1992. (Cited on pages 2. 3, and 5.)
[29] John Duchi and Feng Ruan. Asymptotic optimality in stochastic optimization. Arxiv Preprint, 2018. (Cited on pages and 3.)
[30] Andreas Anastasiou, Krishnakumar Balasubramanian, and Murat A Erdogdu. Normal approxi- mation for stochastic gradient descent via non-asympiotic rates of martingale clt. In Conference on Learning Theory, pages 1 115-137, 2019. (Cited on pages 2 and S.)
[31] Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: nonasymptotic analysis. In Conference on Learning Theory, pages 1703, 2017. (Cited on pages 2, 3, and 4.)
[32] Xiang Cheng. Niladri S Chatterji. Yasin Abbasi- Yadkori, Peter L Bartlett, and Michael I Jordan. Sharp convergence rates for langevin dynamics in the nonconvex setting. arXiv preprint /
2018. (Cited on pages 2 and 3.)
[33] Murat A Erdogdu, Lester Mackey, and Ohad Shamir. Global non-convex optimization with discretized diffusions. In Advances in Neural Information Processing Systems, pages 9671-9680. 2018. (Cited on pages 2, 3, 4, and 8.)
[34] Zhengling Qi. Ying Cui, Yufeng Liu, and Jong-Shi Pang. Statistical analysis of station- ary solutions of coupled nonconvex nonsmooth empirical risk minimization. arXiv preprint arXiv: arXiv:1910002488, 2019. (Cited page 2.)
[35] Kai Lai Chung. On stochastic approximation method. The Annals of Mathematical Statistics, pages 463-483, 1954. (Cited on page 2.)
[36] Jerome Sacks. Asymptotic distribution of stochastic approximation procedures. The Annals of Mathematical Statistics, 29(2):373-405, 1958. (Cited on page 2.)
[37] Vaclav Fabian. On asymptotic normality in stochastic approximation. The Annals of Mathemat- ical Statistics, 39(4):1327-1332, 1968. (Cited on page 2.)
[38] David Ruppert. Efficient estimations from slowly convergent robbins-monro process. Techni- cal report, Cornell University Operations Research and Industrial Engineering, 1988. (Cited on pages and 5.)
[39] Alexander Shapiro. Asymptotic properties of statistical estimators in stochastic programming. The Annals of Statstics, 17(2):811-858, 1989. (Cited on page 2.)
[40] Nilesh Tripuraneni, Nicolas Flammarion, Francis Bach, and Michael Jordan. Averaging stochastic gradient descent on riemannian manifolds. arXiv preprint 10X2::8802.0922, 2018. (Cited on page 3.)
[41] Weijie Su and Yuancheng Zhu. Statistical inference for online learning and stochastic approxi- mation via hierarchical incremental gradient descent. arXiv preprint wxXiv:182.00483 2018. (Cited on pages 3 and 10.)
[42] Panos Toulis and Edoardo M Airoldi. Asymptotic and finite-sample properties of estimators based on stochastic gradients. The Annals of Statistics, 15(4):16941172) 2017. (Cited on page 3.)
[43] Yixin Fang, Jinfeng Xu, and Lei Yang. Online bootstrap confidence intervals for the stochastic gradient descent estimator. The Journal of Machine Learning Research, 191333033-3373 2018. (Cited on pages 3 and 10.)
[44] Hongjian Wang, Mert Gürbüzbalaban, Lingjiong Zhu, Umut Şimşekli, and Murat A Erdogdu. Convergence rates of stochastic gradient descent under infinite noise variance, arXiv preprint 11X1v:2102.10346. 2021. (Cited page 3.)
12

---

[45] Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under strong growth condition. arXiv preprint arXiv:1308.6333 1300,6670 2013. (Cited on page 3.)
[46] Deanna Needell, Rachel Ward, and Nati Srebro. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. In Advances neural information processing systems, pages 1017-1025, 2014. (Cited on page 3.)
[47] Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern parammetrttee learning. In International Conference on Machine Learning, pages 3325-33333 2018. (Cited on page
[48] Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and an accelerated perceptron. In The 22nd International Conference on Artificial Intelligence and Stutistccs, pages 1195-1204, 2019. (Cited on page 3.)
[49] Yuri Kifer. Random perturbations of dynamical systems. Nonlinear Problems in Future Particle Accelerators. World Scientific, page 189, 1988. (Cited on page 3.)
[50] Michel Benaim. A dynamical system approach to stochastic approximations. SIAM Journal on Control and Optimization, 34(2):437-477 472, 1996. (Cited page 3.)
[51] Priouret and A Yu Veretenikov. remark on the stability of the Ims tracking algorithm. Stochastic analysis and applications, 16(1):119-129, 1998. (Cited on page 3.)
[52] Rafik Aguech, Eric Moulines, and Pierre Priouret. On perturbation approach for the analysis of stochastic tracking algorithms. SIAM Journal on Control and Optimization, 39(3):872-899 2000. (Cited on page 3.)
[53] Yan Shuo Tan and Roman Vershynin. Online stochastic gradient descent with arbitrary initial- ization solves non-smooth, non-convex phase retrieval. arXiv preprint arXiv: 12837, 2019. (Cited on pages 3 and 4.)
[54] Jerry Chee and Panos Toulis. Convergence diagnostics for stochastic gradient descent with constant learning rate. In International Conference on Artificial Intelligence and Statisties, pages 1475-1485, 2018. (Cited page 3.)
[55] Rabi Bhattacharya and Chanho Lee. On geometric ergodicity of nonlinear autoregressive models. Statistics & Probability Letters, 2114):3 1995. (Cited on page 3.)
[56] Eckhard Liebscher. Towards unified approach for proving geometric ergodicity and mixing properties nonlinear autoregressive processes. Journal of Time Series Analysis, 26(5):669~ 689, 2005. (Cited page
[57] HZ An and SG Chen. A note on the ergodicity of non-linear autoregressive model. Statistics probability letters, 34(4)3365-372, 1997. (Cited on page 3.)
[58] Randal Douc, Eric Moulines, Pierre Priouret, and Philippe Soulier. Markov chains. Springer, 2018. (Cited on pages 3, 5, and 19.)
[59] Arnak S Dalalyan and Avetik G Karagulyan. User-friendly guarantees for the langevin monte carlo with inaccurate gradient. arXiv preprint arXiv:1710.0009 2017. (Cited on page 3.)
[60] Nicolas Brosse, Alain Durmus, fric Moulines, and Marcelo Pereyra. Sampling from a log- concave distribution with compact support with proximal langevin monte carlo. In COLT, 2017. (Cited on page 3.)
[61] Alain Durmus and Eric Moulines. Nonasymptotic convergence analysis for the unadjusted langevin algorithm. The Annals of Applied Probability, 270):1551-1587, 2017. (Cited on page 3.)
[62] Arnak S Dalalyan. Theoretical guarantees for approximate sampling from smooth and log- concave densities. Journal of the Royal Stotistical Society: Series (Statistical Methodology). 79(3):651-676, 2017. (Cited on page
13

---

[63] Xiang Cheng, Niladri S Chatterji, Peter L Bartlett, and Michael I Jordan. Underdamped langevin meme: A non-asymptotic analysis. arXiv preprint arXiv:1707.0300 2017. (Cited on page 3.)
[64] Sébastien Bubeck, Ronen Eldan, and Joseph Lehec. Sampling from a log-concave distribution with projected langevin monte carlo. Discrete & Computational Geomelry, 2018. (Cited on page 3.)
[65] Raaz Dwivedi, Yuansi Chen, Martin J Wainwright, and Bin Yu. Log-concave sampling: Metropolis-hastie algorithms are fast! arXiv preprint arXiv:1801.02309, 2018. (Cited on page 3.)
[66] Arnak Dalalyan and Lionel Riou- On sampling from log-concave density using kinetic langevin diffusions. arXiv preprint arXiv: 1et..10077.88. 2018. (Cited on page 3.)
[67] Xuechen Li, Yi Wu, Lester Mackey, and Murat A Erdogdu, Stochastic runge-kutta accelerates langevin monte carlo and beyond. In Advances in Neural Information Processing Systems, pages
2019. (Cited on page 3.)
[68] Ruoqi Shen and Yin Tat Lee. The randomized midpoint method for log- log-concave sampling. In Advances in Neural Information Processing Systems, pages 2098-2109, 2019. (Cited on page 3.)
[69] Murat A Erdogdu and Rasa Hosseinzadeh. On the convergence of langevin monte carlo: The interplay between tail growth and smoothness. arXiv preprint vrXiv:2005.13097 2020. (Cited on page 3.)
[70] Mufan Bill Li and Murat A Erdogdu. Riemannian langevin algorithm for solving semidefinite programs. arXiv preprint arXiv:2010.11176, 2020. (Cited on page 3.)
[71] Nhat Ho, Koulik Khamaru, Raaz Dwivedi, Martin Wainwright, Michael I Jordan, and Bin Yu. Instability, computational efficiency and statistical accuracy. arXiv preprint arXiv:2005.1141. 2020. (Cited on page 3.)
[72] Jonathan C Mattingly, Andrew M Stuart, and Desmond J Higham. Ergodicity for sdes and approximations: locally lipschitz vector fields and degenerate noise. Stochastic processes and their applications, 12):1): 132,,,2,-3 2002. (Cited on pages 3 and 19.)
[73] Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu. Global convergence of langevin dynamics based algorithms for nonconvex optimization. In Advances in Neural Information Processing Systems, pages 3122-3133, 2018. (Cited on pages and 4.)
[74] Wenlong Mou, Nhat Ho, Martin J Wainwright, Peter Bartlett, and Michael I Jordan. A diffusion process perspective on posterior contraction rates for parameters. arXiv preprint 1xXiv:190..0090 2019. (Cited on page 3.)
[75] Sean P Meyn and Richard L Tweedie. Markov chains and stochastic stability. Springer Science & Business Media, 2012. (Cited on pages 4, 18, 19, and 20.)
[76] Eric Moulines and Francis R Bach. Non-asympiotic analysis of stochastic approximation algorithms for machine learning. In Advances in Neural Information Processing Systems, pages 451 451-459,20 2011. (Cited on page 5.)
[77] Charles J Geyer. On the asymptotics of constrained m-estimation. The Annals of Statistics, 2994): 2010, 1994. (Cited on page 5.)
[78] Alexander Shapiro. On the asymptotics of constrained local m-estimators. Annals of statistics, pages 948-960, 2000. (Cited on page 5.)
[79] Zhiyan Ding, Yiding Chen, Qin Li, and Xiaojin Zhu. Eror lower bounds of constant step-size stochastic gradient descent. arXiv preprint arXiv: 2019. (Cited on page 6.)
[80] Bin Gao, Xin Liu, Xiaojun Chen, and Ya-xiang Yuan. On the (!L) ojasiewicz exponent of the quadratic sphere constrained optimization problem. arXiv preprint arXiv: 161111078/ 2016. (Cited on page 6.)
14

---

[81] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak polyak-tojasiewice condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795-811. Spriner, 2016. (Cited on page 6.)
[82] Soham De, Abhay Yadav, David Jacobs, and Tom Goldstein. Automated inference with adaptive batches. In Artificial Intelligence and Statistics, pages 1504-1513, 2017. (Cited page
[83] Peter Huber. Robust statistics, volume 523. John Wiley & Sons, 2004. (Cited on page 7.)
[84] Jianqing Fan and Qiwei Yao. The elements of financial econometrics. Cambridge University Press, 2017. (Cited on page 7.)
[85] Andrew Blake and Andrew Zisserman. Visual reconstruction. 1987. (Cited on page 8.)
[86] Wanrong Zhu, Xi Chen, and Wei Biao Wu. A fully online approach for covariance matrices estimation stochastic gradient descent solutions. arXiv preprint urXiv:2002.03999, 2020. (Cited page 9.)
[87] Whitney K Newey and Kenneth D West. A simple, positive semi-definite heteroskedasticity and autocorrelationoonsitten covariance matrix. Technical report, National Bureau of Economic Research, 1986. (Cited page 10.)
[88] Whitney K Newey and Kenneth D West. Automatic lag selection in covariance matrix estimation. The Review of Economic Studies, 61(4):631-653, 1994. (Cited on page 10.)
[89] Dimitris N Politis, Joseph P Romano, and Michael Wolf. Subsampling. Springer Science & Business Media, 1999. (Cited on pages
30.)
[90] Xi Chen, Jason Lee, Xin T Tong, Yichen Zhang, et al. Statistical inference for model parameters in stochastic gradient descent. The Annals of Statistics, 48(1):251-21) 2020. (Cited on page 10.)
15


Reviews:
[{"review_id": "vB04mLaFZ37", "reviewer": "Reviewer_iHb7", "summary": "This paper provides a theoretical analysis of the average version of SGD iterates, and shows that the averaged version of SGD iterates is asymptotically normally distributed around the expected value of their unique invariant distribution, under a generalized condition of dissipativity. ", "questions": "", "limitations": "", "rating": 4, "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": "This paper generalizes the DDB19 to a more generalized condition than the PL condition. Though the authors claim the non-convex regime, the main contribution falls in the use of PL condition and the analysis is analogous to DDB19. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "From my perspective, the main limitation is the novelty. The analysis is analogous to the DDB19, but just extends the analysis to some generalization of the PL condition. The experiments also did not justify the nonconvex settings, nor surprising. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "XVvKxYD6LkB", "reviewer": "Reviewer_LBYf", "summary": "In the paper, the authors establish an asymptotic normality result for the constant step size stochastic gradient descent (SGD) algorithm under the dissipative settings of non-convex and non-smooth objective functions. ", "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": "\nIn my opinion, the asymptotic results of the constant step size SGD presented in the paper under non-smooth and non-convex objective settings are of interest. Here are my comments on the paper:\n\n(1) The dissipativity assumptions in Assumptions 2.2 or 3.2 are satisfied by also symmetric two components Gaussian mixtures, non-linear regression models, and informative non-response model (See references [1] and [2] that I mentioned below for more details).\n\n(2) In Proposition 1, since $L$ and $L_{\\xi}$ are not known in practice, what is the practical way to choose $\\eta$ to satisfy the constraint in that proposition? Furthermore, do we have some explicit forms for the stationary distribution or simply just some approximation?\n\n(3) In Theorem 3.1, I also have the same comment on the learning rate as the previous comment. We usually do not know $\\alpha, \\beta$, and the growth of function $g$ in localized dissipativity assumption. Furthermore, it seems that the upper bound of the expectation of $\\|theta^{(\\eta)} - \\theta^{*}\\|$ is not tight when $g(x) = x^{p}$ for $p > 2$. Can the authors clarify more this result?\n\n(4) The results of Theorem 3.2 are not readable. I do not understand the meanings of constants $M$ and $m$ in that theorem. Furthermore, what is the implication of the results of Theorem 3.2 apart from the complicated constants?\n\n(5) I think that in the localized dissipativity setting where $g(x) = x^{p}$ with $p > 2$, the CLT of constant step size SGD is not a normal distribution. In fact, it seems to be a Gaussian process. Can the authors provide more insight into this setting?\n\n(6) There are a few relevant papers around the context of the paper that the authors may consider adding to the work:\n\n(6.1) For the literature for the computational complexity and statistical accuracy of estimators in general non-convex settings (need not be locally strongly convex), the current work of [1] established the trade-off between the instability of general optimization algorithms and their statistical accuracy and computational efficiency.\n\n(6.2) The dissipativity and local dissipativity also recently have been used to study the posterior convergence rates of parameters under Bayesian models [2].\n\n--- References:\n\n[1] N. Ho, R. Dwivedi,  K. Khamaru, M. J. Wainwright, M. I. Jordan, B. Yu. Instability, computational efficiency, and statistical accuracy. Arxiv preprint Arxiv 2005.11411, 2020.\n\n[2] W. Mou, N. Ho, M. J. Wainwright, P. Bartlett, M. I. Jordan. A diffusion process perspective on the posterior contraction rates for parameters. Arxiv preprint Arxiv 1909.00966, 2019.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any foreseeable limitations and negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not detect any ethical issues with the paper.", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "7rc-aznfSM", "reviewer": "Reviewer_8kWx", "summary": "The paper provides CLT and bias control for constant step-size stochastic gradient descent in the non-convex case. The general theory is applied to several specific examples.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper presents an interesting results on SGD algorithm with constant stepsizes. Under reasonable assumptions, the authors study the limiting behaviour of SGD output. It is well known, that constant stepsize SGD produces a biased stationary measure. The author quantifies this phenomenon. First, they show CLT for biased sequence and next provide bounds on the bias. The main result is applied to several examples. In my opinion, the paper provides an important and interesting contribution to the theory of SGD with constant stepsize.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "not applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10h"}, "extra_text": {}}, {"review_id": "4rMtjXzuGLw", "reviewer": "Reviewer_HoaV", "summary": "This paper studies the asymptotic normality and the bias for non-convex optimization problem with constant stepsize SGD algorithm. Relaxing previous strongly convex assumption, adopting techniques from Markov chains, they show that under some mild conditions, SGD with constant stepsize will quickly converge to a stationary distribution that is uniquely determined by the stepsize $\\eta$. Also, they analyze the bias under various conditions, basically showing that the bias is also (positively) dependent of the stepsize $\\eta$. Last, they provide thorough experiments in Regularized MLE and Regularized Blake-Zisserman MLE settings, showing that the numerical results match their theoretical prediction.", "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": "Overall, this is a good and well-written paper. It studies a very important problem: how to quantify the uncertainty of SGD in the realistic non-convex and non-smooth setting. Also, its proof techniques may have independent interest. Different from previous work, this paper uses $V$-uniform ergodicity to show the existence and uniqueness of the stationary distribution (Proposition 2.1). Some detailed suggestions and comments are listed below and I would be happy if you can answer this questions.\n\n1. In the application part, you list the Regularized MLE and Regularized Blake-Zisserman MLE. I am interesting that whether we can show that neural network also satisfies the conditions required to have the asymptotic normality. To me, with some regularizer or weight decay, at least shallow networks is hopeful to satisfy your conditions. \n\n2. As you already mentioned, there is an interplay between the convergence to the stationary distribution and the bias term. If $\\eta$ is large, then the convergence is quick. On the other hand, the bias will become large if $\\eta$ is large. Could you provide a quantitive analysis to provide some suggestions on how to choose a good stepsize.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the asymptotic normality and the bias for constant step size stochastic gradient descent (SGD) algorithm in the non-convex and non-smooth setting. It shows that if the non-convex and non-smooth objective function satisfies a dissipativity property, the average of SGD iterates is asymptotically normally distributed around the expected value of their unique invariant distribution. It also characterizes the bias between this expected value and the critical points of the objective function under different local regularity conditions. The paper is well-written and studies an important problem. The authors are encouraged to incorporate the feedback from the reviewers in the revision.
Decision: Accept (Poster)