# Stochastic Dynamic Barrier Perturbed Gradient Methods for Nonconvex Simple Bilevel Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2026.

## Built on by (most cited first, 1 of 1)

- [Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption](https://mlsanity.com/paper/2609.06580/) (2026)

## Abstract (arXiv)

We study stochastic simple bilevel optimization with smooth, possibly nonconvex upper- and lower-level objectives accessed only through stochastic gradient oracles. A key challenge is that the dual multiplier induced by the lower-level constraint may become unbounded near lower-level stationary points, invalidating bounded-dual analyses and destabilizing stochastic gradient estimates. To address this, we propose Stochastic Dynamic Barrier Perturbed Gradient (SDBPG), a single-loop method that adaptively perturbs the dual formulation to regularize this degeneracy. The perturbation stabilizes the multiplier and yields controlled bias and variance even near the lower-level stationarity region. Under a rare-visit assumption governed by a parameter δ ∈ (0, tfrac12], SDBPG finds an (ε, ε)-stationary point in O(ε-1/δ) iterations, with sample gradient complexities O(ε-2/δ) and O(ε-3/δ) for the upper- and lower-level objectives, where larger δ corresponds to rarer visits to the bad region describing the negative alignment between the two objectives when the lower-level gradient is small. We further develop PR-SDBPG, a penalty-regularized variant that eliminates the rare-visit assumption, and VR-PR-SDBPG, which improves the resulting sample complexities entirely through variance reduction. To our knowledge, these are the first explicit (εf,εg)-stationarity guarantees for stochastic nonconvex-nonconvex simple bilevel optimization.