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 interpolating that of gradient descent $O(n^{-1/2})$ and cubic regularized quasi-Newton $O(n^{-2/3})$. 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.