Quasi-Newton method with subspace gradients

In recent years, various subspace algorithms have been developed to handle large-scale optimization problems. Although existing subspace Newton methods require fewer iterations to converge in practice, the matrix operations and full gradient computation are bottlenecks when dealing with large-scale problems. We propose a subspace quasi-Newton method that is restricted to a deterministic subspace together with a subspace gradient based on random matrix theory. Our method does not require full gradients, let alone Hessian matrices. Yet, it achieves the same order of worst-case iteration complexity in expectation for both convex and nonconvex cases as existing subspace methods. In numerical experiments, we confirm the superiority of our algorithm in terms of computation time.