Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 25 min ago
PreprintarXiv licencearXiv

An Ω(κy8ε−6) Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles

  • Zhihao Gu
  • Qilong Wu
  • Junchi Yang
Open at sourcePDFDOICite

Abstract

We study the oracle complexity of finding ε-stationary points of smooth bilevel optimization problems with a nonconvex upper-level objective and a strongly convex lower-level problem. We consider a stochastic first-order oracle that returns unbiased stochastic gradients of both the upper- and lower-level objectives, with variance bounded by σ2. We prove that, for any initial optimality gap Δ>0 and all sufficiently small ε>0, every adaptive randomized first-order algorithm requires Ω (Δκy2 ε−2max{1,σ2κy6ε−4}) oracle queries to find an ε-stationary point of its hyper-objective function, where κy denotes the condition number of the lower-level problem. In particular, in the noise-dominated regime, the lower bound is Ω (Δσ2κy8ε−6). This establishes the optimality of the ε−6 dependence achieved by the best-known first-order stochastic methods.

Related

  1. Optimal Stochastic Bilevel Optimization with First-Order Oracles
    Linxuan Pan, Junchi Yang
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  2. Multilevel Monte Carlo for Zeroth-Order Stochastic Bilevel Optimization with Inexact Lower Level Solves
    Neil K. Chada, Mohammad S. Salehi, Mathias Staudigl +1
    arXivPreprintCC BY-NC-SA 4.0Full textNumerical analysis & scientific computingOptimisation & controlarXiv
  3. Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles
    Qihao Zhou, Shanshui Niu
    arXivPreprintCC BY 4.0Full textOptimisation & controlStatisticsarXiv
  4. An Ω(T3/4) lower bound for projection-free online learning with linear minimization oracles
    Julien Weibel, Pierre Gaillard, Wouter Koolen +1
    arXivPreprintCC BY 4.0Full textStatisticsarXivHAL
  5. Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption
    Daniel Cortild, Mathias Staudigl, Juan Peypouquet +1
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{gu2026ωκy8ε6,
  title = {{An $Ω(κ_y^8ε^-6)$ Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles}},
  author = {Zhihao Gu and Qilong Wu and Junchi Yang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.21905},
  eprint = {2609.21905},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.21905},
}
RIS
TY  - UNPB
TI  - An Ω(κ_y^8ε^−6) Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles
AU  - Zhihao Gu
AU  - Qilong Wu
AU  - Junchi Yang
PY  - 2026
DA  - 2026/09/18
PB  - arXiv
DO  - 10.48550/arxiv.2609.21905
UR  - https://arxiv.org/abs/2609.21905
AB  - We study the oracle complexity of finding ε-stationary points of smooth bilevel optimization problems with a nonconvex upper-level objective and a strongly convex lower-level problem. We consider a stochastic first-order oracle that returns unbiased stochastic gradients of both the upper- and lower-level objectives, with variance bounded by σ^2. We prove that, for any initial optimality gap Δ>0 and all sufficiently small ε>0, every adaptive randomized first-order algorithm requires Ω (Δκ_y^2 ε^−2max{1,σ^2κ_y^6ε^−4}) oracle queries to find an ε-stationary point of its hyper-objective function, where κ_y denotes the condition number of the lower-level problem. In particular, in the noise-dominated regime, the lower bound is Ω (Δσ^2κ_y^8ε^−6). This establishes the optimality of the ε^−6 dependence achieved by the best-known first-order stochastic methods.
ER  -