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 ε>0 in nonconvex--strongly-convex stochastic bilevel optimization using fresh, globally unbiased first-order samples with bounded variance. For lower-variable smoothness order p≥1, F2SA-p achieves Õ(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 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 Lj=MΛj(j!)β for j≥3: Qp,β*(ε)=Θ(ε−4[inf1≤ r≤ p,,r∈ℕ rβε−1/r]2), for p∈ℕ∪∞, with constants independent of p. At infinite order, this gives Θ(ε−4) for β=0 and Θ(ε−4log2(1/ε)) for β=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 Θ(ε−6) complexity.
Related
- Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles
- Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption
- An Ω(κy8ε−6) Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles
- Optimal Stochastic Bilevel Optimization with First-Order Oracles
- Multilevel Monte Carlo for Zeroth-Order Stochastic Bilevel Optimization with Inexact Lower Level Solves
BibTeX
@misc{wu2026minimax,
title = {{The Minimax Cost of Smoothness in Fully First-Order Stochastic Bilevel Optimization}},
author = {Wendao Wu and Haihan Zhang 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.03638},
eprint = {2610.03638},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03638},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Minimax Cost of Smoothness in Fully First-Order Stochastic Bilevel Optimization
AU - Wendao Wu
AU - Haihan Zhang
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.03638
UR - https://arxiv.org/abs/2610.03638
AB - 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≥1, F^2SA-p achieves Õ(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 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Λ^j(j!)^β for j≥3: Q_p,β^*(ε)=Θ(ε^−4[inf_1≤ r≤ p,,r∈ℕ r^βε^−1/r]^2), for p∈ℕ∪∞, with constants independent of p. At infinite order, this gives Θ(ε^−4) for β=0 and Θ(ε^−4log^2(1/ε)) for β=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 Θ(ε^−6) complexity.
ER -