# Second-Order Bilevel Optimization with Accelerated Convergence Rates

arXiv: https://arxiv.org/abs/2605.06431 · HTML: https://mlsanity.com/paper/2605.06431/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2026.

## Built on by (most cited first, 1 of 1)

- [ABO-Med: Accelerated Bilevel Optimization for Few-Shot Medical Image Classification](https://mlsanity.com/paper/2609.33176/) (2026)

## Abstract (arXiv)

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 tildeO(ε-1.5) for finding the (ε, O(√ε)) 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 √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.