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

Wendao Wu, Haihan Zhang, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li, Zhouchen Lin

arXivarxiv/2610.03638Oct 2, 2026math.OCscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.03638
curl -X POST /api/v1/records/arxiv/2610.03638/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.03638/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'