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

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.