A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization
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(ε−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 approximation. To address this challenge, we develop a stochastic SIngle-loop COnstant-Batch first-order penalty method (SICO) that combines two complementary ingredients. First, it performs one stochastic-gradient update per-iteration for both the original lower-level and penalized problems, with a projection that controls the separation between their iterates. Second, it applies an exponential moving average to stabilize the upper-level gradient estimator. We show that this combination achieves $ O(ε^{-6}) $ sample complexity using only O(1) stochastic-gradient samples per iteration under unbiased, bounded-variance stochastic gradients. Under the additional mean-square smoothness assumption on the lower-level stochastic gradients, the same algorithm improves the complexity to O(ε−4) also with O(1) batch size. To the best of our knowledge, this is the first work to match the best-known convergence rate for fully first-order SBO methods using a single loop and a constant batch size. This result addresses an open problem posed in the literature.
Related
- Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption
- An Ω(κy8ε−6) Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles
- Optimal Stochastic Bilevel Optimization with First-Order Oracles
- Multilevel Monte Carlo for Zeroth-Order Stochastic Bilevel Optimization with Inexact Lower Level Solves
- The Minimax Cost of Smoothness in Fully First-Order Stochastic Bilevel Optimization
BibTeX
@misc{chen2026singleloop,
title = {{A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization}},
author = {Xingyu Chen and Ming Yang and Quanqi Hu and Tianbao Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07290},
eprint = {2610.07290},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07290},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization
AU - Xingyu Chen
AU - Ming Yang
AU - Quanqi Hu
AU - Tianbao Yang
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.07290
UR - https://arxiv.org/abs/2610.07290
AB - 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 approximation. To address this challenge, we develop a stochastic SIngle-loop COnstant-Batch first-order penalty method (SICO) that combines two complementary ingredients. First, it performs one stochastic-gradient update per-iteration for both the original lower-level and penalized problems, with a projection that controls the separation between their iterates. Second, it applies an exponential moving average to stabilize the upper-level gradient estimator. We show that this combination achieves $ O(ε^{-6}) $ sample complexity using only O(1) stochastic-gradient samples per iteration under unbiased, bounded-variance stochastic gradients. Under the additional mean-square smoothness assumption on the lower-level stochastic gradients, the same algorithm improves the complexity to O(ε^−4) also with O(1) batch size. To the best of our knowledge, this is the first work to match the best-known convergence rate for fully first-order SBO methods using a single loop and a constant batch size. This result addresses an open problem posed in the literature.
ER -