An $Ω(κ_y^8ε^{-6})$ Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles
We study the oracle complexity of finding $ε$-stationary points of smooth bilevel optimization problems with a nonconvex upper-level objective and a strongly convex lower-level problem. We consider a stochastic first-order oracle that returns unbiased stochastic gradients of both the upper- and lower-level objectives, with variance bounded by $σ^2$. We prove that, for any initial optimality gap $Δ>0$ and all sufficiently small $ε>0$, every adaptive randomized first-order algorithm requires $Ω\!\left(Δκ_y^2 ε^{-2}\max\{1,σ^2κ_y^6ε^{-4}\}\right)$ oracle queries to find an $ε$-stationary point…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.21905
curl -X POST /api/v1/records/arxiv/2609.21905/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.21905/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'