A Fast and Efficient Randomized Quasi-Newton Method

Abstract

We propose a novel randomized quasi-Newton method that scales well with problem dimension by leveraging a recent randomized low-rank Hessian approximation technique. Our algorithm achieves the seemingly exclusive benefits of the first-order and second-order methods. The iteration cost of our algorithm scales linearly with the problem dimension, as with the first-order methods. For non- convex smooth objectives, our algorithm globally converges to a stationary point with convergence rate $O(n^{-1/2})$, matching that of the standard gradient descent with an improved implicit constant. When the Hessian of the objective near a local minimum has a good low-rank approximation, our algorithm can leverage such local structure and achieve a linear local convergence with a rate superior to that of standard gradient descent. If the Hessian is actually low-rank, our algorithm achieves superlinear local convergence. We verify our theoretical results with various numerical experiments.