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

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

## Key facts

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

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

- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [BLUR: A Bi-Level Optimization Approach for LLM Unlearning](https://mlsanity.com/paper/2506.08164/) (2025)
- [A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2206.08868/) (2022)
- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2308.07536/) (2023)
- [A Method with Convergence Rates for Optimization Problems with Variational Inequality Constraints](https://mlsanity.com/paper/2007.15845/) (2020)
- [Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems](https://mlsanity.com/paper/2507.14122/) (2025)
- [Stochastic Krasnoselskii-Mann Iterations: Convergence without Uniformly Bounded Variance](https://mlsanity.com/paper/2604.22581/) (2026)
- [An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization](https://mlsanity.com/paper/2402.08097/) (2024)
- [Improved guarantees for optimal Nash equilibrium seeking and bilevel variational inequalities](https://mlsanity.com/paper/2307.12511/) (2023)
- [Bias-Optimal Bounds for SGD: A Computer-Aided Lyapunov Analysis](https://mlsanity.com/paper/2505.17965/) (2025)
- [On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization](https://mlsanity.com/paper/2507.23155/) (2025)
- [Regularization methods for solving hierarchical variational inequalities with complexity guarantees](https://mlsanity.com/paper/2512.20772/) (2025)
- [Stochastic Dynamic Barrier Perturbed Gradient Methods for Nonconvex Simple Bilevel Optimization](https://mlsanity.com/paper/2607.10957/) (2026)

## Abstract (arXiv)

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.