{"id":"arxiv/2609.21905","url":"https://arxiv.org/abs/2609.21905","tags":["math.OC"],"score":0,"title":"An $Ω(κ_y^8ε^{-6})$ Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles","domain":"math.OC","source":"arxiv","authors":["Zhihao Gu","Qilong Wu","Junchi Yang"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-18","reactions":{}}