Paper recorded by Signals 4 on 2026-09-08 in cs.LG. Abstract reproduced from arXiv; link to the original below.
Published 2026-09-08 on arXiv · recorded by Signals 4 on 2026-09-09
Category: cs.LG · 机器学习 · first seen 2026-09-09
We study how far gradient descent (GD) can be accelerated by predetermined nonnegative stepsizes in smooth convex optimization. Writing $p_{\mathrm{sil}}=\log_2(1+\sqrt{2})$, we prove an $Ω\left(n^{-p_{\mathrm{sil}}-O(\sqrt{\log\log n/\log n})}\right)$ non-anytime lower bound. In the anytime setting, every infinite nonnegative schedule has infinitely many horizons with error $Ω\left(n^{-\frac{2p_{