On the Condition Number Dependency in Bilevel Optimization

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 $\tilde{\mathcal{O}}(\bar \kappa_y^4 \epsilon^{-2})$ upper bound that is near-optimal in $\epsilon$, which can be reduced to $\tilde{\mathcal{O}}(\bar \kappa_y^{7/2} \epsilon^{-2})$ by a naive application of Nesterov acceleration in the inner loop, where $\bar \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 < \bar \kappa_y$ is the lower-level condition number that is of the same order as $\bar \kappa_y$ when the smoothness constants are $\mathcal{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})$.

Optimization and Control (math.OC); Artificial Intelligence (cs.AI); Machine Learning (cs.LG)

arXiv:2511.22331 [math.OC]

(or arXiv:2511.22331v2 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2511.22331 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.