Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 30 min ago
PreprintCC BY 4.0arXiv

Improved Gradient Descent Lower Bounds Beyond Nesterov

  • Yuhan Ye
  • Kaizhao Liu
Open at sourcePDFDOICite

Abstract

We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Going beyond the classical Ω(n−2) first-order oracle lower bound of Nemirovsky and Yudin (1983), we prove an Ω(n−1.6342) non-anytime lower bound and an Ω(n−1.2408) anytime lower bound. These improve the recent Ω(n−1.932) non-anytime lower bound of Ma and Chen (2026) and the Ω(n−4/3) anytime lower bound of Tsai et al. (2026), respectively. Both results continue to hold when the stepsizes may be negative. Our anytime lower bound also shows that the O(n−log2(1+√2)) rate of non-anytime silver schedules (Altschuler and Parrilo, 2025; Grimmer et al., 2025) is unattainable in the anytime setting. This establishes a strict separation between the two settings.

Related

  1. Convergence Analysis of Nesterov's Accelerated Gradient Descent under Relaxed Assumptions
    Chenhao Yu, Junhong Lin
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  2. Stronger Lower Bounds for (Non-)Anytime Acceleration of Gradient Descent
    Minchan Jung, Hanseul Cho, Chulhee Yun
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  3. Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent
    Denis Belomestny, Alexey Naumov, Sergey Samsonov
    arXivPreprintarXiv licenceFull textOptimisation & controlStatisticsarXiv
  4. Improved Convergence Rates for Stochastic Multi-Gradient Descent which Close the Gap: A Proof by AI
    Lisha Chen
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  5. On the Nonoccurrence of Gradient Restart in Nesterov Accelerated Gradient Method
    Chenglong Bao, Liang Chen, Jiahong Li +1
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{ye2026improved,
  title = {{Improved Gradient Descent Lower Bounds Beyond Nesterov}},
  author = {Yuhan Ye and Kaizhao Liu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.02855},
  eprint = {2609.02855},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.02855},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Improved Gradient Descent Lower Bounds Beyond Nesterov
AU  - Yuhan Ye
AU  - Kaizhao Liu
PY  - 2026
DA  - 2026/09/03
PB  - arXiv
DO  - 10.48550/arxiv.2609.02855
UR  - https://arxiv.org/abs/2609.02855
AB  - We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Going beyond the classical Ω(n^−2) first-order oracle lower bound of Nemirovsky and Yudin (1983), we prove an Ω(n^−1.6342) non-anytime lower bound and an Ω(n^−1.2408) anytime lower bound. These improve the recent Ω(n^−1.932) non-anytime lower bound of Ma and Chen (2026) and the Ω(n^−4/3) anytime lower bound of Tsai et al. (2026), respectively. Both results continue to hold when the stepsizes may be negative. Our anytime lower bound also shows that the O(n^−log_2(1+√2)) rate of non-anytime silver schedules (Altschuler and Parrilo, 2025; Grimmer et al., 2025) is unattainable in the anytime setting. This establishes a strict separation between the two settings.
ER  -