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

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 $(\epsilon ,\epsilon )$-stationarity in $O({\epsilon }^{-2})$ iterations using $O({\epsilon }^{-4})$ upper-level and $O({\epsilon }^{-7})$ lower-level stochastic gradients, which improves upon the best assumption-free complexities. We additionally derive anytime parameter schedules.