Does the silver exponent remain optimal when gradient steps may be negative?
Let $h = (h_1, \dots, h_n) \in \mathbb{R}^n$ be a stepsize schedule, fixed in advance and possibly depending on $n$; negative and zero steps are allowed. For a differentiable convex $f : \mathbb{R}^d \to \mathbb{R}$ with $1$-Lipschitz gradient and a nonempty set of minimizers, gradient descent runs $$x_k = x_{k-1} - h_k \nabla f(x_{k-1}), \qquad k = 1, \dots, n,$$ and the schedule's worst-case error is $$R_n(h) = \sup_{d \ge 1} \, \sup_f \, \sup_{x_\star \in \operatorname{argmin} f} \, \sup_{x_0 \ne x_\star} \frac{f(x_n) - f(x_\star)}{\tfrac12 \|x_0 - x_\star\|^2}.$$ Put $p_{\mathrm{sil}} = \log_2(1 + \sqrt{2})$. The silver schedule of Altschuler and Parrilo, whose steps are positive, attains the rate $O(n^{-p_{\mathrm{sil}}})$. Ye and Liu proved that there is an absolute constant $C > 0$ such that $R_n(h) \ge n^{-p_{\mathrm{sil}} - C \sqrt{\log\log n / \log n}}$ for every sufficiently large $n$ and every $h \in [0, \infty)^n$, and, earlier, a lower bound $\Omega(n^{-1.6342})$ for arbitrary real schedules.
Problem. Is it true that for every $\delta > 0$ there are constants $c_\delta > 0$ and $n_\delta \ge 1$ such that $$R_n(h) \ge c_\delta \, n^{-p_{\mathrm{sil}} - \delta}$$ for every $n \ge n_\delta$ and every $h \in \mathbb{R}^n$?
Source: Ye and Liu (2026), §5, first remaining question (whether the lower and upper bounds match for schedules that may include negative stepsizes). Stated by AIM — Open Applied Problems for the polynomial exponent, with an arbitrary loss δ > 0.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- OC — Optimization and Control
- Keywords
- AIM Open Applied Problems, first-order methods, gradient descent, stepsize schedules
- Literature checked
- Nov. 5, 2026 by clemens-admin
References
@misc{yeliu2026silver,
author = {Ye, Yuhan and Liu, Kaizhao},
title = {Silver rate is (almost) optimal for gradient descent},
year = {2026},
eprint = {2609.09152},
archivePrefix = {arXiv},
}
@article{altschuler2025silver,
author = {Altschuler, Jason M. and Parrilo, Pablo A.},
title = {Acceleration by stepsize hedging: {S}ilver {S}tepsize {S}chedule for smooth convex optimization},
journal = {Math. Program.},
volume = {213},
number = {1--2},
year = {2025},
pages = {1105--1118},
doi = {10.1007/s10107-024-02164-2},
eprint = {2309.16530},
archivePrefix = {arXiv},
}
@misc{yeliu2026beyond,
author = {Ye, Yuhan and Liu, Kaizhao},
title = {Improved gradient descent lower bounds beyond {N}esterov},
year = {2026},
eprint = {2609.02855},
archivePrefix = {arXiv},
}
@misc{aim-does-the-silver-exponent-remain-optimal-when-gradient-steps-may-be-negative,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Does the silver exponent remain optimal when gradient steps may be negative?}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/4f5b1659355cb61d194da94ef14615214e1363a8/problems/732-does-the-silver-exponent-remain-optimal-when-gradient-steps-may-be-negative.md},
note = {Entry 732 at commit 4f5b165, 2026-11-04},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01115, "Does the silver exponent remain optimal when gradient steps may be negative?", clopen.solutions.