跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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 O(n−psil)O(n^{-p_{\mathrm{sil}}}) rate, where psil=log⁡2(1+2)≈1.2716p_{\mathrm{sil}}=\log_2(1+\sqrt2)\approx1.2716, improving upon the classical O(n−1)O(n^{-1}) rate of constant-step GD. Although the optimality of psilp_{\mathrm{sil}} has been well supported by numerical evidence for small nn, a matching lower bound has remained missing. In this paper, we prove an Ω(n−psil−o(1))Ω(n^{-p_{\mathrm{sil}}-o(1)}) lower bound for GD, showing that psilp_{\mathrm{sil}} is the optimal convergence exponent. Additionally, we prove an anytime lower bound that matches the exponent 2psil/(1+psil)≈1.11952p_{\mathrm{sil}}/(1+p_{\mathrm{sil}})\approx1.1195 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

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 O(n−psil)O(n^{-p_{\mathrm{sil}}}) rate, where psil=log⁡2(1+2)≈1.2716p_{\mathrm{sil}}=\log_2(1+\sqrt2)\approx1.2716, improving upon the classical O(n−1)O(n^{-1}) rate of constant-step GD. Although the optimality of psilp_{\mathrm{sil}} has been well supported by numerical evidence for small nn, a matching lower bound has remained missing. In this paper, we prove an Ω(n−psil−o(1))Ω(n^{-p_{\mathrm{sil}}-o(1)}) lower bound for GD, showing that psilp_{\mathrm{sil}} is the optimal convergence exponent. Additionally, we prove an anytime lower bound that matches the exponent 2psil/(1+psil)≈1.11952p_{\mathrm{sil}}/(1+p_{\mathrm{sil}})\approx1.1195 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.

查看此版本解读 →查看此版本原文 ↗