← 研踪 PaperTrailarXiv:2609.09152 · v3
Silver Rate Is (Almost) Optimal for Gradient Descent
首次提交 2026-09-09 01:59
版本更新 2026-11-19 13:08
雷达观测 2026-11-20 19:58
摘要
Gradient descent (GD) is one of the most fundamental algorithms in optimization. Yet even for smooth convex objectives, the optimal rate among predetermined nonnegative stepsize schedules has remained unresolved. Altschuler and Parrilo [Mathematical Programming, 2025] showed that their recursive silver stepsize schedule achieves an rate, where , improving upon the classical rate of constant-step GD. Although the optimality of has been well supported by numerical evidence for small , a matching lower bound has remained missing. In this paper, we prove an lower bound for GD, showing that is the optimal convergence exponent. Additionally, we prove an anytime lower bound that matches the exponent of the known upper bound [Zhang, Lee, Du, and Chen, COLT 2025]. Building on the approaches of [Ma and Chen, 2026; Jung, Cho, and Yun, 2026], we select specific iterations as checkpoints at which the GD trajectory explores a new coordinate, and we couple these coordinates using a chain of local functions. Our main technical contribution is a local hard function that bends the GD trajectory between successive checkpoints, resulting in a sharpened lower bound. For each prescribed stepsize schedule, we maximize this bound over admissible checkpoint sets. A recursive analysis of this maximum then yields a lower bound matching the silver exponent for every such schedule.
作者备注:34 pages, 4 figures
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-19 13:08 · 最新观测版本
Silver Rate Is (Almost) Optimal for Gradient Descent
Gradient descent (GD) is one of the most fundamental algorithms in optimization. Yet even for smooth convex objectives, the optimal rate among predetermined nonnegative stepsize schedules has remained unresolved. Altschuler and Parrilo [Mathematical Programming, 2025] showed that their recursive silver stepsize schedule achieves an rate, where , improving upon the classical rate of constant-step GD. Although the optimality of has been well supported by numerical evidence for small , a matching lower bound has remained missing. In this paper, we prove an lower bound for GD, showing that is the optimal convergence exponent. Additionally, we prove an anytime lower bound that matches the exponent of the known upper bound [Zhang, Lee, Du, and Chen, COLT 2025]. Building on the approaches of [Ma and Chen, 2026; Jung, Cho, and Yun, 2026], we select specific iterations as checkpoints at which the GD trajectory explores a new coordinate, and we couple these coordinates using a chain of local functions. Our main technical contribution is a local hard function that bends the GD trajectory between successive checkpoints, resulting in a sharpened lower bound. For each prescribed stepsize schedule, we maximize this bound over admissible checkpoint sets. A recursive analysis of this maximum then yields a lower bound matching the silver exponent for every such schedule.
查看此版本解读 →查看此版本原文 ↗