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

Excerpt

arXiv:2610.07290v1 Announce Type: cross Abstract: 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(\epsilon^{-6})$ or $O(\epsilon^{-4})$ sample complexity under standard bounded-variance assumption or mean-square smoothness assumption