Stochastic Dynamic Barrier Perturbed Gradient Methods for Nonconvex Simple Bilevel Optimization

Abstract

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 \emph{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 $δ\in (0, \tfrac{1}{2}]$, SDBPG finds an $(ε, ε)$-stationary point in $\mathcal{O}(ε^{-1/δ})$ iterations, with sample gradient complexities $\mathcal{O}(ε^{-2/δ})$ and $\mathcal{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.