An $Ω(κ_y^8ε^{-6})$ Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles

This paper proves a sharp lower bound for finding an ε-stationary point in smooth nonconvex-strongly-convex bilevel optimization using only a standard unbiased stochastic first-order oracle with variance bounded by σ². For every adaptive randomized algorithm, the required oracle calls are Ω((Δκ_y²/ε²) max{1, σ²κ_y⁶/ε⁴}), where Δ is the initial optimality gap and κ_y is the lower-level condition number; in the noise-dominated regime, this becomes Ω(Δσ²κ_y⁸ε^-6). The result closes the previous ε^-2 gap between known stochastic first-order upper and lower bounds, establishing that the ε^-6 dependence achieved by methods such as F3 BSA and SGHA is information-theoretically unavoidable, although the condition-number dependence remains open compared with the best-known Õ(κ̄_y^11ε^-6) upper bound. Technically, the hard instance embeds Carmon-style smooth nonconvex zero-chains into a bilevel problem, uses smooth coordinate indicators and a Haar-random rotation to limit each query to one newly revealed coordinate, and injects Bernoulli importance-weighted noise into a compensated two-dimensional strongly convex quadratic block. This reduces stochastic-gradient variance by a factor proportional to κ_y² without weakening the resulting hypergradient, producing the κ_y⁸ε^-6 term under the standard global oracle model. The paper also reports assistance from OpenAI’s GPT-5.6 Sol and Codex in refining and formalizing the proof, while stating that the mathematical arguments were independently checked.