Parameter-Free Accelerated Quasi-Newton Method for Nonconvex Optimization

We propose a quasi-Newton-type method for nonconvex optimization with Lipschitz continuous gradients and Hessians. The algorithm finds an varepsilon-stationary point within O(d1/4 varepsilon-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 varepsilon 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.