Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

A continuous-time analysis shows that a momentum-only algorithm with stochastic parameters reaches the best known O(ε^{-7/4}) complexity for smooth nonconvex optimization, in a weighted, event-restricted sense.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 04:13 UTC pith:UMGMH243

load-bearing objection Serious continuized-analysis paper with a genuinely new but restricted rate; the missing lower bound on P(A_n) keeps it short of the advertised claim. the 3 major comments →

arxiv 2602.05504 v4 pith:UMGMH243 submitted 2026-02-05 math.OC

Continuized Nesterov Momentum Achieves the O(varepsilon^(-7/4)) Complexity in Smooth Nonconvex Optimization

Julien Hermant , Jean-Fran\c{c}ois Aujol , Charles Dossal , Lorick Huang , Aude Rondepierre , Ir\`ene Waldspurger This is my paper
classification math.OC MSC 90C2668Q2590C30
keywords continuized methodNesterov momentumnonconvex optimizationLipschitz HessianO(ε^-7/4) complexityPoisson processstochastic differential equationfirst-order methods
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper asks whether plain Nesterov momentum can achieve the best known O(ε^{-7/4}) complexity for finding near-stationary points of nonconvex functions with Lipschitz gradient and Hessian, without the restarts or negative-curvature steps required by all previous algorithms. The authors answer yes, provided the momentum parameters are stochastic: they analyze the continuized Nesterov algorithm (CNA), a discrete method obtained by sampling a continuous-time Poisson-driven process, and prove that after n iterations it outputs a point with gradient norm O(n^{-4/7}) in expectation. The expectation, however, multiplies the gradient norm by a positive random weight of unit mean and restricts to an event A_n, both independent of the objective function. Simulations suggest A_n has probability close to one and the weight concentrates near one, but no proof of this is given. If the result holds up, it is the first momentum-only discrete algorithm to match the O(ε^{-7/4}) rate under these smoothness assumptions.

Core claim

The paper's central claim is Theorem 4.2: for a function f with L-Lipschitz gradient and L2-Lipschitz Hessian, the continuized Nesterov algorithm with step size γ ≤ 1/L and momentum parameters γ' = γ + √(γ/2), η = √(γ/2), η' = n^{-1/7} − √(γ/2) satisfies E[ 1_{A_n} min_{1≤k≤n} ‖∇f(x̄_k)‖ Δ_n/E[Δ_n] ] = O(n^{-4/7}), where x̄_k is a Poisson-weighted average of past momentum iterates, Δ_n is a positive function-independent random weight with E[Δ_n] finite, and A_n is a function-independent event controlling certain Gamma-type sums. Converting the n^{-4/7} rate to ε accuracy requires O(ε^{-7/4}) gradient evaluations. The authors emphasize that CNA performs only gradient and momentum steps, with

What carries the argument

The central object is the continuized Nesterov equation (CNE), a stochastic differential equation coupling a continuous momentum flow (dx_t = η(z_t − x_t)dt, dz_t = η'(x_t − z_t)dt) with gradient jumps at the jump times of a unit-rate Poisson process. Sampling the continuous trajectory exactly at the jump times yields the discrete continuized Nesterov algorithm (CNA), so continuous-time proofs transfer to an implementable method. The main identity is a stochastic integration-by-parts formula (Lemma 5.2) that rewrites the Poisson-weighted average of gradients as (z_t − x_t)/(γ' − γ), turning the goal of bounding ∇f of the averaged point into a bound on the distance between the two momentum tr

Load-bearing premise

The proof's load-bearing premise is that the event A_n—on which certain function-independent Gamma-type sums stay within constant multiples of their means—has probability not decaying with n; the paper does not prove this and states that a lower bound 'appears challenging'.

What would settle it

Numerically estimate or analytically bound P(A_n) for large n for the Gamma sums in Definition 4.1; if P(A_n) tends to 0 as n grows, Theorem 4.2 governs only a vanishing fraction of runs. Alternatively, run CNA on a smooth nonconvex function (e.g., a quartic with a saddle) and track the unweighted average of min_{k≤n} ‖∇f(x_k)‖; if that average decays slower than n^{-4/7}, the weight Δ_n/E[Δ_n] is doing essential work and a typical run is not captured by the bound.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • A momentum-only algorithm, CNA, attains the O(ε^{-7/4}) gradient complexity for smooth nonconvex functions with Lipschitz gradient and Hessian, without restarts or negative-curvature steps, in the weighted/event-restricted sense of Theorem 4.2.
  • The continuous-time heavy-ball ODE analysis that established the O(ε^{-7/4}) rate is transferred to the discrete setting through the continuized framework.
  • Under only Lipschitz gradient, CNA achieves the standard O(ε^{-2}) complexity for finding an ε-stationary point (Proposition 3.2), recovering the known rate for Nesterov momentum.
  • The algorithm requires no knowledge of the target accuracy; it only needs the iteration budget n, and it returns a computable point x̄ minimizing the gradient norm among Poisson-weighted averages of past evaluator points.
  • In the regime L2/L ≪ 1, the bound simplifies to roughly O( L^{7/8} Δ_f^{7/8} ε^{-7/4} ), improving the dependence on the initial suboptimality Δ_f over the fastest prior restart-based method.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If a uniform lower bound on P(A_n) could be proved (the paper only provides simulations), Theorem 4.2 would imply a standard unweighted expectation bound for typical runs, making CNA a practical restart-free accelerated method.
  • The stochastic-parameter construction suggests that randomizing momentum coefficients may be a general substitute for safeguard mechanisms; the same continuized analysis could be adapted to Heavy Ball or other inertial methods to avoid restarts.
  • Because A_n and Δ_n depend only on the Poisson schedule, their distributions can be precomputed; a sharper tail analysis of the Gamma-type sums H_i^0, H_i^1, H_i^2 could convert the empirical observations into a proof of the event's high probability.
  • Replacing the final-iteration tuning η' = n^{-1/7} − √(γ/2) with a schedule η'_k = k^{-1/7} − √(γ/2) might yield a fully parameter-free variant, as the paper notes but leaves open.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies a continuized Nesterov momentum algorithm (CNA) with random inter-iteration times, under the assumptions of L-Lipschitz gradient and L2-Lipschitz Hessian. Its main result, Theorem 4.2, states that with parameters γ ≤ 1/L, γ' = γ + √(γ/2), η = √(γ/2), η' = n^{-1/7} − √(γ/2), and α = n^{-1/7}, the iterations satisfy E[1_{A_n} min_{k≤n} ‖∇f(x_k)‖ Δ_n/E[Δ_n]] = O(n^{-4/7}), where A_n is a function-independent event on the Poisson jump times and Δ_n is a positive random weight of unit expectation. The proof combines a continuous-time SDE analysis of (CNE) with a Poisson-averaged trajectory, a stochastic integration-by-parts identity (Lemma 5.2), and a decoupling step (Lemma 5.4) that is valid only on the event A_n. The paper explicitly acknowledges that no lower bound on P(A_n) is proved and that the result is weaker than the standard unweighted expectation guarantee.

Significance. If the missing probability bound on A_n were supplied and the weight Δ_n/E[Δ_n] were controlled from below, this would be the first momentum-only algorithm without restarts or negative-curvature steps to achieve O(ε^{-7/4}) in the smooth nonconvex setting. The continuized-analysis framework is elegant: the reduction from a stochastic differential equation to the discrete algorithm (Proposition 2.3), the Poisson integration-by-parts lemma, and the explicit function-independent event/weight are valuable ideas. The paper also provides detailed proof sketches and elementary computations for the stochastic integrals. However, the advertised claim is materially weaker than what is proved: the theorem controls only an event-restricted, weighted expectation, and the event's probability is unquantified. This prevents the result from being interpreted as a standard complexity guarantee for an average run.

major comments (3)
  1. [Theorem 4.2 and Definition 4.1; 'Limitations of Theorem 4.2'] The central guarantee is E[1_{A_n} min_k ‖∇f(x_k)‖ Δ_n/E[Δ_n]] = O(n^{-4/7}), but no lower bound on P(A_n) is proved. Lemma 5.4 uses A_n in an essential way to decouple the triple stochastic integrals; without A_n the proof breaks. The paper states that a lower bound 'appears challenging' and offers only simulations. If P(A_n) decays with n, the theorem controls a vanishing subset of realizations and gives no information about a typical run. This is a load-bearing gap, not a cosmetic one. The authors should either prove a quantitative lower bound on P(A_n) (e.g., P(A_n) ≥ c > 0, or at least P(A_n) ≥ C n^{-p} compatible with the O(n^{-4/7}) rate) or explicitly rescope the contribution as a conditional result.
  2. [Theorem 4.2; Eq. (17)] The weight Δ_n/E[Δ_n] has unit expectation but can be arbitrarily small on parts of A_n. The theorem therefore does not imply the standard unweighted bound E[ min_k ‖∇f(x_k)‖ ] = O(n^{-4/7}), even conditionally on A_n. The abstract's phrase 'achieves this complexity in expectation' is not supported by the formal statement. A lower bound on Δ_n/E[Δ_n] on A_n (or a concentration result) is needed to translate the weighted bound into a statement about the gradient norm itself. Without such a bound, the advertised O(ε^{-7/4}) complexity is strictly weaker than claimed.
  3. [Sections 4-5; Lemma 5.4] The proof of Lemma 5.4 replaces the H_i^j terms by their expectations using the event A_n and then drops the indicator 1_{A_n} to use independence. This is plausible, but the argument is not complete: the event A_n involves all indices up to n, while the decoupling step separates quantities depending on early and late interarrival times. The written proof sketches this step rather than giving full measurability/independence details. Given that A_n is the main new object of the paper, a full, self-contained proof of Lemma 5.4 should be provided, including the exact role of each defining inequality in Definition 4.1.
minor comments (5)
  1. [Section 1.1] 'The existing lower bound ... is O(ε^{-12/7})' should read Ω(ε^{-12/7}), since a lower bound should be stated with Ω, not O.
  2. [Lemma 5.5 and Eq. (15)] The notation '√α n' is ambiguous; it should be written as √(α n) to match the subsequent computation √(α n) = n^{3/7} when α = n^{-1/7}.
  3. [Figure 1] The caption says 'All the realizations belong to A_n' based on 100 realizations. This is empirical evidence and should be phrased as such; as written it could be mistaken for a theoretical statement.
  4. [Appendix C.4, Eq. (31)] The step 'using 1_{A_n} ≤ 1' is valid but should be stated more explicitly, since the bound replaces 1_{A_n} times an H_i^j by its expectation only after using the A_n inequalities and positivity. A short clarification would improve readability.
  5. [Appendix E, Theorem E.6] The proof relies on Theorem E.6 and Proposition 2.3 from the authors' previous preprint [31]. If [31] is not yet published, the dependence should be highlighted in the introduction and the results should be made self-contained or clearly referenced.

Circularity Check

0 steps flagged

No significant circularity; the main limitation is an unproved event probability, not a circular derivation.

full rationale

The paper's central claim (Theorem 4.2, eq. (6)) explicitly conditions on the function-independent event A_n and multiplies by the unit-expectation weight Δ_n/E[Δ_n]; the section 'Limitations of Theorem 4.2' openly admits that a lower bound on P(A_n) 'appears challenging' and offers only simulations. This is a real weakness of the guarantee, but it is not circular: A_n is defined purely in terms of Gamma-type sums of the Poisson jump times (Definition 4.1), not in terms of the target gradient-norm bound, and no fitted parameter is later repackaged as a prediction. Lemma 5.4 legitimately uses A_n as a truncation/conditioning device to decouple Poisson integrals; it does not assume the O(n^{-4/7}) conclusion. The cited results from the authors' prior work, Proposition 2.3 ([31], Prop. 5) and Theorem E.6 ([31], Thm. 6), are general, parameter-free equivalences and a stopping theorem with stated assumptions that do not include the target result; under the review rules they are independent support rather than load-bearing circularity. The adaptation of the Heavy Ball ODE analysis of [53] is a genuine transfer, not a renaming of a known result, and the theorem is self-contained once its explicitly stated probabilistic limitations are accepted. Accordingly, no circular step is present.

Axiom & Free-Parameter Ledger

3 free parameters · 5 axioms · 0 invented entities

No new physical or mathematical entities are postulated. The event A_n and the weight Δ_n/E[Δ_n] are proof devices rather than invented entities. The main hidden inputs are the smoothness assumptions, the authors' own prior continuized framework, and the unquantified high-probability event A_n.

free parameters (3)
  • α = n^{-1/7} = n^{-1/7}
    Horizon-dependent parameter chosen to balance the two terms in Lemma 5.5; it controls η' and the averaging weight, and is not fitted to data.
  • γ (step size) = ≤ 1/L
    Standard first-order step size chosen from the smoothness constant; not a data-fitted parameter.
  • C in definition of A_n = unspecified (simulations use 5)
    Constant in the good event A_n; the proof only requires existence, so its value is left unspecified.
axioms (5)
  • domain assumption f is lower bounded and differentiable with L-Lipschitz gradient (Assumption 2.1)
    Core smoothness assumption used in the Lyapunov inequalities of Lemma 3.1 and Lemma 5.5.
  • domain assumption Hessian is L2-Lipschitz (Assumption 2.2)
    Needed for Lemma 5.1 to control the gradient of the weighted average, which is what produces the ε^{-7/4} rate.
  • domain assumption Proposition 2.3: CNE-CNA equivalence from the authors' prior paper [31]
    Load-bearing bridge between the continuous-time SDE and the discrete algorithm; previously proven by the same authors and cited, not re-derived here.
  • domain assumption Theorem E.6: stopping-time theorem from [31]
    Used to convert continuous-time almost-sure inequalities into expectations at the random time T_k.
  • standard math Itô/stochastic calculus for Poisson processes (integration by parts, martingale representation)
    Standard results invoked in Lemmas 5.2 and E.4; e.g., Protter [56].

pith-pipeline@v1.3.0-alltime-deepseek · 36983 in / 17539 out tokens · 168815 ms · 2026-08-03T04:13:14.115596+00:00 · methodology

0 comments
read the original abstract

For first-order optimization of non-convex functions with Lipschitz-continuous gradient and Hessian, the best-known complexity for reaching an $\varepsilon$-approximation of a stationary point is $\mathcal{O}(\varepsilon^{-7/4})$. The existing algorithms achieving this bound are based on momentum, but are always complemented with safeguard mechanisms that erase the accumulated momentum if a certain condition is violated. Whether such momentum-control mechanisms are fundamentally necessary has remained an open question. We show that randomizing the parameters enables one to achieve this complexity in expectation when using momentum without any of such mechanisms, and we improve the numerical constant factor of the bound in the case of a large enough number of iterations. From an analysis perspective, we do so by leveraging the continuized method, which interprets the algorithm as a realization of a continuous-time stochastic differential equation (SDE) involving a Poisson process. We show that this SDE converges in probability to the Heavy Ball ordinary differential equation when the stepsize goes to zero, paralleling the behavior of more classical instances of Nesterov momentum.

Figures

Figures reproduced from arXiv: 2602.05504 by Aude Rondepierre, Charles Dossal, Ir\`ene Waldspurger, Jean-Fran\c{c}ois Aujol, Julien Hermant, Lorick Huang.

Figure 1
Figure 1. Figure 1: For 100 realizations of sequences {Tk}k∈{1,...,10000}, (a) shows the evolution of the max over all the realizations of Hi 0−5E [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Histogram distribution of the centered laws of [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Decrease of log f values along the iterations of gradient descent and (CNA), with f defined by the matrix factorization problem (18). Because (CNA) is a stochastic algorithm, we averaged for 10 runs the functions values iteration-wise. We observe a faster decrease in favor of (CNA). ∇f(xs− ) − ∇f(xt) = Z 1 0 ∇2 f((1 − σ)xt + σxs− )(xs− − xt)dσ = ∇2 f(xt)(xs− − xt) + Z 1 0 (∇2 f((1 − σ)xt + σxs− ) − ∇2 f(xt… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Accelerated Stochastic Zeroth-Order Quasar-Convex Optimization

    math.OC 2026-07 conditional novelty 6.0

    A continuized zeroth-order Nesterov method achieves O(d/√ε) function-evaluation complexity for smooth quasar-convex minimization, with improved dimension dependence under a 1-norm mirror step when the solution is sparse.

Reference graph

Works this paper leans on

68 extracted references · 5 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Finding approximate local minima faster than gradient descent

    Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. InProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, page 1195–1199, 2017

    2017

  2. [2]

    Katyusha: The first direct acceleration of stochastic gradient methods

    Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18(221):1–51, 2018

    2018

  3. [3]

    Neon2: Finding local minima via first-order oracles

    Zeyuan Allen-Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles. Advances in Neural Information Processing Systems, 31, 2018

    2018

  4. [4]

    Linear coupling: An ultimate unification of gradient and mirror descent

    Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent. In8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67, pages 3:1–3:22, 2017

    2017

  5. [5]

    Convergence rates of inertial forward-backward algo- rithms.SIAM Journal on Optimization, 28(1):849–874, 2018

    Hedy Attouch and Alexandre Cabot. Convergence rates of inertial forward-backward algo- rithms.SIAM Journal on Optimization, 28(1):849–874, 2018

    2018

  6. [6]

    Optimal convergence rates for Nesterov acceleration.SIAM Journal on Optimization, 29(4):3131–3153, 2019

    Jean-Fran¸ cois Aujol, Charles Dossal, and Aude Rondepierre. Optimal convergence rates for Nesterov acceleration.SIAM Journal on Optimization, 29(4):3131–3153, 2019. 10

    2019

  7. [7]

    Convergence rates of the Heavy- Ball method under the lojasiewicz property.Mathematical Programming, 198(1):195–254, 2023

    Jean-Fran¸ cois Aujol, Charles Dossal, and Aude Rondepierre. Convergence rates of the Heavy- Ball method under the lojasiewicz property.Mathematical Programming, 198(1):195–254, 2023

    2023

  8. [8]

    On the low-rank approach for semidefinite programs arising in synchronization and community detection

    Afonso S Bandeira, Nicolas Boumal, and Vladislav Voroninski. On the low-rank approach for semidefinite programs arising in synchronization and community detection. InConference on learning theory, pages 361–382. PMLR, 2016

    2016

  9. [9]

    A fast iterative shrinkage-thresholding algorithm for linear inverse problems.SIAM journal on imaging sciences, 2(1):183–202, 2009

    Amir Beck and Marc Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems.SIAM journal on imaging sciences, 2(1):183–202, 2009

    2009

  10. [10]

    Global optimality of local search for low rank matrix recovery.Advances in Neural Information Processing Systems, 29, 2016

    Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Global optimality of local search for low rank matrix recovery.Advances in Neural Information Processing Systems, 29, 2016

    2016

  11. [11]

    The non-convex burer-monteiro approach works on smooth semidefinite programs.Advances in Neural Information Processing Systems, 29, 2016

    Nicolas Boumal, Vlad Voroninski, and Afonso Bandeira. The non-convex burer-monteiro approach works on smooth semidefinite programs.Advances in Neural Information Processing Systems, 29, 2016

    2016

  12. [12]

    A geometric alternative to nesterov’s accelerated gradient descent.arXiv preprint arXiv:1506.08187, 2015

    S´ ebastien Bubeck, Yin Tat Lee, and Mohit Singh. A geometric alternative to nesterov’s accelerated gradient descent.arXiv preprint arXiv:1506.08187, 2015

    Pith/arXiv arXiv 2015

  13. [13]

    Phase retrieval via wirtinger flow: Theory and algorithms.IEEE Transactions on Information Theory, 61(4):1985–2007, 2015

    Emmanuel J Candes, Xiaodong Li, and Mahdi Soltanolkotabi. Phase retrieval via wirtinger flow: Theory and algorithms.IEEE Transactions on Information Theory, 61(4):1985–2007, 2015

    1985

  14. [14]

    convex until proven guilty

    Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. “convex until proven guilty”: Dimension-free acceleration of gradient descent on non-convex functions. InInternational conference on machine learning, pages 654–663. PMLR, 2017

    2017

  15. [15]

    Accelerated methods for nonconvex optimization.SIAM Journal on Optimization, 28(2):1751–1772, 2018

    Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization.SIAM Journal on Optimization, 28(2):1751–1772, 2018

    2018

  16. [16]

    Lower bounds for finding stationary points i.Mathematical Programming, 184(1-2):71–120, 2020

    Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i.Mathematical Programming, 184(1-2):71–120, 2020

    2020

  17. [17]

    Lower bounds for finding stationary points ii: first-order methods.Mathematical Programming, 185(1):315–355, 2021

    Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points ii: first-order methods.Mathematical Programming, 185(1):315–355, 2021

    2021

  18. [18]

    On the convergence of the iterates of” fista”

    Antonin Chambolle and Charles H Dossal. On the convergence of the iterates of” fista”. Journal of Optimization Theory and Applications, 166(3):25, 2015

    2015

  19. [19]

    The loss surfaces of multilayer networks

    Anna Choromanska, Mikael Henaff, Michael Mathieu, G´ erard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. InArtificial intelligence and statistics, pages 192–204. PMLR, 2015

    2015

  20. [20]

    Recent theoretical advances in non-convex optimization

    Marina Danilova, Pavel Dvurechensky, Alexander Gasnikov, Eduard Gorbunov, Sergey Gumi- nov, Dmitry Kamzolov, and Innokentiy Shibaev. Recent theoretical advances in non-convex optimization. InHigh-Dimensional Optimization and Probability: With a View Towards Data Science, pages 79–163. Springer, 2022

    2022

  21. [21]

    Identifying and attacking the saddle point problem in high-dimensional non- convex optimization.Advances in neural information processing systems, 27, 2014

    Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non- convex optimization.Advances in neural information processing systems, 27, 2014

    2014

  22. [22]

    Continuized accelerations of de- terministic and stochastic gradient descents, and of gossip algorithms.Advances in Neural Information Processing Systems, 34:28054–28066, 2021

    Mathieu Even, Rapha¨ el Berthier, Francis Bach, Nicolas Flammarion, Hadrien Hendrikx, Pierre Gaillard, Laurent Massouli´ e, and Adrien Taylor. Continuized accelerations of de- terministic and stochastic gradient descents, and of gossip algorithms.Advances in Neural Information Processing Systems, 34:28054–28066, 2021

    2021

  23. [23]

    No spurious local minima in nonconvex low rank problems: A unified geometric analysis

    Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. InInternational conference on machine learning, pages 1233–1242. PMLR, 2017. 11

    2017

  24. [24]

    Matrix completion has no spurious local minimum

    Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. Advances in neural information processing systems, 29, 2016

    2016

  25. [25]

    Accelerated gradient methods for nonconvex nonlinear and stochastic programming.Mathematical Programming, 156(1):59–99, 2016

    Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming.Mathematical Programming, 156(1):59–99, 2016

    2016

  26. [26]

    Optimal first-order methods for convex functions with a quadratic upper bound.arXiv preprint arXiv:2205.15033, 2022

    Baptiste Goujaud, Adrien Taylor, and Aymeric Dieuleveut. Optimal first-order methods for convex functions with a quadratic upper bound.arXiv preprint arXiv:2205.15033, 2022

    Pith/arXiv arXiv 2022

  27. [27]

    Provable non-accelerations of the heavy-ball method.arXiv preprint arXiv:2307.11291, 2023

    Baptiste Goujaud, Adrien Taylor, and Aymeric Dieuleveut. Provable non-accelerations of the heavy-ball method.arXiv preprint arXiv:2307.11291, 2023

    arXiv 2023

  28. [28]

    Nesterov acceleration despite very noisy gradients

    Kanan Gupta, Jonathan W Siegel, and Stephan Wojtowytsch. Nesterov acceleration despite very noisy gradients. InThe Thirty-eighth Annual Conference on Neural Information Pro- cessing Systems, 2024

    2024

  29. [29]

    Understanding alternating minimization for matrix completion

    Moritz Hardt. Understanding alternating minimization for matrix completion. In2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 651–660. IEEE, 2014

    2014

  30. [30]

    Deep residual learning for image recognition

    Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. InProceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016

    2016

  31. [31]

    Continuized nesterov acceleration for non-convex optimization.arXiv preprint arXiv:2512.16533, 2025

    Julien Hermant, Jean-Fran¸ cois Aujol, Charles Dossal, Lorick Huang, and Aude Ronde- pierre. Continuized nesterov acceleration for non-convex optimization.arXiv preprint arXiv:2512.16533, 2025

    arXiv 2025

  32. [32]

    Study of the behaviour of nesterov accelerated gradient in a non convex setting: the strongly quasar convex case.arXiv preprint arXiv:2405.19809, 2024

    Julien Hermant, Jean-Fran¸ cois Aujol, Charles Dossal, and Aude Rondepierre. Study of the behaviour of nesterov accelerated gradient in a non convex setting: the strongly quasar convex case.arXiv preprint arXiv:2405.19809, 2024

    arXiv 2024

  33. [33]

    Gradient correlation is a key ingredient to accelerate sgd with momentum

    Julien Hermant, Marien Renaud, Jean-Fran¸ cois Aujol, Charles Dossal, and Aude Rondepierre. Gradient correlation is a key ingredient to accelerate sgd with momentum. InThe Thirteenth International Conference on Learning Representations, 2025

    2025

  34. [34]

    Near-optimal methods for minimizing star- convex functions and beyond

    Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star- convex functions and beyond. InConference on learning theory, pages 1894–1938. PMLR, 2020

    1938

  35. [35]

    Neural networks for machine learning

    Geoffrey Hinton. Neural networks for machine learning. Coursera Lecture 6e, 2012. Available athttps://www.coursera.org/learn/neural-networks

    2012

  36. [36]

    How to escape saddle points efficiently

    Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. InInternational conference on machine learning, pages 1724–1732. PMLR, 2017

    2017

  37. [37]

    Accelerated gradient descent escapes saddle points faster than gradient descent

    Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. InConference On Learning Theory, pages 1042–

  38. [38]

    Deep learning without poor local minima.Advances in neural information processing systems, 29, 2016

    Kenji Kawaguchi. Deep learning without poor local minima.Advances in neural information processing systems, 29, 2016

    2016

  39. [39]

    Kingma and Jimmy Ba

    Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. InInter- national Conference on Learning Representations, 2015

    2015

  40. [40]

    Gradient descent only converges to minimizers

    Jason D Lee, Max Simchowitz, Michael I Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. InConference on learning theory, pages 1246–1257. PMLR, 2016

    2016

  41. [41]

    Visualizing the loss landscape of neural nets.Advances in neural information processing systems, 31, 2018

    Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets.Advances in neural information processing systems, 31, 2018. 12

    2018

  42. [42]

    Restarted nonconvex accelerated gradient descent: No more poly- logarithmic factor in the in theo(ϵ −7/4) complexity.Journal of Machine Learning Research, 24(157):1–37, 2023

    Huan Li and Zhouchen Lin. Restarted nonconvex accelerated gradient descent: No more poly- logarithmic factor in the in theo(ϵ −7/4) complexity.Journal of Machine Learning Research, 24(157):1–37, 2023

    2023

  43. [43]

    Parameter-free accelerated gradient descent for nonconvex minimization.SIAM J

    Naoki Marumo and Akiko Takeda. Parameter-free accelerated gradient descent for nonconvex minimization.SIAM J. Optim., 34:2093–2120, 2022

    2093

  44. [44]

    Universal heavy-ball method for nonconvex optimization under h¨ older continuous hessians.Mathematical Programming, 212(1):147–175, 2025

    Naoki Marumo and Akiko Takeda. Universal heavy-ball method for nonconvex optimization under h¨ older continuous hessians.Mathematical Programming, 212(1):147–175, 2025

    2025

  45. [45]

    Solving sdps for synchronization and maxcut problems via the grothendieck inequality

    Song Mei, Theodor Misiakiewicz, Andrea Montanari, and Roberto Imbuzeiro Oliveira. Solving sdps for synchronization and maxcut problems via the grothendieck inequality. InConference on learning theory, pages 1476–1515. PMLR, 2017

    2017

  46. [46]

    A 2CiD2: Accelerating Asynchronous Communication in Decentralized Deep Learning.Advances in Neural Information Processing Systems, 36:47451–47474, 2023

    Adel Nabli, Eugene Belilovsky, and Edouard Oyallon. A 2CiD2: Accelerating Asynchronous Communication in Decentralized Deep Learning.Advances in Neural Information Processing Systems, 36:47451–47474, 2023

    2023

  47. [47]

    Dadao: Decoupled accelerated decentralized asynchronous optimization

    Adel Nabli and Edouard Oyallon. Dadao: Decoupled accelerated decentralized asynchronous optimization. InInternational Conference on Machine Learning, pages 25604–25626. PMLR, 2023

    2023

  48. [48]

    Problem complexity and method efficiency in optimization.Wiley-Interscience, 1983

    Arkadij Semenoviˇ c Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization.Wiley-Interscience, 1983

    1983

  49. [49]

    A method for solving the convex programming problem with convergence rate o(1/k2)

    Yurii Nesterov. A method for solving the convex programming problem with convergence rate o(1/k2). InDokl akad nauk Sssr, volume 269, page 543, 1983

    1983

  50. [50]

    Introductory lectures on convex optimization

    Yurii Nesterov. Introductory lectures on convex optimization. applied optimization, 2004

    2004

  51. [51]

    Springer, 2018

    Yurii Nesterov.Lectures on convex optimization, volume 137. Springer, 2018

    2018

  52. [52]

    Cubic regularization of newton method and its global performance.Mathematical programming, 108(1):177–205, 2006

    Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance.Mathematical programming, 108(1):177–205, 2006

    2006

  53. [53]

    Heavy-ball differential equation achieves O(ε−7/4) convergence for nonconvex functions.arXiv preprint arXiv:2406.06100, 2024

    Kaito Okamura, Naoki Marumo, and Akiko Takeda. Heavy-ball differential equation achieves O(ε−7/4) convergence for nonconvex functions.arXiv preprint arXiv:2406.06100, 2024

    Pith/arXiv arXiv 2024

  54. [54]

    Behavior of accelerated gradient methods near critical points of nonconvex functions.Mathematical Programming, 176(1):403–427, 2019

    Michael O’Neill and Stephen J Wright. Behavior of accelerated gradient methods near critical points of nonconvex functions.Mathematical Programming, 176(1):403–427, 2019

    2019

  55. [55]

    Some methods of speeding up the convergence of iteration methods.USSR Computational Mathematics and Mathematical Physics, 4(5):1–17, 1964

    Boris Polyak. Some methods of speeding up the convergence of iteration methods.USSR Computational Mathematics and Mathematical Physics, 4(5):1–17, 1964

    1964

  56. [56]

    Stochastic differential equations

    Philip E Protter. Stochastic differential equations. InStochastic integration and differential equations, pages 249–361. Springer, 2012

    2012

  57. [57]

    Provably accelerated imaging with restarted inertia and score-based image priors.arXiv preprint arXiv:2510.07470, 2025

    Marien Renaud, Julien Hermant, Deliang Wei, and Yu Sun. Provably accelerated imaging with restarted inertia and score-based image priors.arXiv preprint arXiv:2510.07470, 2025

    arXiv 2025

  58. [58]

    Accelerated first-order methods: Differential equations and lyapunov functions.arXiv preprint arXiv:1903.05671, 2019

    Jonathan W Siegel. Accelerated first-order methods: Differential equations and lyapunov functions.arXiv preprint arXiv:1903.05671, 2019

    Pith/arXiv arXiv 1903

  59. [59]

    Cand` es

    Weijie Su, Stephen Boyd, and Emmanuel J. Cand` es. A differential equation for modeling nesterov’s accelerated gradient method: theory and insights.Journal of Machine Learning Research, 17(153):1–43, 2016

    2016

  60. [60]

    Heavy-ball algorithms always escape saddle points.arXiv preprint arXiv:1907.09697, 2019

    Tao Sun, Dongsheng Li, Zhe Quan, Hao Jiang, Shengguo Li, and Yong Dou. Heavy-ball algorithms always escape saddle points.arXiv preprint arXiv:1907.09697, 2019

    Pith/arXiv arXiv 1907

  61. [61]

    On the importance of ini- tialization and momentum in deep learning

    Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of ini- tialization and momentum in deep learning. InInternational Conference on Machine Learning, pages 1139–1147, 2013. 13

    2013

  62. [62]

    Continuized acceleration for quasar convex functions in non-convex optimization, 2023

    Jun-Kun Wang and Andre Wibisono. Continuized acceleration for quasar convex functions in non-convex optimization, 2023

    2023

  63. [63]

    First-order stochastic algorithms for escaping from saddle points in almost linear time.Advances in neural information processing systems, 31, 2018

    Yi Xu, Rong Jin, and Tianbao Yang. First-order stochastic algorithms for escaping from saddle points in almost linear time.Advances in neural information processing systems, 31, 2018. A Complementary details to Section 1 A.1 Accelerated gradient algorithms under convexity A seminal work [55] shows that the heavy ball momentum algorithm xn+1 =x n +α(x n −x...

    2018

  64. [64]

    Z (Ti,Ti+1) η2 ∥zs −x s∥2 ds # E[A i+1] ≤Cmax i∈{1,...,n−1} E[A i+1] n−1X i=1 E

    for alli∈ {1, . . . , n}. We also emphasized that these quantities are difficult to study theoretically. To give more insights about their behaviour, we plot in Figure 2 histograms of their centered law. We fixn= 100, and plot the histogram distribution of 10 4 realizations fori= 2, i= 10 andi= 100. We observe that the shape of the laws significantly chan...

  65. [65]

    Z Tn 0 Λt wt(t)(zt −x t) γ′ −γ dNt # =E

    Bounding the right hand side of(42).Recallingw t(t) = αeαt R t 0 αeαsdNs , one has wt(t)(zt −x t) γ′ −γ = αeαt (γ′ −γ) 1R t 0 αeαsdNs ∥zt −x t∥ = α (γ′ −γ) 1R t 0 αeα(s−t)dNs ∥zt −x t∥ So E "Z Tn 0 Λt wt(t)(zt −x t) γ′ −γ dNt # =E "Z Tn 0 α γ′ −γ Z t 0 αeα(s−t)dNs ∥zt −x t∥dN t # ≤ α γ′ −γ vuutE "Z Tn 0 ΛtdNt #vuutE "Z Tn 0 ∥zt −x t∥2 dNt # , (45) where w...

  66. [66]

    Combining this with (45), Lemma D.5-(i) and (48), we deduce E "Z Tn 0 Λt wt(t)(zt− −x t− ) γ′ −γ dNt # ≤ α γ′ −γ s 3 1 + 3 2 α (1 + 2α)n r 2 f(x 0)−f ∗ α = √αn s 6 1 + 3 2 α (1 + 2α) γ p f(x 0)−f ∗ = √αn s Cα γ p f(x 0)−f ∗,(49) where we usedγ ′ =γ+ p γ 2 and definedC α = 6 1 + 3 2 α (1 + 2α)

  67. [67]

    1An α2L2 Z Tn 0 η2 ∥zs −x s∥2 Z Tn s Z t s Z s 0 eα(τ−t) eα(σ−t)(τ−σ)dN σdNτ dNt ! ds # ≤CL 2 (1 + 2α)4 α2 E

    Bounding(43).Using Lemma 5.4 and Lemma C.2, we have E " 1An α2L2 Z Tn 0 η2 ∥zs −x s∥2 Z Tn s Z t s Z s 0 eα(τ−t) eα(σ−t)(τ−σ)dN σdNτ dNt ! ds # ≤CL 2 (1 + 2α)4 α2 E "Z Tn 0 η2 ∥zs −x s∥2 ds # . (50) From (39), we have E "Z Tn 0 ∥zs −x s∥2 ds # ≤ 1 η+η ′ (f(x 0)−f ∗) = 1 α (f(x 0)−f ∗).(51) So, combining (50) and (51), we deduce E " 1An α2L2 Z Tn 0 η2 ∥zs ...

  68. [68]

    1An α2L2 Z Tn 0 γ2 ∥∇f(x s− )∥2 Z Tn s Z t s Z s 0 eα(τ−t) eα(σ−t)(Nτ − −N σ− )dNσdNτ dNt ! dNs # ≤Cα −1L2 (1 + 2α)5 α4 E

    Bounding(44).Using Lemma 5.4 and Lemma C.2, we have E " 1An α2L2 Z Tn 0 γ2 ∥∇f(x s− )∥2 Z Tn s Z t s Z s 0 eα(τ−t) eα(σ−t)(Nτ − −N σ− )dNσdNτ dNt ! dNs # ≤Cα −1L2 (1 + 2α)5 α4 E "Z Tn 0 γ2 ∥∇f(x s− )∥2 dNs # (53) From (40), we have E "Z Tn 0 ∥∇f(x s− )∥2 dNs # ≤ 4 γ (f(x 0)−f ∗).(54) So, combining (53) and (54), we deduce E " 1An α2L2 Z Tn 0 γ2 ∥∇f(x s− )...