The paper investigates nonconvex–strongly-convex bilevel optimization using a stochastic first-order oracle. It introduces MRT‑FD, a single-loop first‑order algorithm that tracks the upper-level variable, the lower-level solution, and an auxiliary response from implicit differentiation, updating all variables in each iteration and approximating second‑order derivative actions via order‑p finite differences. For any fixed finite smoothness order p ≥ 1, MRT‑FD achieves an ε‑stationary point with O(ε^{‑4‑2/p}) stochastic gradient queries, and the authors prove a matching Ω(ε^{‑4‑2/p}) lower bound, thereby closing the complexity gap in this setting.
By Linxuan Pan, Junchi Yang
arXiv:2511. 19656v3 Announce Type: replace Abstract: Although upper bound guarantees for bilevel optimization have been widely studied, progress on lower bounds has been limited due to the complexity of the bilevel structure.
By Kaiyi Ji
In this work, we study the oracle complexity of finding an $ε$-stationary point for nonconvex-strongly-convex (NC-SC) bilevel optimization using only first-order oracles. Existing methods achieving th...
arXiv:2405. 00914v4 Announce Type: replace-cross Abstract: We present in this paper novel accelerated fully first-order methods in \emph{Bilevel Optimization} (BLO).
By Chris Junchi Li
The paper introduces single-loop stochastic projected damped extragradient (SPDE) and its variance-reduced variant (VR-SPDE) for stochastic nonconvex–(strongly) concave minimax problems. It provides SFO complexity bounds for achieving game stationarity and optimization stationarity, improving upon previous multi-loop methods while maintaining a single-loop structure. The results claim the best-known SFO complexities for these stationarity criteria among single-loop stochastic first‑order methods.
By Huiling Zhang, Minhao Zhang, Zi Xu
arXiv:2406. 13041v3 Announce Type: replace Abstract: Lower-bound analyses for nonconvex strongly-concave minimax optimization problems have shown that stochastic first-order algorithms require at least $\mathcal{O}(\varepsilon^{-4})$ sample complexity to find an $\varepsilon$-stationary point.
By Haoyuan Cai, Sulaiman A. Alghunaim, Ali H. Sayed
arXiv:2606. 01764v1 Announce Type: cross Abstract: We revisit the convergence guarantees of the Extragradient (EG) method for unconstrained biaffine min-max optimization.
By Yue Wu, Weiqiang Zheng, Yang Cai, Haipeng Luo
arXiv:2609. 12785v1 Announce Type: new Abstract: Classical convergence guarantees for stochastic gradient methods typically assume Lipschitz-smooth objectives and finite-variance gradient noise, both frequently violated in practice.
By Misbah Uz Zaman, Anirbit Mukherjee
arXiv:2504. 09951v2 Announce Type: replace-cross Abstract: We revisit a classical assumption for analyzing stochastic gradient algorithms where the squared norm of the stochastic subgradient (or the variance for smooth problems) is allowed to grow as fast as the squared norm of the optimization variable.
By Ahmet Alacaoglu, Yura Malitsky, Stephen J. Wright
arXiv:2609.16350v1 Announce Type: new
Abstract: Federated stochastic bilevel optimization has been actively studied in recent years due to its widespread applications in machine learning. However, mo...
By Yihan Zhang, Rohit Dhaipule, Chiu C Tan, Haibin Ling, Hongchang Gao
arXiv:2609. 30501v1 Announce Type: new Abstract: Although bilevel optimization (BLO) has emerged as a powerful framework for addressing many complex and nested machine learning problems in recent years, most existing studies are confined to the lower-level strongly convex (LLSC) or lower-level generally convex (LLGC) settings (i.
By Zhiyao Zhang, Menglu Yu, Alvaro Velasquez, Nathaniel D. Bastian, Jia Liu
arXiv:2509. 14952v3 Announce Type: replace Abstract: This paper considers the smooth bilevel optimization in which the lower-level problem is strongly convex and the upper-level problem is possibly nonconvex.
By Zhuanghua Liu, Luo Luo