On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization
Jincheng Cao, Ruichen JiangErfan Yazdandoost Hamedani, Aryan Mokhtari · 2025
Read On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization by Jincheng Cao, Ruichen JiangErfan Yazdandoost Hamedani, Aryan Mokhtari (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-23155.txt.
Introduction
Jincheng Cao and co-authors wrote this 2025 mathematics paper on nested optimization problems where neither level is convex. In a simple bilevel problem, the upper goal is minimized only over points that already solve the lower problem. Without convexity downstairs, global optimality is out of reach, so the target becomes a stationary point.
Stationarity here means the upper objective cannot improve locally without hurting the lower one by more. The authors adapt a dynamic barrier gradient method to hunt such points with plain first-order steps. They prove the method reaches the target accuracy in polynomial time, with explicit rates for both levels. The result gives a usable algorithm for a problem class long considered intractable.
Catalog record
| CREATOR | Jincheng Cao, Ruichen JiangErfan Yazdandoost Hamedani, Aryan Mokhtari |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-23155
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization Jincheng Cao, Ruichen JiangErfan Yazdandoost Hamedani, Aryan Mokhtari Abstract In this paper, we study the problem of solving a simple bilevel optimization problem, where the upper-level objective is minimized over the solution set of the lower-level problem. We focus on the general setting in which both the upper- and lower-level objectives are smooth but potentially nonconvex. Due to the absence of additional structural assumptions for the lower-level objective—such as convexity or the Polyak–Łojasiewicz (PL) condition—guaranteeing global optimality is generally intractable. Instead, we introduce a suitable notion of stationarity for this class of problems and aim to design a first-order algorithm that finds such stationary points in polynomial time. Intuitively, stationarity in this setting means the upper-level objective cannot be substantially improved locally without causing a larger deterioration in the lower-level objective. To this end, we show that a simple and implementable variant of the dynamic barrier gradient descent (DBGD) framework can effectively solve the considered nonconvex simple bilevel problems up to stationarity. Specifically, to reach an ( ϵ f , ϵ g ) (\epsilon_{f},\epsilon_{g}) -stationary point—where ϵ f \epsilon_{f} and ϵ g \epsilon_{g} denote the target stationarity accuracies for the upper- and lower-level objectives, respectively—the considered method achieves a complexity of 𝒪 ( max ( ϵ f − 3 + p 1 + p , ϵ g − 3 + p 2 ) ) \mathcal{O}(\max(\epsilon_{f}^{-\frac{3+p}{1+p}},\epsilon_{g}^{-\frac{3+p}{2}})) , where p ≥ 0 p\geq 0 is an arbitrary constant balancing the terms. To the best of our knowledge, this is the first complexity result for a discrete-time algorithm that guarantees joint stationarity for both levels in general nonconvex simple bilevel problems. 1 Introduction In this paper, we consider the following nonconvex simple bilevel optimization problem \min_{\mathbf{x}\in\mathbb{R}^{n}}~f(\mathbf{x})\qquad\hbox{s.t.}\quad\mathbf{x}\in\mathcal{X}_{g}^{*}=\argmin_{\mathbf{z}\in\mathbb{R}^{n}}~g(\mathbf{z}), (1) where f,g:\mathbb{R}^{n}\to\mathbb{R} are continuously differentiable and \mathcal{X}_{g}^{*} denotes the solution set of the lower-level problem. This problem is referred to as simple bilevel. The term “simple” distinguishes this setting from general bilevel optimization, where the lower-level solution set \mathcal{X}_{g}^{*} may depend on the upper-level variable, introducing additional complexity. Owing to its numerous applications in areas such as lifelong learning [ Mal17 , JAMH23 ] and over-parameterized machine learning [ GLL21 , CJAYM23 ] , simple bilevel optimization has garnered significant recent interest in understanding its structure and developing efficient algorithms for finding its solution [ JAMH23 , CJAYM23 , Hsi+24 , TLRZ24 ] . The main challenge in solving Problem ( 1 ) stems from the fact that the feasible set, defined as the optimal solution set of the lower-level problem, lacks a clear characterization and is not explicitly given. As a result, a direct application of projection-based or projection-free methods is infeasible. Several works have studied the case where both the upper- and lower-level objectives are convex. In this case, Problem ( 1 ) is “well-behaved”, facilitating the application of various optimization techniques. For instance, several works [ Sol07 , DDD10 , KY21 , SBY24 ] employ Tikhonov regularization [ TA77 ] , combining the upper- and lower-level objectives with an appropriately chosen weight. Another line of research [ JAMH23 , CJAYM23 , CJYM24 ] provides a linear approximation of the lower-level objective to form an outer approximation of the lower-level optimal solution set \mathcal{X}_{g}^{*} . However, in several applications such as neural network training [ Hsi+24 ] , sparse representation learning [ GLL21 , TLRZ24 ] , and adversarial training [ Mad17 , WRK20 , Zha+22 ] , the objective functions at both levels are not necessarily convex. As a result, the lower-level solution set \mathcal{X}_{g}^{*} could be a nonconvex set, making it intractable to achieve any form of global optimality. Consequently, in nonconvex simple bilevel optimization, similar to its single-level counterpart, the primary objective is to find a near-stationary point rather than a near-optimal solution, as defined in [ JAMH23 , CJYM24 , ZCXZ24 ] . The search for near-stationary points in nonconvex simple bilevel problems has been addressed by only a few works. Among these, [ GLL21 ] proposed the Dynamic Barrier Gradient Descent (DBGD) algorithm, which employs a dynamic barrier constraint on the search direction at each iteration. By adaptively balancing objectives f and g with a dynamic combination coefficient, it guides the optimization trajectory. It was originally introduced to solve the constrained problem: \min_{\mathbf{x}\in\mathbb{R}^{n}}~f(\mathbf{x})\quad\text{s.t.}\quad g(\mathbf{x})\leq c, (2) where f and g are smooth but possibly nonconvex, c\geq g^{*} , and g^{*} is the minimum value of g . Note that the analysis in [ GLL21 ] is limited to the continuous-time limit behavior of DBGD (step size \eta\!\to\!0 ). Specifically, it was shown that the continuous-time dynamics of DBGD converge at a rate of \mathcal{O}(1/t) in terms of the violation of the Karush–Kuhn–Tucker (KKT) conditions of Problem ( 2 ) with the assumption of bounded dual iterates, i.e., \max_{t}\lambda_{t}<+\infty . For the specific choice of c=g^{*} , the problem in ( 2 ) becomes equivalent to the simple bilevel problem in ( 1 ). However, in this case, the assumption of bounded dual iterates is violated, rendering the associated theoretical guarantees inapplicable. Under the additional assumption that \|\nabla f\| and \|\nabla g\| are uniformly bounded, the presented continuous-time convergence rate deteriorates to \mathcal{O}(\max(1/t^{2/\tau},1/t^{1-1/\tau})) for any user-defined \tau>1 . More importantly, their analysis does not hold when considering the discrete time case (step size \eta>0 ). Another closely related work is [ Hsi+24 ] , which introduced BLOOP (BiLevel Optimization with Orthogonal Projection) for stochastic nonconvex simple bilevel problems. The core idea of BLOOP is to project the upper-level gradient onto the space orthogonal to the lower-level gradient. However, their analysis is limited to a non-asymptotic convergence rate of \mathcal{O}(1/K^{1/4}) for the lower-level objective, where K is the number of iterations, without providing any rate guarantees for the upper-level objective. Motivated by the above discussion, we aim to address the following research question: Is it possible to design a first-order method with discrete-time guarantees for both levels of the nonconvex simple bilevel problem in ( 1 ) under the given assumptions? Contributions. Motivated by this research question, We begin by defining a first-order stationarity metric for nonconvex simple bilevel problems in Section 3 , which intuitively identifies points where no significantly better solution exists in a local neighborhood. In Section 3.1 , we relate this notion to existing stationarity concepts in the literature. We then develop and analyze a practical variant of the dynamic barrier gradient descent (DBGD) method proposed in [ GLL21 ] , providing theoretical guarantees for its convergence in discrete time. The specifics of our main contributions are as follows: (i) We define an (\epsilon_{f},\epsilon_{g}) -stationary point for nonconvex simple bilevel optimization as a point \hat{\mathbf{x}} for which there exists \lambda\geq 0 such that \|\nabla f(\hat{\mathbf{x}})+\lambda\nabla g(\hat{\mathbf{x}})\|^{2}\leq\epsilon_{f} and \|\nabla g(\hat{\mathbf{x}})\|^{2}\leq\epsilon_{g} , where \epsilon_{f} and \epsilon_{g} specify the desired stationarity accuracy for the upper and lower levels. We also discuss how this notion relates to existing stationarity metrics in the constrained and bilevel optimization literature. (ii) We show that to achieve an (\epsilon_{f},\epsilon_{g}) -stationary point of the considered nonconvex simple bilevel problem, the studied method has a complexity of \mathcal{O}(\max(\epsilon_{f}^{-\frac{3+p}{1+p}},\epsilon_{g}^{-\frac{3+p}{2}})) , where p\geq 0 . This is the first explicit (discrete-time) complexity bound that guarantees