A universally optimal multistage accelerated stochastic gradient method

Necdet Serhat Aybat; Alireza Fallah; Mert Gürbüzbalaban; Asuman Ozdaglar

Conference paper, 2019

A universally optimal multistage accelerated stochastic gradient method

Necdet Serhat Aybat, Alireza Fallah, Mert Gürbüzbalaban, Asuman Ozdaglar

Advances in Neural Information Processing Systems (NeurIPS), 32, pp. 8523–8534, 2019.

Publisher page arXiv:1901.08022

In brief

An accelerated stochastic gradient method for strongly convex problems that is optimal in both of the terms that matter — the deterministic part of the error, which decays at the accelerated rate, and the noise part, which decays at the optimal statistical rate — without knowing the noise level in advance. The method proceeds in stages, each with its own stepsize and momentum, and achieves this universally over the noise.

Topics

Momentum & acceleration Risk & robustness

Cite

@inproceedings{aybat2019multistage,
  title   = {A universally optimal multistage accelerated stochastic gradient method},
  author  = {Necdet Serhat Aybat and Alireza Fallah and Mert Gürbüzbalaban and Asuman Ozdaglar},
  year    = {2019},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  volume  = {32},
  pages   = {8523--8534},
  url     = {https://proceedings.neurips.cc/paper/2019/hash/d630553e32ae21fb1a6df39c702d2c5c-Abstract.html},
  note    = {arXiv:1901.08022},
}