Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles

Abstract

We study nonconvex--strongly-convex bilevel optimization with finite-sum objectives and fully first-order oracles. We propose Sampled Implicit Corrections for Bilevel Optimization (SICBO), which combines a penalty approximation with variance-reduced corrections for the lower-level variables. Under componentwise lower strong convexity, SICBO finds a point x satisfying 𝔼|∇Φ(x)|²≤ε² within Õ(N+√Nκ^7/2ε⁻²) component-gradient calls, where N is the total number of components and κ is the normalized lower-level condition number. The bound achieves square-root finite-sum dependence using only gradients and preserves the best known deterministic fully first-order condition-number exponent for smooth problems. Our improvement follows from a curvature-dependent bound for nonlinear correction errors, which permits epochs of length Θ̃(√(N/κ)) with batches of size Θ̃(√(Nκ)). A single-level reduction shows that the dependence on N and ε is optimal up to logarithmic factors for fixed κ.

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
Optimal Stochastic Bilevel Optimization with First-Order Oracles
Linxuan Pan, Junchi Yang
arXiv1 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
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
Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms
Víctor Bucarey López, Sophia Calderón, Gonzalo Muñoz +1
Computational Optimization and Applications7 Aug 2026Peer-reviewedLicence not statedCombinatorics & discrete mathematicsHAL
Near-Optimal Convex Optimization with Lazy Second-Order Oracles
Xinliang Zhang, Lesi Chen, Chengchang Liu +1
arXiv2 Oct 2026PreprintCC0Full textOptimisation & control StatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{zhou2026accelerating,
  title = {{Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles}},
  author = {Qihao Zhou and Shanshui Niu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.24538},
  eprint = {2610.24538},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.24538},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles
AU  - Qihao Zhou
AU  - Shanshui Niu
PY  - 2026
DA  - 2026/10/17
PB  - arXiv
DO  - 10.48550/arxiv.2610.24538
UR  - https://arxiv.org/abs/2610.24538
AB  - We study nonconvex--strongly-convex bilevel optimization with finite-sum objectives and fully first-order oracles. We propose Sampled Implicit Corrections for Bilevel Optimization (SICBO), which combines a penalty approximation with variance-reduced corrections for the lower-level variables. Under componentwise lower strong convexity, SICBO finds a point x satisfying 𝔼|∇Φ(x)|^2≤ε^2 within Õ(N+√Nκ^7/2ε^−2) component-gradient calls, where N is the total number of components and κ is the normalized lower-level condition number. The bound achieves square-root finite-sum dependence using only gradients and preserves the best known deterministic fully first-order condition-number exponent for smooth problems. Our improvement follows from a curvature-dependent bound for nonlinear correction errors, which permits epochs of length Θ̃(√(N/κ)) with batches of size Θ̃(√(Nκ)). A single-level reduction shows that the dependence on N and ε is optimal up to logarithmic factors for fixed κ.
ER  -

Abstract

Related

Cite