Parameter-Free Accelerated Quasi-Newton Method for Nonconvex Optimization

Abstract

We propose a quasi-Newton-type method for nonconvex optimization with Lipschitz continuous gradients and Hessians. The algorithm finds an $\epsilon$-stationary point within $\mathrm{O}(d^{1/4}{\epsilon }^{-13/8})$ function and gradient evaluations, where $d$ is the problem dimension. Our method is parameter-free in the sense that it requires no prior knowledge of problem-dependent parameters such as Lipschitz constants or the optimal value. Moreover, it does not need the target accuracy $\epsilon$ or the total number of iterations to be specified in advance. The result is achieved by combining several key ideas: momentum-based acceleration, quartic regularization for subproblems, and a scaled variant of the Powell-symmetric-Broyden (PSB) update.

27 pages, 2 figures, 1 table