{"id":"arxiv/2610.03633","url":"https://arxiv.org/abs/2610.03633","tags":["math.OC"],"score":0,"title":"Closing the Accuracy Gap in Stochastic First-Order Bilevel Optimization","domain":"math.OC","source":"arxiv","authors":["Haihan Zhang","Wendao Wu","Chenheng Zhang","Yanyi Li","Chunyuan Zheng","Cong Fang","Haoxuan Li","Zhouchen Lin"],"reviews":0,"subject":"math.OC","summary":"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 $\\mathbb{E}|\\nabla F(\\widehat{x})|\\leε$. Let $L$ be the common first-order scale, $μ$ the lower strong-convexity modulus, $ρ$ the lower…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-02","reactions":{}}