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\ge1$, F$^2$SA-$p$ achieves $\widetilde 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\ge3$: $Q_{p,\beta}^*(\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.