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

arXiv:2609.06580v1 Announce Type: cross 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 (arepsilon, arepsilon)-stationarity in O(arepsilon^{-2}) iterations using O(arepsilon^{-4}) upper-level and O(arepsilon^{-7}) lower-level stochastic gradients, which improves upon the best assumption-free complexities. We additionally derive anytime parameter schedules.

Source: arXiv cs.LG | 2026-09-09