Optimal Stochastic Bilevel Optimization with First-Order Oracles

Abstract

We study nonconvex--strongly-convex bilevel optimization under a stochastic first-order oracle. We introduce MRT-FD, a single-loop first-order method that simultaneously tracks the upper-level variable, the lower-level solution, and the auxiliary response arising from implicit differentiation of the hyperobjective. MRT-FD performs one update of each variable per iteration and approximates the second-order derivative actions using order-p finite differences. For any fixed finite smoothness order p≥1 in the lower-level variable, MRT-FD finds an ε-stationary point using 𝒪(ε^−4−2/p) stochastic gradient queries. We also prove a matching Ω(ε^−4−2/p) oracle lower bound. The lower-bound construction starts from a hard nonconvex minimization chain with a stronger stochastic oracle, and lifts it to a bilevel problem through a sinusoidal coupling with a scalar lower-level variable. Consequently, the dependence on ε is optimal for every fixed finite p, closing the upper--lower complexity gap in this stochastic first-order oracle setting.

An Ω(κ_y⁸ε⁻⁶) Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles
Zhihao Gu, Qilong Wu, Junchi Yang
arXiv18 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles
Qihao Zhou, Shanshui Niu
arXiv17 Oct 2026PreprintCC BY 4.0Full textOptimisation & control StatisticsarXiv
The Minimax Cost of Smoothness in Fully First-Order Stochastic Bilevel Optimization
Wendao Wu, Haihan Zhang, Chenheng Zhang +5
arXiv19 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization
Xingyu Chen, Ming Yang, Quanqi Hu +1
arXiv5 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Closing the Accuracy Gap in Stochastic First-Order Bilevel Optimization
Haihan Zhang, Wendao Wu, Chenheng Zhang +5
arXiv19 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{pan2026optimal,
  title = {{Optimal Stochastic Bilevel Optimization with First-Order Oracles}},
  author = {Linxuan Pan and Junchi Yang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.01843},
  eprint = {2610.01843},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.01843},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Optimal Stochastic Bilevel Optimization with First-Order Oracles
AU  - Linxuan Pan
AU  - Junchi Yang
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2610.01843
UR  - https://arxiv.org/abs/2610.01843
AB  - We study nonconvex--strongly-convex bilevel optimization under a stochastic first-order oracle. We introduce MRT-FD, a single-loop first-order method that simultaneously tracks the upper-level variable, the lower-level solution, and the auxiliary response arising from implicit differentiation of the hyperobjective. MRT-FD performs one update of each variable per iteration and approximates the second-order derivative actions using order-p finite differences. For any fixed finite smoothness order p≥1 in the lower-level variable, MRT-FD finds an ε-stationary point using 𝒪(ε^−4−2/p) stochastic gradient queries. We also prove a matching Ω(ε^−4−2/p) oracle lower bound. The lower-bound construction starts from a hard nonconvex minimization chain with a stronger stochastic oracle, and lifts it to a bilevel problem through a sinusoidal coupling with a scalar lower-level variable. Consequently, the dependence on ε is optimal for every fixed finite p, closing the upper--lower complexity gap in this stochastic first-order oracle setting.
ER  -

Abstract

Related

Cite