Finding Local Minima for Nonconvex Optimization in Linear Time

Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, Tengyu Ma

Published 2016-11-03Version 1

We design a non-convex second-order optimization algorithm that is guaranteed to return an approximate local minimum in time which is linear in the input representation. The previously fastest methods run in time proportional to matrix inversion or worse. The time complexity of our algorithm to find a local minimum is even faster than that of gradient descent to find a critical point (which can be a saddle point). Our algorithm applies to a very general class of optimization problems including training a neural network and many other non-convex objectives arising in machine learning.