Metraipolis › archive › dc_a4644bfacea1
Can Acceleration in Gradient-Norm Minimization Be Anytime? Sharp Last-Iterate Limits in Smooth Convex Optimization — arXiv:2609.05710
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.05710
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T14:23:56.598Z
- SHA-256 of the archived text
bf1df5982b30540d12811997b56f8714d924be0c057c1143749713a36f3b250e- Stable URL of this page
https://metraipolis.com/documento/dc_a4644bfacea1
How to cite
Can Acceleration in Gradient-Norm Minimization Be Anytime? Sharp Last-Iterate Limits in Smooth Convex Optimization — arXiv:2609.05710 — arXiv (en), https://arxiv.org/abs/2609.05710 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a4644bfacea1 (Metraipolis archive dc_a4644bfacea1, sha256 bf1df5982b30540d12811997b56f8714d924be0c057c1143749713a36f3b250e)
BibTeX
@misc{dca4644bfacea1,
title = {Can Acceleration in Gradient-Norm Minimization Be Anytime? Sharp Last-Iterate Limits in Smooth Convex Optimization — arXiv:2609.05710},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.05710},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a4644bfacea1; sha256 bf1df5982b30540d12811997b56f8714d924be0c057c1143749713a36f3b250e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.05710. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\Omega(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 $\Omega(N^{-1})$ lower bound must hold for infinitely many horizons. More precisely, if $\mathcal G_N(\mathcal A)$ denotes the bound on the squared gradient norm after $N$ iterations for a method $\mathcal A$, we prove that $\limsup_{N\to\infty}N \mathcal G_N(\mathcal A) \ge 1/2$ for any method $\mathcal A$. 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 $\mathcal A$ with an $o(N^{-1})$ guarantee on a subsequence of iterates must satisfy $\limsup_N N \mathcal G_N(\mathcal A)=\infty$. In contrast, best-so-far output admits a uniform $O(N^{-2})$ guarantee.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.05710 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T14:09:21.645Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).