Global Convergence and Stability of Stochastic Gradient Descent
Authors: Vivak Patel
Shushu Zhang
Bowen Tian
Venue: NeurIPS 2022 Accept (2022)
Keywords: Stochastic Gradient Descent
Nonconvexity
General Noise Models
Global Convergence

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 demonstrate the restrictiveness of these assumptions using three canonical models in machine learning. Then, we develop novel theory to address this shortcoming in two ways. 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.

Global Convergence and Stability of Stochastic Gradient Descent
Vivak Patel
Shushu Zhang Department of Statistics University of Michigan Ann Arbor shushuz@umi ch edu
Department of Statistics
University of Wisconsin Madison
Madison, WI 53706 vivak. waak..patelvvicc.ee
Bowen Tian
Department of Statistics
The Ohio State University
tian. ww8.83770ccc. 3338bbckeeemail....mm osu. edu
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 con-conyy of real problems, and almost entirely ignore the complex noise models that exist in practice. In this work, we demonstrate the restrictiveness of these assumptions using three canonical models machine learning. Then, we develop novel theory to address this shortcoming in two ways. First, establish that SGD's 's iterates will either globally converge to stationary point or diverge under nearly arbitrary nonconvexity and noise models. Under 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 greater range of stochastic optimization problems with confidence about its global convergence behavior and stability.
Introduction
Stochastic Gradient Descent (SGD) and its variants are dominant algorithms for solving stochastic optimization problems arising in machine learning, and have expanded their 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 and Patel, 2020). Accordingly, understanding the behavior of SGD and its variants has been erucial their reliable application in machine learning and beyond. As a result, the theory of these methods has greatly advanced, most notably for SGD as it is the basis for, and simplest of, these methods. Indeed, SGD has been analyzed from many perspectives: global convergence analysis [Lei et al., 2019, Gower al., 2020, Khaled and Richtárik, 2020, Mertikopoulos et al., 2020, Patel, 2021], local convergence analysis [Mertikopollos et al., 2020], greedy and global complexity analysis [Gower et al., 2020, Khaled and Richtárik, 2020], asymptotic weak convergence [Wang al., 2021], and saddle point analysis [Fang et al., 2019, Mertikopoulos et al., 2020, Jin et al., 2021].
While all of these perspectives add dimensions gence analysis of SGD is the foundation as it dictates whether local analyses, complexity analyses saddle point analyses are even warranted. As surveyed in Patel [2021], these current global
understanding of SGD, the global conver-
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

convergence analyses of SGD make a wide variety of assumptions, most commonly: (1) the objective function is bounded from below, (2) the gradient function globally Lipschitz continuous, (3) the stochastic gradients are unbiased, and (4) the variance of the stochastic gradients are bounded. While the first and third assumption are generally reasonable, the second and fourth assumptions and their more recent generalizations are not usually applicable to machine learning problems as we now demonstrate through three simple examples. Note, in the first two examples, we make use of a penalty function, which can be removed without impacting the result.
Feed Forward Neural Network. Consider the example (Y, 2) where Y is binary label and Z is feature vector. We will attempt to predict Y from Z using a simple multi-layer feed forward network as shown in Fig. 1. The next result states that for a simple distribution over the example space and for simple, archetype network, the gradient function is not globally Lipschitz continuous, nor does it satisfy the (possibly) more general (Lo, L1 -smooth assumption [Zhang et al., 2019, Definition Assumption 3]. Moreover, the variance of the stochastic gradients is unbounded. See Appendix A.2 for a proof.
Example I:
Wix
W2x
W3X
W4X
Z
4
Figure 1: A diagram of a simple feed forward network for binary classification.
Proposition 1. Consider the feed forward network in Fig. 1 with a linear and y sigmoid trained with binary cross- pross-entropy loss with a Ridge penalty. There exists a finite, discrete distribution for (Y, Z) such that the risk function's 's gradient is not globally Lipschitz continuous, nor does satisfy the (In, Lsm-shoth assumption. Moreover, the variance of the stochastic gradients is not bounded.
Example 2: Recurrent Neural Network. Consider the example (Y. Z1, Z2, Zz) where Y is binary label and (Zo: Zi, Z2, Za} are sequentially observed. We will attempt predict Y from Z using a simple recurrent network as shown in Fig. 2. The next result states that for a simple distribution over the example space and for a simple, archetype network, the training function violates the aforementioned assumptions. See Appendix A.3 for proof.
Hi
WaX x
Wix x
W2
Zi
Figure 2: A diagram of recurrent neural network for binary classification task.
Proposition 2. Consider the recurrent network in Fig. 2 with linear and y sigmoid trained with a binary cross-entropy loss with a Ridge pemalty. There exists a finite, discrete distribution for (Y, Zo. Zn, Zoz Z3) such that the risk function's 's gradient is not globally Lipschitz continuous, nor does it satisfy the (Lg, L2) -mmothh assumption. Moreover, the variance of the stochastic gradients is bounded.
Example 3: Poisson Regression. Consider fitting a Poisson regression model by the standard maximum likelihood framework using independent copies of the example (Y, Z), where Y is count
See Bottou et al. [2018] for a simple relaxation of unbiased stochastic gradients.

---

response variable and Z is a predictor. The next result states that for a very nice Poisson regression problem, the stochastic gradients violate the bounded variance assumption, its generalization [Bottou et al., 2018, Assumption 4.3c], and, in turn, its generalization, expected smoothness [Khaled and Richtárik, 2020, Assumption 2]. See Appendix A.4 for a proof.
Proposition 3. Let Y and Z. be independent Poisson random variables with mean one. Consider estimating a Poisson regression model of Y as a function of Z. Then, the gradient function is not globally Lipschitz continuous, nor does satisfy the (Lo, L1)-smooth assumption. Moreover, the variance of the stochastic gradients is not bounded, does not satisfy [Bottou et al., 2018, Assumption 4.3c], nor does satisfy [Khaled and Richtárik, 2020, Assumption 2].
As these three examples show, global convergence analyses that make use of the aforementioned assumptions do not apply to these canonical examples of machine learning problems. In fact, to our knowledge and as summarized in Table I, there are global convergence analyses of SGD that apply to these examples.
The Problem:
As result, do not have guarantees about how SGD behaves these simple machine learning problems, which calls into question what SGD and its variants are doing on more complicated machine learning models.
Contributions. To address this problem,
1. We relax the global Lipschitz continuous gradient assumption, the bounded variance assumption, and their aforementioned generalizations to assumptions that are applicable to the examples above. Specifically, we relax the global Lipschitz continuity assumption and the (Lo, L1) -smoohhth assumption to local a-Hölder continuity of the gradient for a E (0, 1] (see Assumption 2), which is even a relaxation even for deterministic gradient algorithms (c.f. Nocedal and Wright (2006),Theorem, 3.2, 3.8, 4.5, 4.6). For the a in the local Hölder assumption, we also relax the bounded variance assumption to only require that the (1 a) mmmmtt of the stochastic gradient is bounded by an arbitrary upper semi- coniicontinuous function (see Assumption 4). Our assumption allows stochastic gradients whose noise may not have variance. Moreover, assumption generalizes the noise assumption of Bottou et al. [2018], the expected smoothness assumption of Gower et al. [2020] and Khaled and Richtárik [2020], and the noise assumption of Asi and Duchi [2019]. We also point out that we do not require the coercivity or asymptotic flatness assumptions that are commonly considered in the analysis of SGD (c.g., Mertikopoulos al. [2020]. Assumptions 2 and 3).
2. Owing to the relaxation in the assumptions, we cannot apply the standard analysis as the local Hölder constant and the iterate difference are conditionally dependent random variables (see the discussion after Lemma 1). As result, by generalizing our previous techniques in Patel [2021], Patel and Zhang [2021] to the a-Hölder continuous setting, we innovate a new analysis strategy (see Section 4.1) to prove that, with probability one, either SGD's 's iterates will converge to stationary point or they diverge (see Theorem 2). Importantly, our new analysis strategy can be broadly applied even deterministic algorithms to relax the assumptions found in the literature.
3. The divergence component of our Theorem 2 is somewhat disconcerting what happens if the iterates diverge. To amcliorate this concern, we add an additional assumption (see Assumption 5) and introduce another analysis strategy (see Section 4.2) to prove, even if the iterates are diverging, the objective function converges to a finite random variable with probability one (see Theorem 3).
cannot say exactly
Our results do not supply a rate of convergence as this is impossible for the broad class of nonconvex functions and the generality of the noise models studied in this work [Wolpert and Macready, 1997]; in other words, we can always construct a nonconvex objective function, a noise process, and choose an initialization such that any rate of convergence statement will be violated. Indeed, find it remarkable that it is even possible to provide a global convergence statement for such a broad class of nonconvex functions and general noise models.
II Majewski et al. [2018], this implied by their third assumption.
3

---

Table 1: A survey of influential, recent global analyses of SGD and their dependence on the two assumptions that are either individually or both violated by the simple examples discussed Section 1.
Assumption
Works Depending the Assumption
Global Lipschitz
Reddi al. [2016a] 6, Ma and Klabjan [2017]. Zhou al. [2018], Bassily et al. [2018], J3, Lei et al. [2019]. Li and Orabona [2019],
Hölder Continuity of Gradient
Gower et al. [2020], Khaled and Richtárik [2020]. Mertikopoulos
et al. [2020]. Patel [2021], Jin et al. [2021]. Wang et al. [2021].
Bounded Variance of Stochastic Gradients
Reddi al. [2016b], Ma and Klabjan [2017], Majewski et al. [2018], Hu et al. [2019], Bi and Gunn [2019], Zou et al. [2019],
Mertikopoulos al. [2020].
Limitations. We make note of two important limitations in our work. First, we do not consider the important case of nonsmoothness in this work as we require that the gradients of the stochastic optimization function are continuous. However, we note that if the results of Bianchi et al. [2022] are broadly applicable, then SGD never observes point of nonsmoothness and our results would then be applicable. Second, we do not have a simple interpretation of Assumption 5-though it seems to have a close relative in another analysis (see Wang and Wu [2020])~ nor have we been able to construct relevant counterexample that can illuminate the limitations of this assumption.
2 Stochastic Optimization
We consider solving the optimization problem
min (F(O) = [1(, [|(0, BER"
where F maps R into R; f maps IRP and the co-domain of the random variable X into IR; 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 I by F()) and f(0, X). With this notation, we make the following general assumptions about the deterministic portion of the objective function.
Assumption 1. There exists FL.. E R such that v0 E RP, FL. < F()).
Assumption 2. There exists E (0, 1] such that F(0) is locally a- c-Hölder continuous.
Remark 1. For F to be locally a-Hölder continuous for some a (0, 1], for every compact set K C I2 there exists constant L > 0 such that for every 0, 1 E K,
| - F(t))| - L - v
(2)
Remark 2. As an example, empirical risk minimization problem for deep neural network with twice continuously differentiable activation functions with a twice continuously differentiable loss function will readily satisfy the above conditions.
Assumptions 1 and 2 would even be considered mild in the context of non-convex deterministic optimization, in which is also common to assume that the objective function has well-behaved level sets [e.g.. Nocedal and 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 (see Table 1).
Our final step 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 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 to not exist when a < 1 [c.f. Wang et al., 2021, which requires a decomposition
the noise term that we do not require].
Assumption 3. For all 0 E Rº, F())= = (, X)].
Assumption 4. Let a E (0, be as in Assumption 2. There exists an upper semi-continuous function G()) such that [0) X) 1 < G(0).

---

Remark 3. For G(Ø) to be upper cemi-continuous, then for all > 0, (0 E R": G(O) < و) are open R.
We will show that Assumptions to 4 are sufficient for global convergence result (see Theorem 2).
Remark 4. As shown in $A, our examples from $1 satisfy Assumptions to 4.
Remark 5. entirely possible that [0) x [a] is (at least) upper semi-continuous, and to set G(0) equal to this function. In the case that [ (0, x)1l2++ is not upper semi-continuous, is possible to specify G(0) as the upper envelope of E x)112 (i.e., its limit supremum function). However, it is unlikely that (f, X 112 +0 nor its upper envelope are easy to specify explicitly, and is more likely to be able to find an upper bound.
Remark 6. We use Assumption 4 to conclude that on any compact set, the 1 + a moment of the stochastic gradient is bounded. Of course, we can assume this directly (i.e., on any compact set, the 1 + a moment is bounded), which, at first glance, appears be a relaxation. However, if assume that on any compact set, the 1 + moment is bounded, we can use this to construct G(#) that is upper cami-continuous, Thus, the two assumptions are equivalent.
Remark 7. A simple example that shows the utility of Assumption 4 is to optimize E[0x] where X is an exponential random variable with parameter 1 and 0 E [1, u] where u < exp(1). First, it is easy confirm that the objective function is differentiable and its derivative globally Lipschitz continuous. Moreover, given that we are on a bounded interval, we conclude that the derivative is globally a-Hölder continuous for any a E (0, 1]: therefore, we are free to choose the a as we see fit. Now, when u < exp(1/2), we have that second moment of the stochastic gradient function exists. However, when cxp(1/2)
< cxp(1). only smaller moments of the stochastic gradient will exist. e)) with
Specifically, only for u < exp(11(1 gradient will exist. Thus, depending on the size of our interval, we may not have the existence the second moment, and, consequently, we may not have the existence of the variance.
(0, 1) will the 1 + moment of the stochastic
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] be as in Assumption 2 and
be arbitrary, and define
[[(())
||<p 0l12 s (G(O) V } if this quantity is nonzero (3)
(0)
sup
1 1
otherwise,
where V 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 be the same for simplicity. Importantly, the quantity, C., is defined at every parameter under Assumption 2.
With this quantity, Assumption 5. There exists C₁ C2. O3 2
state a nonintuitive, technical assumption that is needed to prove stability.
such that, V0 R.P.
1ta
1/a
[(0)
S. CC -F.)) + Os 1
C.(0)G(0)
(4)
(0)
Assumption 5 generalizes Assumption 4.3(c) of Bottou et al. [2018], which is satisfied for large swath of statistical models. Moreover, Assumption 5 generalizes the notion of expected smoothness [see Khaled and Richtá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 Assump- tion 5 can be bounded inside of any compact set. Thus, Assumption 5 covers a variety of asymptotic behaviors, such as exp([|@]]3 ),, exp( [0][2), ||@|| for E R. log( [ |2 1). and log (log( [|0]]2 [1]+|++1)++ Therefore, Assumption 5 holds for functions with a variety of different asymptotic behaviors.
We will show that Assumptions to 5 are sufficient for stability result (see Theorem 3).
5

---

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, 8o E R², and generates sequence of iterates {0s h N} according to the rule
0 = 6g M&f Xx+1);
(5)
where {M& k +IEN) C R and ( [xx k NJ are independent and identically distributed copies of X. Importantly, { {M&] cannot be arbitrary, and the following properties specify a gener- alization of the Robbins and Monro [1951] conditions for matrix-valued learning rates [c.f. Patel, 2021].
The first condition requires a positive learning rate, and imposes symmetry to ensure the existence of real eigenvalues.
Property 1. (Mx k + 1 E NJ are symmetric, positive definite matrices.
The next two properties are natural generalization of the Robbins-Momn conditions. Let (0, 1] be as in Assumption 2.
Property Let Amax (.) denote the largest eigenvalue of symmetric, positive definite matrix. Then,
kk Amax (Mx) =: S < co.
Property 3. Let Amnn (.) denote the smallest eigenvalue of symmetric, positive definite matrix.
Then, Ex Amia (Mx)
We will show that Properties to 3 are sufficient for global convergence result (see Theorem 2).
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.
Property 4. Let x(-) denote the ratio of the largest and smallest eigenvalues symmetric, positive definite matrix. Then, lim Amax (M2)) " nd (M = 0.
We will show that Properties to are sufficient for stability (see Theorem 3).
4 Global Convergence & Stability
With the stochastic optimization problem and with stochastic gradient descent (SGD) specified, we now turn attention what happens when SGD is applied to stochastic optimization problem. The key step in the analysis of SGD on any objective function to establish a bound between the optimality gap at 04+1 with that of fg. This step is achieved by using the local Hölder continuity of the gradient function and the fundamental theorem of calculus. Using Assumption 2, we first specify the local Hölder constant.
Definition 1. For any 0, E IR,, define
F(w) F()) |/
L(O Φ) = sup +
0 0 1 B(O, 11/ 012))
(6)
where B(0,r) is an open ball around 0 of radius r > 0. and B(O,r) r) is its closure. Moreover, for any
R > 0, let Lg be the supremum of L(0, :p) for any distinct 0, sp E B(O, R).
Remark 8. Note, when the gradient is locally Hölder continuous, LR is finite for any R 2 0.
With this definition, we can now relate the optimality gap of 0x+1 with that of 0g by using the following result and proved in Appendix B.

---

Lemma 1. Suppose Assumptions and 2 hold. Then, for any 0,4 IP,,
_(,,0) F(Ø) - FLo.3 S F(O) FLS. + ((0)((0 - 8) I+a
11 011 1+
Now, we simply set = 0x+1 and 0 = 0x in Lemma and try to take expectations to man- age the randomness of the stochastic gradient, ||0=-1 0ell2 are potentially dependent," and we cannot compute its expectation. In previous work, this technical challenge waived away by using global Hölder constant to upper bound L(Ok, 0x+1). which is unrealistic even for simple problems (see Section I).
will run into the problem that L(0k, 0k+1) and
To address this technical challenge, innovate between L(Ox, (x+1) and [ - 8% 22- In both strategies, we follow the same general approach:
strategies for handling the dependence
1. We begin by restricting our analysis to specific events, which will allow to decouple [(0,, 02+1) and |[0++1 - 0x 12
2. With these two quantities decoupled, we will develop recurrence relationship between the optimality gap at 0x+1 and that of 0g.
3. We apply this recurrence relationship with refinements of standard arguments new ones 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, it follows, we will define two distinct series of events for the two strategies. The first strategy, which we refer to as the pseudo-globe strategy, will provide the global convergence analysis. The second strategy, which we refer to 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
(R) = n [10,112 s R}. K k+1eN,
(8)
1=0
for every R 2 O. We now try to control the optimality gap at iteration is + with that of iteration k which will result in two cases.
1. (Case 1) B (R)) holds. We can bound L(O,, 0x+1) by LR. and G(0) is also bounded in the ball of radius R about the origin (which follows from G being upper semi-continuous in Assumption 4). As result, we could then proceed with the analysis in manner that is similar to having global Hölder constant.
2. (Case 2) | ll > R and B&(R) holds. In this case, controlling L(Ok, 0x+1) is very challenging and, our knowledge, was not solved before our work.
Our approach for controlling the optimality gap in both cases supplied the next lemma, whose proof is in Appendix C.
Lemma 2. Let {Ma} satisfy Property 1. Suppose Assumptions to 4 hold. Let {0x) satisfy (5). Then, VR 2 0,
E [[F(Ox+1)) -F...) [B ( S [F(0+) F B8 (R)
Amin (Ma) (0x)) [Bx( + LR+1 + +FR
Amax (Mx) 1 GR.
1
where GR = S(PDE G(O) < 2o with G(f); and OFR = suPoe [0) + +a) < co.
With this recursion and standard martingale results [Robbins and Siegmund, 1971, Neveu and Speed, 1975, Exercise II.4], the limit of [F())) Fi.o.]1. [Bx exists with probability one and is finite for
While it is possible that these two terms are independent, we would require lot more information to determine this and it would likely be on herate-by-iterate basis for the general class of problems considered this work. Thus, in this general setting, we camnot assume independence and need default treating these terms as dependent.
7

---

every R 2 O. As a result, the limit of F(Ox) FL... exists and is finite on the event (sup, |101112 < oo} (see Corollary 1).
We can also use Lemma 2 to make a statement about the gradient. Specifically, we can show that (R)]] must be zero, which is now a standard argument that mimics Zoutendijk's theorem [Nocedal and Wright, 2006, Theorem 3.2]. By Markov's inequality, this result implies that || [0x0)) 2 [B& [)] gets arbitrarily close 0 infinitely often (see Lemma 9).
the limit infimum of E|] ((x)) (0x)) [Bx
To show convergence to zero, however, is not standard. Several strategies have been developed, namely those of Li and Orabona [2019], Lei et al. [2019], Mertikopoulos et al. [2020), Patel [2021],
Patel and Zhang [2021]. Unfortunately, the approaches of Li and Orabona [2019], Lei et al. [2019] rely intimately on the existence of a global Hölder constant, while that of Mertikopoulos et [2020] requires even more restrictive assumptions. Fortunately, the approach of Patel [2021]. Patel and Zhang [2021] can be improved and generalized to the current context (see Lemma 10). Thus, we
show that limx-+so [[=((x) ll on {sup; ||0*122 oo) (see Corollary 2).
Our final step is to clarify the role of {sup,, ||0x112 < bo} in the asymptotics of SGD's s iterates. At point. However, owing the
first glance, this event seems to imply that the iterates converge general nature of the noise, it is also possible, say, that the iterates approach 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 Fi.. and infinity (c.f., simple random walk, which has 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 (Capture Theorem). Let {8x} be defined in (5). and let {Mr} satisfy Properties 1 and 2. If Assumption holds, then either (lima- 0g exists} } or {lim inf |0& = oc) must occur
By putting together the above arguments and results, we can conclude that either SGD's iterates diverge or SGD'ss iterates converge a stationary point.
Theorem 2 (Global Convergence). Let Ou be arbitrary, and let (0x k N be defined according to (5) with [M& k + 1} satisfying Properties to 3. Suppose Assumptions 1 to hold. Let A (lim infu |10A122 )o) and A = {limx++o Og exists). Then, the following statements hold.
1. [[AA]] + P[A2]
2. On A2. there exists a finite random variable, Flims such that lim4 F(Ox) Fimm and limx F(Ox)= = 0 with probability one.
Proof. By Theorem I, we have that P[A.] + +[A2] 1. Then, on A2, Corollaries 1 and 2 imply that F(Ox)) Fim, which is finite, and F(Ox) + O.
We pause to stress to a fact about Theorem 2: it is nonobvious. To be specific, under such general nonconvexity and noise, we should anticipate any number of asymptotic behaviors for the iterates: convergence to a stationary point, convergence to a nonstationary point, being trapped in cycle, convergence to limit cycle, and divergence infinity. However and very surprisingly, able to show that only two possible outcomes can occur: convergence to a stationary point or divergence. Indeed, in previous results [c.g.. Mertikopoulos et al., 2020, Patel, 2021], only less specific determinations could be made under much more limited settings.
are
4.2 Local Strategy and Stability Analysis
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 possibility that SGD may be unstable, which would be highly unexpected and undesirable, especially when the objective function is coercive (c.g., has an ll penalty on the parameters). To formalize this concept, we define relevant notion of stability.
8

---

Definition 2. Stochastic Gradient Descent is stable if
IP sum F(Ox) k-000
=0,
(10)
where }0x} satisfy (5).
We now state the stopping times that we will use to decouple the relationship between L(Ok, 0k+1)
and |0 0x|12. For every 1 E N, define
F(0x+1) F.o. F(Ox) PLS. + F(0x)(00+z - -0a)
= min
k:
(kk0) + 1 11:+11 - 0x112ta, and j
(1I)
Now, we will use (11) to establish the stability of the objective function. Just as we did with 5e (R), we will derive a recursion on the optimality gap over the events (1T > k} k+ 1 NJ. 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.
Lemma 3. Let } satisfy Property 1. Suppose Assumptions to 4 hold. Let {0x} satisfy (5).
Then, for any j + E and k > j.
E [[F(0++1) Fi..) 1 [T, > k]] Fx] S (((0)) FLB. - F(0&) Mn M(.)) 1 [T, > --
1ta 1/a
Amax (hax(MMe) (Ma)++a
F(O+))
(12)
(O,)))()))++
+a
+a
1 [ k -
1+a
(0a)
From Lemma 3, there is a clear motivation for Assumption 5. Indeed, if apply Assumption 5, Lemma 3 produces the following simple recursive relationship.
Lemma 4. If Assumptions 1 to 5, and Properties and hold, and {0x} satisfy (5), then there exists a K E N such that for any j + N and any l 2 min(K, K,j + 1}.
E [[(F(Ox+1) FL..) [Ti > Fr)
C2
+ Amax (Ma)
(F(0k) - FL..) [ --1] 1]
1+
(13)
Amina (Mx) |((A)) 1/3 1 [T, > k - 1] Amax (Mx 1+a Ci
(Mx)
1
Just as in the pseudo-glote strategy, Lemma can be combined with standard martingale results [Robbins and Siegmund, 1971, Neveu and Speed, 1975, Exercise II.4] to conclude that the limit of F(Ox) exists and finite on the event U (T, = 00) (see Corollary 3). Also as in the pseudo-global strategy, by improving on the arguments in Patel [2021], Patel and Zhang [2021], we show that lim inf; F(0x) = 0 on the event o = co} (see Lemma 14).
Finally, we show that o = j is a probability one event (see Theorem 5). This statement should not come as surprise on the event (lim 0g exists), but is slightly surprising that it must also hold on {limæ ||0xl12 = 30). By combining these results, we can conclude as follows.
Theorem 3 (Stability). Let 0g be arbitrary, and let {0x NJ be defined according to (5) with {My+ : + 1} satisfying Properties to 4. Suppose Assumptions 1 to 5 hold. Then,
1. There exists finite random variable, Fii. such that limg F(Ox) = Fiim with probabil- ity one;
2. lim inf F(xx) with probability one.
Proof. Using Corollary 3, we conclude that 3Fmm that is finite such that lim F(Ox) Fiim on o oo). Using Lemma 14, we conclude that lim infa ((x)) = 0 on o 00). Finally, apply Theorem 5 to conclude that PPU co)) =

---

We would like to demonstrate simple example of how we would use Theorem 3. Consider applying SGD to linear regression specified in Appendix A.I. For this example, straightforward to verify that the assumptions of Theorem 3 are satisfied. Therefore, if we are to apply SGD to linear regression, we know that with probability one, F(Ox) -> Flim which finite. Since F(0) + oo as 0 + xc, we know that } cannot diverge. Hence, {0x} must remain finite with probability one. By Theorem {0x} must converge to a stationary point, Since this stationary point unique in our specific example of linear regression, we know that SGD must converge to the global minimizer of the linear regression problem. Note, we can follow this outline to draw similar conclusions more complex situations.
5
Conclusion
In this work, we studied the global convergence analysis of Stochastic Gradient Descent with diminishing step size. We began our discussion by producing three simple problems for which the common assumptions (i.e., global Hölder continuity, bounded variance) and their generalizations in the SGD literature are violated. Indeed, to our knowledge, there does exist theory that covers these problems. For example, prior to our work, it was unknown what SGD with arbitrary initialization and diminishing step sizes will do on simple neural network problems, which raised the question of what SGD is doing on more complicated learning problems.
Motivated by example problems, considered more general set of assumptions (see Assump- tions 2 and 4). Given the generality of our assumptions, we developed a new analysis technique that of interest beyond this work, and we proved that SGD's iterates either converge to a stationary point or diverge. Thus, we now know how SGD with arbitrary initialization and diminishing step sizes will behave
much larger class of learning problems.
We note that we do not provide rate of convergence results mainly because it is impossible for the broad class of functions admitted by our assumptions [Wolpert and Macready, 1997]. We stress that global rates of convergence (c.g., complexity statements) results that exist do not apply to the two simple neural network problems that supplied at the beginning of this work.
We also studied what happens when SGD's ' iterates diverge. To this end, we required an additional assumption under which we developed another novel analysis technique and showed that, regardless of SGD's iterates' behavior, the objective function will converge to a finite random variable with probability one. Unfortunately, we make an assumption that we were not able to interpret, but we will leave this to future work.
10

---

References
H. Asi and C. Duchi. Stochastic (approximate) proximal point methods: Convergence, optimality. and adaptivity. SIAM Journal on Oprimization, 29(3):2257-2290 2019.
R. Bassily, M. Belkin, and S. Ma. On exponential convergence of sgd in non-convex over-parametrized learning. arXiv preprint arXiv:1811.02560 2018.
J. Bi and S. R. Gunn. stochastic gradient method with biased estimation for faster nonconvex optimization. In Pacific Rim International Conference on Artificial Intelligence, pages 337-349. Springer, 2019,
Bianchi, W. Hachem, and Schechtman. Convergence of constant step stochastic gradient descent for non-smooth non-convex functions. Set- Valued and Variational Analysis, pages 1-31, 2022.
L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223- 311, 2018.
H.. Chen, Zheng, Al Kontar, and G. Raskutti. Stochastic gradient descent in correlated settings: A study gaussian processes. NewrIPS, 2020.
C. Fang, Z. Lin, and T. Zhang. Sharp analysis for nonconvex sgd escaping from saddle points. In Conference on Learning Theory. pages 1192-1234, PMLR, 2019.
R. M. Gower, O. Sebbouh, and N. Loizou. Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation. arXiv preprint arXiv:2006.100 10311, 2020.
M. Hardt, T. Ma, and B. Recht. Gradient descent learns linear dynamical systems. WwXiv:1609005199 2016.
arXiv preprint
W. Hu, C. J. Li, L. Li, and J.-G. Liu. On the diffuusion approximation of nonconvex stochastic gradient descent. Annals of Mathematical Sciences and Applicaaions, 4(1), 2019.
C. Jin, Netrapalli, R. Ge, S. M. Kakade, and I. Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. Journal of ACM (JAMM), 68(2):1-29, 2021.
A. Khaled and Richtárik. Better theory for sgd in the nonconvex world. arXiv preprint arXiv22002.03329, 2020.
H.S.. Kim, L. Zhang, A. Bienkowski, and K. Pattipati. Multi-pat pass sequential mini-batch stochastic gradient descent algorithms noise covariance estimation adaptive kalman filtering. JEEE Access, 9:99220-99234, 2021.
Lei, T. Hu, G. Li, and Tang. Stochastic gradient descent nonconvex learning without bounded gradient assumptions. IEEE Iransactions on neural networks and learning systems. 31(10):43944440 2019.
Orabona. the convergence of stochastic gradient descent with adaptive stepsizes. The 22nd
International Conference on Artificial Intelligence and Statistics, pages 983-992, PMLR, 2019.
Ma and Klabjan. Convergence analysis of batch normalization for deep neural nets. arXiv preprint /tdd::/705.80000 2017.
Majewski, B. Miasojedow,
Moulines. Analysis nonsmooth stochastic approximation: the differential inclusion approach. arXiv preprint arXiv: 1805.0/916 2018.
Mertikopoulos, N. Hallak, A. Kavis, and V. Cevher. On the almost sure convergence stochastic gradient descent in non-convex problems. arXiv preprint arXiv:2006. / 11144, 2020.
J. Neveu and T. Speed. Discrete-paramette martingales, volume 10.
Amsterdam, 1975.
Nocedal Wright. Numerical optimization. Springer Science & Business Media, 2006.
V. Patel. Stopping criteria for, and strong convergence of, stochastic gradient descent bottou-curtis-nocedal functions. Mathematical Programming, pages 1-42, 2021.
V. Patel and S. Zhang. Stochastic gradient descent nonconvex functions with general noise models. arXiv preprint arXiv:2104,0 004233 2021.
S. Reddi, S. Sra. B. Poczos, and A. J. Smola. Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. Advances in neural information processing systems, 29:1 11111155115 2016a.

---

S. J. Reddi, A. Hefny, S. Sra. B. Poczos, and A. Smola. Stochastic variance reduction for nonconvex optimization. In International conference muchine learning, pages 314-323. PMLR, 2016b.
H. Robbins and S. Monro. A stochastic approximation method. The onnals of mathematical statistics, pages 400-407, 1951.
H. Robbins and D. Siegmund. A convergence theorem for non negative almost supermartingales and some applications. In Optimizing methods in statistics, pages 233-257. Elsevier, 1971.
H. Wang. M. Gürbüübalaban, I. Zhu, U. Şimçekli, and M. A. Erdogdu, Convergence rates of stochastic gradient descent under infinite noise variance. arXiv preprint arXiv:2102. 10346, 2021.
Y. Wang and S. Wu. Asymptotic analysis via stochastic differential equations of gradient descent algorithms in statistical and computational paradigms. Journal of machine learning research, 21, 2020.
D. H. Wolpert and W. G. Macready, No free lunch theorems for optimization. IEEE transactions on evolutionary computation, 1(1):67-82, 1997.
J. Zhang. T. He, S. Sra, and A. Jadbahaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference Learning Representations, 2019.
S. Zhang and V. Patel. Stochastic approximation for high-frequency observations in data assimilation. arXiv preprint arXiv:201 2020.
D. Zhou, P. Xu, and Q Gu. Stochastic nested variance reduction for nonconvex optimization. arXiv preprint arxiv: 1806.0781 2018.
F. Zou, L. Shen, Z. Jie. W. Zhang, and W. Liu. A sufficient condition for convergences of adam and rmsprop. In Proceedings the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11127-11135 2019.
12


Reviews:
[{"review_id": "byr-1ZcQa9", "reviewer": "Reviewer_JXLB", "summary": "The authors analyze the convergence and stability of stochastic gradient descent under certain assumptions. In particular, they consider the function to be *locally* Holder-continuous (in opposition to global assumptions), and they relax the boundedness of the variance. In particular:\n\nUnder reasonable assumptions on the stochastic gradient descent (SGD) algorithm (with diminishing step size),  the authors show the iterates of SGD either converge (to a stationary point) or diverge to infinity. Under another technical assumption, they also show convergence with probability one.", "questions": "Do the authors believe it is possible to remove the assumption that max_k |theta_k| < infinity?", "limitations": "See the \"strengths & weaknesses\" section.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper claims it uses less restrictive assumptions than other existing results. I agree with the authors; they generalize the analysis of SGD to a broader class of functions. However, my biggest concern is the (kind of hidden) assumption that most results hold under |theta_k|<infty.\n\nMoreover, the result of Theorem 1 seems intuitive, given that we are working with diminishing stepsize. I may be wrong on this point, however. Here is my intuition. \nEither:\nthe iterates are unbounded,\nthe iterates are bounded and, in that case, contained in a compact set of radius at most R. Since we have diminishing stepsize and a bounded variance, it seems reasonable to believe that, eventually, the iterates stop moving. Moreover, I think that in such a case, it is possible to write a rate of convergence for SGD to a stationary point that depends on R (which justifies Theorem 2).\nIn particular, the assumptions made in this paper are that f is locally Holder-smooth, and the variance is locally bounded - the authors justify introducing those hypotheses to contrast with similar results that assume global bounds. However, combining local assumptions and |theta_k|<R is (almost) the same as assuming global constants, as we can take the worst-case of those constants over R.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "b3LV9KWZxMs", "reviewer": "Reviewer_SUmp", "summary": "This paper studies the convergence of stochastic gradient descent for smooth non-convex stochastic optimization. The main contribution of this paper is that it relaxes the commonly-used assumptions in proving the convergence: (1) global smoothness of the objective function, (2) bounded variance of the stochastic gradient. They are replaced by a much weaker assumption, i.e. local Hölder continuous of the gradient and bounded $1+\\alpha$ moment of the stochastic gradient. The authors prove that SGD with a diminishing step size must either converge to a stationary point or diverge. They further add a technical assumption and prove a stability result, showing that the objective function cannot diverge even if the iterates diverge.", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n1. This paper is well-written. The motivation is clear and the presentation is concise.\n2. It seems that the results and technical contribution are non-trivial.\n\n**Weaknesses**:\nThe results seems to be not very interesting. While it gives convergence results, it does not say anything about the convergence speed (while the authors have pointed out that it is impossible under such general assumptions). In such a situation, my concern is that are the general assumptions really necessary? For example, modern optimization problems for neural networks are clearly not globally smooth, but relaxing it by locally Hölder continuous in gradients seems too general. Several works considered more restrictive assumptions, e.g. the generalized smoothness [1,2], under which optimal algorithms have been proved. Analogously, several works relax the assumption of bounded gradient variance by unbounded one that is locally proportional to the gradient magnitude [3,4] (which is satisfied by your first example), in which case optimal algorithms are also developed. \n\nBut this paper clearly has its own values. Currently I haven't delved into the proof details and I may not correctly understand the implications of these results, so I toned down the level of confidence.\n\n[1] Why gradient clipping accelerates training: A theoretical justification for adaptivity. ICLR 2020.\n\n[2] Improved Analysis of Clipping Algorithms for Non-convex Optimization. NeurIPS 2020.\n\n[3] The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance. COLT 2022.\n\n[4] Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis. NeurIPS 2021.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "XgwwNMa23GC", "reviewer": "Reviewer_fVMv", "summary": "This paper analyzes the global convergence of SGD under more practical assumptions, for the ease of studying the realistic performance for training with non-convex function and noisy feedback. Specifically: 1) it relaxes the global Lipschitz continuity of the gradient function to local $\\alpha$-Holder continuity; 2) it relaxes the bounded variance assumption to that the $(1+\\alpha)$-moment of the stochastic gradient is bounded by an arbitrary upper semi-continuous function. Hence, the authors provide a new analysis that SGD will either converge to a stationary point or diverge. To ensure the convergence, an additional assumption that generalizes the notion of expected smoothness is introduced.", "questions": "1. How does assumption 5 hold for the cases in Example 1,2,3?\n2. It is better to give full definitions of $\\alpha$-holder continuous and semi-continuous function.\n", "limitations": "The main limitation is the interpretation of Assumption 5, which is left for future works.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The authors provide three typical losses: linear regression, feed-forward neural networks and recurrent neural networks, to demonstrate the invalidation of current assumptions for analyzing the global convergence of SGD. This shows that current analyses can be applied to practical machine learning problems.\n2. The authors give a solid analysis of the global convergence and high-level descriptions for the proof. \n3. Theorem 1 is a strong result than I thought when I just read the introduction. Provided that the model parameters are usually finite, we can infer that the model converges globally from Theorem 1. \n\nWeakness:\n\n1. Proposition 1 is built by setting $\\|\\theta\\|_2 \\rightarrow \\infty$, which is not the typical situation for training deep learning models, since the model parameters usually are finite during the training process. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "I_B_k9JNgaZ", "reviewer": "Reviewer_3g83", "summary": "The paper considers the stability of SGD under more general conditions noise models than have been considered before. The paper first  demonstrates three common ML optimization were the convergence of SGD has not been established. Then the paper explores the convergence of SGD under quite general condition, e.g., relaxing both the assumption of Lipschitz continuous gradients and bounded variance, which are usually critical in establishing convergence results for SGD. The results establish that under such general conditions, SGD either convergence to a stationary point or they diverge to infinity. Finally, the paper suggests a technical condition that, if met, ensures convergence to a stationary point.", "questions": "I am a bit surprise that the SGD will always converge to a unique stationary point (given that it does not diverge). If there is a connected set of stationary points, is it not possible that the iterates do not converge to any one of them but rather move around around that set? I mean, e.g., if F:R—>R, if [0,1] is the set of stationary points with F’(\\theta)=0 for all \\theta in [0,1], I could imagine that the iterates of SGD would after some time start to move around randomly in [0,1]. According to your results, this is not possible? or I am I misunderstanding something? ", "limitations": "No major limitations that I could see.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper is mostly well written. The paper is very upfront about the limitations of the work.  The mathematical results seem solid. The problem that is considered here is very general and it is indeed that it is possible to establish some convergence results in this case.\n\nWeaknesses: It is difficult to see how the results could be useful in practice, because it is impossible to say before running the algorithm whether it converges to stationary point or diverges. In fact, the only thing the results in the paper exclude is that the iterate move around without diverging and without settling on a stationary point. \n\nThere are no-indepth discussion about how the insights here could be used in practice. There are also no experimental results.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GevNcbgzdkv", "reviewer": "Reviewer_GcPb", "summary": "The paper presents an analysis of stochastic gradient descent for a wide range of applications by removing several usual but problematic assumptions from the analysis, replacing them with more acceptable alternatives. The issues with the current assumptions are illustrated for 3 common problems. Somewhat surprisingly, the authors are able to prove convergence and stability under the new, more permissive assumptions, though not a convergence rate (which wouldn't be possible under these assumptions anyway).", "questions": "1. For 2 counter-examples, a Ridge penalty is mentioned. Is it strictly necessary? If that's the case, then this weakens the argument that previous assumptions were not good enough.\n2. l92, where the authors claim that SGD basically always converges, seems somewhat surprising for deep learning practitioners. Can the authors shed some light as to why there seems to be a difference with practice (where SGD certainly can blow up)?", "limitations": "The authors mention the limitations of their work several times, notably making clear that the technical assumption that they require for their analysis cannot easily be interpreted. In that sense, I think limitations are honestly and properly addressed.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and easy to follow (at least superficially). The improved assumptions mean that the analysis is a lot more widely applicable than previous attempts, which relied on violated assumptions and were thus of less value. The results are original and significant, as are the new methods used to prove the theoretical results.\n\nI do have a few suggestions for improvements though:\n- when presenting the 'counter-examples' in the main text, all the authors say is that they have a result that shows there is a counter-example, without even referring to the Appendix for the actual example. I wonder if a simplified version of the counter-examples themselves wouldn't improve the main text, which currently reads as 'trust me on this'.\n- there is a lot of introductory space in the paper, and we only get to the meat of it on page ~6, with many results devolved to the Appendix. If the authors want a self-contained paper, then a journal format would be a better fit. For a conference paper, summarizing the first few pages more succinctly might read better.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept