NEON2: Finding Local Minima via First-Order Oracles
Abstract
We propose a reduction for non-convex optimization that can (1) turn an stationary-point finding algorithm into an local-minimum finding one, and (2) replace the Hessian-vector product computations with only gradient computations. It works both in the stochastic and the deterministic settings, without hurting the algorithm's performance. As applications, our reduction turns Natasha2 into a first-order method without hurting its theoretical performance. It also converts SGD, GD, SCSG, and SVRG into algorithms finding approximate local minima, outperforming some best known results.
Cite
Text
Allen-Zhu and Li. "NEON2: Finding Local Minima via First-Order Oracles." Neural Information Processing Systems, 2018.Markdown
[Allen-Zhu and Li. "NEON2: Finding Local Minima via First-Order Oracles." Neural Information Processing Systems, 2018.](https://mlanthology.org/neurips/2018/allenzhu2018neurips-neon2/)BibTeX
@inproceedings{allenzhu2018neurips-neon2,
title = {{NEON2: Finding Local Minima via First-Order Oracles}},
author = {Allen-Zhu, Zeyuan and Li, Yuanzhi},
booktitle = {Neural Information Processing Systems},
year = {2018},
pages = {3716-3726},
url = {https://mlanthology.org/neurips/2018/allenzhu2018neurips-neon2/}
}