Global Convergence and Stability of Stochastic Gradient Descent
Authors: Vivak Patel
Bowen Tian
Shushu Zhang
Venue: ICLR 2022 Submitted (2022)
Keywords: Stochastic Gradient Descent
Nonconvexity
Noise Model
Global Convergence
Stability

Abstract: In machine learning, stochastic gradient descent (SGD) is widely deployed to train models using highly non-convex objectives with equally complex noise models. Unfortunately, SGD theory often makes restrictive assumptions that fail to capture the non-convexity of real problems, and almost entirely ignore the complex noise models that exist in practice. In this work, we make substantial progress on this shortcoming. First, we establish that SGD’s iterates will either globally converge to a stationary point or diverge under nearly arbitrary nonconvexity and noise models. Under a slightly more restrictive assumption on the joint behavior of the non-convexity and noise model that generalizes current assumptions in the literature, we show that the objective function cannot diverge, even if the iterates diverge. As a consequence of our results, SGD can be applied to a greater range of stochastic optimization problems with confidence about its global convergence behavior and stability.

Under review as a conference paper at ICLR 2022
GLOBAL CONVERGENCE AND STABILITY STOCHASTIC GRADIENT DESCENT
OF
Anonymous authors Paper under double-blind review
ABSTRACT
In machine learning, stochastic gradient descent (SGD) is widely deployed to train models using highly non-convex objectives with equally complex noise models. Unfortunately, SGD theory often makes restrictive assumptions that fail to capture the non-convexity of real problems, and almost entirely ignore the complex noise models that exist in practice. shortcoming. First, establish that SGD's iterates will either globally converge to a stationary point or diverge under nearly arbitrary nonconvexity and noise models. Under slightly more restrictive assumption the joint behavior of the non-convexity and noise model that generalizes current assumptions in the literature, show that the objective function cannot diverge, even if the iterates diverge. As a consequence of our results, SGD can be applied to a greater range of stochastic optimization problems with confidence about its global convergence behavior and stability.
this work, we make substantial progress on this
INTRODUCTION
Stochastic Gradient Descent (SGD) is dominant algorithm for solving stochastic optimization problems that arise in machine learning, and has expanded its reach to more complex problems from estimating Gaussian Processes (Chen et al., 2020), covariance estimation in stochastic filters (Kim et al., 2021), and systems identification (Hardt et al., 2016; Zhang & Patel, 2020). Accordingly, understanding SGD's behavior has been crucial to its reliable application in machine learning and beyond. As a result, SGD's theory has greatly advanced from a variety of perspectives: global convergence analysis (Lei al., 2019; Gower et al., 2020; Khaled & Richtárik, 2020; Mertikopoulos et al., 2020; Patel, 2020), local convergence analysis (Mertikopoulos et al., 2020), greedy and global complexity analysis (Gower al., 2020; Khaled & Richtárik, 2020), asymptotic weak convergence (Wang et al., 2021), and saddle point analysis (Fang et al., 2019; Mertikopoulos et al., 2020; Jin al., 2021).
While all of these perspectives add new dimensions to understanding of SGD, the global conver- gence analysis of SGD is the foundation as it dictates whether local analyses, complexity analyses saddle point analyses even warranted. Unfortunately, current global convergence analyses of SGD make restrictive assumptions that fail to capture actual stochastic optimization problems arising in machine learning. In particular, global convergence analyses SGD assume:
1. global Hölder constant for the gradient of the objective function (c.g.. Reddi et al., 2016:; Ma & Klabjan, 2017; Zhou et al., 2018; Bassily et al., 2018; Lei et al., 2019; Li Orabona, 2019; Gower al., 2020; Khaled & Richtárík, 2020; Mertikopoulos al., 2020; Patel, 2020; Jin et al., 2021);
2. unrealistic noise models (e.g., uniformly bounded variance) for the stochastic gradients (e.g., Reddi et al., 2016b; Ma & Klabjan, 2017; Hu et al., 2019; Bi & Gunn, 2019; Zou et al., 2019; Mertikopoulos et al., 2020).
While such assumptions often make the analysis simpler, the resulting global convergence results would not even apply to simple neural network models for binary classification (see Appendix A).

---

Under review as a conference paper at ICLR 2022
To address this gap, we analyze the global convergence of SGD nonconvex stochastic optimiza- tion problems that capture many actual machine learning applications. In particular, we assume local Hölder continuity of the gradient function (see Assumption 2). which substantially relaxes the global Hölder assumption of all previous works. Second, we assume that the noise model of the stochastic gradients is bounded by an arbitrary upper semi-continuous function of the parameter (see Assumption 4), and can even have infinite variance (c.f., Wang et al., 2021), which generalizes the assumptions of all previous work. With these two general assumptions, we prove that the iterates of SGD will either converge to a stationary point or diverge to infinity with probability one (see The- orem 2). Owing to our result, SGD can be applied to actual empirical risk minimization problems with guarantees about its asymptotic behavior.
In the process of proving Theorem 2, we also prove another almost remarkable claim about the behavior of SGD's iterates: that of all the possible asymptotic behaviors of the iterates (e.g., con- vergence to a fixed point, convergence to manifold, limit cycles, oscillation between points, di- vergence), even with rather arbitrary noise models, the only two possibilities are either the iterates converge to a fixed point or they diverge (see Theorem 1). Note, we cannot expect this outcome apriori even in such a simple context as applying SGD with fixed step sizes to solve a consistent linear system: the iterates may terminate in a cycle and, thus, fail to converge to a fixed point (Motzkin & Schoenberg, 1954, Theorem 2). Thus, from a practical perspective, applying SGD to nonconvex problems with exotic noise models, which may initially cause concern, will either result in convergence to a stationary point or divergence of the iterates.
While Theorem patently useful, SGD's iterates diverging may cause some concern, especially when optimizing regularized empirical risk functions that are guaranteed to be coercive (i.c.. the objective diverges to infinity as the argument tends to infinity). To address this issue, we generalize the notion of expected smoothness (see Khaled & Richtárik, 2020) to an assumption about the joint behavior of the gradient function, the noise model, and the local Hölder constant (see Assumption 5) to prove that, regardless SGD's iterates' behavior, the objective function will remain finite and the gradient function will converge to zero with probability one (see Theorem 3). Thus, from a practical perspective, if we can apply Theorem 3 coercive objective function, are guaranteed that the iterates cannot diverge, and, consequently, must converge to a stationary point.
Furthering the practical value of our results, as alluded to previously, our results enable the use of downstream analyses. Specifically, our results allow for SGD's iterates to converge to stationary point or diverge; as result, when SGD's iterates converge to a stationary point, saddle point escape analyses (c.g., Fang al., 2019; Mertikopoulos et al., 2020; Jin et al., 202 1) can be applied to ensure that the stationary point is a local minimizer. Moreover, when SGD is converging to a stationary point, local convergence rate analyses can also be supplied, which can inform adaptive step size rules and stopping criteria (Patel, 2020).
Finally, from a theoretical perspective, we innovate two new analysis strategies deal with the generality of the local Hölder continuity assumption on the gradient, and our general noise model assumption. We term these two strategies the pseudo-global strategy and the local strategy. We develop the pseudo-global strategy to prove global convergence (i.e., Theorem 2), while we develop the local strategy to prove stability (i.c., Theorem 3). We believe that both of our strategies are of independent interest theoreticians.
Contribution Summary. To summarize, we study the behavior of SGD under much more realistic assumptions than what is currently in the literature; namely, we consider local Hölder continuity and general noise models. In this context, to a fixed point or that they might diverge (Theorem I); and (2), when the iterates converge to a fixed point, it must be a stationary point of the objective function (Theorem 2).
able to show (I) that the iterates must either converge
Moreover, under a slightly more restrictive assumption-whiel still generalizes current assumptions in the literature-, we show that, regardless of iterate behavior, the objective function will converge to a finite random variable (i.e., SGD is stable) and the gradient function will converge to zero (Theorem 3).
2

---

Under review as a conference paper at ICLR 2022
Finally, we develop analysis strategies, the pseudo-global strategy and the local strategy, that are of independent interest to theoreticians in machine learning and stochastic optimization.
Organization. The remainder of the paper is organized as follows. In Section 2, we specify the stochastic optimization problem that we will study, including formal statement of all assumptions. In Section 3, we specify Stochastic Gradient Descent (SGD) and the properties the needed prop- erties of the learning rate. In Section 4, we prove and discuss main results and highlight key steps, while leaving the rest to the appendix. In Section 5, we conclude this work.
2 STOCHASTIC OPTIMIZATION
We consider solving the optimization problem
min (F(0) = [[(0 X)]}. DER"
where F' maps I2 into R; maps Rº and the co-domain of the random variable X into I;; and E is the expectation operator. As we require gradients, we take F and f to differentiable in 6, and denote its derivatives with respect to 6 by F(0) and X.) With this notation, we make the following general assumptions about the deterministic portion of the objective function.
Assumption 1. There exists Fi.. IR such that v0 RP, FLs. F(O).
Assumption 2. There exists a E (0, 1] such that (0) is locally a- Hölder continuous.
Assumptions 1 and 2 would even considered mild in the context of non-convex deterministic optimization, in which it is also common assume that the objective function well-behaved level sets (e.g., Nocedal & Wright, 2006, Theorems 3.2, 3.8, 4.5, 4.6). Importantly, Assumption 2 relaxes the common restrictive assumption of globally Hölder continuous gradient functions that is common in other analyses.
Our final step is to make some assumptions about the stochastic portion of the objective function. The first assumption requires the stochastic gradients be unbiased, which readily be relaxed (Bottou et al., 2018). The second assumption allows for a generic noise model for an a-Hölder continuous gradient function, and even allows for the second moment not exist when (c.f. Wang et al., 2021).
Assumption 3. For all 0 E RP,
= E X)).
Assumption 4. Let a E [0.1] be as in Assumption 2. There exists an upper semi-continuous function G(O) such that (0 x)1l++a| s G(0).
We will show that Assumptions 1 to 4 are sufficient for a global convergence result.
Remark 1. It is entirely possible that ElI x)|l+ to is (at least) upper semi-continuous,, and to set G(Ø) equal to this function. In the case that [ x) is not upper semi- semi-continuous, it is possible specify G(0) the upper envelope of (0, x) 1 (i.e., the its limit supremum function). However, it is unlikely that [[]] - nor its upper envelope are easy specify
explicitly, and it is more likely to be able to find an upper bound.
In order to show that the objective function cannot diverge (i.e., to prove stability), we will need an additional assumption. This assumption will relate the gradient function, noise model and variation on the local Hölder constant. To begin, we define the variation on the local Hölder constant. Let (0, 1] as Assumption 2 and
arbitrary, and define
((())-F(e)) 1-
|| 0112 s (G(O) v
C. (0) = sup,
this quantity is nonzero (2)
otherwise,
3

---

Under review as a conference paper at ICLR 2022
where V indicates the maximum between quantities. Note, the choice of is irrelevant, and they can be distinct for the two cases in the definition of Le, but we fix them to be the same for simplicity. Importantly the quantity, L., is defined at every parameter under Assumption 2.
With this quantity, we can state a nonintuittve, Assumption 5. There exists Ci, C2 C3 2 0 such that, 40 E RR,
assumption that is needed to prove stability.
(((0)((0) - a | 1+a 1/a
CC+CC(F(O) (Ft.) + Ca F(O)
(3)
(0)
Assumption 5 generalizes Assumption 4.3(c) Bottou et al. (2018), which is satisfied for a large swath of statistical models. Moreover, Assumption 5 generalizes the notion of expected smoothness (see Khaled & Richtárik, 2020, for history of the assumption), which expanded the optimization problems covered by the theory of Bottou et al. (2018). Note, Assumption 5 is about the asymptotic properties of the stochastic optimization problem as the left hand side of the inequality in Assump- tion 5 can be bounded inside of any compact set. Thus, Assumption covers a variety of asymptotic behaviors, such as 2xp(((112) (xp(11012), || for R, log(I|0] || + +), and log (log( [|0[[2+++++1) Therefore, Assumption 5 holds for functions with a variety different asymptotic behaviors.
We will show that Assumptions to 5 are sufficient for stability result.
Now that we have specified the nature of the stochastic optimization problem, we turn our attention the algorithm used to solve the problem, namely, stochastic gradient descent (SGD).
STOCHASTIC GRADIENT DESCENT
SGD starts with an arbitrary initial value, 0, E RP, and generates sequence of iterates {0x k N} according to the rule
0k+1 = 6 ( where {M& : + e N} RexP; and (X& k N} are independent and identically distributed copies of X. Importantly, }M&} cannot be arbitrary, and the following properties specify a gen- eralization of the Robbins & Monro (1951) conditions for matrix-valued learning rates (c.f. Patel, 2020).
The first condition requires a positive learning rate, and imposes symmetry to ensure the existence of real eigenvalues.
Property 1. (M& k + 1 E NJ are symmetric, positive definite matrices.
The next two properties are natural generalization of the Robbins-Monro conditions. Let E (0, be as in Assumption
Property 2. Let )max( denote the largest eigenvalue of symmetric, positive definite matrix. Then, Ex Amax Amax(Ma)) 14 =: S < cc.
Property 3. Let Amin() (-) denote the smallest eigenvalue of a symmetric, positive definite matrix. Then, Ex Amin
DC.
We will show that Properties to are sufficient for a global convergence result.
The final property ensures the stability of the condition number of {M&). Note, this property is readily satisfied for scalar learning rates satisfying the Robbins-Monro conditions.

---

Under review as a conference paper at ICLR 2022
Property 4. Let vc-) denote the ratio the largest and smallest eigenvalues of symmetric, positive definite matrix. Then, limg-+ce Amax(Mp [MM)))<[MM = 0.
We will show that Properties are sufficient for stability.
4 GLOBAL CONVERGENCE & STABILITY
With the stochastic optimization problem and with stochastic gradient descent (SGD) specified, now turn our attention to what happens when SGD is applied to stochastic optimization problem. The key step in the analysis of SGD any objective function is to establish bound between the optimality gap at 0x+1 with that of 8x. This step achieved by using the local Hölder continuity of the gradient function and the fundamental theorem of calculus. Using Assumption 2, first specify the local Hölder constant.
Definition 1. For any 0, p E IR, define
((V) F(0)
L(0,4) = sup
2 11vb - 0ll2 S 114 01l2 || - 0
(5)
Moreover, for any R2 0, let LR = L(0, for 11 = R. Remark Note, when the gradient locally Hölder continuous, La well defined for any 2 0.
With this definition, we can now relate the optimality gap of oxt1 with that of 0g by using the following result.
Lemma 1, Suppose Assumptions and 2 hold. Then, for any 0 E IR,,
F F(0) Fis. + F(0))( 0)+ L(0,4p)
1+a |11- -011 0112
(6)
Proof. By Taylor's theorem,
F(Ø) - Fi.o. F(0) Fi.. + / i(( t(p 0)) O)dt.
Now, add and subtract F(0) F(O t(p 0)) in the integral, then apply Assumption 2. We conclude,
Fi.. F(0) 0) ((0 11 011 1a / dt.
F(ç) - FI.b. < F(0)
(8)
By computing the integral, the result follows.
Now, simply set Pp 0x+1 and 0₂ in Lemma and try to take expectations man- age the randomness of the stochastic gradient, we will run into the problem that T.(O,. 0++1) and ||0A-1 fxll2 are dependent, and we cannot compute expectation. In previous work, this techni- cal challenge is waived away by using global Hölder constant to upper bound L(O,, 0x+1), which unrealistic even for simple problems (see Appendix A).
To address this technical challenge, innovate two new strategies for handling the dependence between L(O,, 0k+1) and [|0++1 - 0g ll- In both strategies, we follow the same general approach:
1. We begin by restricting our analysis to specific events, which will allow us to decouple L(8, L(0g, 0k41) and ||0 22
2. With these two quantities decoupled, we will develop recurrence relationship between the optimality gap 0x+1 and that of 0g.
5

---

Under review as a conference paper at ICLR 2022
3. We apply this recurrence relationship with refinements of standard arguments new to derive the desired property about the objective function. 4. Finally, we state the generality of the specific events which we have studied SGD's iterates.
Thus, follows, we will define two distinct series of events for the two strategies. The first strategy, which we refer to as the pseudo-global strategy, will provide the global convergence analysis. The second strategy, which we refer to as the local strategy, will provide the stability result.
4.1 PSEUDO-GLOBAL STRATEGY AND GLOBAL CONVERGENCE ANALYSIS
For the first strategy, which supplies the global convergence result, we study SGD on the events
B = n
{103112 s R), ++ 1NN
j=0
for every R 2 O. We now try to control the optimality gap at iteration A: + 1 with that of iteration k, which will result in two cases.
1. (Case 1) B (R) holds can bound L(0,, 0x+1) by Lns and G(f) is also bounded in the ball of radius about the origin (which follows from being upper semi-continuous in Assumption 4). As result, we could then proceed with the analysis in manner that is similar to having a global Hölder constant.
2. (Case 2) |0++1| ll > R and B2 (R) holds. In this case, controlling 0x+1) is very challenging and, to our knowledge, was not solved before our work.
Our approach for controlling the optimality gap in both cases supplied in the next lemma, whose proof is in Appendix C.
Lemma 2. Let {Mx} satisfy Property 1. Suppose Assumptions 1 to 4 hold. Let 10x} satisfy (4).
Then, VR 2 0,
[[F(0k+1] Fi... [B++ (R)) Fil [ < [F(0A) Fis. [R]]
Amiia (Mx) (0x)) [B& (R)]+ L OFn
(10)
Amaax (Max) 1+a GR.
1
where GR suppEBBR G(0) 00 with G(0); and OFR suPaEB(R) [((0)]2(1 + +a)
With this recursion and standard martingale results (Robbins & Siegmund, 1971; Neveu Speed, 1975, Exercise II.4), the limit of [F'(0x) ( Fi...] -f..)..F.....
[Bx (R)) exists with probability one and finite for
every R 2 0. As a result, the limit of F(Ox) Fis. exists and is finite on the event {sup, |00x|2 < 0o) (see Corollary 1).
We can also use Lemma 2 to make statement about the gradient. Specifically, limit infimum of [|]]] F (0x) 11 B (R)]] must be zero, which is now standard argument that mimics Zoutendijk's 's theorem (Nocedal & Wright, 2006, Theorem 3.2). By Markov's 's incquality, this result implies that ( (Ox 2 [B& R)] gets arbitrarily close to 0 infinitely often (see Lemma 8). To show however, is not standard. Several strategies have been developed, namely those of Li & Orabona (2019); Lei et al. (2019); Mertikopoulos et al. (2020); Patel (2020). Unfortunately. the approaches of Li & Orabona (2019); Lei et al. (2019) rely intimately global Hölder constant, while that of Mertikopoulos et al. (2020) requires even more restrictive assumptions. Fortunately, the approach of Patel (2020) can be improved and generalized to the current context (see Lemma 9). Thus, we show that limg- (1(x))) 0 {sup, ||0x|1 oo) (see Corollary 2).
show that the
convergence
the existence of
Our final step is to clarify the role of (sup, 0 l1z < 0c) in the asymptotic behavior of SGD's iterates. At first glance, this event seems imply that the iterates converge point. However, owing to the general nature of the noise, it is also possible, say, that the iterates approach limit cycle oscillate between points with the same norm. Even beyond this event, the generality of the

---

Under review as a conference paper at ICLR 2022
noise model may allow for substantial excursions between Fi.. and infinity (c.f., simple random walk, which has limit supremum of infinity and a limit infinimum of negative infinity). Thankfully, can prove that either the iterates converge point they must diverge- result that refer to as the Capture Theorem (see Appendix C).
Theorem (Capture Theorem). Let {0x} be defined as in (4), and (M&} satisfy Properties and 2. If Assumption 4 holds, then either (limg-so Og exists) or {lim infx-sso 10 l2 = oc must occur.
By putting together the above arguments and results, we can conclude that either SGD's iterates diverge SGD's iterates converge to stationary point. This is formally stated in the following theorem. See Section for a discussion the practical value of this result.
Theorem (Global Convergence). Let 0g be arbitrary, and let {0x N} be defined according to (4) with {M& k + 1} satisfying Properties to 3. Suppose Assumptions 1 to 4 hold. Let A = (lim -- |10x|12 = 20) and A2 (lim O2 exists}. Then, the following statements hold.
1. ||[A||+ ([A2)=
2. On A2, there exists a finite random variable, Fiim- such that limg-400 F(Ox) Fim and lim F(Ox)= = 0 with probability one.
Proof. By Theorem we have that P[A[] + P[[2]] 1. Then, Ag. Corollaries 1 and 2 imply that F(0)) + Fiim- which is finite, and F(0x) O.
4.2 LOCAL STRATEGY AND STABILITY ANALYSIS
While Theorem 2 provides a complete global convergence result, allows for the possibility of diverging iterates. The possibility of divergent iterates raises the spectre of whether the objective function can also diverge along this sequence. That is, there is a possibility that SGD may be unstable, which would be highly unexpected and undesirable, especially when the objective function is coercive (e.g., has an é! penalty on the parameters).
To formalize this concept, we define a relevant notion of stability. Definition 2. Stochastic Gradient Descent stable if
IP sum F(Ox) 30
(1I)
k=+00
where { satisfy (4).
We now state the events that we will use to decouple the relationship between L(k,, 06+1) and |10x-1 02 Unlike our pseudo-global strategy, we will make use of two sequences of events that are closely related. To define these sequences, we will first need to define stopping times. For every j + N, define
F(0+41)- - Fib. F(Ox) - FLs. + F(0.)(00+1 - -0)
= min
k:
(0k)
(12)
+ 1 110++1 - 0x112 1t and >
Analogously, for every j + 1 E N, define
Vj min (k: I(Ok, 0k+1) (oce),, and k > 1}
(13)
Now, we will use (12) to establish the stability of the objective function, and we will use (13) to show that the gradient function must tend to zero. Just as we did with B& (R), we will derive a recursion on the optimality gap the events (1T, > k} l + E N). Of course, just as before, the main challenge in deriving a recursive formula is to address {T, = k}. Our solution supplied in the following lemma, whose proof is in Appendix D.

---

Under review as a conference paper at ICLR 2022
Lemma 3. Let }M& satisfy Property 1. Suppose Assumptions 1 to 4 hold. Let {0kt satisfy (4).
Then, for any j + 1 E N and k > J.
B [[(((0k41) Fib.) [Tj k]] Fr) - (((0z) FLS. - -((0s) (x 1 1Tg > k-
1ta1 1/07
Amax (Mz)
[((x))
(14)
(.(O))G(Ox)) +a
2
1 1
1 1+0
(On)
From Lemma 3, there is a clear motivation for Assumption 5. Indeed, if we apply Assumption 5, Lemma 3 produces the following simple recursive relationship.
Lemma 4. If Assumpptions 1 to 5, and Properties and 4 hold, and {0k} } satisfy (4), then there exists a E N such that for any j + E N and any 2 Kij + 1}.
E [[F(Ot+1) (T, FR]
C2
1 + Amax (Ma)
(F(0k) - FL.. [Tg k 1]
1+a
(15)
2 Amina (Mx) F((K) 1 [T, > k -2-1 1] Amax Aaax((M) (Mx)
|
C1
2
+
Just as in the pseudo-global strategy, Lemma 4 can be combined with standard martingale results (Robbins Siegmund, 1971; Neveu & Speed, 1975, Exercise II.4) to conclude that the limit of F(0s) exists and is finite on the event UT= oc} (see Corollary 3). Also as in the pseudo- global strategy, by improving on the arguments Patel (2020), we show that lim, F(Ox) = on the event o oo) (see Corollary 4).
Finally, we show that of oc} and uf-o(r, )0) are probability one events (see Theo- rem 5). In other words, we show that eventually (fx()) will always dominate L(Op, fx+1). This statement should not come as a surprise on the event {lim, 0g exists), but is slightly surprising that must also hold on (limn |00ll2 = oo}. By combining these results, we can conclude as follows.
Theorem 3 (Stability). Let 0g be arbitrary, and let (fk: k N) be defined according to (4) with {M& : k + 1} satisfying Properties to 3. Suppose Assumptions to 5 hold. Then,
1. There exists a finite random variable, Fim- such that lom F(Ox) Fim with proba- bility one;
2. lime (0x)) = O with probability one.
Proof. Using Corollary 3, we conclude that 3Fim that is finite such that lim; F(Ox) Fiim on
o ). Using Corollary 4, we conclude that lim, ((x)) 0 on Ug (vj o0.. Finally, apply Theorem 5 to conclude that Plus=ot coj] Pi cof| = 1.
See Section for a brief discussion of the practical consequences of Theorem 3.
CONCLUSION
In this work, we further filled the gap between SGD's use in practice and SGD's theory; that is, SGD is often applied in situations where the non-convexity of the objective and noise model are not covered by existing theory. Thus, we focused on analyzing SGD in a context that was more realistic to machine learning problems in two ways. First, we eliminated the unrealistic assumption that the gradient of the objective function is globally Hölder continuous, and replaced it with a local Hölder continuity assumption. Second, we allowed for arbitrary noise models. This latter innovation suggests the possibility of potentially undesirable outcomes: the iterates can enter a limit cycle or they can oscillate. Perhaps most interestingly, in the process of establishing our global convergence
8

---

Under review as a conference paper at ICLR 2022
result, we showed that these undesirable outcomes impossible (Theorem 1): either the iterates converge to a stationary point or they diverge (Theorem 2).
The possibility of the iterates diverging also raises the question of what happens to the objective function when the iterates diverge. Thus, under an additional assumption on the joint behavior of the local Hölder constant, noise model and gradient function, we showed that the objective function remains finite along any iterate sequence (i.e., SGD is stable), and the gradient function converges to zero along this iterate sequence (Theorem 3). Surprisingly, in the process of proving this result, we showed that, eventually, the constant L(0k, 0k+1) is eventually well controlled by (0s), even if the iterate sequence is diverging.
These results have several practical consequences, which we enumerate presently. First, by estab- lishing the global convergence and stability of SGD over nonconvex functions with general noise models, we enable all other types of analyses: local convergence rate analyses, local weak converge analyses, saddle point escape time analyses, and complexity analyses. Second, our global conver- gence and stability results can be applied to realistic machine learning optimization problems, and provide guarantees about whether SGD will find a stationary point. Finally, as SGD continues to be applied to more complex problems outside of machine learning, our results are able to supply confidence in the performance of the algorithm such problems.
From a theoretical perspective, we innovated two new analysis strategies and substantially refined a number of argument approaches currently the literature. We anticipate that these new argu- ment strategies will be of substantial interest to those working in machine learning and stochastic optimization.
One of the important issues not considered in this work is the nature of (0). In particular, there are functions that may admit upper bounds on (0) that ensure Assumption 5 is satisfied, yet using actual value of (0) would suggest that Assumption 5 is not satisfied. Exploring this issue will be the subject of future work. Another area of future effort will be to construct realistic example in which Assumption is not satisfied, and show that either (1) the iterates diverge, which implies that Assumption 5 is sufficient and may be necessary; or (2) the iterates converge, which implies that Assumption 5 is sufficient but not necessary.
REFERENCES
Raef Bassily, Mikhail Belkin, and Siyuan Ma. On exponential convergence of sgd in non-convex over-parametrized learning. arXiv preprint arXiv: 18/ 1.02564, 2018.
Jia Bi and Steve R Gunn. A stochastic gradient method with biased estimation for faster nonconvex optimization. In Pacific Rim International Conference Artificial Intelligence, pp. 337-349.
Springer, 2019.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-31 2018
Hao Chen, Lili Zheng, Raed Al Kontar, and Garvesh Raskutti. Stochastic gradient descent in corre- lated settings: A study on gaussian processes. In NeurIPS, 2020.
Cong Fang, Zhouchen Lin, and Tong Zhang. Sharp analysis for nonconvex sgd escaping from saddle points. In Conference on Learning Theory, pp. 1192-1234. PMLR, 2019.
Robert M Gower, Othmane Sebbouh, and Nicolas Loizou. Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation. arXiv preprint arXiv:2006.1031 2020.
Moritz Hardt, Tengyu Ma. and Benjamin Recht. Gradient descent learns linear dynamical systems. arXiv preprint arXiv: 1609.05191, 2016.
Wenqing Hu, Chris Junchi Li, Lei Li, and Jian-Guo Liu. On the diffusion approximation of noncon- vex stochastic gradient descent. Annals of Mathematical Sciences and Applications, 4(1), 2019.

---

Under review as a conference paper at ICLR 2022
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. Journal of the ACM (JACM), 68(2):1-29, 2021.
Ahmed Khaled and Peter Richtárik. Better theory for sgd in the nonconvex world. arXiv preprint arXiv:2002.03:29, 2020.
Hee-Seung Kim, Lingyi Zhang. Adam Bienkowski, and Krishna R Pattipati. Multi-pass sequen- tial mini-batch stochastic gradient descent algorithms for noise covariance estimation in adaptive kalman filtering. IEEE Access, 9,99220-992$33 2021.
Yunwen Lei, Ting Hu, Guiying Li, and Ke Tang. Stochastic gradient descent for nonconvex learn- ing without bounded gradient assumptions. IEEE transactions on neural networks and learning systems, 31100)4334444000 2019.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 983- 992. PMLR, 2019.
Yintai Ma and Diego Klabjan. Convergence analysis of batch normalization for deep neural nets. arXiv preprini arXiv: /705.08011, 2017.
Panayotis Mertikopoulos, Nadav Hallak, Ali Kavis, and Volkan Cevher. On the almost sure conver- gence of stochastic gradient descent in non-convex problems. arXiv preprint arXiv:2006. 11144, 2020.
Theodore Samuel Motzkin and Isaac Jacob Schoenberg. The relaxation method for linear inequali- ties. Canadian Journal of Mathematics, 6:393 1954.
Jacques Neveu and TP Speed. Discrete-purumeter dam, 1975.
volume 10. North-Holland Amster-
Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.
Vivak Patel. Stopping criteria for, and strong convergence of, stochastic gradient descent on bottou- curtis-nocedal functions. arXiv preprint arXiv:20044000455 2020.
Sashank Reddi, Suvrit Sra, Barnabas Poczos, and Alexander Smola. Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. Advances in neural information processing systems, 29: 145-1153, 2016a.
Sashank Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference on machine learning, pp. 314- 323. PMLR, 2016b.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400-407, 1951.
Herbert Robbins and David Siegmund. A convergence theorem for non negative almost super- martingales and some applications. In Optimizing methods in statistics, pp. 233-257. Elsevier, 1971.
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 1XXi:22022.10346 2021.
Shushu Zhang and Vivak Patel. Stochastic approximation for high-frequency observations in data assimilation. arXiv preprint arXiv:2011.0266 2020.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. arXiv preprini arXiv: 10X.v8:/06.078/.,,, 2018.
Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. sufficient condition for conver- gences of adam and mmsrrp.. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11127-11135, 2019.
10


Reviews:
[{"review_id": "lbimSBKQt5p", "reviewer": "Reviewer_tECd", "summary": "", "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": "The paper is clearly written and the results seem to be interesting. Here are some comments/suggestions:\n\n- Assumption 5 is a bit complicated and difficult to understand. It is not quite clear how this assumption comes. I would suggest the authors to give some discussions on its motivation and its connection to the existing assumptions in the literature.\n\n- The results in the paper are of asymptotical nature, i.e., related to the limiting behavior of SGD if the iteration number goes to infinity. In practice, we are perhaps more interested in the nonasymptotical behavior, i.e., how the convergence rate is w.r.t. the iteration number. Is it possible to provide some nonasymptotical results under the local Holder continuity  assumption and the general noise model assumption? If not, are there any essential difficulties.\n\n- The authors consider general stepsize in the form of matrices. While this stepsize is very general, in practice the most used stepsize the scalar stepsizes. If we consider scalar stepsizes, can the global convergence and stability results be further improved?\n\n- Note that $L_R$ is defined as $L(0,\\psi)$ for $\\|\\psi\\|_2=R$. However, there are many $\\psi$ with $\\|\\psi\\|_2=R$. Can these different $\\psi$ lead to the same $L(0,\\psi)$. If not, then $L_R$ would not be well defined.\n\nTypos:\n\npage 2: the the\n\npage 4: holds for functions a variety\n\npage 6: our for\n\neq (9): Does $\\\\{\\|\\theta_j\\|_2\\leq R\\\\}$ mean $\\\\{X:\\|\\theta_j\\|_2\\leq R\\\\}$?\n\npage 6: be get arbitrarily close", "summary_of_the_paper": "In this paper, the authors study the behavior of SGD under very general assumptions. The existing global convergence of SGD requires two restrictive assumptions: a global Holder continuity for gradients and unrealistic noise models for stochastic gradients. This paper relaxes the global Holder continuity assumption to a local Holder continuity assumption, and consider general noise model assumptions. The main results include global convergence and stability. By global convergence, the authors show that either the iterates converge to a stationary point or they diverge. By stability, the authors show that the objective function remains finite along any iterate sequence. In the deduction, the authors introduce novel techniques to decouple some dependencies encountered in considering general assumptions. ", "summary_of_the_review": "The convergence and stability analysis of SGD in the general assumption seems interesting. The authors also introduce some techniques in the analysis.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PCLqsCPpXIr", "reviewer": "Reviewer_bDLV", "summary": "", "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 strength of the paper is that it studies the global convergence and stability of SGD under a fairly general non-convex setting. It is nice that unrealistic uniform boundedness noise assumption often used in the literature can be removed. One weakness is that some of the assumptions is less intuitive, and needs more explanations, discussions and justifications, especially Assumption 5. Also, the authors should perhaps provide some discussions in the contributions section what are the main technical difficulties and challenges that they overcome in order to achieve these results, and whether there is any technical novelty here. ", "summary_of_the_paper": "In this paper, the authors consider the global convergence and stability of stochastic gradient descent in a fairly general non-convex setting. They are able to remove the often-assumed unrealistic uniform bounded assumption on the noise, and also relax the global Holder assumption in the literature. Their discussions in Appendix A provide an example for which the uniform bounded assumption on the noise commonly assumed in the literature fails. Their global convergence says that under some relatively weak assumptions, SGD either diverges or the objective converges to a finite random variable and the gradient converges to zero. This excludes the bad outcomes, e.g. limit cycle or oscillation. Their stability result says that under a stronger assumption, SGD's objective converges to a finite random variable and the gradient converges to zero with probability one. ", "summary_of_the_review": "(1) I'm a little bit confused with Assumption 4. Would it be enough to simply assume that $\\mathbb{E}\\Vert\\dot{f}(\\theta,X)\\Vert_{2}^{1+\\alpha}$ is finite for any $\\theta$? Because it seems that if so, one can always find a function $G(\\theta)$ to upper bound this? Or your assumption is stronger than it seems? I understand that $G(\\theta)$ appears in (2) and Assumption 5. But it is not clear to me why you need this in Assumption 4, and am also wondering in mathematics, is there some name for the smallest upper semi-continuous function that upper bounds? Another comment I have is that in Assumption 4, you already taken the expectation. So my guess is that most likely, $\\mathbb{E}\\Vert\\dot{f}(\\theta,X)\\Vert_{2}^{1+\\alpha}$ is not just upper-semi-continuous but actually continuous. Do you know any commonly used example where this is not true? If so, why don't you assume this is upper-semi-continuous and use this function instead of $G(\\theta)$ in later discussions?\n\n(2) Some discussions on the intuitions behind Assumption 5, and connecting it to some assumptions that the readers are more familiar with would be very helpful. For example, the authors mentioned that Assumption 5 is satisfied for $\\theta\\in\\mathbb{R}$ for $\\exp(\\theta^{2})$, $\\exp(\\theta)$, $\\theta^{r}$ etc. But those examples are all for one-dimensional $\\theta$. How about in high-dimensions?\n\n(3) I don't understand why the assumptions in Section 3 are called Property 1-Property 4 instead of say Assumption 1'-Assumption 4' or Assumption 6-Assumption 9. They seem to be assumptions instead of properties.\n\n(4) In Theorem 3 (and maybe in Theorem 2 as well), can you say something about the properties of $F_{\\lim}$? For example, is it $L_{p}$ for some $p$?\n\n(5) In Theorem 3, when you have stability, can your proof techniques also provide some non-asymptotic convergence guarantees instead of just some asymptotic results? That can strengthen the paper by a lot.\n\n(6) In the proof of Theorem 2, it's better to write \"imply\" instead of \"supply\" and in the first line of Section 4.2., maybe you can write \"provides\" instead of \"supplies\". \n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "AS9Bu9PXdw", "reviewer": "Reviewer_TjZW", "summary": "", "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": "Strength:\n1. Analyzing the global convergence of SGD is a very important research problem in the area of machine learning and optimization. \n2. The paper is well written and very good to follow.\n3. The analysis strategies may be beneficial for the community. \n\nWeakness:\nCompared with previous results, the main difference is the weaker assumptions, i.e. \n    (1) global Holder continuity (literature) -> local Holder continuity (this work)\n    (2) bounded variance of stochastic gradient (literature) -> the stochastic gradient is upper bounded by some upper semi-continuous function (this work). \nThe author claims that their setting is more realistic. However, they don't provide any example for supporting this claim (especially for the second one). \n\n", "summary_of_the_paper": "In this paper, the author studies the global convergence of SGD. Compared with previous results, the authors show that under weaker conditions, the iterates of SGD will either converge to a stationary point of the objective function or diverge. ", "summary_of_the_review": "I found the manuscript to be clearly written and technically sound. Although it has some weakness, I think it still worth a publication. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the global convergence and stability of SGD for non-convex setting. The main contribution of the work seems to be to remove uniform bounded assumption on the noise, and to relax the global Holder assumption typically made. Their discussions in Appendix A provide an example for which the uniform bounded assumption on the noise commonly assumed in the literature fails.  The authors establish that SGD’s iterates will either globally converge to a stationary point or diverge  and hence tehir result exclude limit cycle or oscillation. Under a more restrictive assumption on the joint behavior of the non-convexity and noise model they also show that the objective function cannot diverge, even if the iterates diverge.

The reviewers are on the fence with this paper. While they agree that the paper is interesting, they only give it a score of weak accept (subsequent to rebuttal as well). One of the qualms is that while the authors claim the result helps show success of SGD in more natural non-convex problems, they don’t provide realistic examples supporting their claim. Further, while the extension to holder smoothness assumption while is indeed interesting, unless practical significance is shown via examples, the result is not that exciting.

From my point of view and reading, while the reviews are not extensive, i do not disagree with reviewers sentiment. Technically the paper is strong but there is a unanimous lack of strong excitement for the paper amongst reviewers. While there is this lack of more enthusiasm, given the number of strong submissions this year, I am tending towards a reject.
Decision: Reject