Neon2: Finding Local Minima via First-Order Oracles
This addresses the challenge of efficient local-minimum finding in non-convex optimization for machine learning practitioners, offering a novel reduction that enhances existing algorithms without performance loss.
The paper tackles the problem of finding local minima in non-convex optimization by proposing a reduction that converts stationary-point algorithms into local-minimum finders and replaces Hessian-vector products with gradient computations, resulting in first-order methods like Natasha2 and improved algorithms such as SGD and SVRG that outperform some best-known results.
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 performance. It also converts SGD, GD, SCSG, and SVRG into algorithms finding approximate local minima, outperforming some best known results.