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.
From: Julien Hermant [view email]
[v1]
Thu, 5 Feb 2026 10:05:47 UTC (269 KB)
[v2]
Sat, 23 May 2026 14:15:59 UTC (63 KB)
[v3]
Tue, 26 May 2026 06:18:19 UTC (63 KB)
[v4]
Tue, 28 Jul 2026 09:16:51 UTC (163 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。