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 Ω(ε−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 𝔼|∇ F(x̂)|≤ε. Let L be the common first-order scale, μ the lower strong-convexity modulus, ρ the lower Hessian-variation budget, κ=L/μ, and χ=1+ρ/μ. For ρ≳μ, χ≲κ, sufficiently high accuracy, and sufficiently large dimension, we establish Ω(Lκ2Δε−2+L3χ2κ8σg2Δε−6), where Δ is the initial gap budget and σg2 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 ρ=Θ(L), the leading stochastic term has condition-number dependence κ10, compared with the achievable κ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.
Related
- An Ω(κy8ε−6) Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles
- Optimal Stochastic Bilevel Optimization with First-Order Oracles
- The Minimax Cost of Smoothness in Fully First-Order Stochastic Bilevel Optimization
- A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization
- Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption
BibTeX
@misc{zhang2026closing,
title = {{Closing the Accuracy Gap in Stochastic First-Order Bilevel Optimization}},
author = {Haihan Zhang and Wendao Wu and Chenheng Zhang and Yanyi Li and Chunyuan Zheng and Cong Fang and Haoxuan Li and Zhouchen Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03633},
eprint = {2610.03633},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03633},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Closing the Accuracy Gap in Stochastic First-Order Bilevel Optimization
AU - Haihan Zhang
AU - Wendao Wu
AU - Chenheng Zhang
AU - Yanyi Li
AU - Chunyuan Zheng
AU - Cong Fang
AU - Haoxuan Li
AU - Zhouchen Lin
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.03633
UR - https://arxiv.org/abs/2610.03633
AB - 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 Ω(ε^−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 𝔼|∇ F(x̂)|≤ε. Let L be the common first-order scale, μ the lower strong-convexity modulus, ρ the lower Hessian-variation budget, κ=L/μ, and χ=1+ρ/μ. For ρ≳μ, χ≲κ, sufficiently high accuracy, and sufficiently large dimension, we establish Ω(Lκ^2Δε^−2+L^3χ^2κ^8σ_g^2Δε^−6), where Δ is the initial gap budget and σ_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 ρ=Θ(L), the leading stochastic term has condition-number dependence κ^10, compared with the achievable κ^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.
ER -