New Lower Bounds Push Gradient Descent Acceleration Beyond the Nesterov Era
burny_tech · x · 2026-09-04
A new arXiv paper by Yuhan Ye and Kaizhao Liu studies how far gradient descent can be accelerated via predetermined stepsizes in smooth convex optimization.
- Going beyond the classic Nemirovsky–Yudin Ω(n⁻²) first-order oracle lower bound, the authors prove a new non-anytime lower bound of Ω(n⁻1.6342) and an anytime lower bound of Ω(n⁻1.2408)
- These improve the recent Ω(n⁻1.932) non-anytime bound of Ma & Chen and the Ω(n⁻4/3) anytime bound of Tsai et al.
- Combined with the non-anytime O(n⁻log₂(1+√2)) rate of silver schedules, the new anytime bound establishes a strict separation between achievable convergence exponents in the two settings
The paper is 32 pages, spanning math.OC and machine learning.
More from Research
- Eric Topol's new Lancet essay reviews 5 AI health models predicting 20-year outcomes — EricTopol · 2026-09-04
- DeepMind researcher: CoT interpretability is too fragile to anchor long-term AI safety — cephaloform · 2026-09-04
- Vals AI launches SRE-Bench, a cybersecurity benchmark testing LLMs on binary reverse engineering — dyn___ · 2026-09-04
- Emergent Misalignment Is Predictable Generalization, Not a Magic "Evil Persona" — burny_tech · 2026-09-04
- RL-driven progress may hit a wall on out-of-distribution generalization, researcher argues — chris_j_paxton · 2026-09-04
- Kastor: Turning Physics Foundation Models Into Efficient Generative PDE Simulators — qberthet · 2026-09-04