On the Condition Number Dependency in Bilevel Optimization

arXiv:2511.22331v2 Announce Type: replace-cross Abstract: Bilevel optimization minimizes an objective function, defined by an upper-level problem whose feasible region is the solution of a lower-level problem. We study the oracle complexity of finding an epsilon-stationary point with first-order methods when the upper-level problem is nonconvex, and the lower-level problem is strongly convex. Recent works (Ji et al., ICML 2021; Arbel and Mairal, ICLR 2022; Chen et al., JMLR 2025) achieve a ilde{O}(ar kappa_y^4 epsilon^{-2}) upper bound that is near-optimal in epsilon, which can be reduced to ilde{O}(ar kappa_y^{7/2} epsilon^{-2}) by a naive application of Nesterov acceleration in the inner loop, where ar kappa_y is the global condition number. However, the optimal dependency on the condition number is unknown. In this work, we establish a new Omega(kappa_y^{5/2} epsilon^{-2}) lower bound, where kappa_y < ar kappa_y is the lower-level condition number that is of the same order as ar kappa_y when the smoothness constants are O(1). Our lower bound establishes the first provable gap in terms of condition number dependency between bilevel problems and minimax problems in this setup. Our lower bounds can be extended to various settings, including high-order smooth functions, stochastic oracles, and convex hyper-objectives: (1) For second-order and arbitrarily smooth problems, we show lower bounds of Omega({kappa_y^{31/14}} epsilon^{-12/7}) and Omega(kappa_y^{21/10} epsilon^{-8/5}), respectively. (2) For convex-strongly-convex problems, we improve the previously best lower bound (Ji and Liang, JMLR 2022) from Omega(kappa_y /sqrt{epsilon}) to Omega(kappa_y^{3/2} / sqrt{epsilon}). (3) For smooth stochastic problems, we also show a lower bound of Omega(kappa_y^4 epsilon^{-4}).

Source: arXiv cs.AI | 2026-06-10