Second-Order Bilevel Optimization with Accelerated Convergence Rates

This paper studies second-order methods for nonconvex-strongly-convex bilevel optimization. We propose a novel fully second-order bilevel approximation method (FSBA) that achieves an iteration complexity of $\tilde{\mathcal{O}}(\epsilon^{-1.5})$ for finding the $(\epsilon, \mathcal{O}(\sqrt{\epsilon}))$ second-order stationary point of the hyper-objective function. Our results demonstrate that second-order methods can achieve an accelerated convergence rate than first-order methods in bilevel optimization. To address the heavy computational cost associated with the second-order oracle, we introduce a lazy variant of FSBA, called LFSBA, which reuses second-order information across several iterations. We prove that LFSBA exhibits better computational complexity than FSBA by a factor of $\sqrt{d}$, where $d$ is the dimension of the problem. We also apply a similar idea to nonconvex strongly-concave minimax optimization and propose the lazy minimax cubic-regularized Newton (LMCN) method with better computational complexity compared to existing second-order methods.

Many machine learning systems are trained by solving one learning problem inside another. For example, an algorithm may first learn how to adapt a model to a specific task, and then use this result to improve how future adaptation should be done. This two-level structure, known as bilevel optimization, is powerful but often slow and computationally expensive. Our paper asks whether using richer information about the learning landscape can make this process faster. Instead of only using gradients, which tell an algorithm which direction to move, we study methods that also use second-order information, which describes how the landscape bends. Our main result shows that such second-order methods can achieve faster convergence for an important class of bilevel optimization problems. A key challenge is that second-order information is expensive to compute. To address this, we propose a lazy version of our method that reuses second-order information across several steps rather than recomputing it each time. This reduces the computational burden while preserving much of the acceleration. We also show that this idea extends to related minimax optimization problems.