Improved Gradient Descent Lower Bounds Beyond Nesterov

arXiv:2609.02855 · math.OC, cs.LG, stat.ML · Submitted 2026-09-02 · Read on arXiv

math.OC, cs.LG, stat.ML

Submitted: 2026-09-02

Updated: 2026-09-03

Project page: https://chungentsai.github.io/gd-lower-bounds.html

Terminology

• Verification — 1× in this paper · explained in 2 episodes

Sources

• Numerical Design of Optimized First-Order Algorithms
• A lower bound for stepsize-based acceleration of gradient descent
• Negative Stepsizes Make Gradient-Descent-Ascent Converge
• Lower Bounds for Anytime Acceleration of Gradient Descent

Related papers

• Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
• Adam-HNAG: A Convergent Reformulation of Adam with Accelerated Rate
• Incremental Learning in Mirror Flows
• Online Control via Counterfactual Tracking
• Asynchronous Replanning in Two Population Linear Quadratic Mean Field Games: Information Requirements and Stability
• Petrov-Galerkin operator inference with application to stability-encouraging identification