Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption

Daniel Cortild; Mathias Staudigl; Juan Peypouquet; Coralia Cartis

math.OCSep 6, 2026

Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption

Authors: Daniel Cortild, Mathias Staudigl, Juan Peypouquet, Coralia Cartis

Organizations: Mathematical Institute, University of Oxford, United Kingdom · Department of Business Analytics and Decision Sciences, University of Economics and Business, Vienna, Austria · Bernouilli Institute, University of Groningen, The Netherlands

Abstract

We investigate stochastic simple bilevel optimization with smooth and possibly nonconvex upper- and lower-level objectives. Existing stochastic extensions of dynamic barrier gradient descent (DBGD) either obtain fast convergence under an unverifiable trajectory-dependent ``rare-visit'' assumption, or remove this assumption at a substantially higher oracle cost. We show that a simple denominator-only regularization of the DBGD multiplier eliminates the need for such an assumption while preserving fast convergence rates. Specifically, our method achieves $(\varepsilon, \varepsilon)$ -stationarity in $O(\varepsilon^{-2})$ iterations using $O(\varepsilon^{-4})$ upper-level and $O(\varepsilon^{-7})$ lower-level stochastic gradients, which improves upon the best assumption-free complexities. We additionally derive anytime parameter schedules.

Figures & tables

Algorithm	Setting	Iterations	Upper	Lower	Extra Assumption?
DBGD Cao et al. (2026)	Det	$\mathcal{O}(\varepsilon^{-2})$	$\mathcal{O}(\varepsilon^{-2})$	$\mathcal{O}(\varepsilon^{-2})$	N/A
SDBPG Ahmadi et al. (2026)	Sto	$\mathcal{O}(\varepsilon^{-2})$	$\mathcal{O}(\varepsilon^{-2/\varsigma})$	$\mathcal{O}(\varepsilon^{-3/\varsigma})$	Yes 1,2
PR-SDBPG Ahmadi et al. (2026)	Sto	$\mathcal{O}(\varepsilon^{-4})$	$\mathcal{O}(\varepsilon^{-8})$	$\mathcal{O}(\varepsilon^{-10})$	Yes, but verifiable 2
VR-PR-SDBPG Ahmadi et al. (2026)	Sto	$\mathcal{O}(\varepsilon^{-4})$	$\mathcal{O}(\varepsilon^{-6})$	$\mathcal{O}(\varepsilon^{-8})$	Yes, but verifiable 2,3
SDBGD (This work)	Sto	$\mathcal{O}(\varepsilon^{-2})$	$\mathcal{O}(\varepsilon^{-4})$	$\mathcal{O}(\varepsilon^{-7})$	N/A

Table 1: Comparison of iteration count, and upper- and lower-level (stochastic) oracle calls to reach a

(\varepsilon,\varepsilon)

-stationary point, and the additionally required assumptions.

Figure 1: Comparison of stationarity measures in terms of stochastic oracle calls.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Method	Step-Size ( $\eta_{k}$ )	Barrier ( $\beta_{k}$ )	Regul. ( $\rho_{k},\gamma_{k}$ )	Upp.-Bat. ( $B_{f,k}$ )	Low.-Bat. ( $B_{g,k}$ )	Other
SDBGD	$0.05t_{k}^{-1/4}$	$0.5t_{k}^{-1/4}$	$t_{k}^{-3/2}$	$\lfloor t_{k}\rfloor$	$\lfloor t_{k}^{5/2}\rfloor$	N/A
SDBPG	$0.05t_{k}^{-1/4}$	$0.5t_{k}^{-1/4}$	$t_{k}^{-1}$	$\lfloor t_{k}\rfloor$	$\lfloor t_{k}^{2}\rfloor$	N/A
PR-SDBPG	$0.05t_{k}^{-1/2}$	$0.5t_{k}^{1/4}$	$1$	$\lfloor t_{k}\rfloor$	$\lfloor t_{k}^{3/2}\rfloor$	$\mu_{k}=1$
VR-PR- SDBPG	$0.05t_{k}^{-1/2}$	$0.5t_{k}^{1/4}$	$1$	$\lfloor t_{k}^{1/2}\rfloor$	$\lfloor t_{k}\rfloor$	$\mu_{k}=1$ $\alpha_{k}=0.2t_{k}^{-1/2}$

Appendix

Table 2: Parameter choices for the compared methods. Here,

t_{k}=k+1

for convenience.

Stochastic Bilevel Optimization

See all 15 papers

A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization
Oct 5, 2026Xingyu Chen, Ming Yang, Quanqi Hu +1Stochastic Bilevel Optimization Bilevel Optimization
Department of Computer Science and Engineering Texas A&M University, College Station, USA
Optimal Stochastic Bilevel Optimization with First-Order Oracles
Oct 1, 2026Linxuan Pan, Junchi YangStochastic Bilevel Optimization Oracle Complexity
The Chinese University of Hong Kong, Shenzhen
SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimization
Aug 24, 2026Zhihao Gu, Qilong Wu, Junchi YangStochastic Bilevel Optimization Bilevel Optimization
Department of Industrial and Manufacturing Engineering The Pennsylvania State University · School of Data Science The Chinese University of Hong Kong, Shenzhen · Shenzhen Research Institute of Big Data and Shenzhen International Center for Industrial and Applied Mathematics

Oct 5, 2026J/K move · Enter open · S save

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

Xingyu Chen, Ming Yang, Quanqi Hu, Tianbao Yang

Department of Computer Science and Engineering Texas A&M University, College Station, USA

Stochastic Bilevel Optimization Bilevel Optimization Stochastic Optimization Convergence

Open paper AskPDF 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})

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.

Abstract

Stochastic Bilevel Optimization

Explore similar work

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

Optimal Stochastic Bilevel Optimization with First-Order Oracles

SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimization