{"id":"arxiv/2610.03638","url":"https://arxiv.org/abs/2610.03638","tags":["math.OC"],"score":0,"title":"The Minimax Cost of Smoothness in Fully First-Order Stochastic Bilevel Optimization","domain":"math.OC","source":"arxiv","authors":["Wendao Wu","Haihan Zhang","Chenheng Zhang","Yanyi Li","Chunyuan Zheng","Cong Fang","Haoxuan Li","Zhouchen Lin"],"reviews":0,"subject":"math.OC","summary":"We study the sample complexity of finding a point with expected hypergradient norm at most $ε>0$ in nonconvex--strongly-convex stochastic bilevel optimization using fresh, globally unbiased first-order samples with bounded variance. For lower-variable smoothness order $p\\ge1$, F$^2$SA-$p$ achieves $\\widetilde O(pε^{-4-2/p})$ (Chen et al., 2026), but necessity of the exponent $4+2/p$ was open. We prove matching upper and lower bounds $Θ_p(ε^{-4-2/p})$ under fixed nondegenerate regularity budgets, with constants allowed to depend on $p$. The lower bound holds for unrestricted randomized…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-02","reactions":{}}