Continuized Nesterov Acceleration for Non-Convex Optimization
Julien Hermant [email protected], Jean-François Aujol [email protected], Charles Dossal [email protected], Lorick Huang [email protected], Aude Rondepierre [email protected] · 2025
Read Continuized Nesterov Acceleration for Non-Convex Optimization by Julien Hermant [email protected], Jean-François Aujol [email protected], Charles Dossal [email protected], Lorick Huang [email protected], Aude Rondepierre [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-16533.txt.
Introduction
Julien Hermant and coauthors work on faster methods for minimizing rough, non-convex cost functions, a core task in machine learning. In smooth convex settings, flow-like views of momentum methods give sharp insight, but for non-convex costs the flow view and the step-by-step view often disagree.
The team uses a mixed frame that blends flow and steps, first built by Even and coauthors. They widen it to cover non-smooth energy tools, then sharpen its path-by-path promises for fast linear rates. Applied to strongly quasar convex functions, a broad non-convex class, the frame improves the known rate by a fixed factor and softens the terms on the set of lowest points.
Catalog record
| CREATOR | Julien Hermant [email protected], Jean-François Aujol [email protected], Charles Dossal [email protected], Lorick Huang [email protected], Aude Rondepierre [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 118 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-16533
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Continuized Nesterov Acceleration for Non-Convex Optimization Julien Hermant [email protected], Jean-François Aujol [email protected], Charles Dossal [email protected], Lorick Huang [email protected], Aude Rondepierre [email protected] Abstract In convex optimization, continuous-time counterparts have been a fruitful tool for analyzing momentum algorithms. Fewer such examples are available when the function to minimize is non-convex. In several cases, discrepancies arise between the existing discrete-time results — namely those obtained for momentum algorithms — and their continuous-time counterparts, with the latter typically yielding stronger guarantees. We argue that the continuized framework ( 25 ) , mixing continuous and discrete components, can tighten the gap between known continuous and discrete results. This framework relies on computations akin to standard Lyapunov analyses, from which are deduced convergence bounds for an algorithm that can be written as a Nesterov momentum algorithm with stochastic parameters. In this work, we extend the range of applicability of the continuized framework, e.g. by allowing it to handle non-smooth Lyapunov functions. We then strengthen its trajectory-wise guarantees for linear convergence rate, deriving finite time bounds with high probability and asymptotic almost sure bounds. We apply this framework to the non-convex class of strongly quasar convex functions. Adapting continuous-time results that have weaker discrete equivalents to the continuized method, we improve by a constant factor the known convergence rate, and relax the existing assumptions on the set of minimizers. † † shortheadings: Continuized Nesterov acceleration / Hermant, Aujol, Dossal, Huang, Rondepierre † † firstpage: 1 † † editor: My editor keywords Non-Nonvex Optimization, Accelerated First-Order Algorithms, Stochastic Optimization, Continuized Algorithms, Jump Process 1 Introduction We consider the following unconstrained minimization problem \min_{x\in\mathbb{R}^{d}}f(x):=f^{\ast} (P) where f:\mathbb{R}^{d}\to\mathbb{R} is a differentiable function such that \arg\min_{x\in\mathbb{R}^{d}}f(x) is non-empty. As there is often no closed-form solution to Problem ( P ), optimization algorithms are used to approximate its solution. When it comes to high-dimensional problems, i.e. d>>1 , the so-called first-order algorithms that make use of the gradient information, such as gradient descent , are popular. It can be explained by their dimension-free complexity bounds, and the relative cheapness of their iterations, e.g. compared to second order methods which involve the computation of the Hessian matrix. To solve Problem ( P ) efficiently, we seek algorithms that converge as fast as possible. If gradient descent benefits from a simple formulation, it however typically exhibits relatively slow convergence, such that several mechanisms exist in order to accelerate its convergence ( 45 ; 52 ) . A widely used acceleration technique consists in adding a momentum mechanism to gradient descent. The two main variants are Polyak’s Heavy Ball ( 72 ) and Nesterov momentum ( 66 ) . In convex optimization, momentum algorithms are known to attain the optimal worst-case complexity rate among first-order methods in many settings ( 72 ; 66 ; 64 ; 81 ; 10 ; 9 ) . However, many problems ( P ) of practical interest are such that f is non-convex ( 57 ; 23 ; 31 ; 30 ; 13 ) . While it is empirically observed that the acceleration property of momentum still holds despite non-convexity in various settings ( 80 ; 40 ) , there exist some classes of non-convex functions such that gradient descent already achieves optimal convergence bounds among first-order algorithms ( 17 ; 86 ) . Showing the benefit of momentum algorithms in a non-convex regime is thus an active field of research ( 39 ; 83 ; 58 ; 48 ; 44 ; 42 ; 38 ; 28 ; 68 ; 55 ) . 1.1 ODEs Momentum and their Limit for Algorithm Design Different canonical formulations of momentum algorithms coexist in the literature, see a brief discussion in Appendix E.2 . In this work, we study the following ( 67 ) \displaystyle\left\{\begin{array}[]{ll}\tilde{y}_{k}&=\alpha_{k}\tilde{x}_{k}+(1-\alpha_{k})\tilde{z}_{k}\\ \tilde{x}_{k+1}&=\tilde{y}_{k}-s\nabla f(\tilde{y}_{k})\\ \tilde{z}_{k+1}&=\beta_{k}\tilde{z}_{k}+(1-\beta_{k})\tilde{y}_{k}-\eta_{k}\nabla f(\tilde{y}_{k})\end{array}\right. Note that \{\tilde{x}_{k}\}_{k\in{\mathbb{N}}} reduces to gradient descent for the choice \alpha_{k}=1 , \forall k\in{\mathbb{N}} . As previously mentioned, it is known to accelerate over gradient descent in many settings in convex optimization ( 79 ; 9 ; 10 ; 56 ) . In particular, for \mu -strongly convex functions with L -Lipschitz gradient, \{\tilde{x}_{k}\}_{k\in{\mathbb{N}}} generated by ( 1.1 ) properly parameterized ensures f(\tilde{x}_{k})-f^{\ast}=\mathcal{O}((1-\sqrt{\mu/L})^{k}) ( 67 ) . This should be compared with the bound \mathcal{O}((1-\mu/L)^{k}) using gradient descent, which can be significantly worse as typically \mu\ll L (this is particularly true in the high dimensional setting). It is thus common to mention this gain of a squared dependence on \mu/L as acceleration . A common approach to studying optimization algorithms is to consider their continuous-time counterparts. By letting the stepsize s in ( 1.1 ) tend to zero, we obtain a continuous-time limit, closely related to the Heavy Ball equation (see Appendix E.3 ), that is \displaystyle\left\{\begin{array}[]{ll}\dot{x}_{t}&=\eta_{t}(z_{t}-x_{t})-\gamma_{t}\nabla f(x_{t})\\ \dot{z}_{t}&=\eta^{\prime}_{t}(x_{t}-z_{t})-\gamma^{\prime}_{t}\nabla f(x_{t})\end{array}\right. with t\in{\mathbb{R}}_{+} for some choices of parameters \eta_{t},\eta^{\prime}_{t},\gamma_{t} and \gamma^{\prime}_{t} , see the derivation in ( 51 , Appendix A.1) . A strategy to obtain convergence results is then to find a suitable function \varphi:\mathbb{R}^{d}\to{\mathbb{R}} , typically depending on the function we want to minimize, such that the Lyapunov function E_{t}:=\varphi(x_{t},z_{t},t) will decrease with t . Working in continuous time is often more convenient, since one can analyze the derivative \dot{E}_{t} . To deduce a result for ( 1.1 ), one can try to mimic the analysis of the continuous counterpart by constructing a discrete Lyapunov function \{E_{k}\}_{k\in{\mathbb{N}}} inspired by (E_{t})_{t\geq 0} . As an illustration, considering \mu -strongly convex functions, an appropriate choice (E_{t})_{t\geq 0} applied to the solution (x_{t})_{t\geq 0} of ( 1.1 ) (properly parameterized), yields the rate f(x_{t})-f^{\ast}=\mathcal{O}(e^{-\sqrt{\mu t}}) ( 78 ) . A straightforward discrete analogue of this Lyapunov function leads to the bound f(\tilde{x}_{k})-f^{\ast}=\mathcal{O}((1-\sqrt{\mu/L})^{k}) , for \{\tilde{x}_{k}\}_{k\in{\mathbb{N}}} generated by ( 1.1 ) properly tuned, see Table 1 . Lyapunov Function Convergence Bound Continuous E_{t}=f(x_{t})-\min f(x)+\frac{\mu}{2}\left\lVert z_{t}-x^{\ast}\right\rVert^{2} f(x_{t})-f^{\ast}=\mathcal{O}(e^{-\sqrt{\mu t}}) Discrete E_{k}=f(\tilde{x}_{k})-\min f(x)+\frac{\mu}{2}\left\lVert\tilde{z}_{k}-x^{\ast}\right\rVert^{2} f(\tilde{x}_{k})-f^{\ast}=\mathcal{O}((1-\sqrt{\mu/L})^{k}) Table 1: Example of ”convergence transfer” between continuous and discrete settings. (x_{t})_{t\geq 0} , respectively \{\tilde{x}_{k}\}_{k\in{\mathbb{N}}} , is generated by ( 1.1 ), respectively ( 1.1 ), properly tuned. f is supposed to be \mu -strongly convex in both cases, and is also L -smooth in the discrete case. Both rates correspond to linear convergence, with rates \sqrt{\mu} and \sqrt{\mu/L} , respectively. In this sense, the continuous-time result is ”transferred” to the discrete setting. The L -Lipschitzness of the gradient is a key property to enable this transfer. In particular, the accelerated rate (1-\sqrt{\mu/L})^{k} can be achieved if we take s in ( 1.1 ) large enough, namely s=1/L . This has been extensively used in the convex setting where similar convergence results are obtained for (x_{t})_{t\geq 0} and \{x_{n}\}_{n\geq 0} , see e.g. ( 79 ; 78 ; 5 ; 77 ; 10 ; 7 ; 56 ) . However, this approach may suffer from two drawbacks. (i) Convergence properties do not transfer The convergence properties of (x_{t})_{t\geq 0} may not transfer to \{x_{n}\}_{n\geq 0} when f is not convex. In the case of L -smooth functions, if the total energy decreases when applied to the solution of the Heavy Ball equation, it is not the case for the discrete counterpart, see ( 48 , Section A.1) . For functions with Lipschitz gradient and Hessian, a convergence result exists for the Heavy Ball equation, but needs