We design a stochastic algorithm to train any smooth neural network to eps-approximate local minima, using O(e^{-3.25}) backpropagations. The best result was essentially O(e^{-4}) by SGD.

More broadly, it finds eps-approximate local minima of any smooth nonconvex function in rate O(e^{-3.25}), with only oracle access to stochastic gradients and Hessian-vector products.