A Universally Optimal Multistage Accelerated Stochastic Gradient Method
Abstract
We study the problem of minimizing a strongly convex, smooth function when we have noisy estimates of its gradient. We propose a novel multistage accelerated algorithm that is universally optimal in the sense that it achieves the optimal rate both in the deterministic and stochastic case and operates without knowledge of noise characteristics. The algorithm consists of stages that use a stochastic version of Nesterov's method with a specific restart and parameters selected to achieve the fastest reduction in the bias-variance terms in the convergence rate bounds.
Cite
Text
Aybat et al. "A Universally Optimal Multistage Accelerated Stochastic Gradient Method." Neural Information Processing Systems, 2019.Markdown
[Aybat et al. "A Universally Optimal Multistage Accelerated Stochastic Gradient Method." Neural Information Processing Systems, 2019.](https://mlanthology.org/neurips/2019/aybat2019neurips-universally/)BibTeX
@inproceedings{aybat2019neurips-universally,
title = {{A Universally Optimal Multistage Accelerated Stochastic Gradient Method}},
author = {Aybat, Necdet Serhat and Fallah, Alireza and Gurbuzbalaban, Mert and Ozdaglar, Asuman},
booktitle = {Neural Information Processing Systems},
year = {2019},
pages = {8525-8536},
url = {https://mlanthology.org/neurips/2019/aybat2019neurips-universally/}
}