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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 24 references that are in the map.
- First posted on arXiv 5 Oct 2026.

## Builds on (most cited first, 6 of 6)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Self-Guided Noise-Free Data Generation for Efficient Zero-Shot Learning](https://mlsanity.com/paper/2205.12679/) (2022)
- [Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimization](https://mlsanity.com/paper/2105.02266/) (2021)
- [On the Complexity of First-Order Methods in Stochastic Bilevel Optimization](https://mlsanity.com/paper/2402.07101/) (2024)
- [SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimization](https://mlsanity.com/paper/2608.23211/) (2026)

## Abstract (arXiv)

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.