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(\widehat{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.