Open Problem: Anytime Convergence Rate of Gradient Descent
Abstract
Recent results show that vanilla gradient descent can be accelerated for smooth convex objectives, merely by changing the stepsize sequence. We show that this can lead to surprisingly large errors indefinitely, and therefore ask: Is there any stepsize schedule for gradient descent that accelerates the classic $\mathcal{O}(1/T)$ convergence rate, at \emph{any} stopping time $T$?
Cite
Text
Kornowski and Shamir. "Open Problem: Anytime Convergence Rate of Gradient Descent." Conference on Learning Theory, 2024.Markdown
[Kornowski and Shamir. "Open Problem: Anytime Convergence Rate of Gradient Descent." Conference on Learning Theory, 2024.](https://mlanthology.org/colt/2024/kornowski2024colt-open/)BibTeX
@inproceedings{kornowski2024colt-open,
title = {{Open Problem: Anytime Convergence Rate of Gradient Descent}},
author = {Kornowski, Guy and Shamir, Ohad},
booktitle = {Conference on Learning Theory},
year = {2024},
pages = {5335-5339},
volume = {247},
url = {https://mlanthology.org/colt/2024/kornowski2024colt-open/}
}