Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption
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 (ε, ε)-stationarity in O(ε−2) iterations using O(ε−4) upper-level and O(ε−7) lower-level stochastic gradients, which improves upon the best assumption-free complexities. We additionally derive anytime parameter schedules.
Related
- Efficient Hessian-Free Methods for Multi-Objective Bilevel Optimization with Nonconvex Lower Level
- Improved KKT Complexity for First-Order Bilevel Optimization under Weak Lower-Level Convexity
- 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
BibTeX
@misc{cortild2026stochastic,
title = {{Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption}},
author = {Daniel Cortild and Mathias Staudigl and Juan Peypouquet and Coralia Cartis},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06580},
eprint = {2609.06580},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06580},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption
AU - Daniel Cortild
AU - Mathias Staudigl
AU - Juan Peypouquet
AU - Coralia Cartis
PY - 2026
DA - 2026/09/06
PB - arXiv
DO - 10.48550/arxiv.2609.06580
UR - https://arxiv.org/abs/2609.06580
AB - 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 (ε, ε)-stationarity in O(ε^−2) iterations using O(ε^−4) upper-level and O(ε^−7) lower-level stochastic gradients, which improves upon the best assumption-free complexities. We additionally derive anytime parameter schedules.
ER -