Finding Approximate Local Minima Faster than Gradient Descent

Understand

We design a non-convex second-order optimization algorithm that is guaranteed to return an approximate local minimum in time which scales linearly in the underlying dimension and the number of training examples.

• The time complexity of our algorithm to find an approximate local minimum is even faster than that of gradient descent to find a critical point.
• Our algorithm applies to a general class of optimization problems including training a neural network and other non-convex objectives arising in machine learning.