Nesterov acceleration in benignly non-convex landscapes
Authors: Kanan Gupta
Stephan Wojtowytsch
Venue: ICLR 2025 Spotlight (2025)
Keywords: Nonconvex optimization
stochastic optimization
stochastic acceleration
smooth convex optimization
deep learning
accelerated gradient descent
Primary area: optimization

Abstract: While momentum-based optimization algorithms are commonly used in the notoriously non-convex optimization problems of deep learning, their analysis has historically been restricted to the convex and strongly convex setting. In this article, we partially close this gap between theory and practice and demonstrate that virtually identical guarantees can be obtained in optimization problems with a 'benign' non-convexity. We show that these weaker geometric assumptions are well justified in overparametrized deep learning, at least locally. Variations of this result are obtained for a continuous time model of Nesterov's accelerated gradient descent algorithm (NAG), the classical discrete time version of NAG, and versions of NAG with stochastic gradient estimates with purely additive noise and with noise that exhibits both additive and multiplicative scaling.

Published as a conference paper at ICLR 2025
NESTEROV ACCELERATION IN BENIGNLY NON-CONVEX LANDSCAPES
Kanan Gupta, Stephan Wojtowytsh Department of Mathematics, University of Pittsburgh kanan. gêp depiit.eeee tt. edu, s.woj@pitt..ed
ABSTRACT
While momentum-basse optimization algorithms are commonly used in the no- toriously non-convex optimization problems of deep learning, their analysis has historically been restricted to the convex and strongly convex setting. In this article, we partially close this gap between theory and practice and demonstrate that virtu- ally identical guarantees can be obtained in optimization problems with a 'benign' non-convexity. We show that these weaker geometric assumptions are well justified in overparametrized deep learning, at least locally. Variations of this result are obtained for continuous time model of Nesterov's 's accelerated gradient descent algorithm (NAG), the classical discrete time version of NAG, and versions of NAG with stochastic gradient estimates with purely additive noise and with noise that exhibits both additive and multiplicative scaling,
INTRODUCTION
Accelerated first order methods of optimization are the backbone of modern deep learning. So far, theoretical guarantees that momentum- methods accelerate over memory-less gradient-based methods have been limited to the setting of convex objective functions. Indeed, recent work of Yue et al. (2023) shows that the assumption of convexity cannot be weakened as far as, for instance, the Dolyak-Lojasiewiez (PL) condition V fll 2 2μ (f inf f). which has been used to great success in the study of gradient descent algorithms without momentum for instance by Karimi et al. (2016).
Optimization problems in deep learning are notoriously non-convex. Initial theoretical efforts focused on approximating the training of very wide neural networks by the parameter optimization in related linear model: The neural tangent kernel (NTK). Jacot et al. 20; E et al. (2019) show that for randomly initialized parameters, gradient flow and gradient descent trajectories remain uniformly close to those which are optimized by the lincarization of the neural network around the law of its initialization. This analysis was extended
coamentuum-bssee optimization by Liu et al. (2022).
Recall that C²-smooth function / is convex if and only if its Hessian, D² is positive semi-definite, i.e. has only non-negative eigenvalues. Strictly negative (but small) eigenvalues of the Hessian of the loss function have been observed close to the set of global minimizers experimentally by Sagun et al. (2017; 2018); Alain al. (2018) and their presence (2023). This poses questions about the use of momentum-based optimizers such as SGD with (heavy ball or Nesterov) momentum or Adam in the training of deep neural networks. In this work, we show that acceleration can be guaranteed for Nesterov's method under much weaker geometric assumptions than (strong) convexity, particular for certain objective functions that have non-unique and non-isolated minimizers and whose Hessian may have negative eigenvalues up to certain size.
been explained theoretically by Wojtowytsch
In the remainder of this section, we briefly review how our work fits into the literature. In Section 2, precisely state the assumptions under which we prove convergence at accelerated rate and diseuss how our work connects to optimization in deep learning. Our main results are presented in Section 3, both in discrete and continuous time. Some technical details postponed to the appendix.
1.1 PREVIOUS WORK
Gradient-based optimization was first proposed by Cauchy et al. (1847) in form of the gradient descent algorithm. Over a century later, momentum-based 'accelerated" algorithms were introduced

---

Published as a conference paper at ICLR 2025
by Hestenes & Stiefel (1952) for convex quadratic functions and by Nesterov (1983) for general smooth and convex objective functions. Nesterov's work was generalized to non-smooth convex optimization by Beck & Teboulle (2009) and to stochastic smooth convex optimization among others by Nemirovski et al. (2009); Shamir & Zhang (201)); Jain et al. (2019); Laborde & Oberman (2020) for additive noise and by Liu & Belkin (2018); Even al. (2021); Vaswani et al. (2019); Gupta et al. (2024) for multiplicatively scaling noise. See also (Ghadimi & Lan, 2012; 2013) for more information on accelerated stochastic gradient methods. While the heavy ball method is used extensively in deep learning, Lessard et al. (2016); Goujaud et al. (2023) prove that it does not generally achieve accelerated convergence for smooth strongly convex functions and may even diverge see however (Kassing& & Weissmann, 2024) for positive results under stronger smoothness assumptions
Accelerated gradient methods have been studied e.g. by Josz. et al. (2023) under much weaker regularity conditions and weaker geometric conditions than (strong) convexity, namely the Kurdyka- Lojasiewiez (KI.) condition. Under those weaker assumptions, is best possible to prove con- vergence to local minimizer at non-acclerated rate: Under the (comparatively weak) Polyak- Lojasiewicz (PL) condition, a special case of the KL condition, Yue et al. (2023) show that it is not possible to obtain accelerated rate of convergence. A slower linear rate of convergence is established by Apidopoulos et al. (2022) in continuous time under the assumption that the ob- jective function f satisfies has L-Lipschitz continuous gradient and satisfies the PL-inequality The rate of convergence is
2j(s - inf f) - [|.
Vu (LL/u-VL/p-i)--- (-
1 D
J 2VT.
2L
A stable dime-discretization can generally be attained with effective step-size 1/VL for momentum methods (see Su et al., 2016, Section 2), suggesting convergence at the non-accelerated linear rate (1 - -//21* in discrete time. To the best of our knowledge, no proof has been given yet.
There have been several efforts find reasonable relaxation of convexity for which accelerated convergence can still be achieved. Hinder et al. (2020); Fu et al. (2023); Wang & Wibisono (2023); Guminov et al. (2023) consider acceleration under the weaker condition that the objective function is y-quasar or (7, -t--tony quasar-convex, i.e. the inequality
[z)))) =-=)) x²) 2 (f(x) - f(x"((()))))))))))))))) 1|=-="1133
||
holds for any x E Rd and any minimizer x² of f. Compared (strong) convexity, relaxes the condition in two ways: It only considers pairs (x,x") rather than general pairs of points E Rd and it introduces a factor y into the inequality which may be strictly smaller than one. Still, it has geometric implications which may be too strong in the context of deep learning: In the strongly quasar-convex case, minimizers are unique, and in the quasar-convex case, sub-level sets are star- shaped with respect to any minimizer x" since f ftr + (1 - -))=") is monotone increasing [0, 1] (see Lemma 24, Appendix C).
Accelerated rates of convergence Aujol et al. (2022) in continuous time under the assumption that the objective function is both convex and quasi-strongly convex, and that it has unique minimizer. Their results are generalized by Hermant et al. (2024) who allow for non-smooth composite optimization and consider E (0, 1] rather than just 7 1. Unlike the present work, Hermant et al. (2024) require the uniqueness of minimizers and only study deterministic optimization. Curiously, despite the difference in settings, they independently find the same lower bound on Hessian eigenvalues that we require (compare e.g. Theorem 1 and (Hermant et al., 2024, Theorem 2)). See also (Aujol et al., 2024, Table 1) for an overview of theoretical guarantees of acceleration without strong convexity.
obtained by Necoara et al. (2019) in discrete time and by
In overparametrized deep learning, the set of minimizers of the loss function is (generally curved) manifold, and tangential motion to the manifold can have important implications on the implicit bias of an algorithm (Li et al., 2021; Damian et al., 2021). Any notion that takes into account all minimizers quite rigid for such tasks. A more realistic assumption the 'aiming condition' of Liu et al. (2024) that
x 2 >f min
where . (Ix) is the closest minimizer to the point æ. This notion enjoys much greater flexibility in terms of the global geometry of f. Liu et al. (2024) investigate the convergence of gradient flows under the aiming condition, but not that of momentum methods.
2

---

Published as a conference paper at ICLR 2025
1.2 OUR CONTRIBUTION
Our study can be seen as combining geometric ideas pertaining to (1, 4 convexity and the aiming condition. Our assumption in (1) is equivalent to quasi-strong convexity (Necoara al., 2019). but notably we do not make any additional assumptions about the convexity of the objective function or uniqueness of minimizers unlike prior works. Since we focus on the closest minimizer at any point in the trajectory, this presents unique challenge compared to analyzing the distance from fixed minimizer. As the current iterate Iy moves, its projection onto the set of minimizers, x (xx), also moves. This requires modification of the usual Lyapunov function to account for the movement of π (xt) (or the tangential movement of z parallel to the set of minimizers) as well as the 'drift' in directions where the objective function is negatively curved. To the best of our knowledge, this is the first study which takes into account this tangential movement and obtains accelerated convergence.
In overparametrized learning, the set of minimizers of loss function is submanifold of high dimension a usually much nigher-dimenssionn space, the Hessian of the loss function is geometrically required have negative eigenvalues in any neighborhood of the set of a minimizer where the manifold is curved. Still, accelerated methods in first order optimization have been found be highly successful in deep learning. A common heuristic has been that as long as the objective function is convex in the direction towards the set of minimizers, small negative eigenvalues in directions parallel to the set of minimizers can safely be ignored: Tangential drift along the set of minimizers should not affect the decay of the objective function significantly. We prove that this intuition indeed applies in a continuous time model for gradient descent with momentum (Theorems 6 and 8) and for Nesterov's 's time-stepping scheme (Theorems 11, 13 and 14) in deterministic optimization and stochastic optimization with bounded noise. With 'multiplicative (state-dependent)) noise' motivated by overparametrized deep learning, we prove an analogous statement for a modified version of Nesterov's algorithm (Theorem 15).
space. Unless the manifold of minimizers is a linear
2 SETTING
2.1 ASSUMPTIONS
We always make the following assumptions on the regularity and geometry of the function f and its set of minimizers.
1. The objective function f Rd - R is bounded from below, Cm-soh and its gradient ff Rd + Rd is locally Lipschitz continuous.
2. The set M {a E TRd f() inf =e0= [()) of minimizers of f a (non-empty) k-dimensional C C"-submanifoll of ndd for k < d.
3. There exists open sub-level set Ul fx E Rd f(x) at for some 0 such that for every E Un there exists unique E M which is closest to x. We denote z as (x)) and assume that the closest point projection map Uu, - M is C"-smooth.
4. f satisfies the j-strong aiming condition (with respect to the closest minimizer) in Ug i.e.
Vz(x) (s x(x)) 2 f(z) f(((=))
# ~ || (2))]
V T Ua.
(1)
These assumptions are significantly weaker than the assumption of strong convexity, but for instance strong enough to imply a PL inequality with constant μ (see Appendix C). As illustrated in Section 2.3, they match many geometric features of overparametrized deep learning. For an analysis in discrete time, will make stronger quantitative assumptions.
2.2 SIMPLE EXAMPLES
We give a number of examples which are covered by these assumptions where f is not merely j-strongly convex function. The first example illustrates how subtle the interplay between geometric conditions is, even in one dimension.
Example 1. For E, R. >> 0, consider the function fx) = o has unique global minimizer at x² O and its derivative is Lipschitz-continuous function
x² sin log((=)) The function
3

---

Published as a conference paper at ICLR 2025
20
16:
20-
30-
62
10-
Figure 1: We visualize f from Example I in the top row and its derivative in the bottom row with R = 2 and 0.2 (left), 0.1 (middle) and 0.05 (right). Left: I has many local minimizers as the derivative crosses 0 an infinite number of times. Middle: satisfies the PL condition, but not the strong aiming condition. Right: f strongly aiming (with respect the unique global minimizer, which implies the PI. condition). In all plots. f is non-convex since I' is non-monotone.
with Lipschitz-cconstant + + 5R 4R Furthermore, f has infinite number of strict local minimizers if R > 1, but satisfies favorable geometric properties under stronger assumptions:
PL condition
p-strongly aiming
μ-strongly convex
Must <1
+VI+
e eV + 4R
8V 8V 5R + 4R
Constant
(1 - 11-ev11+ R1)3(1+)))
1 1- 4 1- 5R 4R
Evidently, the geometric conditions and associated constants are quite different if R >>>>>>> 1. See Figure 1 for an illustration f. Further details for the example and comparison to less common notions such as quasar-convexity are given in Appendix C.2. We note that the example exploits the fact that f is C but not C²-smooth: For C"-functions, Rebjock Boumal (2023) prove that the PL condition locally implies strong aiming condition.
The next example is trivial but useful to illustrate why tangential movement should not matter.
Example 2. Let f : Rd-k + [0, oc) be non-negative p-strongly convex function such that (1( = 0 and let f2 R + o0) be continuous function for >> 0. Define
R R. f(z) f2 .x) f1 f1
Then f is apu-strongly aiming x(x) (#1, Tb. .......... 0), but not strongly convex since the minimizer is non-unique. Similarly, if A & - (d--)) is function which takes values in the set of symmetric matrices with eigenvalues larger than μ, then
R:R-DE
f(x) (* (#641....,za) A ( (2k41....,
is justtrongly aiming, but generally non-convex.
Example 3. Let M be a compact C -ubmmanniio of Rd. k 2 2 and d(x)) dist(xr, Then there exists a 'tubular neighborhood" 24 {a E Rd d(z) { on which d -mmooh and the unique closest point projection x is well-defined and Ck- -o-o-h see Appendix A.
Assume that f -
given by ((x) = _ d(t))² (and extended arbitrarily to Rd (&)). Recall that Vd(x) is the unit vector pointing towards the closest point in M all points where the distance function is smooth, so in particular Vd(x)]l = Thus (x) = dd(x) and
f((x) (x (x)) = r d( Vd(x))((()) (x d(x)) (x) [Vd(=)] (x-
P & (x) + 11 (
| || (x))
f(x(x))
2
for x E U,, i.e. f is u-strongly aiming. the other hand, f is not convex unless M is. Otherwise, take 21, D2 and E (0, such that tæ (1-t)xz & M. Then the map d² tz + (1-t)x2) attains maximum inside the interval (0, meaning that d² cannot be convex.
4

---

Published as a conference paper at ICLR 2025
500
C
11
13
33
125
1.00
4.35
-355
-0.25
3.3
0.59
6.75
130
180 280 304
1300
2006
3000
4000
500
6000
7308
0600
Figure 2: Left:
The dashed red line connects two minimizers of the function f. Along the line, f must achieve interior local maximum. At this point, the Hessian D cannot be positive definite. Middle, Right: Optimization trajectories for Nesterov's 's method (top) and its associated energy curve (bottom). The selection of limit point may depend crucially on optimization parameters: In the middle plot, we take 800 steps with stepsize 10 while on the right, we take 8,000 steps with stepsize 10-3 the limit points on
from the same initial point. The decay of f(xxx) similar for both trajectories, the manifold of minimizers are far apart. The objective function is fxx v) = (a /2 + 3y 1)2.
This consideration more generally shows that if the manifold of minimizers M of a function f is not perfectly straight, then the objective funetion cannot be convex also Figure 2. More precisely:
Lemma 4. (Wojtowytsch, 2023, based Appendix B) Let f Rd - R be C*-function and M = {a E (R f(()) inf f). Assume that M is k-dimensional C -u-smmnanifold of IR', M. T,M the tangent space at 2, r >> 0. M.M (2) is not the same as (z + T,M) (z),,, then there exists x E (2)2) such that D2 f() has a strictly negative eigenvalue.
2.3 CONNECTION DEEP LEARNING
An important class of objective functions are those which combine the geometric features of Examples and Such functions can seen as geometric prototypes for loss functions overparametrized regression problems, such as in deep learning. Namely, consider a parametrized function class h IP x Rd + I of weights w E IR' and data æ E Rd (c.g. a neural network) and the mean squared error (MSE) loss function
Ly IP > (0),
(w(w)= = 2n Σ (Mw, - ys) = (V1, Un) E R".
(2)
If h is sufficiently smooth in w and for every vector E R", there exists By E R such that Ly (wr,) 0, then Cooper (2021) showed that for Lebesgue-almost all y E R", the set M, {w Rº (w) = 0} is a n-dimensional submanifold of R". Essentially, the solution set of n equations h(w: x1) = y: in p variables
n-dimensional, much like when linear w.
Cooper (2021) demonstrates that the expressivity and smoothness assumptions provably apply to parametrized function classes h(w, 2)) of sufficiently wide neural networks with analytic activation function such as tanh or sigmoid. Cooper (2021)'s proof involves the regular value theorem and Sard's theorem to show that all gradients (w,, xx) are linearly independent on almost every level set My. As a byproduct, this implies that the Hessian of the loss function
D²L(w)=
(h(w, - vi) (1e, + V Var(ww vs) s V V.h(w,))))
has full rank n at every x E My (for almost every y). Thus, all n eigenvalues in direction orthogonal to M non-zero. We prove the following in Appendix A. The same connection has been made e.g. by Rebjock & Boumal (2023) for C22ffuctton and overparametrized regression problems.
Lemma 5. Assume that ff Rdd + IR C² smooth and that M = {x E Rd f(x) = inf f is closed k-dimensional C² ---ubmanifold of Id (i.e. compact and without boundary). If f(x has rank d - l everywhere on M, then there exist p. a > O such that there exists C¹ smooth closest point projection U. R with U.. {x f(x) < a)) and f is p-strongly aiming with
5

---

Published as a conference paper at ICLR 2025
loss function
Strong convertty parameter. second derivative
Strong convodit parameter w respect minimber
10
-1.00
Figure 3: Convexity analysis of (() L(w + tg) for w near global minimizers of loss function L and g VL(w)/|
Left: @(t), middle: second derivative of é, right: estimated strong aim- ing parameter for / E [-1, Evidently, á is strongly convex in a neighborhood of the minimizers. Strong aiming condition yields consistently larger constants than the strong convexity parameter obtained from second derívatives. Different colors correspond to different random initializations.
In particular, f. M meet all conditions in Section 2.1. Note that by Lemma 4, the loss function f cannot be convex since compact manifold cannot be perfectly straight everywhere. Lemma 5 does not apply to networks with the non-smooth ReI.U activation ((2) = max z. 0). also here minimizers cannot be isolated due to the continuous scaling symmetry a(2) o (X2) for À 0.
Wojtowytsch (2023, Theorem 2.6) shows that the assumption that M is compact a simplification and generally does not apply in deep learning. Local versions of Lemma 5 could be proved with J4, a which are positive functions on the manifold, but not necessarily bounded away from zero. Naturally, this suffices in all cases where we provably remain in local neighborhood in the course of optimization. We eschew this greater generality for the sake of geometric clarity and commit the pervasive sin of optimization theory for deep learning: We make global assumptions which can only be guaranteed locally. For further comparison of geometric conditions in optimization and deep learning, see also Appendix C.
We illustrate in Figure that our assumptions are locally reasonable in deep learning. We trained a fully connected neural network (with layers, width 35, tanh activation) to labels y at 100 randomly generated datapoints x; E I2,2, The small dataset size allowed us to use the exact gradient and loss function instead of stochastic approximations, for better exploration of the loss landscape. Since the closest minimizer is generally unknown, use the gradient examine the convexity of d(t) = L(w + tg) for w very close to the set of global minimizers of the loss function L in (2) and g = V (w())/l /[VL[]) Labels were generated using randomly initialized teacher network (with 7 layers and width 20). Student networks were trained for 10,000 epochs using stochastic gradient descent with Nesterov momentum, with learning rate 1) 0.005 and momentum 0.99. Final training loss ranged between 10 10-12 and 10-9 across the five runs. Second
proxy and
derivatives were approximated using second order difference quotients ("(t) @(t++A) 20(t)+ for h = 0.01. Similarly, the strong aiming parameter with respect to the global minimizer was estimated by 2 ((())))((t)++))) where Øi (t) was estimated as ((t++h)-o(k
Due to the inherent randomness of training, geometric behaviors varied. Generally, the loss function was convex along the gradient direction near minimizers, but neighborhood size, magnitude of the second derivative, and steepness the loss function varied. Some runs exhibited convex but not strongly convex behavior, while others failed to reach zero loss along the line ////lg//- The gradient is an imperfect approximation of the minimizer's 's direction, and rounding errors may occur when it is so small near the set of minimizers.
MAIN CONTRIBUTIONS
3.1 OPTIMIZATION IN CONTINUOUS TIME
In this section, we study a continuous time version of gradient descent with (heavy ball or Nesterov) momentum derived by Su et al. (2016). Namely, study solutions of the heavy ball ODE
σ -V (xr),
2 (0) To:
i0()) 0.

---

Published as a conference paper at ICLR 2025
This is a popular model for the study of accelerated methods in optimization which avoids some of the technicalities of discrete time stepping algorithms while relying on the same core geometric concepts. Our main result is the following.
Theorem 6. /Continuous time convergence guarantee] Assume that J satisfies the assumptions of
Section 2.1, y = 2/ and that zo satisfies f(2o) < a where a is as in Section 2.1. Then there exists a unique solution zt) = Tt of (3) and f(xx) < a for all t > O. Furthermore, a is C? -m-shooth and
P f(x+) inf f(=) Se (1(Zo) inf ʃ dist dist M))). =ERd
The proof can be found in Appendix B. There, we prove that the Lyapunov function
(t) f(x)) - f(x(())) + 2 || + vala, (x:))|]
satisfies C(t)= S e <E-viL C(0). The function C can considered as a modified energy with potential energy f- inf 51 (2))] and kinetic energy 1 || but with more complex quadratic term in which velocity and position interact. Going back to (Su et al., 2016), this strategy proof common in convex optimization. The main difficulty in more general geometric setting is that the time derivative of ((x) (i.e. tangential velocity) is not zero in general, unless the minimizer is unique in Ma- Thus, have additionally control for the interaction of the tangential velocity with the other terms in the Lyapunov sequence. One key observation that helps us is that the connecting line Iy (2x) orthogonal the velocity of т (zt). The other technical tool is the following lemma.
Lemma 7. Let M be CZ-submanifold of d and U open set containing M such that there exists unique closest point projection π U + M. Let x (-e,e) + U be a -curre and =(t) o xr)). Then (i, 2) 2 on (-E,E).
Geometrically, Lemma 7 states that the closest point projection = of point does not move in the opposite direction when we move x. Despite its geometric simplicity, Lemma is non-trivial and a crucial ingredient in proofs. Its proof is given in Appendix A.
Venturi al. (2019) show that loss functions in overparametrized deep learning do not have strict local minimizers outside the set of global minimizers (under suitable assumptions). Under quantitative version of this geometric assumption, we obtain a global version of Theorem 6, albeit with less precise quantitative guarantees.
Theorem 8. In addition to the assumptions of Section 2.1, assume that
1. for every R > inf f. there exists LR > such that f is Lipschite-continuouss with Lipschitz constant La on Un {x f(x) ) < R} and
2. there exists a value 8 > O such that [V < 5 implies that f(xx) - (in))-inf]]) < f
Then, for any zo E Rd, there exists T 2 0 such that axt) Ua for all 2 T and such that f(x(t)) - inf < (3a/2 + M)²) for all > T.
The rate of decay here e V as compared -ut for gradient flow. We see more clearly why we speak of acceleration in discrete time (see the discussion below Theorem 11).
Remark 9, We conjecture that Theorem 6 remains valid if the set M is convex rather than smooth manifold. Then æ is defined globally, but generally only Lipschitz-continuuus and not smooth.
3.2 DETERMINISTIC OPTIMIZATION IN DISCRETE TIME
We can equivalently write the heavy ball ODE (3) as system of two first order ODEs:
{
t = =
xx0)= To.
(0)) = 0.
(4)
22 Vf(x).
We choose time steessg scheme
2/1 Fr. Vrln,
In. ()(()))
In+1 J/1 ?gan
Un+1 p(v,. viga) (5)

---

Published as a conference paper at ICLR 2025
for p 1+
1- pm
- 2/1m + O()). (())
In partieular, have
Tn+1 Jn vn + (1)). Un+1 = (T(2V + VS(z)) + O())
Lec the scheme is a time discretization of the heavy ball system (4) with time-step size vn. The square root is chosen for consistency with the literature. This scheme is a geometrically intuitive reparametrization of Nesterov's s accelerated gradient descent algorithm, except for the fact that Nesterov's s scheme typically begins with the gradient descent step rather than the momentum step (see Gupta et al., 2024, Appendix B, for proof of equivalence).
In discrete time, we need to make additional quantitative regularity assumptions on both and the projection map π order to ensure that the time step size sufficiently small to recover the continuous time behavior. Note that the Hessian of the objective function f is positive semi-definite on the set of global minimizers M, i.c. it stands to reason that any negative eigenvalues of D2 should be small, least close to M. We note the following.
Lemma 10. Assume that D2 f(x) 2 -E in ball B, (2o). Then
(Vf(z), 2) 2 f()) f2)
2|
V2,2E (zO)..
This lemma informs our geometric assumptions on the objective function f. For the closest point projection H, we assume that (xx) Px x for some (linear) orthogonal projection P onto subspace V S Rd and fixed vector x² which is the unique element with the smallest Euclidean norm in the affine space V = x² + V. The assumption that the derivative DT = P is constant is (very restrictive) geometric linearization, and relaxing it an important subject of future research. Still, it applies to many functions which are not convex, such those with unique minimizer (i.e. P= or those in Example 2. With an eye towards stochastic optimization, we opt for the simpler global geometric assumptions,
also Remark 16.
Theorem 11. Assume that I is L-smooth and the sequences In, x' Un are generated according to the Nesterov scheme (5) with parameters n S 1/T. and p (1 / /ioj). Assume further that there exists an affine linear projection map π (x) = Pr + x² such that
(V -xx)) 2 f(x) f(x(xx))=))))))))))(((()))))ff + P || Tx))1
(6)
Finally, assume that for arbitrary x, v E R.d we have
(Vf(z + u), 2 f(x - -e) - E ||u1|2
(7)
with some S Vu/n. Then
(xx) inf (1- Vun)" [(xx) - inf - -
m(20)]]²
The proof, given in Appendix B.2, builds on similar ideas as Theorem 6, with additional complications introduced by the discrete-time setting. We have to modify the usual Lyapunov sequence used for strongly convex functions. We treat the tangential and normal components of the velocity (i.c. Ptn and p-r, e,2 (I - P)r,) separately, and carefully choose coefficients to ensure that the following Lyapunov sequence decays at each step.
inf f 1
p-c, cn + Vu(a', - -x,2)))1 (1 + 2
Cn = s(x)) - inf
2(1 vum) PPall
In Theorem 11, we see more clearly than in Theorem 6 why we talk of acceleration: While gradient descent would achieve a decay rate of (1 (1- =/L)" with the commonly proposed step size = 1/L discrete time based on our assumptions, Nesterov's method achieves decay like (1 - Vp/L.) L.) with
17 1/L. Since p/ L < 1, Nesterov's 's method converges much faster than gradient descent.
Remark 12. Note that the negative eigenvalues of the Hessian may be large as /и/ij in Theorem 11. If 1 is chosen large as 1 I/L, this is a real restriction of the eigenvalues to the range --V Z). However, since the Hessian eigenvalues of an L-smooth function are in [-L, L] a priori, there is no additional restriction if /p/n 2 L. i.c. if < #.. This corresponds to the continuous time guarantee of Theorem 6, which does not depend on the magnitude of the negative eigenvalues.
8

---

Published as a conference paper at ICLR 2025
However, if the eigenvalues of f are negative LL, the step size 1j = 2/ is small that does not improve upon gradient descent with step size = 1/L since / / in this case. Thus, if f is too far from being convex, acceleration may not be achievable in discrete time. Notably, especially close to the set of global minimizers, we can picture & as small compared to L.
3.3 STOCHASTIC OPTIMIZATION IN DISCRETE TIME
In typical applications in deep learning, the gradient V of the objective function/loss function is prohibitively expensive to evaluate, but we have access to stochastic estimates of the true gradient. In this section, addition to the assumptions Theorem 11, we assume that we are given a probability space (S2 A, Q) and a measurable function IRdd x Ω + IR such that
E [g(2, w = fx),, E [1 w)l to0
Rd
(8)
For quantitative statements, a more precise assumption on the variance of the gradient estimates must be made. We make the modelling assumption
E [Ila(1, w) [)())]]]] S 5 + [V)(0))
YOERS.
We call 0r the additive standard deviation and o. the multiplicative standard deviation since they resemble the prototypical example 9 (1 + N1) Vf + J,N2 where N1, NV are random variables with mean zero and variance one. The case of purely additive noise (i.c. am = 0) is classical and hails back to the seminal article of Robbins & Monro (1951). The case of purely multiplicative noise much closer to reality in overparametrized learning: If all data points can be fit exactly, there is no noise when estimating the gradient of the empirical risk/training loss the set of global minimizers. It has received significant attention more recently by Liu & Belkin (2018 8);; Bassily et al. (2018); Vaswani et al. (2019); Even et al. (2021); Wojtowytsch (2023); Gupta et al. (2024) and others.
Let us consider the purely additive case first. We follow the scheme (5), but we replace the determin- istic gradient V fz by Gn. g( w,) where wio ....... are drawn from Q independently of each other and the initial condition To with law Q. This framework allows c.g. for minibatch sampling (but assumes that all batches are drawn independently of each other from the dataset).
Theorem 13. [Acceleration with additive noise] Assume that f P are as in Theorem 11 and that the g satisfies (8) and (9) with o. O. Assume that the sequences Fuy F'yy Vn are generated by the scheme (5) for parameters S 1/L and 1- but with the stochastic gradient estimates I+
g( wn) with independently identically distributed wa in place V Then
[lf(xn) - inf fl S (1- Vum)" [((0) inf f K -11z0- -(x0))1))) 2
T
Thus Nesterov's method reduces (Ix,) below 'noise level' proportional to o3 v n/j linear rate (1 - / in the presence of additive noise. The analogous bound for stochastic gradient descent was obtained (in the more general setting of PL functions) in (Karimi al., 2016, Theorem 4)
Lo²n
Elf( inf fl s (1 -17)** [xf())) - inf f] +
2p
With the largest admissible learning rate 1j = 1/T., the noise level for GD is o²//2u compared to the usually much lower value o /2//VT.ji T.p. for Nesterov's 's method. Keeping a memory of previous gradient estimates facilitates 'averaging out' the random noise.
With fixed positive learning rate 7, generally f A unless 0g = 0. We therefore consider sequence of decreasing step sizes.
Theorem 14. [Additive noise and decreasing step size] Assume that f.g are as in Theorem 13 and that the sequences In, z'ns Pn are generated by the scheme
d/-- En Vm--inn
Ent1 =x',
Unt1 Pn (Un (hng))
for parameters Th (n+ Pn
1- 1-1pim
Ifs / pl
- / LLu, then
ItVPTm
V 4 [f(0)) - inf / + 11100 - ( 12 + c log (1 + nY 1/L)
E[f(x,)) inf f]
n LLP

---

Published as a conference paper at ICLR 2025
Note that the 'physical' step size Vi decays 1/n and thus satisfies the (non- (non))summability conditions of Robbins & Monro (1951). We can allow for larger e by choosing 7m = ps/ + no)
with > vL/u- 1 for a smaller initial step size.
If m O, Liu & Belkin (2018) and Gupta al. (2024) show that Nesterov's scheme no longer achieves acceleration. For general noise, we therefore consider a modified Nesterov scheme:
2/ In + Vaen,
Fn+1 z 199m: Un+1 Pr. (Mh Vag.)
(10)
where again 9n, g(,,,,,,) The scheme (10) was introduced the Accelerated Gradient method with Noisy EStimators method (AGNES) by Gupta et al. (2024) in convex and strongly convex optimization with purely multiplicative noise. Compared to Nesterov's algorithm, AGNES has an additional parameter which is required to adapt to the multiplicative variance, at least if am 2 1. Here, we generalize the work of Gupta al. (2024) by both allowing noise with general scaling for Ja: m > 0 and relaxing the convexity assumption on f.
Theorem 15. [Additive and multiplicative noise] Assume that f. T.P. are as in Theorem 11 and that g is family of gradient estimators such that (8) and (9) hold for some oa On 2 0. Assume that the sequences Inyy Fno Un are generated by the AGNES scheme (10) with parameters
/u(1 + +,20m
0 0<NS
L(1 + 7()+
47 Ito
a
M01 + )z))) o2
Then, ife < v ML1 + +on)/11 we have
n
((f(zx) - inf f] s
pmn o2
E
f((o) inf f
11 2 || x (x+0)??
The proof of Theorem 15 is given in Appendix B.4. While at a glance it appears that the multiplicative noise is helping us reduce the additive error term, this is merely a consequence of the small learning rate which is forced upon us. The condition on the negative eigenvalues is relaxed to S (I with the largest admissible step size 1 = 1/ (L(1 + o),)) as the issues stemming from tangential drift pale comparison to those stemming from stochastic gradient estimates. For comparison, we chose the same 17 in Theorem 11, we could only allow for E S. VpJ. v1 + oz < VuT(( on). but we would obtain a rate of convergence of 1 vu/L(1+0R) J.... In the stochastic case, we only achieve 1 - Vu/ L//+L(1+ o Thus the limiting factor is the stochastic noise, not the geometry of f. Remark 16. We opted for a linear closest point projection map to facilitate proofs. In the non-linear case, closest point projections cannot be defined globally: Jessen (1940); Busemann (1947); Phelps (1957) show that if K is subset of Rd such that for every E Rd there exists unique closest point in K, then K is closed and convex. If K is both a k-dimensional submanifold of TRd and a convex set, then K is an affine k-dimensional subspace of TRd i.e. our assumptions are the most general when assuming that a unique closest point projection onto a submanifold is defined globally.
Thus, if MM is not an affine space, we can only assume that π is 'good' in a neighborhood of M. In stochastic optimization, where we can randomly 'jump' out of the good neighborhood, this leads to serious technical challenges. Guarantees on 'remaining local' with high probability have recently been derived for SGD with additive noise and decaying learning rates by Mertikopoulos et al. (2020) and with multiplicative noise by Wojtowytsch (2023). To avoid obscuring the new geometric constructions, we opted to forgo this highly technical setting here and prioritize the extension of Theorems 6 and 11 towards stochastic optimization.
CONCLUSION
We have proved that first order momentum-based methods accelerate convergence in more general setting than convex optimization with many geometric features motivated by loss landscapes encoun- tered in deep learning. The models studied include the heavy ball ODE and deterministic and stochastic optimization schemes in discrete time under various noise assumptions.
The most cumbersome limitation of our convergence guarantees is the assumption that the closest point projection onto the set of minimizers is affine linear in the discrete time setting, i.c. the derivative Di is constant in space. Future work will focus relaxing this assumption.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
The authors gratefully acknowledge the financial support of the NSF, grant DMS 2424801. The authors grateful to Quentin Merigot, who pointed a simpler proof of Lemma 7 which requires less regularity than the authors' original approach.
REFERENCES
Guillaume Alain, Nicolas Le Roux, and Pierre-Antoine Manzagol. Negative eigenvalues of the hessian in deep neural networks, 2018. URL https: https://openreviev. net nww/foruutttteeeeee
SliiddyDG.
Vassilis Apidopoulos, Nicolò Ginatta, and Silvia Villa. Convergence rates for the heavy-ball continu- ous dynamics for non-convex optimization, under Optimization, 84(3):563-589 2022.
condition. Journal of Global
J-F Aujol, Ch Dossal, and Aude Rondepierre. Convergence rates of the heavy ball method for quasi-strongly convex optimization. SIAM Journal on Optimization, 32(3):1817-1842 2022.
Jean-Françond Aujol, Charles Dossal, Hippolyte Labarrière. and Aude Rondepierre. Heavy ball momentum for non-strongly convex optimization, 2024. URL https://arxiii org. /bs/ 2403.063 06930.
Raef Bassily, Mikhail Belkin, and Siyuan Ma. On exponential convergence of sgd in non-convex over-parametrized learning. arXiv preprint arXiv: /8/ 1.02564, 2018.
Amir Beck and Mare Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM journal imaging sciences, ((1):183-202 2009.
Herbert Busemann. Note on theorem on convex sets. Matematisk Tidsskrift. B, pp. 32-34, 1947.
Augustin Cauchy et Méthode générale pour résolution des systemes d' d'équations simultanées. Comp. Rend. Sci. Paris, 25(1847):536
1847.
Yaim Cooper. Global minima of overparameterized neural networks. SIAM Journal on Mathematics of Data Science, 362) 2021.
Alex Damian, Tengyu Ma, and Jason Lee. Label noise sgd provably prefers flat global minimizers. Advances in Neural Information Processing Systems, 34:27449-27464 2021.
Simon S Du, Chi Jin, Jason D Lee, Michael I Jordan, Aarti Singh, and Barnabas Poczos. Gradient descent can take exponential time to escape saddle points. Advances in neural information processing systems, 30, 2017.
Weinan E, Chao Ma, and Lei Wu. comparative analysis of optimization and generalization properties of two-layer neural network and random feature models under gradient descent dynamics. Sci. China Math, 2019.
Mathieu Even, Raphaël Berthier, Francis Bach, Nicolas Flammarion, Pierre Gaillard, Hadrien Hendrikx, Laurent Massoulié, and Adrien Taylor. A continuized view nesterov acceleration for stochastic gradient descent and randomized gossip. arXiv preprint arXiv:2106.07644 2021.
Qiang Fu, Dongchu Xu, and Ashia Camage Wilson. Accelerated stochastic optimization methods under quasar-convexing In International Conference on Machine Learning, pp. 10431-10460. PMLR, 2023.
Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization,
2012.
Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, shrinking procedures and optimal algorithms. SIAM Journal Optimization, (3(4):2061-208) 2013.
11

---

Published as a conference paper at ICLR 2025
Baptiste Goujaud, Adrien Taylor, and Aymeric Dieuleveut. Provable non-accelerations of the heavy- ball method. arXiv preprint (XXi:2337711299 2023.
Sergey Guminov, Alexander Gasnikov, and Ilya Kuruzov. Accelerated methods for weakly-quasi- convex optimization problems. Computational Management Science, 20(1):36, 2023.
Kanan Gupta, Jonathan W. Siegel, and Stephan Wojtowytsch. Nesterov acceleration despite very noisy gradients. In Advances Neural Information Processing Systems, volume 37, pp. 20694- 20744, 2024. URL https: httpp//////pppepppeo/eee...ee//s neuripssssiinnnnniiprre..rrriiis neurips 2024 fi le/ -o
htapapprrrrieeeapaaaeeeeeeeeeeee pdf..
J Hermant, J. F Aujol, C Dossal, and A Rondepierre. Study of the behaviour of nesterov accelerated gradient in a non convex setting: the strongly quasar convex case, 2024. URL https://arxii: org/ abs org/abs// /atas/24055 2/22..1108..
Magnus Rudolph Hestenes and Eduard Stiefel. Methods of conjugate gradients for solving linear systems. NBS Washington, DC, 1952.
Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. In Conference on learning theory, pp. 1898-1938. PMLR, 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. Making the last iterate of sgd information theoretically optimal. In Conference on Learning Theory, pp. 1752-1755, PMLR, 2019.
Børge Jessen. To saetninger om konvekse punktmaengder. Matematisk tidsskrift. B, pp. 66-70, 1940.
Cédric Josz, Lexiao Lai, and Xiaopeng Li. Convergence of the momentum method for semialgebraic functions with locally lipschitz gradients. SIAM Journal on Optimization, 33(4):3012-3033 2023.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- condition. Machine Learning and Knowledge
gradient methods under the Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings. Part 16, pp. 795-811. Springer, 2016
Sebastian Kassing and Simon Weissmann. Polyak's ' heavy ball method achieves accelerated local rate of convergence under Polyak-Lojasiewier inequality. arXiv preprint arXiv:2410. 16849, 2024.
Maxime Laborde and Adam Oberman. A Iyарunov analysis for accelerated gradient methods: from deterministic to stochastic case. International Conference on Artificial Intelligence and Statistics, pp. 602-612. PMLR, 2020.
Jason D Lee, Ioannis Panageas, Georgios Piliouras, Max Simchowitz, Michael I Jordan, and Benjamin Recht. First-order methods almost always avoid strict saddle points. Mathematical programming, 176:311-337, 2019.
Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal Optimization, 26(1):57-95 2016.
Zhiyuan Li, Tianhao Wang, and Sanjeev Arora. What happens after sgd reaches zero loss?-a
mathematical framework. arXiv preprint arXiv:2110.06914, 2021.
Chaoyue Liu and Mikhail Belkin. Mass: an accelerated stochastic method for over-parametio paramerraetri learning. arXiv preprint urXiv:I8/00 13395, 2018.
Chaoyue Liu, Dmitriy Drusvyatskiy, Misha Belkin, Damek Davis, and Yian Ma. Aiming towards the minimizers: fast convergence of sgd for overparametrized problems. Advances in neural information processing systems, 36, 2024.
Xin Liu, Zhisong Pan, and Wei Tao. Provable convergence of nesterov's accelerated gradient method for weeeeearameterized neural networks. Knowledge-Baan Baaeed Systems, 251:109277, 2022.
12

---

Published as a conference paper at ICLR 2025
Panayotis Mertikopoulos, Nadav Hallak, Ali Kavis, and Volkan Cevher. On the almost conver- gence stochastic gradient descent in non-convex problems. Advances in Neural Information Processing Systems, 33:1117-1128, 2020.
Ion Necoara, Yu Nesterov, and Francois Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, 175.:mmminn....19....1 175:69-107, 2019.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):5574 1609, 2009.
Yurii Nesterov. A method for solving the convex programming problem with convergence rate o11/k2). Dokd. Akad. Nauk SSSR, 269:543-547 -47, 1983.
Michael O O'Neill and Stephen J Wright. Behavior of accelerated gradient methods near critical points of nonconvex functions. Mathematical Programming, 176:403-427, 2019.
RR Phelps. Convex sets and nearest points. Proceedings of the American Mathematical Society, 8(4): 790-797, 1957.
Quentin Rebjock and Nicolas Boumal. Fast convergence non-isolated minima: four equivalent conditions for c'-functions. arXiv preprint arXiv:2303.00096, 2023.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues of the hessian in deep learning: Singularity and beyond, 2017. URL / http:/:://///eeeeeeeeeeeeee n forum? d=B1 8 86P99xx
Levent Sagun, Utku Evei, V. Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the hessian of over--vraameeee per-parametrriedd neural networks, 2018. URL https: http:////ppeeeeeeeeeeeeee net/ forum?id=rJrrweeer.
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International conference on machine learning, pp. 71-79. PMLR. 2013.
Weijie Su, Stephen Boyd, and Emmanuel J Candes. A differential equation for modeling nesterov's accelerated gradient method: Theory and insights. Journal of Machine Learning Research, 17 1353):1-43, 2016.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and accelerated perceptron. In The 22nd international conference artificial intelligence and statistics, pp. 1195-1204. PMLR, 2019.
Luca Venturi, Afonso S Bandeira, and Joan Bruna. Spurious valleys in one-hidden-layer neural network optimization landscapes. Journal of Machine Learning Research, 20(133):1 2019.
Jun-Kun Wang and Andre Wibisono. Continuized acceleration for quasar convex functions in non-convex optimization. arXiv preprint arXiv:2302.0785// 2023.
Stephan Wojtowytsch. Stochastic gradient descent with noise of machine learning type part i: Discrete time analysis. Journal of Nonlinear Science, 33(3):45, 2023.
Pengyun Yue, Cong Fang, and Zhouchen Lin. On the lower bound of minimizing folyak-lojasiewin functions. In The Thirty Sixth Annual Conference on Learning Theory, pp. 2948-2968. PMLR, 2023.
13

---

Published as a conference paper at ICLR 2025
A PROOFS OF LEMMAS 5 AND 7: GEOMETRY OF THE ENERGY LANDSCAPE
We assume that the reader is familiar with basic concepts of differential geometry, such subman- ifolds of Euclidean spaces and tangent spaces and with concepts multi-variate analysis such as compactness and the inverse function theorem.
We first recall an important observation: Assume that M Cl-manifold. Fix point a E IRd Assume that the function d :M- + R given by d(z) || =|| has a local extremum at E M. Then for every C -curve 7 (-E,E) + .M such that (0) = 2, we have
0 dt t=0
d(>(t))² = 2 - -0), +()) = 2(z 2, (())
or in other words: the connecting line x orthogonal to the tangent space T.M. This is in particular true if z is the closest point in M to x.
Lemma 7. Let M be CZ-submanifold of d and U open set containing M such that there exists unique closest point projection π. U + M. Let x (-8,e) + U be a C and 2(t) o zt)). Then (i, 2) 2 0 on (-E,E).
Proof. The closest point projection onto -a-miollldd is C' and satisfies
( x d(x) Vd(x)
(11)
where d(x) dist(x: MM is the distance function the manifold, i.e. Vd(x) gives the unit vector pointing directly towards the manifold. For details, see the proof of Lemma 5.
We can rewrite (11) as
[
d(x)²)
|-|
mingeM
||x - =/12
T(x) V
=
2
2
2
2
|1:11
|
2(x, 2) + ||
|=13
V max
V. max sEM
(x. 2)
2
2
We taking the (pointwise in 2)) maximum over class of functions which are linear in ær, i.e. find that
||
{(x)
max ZEM
(a,
2
convex. In particular, the derivative matrix DT D2g symmetric and positive semi-definite and thus
d 1.
π o = ((; DT(x)))
di.
Lemma 5. Assume that f Rdd IR is C² -smooth and that M = E f(x) = inf f} is closed k-dimensional Ce-summanifold of RRd (i.e. compact and without boundary). If Df has rank d - k everywhere on M, then there exist p., >> 0 such that there exists C¹ smooth closest point projection π U. + with U. = {x: f(x) ()) < a) and I is p-strongly aiming with æ.
Proof. This result uses standard ideas from differential geometry. For the reader's convenience, we provide full proof sketch.
Step 1. Closest point projection. Assume that M is C""-manifold for m 2 2. Fix point 2o E M. radius and the neighbourhood U (zn). We assume that 0s small that there exists a cm--diffcomorphism & U - C R such that @UU M)) = V n {y : yk+1 = ... Dd = 0}. If is mmmmmnofoodd we can find a collection of C -m---s vector fields A As such that
1. A1(=).... ... ((()))...AA(()) span the tangent space T.M for all a e Mnd and 2. (A((2), Ay(=)) dey for all j 1, 1,.., and MnU.
14

---

Published as a conference paper at ICLR 2025
Such vector fields can be obtained for instance by applying the Gram-Schmide algorithm to the columns of the derivative matrix D( D(o=')o(=) = (Dé.) of the inverse diffeomorphism. The algorithm returns orthonormal basis since ø a diffeomorphism, i.c. De has full rank. The first k columns span the tangent space of T . since motion tangential to M in U corresponds to motion where the last d k coordinates are kept zero in V, i.e. to the first k columns of DØ-
We now introduce new coordinates: Denote by V C R the such that V {0a=a) (y yk++
Vd 0} and
V : V x Rd RR
(0, Sk+1...., sa) = (0.0)
Σ 8: A 1=++
The map V is CT l.e--ssmoohh since is linear in and the least regular components, the vector fields A;, are Cim-1-smon (0g, D.... .g.....0.. , A.t is invertible. Hence, the map is a local diffcomorphism by the inverse function theorem. Notably, we see that
in y. If m 2 2, we trivially find that is differentiable and ( =
x (ū. 0) LT
x (0, E span (Ax+1(((00))) 0)). (
and thus if and only if
x = 000.0)
Σ s; ( = ((iss)
k=k+1
for some 8 E Rd-k In a neighbourhood of 2g where is diffeomorphism, we set x (V((,))) (ū 0), i.e
π T 1
Ply Vo) = (V1 (v...... yks .).
The map is as smooth as V, i.c. Cmm-1-smoote (assuming that m 2 2). The map ा defined in this way may not be the unique closest point projection on all of U (e.g. when point z' E M \ U is closer), but it is guaranteed to be the unique closest point projection on smaller subset (2)) where the closest point on M is closer than the boundary of U.
Thus, for every point 2 E M. there exists a neighborhood (z) for r(z) in which a unique closest point projection is defined. Setting U := UZEM (x)=) we find a neighborhood of the manifold M inside of which the closest point projection is defined.
Assume that the radius r(2) is chosen as the supremum of all admissible radii. Then the function r(2) is strictly positive and Lipschitz-contimmuut with Lipschitz-constant 1: r(z') 2 r(2) - -| 2'll since B/-1)===1| S (z). Exchanging the role of 2, 2' shows that
r(=') 2 ((=))\1=-=>))
r(*) 2 r>=))-(2==>>
Ir(=)-r(z') 1 12,z' M.
In particular, if M is compact, then continuous positive function, r is uniformly positive and there exists a neighborhood Ws := {a E Rd dist(x, < 8} on which the unique closest point projection is defined. Additionally, we find that
|| | s) - π (0.
Σ
s,A, ( (0. 0)) = ||$|||
since the vector fields A, are orthonormal.
In Lemma 7, we require π (x(()) to be C*-smooth if zt() is OH-smooth due to the technicalities of the proof. For this reason, we make the assumption that M is a C mm-mffiolld to ensure that æ is C -map For the required smoothness of solutions to the heavy ball ODE, is sufficient to require that f is C²=smooth.
Step The geometry of f. Since M the set of minimizers of f. the Hessian D²2(2) is positive semi-definite for every z E M. As f is constant on M, we for every curve (-c,e) + M we have
d²
0 0= f((()) v (00) + ())()))))))))))))))))))))))))))) = -tt) ('(())))
15

---

Published as a conference paper at ICLR 2025
because f = 0 on the set M of minimizers of L.. v² = M and u E T.M. we assume that D2 f() has rank k for all 2 E M, then necessarily v" D2 f())u > for all which are orthogonal to .M or equivalently
0
v² D'=' 2 {())|Pp] 2
A3 M, u UER" R
where P. denotes the orthogonal projection onto the orthogonal complement of the tangent space of M at i.e.
P. E (o)),( A.(=).
i-++1
If M is compact, then the function À is bounded from below by some λo > Let 0p/2. Using the uniform continuity of n, P and D2 on a compact set W8 and choosing 8 0 suitably small, we find that
of DD 2 P
Ao 201
e||na| >
V W8, v E 5
2
since the map from matrix to smallest eigenvalue continuous on the space of symmetric matrices. In particular, for any fixed (g. s) E V x s we see that the function
g (-8,6) R, g(t) = f ( (g. ts))
is A strongly convex. To this, abbreviate = 2ink+1 s² A0) and compute
d
d² g²(t) = dt f (V.), 0) + tv) = .7 D'
2 (No E) ||0112 = Ao - E
since v Tu(j,o) and ||a|| ||||| = 1. Hence
((V(0, 0)) = s(0) 2 s(1) ( + An م
2
Ao - E ||,o|l²
= =f( 1s)) - (VV 0, ts)) v) +
2
Ao -
= f(((ttts)) + (V ts)), 0) (2i ts))
+
(0 0) (0.tts)]
2
or in the original coordinates of W; Rdd:
f(*(z)) 2 f()) + (((()) z) + An
1| xxx)
By the same argument with reversed roles for x, x xxx) we have
f(x) 2 f(x(2)) + Ao - n (x)]
inf f f+ Ao E
dist M)²
2
In particular: f(x) < inf f + ar implies that
2
2a
dis V An (f(x) V
Ao
Choosing a small enough, we see that the open neighhorhood
Ua = (- f(z) < inf a
a subset of Ws. Within this neighborhood, the unique closest point projection therefore well- defined. This concludes the proof of the Lemma and shows that the Assumptions of Section 2.1 satisfied in this setting.
Remark 17. Controlling the largest eigenvalue the Hessian rather than the smallest, we see that there exist 0 < < L such that
dist(e, S f(x) S L (a, M)2
in neighborhood of U. For this reason, we presented Example for context and intuition.
16

---

Published as a conference paper at ICLR 2025
B PROOFS OF ACCELERATION IN OPTIMIZATION
B.1 PROOF OF THEOREMS AND 8: OPTIMIZATION IN CONTINUOUS TIME
We first prove the 'local' convergence statement.
Theorem 6. /Continuous time convergence guarantee] Assume that f satisfies the assumptions of
Section 2.1, 7 7 = 2V and that To satisfies [(30) <, a where a as Section 2. Then there exists a unique solution z(t) = Tt of (3) and f(x)) < a for all > O. Furthermore, x is C -smooth and
f(x))) inf (E (s(Zo) inf f P dist (M))
=E
Proof. Step 0: Existence and Uniqueness. Note that a solution to the heavy ball ODE can be obtained solution the ODE system
{
i
=- - VV(()). 1
If V is locally Lipschitz-continouus (for instance if f is C²-smooth), a unique C'-solution (x, v) of the ODE system exists by the Picard-Lindelöff' Theorem. Since é is -m-ooh,h, we see that the solution æ of the heavy ball ODE is C²-smooth.
Step Ie remains in Uo Note that d di (f()) + [ = (1t)) + Rr) = (i + VS(),, 1 20,
so
f(x)) S f(x)) 1 2/11011² ? s f(xo)
1
2 || 1| f(xo) <
for all / 1 0 since d = 0. which implies E Un for all / 2 0.
Step 2: Bounding fxx).. Let 2, == TTx)) denote the closest point projection of x, onto M and by
& its derivative. Consider the Lyapunov function
C(t) f(x) f(x(xx))) || + valaz (xx))|1
We will show that Ct( < - (T)((t) under some neighborhood assumption on z₁. Using the heavy ball dynamics and properties of the projection, we can bound (1( as:
(t) (V)) #2) + (ita vilaa x(x))), 3t valli ic) (de, fx()) + R. + Vu - Vu + Vp (st x(x1); Bt + Vu - Vuži)
(ie, V - vuar, > v/l (x+ - 21 -Vust vf(xx) - vuži)
S S-VAl 2 - u(1; - 2z, iz) - v (V f(xx), It -
where used the heavy ball dynamics 3. 2 (f(xz) and the geometric properties of the closest point projection:
1. (it, &)) S 0 by Lemma 7 and
2. (1e 2t, 2 0 since x, z, meets M orthogonally 2, and é, is tangent M zt.
Next, using the μ-strong aiming condition, we have
(Vf(z)), T(2))) 2 f(z)) ((((2))) + Il1z (
Substituting this into the bound on (t) and simplifying gives:
C'(t)= < - Vu | ? - p (x; - (xx), iz) vP (f(z.) - f(x(xx)) + - (zx)))?
- x
= =-VØ (((zz) - f(T(())) + ブ l| + vallse T(x:)) 11 + [
1
17

---

Published as a conference paper at ICLR 2025
< =vvu
Now, we can bound the initial value of the Lyapunov function (()) as follows:
()) = f(xo)= - inf
f(=) + | + vu(2o - ग - (2
=ER*
2
f inf f(z) 1 dis M)2
zERtd
since dg = 0 and dist(r,
= || - π()))| ||. We deduce that
d
evPL C(t) (VūL(()+ ('(())) 50
dt
1(x)) inf ((1) S V C(0) - (f(20) 1 inf f 1 (ro
Next, we prove the 'global convergence' statement.
Theorem 8. In addition to the assumptions of Section 2.1, assume that
1. for every R > inf f. there exists La 0 such that f is Lipschitz-continnoue with Lipschitz constant LR on Ug = {x : f(z) < R} and
2. there exists a value > 0 such that [f(2))| < 6 implies that f(x) inf < 7.-
Then, for any E RRd, there exists T 2 O such that axl) Ua for all 2 T and such that f(x(t)) inf? < (3a/2 + dist(rr, MM?) (e) for all > T.
Proof. The idea of the proof to show that at some large time T, the trajectory enters the set Ua with sufficiently low velocity that it gets trapped in Ma. From that point onwards, the proof of Theorem applies with minor modifications.
Step 1. Denote by E(t) fxx) + } || 112 the 'total energy' of the curve time As in the proof of Theorem find that F1( 22/ | so in particular || is square integrable in time:
00
E(() lim E(t)
f(zo) inf f
| dt
2/77
2/F
Recall for future use that f(x,) I E(t < E()) f for t t2 0.
Step 2. In this step, we show that also (I(x)) square integrable time. To do this, we first observe that
["
+
+ |
[V AVD /' d ( + 4p 1'' || dt.
On the other hand, we can write
S" [V((z) + 2 di di= =
1" (V[(x) + 2u/ 3) dl
T
(Vf(x), 8) dt v (" d
di || dt
- (V) bT) + I (D x) di v |
since do 0. Overall, we find that
5 [f(x)) dt dt= = 4Vn(f(000) f(xr) (Vf(xr), - v/ /11l?
18

---

Published as a conference paper at ICLR 2025
+ ['" (D² 1:00--41111 1pllil/2d1
$ <4/u(f(zn) - inf f) + S/² |1 dt + (V)(
where L L(((oo is the Lipschitz-constant of f / on the set fo: f(x) f(zo)) Note that
t (Vf(z), = dt f(xt)
is the derivative of the bounded function f(x)) E [inf f, [(x)]] and continuous, so there exists sequence of times Tn + oc such that (f) + Since || non-negative integrand. we can bound
[VS(Z)) < lim [VT(([(0)) inf
f) -in
L /'
Th | + (V)()).
-((()()))-nff) fo | 2 dt < to0.
Step 3. Using Steps I and 2, we find that
[++((=)))? + || dt < +00.
In particular, there exists sequence of times such that [z + [t.
as n2 + co. We can therefore choose 7 > 0 such that
[Vf((r)) + || < min a6.
Then we find that
1 | 2 <a + E(T) f(x)) +
[V
f(xT) a,
2 || 1|2 a.
In particular, we conclude that f(x)) < E(I) < a for all 1> T, i.e. I E U. for all 1 > T. Thus, by the same argument as Theorem 6, find that
1
[(t) = f(xx) inf f - 2
a + vu (xx (xx))]²
satisfics L(t) S e vp(t T) L(T) for So
[(x)) - inf < ((1) S eVF(T-() (((ØT) - inn f + マ 1 + valer x(or)))²)
S <evi(T-))
f(x)) - inn f + 2
2 [1 + ||r - (())))]]
S (e
33 [
+ dist(Er,
Remark 18. Obviously, the condition that V is Lipschitz-continuuus on all sublevel sets could easily be relaxed to requiring that the initialization in is such that f is merely Lipschizz-comtinuous the set {x f(x) < [( or even on every connected component of the set.
B.2 PROOF OF THEOREM 11: ACCELERATION IN DISCRETE TIME (DETERMINISTIC SETTING)
Lemma 10. Assume that D2 fxx 2 - in ball (zo). Then
(Vf(z),r - 2) 2 f(x) - f(z)
E
||
2||
2x,2E E (xxx).
2
19

---

Published as a conference paper at ICLR 2025
Proof. The function f(x) +21122 $|[=]| is convex since all eigenvalues of its Hessian D + El are non-negative, so
((2) + |= (xx ||-|| (V)(x) + +ex x²)
which is equivalent to
(VI(x), 2)2 [(x) - f(z) + 2 || + + 2- x) ||=1|²
= =(x) f(z) + ||/11 + ((x, =||ar|1 ||
= f(x) - f(z) 2 =122 z1|2.
Before proving Theorem 11, we recall well-known auxiliary result.
Lemma 19. (Gupta et al., 2024, Lemma 13) Assume that V f is Lipschitz-contimmuus with Lipschitz- constant L. Then
+ Tnp
ng) S f(x)
2 1|911.
Theorem 11. Assume that f is I-smooth and the sequences In, x'n Un are generated according to the Nesterov scheme (5) with parameters n S L/L and p (1 /pT)/ (1 /pri.. Assume further
that there exists an affine linear projection map (x) = Pr + x² such that
(V(()) xxx)) 2 f(x) f(x(x))) + こリr || (x))1
(6)
Finally, assume that for arbitrary v, u E Rd we have
+ + - f(x) ||a|| [V z ((x+
(7)
with some E S Vu/n. Then
f(a,) inf f < (1-11111) " [f(0)) - -nf f - 1| T (
Proof. Setup. Denote by P+ II P the orthogonal projection the orthogonal complement of the space which P projects onto. Consider the Lyapunov sequence defined by
C. = [(r)) - inf f + _ pl on + Vala, - 71 2(1 Vjm)) |P
(1 + vun)
This is variation of the usual Lyapunov sequence which we separately analyze the tangential and normal velocities. Note however that
(uT)
O(VT).
(T)
Le. if - O, recover the Lyapunov function in the continuous time setting where tangential and normal velocity are not separated:
(1 + 2
P ut
Pull |
2(1 v
17 + 0 since the vectors Pv and p- + x (x)) are orthogonal and v = Pv + p-v. We want to
show that Ln+1 < (1 C.. Note that 1 ymn 2 1 V 2 since S L by Lemma 24.
For simplicity, we assume that x² 0, i.e. x/ (+*)) 2/, Pa', P-
Step Since f is L-smooth and 17 5 1/L, we have
f(aat1) f(()))
Taj
" nIV[f(()))1 f((h)) " |
by Lemma 19 with =x', and g (((a())
20

---

Published as a conference paper at ICLR 2025
Step 2. We compute
P-u VTP /TPP-Wnt1 P-u11 + VTPP (Inn + 7 - (V((E())
-Pp /1mpP-))uTT + VIPP'a, -VVP--(((()))
= =p(1+ Vum) on + VPP xn VT(Viq + p(1 vAVT) p(V)()))
(1 - V + VuP- (T
where we simplify the coefficients in the last step by substituting p 1t
1-van So.
1 p un + vuP- 1nt1 11 (1 - ) 2
PP unll 2 -1Pp- x' 11 + ((
2
2
T v1m) (P- Una: p(rn)) Vum (V)(s)), P p'
(1 - vum) (VI()'),,, P vn)-
Recall that since both P and PL are orthogonal projections, for any I.Y E Rd, (Px, Pv) (Px, y) = (x, Py), and the analogous result holds for pl as well.
Step 3. Now we expand the last term in the Lyapunov sequence.
(1 + V
(1 + v
2
|Punt1l2
p² P' (MVI(=
2(1 / pm)
2(1 VPT)
1 - yun
(1Peoll
2 + P| - (()))
2
Step 4. We add the expressions from the previous steps and use the fact that Pv, + P- Un = = to
get
(1 - v/un)2
Cn+1
| 1n
L 11P22111 + 272 p ((
+ VT((1 - VITT (P- Un, p(ay)) V (V} p
uPT Pú,
VT(1 VHT)
2
77 - (m))
|P f(xa11) - inf f.
2
Using (6) and (7) to bound the inner products
(VI(s)) v.)) and (VS(x))) P P-
Lat1 S (1 v/m)2 ||P- Un $1 2/ + " " p [(
P
+ VT((1 - v p- Un, p+ - v (5((n) - inf f +
!1
p p 112)
2
(1 - viJ) (f(2/)) - 1
- E 1|
-
=))) +
vun
|Ponl1
2
(7(1 V PVV + (x(h)
"
| f (1(²) (x/))² 11 - inf ʃ.
2
Now, we use Pythagoras theorem, i.e. for all w E Rdd || Pw|l 2 + || |P w || = |l p w/| = ||w|1 and rearrange some of the terms,
Cnt1 (1 2 + (1 VIMiiNE
(1 v (1 + 1)8)
Pu 11
+ 11(1 (TT))
VT VT
2 | 11 + |[
IP 11
2
2
VTi(1 -um) (P Un: p
(1 y +
+1 (f - inff). f).
21

---

Published as a conference paper at ICLR 2025
The coefficients of f(², and [=l)2) are and the coefficient of PV f(,,) is negative, so we can disregard those terms. If Σ Vp/n/, the coefficient
|| PP-val ||2 can be bounded as
(1 (1m pm + nE)
(1 - (1) v pm + v pm
2
and the coefficient of |
Un 1| can be bounded as
(1 v + ne)
(1 (
(1 + STOn) 2
2
2
2
Thus, we conclude that
Lx+1 S (1 - (IT) inf f)
| Un 1|
2
nd - vum)
p 1+21111 + v/((
/uTi Uni p dnn)
2
+ (1 + vPT))² ?
|U 1
2
(1 v Ln.
Consequently,
f(zn) - inf S Ln S (1-vp)))" Lu = (1 (1-v [f(z0)
inf f + " "I 20l 2
B.3 PROOF OF THEOREMS 13 AND 14: ACCELERATION WITH ADDITIVE NOISE
The proof of Theorem mimics that of Theorem with minor modifications to account for stochastic gradient estimates. Since Wn is stochastically independent of anything which has happened in the algorithm before, in particular of 2i Un, we have the following.
Lemma 20. For all n E N. we have
IE (9(2)) V v = E V (2()111
B[(o(T wn), vn E V (z ( w..)
E Ko Wn), pl p' E (VV) P P'
Bllggn 12] = ((P) + E[llsn - VS
where the expectations taken the (potentially random) initial condition To as well as the random coefficients Wo....,w, which govern the gradient estimates.
A proof can be found in (Gupta et al., 2024, Lemma 15). The second identity, which is not included therein, can be proved analogously. As an application, we prove a stochastic analogue of Lemma 19.
Lemma 21. Assume that I I--smooth and E [llg w) [=)) S o + o [>))] for all
x E Rd. Then, if x. w are independent random variables, we have
Beew [f(r= [g) < [[f(())] (1
L(1 L(1 n 11]
+ LT 0
2
Proof. Recall that for any x, n.9: g, the following holds
Ln²² 2
s(x n9) S f(x) (V))())))))))))))))))))()))))))) +
||0|
by Lemma 19. We now assume that g( w) is random estimator for V Vf(x), where may be random, but w is independent of æ. Then, by Lemma 20, we have
Ln² E [[|a|]]
E [ - (g)n s El((()
E [
2
Ln²
= =E(((>) --E||//(>))) +
{
+ E vf(
2
22

---

Published as a conference paper at ICLR 2025
Ln
+ Lnp²
1 [B[(()]]
n ]
2 {o2 + o BI
(1
L(1 + o mn
[[[[vf(>)| + Lni
= =B[f(z)]
n
2 o..
2
Finally, we provide an auxiliary result to resolve recursion. Lemma 22. Assume a sequence In satisfis the recursive estimate In+1 S atn + b for a E (0, and b 0. Then
In S a
30 1 - a
Proof. Consider the sequence yn In + h Then
a-I
b
az,, + ab
Bn+1 In+1
a az
+ b
a a.
b
a
a -
b
In +
ayn
In particular, Un S aa"Yor yo. so
b
b I
In Un 1-a a
a"
a a-1) 3o
If b 0, the estimate follows since b/
O.
We now prove the first main result of this section. Theorem 13. [Acceleration with additive noise] Assume that P.P are in Theorem 11 and that the g satisfies (8) and (9) with om = O. Assume that the sequences Dn, Fy Un are generated by the scheme (5) for parameters di I/L and 1- yun but with the stochastic gradient estimates 14//pn'
g( wn) with independently identically distributed wn in place of (((")) Then
inf f + 11 I1 {(x)))1 [f(Zo)
o² V
[ff(x.) - inf f] S (1 /pm)"
2
Vp
Proof. The proof is mostly identical to that of Theorem 11 with minor modifications: In Step 1, we obtain the estimate
Lo
E [[ [[f((, //l
2
by Lemma 21. In the quadratic terms steps and 3. we need to take the expectation of In rather than V fa(")) By construction, the terms involving [[I| f (a,,,) [] still balance with the same parameters, leading to an additional contribution of r o due to the stochastic gradient estimates. Since S 1/ L, we can bound T.72
overall we obtain the estimate
L I (1 Cn + o.
in place of L.+1 < (1 / Cn since all other terms are identical under the expectation using Lemma 20. The claim now follows from Lemma 22.
For readers who are looking for a more detailed proof, we note that Theorem 13 a special case of Theorem 15 with am = 0. where we provide full proof.
In the same spirit, we sketch the proof of Theorem 14. Let us recall the statement.
Theorem 14. [Additive noise and decreasing step size] Assume that f, are as in Theorem 13 and that the sequences Inz 2n1 Pn are generated by the scheme
dn4- = I 1un
En+1 x'/ Tngun
Unt1 = (v. (nng))
for parameters Th
1-/00= ItVpT=
Ife S / /p/1o + v LLg, then
[B[ - inf f + 1110 - m( |2 + - log (1 + nY 1/L)
V
E[f(x,)) inf fl
n LLP
23

---

Published as a conference paper at ICLR 2025
Proof. Note that in the proof of Theorem 15, we build on the relationships
((x++1) S f((rr)
"hn
[V
2
2n = n - 1n9n + vnnun Un+1 = (r va.g.))
and do not enter further into the recursion. We additionally note that if 1n is monotone decreasing sequence, then the sequence An+1 == (++/m)))
1-vam is also monotone decreasing. Hence, if r/a I [(1405] for all n E N. then by the same proof as Theorem 13, the sequence
Cut1 == f(an) inf f + /
1
p.v, Un + +VTP
An
P
satisfies
Ln S (1 (1-vmmm) f((n))
inf f + 1 < (1- Vmm))) fon J.'n
2 |lpto + v P- x'x
Ant1
| 1
2
if the parameters are chosen as in the theorem statement. If specifically 9n- p (n+no+ip for
no = pL/ then
Lu+1 S (1 + nu + + Ln + p(n + + 1)2
n + n1
o p(n + nu 1)2
Ln +
+ no +
Thus the sequence Zn = (n no) satisfies the relation
0²
o
2nt1 = (n + no + 1) S (n + nn) +
+m++n))
2n +
u(n + no + +1)
u(n + no + 1)
80
n
o²
o² n-1
2n 20 +
2 2k 1)
S 20 +
S noLo +
dt
p(t + no + 1)
no +
02 log
n2 1 1+
S SnoCo Co +
710
Overall, we find that
B[((xn) - inf s| < Ln
Zn
+ no
V 4 [f(xo) inf inf f 11l (xo)]1?]
- log (1 + n-1
n +
B.4 PROOF OF THEOREM 15: ACCELERATION WITH BOTH ADDITIVE AND MULTIPLICATIVE NOISE
In the strongly convex setting, Gupta al. (2024) state version of Theorem 15 in slightly greater generality in terms of choosing variables. The same more general proof goes through also here after account for the tangential and normal components of the velocity as in the proof of Theorem 11. Theorem 15. [Additive and multiplicative noise] Assume that f, P, x² are as in Theorem 11 and that g is family of gradient estimators such that (8) and (9) hold for some oa, o. 0. Assume that the sequences nn, z,,, Un are generated by the AGNES scheme (10) with parameters
Ito
Vu + +0.00
0 0< (11+02))
P
a 1- 1-VP(1 +
1
1+o.
Then, if < / 11( + -.22///, we have
n
σāv / 1 + oz
E[f(2,,) - inf f| < 1 o
um
E
f(10)
inf f f+ 11 ||:00 a(z0)117
+
24

---

Published as a conference paper at ICLR 2025
Proof. Setup. Mimicking the proof of Theorem 11, consider the sequence
> A [1IP 1 E [| ' un + +a(z'n =xxx))) +
C, === -1(=)
2
for constants
o am
(b vun)² 2 b Vuy Va
b
where 7- --v bVa.
The constants will be motivated below where they are introduced. Note that we have '/ if = 0 and thus b = 1 and = Va, recovering the situation of Theorem 13. We want to show that Cn+1 S (1 v /a) For simplicity, we again assume without loss of generality that (2x) = Px, i.e. x 0 throughout the proof.
Step 1. Consider the first term first. Note that
(1 11-
L(1 , [E[[V]C()11]] + 2 d
Laf
E [[((n)))]] = =[[s(a
- ngn)) S [x])]]]]]
2
Lap² 0a
< [B - E [[][(>>))))
if 17 S I(1402) by Lemma 21.
Step 2. We now turn to the second term and use the definition of x from (10),
up-1 + vuP- r = bp- Un+1 + vup (2', + v un+1 79.))
(b /ua)pp- (un vāgn)= + vup-a2 VIIPptg On
= (b + vua) Un + vuP-t (VTm + p(b + /uaa Vo) p ga-
In analogy to the proof of Theorem 11, we have p b+ so
b-ypa
bp- Unt1 VTP s/111 = (b v ma) P on + vpP J/n (Vin Tin - (b via Va) gn-
In the deterministic case where 7) a, the coefficient vu(n a) b of 9n simplified to b/ It does not in this more general setting anymore, so we introduce notation: 7 a)( +bya. Taking expectation of the square, we find that
bp- nn+ + V P-PP--1 1' [1a]
E
(b vua)² 2 E P un ||| + 2/plbb Vua) Un P
+ a ( 2/,l"
2(bb Vuaa 7 E (9m: p+vn) 2/17 E (ynn p p ] [ 13
= -bb- / [1[| [[||Pt
un || + 2 2//x(b vuax E P w + xB[ P 2 [2]
-2(b B
p- un)) 2 B +.)] + 2 13..
Step 3. We now consider the third term
AE [1]
[
>p² E P(u Vagg))
Xp" E Pu, 1 all Pgn 12 2 Pv.))
= Ap² E [] Pu, 2| + all Pgn 12 2 (V())
Step 4. We now add the estimates of steps and 3, with
A (b Vua)r (b + v/aa}² 7
Viai Va such that the coefficients -2(b VuaLy of B(VF(*))) |_ and -2Ap2 of EKVF(=)) Pv.)) coincide. Note that in the deterministic case 7 b/a Va and recover the coefficient chosen in the proof of Theorem 11.
Vaa
E [[|bP* Wati TaPtaaalll + X|| [19]
25

---

Published as a conference paper at ICLR 2025
(b V B || Un [2] + 2//(bb Vua) (P Un. 2/11 + |n
|EE[|PP 2²,11²]
B( P mn (b vualy va E [|| P [|3
2(h - 10-Vvuuj) (oy R (1t)),
+ + g. |||] + (b- vua) V I??]
We note that the coefficient of the norm of the tangential gradient is (b- jaci)aaa S 72 by the definition of (b /uaa va v/n, Next, we combine this estimate with the bound on f(2++1) from Step and use the geometric conditions (6) and (7) on ff to control the inner products of f with e and P-xx, in the previous expression as well as the variance bound (9) for the gradient estimates:
Lu+1 I (((( inf fl [[ 72
Taf 2
19mn
+
0a
+ (b /
E8 || 11 + vu(6 - vaa) B ( Un الاايم + 2 -
2
(b Vua)
E ((1h)) - [(xm)
Ea
Va
V [((xx) inf f 1
|P"2211 2111 + (b - /
E E|l|Pon [2]
2
2/aa
1 (b v Va Vun)
B[[([()]]
- (1 - -Vrr) inf f + (b- vpa) Ja (If(2
Va
+ (1 + oih) 1
LTp² 7 oa
E ff 11
2
+ (b Vua)²
) (b-
pa /pajssVa
E B[||
12| + Vu(b vua E (P-2' p p-)n]]
2
4 Viril
(b- /ua + Ea)
+
B[I|Pt
E
x 112]+
E 1
2
2/a
Step 5. Recall that
a 1 1un(1 + )22)
(1 + 02 )a
11(1 2zn))) 02 1/, b=
11
and thus
b Vua
(1+
V/a
1
v
1
ky
p b 100e
+ V/a
1 V 1
un
as desired.
Let us verify that 7 Va/b. b. This is equivalent to
1 + 02
1 | 02
Vū(y aa) a) +
vu at Vun- v 1 oz
-0
11
1
02
11
i.c. to the choice
I+o4
Vum
Vi+0z
1- Vun(1 + oz,)
a
"1
1 + 0% v /uun(1 + oz "1
+
oz
which we made above. In particular, we find that
(b-vua) 7 Va
b + VHy (/a
- VT+ vT)) == by Va
=1
and therefore
(1 (1-(1- (b
100k) Va
Vi7) B[ + - (1-
inf f + (b
Vaa)
7 E(s(x,)
Va
26

---

Published as a conference paper at ICLR 2025
= (1- B Bf inf fl.
In the coefficient of E [ ||² we have the cancellations
(1 + ) lj = (1+ m 6a (1 +
17 =0 )
By the same analysis, the coefficient of additive noise is
LTf + +2 Laj +
7
1
so overall
Lij² I+ 0
Ln+1 S (1-vTin) (((())) - inf in f]
+ (b vpa)² (b /ua)Enva
E[|Pen| [1]] + v - BBaaBB (Pt oin p- vn)]
2
a² VaN
(b - Vua) +1+ E E|||Pr,,11" 11.
2 E n 1 +
2/a
We now analyze the terms corresponding to the quadratic terms. Using 7 va/b b, we obtain
(b / + (b- vpalerva
(1 vua
1 (EY - vAVa
6a
b
(5y vuVVa
= (1 v(²))
|
$ Vu7
for the coefficient of [[]|u, [] ey S a, i.. i < x
v
=
p(ltom))
Analogously, we see that the
7
coefficient of EE [ [P- P- . that
vn,
pa
(1- v
va
VT(b v max))
jub
Vub
= vTb((1 vTa)
b
b
and for the coefficient of E |P
1 that
2]
7H 1 Viy. v
Before proceeding to the next term, we observe that
1-
V (m 02)
I+ 1 1+ Vun + 02)
aa,
and hence S v//T S viry aa Finally, note for the coefficient of E Pe, that
(b (1 + Ea)
(b - /uajy(1 ea) ViooVa
Val A
Va + //Oa)²
2
/aa
(1 + Ea)
+ /ua
Vua
2
(1 + Ea)
= (1 v (1 + Ea)
$ (1 2 (1 VHn)
(1 vTT) (1-133)
< VPn
27

---

Published as a conference paper at ICLR 2025
as desired. Overall, we find that
6²
Lx+1 S (1 - v Blf(xn) - inf +|+
Elll Un [2]] +
E
tbb Ons
2
Lnf + I+o
+ B [[ 24 [13] + A [1ll 11
+
2 0²
(1 Var) B[s(en) inf /
un + 2/,1 + 2 B(Iiuuu11]
2
Taf² + 7
I+0
+ 2
0
Laf +
T+am
(1 Vun) Ln +
0a
2
By Lemma 22, deduce
Ln S (1-v11))" +
Ln² +
Itol
da
2
L(1 + o )n +
2/10
2(1 + o%h) 1 +
Since L(1 + o S 1, we can simplify the noise term to
L(1+021)7 + 2(1 + o /n/(1 + oN))
S Vu(1 o
C A BRIEF COMPARISON OF GEOMETRIC CONDITIONS FOR OPTIMIZATION
C.I DEFINITIONS AND ELEMENTARY PROPERTIES
In this section, we compare some common geometric assumptions in optimization theory. Recall the following notions.
Definition 23. Let U C Rd be an open set. We say that -u-nctioo f:U + R
1. is quauaar conver if argmin f * 0 and the inequality
(Vf(x), x - x²) 2 (f(()) - f(x)))
holds for any x U and any x² E argmin f.
2. star-convex if it is l-quasrr convex.
3. (7: (r.P))ssrongll quasar convex if argmin f + and
(V((z), - 2 (f(x) f(x*) + -| x 112))
4. is first order p-strongly convex if
f(x) 2 f(x) + x -2) -1 z|12 V
5. satisfies the first order pu-strong aiming condition if for all x we have
f(x(x)) 2 f(x) + (Vf(z), - x) + - - {xx)|2
VEEU
where
π (Φ) = argmin
| - 2|12 :f(=) inf e'e
f(x')
In particular, we assume that the set of minimizers is non-empty and that there exists a unique closest point (x) for all x E U.
28

---

Published as a conference paper at ICLR 2025
6. satisfies PL condition with PL constant if
|V 2 2p(s(z) -nf
If is convex set, the fourth condition of course equivalent regular pestrong convexity.
Lemma 24. 1. If f is first order p-stroogly convex and has minimizer in U, then f satisfies the y-strong aiming condition.
2. If f satisfies the p-strong aiming condition, then f satisfies the PL condition with the same constant μ.
3. If f is j-strongly aiming on Uu fx E ERE f(x) < a.. then the line segment connecting x and <<x) is contained in Ud for all Ua.
4. If f is L-Lipschitz continuous on Ua and satisfies the PL-inequality with constant on Uay then p T..
5. If f (tttoolyy quasar convex, then argmin f consists of a single point.
6. If f y-quasar convex and is star-shaped with respect to the minimizer x" E argmin then all sub-level sets of f are star-shaped with respect x". In particular, the set of minimizers is convex.
If U = Rd, then any strongly convex function f f:U - IR has a minimizer in U. On general open sets, this not guaranteed.
Proof. First claim. If f is first order pestrongly convex and has minimizer in U, then the minimizer x' is unique since for x * x² we have
f(x) 2 f(x)) + (Vf(="),x-"") -
1|
f(=)(((+++++) / x²112 f(x").
In particular, for every x there exists a unique closest minimizer x (xx x² The strong aiming condition therefore requires the first order convexity condition only for pairs of points x, x² rather than all points I, 2.
Second claim.
This result follows by the same proof that implies the PL condition for strongly convex functions: f satisfies the p-stroog aiming condition, then
(vf(x), x - x(x)) 2 f(z) - f(x(x)) + " || +x))]
and thus
[ff(=)] 2 Vf(z). x T②))
1 T(=)||
f(z) f(x(2))
1 (x))| + 1 (a-=((x)
[xx) - f(x(x)
min
{>0
Setting the derivative with respect to & to zero, we find that the minimum is achieved when
f(x) f(x(x))
P
2' so = 2(f(x) -inf
inf
g²
P
so
(f(()) inf f)
2 (f(x) - inf = 22 (f(x) - inf f).
2 The PL condition follows by squaring both sides.
2
Third claim. Let v; = (1 - ())(x) + la for < 1. First we observe that (ar,) = π (x) for
every t [0, 1]. Indeed, if there is another minimizer of such that I|x, 2|l S ||,,, (x)) then
Jar (>))] || sell | क (=:)] s ||x 2r + || =1 S || =||
29

---

Published as a conference paper at ICLR 2025
since æ, zt, and (xx) all lie on straight line. If there exists unique closest point I (2)) in M, then we find that & = (z))
We note that 22 (2) =((x= n (x)) and thus
di [ =( (V)()) - xt - (x+))) 2
d
In particular, + f(ze) an increasing function on the set 1 {t 0: x, EuJ- If has
multiple connected components in (0, 1). this is only possible if f = on the boundaries. If on the lower boundary of connected component, then f 2 inside the entire interval as f increases, contradicting the definition of Ua.
Fourth claim. Since f is continuous, Us open. Therefore, 2 == 2t (V](s) E U, is small. If is I-LLipschitz continuous in Ma then
f(x)) - f(x) (f(z), Iz - -x) -| 1
for all t such that Ia Ua for E (0,t) and I 1/L by Lemma 19. Since the function t + f(x)- - [ is decreasing in t, we see that I E U, fort E [0, 1/L). In particular, we note that
2μ (f(x) inf f) inf
0. f(x Vf/L) inf f(x))
2L [Vf(()] inf f f(x) 2L
$ (1 - (f-)) - inf
implying the result.
Fifth claim. Assume that x²,",= x² E argmin f. Define = txx + (1 t)x'. Then
di ((m)) = (V (VS())), -x') (V/ It x'
2 7 (S(r.) min f + b 11 x' x²((²)
unless ||ar 2212 0, i.c. unless x= x'. Thus f(x) is strictly monotone increasing on {t [0, 1] It E J.. Since x¹ U. this means that must be strictly increasing the final segment
(1 - 1. where it reaches the global minimizer x² at = leading to a contradiction.
Sixth claim. This follows by essentially the same argument as the fifth claim: If x is any point, then to (1 t)x* E U since U is star- shared about x and
dt f(aa) (Vf(x)), - x²) = (xx)). Ft x² ) 2 (f(x)) ff(==(())))))))))))))) 2 0.
In particular, f increasing along any rays starting at x", so if f(x) < a, then f(x)) < a for any
t [0, 1].
The set of minimizers is star-shaped about every minimizer, hence convex.
C.2 A ONE-DIMENSIONAL EXAMPLE
In the following simple one-dimensional example, we illustrate the hierarchy of geometric conditions between convexity and the PL condition.
Example 25, Let > and E (0, 1). Consider the even function given for x > 0 by
f(x) = + e sin log w) 22
2
f(()) = (1 + = (2n x) + Rs cos(2R x))
fx(x) + sin Ra cos(2R æ) 2Rs cos(2Rlogz)) - 2RR sin(2R log x)
1 + e(1 2R²) sin log 3)) 3Re cos(2R x).
We first note that evidently عبا x² < f(x) & ي x² for all r. In particular, x² = 0 the unique global minimizer of ʃ.
30

---

Published as a conference paper at ICLR 2025
L-smoothness, The function g(E) (s)((E) B cos(E) attains its maximum when Acs B
B Biin ç = 0 for A, B E IR, i.e. sin VA and cos A + B2, so
A
VA In particular maxg g(
(x) s1
+3R)2 = 5R + 4RR
The second derivative is discontinuous x 0, but bounded R {0} by L 1 evi + 5/2 + 44R2, i.e. L-smooth.
Convexity. By the same consideration, we see that f is convex if and only if f" 2 0, i.e. and only if Ev + 5R + 4R < 1. the inequality is strict, f is strongly convex with constant
== 1 -v 5R + 4R4
PL inequality. By the same argument above, we that
[r(x)) 2 (1 + e sin +Re cos) )os))²² 2 (1 (1-8V1+ n2) x²²
SievI+ R2 < 1, where all trigonometric functions are evaluated at & = 2R 2Rlogge x.
In particular, if if R then
1f(x)) (1 (1- R2 2
22 (1 (1- RP)
1+E
(1 (1-EV1+ 2v1++ R2
x² 2
f(x),
1+
2
1+E
ie. f satisfies the PL condition with constant
(1--v/ 8V1 + 12)2
1
Infinite number of local minimizers cluster at the orgin. 1ev + R on the other hand, then by the same argument f' changes sign infinite number of times in any neighborhood of the origin since lim log æ = -c.
u-strong aiming condition. Note that
f'(x) f(x)
-
1
+
sin( 2R loglogz) + Rs cos(log x) x²
2
1
2 - (RE)2 x²
2
(1 - E 1 4R² x².
2
In particular, f' is ju-strongly aiming (with respect to the unique global minimizer) with
#= / 1 442
if (fev (TevI+ ARE < and fails to be p-strongly aiming for any >> 0 otherwise.
Quasar-convexity Since the minimizer is unique, (7, (t)-strong convexity is strictly more general notion than strong aiming condition as we have an additional parameter to relax the requirements. Essentially the same calculation reads
z. f
(1 7
((1 7/2) sin(...) + R cos(...))) x
7 - ((11-11110 2 + R2 x²2
2
In particular, f is 7-quasar convex
7 2
8 -1
R2 20
+ 1- 14
R
20 0
1 1 7/2
31

---

Published as a conference paper at ICLR 2025
871
309
300
300
1240
Figure 4: We compare the trajectories of gradient descent and Nesterov's algorithm for the objective function in Example 25 with R = and = 0.075 (left), = 0.08 (middle) and e 0.085 (right). Evidently, if <v 4 is very close to the threshold value 1, gradient descent outperforms Nesterov's algorithm with the theoretically guaranteed parameters.
1
1+ 1 11-7/2
S E2
Such y can be found if and only if R² < -يا Choosing slightly smaller, it is then also always possible to make f (3',n()=stronnly convex for some > (0,7) and μ 0.
Relationship between conditions. We quickly summarize the various parameter ranges for which the function f satisfies good geometric conditions.
condition
μ-strongly aiming
f--strongly convex
Must be <
EvI+R* R
4R
Ev EVI+ 1I++5R* 4R
Constant
[1-sv[+R2) 14f
1-
4R
- 1-EVI+ 5R + 4R
Evidently, classical strong convexity implies strong aiming condition with respect to the global minimizer which in turn implies the PL condition. The parameter ranges and constants are generally vastly different. All estimates, except for the PL constant, are sharp. In particular, the one-dimensional examples demonstrate that strong aiming condition is strictly weaker than convexity along the line segment connecting to (Ix).
In the case of quadratic objective functions or functions modelled on them (such as the distance function from manifold), the PL constant is essentially the same the parameter of strong convexity. For the function parameter of strong convexity with respect to the unique minimizer. In Figure 4, we observe that with the parameters 7) = 1/L and = (1 /ur)/(L (1+ + y gradient descent may at times converge faster, at least with the parameter choice that is derived over a large function class rather than for an individual objective function.
Example 25 on the other hand, the PL constant is noticeably larger than the
C.3 DEEP LEARNING
While some notions of 'good' geometry are weaker than others (for instance, strong convexity implies the PL condition but not vice versa), they all share an important common feature: If x critical point of f. then is a global minimizer. Namely, the PL inequality implies that [V) > unless f(x) = inf f and 7-quasar convexity implies that Vf(x), -xx) > 0 unless f(z) = f(=)) inf f. showing that V fz(z) + 0.
In deep learning applications, critical points are guaranteed to occur under very general circumstances:
If
W,b;,) = 3
Σ (w) x + b)
32

---

Published as a conference paper at ICLR 2025
is neural network with single hidden layer and C' activvatio function satisfying o(0) (e.g.
tanh), then the loss function
a(3 a, W)
W.bxz) -v y!
j=1
satisfies
VL W; = 0
for a = b= E R", W ==0e
O Rnd and 3 = Σ M/j- The same is true if a row of W is merely orthogonal to all data points 2j but does not vanish.
For deeper networks, the set of critical points becomes larger: As long as the parameters of two layers are all zero, the remaining layers can be chosen arbitrarily. If more than two layers are all zero, then the also the second parameter derivative vanishes. In particular, the critical point for which all parameters are zero cannot be strict saddle point.
While there guarantees that individual algorithms escape certain types of critical points almost surely (e.g. strict saddles, (Lee et al., 2019; O'Neill & Wright, 2019)), they may take very long to do so (Du et al., 2017). The analysis of accelerated rates becomes asymptotic at best. We claim that our notion of strong aiming condition suffers from the same 'optimism" globally, but locally captures two important features of deep learning landscapes close to the set of global minimizers which are not captured by concepts which require geometric condition with respect to all minimizers: A manifold along which we can move tangentially, and convexity directions which are perpendicular to the manifold.
33


Reviews:
[{"review_id": "Scpwi9bIPq", "reviewer": "Reviewer_jZe8", "summary": "This paper presents an analysis of NAG that proves accelerated convergence rates in some non-convex scenarios, using assumptions on the loss function inspired by overparameterized deep learning. The authors analyze continuous time with deterministic gradients, discrete time with deterministic gradients, and discrete time with stochastic gradients (and multiplicative noise), showing accelerated convergence rate (better dependence on condition number) compared to gradient descent/gradient flow.", "questions": "1. I'm not sure to what degree the proof of Theorem 7 requires novel techniques. The authors mention (Line 324) that their overall proof strategy is common, and the contribution comes from their Lemma 1. I am not too familiar with this line of work, so it is hard for me to judge the novelty and non-triviality of Lemma 1. Can you elaborate on the technical contribution of Lemma 1?\n2. Do you believe that similar ideas could be used for non-smooth objectives in future work? For example, the objective function for training a ReLU network with squared loss is almost everywhere continuously differentiable, instead of continuously differentiable (as required by your assumption #1). Could this gap be addressed with the kind of techniques used in this paper, or might this setting require entirely an entirely different approach?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper is very clearly written. Previous work is totally explained and the authors are very straightforward when describing their novel contribution (Lines 42-51 and Lines 106-107).\n2. The convergence rates are a clear improvement upon previous work, which either achieves similar rates with stronger assumptions or achieves a non-accelerated rate for gradient flow under a similar setting as this work (aiming condition).\n3. The authors are straightforward about the limitations of their work, which I appreciate. In Lines 253-260, they mention that their global assumption on the loss geometry can only be guaranteed locally. Still, it seems that the assumptions are weaker than previous works (e.g. quasar convexity), so I think that this is acceptable.\n\nI want to mention to other reviewers/AC that I am not too familiar with this particular line of work, so I am slightly less confident about the technical contribution of this submission. However, according to my best judgement, the contribution seems worthy of publication.", "weaknesses": "1. The assumptions are inspired by overparameterized deep learning, but are unlikely to be completely accurate. This authors already comment on one instance of this (Lines 253-260). Another instance is the requirement that the objective is $C^1$-smooth (Line 114), which is not satisfied by non-smooth activation functions. Still, the assumptions are weaker than previous work, and I believe these gaps are very non-trivial to address. This is a minor weakness compared to the strengths of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cTNkhomBDQ", "reviewer": "Reviewer_jpMm", "summary": "This paper studies the convergence rate of momentum-based optimization methods under more general conditions than (strong) convexity. Motivated by existing works, the authors assume a localized version of strong convexity that allows for multiple local minimizers. The authors provide examples of such objective functions and also show empirically that the assumption is reasonable in deep learning applications. By considering a continuous-time ODE, the authors characterize the behavior of momentum-based method and prove accelerated rate compared with standard GD. The setting of stochastic optimization is also considered as an extension.", "questions": "I do not have any questions for this work.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Overall I think this is a nice paper with interesting contributions to the optimization community. I like the writing style of this paper, especially for the concise introduction and discussions of relevant works.\n\n2. This paper justifies the superiority of momentum methods under weaker assumptions than strong convexity. Moreover, the assumptions made in this paper are supported by empirical evidence.", "weaknesses": "While I do not check all the proofs, the paper does not seem to have many novel technical contributions compared with existing works on ODE modeling of optimization algorithms. I'm not sure if this should be considered as a weakness, since the results themselves are interesting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7NZHna7pbc", "reviewer": "Reviewer_4krH", "summary": "The paper presents convergence analysis of Nesterov Acceleration for nonconvex functions. Some (geometric) assumptions weaker than PL inequality are employed to derive convergence results for NAG.", "questions": "See weakness", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "There are some works have been reviewed in the literature, both from the line of momentum algorithms, and the geometry of deep neural networks. The paper is well-organized.", "weaknesses": "1. To the best of my knowledge, both from theoretical and practical perspectives, the momentum methods commonly used in deep learning are based on the Polyak Heavy-ball method, not Nesterov acceleration. However, the paper under review focuses more on Nesterov acceleration, while mentioning motivation from deep learning without any references. Could the author carefully provide sufficient references to support this motivation?\n\n2. The main contributions of the paper in comparison with related references is unclear. Could you state them more explicitly, discuss them in greater detail?\n\n3. The paper lacks a thorough literature review. For example, a unified convergence analysis for momentum algorithms has already been considered in Josz et al. (https://epubs.siam.org/doi/abs/10.1137/23M1545720?journalCode=sjope8). Could the authors please address this paper carefully and consider the references therein to better position their contribution within the literature on Nesterov acceleration? \n\n4. The assumptions in Section 2.1 seem too strong, as they imply the PL inequality. Recent works, such as Josz et al. mentioned above, require only the KL inequality, which holds for a significantly larger class of functions encountered frequently.\n\n5. What is the connection between your continuous-time and discrete-time analyses? While the discrete-time analysis is of primary interest, the purpose of including the continuous-time analysis is unclear, aside from serving as additional motivation. If the continuous-time analysis can be directly applied to derive results for discrete time, its inclusion is entirely appropriate. However, if it is independent of the discrete-time analysis, I do not think it should be included unless carefully justified.\n\n6. The numerical experiments are too simple. Could you include additional experiments on practical classes of nonconvex functions, such as those commonly found in deep learning?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YmtUk56ahY", "reviewer": "Reviewer_cdrW", "summary": "Motivated by nonconvexity of deep learning objectives, this paper studies the  heavy ball method under relaxed convexity assumptions. The continuous time, discrete time and stochastic algorithms are investigated. Some toy experiments are presented to illustrate how the convexity assumptions hold in practice.\n\n\n------- AFTER REBUTTAL -------\n\n\n**I raise my score to 6. The author(s) present interesting and sufficiently new contributions, but the paper needs strong revisions in terms of presentation and redaction.**", "questions": "I suggest the authors to better compare their work with the related works.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "Benign convexity of machine learning problems is an interesting direction in order to understand why gradient methods may converge well in practice.", "weaknesses": "The author(s) confuse the assumptions used in the related work by Aujol et al., titled \"Convergence Rates of the Heavy Ball Method for Quasi-Strongly Convex Optimization,\" published in SIAM Journal on Optimization in 2022.\n\nIn the introduction, the authors claim that \"strong quasar-convexity\" is used in Aujol et al. (2022). This condition appears to be stronger than the one used by the authors, referred to as Assumption 4, which the authors now describe as \"strong convexity with respect to the closest minimizer.\"\n\n**However, Aujol et al. (2022) already use Assumption 4.** Their assumption is not quasar-convexity, as mistakenly stated in the introduction, but rather strong convexity with respect to the projection onto the minimizing set, which corresponds to the closest minimizer (see equation (4) in Aujol et al., 2022). As a result, **all of the theoretical contributions presented by the authors already exist in the literature**. For example, Theorem 7 replicates the convergence rates from [Theorem 1, Aujol et al., 2022].\n\nFurthermore, the authors conflate Nesterov's acceleration with the heavy ball method throughout the paper, although they are two distinct algorithms. **The paper focuses on the heavy ball method, not Nesterov's acceleration.**", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)