Second-Order Bilevel Optimization with Accelerated Convergence Rates

Sheng Yang, Chengchang Liu, Lesi Chen, John C. S. Lui

arXivarxiv/2605.06431May 7, 2026math.OCscore 0

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}}(ε^{-1.5})$ for finding the $(ε, \mathcal{O}(\sqrtε))$ 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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.06431
curl -X POST /api/v1/records/arxiv/2605.06431/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.06431/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'