From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descent
Authors: Christopher De Sa
Satyen Kale
Jason D. Lee
Ayush Sekhari
Karthik Sridharan
Venue: NeurIPS 2022 Accept (2022)
Keywords: Theory
Gradient flow
Stochastic Gradient Descent
Gradient Descent
SGD
Non-convex optimization
Lyapunov potentials

Abstract: Stochastic Gradient Descent (SGD) has been the method of choice for learning large-scale non-convex models. While a general analysis of when SGD works has been elusive,  there has been a lot of recent progress in understanding the convergence of Gradient Flow (GF) on the population loss, partly due to the simplicity that a continuous-time analysis buys us.  An overarching theme of our paper is providing general conditions under which SGD converges, assuming that GF on the population loss converges. Our main tool to establish this connection is a general \textit{converse Lyapunov} like theorem, which implies the existence of a Lyapunov potential under mild assumptions on the rates of convergence of GF. In fact, using these potentials, we show a one-to-one correspondence between rates of convergence of GF and geometrical properties of the underlying objective. When these potentials further satisfy certain self-bounding properties, we show that they can be used to provide a convergence guarantee for Gradient Descent (GD) and SGD (even when the GF path and GD/SGD paths are quite far apart). It turns out that these self-bounding assumptions are in a sense also necessary for GD/SGD to work. Using our framework, we provide a unified analysis for GD/SGD not only for classical settings like convex losses, or objectives that satisfy PL/ KL properties, but also for more complex problems including Phase Retrieval and Matrix sq-root, and extending the results in the recent work of Chatterjee 2022. 

From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descent
Ayush Sekhari as36630cornell.ed edu
Satyen Kale" eatyenkale@googleecoo com
Jason D. Lee'
jasomleesprinnceoon. edu
Chris De Sa² cdesaθcs, cornell.edi
Karthik Sridharan
ks9990cornel1.com
Abstract
Stochastic Gradient Descent (SGD) has been the method of choice for learning large-scale non-convex models. While a general analysis of when SGD works has been elusive, there has been lot of recent progress in understanding the convergence of Gradient Flow (GF) on the population loss, partly due to the simplicity that continuous-time analysis buys us. An overarching theme of our paper is providing general conditions under which SGD converges, assuming that GF the population loss converges. Our main tool establish this connection is a general converse Lyapınov like theorem, which implies the existence of a Lyapunov potential under mild assumptions on the rates of convergence of GF. In fact, using these potentials, we show one-to-one correspondence between rates of convergence of GF and geometrical properties of the underlying objective. When these potentials further satisfy certain self-bounding properties, we show that they can be used provide convergence guarantee for Gradient Descent (GD) and SGD (even when the paths of GF and GD/SGD are quite far apart). It turns out that these self-bounding assumptions are sense also necessary for GD/SGD to work. Using our framework, we provide unified analysis for GD/SGD not only for classical settings like convex losses, or objectives that satisfy Pt. Kt. properties, but also for more complex problems including Phase Retrieval and Matrix sq-root, and extending the results in the recent work of Chatterjee [13].
Introduction
Stochastic Gradient Descent (SGD) has been method of choice to train complex, large scale machine learning models. While understanding of SGD for convex objectives is comprehensive, a general understanding of when SGD works for non-convex models has been somewhat elusive. A large slew of properties like, convexity [47], onc-point-convexity [35], linearizability [32], KE [5, 40] and PL [33, 49, 41] properties, and more problem specific, tailored analysis of SGD and Gradient Descent (GD) for specific problem instances like matrix square-root problem, matrix completion [31], phase retrieval [11, 16, 53] and Dictionary learning [4] have been proposed. Recent success of SGD in over weerparameterized deep learning models have lead to the idea that SGD perhaps optimizes training objective with an implicit bias given by some implicit regularizer [24, 50, 29, 25, 26]. However, in [32] it is argued that there are wee-parameeeriiee models for which SGD works but no method that minimizes an implicit regularized training objective can learn successfully, thus showing that in general, the success of SGD cannot be explained by implicit regularization.
Google Research, NY
'Princeton University and Google Research, Princeton CComell University
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The goal of our paper is to provide unifying analysis for when SGD/GD works. More specifically, we do this via first showing that Gradient Flow (GF) works and then extending this analysis to SGD and GD. Gradient Flow (GF) can be seen as continuous time analogue of GD. In an idealized world, if one had access the population loss, turns out that convergence analysis for running gradient flow on population loss is somewhar hat simpler due to tools from continuous time analysis and PDEs. There has been several recent works [6. 14, 17] that have provided convergence analysis for GF even on non-convex objectives. The high level theme of this paper is to show that, under some mild/appropriate assumptions of population loss/objective and on the noise of gradient estimates, "if, GF converges on population loss, then SGD that uses one fresh example per iteration is successful at learning". Notice, that GF converging on population loss is a purely deterministic optimization problem. However, the fact that SGD works is learning result that implies a sample complexity bound.
There have been past works that have aimed at providing convergence analysis for Gradient Descent (GD) starting from Gradient Flow (GF). Typical route to obtain convergence analysis of GD starting from GF tries to think of GD updates as approximating GF path. Even with more sophisticated discretization schemes like Euler discretization, obtaining convergence for GD, starting from GF can be quite complex. In this paper, to show that when GF converges, SGD/GD also converges, we take different approach. key tool for proving convergence results for GF is by constructing so called Lyapunov potentials. In the literature of Ordinary Differential Equations (ODEs), when ODEs have regular enough convergence rates, one can show, so called converse Lyapunov theorems (see [34] for nice survey of classic results) that state that when ODE converges to stable solutions, there has to exist a corresponding Lyapunov potential. While convergence of GF in terms of sub-optimality is quite different from convergence in the ODE sense, in this paper, first prove converse Lyapunov style theorem for GF. Specifically, we show that when GF converges in terms of sub-optimality to global minimum, then there has to exist a corresponding Lyapunov potential and using such potential, the rates can be recovered. This result becomes a starting point for our analysis. We show that if this Lyapunov potential (obtained from the converse Lyapunov style theorem) satisfies certain extra self- bolfdboun regularity conditions, then one can show that GD and SGD algorithms converge in terms of sub-optimality when appropriate step sizes are used. Such convergence for SGD/GD happens even when the GF path and GD/SGD paths can be quite different.
We summarize our main contributions below:
We prove converse Lyapunov style theorem that shows that if gradient flow converges with rate specified by with an appropriate rate function, then there exists a corresponding Lyapunov potential that recovers this rate.
We provide geometric characterization for a given rate of convergence of gradient flow (ie. GF converges a particular rate if and only if a specific geometric condition on objective holds.)
There are problems for which GF converges at specific rate but GD can be arbitrarily slow to converge.
This motivates the necessity of additional conditions to ensure GD/SGD converges even when GF converges. We provide certain self- self-bounding regularity conditions on the Lyapunov potential, under which we show that GD converges. We also provide conditions on gradient estimate noise under which we show that SGD using these gradient estimates also converges.
We instantiate our results for problems such KL functions, matrix square-root and phase retrieval, amongst other applications.
2 Setup
Given a continuously differentiable function and non-negative function F Rd + R, our goal is to minimize F(w). Without any loss of generality, we assume that min, F()) algorithms are popular for such optimization tasks. In the following, we formally describe the Gradient Descent and Stochastic Gradient Descent algorithm, and their continuous time counterpart called gradient flow.
First-order
Gradient Descent (GD). Gradient descent the most popular iterative algorithm to minimize differentiable functions. Starting from an initial point wo GD on the function F(w) performs the

---

following update on every iteration:
- FVVF(ws)) (w:), W++1 + Wi -
where 7) denotes the step size. argmin,s7 ST F(we).
After T rounds, GD algorithm returns the point Br i=
Stochastic Gradient Descent (SGD). Stochastic gradient descent (SGD) has been the method of choice for optimizing complex convex and non-convex learning problems in practice. In the learning setting, F(w) corresponds to the unknown population loss and can be written as F(w) Ef-o[f(ws z)] where the expectation is taken with respect to samples 2 drawn from an unknown distribution D. SGD algorithm (mini-batch size 1) is iterative algorithm that at every round draws fresh sample žn from D to compute a stochastic unbiased estimate V V.[w;; zi) of the gradient v VF:w: and performs the update
W[+1 - wi 1 f(wz;
(2)
where v) is the step size and wi denotes the initial point. After rounds, SGD algorithm returns ÜT by sampling point uniformly at random from the set (wi...., Wr]
Gradient Flow (GF). Gradient flow from a point w/ is continuous time process (ue(1)ran that starts at w(0) wi and evolves as
dw -VF(w(()
dt
GF has been thought of as continuous time analogue of GD and is popularly used to understand behavior of gradient based optimization algorithms in the limit, primarily due to its simplicity and lack of step size.
Additional notation. For vector R., w[i] denotes its j-th coordinate and |w|| denotes its Euclidean norm. For any W1, E Rd, (W1, w2) denotes their inner product. For a matrix W, (WW and MM denotes its minimum singular value and spectral norm respectively. We define the set R* to contain all non-negative real numbers. We use 1a to denote d-dimensional vector of all 1s, and La to denote the identity matrix in d-dimensions. (O, (T,,))Ta) denotes d-dimensional Gaussian distribution with variance I² Ber(p) denotes the Bernoulli distribution with mean p.
For a function f IRd + R, we denote the p-th derivative at the point w by fP e Rd. We say that real valued f is monotonically increasing if f' 2 O, and monotonically decreas- ing if I' s O. The function f is said to be L-Lipschitz if [(wi) - f(w2) S L L|w) well for all wi, W2- For a set of initial points W, we denote clo(W) as its closure under GF, i.e. clo(W) (w' : w' is in GF path of some wp e W).
3 Gradient Flow, Potentials and Geometry
Lyapunov potentials are popular tool for understanding convergence GF [38, 55. At an intu- itive level, a Lyapunov potential is any non-negative function & that satisfies (w) ie. & decreases along the GF paths of F. This monotonicity property helps to show asymptotic convergence of GF to stable points of the underlying objective. In our work, we consider potential functions for which the rate of change (decrease) of the potential along the GF path related the suboptimality of the objective at that point.
s 0.
Definition (Admissible potentials). A differentiable potential function by : .RR H RR is admissible w.r.t F on a set W there exists monotonically increasing funcction g RR IK* with g(0) = such that for any W.4
((()))
Existence of potential functions of the above form be used to provide rates of convergence for GF as show in the following theorem.
Whenever not specified, we assume that g The function & denote the potential function b, with g(2
3

---

Theorem 1 (From potentials to gradient flow), Let W be a set of initial points that we want to consider. and let 4 g be an admissible potential w.r.t. F on the set clo(W). Then, for any initialization Wo W. the point w()) (t) on the GF path with w0) wp satisfies for any f. 2 0,
2 2 (wo)
g ((((())))
t
The idea that admissible potential functions imply convergence rates for GF has appeared in various
forms in the prior literature [7, 37, 55, 57]. As an example, consider the potential function Φb (v) ||u- w= I1/2. Notice that + is an admissible potential for any F that convex with g(z) 2. This because convexity implies that (4) is true for any Hence, using Theorem we get a || |w == 1 | rate of convergence for GF on any convex objective.
Our main result in this section is to establish a converse Lyapunov style theorem-that given rate, finds a potential function corresponding to that rate. We start by defining admissible rate functions. Definition 2 (Admissible rate functions). A function R: Rd x R + w.E.t F for any w e R.d
IT is admissible rate function
(a) R(w,t) t) is non -on-incceasing function of such that lim R(w, () O.
(b) R satisfies the relation: [ (8R( (V R( (FF,,,, dt 2 0.
(F(w))
0t
Remark 1. In order to simplify the task of checking whether a given rate is admissible, note that Definition 2-(b) is satisfied whenever the condition
OR(w,t) + (FF()))))F(())) 00 Øt
holds for every w. as t. - Many rate functions, e.g. R(w,t) F(w)e** and F being KI., in fact satisfy this condition for every w. t, 2 O.
Furthermore, also note that Definition 2-(b) is satisfied whenever the rate function is such that R(w(s), t) $ ([(.s++) f) for all s, 0 and w e IR",, which may be an easier to check condition, e.g. when Ri( w. t) = e
We utilize admissible rate functions to characterize behavior of GF on F. Before we proceed, let us motivate the two properties above. Property (a) is natural for any rate function and captures the fact that running GF for more time leads to better guarantees. Property (b). while seeming a bit mysterious, characterizes the compatibility of the rate function w.r.t. gradient flow dynamics. For interpretation consider the relaxed version given in Remark which implies property-(b). Here, the condition that R(w(s),)) R(w, s+1) for all 8, 1 2 and RRd simply captures the fact that having additional information about the GF path should only improve the rate. Note that R(w(O), 8 + i) an
corresponds to upper bound on the sub-optimality at w(s t) and R(w(s),) f) corresponds upper bound on the same quantity but with the additional information that w(s is a point on the GF path. We remark that for any rate function R. is easy construct new rate function R that always satisfies this condition (hence, property (b)) by defining R(w, t) min R(w', &+ s) where w' any point such that the point lies on the GF path from w' at time Furthermore, the function R(w, t) (t)(t) is always an admissible rate function. All the rate functions appearing in this paper satisfy both properties (a) and (b).
Our next result shows that admissible rate functions for GF can be used to construction admissible potentials w.r.t. F.
Theorem 2 (From gradient flow to potentials). Let W g Rd be any set of initial points that we want to consider, and R be an admissible rate function w.t.. all GF paths originating from any point in W. Further, suppose that for any e W, the point w() ()) on the GF path satisfies F(w(t)) & R(wo, t), then the function 42 defined as
vy(w)= f. 9(R(w,t) dt
(5)
is an admissible potential w.r.. F on the set clo(W)).for for any differentiable and monotonically increus- ing function g IR. +s TR+ that satisfies J: g( R( w. 1)) di < oo and f g' (R(w, (w,)))]V R(w,)) ()]l dt oo for every clo(W).

---

As an illustration on how to apply Theorem 2, assume that for F the rate for Gs R(w,t) = F( For instance, we already know that such a rate holds when F Fis PL. For this rate, by choosing g() 2, we get that the function Φ ( = f1- F F(w)e * dt F(w) is an admissible potential w.r.t. F. We
provide more examples in Section
Theorem and Theorem 2 are, in a sense, converse of each other. Theorem shows that the existence of an admissible potential function implies a rate of convergence for GF. On the other hand, Theorem shows how to construct admissible potentials starting from the fact that GF has a rate. One might wonder whether there always exist Lyapunov function, more specifically a g function above, such that the rate implied by the constructed potential in Theorem I matches the rate that we started with for Theorem 2, i.e. R(w,t) t) xs g (f)(w//t) We answer this in the positive for rate functions that are of the product form.
Corollary 1. Let = R& be any set of initial points that want to consider, and R be admissible rate function w.r.t. all GF paths originating from from points in W. Additionally, suppose R has the product form R(w, 1) h())r(() where h is difserentiable and is non-increasing function that satisfies r(t) S X/e (1) max for any L R (where X is a universal constant). Furthermore, suppose that for any wo E W, the point w() on the GF path satisfies F(w(l)) I R( R(wn, 1). Then, there exists a monotonically increasing function g IRR +s TK*t such that the potential Φb (w) constructed in Theorem 2 using 9. when plugged in Theorem 1, implies that GF has the rate
F(w(t)) S max
weW
for any initialization w00) E W.
3.1 Geometric Interpretation
The definition of an admissible potential comes with a geometric condition on the function F given in (4). Since Theorem 2 constructs admissible potentials, when a rate R(w, t) holds for GF it suggests that the geometric property in (4) holds for the objective function F. As example, say GF on F
satisfies the rate R(w, ((w, t) = F(w)e=". From Theorem 2, we note that $ (,()) = F(w) is an admissible
potential w.r.t F with g( 2)) z. This implies the geometric property
(VF(w).VF(u)) 2 F(w)
(6)
holds for F whenever GF has rate R(w,1) F(w)e=* On the other, we know that whenever
(6) holds the function ((w)= F(w) satisfies (4) and is thus an admissible potential for F (with
g(2) = 2), and hence Theorem implics the rate of F(w)/t, which is equivalent to the rate F())-* (c.f. Lemma 6). This implies an equivalence between the rates R(w,t) t) F(w)e" and the geometric property (6). We formalize this in the following.
Proposition 1. The following two properties are equivalent:
(a) For any w(0) e Rd and t 2 0, GF has the rate F(w(t)) & F(w(O))e
(b) F(w) satisfies the for any 2 O. Theorem 2 implies (b) and yields the potential function 4(w) F(w).
(PL) property i.e. XF(w) (VF(w))
similar equivalence also holds for the more general class of KE functions. We defer this result to Proposition 3 in Section E. In the following, we show a correspondence between the rate R(w,t) t)- [0)()) 1 [=]]=(t)==' and linearizability- a condition that is weaker than convexity but 2t
is sufficient for the corresponding rate of convergence for GF. Proposition 2. The following two properties are equivalent:
(a) For any w(0) e Rd and t 2 O, GF has the admissible rate F(w (w((t)) s A [==(0)=w" "0 (-] (b) F(w) is linearizable w.r.t. w" iee. F(w) S X(VF(W)) w w))
21
for any X 120
More generally, the equivalence between GF rates and the corresponding geometry on F can be characterized as follows.
Remark 2. GF on enjoys the admissible rate Rww,) 1) (w)(())) and only if F has the geometric property (V),(w), FF)))) 2 ((F(w))
5

---

4 Stochastic Gradient Descent and Gradient Descent
GD can be thought of an approximate discretization of gradient flow. Thus, for problems where GF converges with a given rate R. one may try to get convergence guarantees for GD from an initial point wp by bounding the distance between the GD and GF trajectories starting from wy. This is exactly the approach taken in prior works [27, 39, 56, 52, 62, 21]. However, coming up with non-vacuous bounds on the distance between corresponding GF and GD iterated often quite challenging and requires much stronger assumptions on the underlying objective. In fact there are cases where both GF and GD converge to the same global minimum but their paths can be quite far away from each other. We take a different approach for proving convergence of GD/SGD which directly relies on the properties of corresponding potential for F. In the following theorem, we note that further assumption on top of the premise that GF has rate are required, to even hope that GD succeeds.
Theorem 3. For any integer To > O, there exists a continuously difserentiable convex function F for which min F(w)= O and w² O is the unique minimizer, such that:
(a) (ww) = || 2 is an admissible potential for F. Thus, Theorem I implies that for any initial point Wo- the point w(t) on its GF path satisfies F ((w(t))= S
1
2
(b) There exists an initial point wo with ||roo|| s 1 and F(wo) s 2 such that GD fails to find an 1/10-suboptimal solution for any step size ii within 1 To steps.
Before giving our exact assumptions and the convergence bounds, we provide the intuition behind how admissible potentials can be used for analyzing GD (or SGD). Let the sequence of iterates generated by GD algorithm be given by {we) 120 (=) and & be an admissible potential w.r.t. F. For any time the second-order Taylor's expansion of the potential & implies that
@ 1w s & (ww)) + (v w wi) + (W++1 - we " ( we)
- $ Φ (wx) (Vv((w))) (w)), (F(w)) + - (
where Wy = =Bwe + (1 - 3) Wt+1 for some 3 [0, 1]. and the second line follows by plugging the GD update w Wt 1/ w:). Rearranging the terms, we get that
(V < 4 ((w,) #(w++))
1)
The key idea that enables us to get performance guarantees for GD is that the linear term in the left hand side above upper bounds the suboptimality of F at the point we since an admissible potential w.r.t. F. In particular, the condition (4) implies that
(v V F(w.)) ()))) s F(w,).
Using the above relation in (7), telescoping from 0 to T 1, and dividing by T, we get that
((F(w))) S ((w)) ((wr) T
T-1 Σ
7 T
T-1
Σ
(8)
r/T
Thus, we can bound the expected suboptimality of the point w Uniform ((w,, .... wr-1)) returned by the GD algorithm after steps, whenever the second order term in the bound (8) is well behaved. For example, if (V (w:))) ( s K for any wt, We-1 and Wr we immediately get that
1 T-1 T Σ g(F(w))) (wwo) - ((WT) + +nk = of 1 nT
for == O(IVTT). While the above holds for a very simplified setup, the intuition can be extended to more general cases well. Below present two regularity conditions that are sufficient to show convergence of GD.
Assumption 1. There exists a monotonically increasing function vb RR RR such that [V (F(()) for any point w W.
Assumption The potential function is second-order differentiable, and there exists a monotoni- cally increasing function p: R² + Rt such that (+ S p(((w) any point E W.

---

We will refer to the above conditions on F and o as self-bounding regularity conditions. The following theorem provides convergence guarantees for GD when an admissible potential exists and the above assumptions are satisfies.
Theorem 4 (GD convergence guarantee). Let b be an admissible potential w.E.. F. Assume that F satisfies Assumption I and &g satisfies Assumption 2. Then, for any T2 0 and setting 1 appropriately, the point @r returned by GD algorithm has the convergence guarantee?
g( ((F(Tr) - O (
Furthermore, if the function X(z) appropriate choice of 7)
v(x)
is monotonically increasing in 2, then for different {()
(10)
Let us consider an example. Suppose that gradient flow on F achieves the admissible rate R(w,t) = (Iw- w² w=1 (t) - w= 12)) This implies that F is linearizable (Proposition 2), and thus 2 (w) = w - w" 1/3/2 is an admissible potential for F with g(2) as it clearly satisfies (4). However, as we saw in Theorem 3 just existence of such a rate function does not imply the GD will succeed and we need to make further assumptions. Notice that in this case o (w) satisfies Assumption 2 with p(2) = 1. If we further assume that F L-Lipschitz, then Assumption is satisfied with (=()) = L Hence, applying Theorem 4 for this setting, we get that GD has convergence rate F(@r) = O - w0 \/V)).. Instead if F was H H-smooth, Assumption 1 is satisfied with +b=)) = 2 z and (>))/(=)) 4// is a monotonically increasing function and thus using (10), we get that GD has the convergence rate F (T) O ((H]e w w" 1² /T). Notice that both of these rates are optimal for GD under the Lipschitz/Smoothness assumptions on F, and the fact that F is linearizable [47]. On similar lines, using the rates for GF convergence on PI.KK. functions, we can also recover optimal convergence rates for GD under appropriate smoothness assumptions on F.
We next consider the convergence of SGD algorithm. Recall that at the iterate w,, SGD performs the updated using V V (Ww, 2t), a stochastic and unbiased estimate of VF(w). Of course, unless one has some form of control over the distribution of V V[(,, one cannot hope to prove any convergence guarantees of SGD. To this end, we make the following regularity assumption on the noise in V (w, 21) while estimating FFW).. Assumption 3 (Noise regularity). There exists a monotonically increasing function X =R= R+ such that for any point w, the gradient estimate V ff 2) satisfies
Pr(IVV (FF (2 2 x(F(w))) SE
Assumption 3 is quite general, and can be specialized by appropriately setting the function x model various stochastic optimization problem settings observed in practice. For example, the classical stochastic optimization setting in which V f(w;;) variable with mean 0 and variance o² is captured by the above assumption when x(=) o² [46]. However, it turns out that for many interesting ML problems, the noise typically scales with the function value [58, 59].
F(w) + Et where & is sub-Gaussian random
Theorem (SGD convergence guarantee). Let 2y be an admissible potential w.r.t F. Assume that F satisfies Assumption 1, 2 satisfies Assumption 2 and the stochastic gradient estimates V ff(ws, satisfy Assumption 3. Then, for any T 2 and setting 1) appropriately, the point Tep returned by SGD algorithu has the convergence guarantee'
((F()))==
with probability at least 0.7 over the randomization of the algorithm and stochastic gradients.
Remark 3. In most classic settings, one expects a 1/ VT rate for SGD [10]. However, in cases where by is an admissible potential and g(2) = =(2), Theorem 5 seems suggest a g (1/V/T) rate of convergence which is faster than 1/VT. This is where the self- holf-bounding regularity conditions play important role. As example for PL style rates, one show that F F(w)² is admissible potential with g(2) 2" for any p. However, the self-re regularguy conditions are not satisfied unless
p 2 1. Setting = 1 recovers the 1/VT rate of SGD for PL functions which is optimal [1].
'The O(-) notation here hides initialization and problem dependent constants fully specified in the Appendix.
7

---

Examples: From Gradient Flow to Gradient Descent
So far, we discussed classical examples like Pt. functions, convex functions, etc. At high level, in order to show convergence of SGD for these problems, we first establish an admissible rate of convergence for GF, which implies an admissible potential that used show convergence of SGD, We next extend this approach for other more complex stochastic non-convex optimization problems.
5.1 Phase retrieval
In the phase retrieval problem [11, 16, 53], we wish to reconstruct hidden vector w" e Rd with | = 1 using phaseless observations S = {(a).Hs) V))) of the form V/ = (aj, w*)² where aj I)) The classical approach to recover w" is by using the per-sample loss function (w:; (aj, (j) = ((a)w) w)² - v3)² for which the corresponding population loss is given by
(w) = (w; (a.y))] Ba-N((.1a) ((a"))²= (a" w )
w)²
(11)
For is non-convex, and has stationary points (and local minima) that do not correspond to the global minima. In the following, we provide convergence guarantees for GD algorithm Fpr, and SGD algorithms that computes stochastic gradient estimates using S. We first note that Fpr satisfies self-bounding regularity conditions, and GF has rate of convergence global minimizers of Fpr.
Lemma 1. Fpr satisfies Assumption 1. Furthermore, for any initial point wa, the point w(t) on its gradient flow path satisfies
Prr (1) s min (ur( Fpr (wo)e
(wp(((()).))
Furthermore, the function Rer above is an admissible rate of convergence w.r.f. Fpr
The above rate follows from independently analyzing the parallel and perpendicular components (w,w") and |w| (w,,"" respectively. Our main tool for getting the convergence guarantee for GD/ SGD is to utilize Theorem 2 to get an admissible potential w.r.t. Fpe. which can be plugged in Theorem and to get the corresponding rates.
Theorem 6. Consider the phase retrieval objective For given in (11). For any initial point wa and T21 1, setting appropriately.
(a) The point Th returned by GD starting from wo satisfies For For(#r) ( (o))) for all T to, where to a we dependent constant.
(b) The point Tr returned by SGD starting from we and using stochastic gradient estimates for which Assumption 3 holds, satisfies Fpr Ō( /T
with probability at least 0.7.
The O-) notation above hides wo dependent constants which we specify in the Appendix. Our rate for GD above matches the best known result in the literature in terms the dependence on T [16]. To the best of our knowledge, ours is also the first convergence analysis of SGD under arbitrary noise conditions satisfying Assumption While this rate is optimal under certain noise conditions, e-g. when x(=) = o², further improvements are possible when is favorable. For example, suppose the stochastic gradient estimates were computed using samples from by taking a fresh sample for each estimate, i.e. fw: (a, v)) ) 4((a w)² y) w) w. In this case, the stochastic gradient satisfy Assumption with x(2) min( VE,c) where e is a universal constant (c.f. Candes et al. [1 I, Lemma 7.4, 7.7]). While, framework implies that this SGD algorithm (computing estimates using samples) converges the rate of 1/VT, this rate be improved further [16], and we defer the refined analysis for future research.
5.2 Initialization specific rates
In many applications, GF is only known to converge from nice enough initial points that satisfy certain properties. In this section, we extend show how to use our tools for establishing convergence of GD/SGD for such problems, and consider matrix square root an example. We first provide the following general utility lemma that shows how to construct admissible potentials when the rate for GF from wo holds only when We satisfies certain property characterized by ((wp) 0.

---

Lemma 2. Let h h + 1 [0.1] be a continuously differentiable function, and suppose that any point w for which h(w)> >0, GF with w(0)= = w has rate F(w(t)) < R( w. t) where R(w,-) is monotonically decreasing function in I. Furthermore, suppose that F(w) & R(w, 0), F satisfies Assumption 1, R(w, h(w) (v) (t) an admissible rate function w.r.t F, and any w,
(a) the function r(w) = (axl s x(((w)) where X is positive, monotonically increas- ing function.
R(w,) dt is continuously differentiable, and
(b)
& ([(w)) where π is a positive, monotonically increasing func-
tion.
(c) (h(w) - h( ))2² 2 (w)) where is positive, monotonically increasing function with the property that kp(z) S (k2)) ) for any 2 1.
Then, the function & (g(w) ((w)/h(w) is an admissible potential w.r.t F with g(2) 2, and satisfies the self-bounding regularity condition in Assumption 2.
5.2.1 Matrix square root
In the matrix square root problem [19, 28), given a positive definite and symmetric matrix M e gaxd with oa(M) > 0, and wish to find a symmetric W E Raddd that minimizes the objective
Fms (W) M| - 1
(12)
Fis non-convex in W, and has spurious stationary points. In the following, we provide convergence guarantees for GD/SGD algorithm Fus. We first note that Fins satisfies self- boffdboundig regularity conditions, and GF on Fiss converges to the global minimizer when the initial point Wy satisfies additional assumptions. We capture these initial conditions using the function hms defined
Ams (W) ( a)
(13)
where the function d(Z) -1 log(tr(e->2) + e- e-16a7), miin ( (M)/1600, 7 =loo(d++ 1)/a, and
a denotes a smoothened version of the indicator function given by d(z) (f 2 s 0, 2 2 0f 2 2 - -22²² 1 1 if o S 2 S and 1 if a $ 2}.
Lemma 3. Fis satisfies Assumption 1. Furthermore, for any initial point Wo which h (W)) O. the point W (t) on its GF path satisfies
Fin (W)()) Funs (Wo) exp(-16at) Raus (W)
where a miin
Ominn (M)) 7 = log(d+ + 1)/a a and the function hms is defined in (13).
The above rate follows from directly solving the PDE associated with the gradient flow on the underlying objective. Lemma 3 provides conditions on Wo under which the GF path converges with the rate function Rmss- Our main tool for showing the convergence of GD/ / SGD is by using Lemma 2 to get admissible potentials. Note that the function his takes values [0. 1], is continuously differentiable, and as we show in the appendix satisfies all the required self-bounding regularity conditions in Lemma Thus, Lemma 2 provides an admissible potential w.r.t. Fpz which can be used to get the following rates.
Theorem 7. Consider the matrix square root objective Fms given in (12). For any K. > 0, initial point Wo for which hms (Wu) and setting 7) appropriately.
(a) The point WT returned by GD starting from Wo satisfies Fms (ins(W)) O ((T))))))) for all T lo, where la is wp dependent constant.
(
(b) The point Wy returned by SGD starting from Wo and using stochastic gradient estimates for
which Assumption 3 holds, satisfies Fma Fms(WT) = Ō( with probability at least 0.7.
The O()) notation above hides Wo dependent constants which we specify in the Appendix. Our rate for GD above matches the best known result in the literature in terms of the dependence on T

---

[28]. Ours is also the first convergence analysis of SGD under arbitrary noise conditions satisfying Assumption Note that the classical stochastic optimization setting which V fms (w: 2) 2W22_ M)W 2W 2WW22 - M) + e where E, is a sub-Gaussian random variable with mean 0 and variance x² satisfies Assumption with X(=) = o², and as a result of Theorem 7, we get that SGD converges at the rate of 1/ 1/VT. To the best of our knowledge, convergence of SGD in the stochastic optimization setting for matrix square root problem was not known before.
6 Conclusion
In this paper, we provide a new framework for establishing performance guarantees for SGD in stochastic non-convex optimization. We introduce admissible potentials, and use them get finite- time convergence guarantees for SGD. We also provide a method for constructing such admissible potentials using the rate function with which gradient flow converges on the underlying non-convex objective, provided that this rate function satisfies additional admissibility conditions. Thus, infor- mally speaking, our results suggest that whenever gradient flow has an admissible rate of convergence and additional regularity conditions hold, SGD succeeds in minimizing the underlying non-convex objective (with the rate given in Theorem 5). We discuss some extensions and open problems below:
Contrary to the prior approaches [27, 39, 56, 52, 62, 21I, our convergence proof for SGD does not proceed by showing that the corresponding paths of SGD and gradient flow dynamics are point-wise close to each other. In fact, the example in Theorem 3 suggests that this may not be true even for convex functions, since for that example, gradient flow converges to minimizers but SGD diverges away from good solution. Our key technique is to use admissible potentials, that satisfy (4) w.r.t. gradient flow dynamics, to analyze discrete time algorithms like SGD.
Our framework is motivated by Lyapunov analysis of dynamical systems [12, 15, 18. 57]. The property (4) in fact implies that any admissible potential is a Lyapunov potential w.r.t. the gradient flow dynamics on the underlying non-convex loss. would be interesting to explore if techniques from the Lyapunov analysis of dynamical systems can be used to improve our rates further, or to relax various regularity and admissibility assumptions that we assume for our results. In particular, it would be interesting to explore how to extend our framework for non-smooth non-convex stochastic optimization.
While we restricted ourselves to GD in the paper, our framework can be easily extended to analyze mirror descent algorithms (to get improved dependence on the problem geometry), by modifying the admissibility condition (4) to hold w.r.t. gradient flow dynamics in the dual space (mirror space). Furthermore, we can also extend our framework to other first-order algorithms like acceleration, momentum, etc., by changing (4) to hold w.r.t. the corresponding continuous time dynamics for these algorithms [36, 52, 48].
Theorem gives a construction of admissible potentials using the rate function R for gradient flow on the underlying objective. However, the convergence bound for SGD in Theorem 5 holds only when this constructed potential satisfies additional self-bounded regularity conditions in As- sumption 2. In order to get an end-to-end result, it would be interesting to explore what structural conditions on the rate function R implies that the obtained potential satisfies Assumption 2.
In the paper, we demonstrate the generality of our framework by considering various non-convex stochastic optimization problems including PL/KE functions, phase retrieval and matrix square root, and show that admissible rate functions and the corresponding admissible potentials can be easily obtained by explicitly solving the partial differential equation associated with gradient flow; hence getting rates of convergence for SGD for these problems. Looking forward, it would be interesting to apply our framework for other non-convex stochastic optimization problems appearing in machine learning, and in particular deep learning.
Acknowledgements
AS thanks Robert D. Kleinberg for useful discussions. KS acknowledges support from NSF CAREER Award 7750555. JDL acknowledges support of the ARO under MURI Award W91 INF-1--1-0304, the Sloan Research Fellowship, NSF CCF 2002272, NSF IIS 2107304, NSF CIF 2212262, ONR Young Investigator Award, and NSF CAREER Award 2144994. CD acknowledges support from NSF CAREER Award 2046760.
10

---

References
[1] A. Agarwal, M. J. Wainwright, P. Bartlett and P. Ravikumar. Information-theorel lower bounds the oracle complexity of convex optimization. Advances in Neural Information Processing Systems, 22, 2009.
[2] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. J. Mach. Learn. Res., 22(98):1-76, 2021.
[3] Z. Allen-Zhu, Y. Li, and Z. Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
[4] S. Arora, R. Ge, T. Ma, and A. Moitra. Simple, efficient, and neural algorithms for sparse coding. In Grünwald, E. Hazan, and S. Kale, editors, Proceedings The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, 2015.
[5] H. Attouch, J. Bolte, P. Redont, and A. Soubeyran. Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the surdyya-Lojasiewiezz inequality. Mathematics of Operations Research, 35(2):438-455 2010. ISSN 0364765X. 15265471.
[6] S. Azulay, E. Moroshko, M. S. Nacson, B. E. Woodworth, N. Srebro, A. Globerson, and D. Soudry. On the implicit bias of initialization shape: Beyond infinitesimal mirror descent. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 368-477 PMLR, 2021.
[7] N. Bansal and A. Gupta. Potential-function proofs for first-order methods. arXiv preprint 12.4581, 2017.
[8] Y. Bi, H. Zhang. and Lavaei. Local and global linear convergence of general low-rank matrix recovery problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 10129-10137, 2022.
[9] Bu, A. Meshahi, M. Fazel, and Mesbahi. Lqr through the lens of first order methods: Discrete-time case. arXiv preprint arXiv: 1907.08921, 2019.
[10] S. Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends Machine Learning, 8(3-4)2231-357 2015.
[11] E. J. Candes, X. Li, and M. Soltanolkotabi. Phase retrieval via wirtinger flow: Theory and algorithms. IEEE Transactions on Information Theory, (1(4):1985-200) 2015.
[12] M. Cencini and F. Ginelli. Lyapunov analysis: from dynamical systems theory applications. Journal of Physics Mathematical and Theoretical, 46(25):250301, 2013.
[13] S. Chatterjee. Convergence of gradient descent for deep neural networks. arXiv preprint arXiv:2203. /6462, 2022.
[14] N. S. Chatterji, P. M. Long, and P. L. Bartlett. The interplay between implicit bias and benign overfitting in two-layer linear networks. CoRR, abs/2 1489, 2021.
[15] V. Chellaboina and W. M. Haddad. Nonlinear dynamical systems and control: A Lyapunov- based approach. Princeton University Press, 2008.
[16] Y. Chen, Y. Chi, J. Fan, and C. Ma. Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval. Mathematical Programming, 176(1):5-37, 2019.
[17] L. Chizat and Bach. A note on lazy training in supervised differentiable programming. 2018.
URL http: /tttp://arxxiee /ttp//axvvvo./ wwarxiivv.rr/.ooe ht//a//s//// /etp///1....000 1812.07956. cite arxiv: 881 812.07956.
[18] F. Clarke. Lyapunov functions and feedback in nonlinear control. In Optimal control, stabiliza- tion and nonsmooth analysis, pages 267-282. Springer, 2004.
[19] C. De Sa, C. Re, and K. Olukotun. Global convergence of stochastic gradient descent for some non-convex matrix problems. In International conference machine learning, pages 2332-2341. PMLR, 2015.
[20] S. Du, X. Zhai, Poczos, and A. Singh. Gradient descent provably optimizes over- parameterized neural networks. arXiv preprint arXiw:1810.02054,, 2018.
11

---

[21] O. Elkabetz and N. Cohen. Continuous vs. discrete optimization of deep neural networks. Advances in Neural Information Processing Systems, 34, 2021.
[22] Y. Fang, K. A. Loparo, and X. Feng. Inequalities for the trace of matrix product. IEEE Transactions on Automatic Control, 39(12):2489 1994.
[23] I. Fatkhullin and B. Polyak. Optimizing static linear feedback: Gradient method. SIAM Journal on Control and Optimization, 5955):8887-391 2021.
[24] S. Gunasekar, J. Lee, D. Soudry, and N. Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pages 1832-1841. PMLR, 2018.
[25] S. Gunasekar, J. Lee, D. Soudry, and N. Srebro. Implicit bias of gradient descent linear convolutional networks. arXiv preprint 18060006006 2018.
[26] S. Gunasckar, B. Woodworth, S. Bhojanapalli, B. Neyshabur, and N. Srebro. Implicit regular- ization in matrix factorization. In 2018 Information Theory and Applications Workshop (ITA), pages 1-10. IEEE, 2018.
[27] S. Gunasekar, B. Woodworth, and N. Srebro. Mirrorless mirror descent: A natural derivation of mirror descent. In International Conference on Artificial Intelligence and Statistics, pages PMLR, 2021.
[28] Jain, C. Jin, S. Kakade, and P. Netrapalli. Global convergence of non-convex gradient descent for computing matrix squareroot. In Artificial Intelligence and Statistics, pages 479-488. PMLR, 2017.
[29] Z. Ji and M. Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint M.Kiv:8803.072
2018.
[30] C. Jin, S. M. Kakade, and P. Netrapalli. Provable efficient online matrix completion via non- convex stochastic gradient descent. Advances in Neural Information Processing Systems, 29, 2016.
[31] C. Jin, S. M. Kakade, and P. Netrapalli. Provable efficient online matrix completion via non-convex stochastic gradient descent. In NIPS, 2016.
[32] S. Kale, A. Sekhari, and K. Sridharan. SGD:
the role of implicit regularization, batch-size and multiple-epochs. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 27422-27433, 2021.
[33] H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal- gradient methods under the pojyak-tojasiewiez condition. In European Conference on Ma- chine Learning and Knowledge Discovery in Databases Volume 9851, ECML PKDD 2016, page 795-811, Berlin, Heidelberg, 2016. Springer- Verlag. ISBN 9783319461274
doi:
10. 0117999788--11-46122 1_500
[34] C. M. Kellett. Classical converse theorems in lyapunov's second method. Discrete and Continuous Dynamical Systems B, 20(8):2333-238 2015.
[35] R. Kleinberg, Y. Li, and Y. Yuan. An alternative view: When does sgd escape local minima? In J. G. Dy and A. Krause, editors, ICML, volume 80 of Proceedings of Machine Learning Research, pages 2703-2712. PMLR, 2018.
[36] N. B. Kovachki and A. M. Stuart. Continuous time analysis of momentum methods. Journal of Machine Learning Research, 22(17): 2021.
[37] W. Krichene. Continuous and discrete dynamics for online learning and convex optimization.
Ph. D. Dissertation, 2016.
[38] W. Krichene. A Lyapunov Approach to Accelerated First-Order Optimization In Continuous and Discrete Time. PhD thesis, University of California, Berkeley, 2016.
[39] W. Krichene, A. Bayen, and L.. Bartlett. Accelerated mirror descent in continuous and discrete time. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[40] K. Kurdyka. On gradients of functions definable in o-minimal structures. Annales de l'institut Fourier, 48(3) 48(3):769-783 1998.
12

---

[41] S. Lojasiewizzz A topologiaal property of real analytic subsets. Coll. du CNRS, Les équations anx dérivées partielles, 117(87-89)22, 1963.
[42] C. C.Ma, K. Wang, Y. Chi, and Y. Chen. Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference Machine Learning, pages 3345-3354. PMLR, 2018.
[43] J. Mei, C. Xiao, C. Szepesvari, and D. Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pages 6820-6829.
PMLR, 2020.
[44] J. Mei, Y. Gao, B. Dai, C. Szepesvari, and D. Schuurmans. Leveraging non con-uniformity in first-order non-convex optimization. In International Conference on Machine Learning, pages 7555-7564. PMLR, 2021.
[45] H. Mohammadi, A. 7are, M. Soltanolkotabi, and M. R. Jovanović. Global exponential conver- gence of gradient methods over the nonconvex landscape of the linear quadratic regulator. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 7474-7479. IEEE, 2019.
[46] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Stochastic approximation approach to stochastic programming. In SIAM J. Optim. Citeseer.
[47] A. S. Nemirovskij and D. B. Yudin. Problem complexity and method efficiency in optimization. 1983.
[48] A. Orvicto and A. Lucchi. Continuous-time models for stochastic optimization algorithms. Advances in Neural Information Processing Systems, 32, 2019.
[49] B. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physics, 3(4):864-878, 1963. ISSN 0041-5553.
[50] D. Soudry, F. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19(1):2822-2878 2018.
[51] N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low noise and fast rates. In J. Lafferty, C. Williams, J. Sahawe-Taylor R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23, Curran Associates, Inc., 2010.
[52] W. Su, S. Boyd, and E. Candes. A differential equation for modeling nesterov's 's accelerated gradient method: theory and insights. Advances in neural information processing systems, 27, 2014.
[53] Y. S. Tan and R. Vershynin. Online stochastic gradient descent with arbitrary initialization solves non-smooth, non-convex phase retrieval. arXiv preprint arXiv: 1et::990...... 2019.
[54] G. Vardi and O. Shamir. Implicit regularization in relu networks with the square loss. In Conference on Learning Theory, pages 4224-4258, PMLR, 2021.
[55] A. Wilson. Lyapunov arguments in optimization. University of California, Berkeley, 2018.
[56] A. C. Wilson, B. Recht, and M. I. Jordan. A lyapumov analysis of accelerated methods in optimization. Journal of Machine Learning Research, 22(113):11222 2021.
[57] A. C. Wilson, Recht, and M. I. Jordan. A Iyapunov analysis of accelerated methods in optimization. Journal of Machine Learning Research, 22(113):1-34, 2021.
[58] S. Wojtowytsch. Stochastic gradient descent with noise of machine learning type. part i: Discrete time analysis. arXiv preprint arXiv:2/05.01650) 2021.
[59] S. Wojtowytsch. Stochastic gradient descent with noise of machine learning type. part ii: Continuous time analysis. arXiv preprini
2021.
[60] R. Yuan, R. M. Gower, and A. Lazaric. general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statisties, pages 3332-3384 PMLR, 2022.
[61] J. Zeng, S. Ouyang, T. T.-K. Lau, S. Lin, and Y. Yao. Global convergence in deep learning with variable splitting via the 2018.
property. arXiv preprint arXiv:1803.0022) 9,
[62] P. Zhang, A. Orvieto, H. Daneshmand, T. Hofmann, and R. S. Smith. Revisiting the role of euler numerical integration on acceleration and stability in convex optimization. In International Conference Artificial Intelligence and Statistics, pages 3979-3987. PMLR, 2021.
13

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], , or [N/A] - You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [N/A]
Did you include the license to the code and datasets? [N/A] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below,
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We do not foresee any negative societal impacts of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rre're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "xzAdn926QS", "reviewer": "Reviewer_T8uY", "summary": "This paper aims at providing conditions for the convergence of GD/SGD schemes when there is a rate of convergence for Gradient Flow on population loss, and this is done by deriving a potential function and checking the geometric property. Also this potential should satisfy certain properties, called self-bounding regularity conditions, in order to give us the desired convergence for GD/SGD methods. Authors verify that this is indeed applicable not only to convex and PL functions, but also to non-convex problems.", "questions": "grammatical and mathematical typos:\n\nline 108 derivative. line 112 extra \"in\". line 121 shown. line 144 such that. line 215, $F(w(t))\\leq\\frac{\\lVert w_0 \\rVert^2}{2t}$. line 226, satisfied. lines 587, 592, it should be $\\Phi(w_0)$. line 611, the negative signs in lines 3-4-5 should be removed, as $|r'(z)|=-r'(z)$. line 625, extra \"from\", also $R(w,t)=F(w)e^{-\\lambda t}$. line 630, $\\frac{\\lVert \\nabla F(w) \\rVert ^2}{\\lambda}$. line 634, 3rd line, missing \"=\". line 643, it should be $\\lVert u \\rVert_{3/2}$. line 651, $F(w(T)) - F^*\\leq \\frac{\\Phi(w_0)}{T}\\leq \\frac{\\lVert w_0 \\rVert ^2}{2T}$. line 657, \"many ensure\". line 662, proof. line 700, extra \"defined\". line 705, $\\theta''(z)=\\frac{-\\rho'(z)}{\\rho(z)^2}$. line 712, $u=-\\frac{\\nabla \\Phi(w)}{\\rho(\\Phi(w))}$. line 732, since \"$\\theta$\" is \"monotonic\", this implies that \"$\\Phi(w_{t+1})\\leq \\Phi(w_t)$\". \n\nin line 752 equation (33), 2nd line is wrong. we don't know if $F(w_t)\\leq F(w_0)$. Instead you should use $F(w_t) \\leq \\zeta(\\Phi(w_t)) \\leq \\zeta(\\Phi(w_0))$. However final conclusion of equation (34) is correct.\n\nline 772, $\\psi(F(w))$ instead of $\\lVert \\nabla F(w) \\rVert^2$. line 783, $\\kappa > 1 $. line 792, 3rd line is duplicate. line 796 and afterward, you should replace $\\Phi(w_0)$ with $\\theta(\\Phi(w_0))$. line 809 $\"M=\"$. line 810, $\\text{log}^2$ seems to be $\\text{log}^3$. line 819, \"note that\" and \"when\".  line 826, \"$g$\" is missing. \n\nIn line 947, I couldn't derive second inequality. maybe there should be a larger coefficient.\n\nlines 1018 and 1025, $\\lVert M \\rVert$ instead of M.\n\n\n\nQuestions:\n\nregarding line 207-8, can you provide such examples, or mention some papers? \n\nIn line 614, $\\underset{\\epsilon \\rightarrow 0}{\\text{lim }}  \\epsilon ^{-\\frac{1}{\\epsilon}}$ seems to be infinity, but for your result to hold it should be zero. This also happens in other places like line 181. Please explain. \n\nMy most important question is regarding the exponential rate of GD in theorems 6 and 7. In the proofs you say combining Lemma 1 with Theorem 4 will give the result. However Theorem 4 has a $1/T$ rate and $g(z)=z$. Please carefully explain it and also update the paper to contain more details of this proof.\n\nIn line 722, please explain (if needed by writing equation) that why 27 is valid if 26 is violated. I think there must be some $\"g\"$ and $\"\\psi\"$ missing in (27), by looking at line 741.\n\nIn Theorem (4) you mention $O(\\frac{1}{\\sqrt{T}})$ rate of convergence, but in line 741, I can see $1/T$ as well as a constant term. Please explain. it seems that line 741 and 761 only differ by a constant and both of them are $O(1/T)$ except that 741 is suboptimal assuming g is zero at optimum. \n\nIn line 798, I couldn't use Markov to get (39). I'd like to see one line of proof.\n\nline 804, where do you set $\\kappa$ in the paper?\n\nLine 853 there is a serious issue with derivation of line 5, because we don't know $\\theta(\\Phi(w_{t+1})) - \\theta(\\Phi(w_t))\\geq 0$, hence equation (50) may not be true. Please revise/explain the proof.\n\nIn proof of Lemma 11 needs serious revision. The derivation in lines 890 is incorrect and you should write $\\overset{-}{R}(w(s),t)=R(w(s),\\sigma(h(w(s)))t)\\leq R(w,\\sigma(h(w(s)))t +s) \\leq R(w,\\sigma(h(w(s)))t + \\sigma(h(w(s)))s)\\leq=R(w,\\sigma(h(w(s))) (t+s) )\\leq R(w, h(w(s)) (t+s) )= \\overset{-}{R}(w,s+t)$.\nMore importantly, I see an inconsistency in using $\\sigma(h(w))$ and $h(w)$. For example you define $\\overset{-}{R}(w,t)=R(w,\\sigma(h(w))t)$, but after line 892 suddenly there is no sign of $\\sigma$ in derivations of $\\nabla \\Phi_g(w)$ and $\\nabla ^2 \\Phi_g(w)$. As you use $\\sigma$ in lines 306 and 336, I think $\\sigma$ is kinda absored in $h$ but I can't wrap my head around this issue. in line 895 equation (51) $\\Phi_g(w)$ uses $h(w)$ instead of $\\sigma(h(w))$. Also in line 911 the second term is used incorrectly and should be modified.\n\nIn line 1028, how do you calculate the bound on hessian? I assume hessian would be complicated.\n\nin line 1048 line 3, do you assume $\\text{min }F=0$?\n \nSuggestion:\nI urge you to state the result of Chatterjee more rigorously in the Appendix, and explain (mathematically in appendix) how in the lines 374-378 you can recover his result. I also expected a conclusion part at the end of the paper, but I assume you couldn't fit it.", "limitations": "As this is a completely theoretic paper, I cannot think of anything related to social impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "As authors mention, using admissible potential functions for getting a convergence rate for GF is studied before. Identifying the one-to-one correspondence between admissible rate and potential functions that satisfy the geometric property in (4) seems interesting. Propositions 1 and 2 also provide simple examples on how admissible rates and potentials exist in easy-to-prove scenarios.\nAs I read all of the proofs, there are lots of typos and some derivations, which I will mention in below, are not carried out correctly, and I hope after revision they will not be problematic for the main claims to hold. However, overall the main results are clear and easy to read and providing examples like propositions 1,2 and touching on Phase retrieval and matrix square root problems makes this converse Lyapunov strategy interesting for analysis of GD/SGD using the GF convergence rate. I think this paper aims at connecting GF and GD analysis which is currently a hot research topic in optimization.", "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": "rDUumrNBA5T", "reviewer": "Reviewer_fx5A", "summary": "This work presents a novel framework for analyzing SGD via Lyapunov analyses of continuous-time gradient flow. The authors first establish that, loosely speaking, a Lyapunov function must exist if gradient flow converges. Then the authors show convergence of SGD using the same Lyapunov function. Some interesting and illustrative examples are provided, but there are no experimental results, which makes this a theory paper.", "questions": "What is the key main result that demonstrates the effectiveness of this Lyapunov analysis framework?", "limitations": "The justification of the usefulness of the Lyapunov analysis framework is not sufficiently convincing, since many researchers in the field are already aware that many (if not all) discrete analyses have nice continuous-time counterparts with gradient flow or SDEs.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The level of abstraction regarding Lyapunov functions is not something I have seen in the optimization and SGD literature, and the first result establishing the necessity and sufficiency of Lyapunov functions is interesting, at least to me. However, it is unclear to me what benefit this abstraction brings. The rates established for SGD are not better than any of the prior rates, and, in fact, many of the state-of-the-art rates are established not with the plain SGD but with some minor variation, such as certain varying stepsizes, appropriate batch sizes, or some non-uniform averaging schemes. Such variations probably can be considered under this framework, but this has not been done in this paper yet.\n\nThe control-theoretic framework feels like an interesting framework to me, but there's no key result that validates the strength of this viewpoint. The insistence on considering Lyapunov functions of gradient flow may be a key insight that future research on SGD will benefit from, but I don't think this work has sufficiently demonstrated the usefulness of this framework beyond its novelty.", "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": "qWm2ZjDzhnp", "reviewer": "Reviewer_bbKp", "summary": "This paper provides a new way of developing the convergence analysis of gradient descent (GD) and stochastic gradient descent (SGD) by leveraging the convergence of the gradient flow (GF). The main tool of the paper is to construct a Lyapunov potential which implies a convergence rate of the GF, formalized as a general converse Lyapunov like theorem. With additional self-bounding regularity conditions, the convergence of GF is sufficient to imply the convergence of GD and SGD. This framework is so general that it provides a unified analysis of GD and SGD that match the best convergence rate of convex functions or PL/KL functions, but also for phase retrieval and matrix square root problems.", "questions": "Typos:\n\nDuplicate references: [21] & [22]; [41] & [42]", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written, highlights their contribution clearly, provides lots of interpretations and simple examples of their general framework. The framework and the way to show convergence of GD and SGD are creative. There is a lot of conceptual value to the community that allows to develop new convergence analysis of GD and SGD in more complex models (e.g. neural networks). I am not familiar with the optimization theories of GF. The mathematical derivation of convergence seems solid.\n\nMy evaluation for the work is mostly positive. It may be better for the authors to write a paragraph how this work can be applied in the future. For instance, how SGD convergence analysis for the neural networks can be established under this framework ? More generally, can this framework be extended to other optimization methods, such as second-order methods and other variants of SGD (e.g. Adam, stochastic variance reduced gradient) ?", "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": "fscxnQSZdzl", "reviewer": "Reviewer_RAee", "summary": "The authors of the present paper show the following contributions:\n- They provide an equivalence between satisfying certain convergence rates and geometric conditions\n- They apply their framework to gradient descent and stochastic gradient descent, requiring  more assumptions on the function to be optimised to derive convergence rates.\n- They apply their overall framework to matrix square root and phase retrieval where rates of convergence for the gradient flow have been shown in the literature.", "questions": "- Theorem 4 shows 1/T or 1/\\sqrt{T} rates of convergence for the gradient descent whereas Theorem 6 and 7 show exponential rates if the gradient descent case. I understand some PL inequality seems to be hidden here, but this needs to be precised as these theorems are not an application of the Theorem of the previous section.\n- The SGD noise scales like the function value for the phase retrieval example, hence I would expect an exponential rate of convergence for SGD also (Theorem 6). Can the authors comment on this ?\n- In terms of the two applications, it would be nice to refer to known rates of convergence for GD and a comparison with what you obtain with your technique.", "limitations": "I use this paragraph to conclude as I already discussed the limitations on the two previous boxes. My opinion is that it could be a super nice paper: I like the overall idea to go from gradient flow with rates to geometrical implications on the lost and then to (stochastic) gradient descent rates. However, the implication of such results on concrete examples could be more referenced and the writing improved.\n\nFor now, I give a borderline accept but I will gladly improve my score if the authors give me some evidence that they can improve the paper in such a short notice.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### **Strengths**\n\n- The paper appears to be original, introduce a very nice idea from the ODE's literature with converse Lyapunov theorems (ref 25). The link with gradient descent and stochastic gradient descent is nicely introduced and seems to enable direct analysis from rates of convergence for discrete analysis.\n- The papers show a large diversity of results, which is rare in nowadays paper in conference. \n- The authors really try to apply their machinery to concrete and hard problems in the last section.\n- The hypothesis on the stochastic gradient descent (Assumption 3) is a nice and covers a lot of cases.\n\n### **Weaknesses**\n\n- The paper is overall hard to follow: the progression is okay and technical contributions are understandable but it is hard to understand where the authors want to bring us. As an example of this, I think that the paper lacks some comments in the fifth section where they apply their method: there is absolutely no discussion on knowing whether the rates are tight, whether they are new (for gradient and stochastic gradient descent). Another striking example is the subsection 5.3 where Lemma 4 seems to nicely improve on recent Chatterjee condition without application or explication on this result (even the authors write: \"*With a wider choice of g and r we can extend these to more general models (eg. neural networks with milder assumptions on the activation function)*\". \n- Adding to the previous comment, there is no conclusion, and many times, the paper seems to have been written in a hurry, see some minor flaws below.\n- For the result to hold, there is a need to know in advance rates of convergence, which limit the applicability of the results.\n\n\n### **Minor flaws**\n\n- Why talking of implicit regularisation in the introduction (ligns after 24) ?\n- In lign 38, the cited papers do not provide convergence analysis and only focus on implicit regularisation\n- lign 87, it is not standard that the estimator is not the final iterate, precise that this is your way to see gradient descent. Same lign 96.\n- lign 97, $(w)$ is a weird notation for a process. Prefer $w$ or $(w_t)_{t \\geqslant 0}$ \n- lign 108 ,what is the $p$-th derivative ? Isn't it simply the gradient ?\n- For all theorem, comment the fact that Admissible rate functions could not exist\n- It would be nice to have a commentary on what is $g$ in Corollary 1 \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": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept