@inproceedings{
moursi2023accelerated,
title={Accelerated gradient descent: A guaranteed bound for a heuristic restart strategy},
author={Walaa Moursi and Stephen A. Vavasis and Viktor Pavlovic},
booktitle={OPT 2023: Optimization for Machine Learning},
year={2023},
url={https://openreview.net/forum?id=tyRorUlaqi}
}
The $\mathcal{O}(1/k^2)$ convergence rate in function value of accelerated gradient descent is optimal, but there are many modifications that have been used to speed up convergence in practice. Among these modifications are restarts, that is, starting the algorithm anew with the current iteration being considered as the initial point. We focus on the adaptive restart techniques introduced by O'Donoghue and Candes, specifically their gradient restart strategy. While the gradient restart strategy is a heuristic in general, 
 we prove that applying gradient restarts 
 preserves and in fact improves the $\mathcal{O}(1/k^2)$ bound,
 hence establishing function value convergence, for one-dimensional functions.
Applications of our results to separable and nearly separable functions are presented.
Accelerated gradient descent: A guaranteed bound for a heuristic restart strategy
Walaa Moursi Stephen A. Vavasis Viktor Pavlovic