{"ID":6538265,"CreatedAt":"2026-07-14T02:54:43.516908796Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.10957","arxiv_id":"2607.10957","title":"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 mild rare-visit assumption, SDBPG finds an $(ε_f,ε_g)$-stationary point in $\\mathcal{O}(\\max\\{ε_f^{-2},ε_g^{-2}\\})$ iterations, with sample gradient complexities $\\mathcal{O}(ε^{-4})$ and $\\mathcal{O}(ε^{-6})$ for the upper- and lower-level objectives where $ε=\\max\\{ε_f,ε_g\\}$. 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.","short_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 bou...","url_abs":"https://arxiv.org/abs/2607.10957","url_pdf":"https://arxiv.org/pdf/2607.10957v1","authors":"[\"Mohammad Mahdi Ahmadi\",\"Jincheng Cao\",\"Aryan Mokhtari\",\"Erfan Yazdandoost Hamedani\"]","published":"2026-07-12T23:23:02Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}