Year: 2021

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.

text: 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.

heading: 1 INTRODUCTION
text: Stochastic Gradient Descent (SGD) is a 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 et al., 2019; Gower et al., 2020; Khaled & Richtárik, 2020; Mertikopoulos et al., 2020; Patel, 2020), local convergence analysis (Mertikopoulos et al., 2020), greedy and global complexity analysis (Gower et al., 2020; Khaled & Richtárik, 2020), asymptotic weak convergence (Wang et al., 2021), and saddle point analysis (Fang et al., 2019; Mertikopoulos et al., 2020; Jin et al., 2021).
While all of these perspectives add new dimensions to our understanding of SGD, the global convergence analysis of SGD is the foundation as it dictates whether local analyses, complexity analyses or saddle point analyses are 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 of SGD assume:
1. a global Hölder constant for the gradient of the objective function (e.g., Reddi et al., 2016a; Ma & Klabjan, 2017; Zhou et al., 2018; Bassily et al., 2018; Lei et al., 2019; Li & Orabona, 2019; Gower et al., 2020; Khaled & Richtárik, 2020; Mertikopoulos et 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).
To address this gap, we analyze the global convergence of SGD on nonconvex stochastic optimization problems that capture many actual machine learning applications. In particular, we assume local Hölder continuity of the gradient function (see Assumption 2), which substantially relaxes the global Hö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 Theorem 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., convergence to a fixed point, convergence to a manifold, limit cycles, oscillation between points, divergence), 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 2 is patently useful, SGD’s iterates diverging may cause some concern, especially when optimizing regularized empirical risk functions that are guaranteed to be coercive (i.e., the objective diverges to infinity as the argument tends to infinity). To address this issue, we generalize the notion of expected smoothness (see Khaled & Richtárik, 2020) to an assumption about the joint behavior of the gradient function, the noise model, and the local Hö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 to a coercive objective function, we 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 a result, when SGD’s iterates converge to a stationary point, saddle point escape analyses (e.g., Fang et al., 2019; Mertikopoulos et al., 2020; Jin et al., 2021) 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 to deal with the generality of the local Hö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.e., Theorem 3). We believe that both of our strategies are of independent interest to 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 Hölder continuity and general noise models. In this context, we are able to show (1) that the iterates must either converge to a fixed point or that they might diverge (Theorem 1); and (2), when the iterates converge to a fixed point, it must be a stationary point of the objective function (Theorem 2).
Moreover, under a slightly more restrictive assumption—which 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).
Finally, we develop two new 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 a formal statement of all assumptions. In Section 3, we specify Stochastic Gradient Descent (SGD) and the properties of the needed properties of the learning rate. In Section 4, we prove and discuss our main results and highlight key steps, while leaving the rest to the appendix. In Section 5, we conclude this work.

heading: 2 STOCHASTIC OPTIMIZATION
text: We consider solving the optimization problem
min θ∈Rp {F (θ) := E [f(θ,X)]}, (1)
where F maps Rp into R; f maps Rp and the co-domain of the random variable X into R; and E is the expectation operator. As we require gradients, we take F and f to differentiable in θ, and denote its derivatives with respect to θ by Ḟ (θ) and ḟ(θ,X). With this notation, we make the following general assumptions about the deterministic portion of the objective function. Assumption 1. There exists Fl.b. ∈ R such that ∀θ ∈ Rp, Fl.b. ≤ F (θ). Assumption 2. There exists α ∈ (0, 1] such that Ḟ (θ) is locally α-Hölder continuous.
Assumptions 1 and 2 would even be considered mild in the context of non-convex deterministic optimization, in which it is also common to 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 Hö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 to be unbiased, which can readily be relaxed (Bottou et al., 2018). The second assumption allows for a generic noise model for an α-Hölder continuous gradient function, and even allows for the second moment to not exist when α < 1 (c.f. Wang et al., 2021).
Assumption 3. For all θ ∈ Rp, Ḟ (θ) = E[ḟ(θ,X)]. Assumption 4. Let α ∈ (0, 1] be as in Assumption 2. There exists an upper semi-continuous function G(θ) such that E[‖ḟ(θ,X)‖1+α2 ] ≤ G(θ).
We will show that Assumptions 1 to 4 are sufficient for a global convergence result.
Remark 1. It is entirely possible that E[‖ḟ(θ,X)‖1+α2 ] is (at least) upper semi-continuous, and to set G(θ) equal to this function. In the case that E[‖ḟ(θ,X)‖1+α2 ] is not upper semi-continuous, it is possible to specify G(θ) as the upper envelope of E[‖ḟ(θ,X)‖1+α2 ] (i.e., the its limit supremum function). However, it is unlikely that E[‖ḟ(θ,X)‖1+α2 ] nor its upper envelope are easy to 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 Hölder constant. To begin, we define the variation on the local Hölder constant. Let α ∈ (0, 1] be as in Assumption 2 and > 0 be arbitrary, and define
L (θ) = supϕ { ‖Ḟ (ϕ)−Ḟ (θ)‖ 2 ‖ϕ−θ‖α2 : ‖ϕ− θ‖2 ≤ (G(θ) ∨ ) 1 1+α } if this quantity is nonzero
otherwise, (2)
where ∨ indicates the maximum between two quantities. Note, the choice of is irrelevant, and they can be distinct for the two cases in the definition of L , 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 nonintuitive,technical assumption that is needed to prove stability. Assumption 5. There exists C1, C2, C3 ≥ 0 such that, ∀θ ∈ Rp,
L (θ)G(θ) + α  ∥∥∥Ḟ (θ)∥∥∥1+α 2
L (θ)
 1/α ≤ C1 + C2(F (θ)− Fl.b.) + C3 ∥∥∥Ḟ (θ)∥∥∥2
2 . (3)
Assumption 5 generalizes Assumption 4.3(c) of 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 & Richtárik, 2020, for a 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 Assumption 5 can be bounded inside of any compact set. Thus, Assumption 5 covers a variety of asymptotic behaviors, such as exp(‖θ‖22), exp(‖θ‖2), ‖θ‖r2 for r ∈ R, log(‖θ‖2+1), and log(log(‖θ‖2+1)+1). Therefore, Assumption 5 holds for functions with a variety of different asymptotic behaviors.
We will show that Assumptions 1 to 5 are sufficient for a stability result.
Now that we have specified the nature of the stochastic optimization problem, we turn our attention to the algorithm used to solve the problem, namely, stochastic gradient descent (SGD).

heading: 3 STOCHASTIC GRADIENT DESCENT
text: SGD starts with an arbitrary initial value, θ0 ∈ Rp, and generates a sequence of iterates {θk : k ∈ N} according to the rule
θk+1 = θk −Mkḟ(θk, Xk+1), (4) where {Mk : k + 1 ∈ N} ⊂ Rp×p; and {Xk : k ∈ N} are independent and identically distributed copies of X . Importantly, {Mk} cannot be arbitrary, and the following properties specify a generalization 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. {Mk : k + 1 ∈ N} are symmetric, positive definite matrices.
The next two properties are a natural generalization of the Robbins-Monro conditions. Let α ∈ (0, 1] be as in Assumption 2. Property 2. Let λmax(·) denote the largest eigenvalue of a symmetric, positive definite matrix. Then, ∑∞ k=0 λmax(Mk)
1+α =: S <∞. Property 3. Let λmin(·) denote the smallest eigenvalue of a symmetric, positive definite matrix. Then, ∑∞ k=0 λmin(Mk) =∞.
We will show that Properties 1 to 3 are sufficient for a global convergence result.
The final property ensures the stability of the condition number of {Mk}. Note, this property is readily satisfied for scalar learning rates satisfying the Robbins-Monro conditions.
Property 4. Let κ(·) denote the ratio of the largest and smallest eigenvalues of a symmetric, positive definite matrix. Then, limk→∞ λmax(Mk)ακ(Mk) = 0.
We will show that Properties 1 to 4 are sufficient for stability.

heading: 4 GLOBAL CONVERGENCE & STABILITY
text: With the stochastic optimization problem and with stochastic gradient descent (SGD) specified, we now turn our attention to what happens when SGD is applied to a stochastic optimization problem. The key step in the analysis of SGD on any objective function is to establish a bound between the optimality gap at θk+1 with that of θk. This step is achieved by using the local Hölder continuity of the gradient function and the fundamental theorem of calculus. Using Assumption 2, we first specify the local Hölder constant. Definition 1. For any θ, ϕ ∈ Rp, define
L(θ, ϕ) = sup ψ  ∥∥∥Ḟ (ψ)− Ḟ (θ)∥∥∥ 2 ‖ψ − θ‖α2 : ‖ψ − θ‖2 ≤ ‖ϕ− θ‖2  . (5) Moreover, for any R ≥ 0, let LR = L(0, ϕ) for ‖ϕ‖2 = R. Remark 2. Note, when the gradient is locally Hölder continuous, LR is well defined for anyR ≥ 0.
With this definition, we can now relate the optimality gap of θk+1 with that of θk by using the following result. Lemma 1. Suppose Assumptions 1 and 2 hold. Then, for any θ, ϕ ∈ Rp,
F (ϕ)− Fl.b. ≤ F (θ)− Fl.b. + Ḟ (θ)′(ϕ− θ) + L(θ, ϕ)
1 + α ‖ϕ− θ‖1+α2 . (6)
Proof. By Taylor’s theorem, F (ϕ)− Fl.b. = F (θ)− Fl.b. + ∫ 1
0
Ḟ (θ + t(ϕ− θ))′(ϕ− θ)dt. (7)
Now, add and subtract Ḟ (θ) to Ḟ (θ + t(ϕ − θ)) in the integral, then apply Assumption 2. We conclude,
F (ϕ)− Fl.b. ≤ F (θ)− Fl.b. + Ḟ (θ)′(ϕ− θ) + L(θ, ϕ) ‖ϕ− θ‖1+α2 ∫ 1
0
tαdt. (8)
By computing the integral, the result follows.
Now, if we simply set ϕ = θk+1 and θ = θk in Lemma 1 and try to take expectations to manage the randomness of the stochastic gradient, we will run into the problem that L(θk, θk+1) and ‖θk+1 − θk‖2 are dependent, and we cannot compute its expectation. In previous work, this technical challenge is waived away by using a global Hölder constant to upper bound L(θk, θk+1), which is unrealistic even for simple problems (see Appendix A).
To address this technical challenge, we innovate two new strategies for handling the dependence between L(θk, θk+1) and ‖θk+1 − θk‖2. 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(θk, θk+1) and ‖θk+1 − θk‖2. 2. With these two quantities decoupled, we will develop a recurrence relationship between the optimality gap at θk+1 and that of θk.
3. We apply this recurrence relationship with refinements of standard arguments or new ones to derive the desired property about the objective function. 4. Finally, we state the generality of the specific events on which we have studied SGD’s iterates.
Thus, it 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.

heading: 4.1 PSEUDO-GLOBAL STRATEGY AND GLOBAL CONVERGENCE ANALYSIS
text: For the first strategy, which supplies the global convergence result, we study SGD on the events
Bk(R) := k⋂ j=0 { ‖θj‖2 ≤ R } , k + 1 ∈ N, (9)
for every R ≥ 0. We now try to control the optimality gap at iteration k + 1 with that of iteration k, which will result in two cases.
1. (Case 1) Bk+1(R) holds we can bound L(θk, θk+1) by LR, and G(θ) is also bounded in the ball of radius R about the origin (which follows from G being upper semi-continuous in Assumption 4). As a result, we could then proceed with the analysis in a manner that is similar to having a global Hölder constant. 2. (Case 2) ‖θk+1‖2 > R and Bk(R) holds. In this case, controlling L(θk, θk+1) is very challenging and, to our knowledge, was not solved before our work.
Our approach for controlling the optimality gap in both cases is supplied in the next lemma, whose proof is in Appendix C. Lemma 2. Let {Mk} satisfy Property 1. Suppose Assumptions 1 to 4 hold. Let {θk} satisfy (4). Then, ∀R ≥ 0,
E [ [F (θk+1)− Fl.b.]1 [Bk+1(R)]| Fk] ≤ [F (θk)− Fl.b.]1 [Bk(R)] − λmin(Mk) ∥∥∥Ḟ (θk)∥∥∥2
2 1 [Bk(R)] + LR+1 + ∂FR 1 + α λmax(Mk) 1+αGR,
(10)
where GR = supθ∈B(R)G(θ) <∞ with G(θ); and ∂FR = supθ∈B(R) ‖Ḟ (θ)‖2(1 + α) <∞.
With this recursion and standard martingale results (Robbins & Siegmund, 1971; Neveu & Speed, 1975, Exercise II.4), the limit of [F (θk)−Fl.b.]1 [Bk(R)] exists with probability one and is finite for every R ≥ 0. As a result, the limit of F (θk)− Fl.b. exists and is finite on the event {supk ‖θk‖2 < ∞} (see Corollary 1).
We can also use Lemma 2 to make a statement about the gradient. Specifically, we can show that the limit infimum of E[‖Ḟ (θk)‖221 [Bk(R)]] must be zero, which is now a standard argument that mimics Zoutendijk’s theorem (Nocedal & Wright, 2006, Theorem 3.2). By Markov’s inequality, this result implies that ‖Ḟ (θk)‖21 [Bk(R)] gets arbitrarily close to 0 infinitely often (see Lemma 8). To show convergence to zero, 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 on the existence of a global Hö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 limk→∞ ‖Ḟ (θk)‖2 = 0 on {supk ‖θk‖2 <∞} (see Corollary 2).
Our final step is to clarify the role of {supk ‖θk‖2 < ∞} in the asymptotic behavior of SGD’s iterates. At first glance, this event seems to imply that the iterates converge to a point. However, owing to the general nature of the noise, it is also possible, say, that the iterates approach a limit cycle or oscillate between points with the same norm. Even beyond this event, the generality of the
noise model may allow for substantial excursions between Fl.b. and infinity (c.f., a simple random walk, which has a limit supremum of infinity and a limit infinimum of negative infinity). Thankfully, we can prove that either the iterates converge to a point or they must diverge—a result that we refer to as the Capture Theorem (see Appendix C). Theorem 1 (Capture Theorem). Let {θk} be defined as in (4), and let {Mk} satisfy Properties 1 and 2. If Assumption 4 holds, then either {limk→∞ θk exists} or {lim infk→∞ ‖θk‖2 = ∞} must occur.
By putting together the above arguments and results, we can conclude that either SGD’s iterates diverge or SGD’s iterates converge to a stationary point. This is formally stated in the following theorem. See Section 1 for a discussion of the practical value of this result. Theorem 2 (Global Convergence). Let θ0 be arbitrary, and let {θk : k ∈ N} be defined according to (4) with {Mk : k + 1} satisfying Properties 1 to 3. Suppose Assumptions 1 to 4 hold. Let A1 = {lim infk→∞ ‖θk‖2 = ∞} and A2 = {limk→∞ θk exists}. Then, the following statements hold.
1. P[A1] + P[A2] = 1. 2. On A2, there exists a finite random variable, Flim, such that limk→∞ F (θk) = Flim and
limk→∞ Ḟ (θk) = 0 with probability one.
Proof. By Theorem 1, we have that P[A1] + P[A2] = 1. Then, on A2, Corollaries 1 and 2 imply that F (θk)→ Flim, which is finite, and Ḟ (θk)→ 0.

heading: 4.2 LOCAL STRATEGY AND STABILITY ANALYSIS
text: While Theorem 2 provides a complete global convergence result, it 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 `1 penalty on the parameters).
To formalize this concept, we define a relevant notion of stability. Definition 2. Stochastic Gradient Descent is stable if
P [ lim sup k→∞ F (θk) =∞ ] = 0, (11)
where {θk} satisfy (4).
We now state the events that we will use to decouple the relationship between L(θk, θk+1) and ‖θk+1 − θk‖2. Unlike in 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 + 1 ∈ N, define
τj = min k : F (θk+1)− Fl.b. > F (θk)− Fl.b. + Ḟ (θk)′(θk+1 − θk)
+ L (θk) 1 + α ‖θk+1 − θk‖1+α2 , and k > j  . (12) Analogously, for every j + 1 ∈ N, define
νj = min {k : L(θk, θk+1) > L (θk), and k > j} . (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 Bk(R), we will derive a recursion on the optimality gap over the events {{τj > k} : k + 1 ∈ N}. Of course, just as before, the main challenge in deriving a recursive formula is to address {τj = k}. Our solution is supplied in the following lemma, whose proof is in Appendix D.
Lemma 3. Let {Mk} satisfy Property 1. Suppose Assumptions 1 to 4 hold. Let {θk} satisfy (4). Then, for any j + 1 ∈ N and k > j,
E [ (F (θk+1)− Fl.b.) 1 [τj > k]| Fk] ≤ ( F (θk)− Fl.b. − Ḟ (θk)′MkḞ (θk) ) 1 [τj > k − 1]
+ λmax(Mk)
1+α
1 + α
L (θk)G(θk) + α  ∥∥∥Ḟ (θk)∥∥∥1+α 2
L (θk)
 1/α  1 [τj > k − 1] . (14)
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 Assumptions 1 to 5, and Properties 1 and 4 hold, and {θk} satisfy (4), then there exists a K ∈ N such that for any j + 1 ∈ N and any k ≥ min{K, j + 1},
E [ (F (θk+1)− Fl.b.)1 [τj > k]| Fk] ≤ ( 1 + λmax(Mk) 1+α C2
1 + α
) (F (θk)− Fl.b.)1 [τj > k − 1]
− 1 2 λmin(Mk) ∥∥∥Ḟ (θk)∥∥∥2 2 1 [τj > k − 1] + λmax(Mk)1+α C1 1 + α .
(15)
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 (θk) exists and is finite on the event ∪∞j=0{τj = ∞} (see Corollary 3). Also as in the pseudoglobal strategy, by improving on the arguments in Patel (2020), we show that limk Ḟ (θk) = 0 on the event ∪∞j=0{νj =∞} (see Corollary 4).
Finally, we show that ∪∞j=0{τj = ∞} and ∪∞j=0{νj = ∞} are probability one events (see Theorem 5). In other words, we show that eventually L (θk) will always dominate L(θk, θk+1). This statement should not come as a surprise on the event {limk θk exists}, but is slightly surprising that it must also hold on {limk ‖θk‖2 =∞}. By combining these results, we can conclude as follows. Theorem 3 (Stability). Let θ0 be arbitrary, and let {θk : k ∈ N} be defined according to (4) with {Mk : k + 1} satisfying Properties 1 to 3. Suppose Assumptions 1 to 5 hold. Then,
1. There exists a finite random variable, Flim, such that limk→∞ F (θk) = Flim with probability one;
2. limk→∞ Ḟ (θk) = 0 with probability one.
Proof. Using Corollary 3, we conclude that ∃Flim that is finite such that limk F (θk) = Flim on ∪∞j=0{τj = ∞}. Using Corollary 4, we conclude that limk Ḟ (θk) = 0 on ∪∞j=0{νj = ∞}. Finally, we apply Theorem 5 to conclude that P[∪∞j=0{νj =∞}] = P[∪∞j=0{τj =∞}] = 1.
See Section 1 for a brief discussion of the practical consequences of Theorem 3.

heading: 5 CONCLUSION
text: 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 Hölder continuous, and replaced it with a local Hö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
result, we showed that these undesirable outcomes were 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 Hö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(θk, θk+1) is eventually well controlled by L (θk), even if the iterate sequence is diverging.
These results have several practical consequences, which we enumerate presently. First, by establishing 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 convergence 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 on such problems.
From a theoretical perspective, we innovated two new analysis strategies and substantially refined a number of argument approaches currently in the literature. We anticipate that these new argument 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 L (θ). In particular, there are functions that may admit upper bounds on L (θ) that ensure Assumption 5 is satisfied, yet using actual value of L (θ) 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 a realistic example in which Assumption 5 is not satisfied, and to 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.

Review summaries:
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. 

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.