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

Daniel Cortild, Mathias Staudigl, Juan Peypouquet, Coralia Cartis

arXivarxiv/2609.06580Sep 6, 2026math.OCscore 0

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,…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.06580
curl -X POST /api/v1/records/arxiv/2609.06580/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.06580/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'