Continuized Nesterov Momentum Achieves the O(ε−7/4) Complexity in Smooth Nonconvex Optimization
Abstract
For first-order optimization of non-convex functions with Lipschitz-continuous gradient and Hessian, the best-known complexity for reaching an ε-approximation of a stationary point is 𝒪(ε−7/4). The existing algorithms achieving this bound are based on momentum, but are always complemented with safeguard mechanisms that reset 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.
Related
- The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization
- On the Complexity of Finding Stationary Points in Stochastic (L0, L1)-Smooth Nonconvex Optimization
- Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
- Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization
- Sharp Fresh-Gradient Complexity of Nonconvex-Strongly-Concave Minimax Optimization
BibTeX
@misc{hermant2026continuized,
title = {{Continuized Nesterov Momentum Achieves the $O(\varepsilon^-7/4)$ Complexity in Smooth Nonconvex Optimization}},
author = {Julien Hermant and Jean-François Aujol and Charles Dossal and Lorick Huang and Aude Rondepierre and Irène Waldspurger},
howpublished = {HAL},
year = {2026},
month = sep,
url = {https://hal.science/hal-05503080v2},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Continuized Nesterov Momentum Achieves the O(ε^−7/4) Complexity in Smooth Nonconvex Optimization
AU - Julien Hermant
AU - Jean-François Aujol
AU - Charles Dossal
AU - Lorick Huang
AU - Aude Rondepierre
AU - Irène Waldspurger
PY - 2026
DA - 2026/09/16
PB - HAL
UR - https://hal.science/hal-05503080v2
AB - For first-order optimization of non-convex functions with Lipschitz-continuous gradient and Hessian, the best-known complexity for reaching an ε-approximation of a stationary point is 𝒪(ε^−7/4). The existing algorithms achieving this bound are based on momentum, but are always complemented with safeguard mechanisms that reset 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.
ER -