Closing the Accuracy Gap in Stochastic First-Order Bilevel Optimization

Abstract

We characterize the optimal accuracy dependence for smooth nonconvex--strongly-convex bilevel optimization with stochastic first-order oracles. For globally unbiased fresh-gradient observations with bounded variance, we prove an $\Omega ({\epsilon }^{-6})$ lower bound matching the accuracy exponent of existing upper bounds. We consider globally Lipschitz gradients, a bounded upper gradient in the lower variable, and Lipschitz lower Hessian blocks, with target $\mathbb{E}|\nabla F(\hat{x})|\le \epsilon$. Let $L$ be the common first-order scale, $\mu$ the lower strong-convexity modulus, $\rho$ the lower Hessian-variation budget, $\kappa =L/\mu$, and $\chi =1+\rho /\mu$. For $\rho \gtrsim \mu$, $\chi \lesssim \kappa$, sufficiently high accuracy, and sufficiently large dimension, we establish $\Omega \left(L{\kappa }^2\Delta {\epsilon }^{-2}+L^3{\chi }^2{\kappa }^8{\sigma }_g^2\Delta {\epsilon }^{-6}\right)$, where $\Delta$ is the initial gap budget and ${\sigma }_g^2$ is the lower-gradient variance budget. The bound holds over full Euclidean spaces against arbitrary randomized adaptive algorithms, even when every sample is the gradient of a scalar function. In the common-scale regime $\rho =\Theta (L)$, the leading stochastic term has condition-number dependence ${\kappa }^{10}$, compared with the achievable ${\kappa }^{11}$ dependence. The proof embeds a sequential hard objective into an exact lower response while preserving global regularity and finite gap. A multiscale decomposition limits the gradient signal carrying each new direction, yielding the required sample complexity. We complement this lower bound with a frozen-linear-tilt estimator whose bias is proportional to lower Hessian variation. Its analysis makes this structural dependence explicit and yields matching leading rates in the specified curvature-controlled and small-gap regimes.