NeurIPS 2018spotlight274 citations
Natasha 2: Faster Non-Convex Optimization Than SGD
Abstract
We design a stochastic algorithm to find $\varepsilon$-approximate local minima of any smooth nonconvex function in rate $O(\varepsilon^{-3.25})$, with only oracle access to stochastic gradients. The best result before this work was $O(\varepsilon^{-4})$ by stochastic gradient descent (SGD).
BibTeX
@inproceedings{NEURIPS2018_79a49b3e,
author = {Allen-Zhu, Zeyuan},
booktitle = {Advances in Neural Information Processing Systems},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Natasha 2: Faster Non-Convex Optimization Than SGD},
url = {https://proceedings.neurips.cc/paper_files/paper/2018/file/79a49b3e3762632813f9e35f4ba53d6c-Paper.pdf},
volume = {31},
year = {2018}
}