  We develop a new algorithm for non-convex stochastic optimization that finds
an $\epsilon$-critical point in the optimal $O(\epsilon^{-3})$ stochastic
gradient and Hessian-vector product computations. Our algorithm uses
Hessian-vector products to "correct" a bias term in the momentum of SGD with
momentum. This leads to better gradient estimates in a manner analogous to
variance reduction methods. In contrast to prior work, we do not require
excessively large batch sizes, and are able to provide an adaptive algorithm
whose convergence rate automatically improves with decreasing variance in the
gradient estimates. We validate our results on a variety of large-scale deep
learning architectures and benchmarks tasks.
