On the Condition Number Dependency in Bilevel Optimization (arxiv.org)
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 $\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})$.
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})$.
Comments