Metraipolis › archive › dc_e26e264ad83e
Stronger Lower Bounds for (Non-)Anytime Acceleration of Gradient Descent — arXiv:2609.04032
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.04032
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T02:26:51.960Z
- SHA-256 of the archived text
01b292aca1ae9969a1b861bfed974aa33e24462ac0775a8dc3f3fd0f95e2b738- Stable URL of this page
https://metraipolis.com/documento/dc_e26e264ad83e
How to cite
Stronger Lower Bounds for (Non-)Anytime Acceleration of Gradient Descent — arXiv:2609.04032 — arXiv (en), https://arxiv.org/abs/2609.04032 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e26e264ad83e (Metraipolis archive dc_e26e264ad83e, sha256 01b292aca1ae9969a1b861bfed974aa33e24462ac0775a8dc3f3fd0f95e2b738)
BibTeX
@misc{dce26e264ad83e,
title = {Stronger Lower Bounds for (Non-)Anytime Acceleration of Gradient Descent — arXiv:2609.04032},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.04032},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e26e264ad83e; sha256 01b292aca1ae9969a1b861bfed974aa33e24462ac0775a8dc3f3fd0f95e2b738},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.04032. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The rate-optimal convergence rate of gradient descent (GD) with a fixed step-size is well known to be $\Theta(N^{-1})$ for $L$-Lipschitz smooth convex objectives in the prior art in convex optimization. Surprisingly, several recent works show that we can accelerate vanilla GD by applying a nonconstant, nonadaptive, deterministic step-size schedule. The best-known upper bounds so far in the non-anytime & anytime setups are $O(N^{-1.271})$ [Altschuler and Parrilo, 2025, Grimmer et al., 2023] and $O(N^{-1.119})$ [Zhang et al., 2025], respectively. On the other hand, the best reported lower bounds (or barriers) up to date in the non-anytime & anytime setups are $\Omega(N^{-1.635})$ and $\Omega(N^{-1.241})$ [Ye and Liu, 2026], respectively. We narrow these gaps by establishing stronger lower bounds for GD's convergence rate in both settings: $\Omega(N^{-1.450})$ for the non-anytime rate bound and $\Omega(N^{-1.184})$ for the anytime rate barrier.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-04 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.04032 — 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-17T02:07:43.349Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-04?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).