A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization

Xingyu Chen, Ming Yang, Quanqi Hu, Tianbao Yang

arXivarxiv/2610.07290Oct 5, 2026math.OCscore 0

Recent advances in penalty-based methods for stochastic bilevel optimization (SBO) have eliminated the need for second-order derivative oracles. However, for stochastic nonconvex-strongly convex bilevel problems, existing first-order methods typically rely on nested loops and/or large batch sizes for attaining $O(ε^{-6})$ or $O(ε^{-4})$ sample complexity under standard bounded-variance assumption or mean-square smoothness assumption. Achieving these rates with a single-loop penalty method and a constant batch size remains challenging due to a large penalty value needed for an accurate…

SourceJSON

Comments and reviews

No comments yet.

API

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