Can Acceleration in Gradient-Norm Minimization Be Anytime? Sharp Last-Iterate Limits in Smooth Convex Optimization
Abstract
In smooth convex optimization, the gradient norm is a directly observable measure of stationarity. Accelerating a first-order method that minimizes the gradient norm is known to be more delicate than accelerating the minimization of function values. Optimal accelerated methods such as OGM-G (Kim & Fessler, 2021) are known to exist for any prescribed finite horizon, but their coefficients depend explicitly on the length of that horizon, i.e. the number of iterations. We ask what kind of acceleration is feasible when the stopping horizon is unknown to the method, i.e. for horizon-independent methods. Diakonikolas & Wang (2022) conjectured that an Ω(N−1) lower bound on the squared gradient norm holds at every horizon N for any nonadaptive, horizon-independent linear-span first-order method. We disprove this pointwise conjecture by exhibiting a method that achieves near-N−2 last-iterate guarantees on a density-one set of horizons. We show instead that an Ω(N−1) lower bound must hold for infinitely many horizons. More precisely, if 𝒢N(𝒜) denotes the bound on the squared gradient norm after N iterations for a method 𝒜, we prove that limsupN→∞N 𝒢N(𝒜) ≥ 1/2 for any method 𝒜. This bound is sharp: the constant 1/2 is exactly attained by the horizon-independent gradient-descent schedule of Rotaru et al. (2026). In addition, we show that the above two extreme behaviors cannot be achieved by the same method: any method 𝒜 with an o(N−1) guarantee on a subsequence of iterates must satisfy limsupN N 𝒢N(𝒜)=∞. In contrast, best-so-far output admits a uniform O(N−2) guarantee.
Related
- Stronger Lower Bounds for (Non-)Anytime Acceleration of Gradient Descent
- Anytime-Feasible Gradient Descent for Constrained Optimization Under Gradient Uncertainty
- Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
- Optimal Gradient-Norm Minimization in Non-Euclidean Hölder-Smooth Convex Optimization
- KAYROS: An Anytime and Exact Open-Source Solver for Duration-Minimization Time-Dependent Vehicle Routing. A Technical Report and a Case Study in Human-AI Engineering
BibTeX
@misc{vernimmen2026acceleration,
title = {{Can Acceleration in Gradient-Norm Minimization Be Anytime? Sharp Last-Iterate Limits in Smooth Convex Optimization}},
author = {Pierre Vernimmen and François Glineur},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05710},
eprint = {2609.05710},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05710},
}
RIS
TY - UNPB
TI - Can Acceleration in Gradient-Norm Minimization Be Anytime? Sharp Last-Iterate Limits in Smooth Convex Optimization
AU - Pierre Vernimmen
AU - François Glineur
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.05710
UR - https://arxiv.org/abs/2609.05710
AB - In smooth convex optimization, the gradient norm is a directly observable measure of stationarity. Accelerating a first-order method that minimizes the gradient norm is known to be more delicate than accelerating the minimization of function values. Optimal accelerated methods such as OGM-G (Kim & Fessler, 2021) are known to exist for any prescribed finite horizon, but their coefficients depend explicitly on the length of that horizon, i.e. the number of iterations. We ask what kind of acceleration is feasible when the stopping horizon is unknown to the method, i.e. for horizon-independent methods. Diakonikolas & Wang (2022) conjectured that an Ω(N^−1) lower bound on the squared gradient norm holds at every horizon N for any nonadaptive, horizon-independent linear-span first-order method. We disprove this pointwise conjecture by exhibiting a method that achieves near-N^−2 last-iterate guarantees on a density-one set of horizons. We show instead that an Ω(N^−1) lower bound must hold for infinitely many horizons. More precisely, if 𝒢_N(𝒜) denotes the bound on the squared gradient norm after N iterations for a method 𝒜, we prove that limsup_N→∞N 𝒢_N(𝒜) ≥ 1/2 for any method 𝒜. This bound is sharp: the constant 1/2 is exactly attained by the horizon-independent gradient-descent schedule of Rotaru et al. (2026). In addition, we show that the above two extreme behaviors cannot be achieved by the same method: any method 𝒜 with an o(N^−1) guarantee on a subsequence of iterates must satisfy limsup_N N 𝒢_N(𝒜)=∞. In contrast, best-so-far output admits a uniform O(N^−2) guarantee.
ER -