The Minimax Cost of Smoothness in Fully First-Order Stochastic Bilevel Optimization

Abstract

We study the sample complexity of finding a point with expected hypergradient norm at most $\epsilon >0$ in nonconvex--strongly-convex stochastic bilevel optimization using fresh, globally unbiased first-order samples with bounded variance. For lower-variable smoothness order $p\ge 1$, F${}^2$SA-$p$ achieves $\tilde{O}(p{\epsilon }^{-4-2/p})$ (Chen et al., 2026), but necessity of the exponent $4+2/p$ was open. We prove matching upper and lower bounds ${\Theta }_p({\epsilon }^{-4-2/p})$ under fixed nondegenerate regularity budgets, with constants allowed to depend on $p$. The lower bound holds for unrestricted randomized algorithms under a fixed sample budget, allows dimension to grow with accuracy, and preserves global unbiasedness and all prescribed lower-variable smoothness bounds, even with a scalar lower variable and exact upper gradients. We further characterize the minimax fixed-budget complexity under $L_j=M{\Lambda }^j(j!{)}^{\beta }$ for $j\ge 3$: $Q_{p,\beta }^{\ast }(\epsilon )=\Theta \left({\epsilon }^{-4}{\left[{\inf }_{1\le r\le p,,r\in \mathbb{N}}{r}^{\beta }{\epsilon }^{-1/r}\right]}^2\right)$, for $p\in \mathbb{N}\cup \infty$, with constants independent of $p$. At infinite order, this gives $\Theta ({\epsilon }^{-4})$ for $\beta =0$ and $\Theta ({\epsilon }^{-4}{\log }^2(1/\epsilon ))$ for $\beta =1$. A gradient-difference method with weighted independent batches attains these bounds uniformly in order. Thus quantitative smoothness yields precise gains, whereas qualitative analyticity alone still permits $\Theta ({\epsilon }^{-6})$ complexity.