An Omega(kappay8epsilon-6) Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles

Zhihao Gu; Qilong Wu; Junchi Yang

In the authors' words

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 $Ω (Δ κ_{y}^{2} ϵ^{- 2} max {1, σ^{2} κ_{y}^{6} ϵ^{- 4}})$ oracle queries to find an $ϵ$ -stationary point of its hyper-objective function, where $κ_{y}$ denotes the condition number of the lower-level problem. In particular, in the noise-dominated regime, the lower bound is $Ω (Δ σ^{2} κ_{y}^{8} ϵ^{- 6})$ . This establishes the optimality of the $ϵ^{- 6}$ dependence achieved by the best-known first-order stochastic methods.

Main resultThe abstract does not state a limitation.

An Ω(κy8​ϵ−6) Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles

In the authors' words

More on Optimization that day

Benign Nonconvex Landscape for Policy Optimization: Infinite-Horizon Discounted MDPs with General State and Action Spaces

Beyond Shadow Weights: Quantization-Aware Training as Quantized-Endpoint Descent

Energy minimization for eight points on the sphere

Near-Optimal Acceleration for Smooth ℓp​ / ℓq​ Nondual Convex First-Order Oracle Optimization

Interference-Driven Clustered Optimisation for FM Spectrum Coordination

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

Near-Optimal Acceleration for Smooth $ℓ_{p}$ / $ℓ_{q}$ Nondual Convex First-Order Oracle Optimization