On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization
Authors: Jincheng Cao
Ruichen Jiang
Erfan Yazdandoost Hamedani
Aryan Mokhtari
Venue: NeurIPS 2025 poster ()
Keywords: bilevel optimization
nonconvex optimization
Primary area: optimization

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 $(\epsilon_f, \epsilon_g)$-stationary point—where $\epsilon_f$ and $\epsilon_g$ denote the target stationarity accuracies for the upper- and lower-level objectives, respectively—the considered method achieves a complexity of $\mathcal{O}(\max(\epsilon_f^{-\frac{3+p}{1+p}}, \epsilon_g^{-\frac{3+p}{2}}))$, where $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.

On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization
Jincheng Cao UT Austin j jinchengcaouutexas.ced
Ruichen Jiang UT Austin rj ejiannuutexas.oom edu
Erfan Yazdandoost Hamedani
Aryan Mokhtari
The University of Arizona erfany@arizona. edu
UT Austin & Google Research mokhtari Bokhtari@austine utexas edu
Abstract
In this paper, we study the problem of solving a simple bilevel optimization prob- lem, 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 the absence of additional structural assumptions for the lower-level objective such as con- vexity or the Dolyak-Lojasieen is generally intractable. Instead, we introduce 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 substantially improved locally with- out 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 (c,, Cg) (Cf:Cy)-station -stationnyy point-where ey and Cy denote the target stationarity accuracies for the upper- and lower-level objectives, respectively- the considered method achieves a complex-
(PL) condition guaranteeing global optimality
3+h Bie
fyy )), where 2 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.
ity of Omnax(e
1+p
Introduction
In this paper, we consider the following nonconvex simple bilevel optimization problem
min
f(x) s.t. X E X
argmin g(z),
XER"
zER"
where f.g: 12n - I are continuously differentiable and X denotes the solution set of the lower- level problem. This problem is referred as simple bilevel. The term "simple" distinguishes this setting from general bilevel optimization, where the lower-level solution set X may depend on the upper-level variable, introducing additional complexity. Owing its numerous applications in areas such as lifelong learning 2 and over-parameterized machine learning 3 4 simple bilevel optimization has garnered significant recent interest understanding structure and developing
efficient algorithms for finding its solution 2 4
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

The main challenge in solving Problem (I) 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 result, a direct application of projection-baset or projection-fre methods is infeasible. Several works have studied the case where both the upper- and lower-level objectives are convex. In this case, Problem ① is "well-behaved", facilitating the application of various optimization techniques, For instance, several works [ZHIO] employ Tikhonov regularization [[]], combining the upper- and lower-level objectives with an appropriately chosen weight. Another line of research 12 4 12) provides a linear approximation of the lower-level objective to form an outer approximation of the lower-level optimal solution set X²-
However, in several applications such as neural network training [5], sparse representation learning 61 and adversarial training [13] the objective functions at both levels are not necessarily convex. As result, the lower-level solution set X 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 to find near-stationary point rather than near-optimal solution, defined in (2) [6]
The search for near-stationary points in nonconvex simple bilevel problems has been addressed by only a few works. Among these, Gong et al. [3] proposed the Dynamic Barrier Gradient Descent (DBGD) algorithm, which employs dynamic barrier constraint on the search direction at each iteration. By adaptively balancing objectives f and with dynamic combination coefficient, it guides the optimization trajectory. was originally introduced to solve the constrained problem:
min f(x) s.t. g(x) Sc xER
(2)
where f and g are smooth but possibly nonconvex, c 2 g", and 9" is the minimum value of g. Note that the analysis in R is limited to the continuous-time limit behavior of DBGD (step size " 0). Specifically, it was shown that the continuous-ting dynamics of DBGD converge at a rate of (1/tt) in terms of the violation of the Karush-Kuhh Tucker (KKT) conditions of Problem 2 with the assumption of bounded dual iterates, i.c., max, X < +oc. For the specific choice of c = g" the problem in ( becomes equivalent to the simple bilevel problem in ( However, in this case, the assumption of bounded dual iterates is violated, rendering the associated theoretical guarantees inapplicable. Under the additional assumption that /fll and Vgl are uniformly bounded, the presented continuous-time convergence rate deteriorates to (mmax(1/t2/1 1/F)) for any user- defined r > 1. More importantly, their analysis does not hold when considering the discrete time case (step size 17 > 0).
Another closely related work is 5 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 asymptot convergence rate of O(1/K)/4) for the lower-level objective, where Ki is the number of iterations, without providing any rate guarantees for the upper-level objective.
Motivated by the above discussion, 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 ① 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 3 which intuitively identifies points where no significantly better solution exists in a local neighborhood. In Section [.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 3 providing theoretical guarantees for its convergence in discrete time. The specifics of our main contributions are as follows:
(i) We define (e -stattionn point for nonconvex simple bilevel optimization as a point & for which there exists À 2 0 such that [ + gx)(2) S cy and || gx)())] < <g.. where c and cy specify the desired stationarity accuracy for the upper and lower levels. We also discuss how this notion relates to existing stationarity metries in the constrained and bilevel optimization literature.
(ii) We show that to achieve an (e,, (gy -sttttionn point of the considered nonconvex simple bilevel
Le 81x
problem, the studied method has complexity of O(max(e, Eg )), where p 2 0. This is the
2

---

first explicit (discrete-tine) time) complexity bound that guarantees stationarity at both levels for nonconvex simple bilevel problems.
Further connections between first-order methods for convex and nonconvex simple bilevel problems and the DEGD framework are discussed in Appendix C
1.1 Related Work
Convex simple bilevel problems. Most studies on the "simple bilevel optimization problem" focus cases where both the upper-level and lower-level objective functions convex. Various approaches have been developed to address such convex simple bilevel optimization problems, including regularization-based methods 7710 177, penalty-based methods [88], sequential averaging methods [21], lower-level linearized based methods 22 12).
methods [9 20], pnline-learning-basee
and sneectionbbaed methods [22] [16. However, due to the convexity assumption underlying these algorithms, they are not applicable in our setting.
Nonconvex constrained minimization problems. The simple bilevel problem ① also be reformulated as Problem (2) with c g². This reformulation suggests that existing method for functionally constrained optimization 2 30 could be applied to solve ( However, this approach presents several challenges. First, since g is nonconvex, estimating 9 to high accuracy is intractable. Moreover, Problem (2) does satisfy strict feasibility, and most common constraint qualifications, Constraint Qualification, do not hold. Hence, many results, such may longer hold.
such as the Mangasarian-Frromovy
those in
27 30 29
Nonconvex general bilevel problems. Recent works on nonconvex general bilevel optimization 31 rely different stationarity notions assumptions and are thus directly applicable to setting. For instance, the works in (2] define stationarity based on the norm of the hyper-gradient gradient, which may be ill-defined in the simple bilevel setting where upper-level variables present, rendering it an invalid metric. Moreover, most existing approaches assume the Polyak-Loojsiewwin (PL) condition [3 35
31 32) for the lower-level problem assumption not made in setting, thereby invalidating the convergence guarantees established in those works. A detailed comparison between algorithms for general and simple bilevel problems, along with discussion of different stationarity metrics and other related methods, is provided in Appendix D
After our submission, we became aware of a concurrent work (37,, which provides a similar analysis for a variant of our algorithm. Their study further demonstrates the algorithm's 's effectiveness in the context of machine unlearning, revealing additional and complementary application area to our theoretical and empirical findings.
Assumptions
We denote g oo and f -o as the minimum value of y and respectively. We next formally state our assumptions.
Assumption 2.1. We assume these conditions hold:
(i) f has bounded gradients, i.e., [[V SG3- < for any x E R.
(ii f continuously differentiable, and f Lipsschit i.e., [[Vf(x) vf(y))l s 4, 1x|xx |x- yll.
(iii) is continuously differentiable, and Vg g is Ly Lipischhit iee. Vg(x)= Vo(y)) S 4 yll-
3 Stationarity Metric
This section introduces our performance metric for evaluating convergence rates of algorithms for Problem (I). While objective value gap is commonly used in convex settings TO 12 22 [6), it intractable here due to the potential nonconvexity of and g. Instead, we measure stationarity, defining approximate stationary point as a point & R" where no significantly better solution exists nearby one that lowers g, or lowers f without increasing g. We next present first-order conditions that capture this notion, followed by their interpretation.

---

Definition 3.1. Given Ej 2 0 and Eg 2 0, point & E R is an (cz, Eg) stationaay point of Problem T if there exists a scalar X 2 such that:
VV( 1 Cg and [V XVg(x))1 c,.
Definition 3.1 consists of two conditions that measure the stationarity of a given solution x. The first condition requires that the gradient of the lower-level objective g at x is small, meaning that is stationary for g. To better interpret the second condition, we first introduce decomposition that expresses the upper-level gradient f(() as the sum of two orthogonal components: one parallel to Vg(&) and the other orthogonal to it. Specifically, we write Vf( = ( + Vfi (x), where
V/jj is the component parallel to Vy(x) and V (x) is the component orthogonal to (g(x). Using this decomposition, we can further express:
+(x)++
Vi + (V)i(() + AVg(x))
(4)
where the first term is orthogonal to Vg(x) and the second part (in parenthesis) is parallel to it. Hence, the conditions (3) ensure that all the following norms are small: (i) [[Vg())] (ii) V (x) and
(iii) ($) X VVg()) Interestingly, as shall show in the convergence analysis, these terms do not necessarily diminish at the same rate.
This decomposition offers key insights into the final output. If the first two terms small, the resulting point satisfies two key conditions: (i) the gradient norm of the lower-level problem is small, and (ii) the component of the upper-level gradient orthogonal to the lower-level gradient is also small. In other words, in directions that do not negatively impact the lower-level objective, there is no remaining energy to further decrease the upper-level objective.
The third term being small leads to two possible cases. If ( aligned with Vg(x). then since [[](()]] is small and À 0, it follows that V (x)()) is also small. Combined with the smallness of [V (x)]l, this implies [X)] is small well. On the other hand, if V f (St) is in the opposite direction of ( cannot make definitive statement about [[ (xx) as À could be large.
Hence, any point satisfying the conditions in 3 must fall into one of the following two cases:
Case I: At &, both [ and [[)]] are small, indicating near-stationarity for both the lower- and upper-level objectives.
Case I: At /V]())] is small and the gradient of ʃ has minimal energy directions orthogonal to Vg(x) and its remaining energy (norm) is in the opposite direction of gg(
In both cases, we reach point where further decreasing f would necessarily increase g. indicating that no additional progress can be made without violating the constraint. This means the objective function cannot be significantly improved in its local neighborhood without incurring greater infeasibility. This concept is formally characterized in the following lemma.
Lemma 3.1. A point & E IR" is an (g stationaay point of Problem ① if only if the following holds: for any > O, there exists a radius f > O such that for all r f:
For any x satisfying ||x x|| S have g(x) 2 g(x) (1 8) - x||.
For any x satisfying |x
* S and g(x) S g(x), we have f(x) 2 f(x) (1 + 8) -x]
The first condition of the lemma guarantees that the lower-level objective g cannot be improved by more than O xx [|||||xx]] xxI) locally. The second condition further shows that the upper-level objective
cannot be significantly improved without negatively impacting g.
3.1 Connections with Other Stationarity Metrics
In this section, we examine the connection between our proposed stationarity metrics in Definition 3.1 and existing notions of stationarity in both constrained optimization and bilevel optimization literature.
3.1.1
Connection with the Metrics in Constrained Optimization Literature
We note that Definition 3.1 is closely related to approximate KKT conditions for reformulation of Problem (I) Specifically, recall g" mmixxeR" g(x) and the constraint in i is equivalent to

---

g(x) g" I O. Thus, Problem 1 can be reformulated as Problem 2 with c= =g". Given point
and Lagrange multiplier À 2 the KKT conditions for 2 are:
g(x) g" O, A 2 0, Vf(x) + AVg(x) = 0, X(g(x): - g²) =
However, since Problem 2 with c= g is not strictly feasible, Slater's condition does not hold, and the KKT conditions may not hold an optimal solution. Moreover, since g is nonconvex, enforcing strict feasibility is intractable. To resolve this, the literature on nonconvex constrained optimization has considered relaxed stationarity conditions such as the scaled KKT conditions 27 When specialized to Problem ( these papers aim to find point x that satisfies one of the following for given accuracy parameters Ep and Cg: (i) & satisfies an approximate scaled KKT conditions, i.e.,
g(x) g S Ep. X 2 O, [V + (V)( S ea(1 + A).
(5)
Here, the accuracy of the last condition is proportional to the Lagrange multiplier A. (ii) & is an infeasible stationary point of the constraint function, i.e.,
g(x) g" 0.99cp,
[[V[(*)] S cd.
(6)
Moreover, 28 considered the stronger unscaled KKT conditions, where (5) is replaced by
g(x) - g" S cp. X X 0, Vf(x) + XVg())I & cd-
(7)
Unlike the scaled KKT conditions, the accuracy requirement in the last condition does not depend on
the multiplier X. We observe that our Definition 3.1 implies the unscaled KKT conditions. Suppose
is an approximate (c², -t)-stttoonary point. Then, if gx) g" 2 0.99cp, the condition in (6 holds;
otherwise, the condition 7 is satisfied.
3.1.2 Connection with the Metries in Bilevel Optimization Literature
In this section, we also relate our proposed stationarity metric for the original simple bilevel prob- lem ( to those used in common reformulations in the bilevel optimization literature. A widely used reformulation is the faluue-functionbaee based approach, defined as follows:
min f(x) S.I. g(x) g" =0 xER"
(8)
However, the KKT conditions of the value-function reformulation are not necessary for optimality, as standard constraint qualifications may be violated-eve when the lower-level objective satisfies additional conditions such as the Polyak-Lojasiewics (PL) condition [3]. Instead, we aim to con- nect our proposed stationarity condition with the KKT conditions of the gradient-based reformulation. Before establishing this connection, we introduce the following definition and assumption.
Definition 3.2 (CEpr KKT conditions
35
gradient-based reformulation of Problem ① is
min
fx), s.t. Vg(x) = O,
(9)
FER
A point & is an (Epsea)- KKTT point of Problem 9 if there exists w E R" such that [|V + g()
Ep:
[Vg(2)11 < ed
(10)
Note that the reformulation is equivalent to Problem when g satisfies the PL condition. To analyze the relationship between Definition
3.1 and 3.2 we introduce the following assumption.
Assumption 3.1 (Local Error Bound ) There exists >> O such that for small enough and for any x satisfying gx(x)] S. we have dist(x, ({0H) S <l g(x)ll
This local error bound condition is implied by local PL inequality, which itself is relaxation of the global PL condition. We are now ready to connect our proposed stationarity metric with the (cp: Ca) <a)-KKT conditions of the gradient- reformulated problem. The Proof is in Appendix A.2
Theorem 3.2. Suppose Assumption 3.7 holds and V²y(x) is -ipLipschitz If a point & E R is an (ef, eg statiionayy point of Problem for some Eg > O, then it is an (Ep, ea)-KKY point of Problem (9) for cp =Oee X eg) and Ed Eg.
Theorem 3.2 implies that although the KKT solutions of Problem 9 typically rely on second-order information of the lower-level objective, they can still be approximated using first-order methods. In partieular, this result holds without requiring any constraint qualification (CQ) conditions commonly
assumed in the bilevel optimization literature 3 33 39].
5

---

4 Algorithmic Framework
To efficiently find stationary point for the nonconvex simple bilevel problem in ① adopt the dynamic barrier gradient descent (DBGD) framework in [3] It was first proposed for the constrained optimization problem in (2) with theoretical guarantees established only in the continuous-time limit. One of our contributions is applying this framework to the nonconvex simple bilevel problem II) and establishing the first discrete-time stationarity guarantees. The core idea of DBGD is to choose a descent direction that aligns with the upper-level gradient while minimizing its impact on the lower-level problem. Specifically, consider the general update rule
X++1 = Xk - nj.k:
(11)
where > O is a step size and dg is a descent direction. For the simple bilevel problem of interest, we seek vector de that balances progress on both objectives. When the lower-level objective is far from optimal, the focus is on minimizing it while ensuring that any reduction in the upper-level objective f does not hinder the decrease of g. As the lower-level objective nears optimality, priority shifts to minimizing, f, which may require controlled increase in to keep iterates x within or close to the solution set Xz- It turns out that both properties can be achieved if dą selected as
d₂ = argmin [ all dER"
s.t.
Vg((+) Td 2 (x)))
(12)
Here, Ø: R2 - + is a non-negative function that controls the inner product between the selected direction and the gradient of the lower-level problem. Specifically, Gong et al. 3 propose the choice <(x) = min (xx(
g²) [[ (xx=)) ] This represents one possible design, and as elaborated in Appendix [ alternative choices for è give rise to other methods studied in the literature. The main property of o is that it should capture some form of infeasibility for the original problem, i.c.,
suboptimality in the lower-level problem.
key point is that dy chosen as the closest vector to the upper-level gradient V f while maintaining a positive angle with the lower-level gradient. The set of feasible directions depends on how far the current point from feasibility. If g(xx) g", i.e., o(xx) = O, any direction with an angle less than 90 degrees is feasible, allowing us to reduce f without increasing (up to first-order). But if ((x+) large, we prioritize reducing g by choosing a direction closely aligned with Vg.
Close form solution of the subproblem. Since (2) is a quadratic convex program with a single inequality constraint, its optimal solution can be explicitly expressed as
d = Vf(x)) + d gg(x))
(13)
where D can be computed as follows:
(((x)) (x(x)) Vg(xx)
A max
(14)
VV((+))11
Hence, our method of interest with stepsize 774 can be easily implemented by following the update
X = Xx 7h (Vf(xx)) + ^ Vg(:))..
(15)
Our choice of the subproblem. To establish convergence guarantees for the nonconvex simple bilevel problem, analyze the version of the discussed algorithm that incorporates o(xx) = B& g in its update. This choice is motivated by the fact that, in nonconvex lower-level problems, the gradient norm is the most computationally tractable measure of suboptimality. In this case, the expression for the parameter X₁ introduced in (14) can be simplified as
| (xxx)) 2 (x(x)) VV
A
max
(16)
In Section 5 we establish the convergence rate of the update that follows the update in [5] when A is computed based on the expression in (16).
5 Convergence Analysis
In this section, we analyze the convergence rate of a variant of the dynamic barrier descent method,
which follows the updates in [15) and (16) to solve the nonconvex simple bilevel problem in (L. As

---

discussed, our goal is to find point x that satisfies the conditions in (3). To achieve this, it suffices show that, for at least one iterate of the method, both the lower-level gradient norm [[ )ll and
the update direction norm ||dı|| || are small. Given that dg V (xxx)) ) + X Vg((s)) and that A in our algorithm is always non-negative, this guarantees the desired convergence Definition (3.T
Our starting point is to use the smoothness property of the objective functions f and g (Assump-
tion 2.1 ii) and (iii) derive descent-type lemma. This leads to an upper bound on ||dı; and in each iteration, which is shown in the following lemma. The proof is in Appendix B.
V [kk
Lemma 5.1. Suppose Assumption 2.1 holds and let {xx} be the iterates generated by (15) and
(66 with constant step size The = and constant hyperparameter 0 S BBx 3 S 1. Define = =xxs) - (xx+1) and Agk- = g(xx) - g(xx+1). We have
nレ 1 ||d&
Afk \x
(1
(17)
2
7
Agk
Lg n/ dx
B V
(18)
Lemma 5.1 shows that ||dı]] can be upper bounded in terms of Af - f(xx) - fx*++1) and VVg(x (xx II. while [|Vg(x can, in turn, be upper bounded in terms of Ag = g(xx) g( (x+++)) and |dell- A natural strategy, therefore, is to combine the two inequalities (17) and (18) and construct potential function of the form ||dx 1|2 + v/VV
where e is an appropriate constant. This
would be easy to achieve if As is uniformly bounded by an absolute constant M. Indeed, in this case, by adding 17p and (18) multiplied by 2M,, and further assuming that r) S 1y+2ML, we obtain
||dd g v Af++2Ma9 Applying the standard telescoping argument then yields a convergence rate of O { for both ||d and [
However, a key challenge is that we do not have an a priori upper bound on λς. which prevents us from setting a constant step size B that depends on such bound. Moreover, such uniform upper bound on A may not even exist at all, as d could diverge to infinity when x approaches a near-stationary point of the lower-level objective y. To see this, recall the expression for A in (T6) and the decomposition of
the upper-level gradient V (xx)) = V (xx) + V/V (x)). where V J (X&) is the component parallel
to Vg(xx) and fxi(x)) is the component orthogonal to Vg(x;). ). When V (xie) is in the opposite
direction of V Vg(x)), we have A 3 f(xx)) Vg(x.) B V fi (M.))
(x,))
B [V
[V
(9(x))ll=
Thus, as || | g (xx ]l approaches zero, A diverges whenever S (xx)
) is nonzero that is, when the
upper-level gradient retains nonzero energy in the opposite direction of Vg(x)).
The following lemma presents our first attempt to use the boundedness of the upper-level gradient (Assumption (i) to control the magnitude of λς. The proof is in Appendix B.2
Lemma 5.2. Recall the expression of Xu in 16 If A'Assumption 2.1 holds, then A S 3 + [V III
Gr
Remark 5.1. This result shows X proportional to [[a[x rather than being uniformly bounded by a constant. As a result, for the X generated by DBGD, we have ep Olee + +gg) in Theorem 3.2
However, this bound still suffers from the same issue: it is vacuous as Vg(xt)] approaches zero.
To address this challenge, we construct new potential function that circumvents the need to explicitly upper-bound A by a constant. The key observation is that Å appears in (17) only as a coefficient of the term || V xx )x Hence, while Å is potentially unbounded, the total contribution of the term A ) I[ in (17 can be controlled by 3 (xx)))) + g (x+)ll which converges to zero I diminishes. This suggests that may still obtain meaningful bound on ||d;]]
as long V (xx
by appropriately combining (17) and (18). This is stated in the next lemma.
Lemma 5.3. Consider the updates in
15 If Asssmmttions
2. hold, " S L and B 5 then
| 2(Afx 3Dgk) + 22/BG///
Agk Lg 2 nunlddl12.
(19)
"
Note that this an implicit inequality for |d as ||d the square root. To obtain an explicit bound, we first present the following intermediate lemma.
|| is also present in the right-hand side under
7

---

Lemma 5.4. Suppose x 2 0 and x S A BVI, where A E R and B 2 0. Then z S 2A + B².
To apply Lemma 5.4 and obtain an explicit upper bound on ||d&|l we first manipulate (19 match
the form of the incquality in Lemma 5.4 Specifically, adding Lg to both sides (99 and defining
2
S - d 1| +
2 we obtain the following inequality
Lg
2(Afk (Agk)
2
Sk -
+
Sk.
(20)
Lg
Applying Lemma
5.4 to 20
yields S I 4(A/ttBAm))
+
4Agg Lgge
+23G3
Since S₁ ||d/|l
2A0g it follows
Lo
4(A + +BAg)) +
20gh + 2BG Ln7²
d
(21)
17
which provides upper bound on ||dx|l2. As shall see later, this inequality together with (18) will be the key to constructing our new potential function. We can now proceed to our main theorem, which characterizes the convergence rate of the algorithm. The proof is in Appendix B.5
Theorem 5.5. Suppose Assumption 2.7 holds and let {xx} } be generated by 15) and (6) with
constant step size Ti = 1 LKV/StT where I. == L.f + L.g and hyperparameter 3x
(In))= = Koo.sাт where p 2 0. Further, define A =- (xx0 - -inl J. and Dg == g(x)) - g- Then,
there exists an index kt E { ,K} such that
4LD,
4LA, g
3LD, + 2G
VV
(22)
K3/(4T)
K
K2/(3+p))
SLA,
8LAg g
6L2 + 4G2
[x((x=) AR- Vg(xx-)) >|2
(23)
((++2)((+p)
((2+2
K
As corollary, the algorithm based on the updates in (15) and (16 finds an (ofy(g))statooaayy point
fg ) iterations, where p 2 0. If we want to balance the rates of the upper and lower levels, we can choose p 1, i.e B = O()). in which case the algorithm finds an (c)+C)) stationary point after O (max((7 -2 ..g ;)z")) iterations. To our knowledge, this is the first discrete-time non-asymptotic guarantee to the stationary points for nonconvex simple bilevel optimization.
after (max(e,
Remark 5.2. Gong et al. (3 analyzed the continuous-time limit of the algorithm in (15) and (16). However, their continuous-time analysis does not account for the additional error introduced by approximating functions f and g by their first-order Taylor expansions. As a result, their convergence result does not directly translate into a concrete convergence bound for the discrete-ting Some of our key contributions include addressing the additional discretization error requiring the solution of an implicit inequality (cf. Lemma 5.3) and careful selection of the step size 17 and hyperparameter aa well as removing the common assumption of uniformly bounded V|lll Remark 5.3. Note that the sequence {Ax )x20 may go to infinity asymptotically, which can be potential issue for Definition 3.1 Specifically, as K - 00, the algorithm may converge to a point x where (x(xx)) 0, in which case there may not be finite À such that 2 and X satisfy the second condition in Definition [.I] However, in this limiting case, the above issue can be addressed by considering the alternative stationarity condition in Definition
algorithm.
3.2 In particular, the second condition in Definition 3.1 is replaced by |/ [x)) + V (V))))+W))) < 6p for some bounded vector w. Note that algorithm ensures that A (1/ )l). the product g remains bounded and has a finite limit point. By applying Theorem 3.2, we can show that the limit point of our algorithm satisfies Definition 3.2 with ep O(E, f + eg) under Assumption 3.1 Finally, we note that reaching a point with exactly vanishing gradient is rare in practice, and since Aς- = (11/I the
sequence d remains finite in all practical cases.
6 Numerical Experiments
While the primary focus of this work theoretical, we include a set of numerical experiments to illustrate the behavior of the proposed algorithm and to support theoretical findings. Since
8

---

1v11
Prudly A-
Pensite =
Pendlt Peasity
12"
Faadyy A
10
Paudly A
Peasly
Pesditr 2 (100)
10
200
400
ECO
000
1000
10
200
400
GD0 Tierationne
305
1000
200
430
C20
EC0
1030
lberations
(a) Vglla
(b) - fll
(c) cos
Figure 1: The performance of DBGD compared with Penalty methods with different choices of À on terms of || Vill", IIV fIl?, and cosO.
Problem 24
prior studies 3 have already demonstrated the strong empirical performance of DBGD in large- scale neural network training tasks, we do not repeat such experiments here. Instead, we evaluate DBGD deterministic optimization problems, which align more closely with the scope of this paper. For comparison, we consider a penalty-based method with updates of the form x = X 7/s (V/ fxx) + \Vg(xx)). where 0 is fixed. We justify the use of this penalty method as baseline in Appendix D and provide full experimental details in Appendix D
Toy Example. We study the following nonconvex simple bilevel problem,
π )2 + (I2 + 1)² s.t. x E argmin(22 sin(10z1))²
min (I1 +
(24)
20
ZER2
Based on Definition 3.1 use Vgg|, IV [lll and cos w-eeee 0 is the angle between Vg and
V/-to measure stationarity. Specifically, [ corresponds to the first condition in Definition 3.1
while |/V /'ll and cos 0 reflect the second condition. As shown in Figure 1 DBGD outperforms the penalty methods across all the metrics, regardless of the choice of penalty parameter X. In Figure (a). although increasing the penalty parameter in the penalty method accelerates early-stage convergence. the lower-level stationarity metric V/ll ultimately plateaus. In Figure[[ effectively reduce the norm of the orthogonal component of f.. In Figure [ (c). the penalty methods produce iterates where the angle between f and V remains less than 90" indicating that the gradients are not fully conflicting and that further improvement possible. In contrast, DBGD consistently improves both || / and V Vifll 2 in Figure | (a) and (b). Moreover, the angle between Vg and V approaches 180 Figure (c), indicating that further local improvement is not possible. Taken together, these observations show that the iterate generated by DBGD satisfies Definition 3.1
only small values of
Matrix Factorization. We formulate matrix factorization
simple bilevel problem that seeks to approximate a symmetric matrix via M z UUT, where U is low-rank tall matrix, while simultaneously optimizing secondary criterion.
42
min U
S(U)
s.t. U argmin g( (V) || VV
(25)
VeRexr
In our experiments, lower-level objective is the reconstruction loss, while the upper-level objective f(U) is designed to promote sparsity. Since the fi-norm is non-smooth, one can adopt a smooth
approximation such fi(U) = Eis v U + Alternatively, a log-smooth sparsity penalty can be used 43 (u) E., log(1 U2/a). Both f1 and smooth and encourage sparsity in U.
Figure 2 presents the results of applying DBGD and the penalty method with various choices of 3 or À solve Problem (25). Similar to the previous experiment, we use V|l and || [Vlll convergence metrics, corresponding to the two conditions in Definition 3.1 Additionally. we report the objective values of both the upper- and lower-level problems, which represent the sparsity and reconstruction loss, respectively. As shown in Figures 2 (a) and (c), the solutions obtained by DBGD consistently outperform those produced by the penalty method with respect to both stationarity metrics, g| and | fI]. This superiority holds across wide range of hyperparameter values, regardless of the choice of 33 for DBGD or À for the penalty method, highlighting the effectiveness of DBGD in achieving stationarity. In addition to the stationarity metrics, DBGD also consistently achieves low

---

200
0000
196t
+07)
+00
(a) fI
(b) f1
(c) f2
(d) f2
Figure 2: The performance of DBGD compared with Penalty methods on Problem 25 terms of |Vgl?. 2 ||
2 g. and f. Blue dots indicate the performance DBGD with different choices of B, while red dots show the performance of the penalty method with varying penalty parameters A.
reconstruction loss U)) and sparsity penalty S(U) across wide range of 3 values. In contrast, the performance of the penalty-based methods is highly sensitive to the choice the penalty parameter X, often resulting in suboptimal trade-offs between reconstruction and sparsity. These differences clearly illustrated in Figures 2 (b) and (d), further demonstrating the effectiveness of DBGD.
Conclusion
In this paper, focused nonconvex simple bilevel problems and introduced the definition of (cy, <.y-,tattionnay points as a stationarity metric for this problem class, examining its relationship with existing metrics in the literature. We then established novel non-asymptotic analysis for a variant of the dynamic barrier gradient descent algorithm framework from S demonstrating a
Stp convergence rate of ((mxx(e, Eg for nonconvex simple bilevel problems.
)), where 2 0, for achieving (e, eg)stttttaoonna points
Acknowledgements
The research of J. Cao, R. Jiang and A. Mokhtari is supported in part by NSF Grants 2127697, 2019844, and 2112471, ARO Grant W911NF21 10226, the Machine Learning Lab (MLL) at UT Austin, and the Wireless Networking and Communications Group (WNCG) Industrial Affiliates Program. The research of E. Yazdandoost Hamedani is supported by NSF Grant 2127696.
References
[1] Yura Malitsky. Chambolle-pode and tseng's methods: relationship and extension to the bilevel optimization. arXiv preprini urXiv:/706.0000 02602, page 3, 2017.
[2] Ruichen Jiang, Nazanin Abolfazli, Aryan Mokhtari, and Erfan Yazdandoost Hamedani. A conditional gradient-based method for simple bilevel optimization with convex lower-level problem. In International Conference on Artificial Intelligence and Statistics, pages 10305- 10323, PMLR, 2023.
[3] Chengyue Gong, Xingchao Liu, and Qiang Liu. Bi-objective trade-off with dynamic barrier gradient descent. In Proceedings of the 35th International Conference on Neural Information Processing Systems, pages 29630-29642, 2021.
[4] Jincheng Cao, Ruichen Jiang, Nazanin Abolfazli, Erfan Yazdandoost Hamedani, and Aryan Mokhtari. Projection-free methods for stochastic simple bilevel optimization with convex lower-level problem. Advances in Neural Information Processing Systems, 36, 2023.
[5] Yu-Guan Hsieh, James Thornton, Eugene Ndiaye, Michal Klein, Marco Cuturi, and Pierre Ablin. Careful with that scalpel: Improving gradient surgery with ema. arXiv preprint arXiv:2402.02990 2024.
[6] Nicolás Garefa Trillos, Sixu Li, Konstantin Riedl, and Yuhua Zhu. CB²O: Consensus-based bi-level optimization. arXiv preprint arXiv:2411.1339. 2024.
10

---

[7] Mikhail Solodov. An explicit descent method for bilevel convex optimization. Journal of Convex Analysis, 14(2):227, 2007.
[8] Stephen Dempe, Nguyen Dinh, and Joydeep Dutta. Optimality conditions for a simple con- vex bilevel programming problem. Variational Analysis and Generalized Differentiation in Optimization and Control: In Honor of Boris S. Mordukhovich, pages 149-161, 2010.
[9] Harshal D Kaushik and Farzad Yousefian. A method with convergence rates for optimization problems with variational inequality constraints. SIAM Journal on Optimization, 31(3):2171- 2198, 2021.
[10] Sepideh Samadi, Daniel Burbano, and Farzad Yousefian. Achieving optimal complexity guarantees for a class bilevel convex optimization problems. In 2024 American Control Conference (ACC), pages 2206-2211. IEEE, 2024.
[11] A.N. Tikhonov and V.Y. Arsenin. Solutions of Ill-Posed Problems. Wiley, 1977.
[12] Jincheng Cao, Ruichen Jiang, Erfan Yazdandoost Hamedani, and Aryan Mokhtari. An accel- erated gradient method for convex smooth simple bilevel optimization. Advances in Neural Information Processing Systems, 37:45126-4515 2024.
[13] Aleksander Madry. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083 2017.
[14] Eric Wong, Leslie Rice, and J Zico Kolter. Fast is better than free: Revisiting adversarial training. arXiv preprint arXiv:2001 003944, 2020.
[15] Yihua Zhang, Guanhua Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, and Sijia Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. In International Conference on Machine Learning, pages 26693-267 12. PMLR, 2022.
[16] Huaqing Zhang, Lesi Chen, Jing Xu, and Jingzhao Zhang. Functionally constrained algorithm solves convex simple bilevel problems. arXiv preprint arXiv:2409.065330 2024.
[17] Khanh-Hung Giang- Giang-Tran, Nam Ho-Nguyen, and Dabeen Lee. A projection-free free method for solving convex bilevel optimization problems. Mathematical Programming, pages 1-34, 2024.
[18] Pengyu Chen, Xu Shi, Rujun Jiang, and Jiulin Wang. Penalty-based methods for simple bilevel optimization under h\ ((o} Iderian error bounds. arXiv preprint arXiv:2402.02155. 2024.
[19] Shoham Sabach and Shimrit Shtern. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640-660, 2017.
[20] Roey Merchav and Shoham Sabach. Convex bi-level optimization problems with non-smooth outer objective function. arXiv preprint arXiv:2307.08245 2023.
[21] Lingqing Shen, Nam Ho-Nguyen, and Fatma Kılmę-Karzan. An online convex optimization- based framework for convex bilevel optimization. Mathematical Programming. 198(2):1519- 1582, 2023.
[22] Jiulin Wang, Xu Shi, and Rujun Jiang. Near-optimal convex simple bilevel optimization with bisection method. arXiv preprint arXiv:2402.05445. 2024.
[23] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint, On the complexity of finding first- order critical points in constrained nonlinear optimization. Mathematical Programming, 144(1): 93-106, 2014.
[24] Coralia Cartis, Nicholas IM Gould, and Ph I. Toint. Corrigendum: On the complexity of finding first-order critical points in constrained nonlinear optimization. Mathematical Programming. 161:611-626, 2017.
[25] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled kkt conditions and high-order models. Approximation and Optimization: Algorithms. Complexity and Applications, pages 5-26, 2019.

---

[26] Coralia Cartis, Nicholas IM Gould, and Ph L Toint. Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization. Journal of Complexity, 53:68-94 2019.
[27] Francisco Facchinei, Vyacheslav Kungurtsev, Lorenzo Lampariello, and Gesualdo Scutari. Ghost penalties in nonconvex constrained optimization: Diminishing stepsizes and iteration complexity. Mathematics of Operations Research, 46(2):595-621) 2021.
[28] Ernesto G Birgin, JL Gardenghi, José Mario Martínez, Sandra A Santos, and Ph L Toint. Evaluation complexity for nonlinear constrained optimization using unscaled kkt conditions and high-order models. SIAM Journal on Optimization, 26(2):951-967, 2016.
[29] Digvijay Boob, Qi Deng, and Guanghui Lan. Stochastic first-order methods for convex and nonconvex functional constrained optimization. Mathematical Programming, 197(1):215-279, 2023.
[30] Qihang Lin, Runchao Ma, and Yangyang Xu. Inexact proximal point penalty methods for constrained non-convex optimization. arXiv preprint arXiv: 1118, 2019.
[31] Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. arXiv preprint arXiv:2309.01753, 2023.
[32] Lesi Chen, Jing Xu, and Jingzhao Zhang. On finding small srperegradients in bilevel optimiza- tion: Hardness results and improved analysis. In The Thirty Seventh Annual Conference Learning Theory, pages 947-980. PMLR, 2024.
[33] Bo Liu, Mao Ye, Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: A simple first-order approach. Advances neural information processing systems, 35:17248-1788
2022.
[34] Han Shen and Tianyi Chen. On penalty-based bilevel gradient descent method. In International Conference on Machine Learning, pages 30992-31015. PMLR, 2023.
[35] Quan Xiao, Songtao Lu, and Tianyi Chen. A generalized alternating method for bilevel learning under the polyak- ({L} ojasiewicz condition. arXiv preprint arXiv:2.306.0244 2023.
[36] Feihu Huang. Optimal bessian/jacobian-free nonconvex-pl bilevel optimization. arXiv preprint 2.Xi:22407.18223 2024.
[37] Hadi Reisizadeh, Jinghan Jia, Zhiqi Bu, Bhanukiran Vinzamuri, Anil Ramakrishna, Kai- Wei Chang, Volkan Cevher, Sijia Liu, and Mingyi Hong. Blur: A bi-level optimization approach for Ilm unlearning. arXiv preprint 2506::2500.01666 2025.
[38] Zhi-Quan Luo and Paul Tseng. Error bounds and convergence analysis of feasible descent methods: a general approach. Annals of Operations Research, 46(1):157-178, 1993.
[39] Stephan Dempe and Joydeep Dutta. Is bilevel programming special case of mathematical program with complementarity constraints? Mathematical programming. 131:37-48, 2012.
[40] Nathan Srebro and Tommi Jaakkola. Weighted low-rank approximations. In Proceedings of the 20th international conference on machine learning (ICML-03), pages 720-727, 2003.
[41] Chris Ding, Xiaofeng He, and Horst D Simon. On the equivalence of nonnegative matrix factorization and spectral clustering. In Proceedings of the 2005 SIAM international conference on data mining, pages 606-610, SIAM, 2005.
[42] Sanjeev Arora, Rong Ge, Ravindran Kannan, and Ankur Moitra. Computing nonnegative matrix factorization-provabll, In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 145-162, 2012.
[43] Emmanuel Candes, Michael B Wakin, and Stephen Boyd. Enhancing sparsity by reweighted l minimization. Journal of Fourier analysis and applications, 14:877-905, 2008.
12

---

[44] Mingyi Hong. Hoi-To Wai, Zhaoran Wang. and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application actor-critic. arXiv preprint arXiv:2007.05177, 2020.
[45] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International conference on machine learning, pages 4882-4892. PMLR, 2021.
[46] Lesi Chen, Yaohua Ma, and Jingzhao Zhang. Near-optimal fully first-order algorithms for finding stationary points in bilevel optimization. arXiv preprint arXiv:2306. 14853, 2023.
[47] Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning, pages 18083-18115 PMLR, 2023.
[48] Stephan Dempe. Foundations of bilevel programming. Springer Science & Business Media, 2002.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly stated our contributions in the introduction aligned with the main claims the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [NA]
Justification: This is theoretical paper with standard assumptions.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Our paper provides the full set of assumptions in Section 2 and complete proof in Section and Section
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
The experimental results are stated in Section 6 The implementation details are included in Section The code and data are attached in the supplementary material.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code and data are attached in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ mripss.cc/ubliic/gui.eee CoodeSumeeieeeeee ssi iessonPolll mollicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We explained how we performed the experiments in Section 6 Moreover, the implementation details included in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: The algorithm is designed for deterministic simple bilevel optimization, which does not include any randomness.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes)
Justification:
The compute resources we used are stated in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics Ethics/https://
Answer: [Yes]
Justification:
The paper conforms, in every respect, with the NeurlPS Code of Ethics
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no socictal impact of the work performed in this paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
20

---

Appendix / supplemmentl material
A Omitted Proofs in Section 3
A.1 Proof of Lemma 3.1
First, we show that if the point & is an -y)stttaatta point as defined in Definition 3.1 then the
two conditions in Lemma 3.1 are satisfied. For any 5 > 0, let f = min / T.g 26 26/0/ (ALg
Ly)}. For any x satisfying X it holds that
x
S rrs Using the fact that g is Lm-smooth and [[g
[x)] ||? S Eg.
Lg 8 x|| 2
(xx) 2 (() + (Vg(X), x x}
2g(x) - / x x|| 5 5 xx - x|| = g - +) - *||:
where used ||x X|| S 28 /Eg/Lo in the second incquality. Thus, the first condition in
Lemma 3.1 is satisfied. Moreover, Consider any x that satisfies ||x x|| < and g(x) I g()). Since f is L smmoohh, holds that fxx) 2 f(x) + (Vf()), x) 2 | x|I2. By using [[V + (X)( VEr. we further have
1,f ||x x12
f(x) 2 f(x) + + \V)()) x x) X(Vg(x), x x)
2 f(x) V x x - \(Vg((), x) 4/ | xx1
2
Using the smoothness of g. we also have (x) 2 g(x + (Vg(x), x- - x) 4 ||x - x11 Hence, we
get (Vg(2), x) - 1 x| Thus, this leads
L 1
L1 || x113
f(x) 2 (x) vEr x x
2
Since || x|| S r S 28 (ALg + Lf), ), obtain f(x) > f(x) (1 + o) x|x *||. This
shows that the second condition Lemma ls also satisfied.
For the other direction, assume that & satisfies both conditions in Lemma
3.1 Consider any direction
E R". Then Condition (i) implies that, for all small enough, we have g [td) 2 g (1
E)]l which can be rewritten as 9(x) g(x (x)))g(x-d)) td) < (1 + +0)e]|ddl. By taking the limit t + 0. we
obtain (Vg d) S (1 + 8),, |[]. By taking d Vg(X), this implies that [[Vg(x)] S (1+ 0)eg
Since this holds for any 6 > O, taking the limit ō + 0 yields [V)( S Eg. Moreover, let
R" be any direction that satisfies (Vg()), d) > O. Then for all small enough, it holds that
g(X - td) S 9xx). Thus, using Condition (ii), we have
f(X) 1(X - (d)) S 61+
f(x ( :d) 2 f(x) - (1 + 8)eyt[ld]|
t
Similarly, by taking the limits t - 0 and + O, we obtain (x) S cy||d|| Since this holds
for any d that satisfies (Vg(x), d) 0, continuity ensures that it also holds for any d such that
(Vg(&), d) 2 O. If (v)(x), (x)) 2 0, then by setting d = (x),, we obtain that // (x(() S e
Otherwise, if (x), Vg(x)) < 0, let À (V)(), [x
and set d = ff()) gV)()).
Note that this choice of X ensures that (Vg(8), d) = 0, and hence (VS(8), d) = ||d|| < e which implies that ||d]] s ey. This completes the proof.
A.2 Proof of Theorem 3.2
Suppose & is an (g sttttiooary point of Problem 1 the second inequality in Definition 3.2 satisfied with ed = <g. Now, we start to prove the first inequality Definition 3.2 by setting X(x x"), where x* denotes the stationary point closest to x.
21

---

[V + ( < [V VVxx)
- V>9(*)
- [VV + + XV
- V29(x)) \\
-x)xl||| + AL# -===>>xxx111 xx11
Vg(xx) V -x * - x12
+ |
< + 2
Oles + \l (g)))
where the second and fourth inequalities follow from the Lipschitz continuity of (x)( the third follows from the second condition in Definition 1.1 and the last follows from Assumption 3.1 Hence, the first condition in Definition 3.2
holds with cp Oce + (x)
B
Omitted Proofs in Section 5
B.1 Proof of Lemma
5.1
From Assumption 2.1 has LypLschhit continuous gradient, hence,
d+ + I " ///12 f(xx+1) f(xx) S fxxx) Td,
-V((V((x)) -dx) -d)) dd n1(1 L1 nd 2
Vg(xx) T d2 -n(1 L5 m)llde11
where in the last equality we used fx(xx) = d - A Vg(xs). Since dg is the optimal solution of subproblem [12 with the corresponding optimal dual multiplier Ak. the complementarity slackness implies that (vg((())) de /|[ = 0. Hence, we further obtain
ي _ nelll + Vo(x))
f(x*+1) - f(x)) - 71
By dividing both sides by 7 and rearranging the inequality, we obtain Moreover, from Assumption
has an Lg -iipchitt continuous gradient, which implies that
Lg
Le 1lde Vg(xa L
Lg
g(xx+1) - gx Vg V (xx) dg +
2
where we used Vg(x;) T d 8 ( ]| from (22 in the last inequality. Dividing both sides by and rearranging the inequality yields (8)
B.2 Proof of Lemma 5.2
By Assumption 2.1
the gradient f is bounded by G,- Thus, we have
A s 3 (Vf(xx). Vg(xx))]
G5 ||Vg(x+)]|
I 3 +
This completes the proof.
B.3 Proof of Lemma
By combining Lemma 5.2 with 17 we have (1 nL, | < Ate + V +
2
BG, V Substituting the upper bound [/ in 188 and combining terms, arrive
(1 n + || d < Ale+ADe /3G Age. + / Since 7 N S L,+b ! || 1 By multiplying both sides by 2 the the left side of this inequality can lower bounded by 2 claim follows.
2
22

---

B.4 Proof of Lemma 5.4
Since æ 1 A+BVe, we have (Vz- - A+ B"
which further implies vi- B S A + _ By
adding to both sides, taking the square, and using Young's inequality we obtain # S (v + m
2
B ) A+ B A+ B
< A+ R B2
+
(A+
m2
+ B This completes the proof.
2
B.5 Proof of Theorem
Multiplying
18
by Lg
and adding it to 21 implies
|
fz + 3Agh)
3 + 2337
2
Lng
"
Lgn
Define the potential function 9k - 1 d + A (gg(x))))))) Averaging the above inequality
L,
over k K and noting that =k=0 Aʃk fxx) - f(xx) S f(xo) inf f = and
Ek= k=
K- Agk = g(xo) - g(xx) (xx) - g" Ag. we obtain
1
K
Σ
9
S
, + 3Dg)
3A,
+23G9
K
n
L
k=0
Since 17 LK1/BT and
Koo by letting Ks argmingstsk- K 9k, get
4LA,
4LAg
3 9
2G
GL- S K(249//34p)
((2+2n) K(()///33+ (3+))) K(I+p)/34p))
Finally, since GE. = 2/1dd= 1|2 T.
( )l? follows that || S 29k and Vg(xx=) )l <
L GL. = LKU the proof is complete.
L.9.-
By the definition d = fx(xx) + d (g(x)) and the fact that d 2 0.
C Other Choices of oxx) and their connection to methods considered in the literature.
In this section, we briefly discuss the connection between other methods studied in the literature and the general algorithmic framework described in (12
Lower-level lincarization based methods. we set ((x) = a(g(x) g") in the update (22). eetariizttionbbseee approach introduced in [2]. This method was originally developed to solve simple bilevel optimization problems with conve lower-level objective. The key idea of this type of method is construct halfspace to approximate the lower-level solution set 2 Specifically, the approximated set is constructed using a linear approximation of the lower-level objective follows.
where 1/n. the resulting method closely aligns with the lower-leve
X {x R" 9(xx) Vg(xx) T(xx xx) "
g is convex, then the constructed set 23 contains X for all k. The update of the projection variant of the algorithm in (2) is as follows,
Xx+1 = 11x, 17 f(xo))
which would be equivalent to
X argmin
||x (V(x))) s.t. g(xx) (x(x)) (x- xx) S g
x
Through change of variables and defining = (xx x)/n. we can equivalently reformulate the above subproblem
d₃ = argmin ||d v fx(x)11 s.t. Vg(xa) d 2 (g(Xx) - -g")/m
d
23

---

This is a special instance of (12) with 6(x) = (g(x) /nn. This choice of o(x) is suitable for convex problems, as the solution set X is convex and can be contained within Xg. However, when the lower-level loss is nonconvex, X is also nonconvex, meaning the inclusion X S Xr is not guaranteed. To address this, (xx) must be adapted, and using the gradient norm offers natural extension to the nonconvex case.
Orthogonal projection methods. BiLevel Optimization with Orthogonal Projection (BLOOP) [S] was recently proposed for stochastic simple bilevel optimization. Its key idea is projecting the upper-level gradient to be orthogonal to the lower-level gradient. In the deterministic version, the descent direction dæ for the update X
Xk
7/ chosen
V [((x)) Vg(xe) V
d& = [Vg(xx)
V
[Vg(xx)]
The second part of dg is the projection of the upper-level gradient onto the orthogonal space of the lower-level gradient. If we rearrange the terms in dg. dę is equivalent
d₂ argmin ||d f(xx))1
s.t. Vg(xx) Vg
d
This is special case of 12 with ((x) (x)]3 but with an equality constraint instead of an inequality. Solving the qquality-constrained subproblem with the chosen @(x) ensures convergence
of the lower-level objective but not the upper-level one [5]. In contrast. show that solving the mnequalitycoonstraiee problem also guarantees convergence for the upper level.
D Connections with Algorithms for General Bilevel Problems
In this section, discuss why most algorithms designed for general bilevel problems not directly applicable to our simple bilevel setting and highlight the connections between the two classes of algorithms. In the general form of bilevel problems, the upper-level function f may also depend an additional variable y E Ihm that turn influences the lower-level problem:
min xER" yER",
f(x,y)
arg min g zER"
However, in our considered simple bilevel setting, there is additional upper-level variable. As result, the upper-level updates present in algorithms for general bilevel problems become invalid.
When these updates are removed, some algorithms- -uch as those [4
45
reduce to standard
gradient descent g. i.e., X X 7) V (xx).. Many other methods to the update,
33
34
46
reduce
X++1 X T V fxx)) + A Vg(xx)),
which we refer to as the penalty method for nonconvex simple bilevel problems. We include this method baseline in our experiments in Section 6 The key challenge for the penalty method lies in selecting an appropriate penalty parameter AІ- The choices of Å used in general bilevel problems based on different stationarity metrics.
are not suitable for the simple bilevel setting, Therefore, determining the appropriate value of A for this method requires a tailored analysis specific the simple bilevel setting. Note that DBGD algorithm essentially provides dynamic scheme for selecting A as described in (4).
they
D.1 Connections with Stationarity Metrics for General Bilevel Problems
Besides the algorithms themselves, the stationarity metrics for general bilevel problems also not directly applicable to the simple bilevel setting. For instance, [47 31
32 adopt the norm of the hyper-gradient as measure of stationarity. Recall that the obper-objective
48 is defined follows
min pyy), where s(y) yeRm
min xxx*
f(x
where X" (y) A arg min, g(z, y). However, in the simple bilevel setting without upper-level vari- ables y, the norm of the grper-gradient constant and thus fails serve as a valid metric. Furthermore, most existing approaches rely on strong convexity or the Polyak-toojsiewicz (PL. condition for the lower-level problem-ass assumpiioos that are violated in our case, where the hyper-gradient may not even be well-defined.
24

---

Other works, such as [35,, consider alternative stationarity metrics. When rewritten in the context of our simple bilevel setting, their condition becomes: there exists w R" such that
V gV + (2)())))]l' S Ey,
V S Eg.
Intuitively, the first condition ensures that the component [(() V projected onto the kernel of V²g(8) is small, i.e.
Projken(V (VS(x) + V g w) x O.
This stationary metric generally weaker than the metric defined in Definition 3.2
D.2 Additional Related Works on General Bilevel Problems
To go beyond strongly convex lower-level objectives, additional assumptions on the lower-level problem are necessary ensure meaningful guarantees, particularly in light of the negative results for general bilevel optimization with merely convex lower-level objectives (32). A common strategy assume that the nonconvex lower-level objective satisfies the Polyak-Lojasiewicz (PL) condition. Specifically, a penalty-based gradient method was introduced in (44 for both unconstrained and constrained nonconvex-PL bilevel optimization. Later, [351 proposed GALET, Hessian-ves -eestan-veettor- vector- product- based method with non- non-asymptotic convergence guarantees to the modified KKT points of a gradient- based reformulation. In (3I, nonconvex bilevel optimization under the proximal error- brund (EB) condition was studied, which is analogous to the PL condition. More recently, in method was developed that achieves optimal convergence complexity
36. a Hessian/Jacobian- for nonconvex- PI. bilevel problems. Besides imposing the PI. condition on the lower-level problem, these works also rely on different additional assumptions. For example, (33] additionally assumes that both the upper- and lower-level function values, as well as the norms of their gradients, are bounded, and the lower-level optimal solution is unique. The work in [35] requires both PL and convexity assumptions on the lower-level problem to guarantee convergence. The studies in 3I and [32 impose the condition that a weighted sum of the upper- and lower-level objectives satisfies the PL condition. Finally, in (36] it is assumed that V g(((x) is non-singular at the minimizer of g.
D.3
On the Role of the PL Condition
The PL. condition plays a central role in the analyses of the aforementioned works general bilevel optimization. For example, (32 heavily relies on the fact that the PL condition induces a "strongly convex subspace" around any minimizer of the lower-level objective. This structural property enables the adaptation of proof techniques similar to those in [46). which developed an algorithm for general bilevel problems with a strongly convex lower-level objective. Essentially, general bilevel settings, the PL condition ensures the continuity of the hyper-objective so(y), thereby guaranteeing the existence of the grperrgraddent.. This facilitates rapid convergence to neighborhood of X (y). However, in our considered simple bilevel setting. the oyper-objective and its gradient not well- defined, and we instead rely on alternative stationarity metries. Consequently, the PL condition is less applicable and offers limited benefit compared to its role in general bilevel problems.
E Experiments Details
In this section, we include more details of the numerical experiments in Section 6 All simulations implemented using MATLAB R2022a PC running macOS Sonoma with Apple M1 Pro chip and 16GB Memory.
Toy Example. Recall that for Problem [24 the optimal solution set of the lower-level problem
given by g = {x E R2 x2 = sin 10xz)) }} The optimal solution of the bilevel problem is
x (- 20 -). We apply DBGD using ((x) = [ 12 i... with 3 = 1, and also employ the Penalty methods introduced Section D with À E {1, 10, 100, 10003. Both methods are initialized at the point xa = (-3, -1), using a base stepsize of 1 10-2 and total of K 10 iterations. Since the penalty methods become unstable for large values of X, we further scale the stepsize by a factor of 1/(1 A) in each independent run.
Matrix Factorization. For Problem (25). we set n. = r = 10 to generate U. and construct M U.U. + eln, where 0.000 and I, gaxn denotes the identity matrix. We
25

---

and compare it against the penalty methods described in Section D using À E (1, 20, 50, 100, 200, 500, 1000). Both methods use stepsize of 10-5 and are run for K = 100 iterations. Since the penalty methods become scale
apply DBGD with 8 E 0.,.
unstable for large values of X, we further scale the stepsize by a factor of 1 (1++ +X)) A) in each independent run. The hyperparameter in both f1 and f2 is set to 1.
F
Additional Experiments
E.1
Different Stationary Points
-1.5
100
2000
500
400
500
100
200
320
400
500
(a) Trajectorics
(b) An
(c) cos 0
10./P
1ost
13
100
200
202
420
300
120
200
300
423
530
16
120
220
300
402
530
(d) [xx 2
(e) [xx)))
(1) [[xx)]]
Figure 3: Solving Problem
24 with different Initializations
In this additional experiment, we analyze the exact stationary points to which DBGD converges and examine the effect of different A values these points, as discussed in Section
We consider the problem in Equation 224 from Section and run DBGD with p(x) = ()
on the specified instance. As shown in Figure 3 the algorithm converges to three distinct stationary points, depending on the initialization. This behavior corresponds to the two scenarios discussed in Section 3 further supporting our theoretical insights.
point where both | f (xx²)] and [[Vg(x;) x ]| are small. As shown in Figure 3 d), (e), and (f), all three metrics decrease. As illustrated in Figure c).. the cosine of the angle between fx(x)) and Vg(xx) remains positive and eventually approaches 1. Figure b) shows that A decreases to 0, aligning with the closed-fome expression (16).
Case I: For Initialization 2 (green), DBGD converges
Case I: For Initializations and (blue and red), DBGD converges to stationary points where ([V is small, as shown in Figure 3. Additionally, V fxx) has minimal energy in directions orthogonal to Vg(x)), as seen in Figure d). The remaining energy of V V (xx) is entirely in the opposite direction of Vg(xx), since [ does not converge (Figure B()),, and the angle
between vx(x)) and (x(xx) is close to 180", as shown in Figure 3c). In this case, Ås cannot
be bounded by an absolute constant, as depicted in Figure ((b, which is also consistent with our thcoretical results.
26

---

F.2
Additional Baselines
While there are no existing methods specifically tailored the nonconvex simple bilevel setting, we include two additional baselines- baselines-BigSAM [19] and a-IRG 10-hhich are originally designed for the convex case. We briefly review the update rules of these algorithms below.
BigSAM is given by
Yk+1 X 7g Vg((x);
1 = Xx: 77, V (xxs;
X ax+12k+1 (1 04++1)y++1
where My and "y constant stepsizes, and aq min { 1 1} for some y 0.
a-IRG is given by
Xi++ X;
7e V (xx) + V (xx)),
where
76 and Tee VK+I
71 [1+1)174 for some constants To and 1/o.
Following the same setup as in our original paper, we report the final gradient norms and cos 0 after 1000 iterations. The table below summarizes the performance of the considered algorithms in the first experiment, with parameters chosen via grid search.
Method
Final |V
Final
V ffl
Final cos(
DBGD
8.5657 10
1.0596 10
-1.0000
Penalty
1.8142
4.4409 10-16
1.0000
Penalty À = 10
2.4473 x 10-1
1.9800 x 10
0.2813
Penalty À 100
6.3210 x 10-3
9.4788
0.8692
Penalty À -100
7.2475 x 10-5
1.7477 X 10
0.7334
BigSAM
2.7177 10
2.1026 10
0.4741
a-IRG
9.3776 x 10-7
1.9802 x 10
0.6903
Table 1: Toy Example
For the second experiment, we present the averaged results for each method across these parameter settings the tables below. The total number of iterations is set 10".
Method
Vgll
|Vifll
g(U)
f(U)
DBGD
5.59 x 10
4.72 x 10
2.73 X 10-7
129.32
Penalty
9.79 x 10-1
1.06
1.82 x 10
134.67
BigSAM
4.54 x 10
5.71
3.96 10
134.80
a-IRG
1.89 x 10-2
1.81
1.30 10-4
135.40
Table 2: Matrix Factorization
Method
|V//|
9(U')
[(U)
DBGD
7.12 x 10
3.95 x 10-1
8.15 X 10-7
37.042
Penalty
1.109
2.23
3.57 X 10
48.543
BigSAM
4.55 x 10-3
7.72
3.96 X 10-4
51.254
a-IRG
2.43 10-2
2.75
1.05 10-1
52.709
Table 3: Matrix Factorization f2
As shown in the tables, is not surprising that BiG-SAM and a-IRG underperform compared to DBGD in terms of our proposed stationarity metrics, they are not specifically designed for the nonconvex setting. In particular, their performance is similar to that of the penalty method with large penalty prramtter--veremphaaiinee upper-level. The failure of algorithms designed for convex simple bilevel optimization when applied to nonconvex simple bilevel problems highlights the necessity of studying the nonconvex setting.
the lower-level objective while failing adequately control the
27

---

F.3 Other Applications for Simple Bilevel Optimization
Simple bilevel optimization arises in various applications, such as sparse representation learning [3), faimess regularization (2), and dictionary learning [4]. In what follows, we illustrate several specific formulations.
Sparsity Representation Learning, We learn sparse feature representations on supervised dataset D of (x, v) pairs by applying non-convex Lp regularization:
f(0) Ep[e(y, (x(h)=))))
g(0) Ep The (z)
where E(.,)) is the data loss, (z) + 2 E R is a hidden feature map, Φe is prediction head, and p is power coefficient.
Fairness Classification. Concretely, the lower-level problem a sparse logistic-regression problem for some À > 0:
min ( = log P(:: = -y o.5 3)
s.t.
11 s X,
SER
while the upper-level objective is the squared covariance:
c P) 1 =1|2 22;1 )
?
f(8)
n2
Dictionary Learning. We aim to find the dictionary ñ E TR (q > p) and the coefficient matrix X E Rgxxn' for the new dataset A', and at the same time enforce D to perform well on the old dataset together with the learned coefficient matrix X. This leads to the following bilevel problem:
min min DERIXe
X(D,8)
XERaXH
s.t.
| lo S k= 1, 1'...,,,'
DE arg min g(D),
1d,1laS1
where the objective
n'
8(D,8) A
a
2n'
is the average reconstruction error the new dataset A', and the lower-level objective
g(D) 4
Σ
a D ;
2n i=1
the error on the old dataset A.
28


Reviews:
[{"review_id": "OHpYKfREqD", "reviewer": "Reviewer_oo1n", "summary": "This paper studies the challenging problem of simple bilevel optimization where both the upper- and lower-level objective functions are smooth but potentially nonconvex. Because finding a global optimum in this setting is generally intractable, the work focuses on the more achievable goal of finding a near-stationary point. The authors first introduce a suitable notion of an $(\\epsilon_f, \\epsilon_g)$-stationary point, which intuitively identifies a solution where the upper-level objective cannot be substantially improved locally without causing a larger deterioration in the lower-level objective. This new metric consists of two conditions: the norm square of the lower-level gradient must be smaller than $\\epsilon_g$, and the norm square of the upper-level gradient + $\\lambda$ * the lower-level gradient must be smaller than $\\epsilon_f$.\n\nTo find such a point, the paper analyzes a discrete-time variant of the Dynamic Barrier Gradient Descent (DBGD) algorithm (previously proposed by Gong et al.) The core of the method is a first-order update step where the descent direction is a dynamic combination of the two gradients, controlled by a multiplier $\\lambda_k$ that is gradually increasing over iterations. The paper's main contribution is providing the first complexity result for a discrete-time algorithm that guarantees joint stationarity for both levels in this general nonconvex setting. Specifically, the algorithm is shown to find an $(\\epsilon_f, \\epsilon_g)$-stationary point with a complexity in $O(\\max (\\epsilon_f^{-\\frac{3+p}{1+p}}, \\epsilon_g^{-\\frac{3+p}{2}}) )$.\n\nI have checked most of the proofs in the main paper and the appendix. The main analysis is based on a cute application of the existing results from DBGD by Gong et al. Specifically, the results in Section 4 are the same as the derivation and results in Gong et al. in their Section 2, the analysis of DBGD. The major contribution of this paper starts in Section 5 by applying descent lemmas to both function $f$ and $g$ (Lemma 5.1). The discussion below Lemma 5.1 follows directly by weighting the terms in Lemma 5.1 and this leads to a $\\lambda_k$-dependent bound on the gradient norm. However, since the Lagrangian dual $\\lambda_k$ is increasing over iterations, this leads to additional discussion on Lemma 5.2 - 5.5 to ensure a $\\lambda_k$-independent bound. The bound is achieved by playing with the inequality to remove the $\\lambda_k$ term in Equation 17. This can be achieved by replacing $\\lambda_k$ by its upper bound. The rest of the analysis follows by doing some linear algebra tricks then. I like the analysis in Section 5 and the experimental results in Section 6. The experimental results verify that the proposed algorithm can achieve low gradient norm for both the lower level and the upper level. The baselines for comparison are relatively weak as it only uses fixed penalty parameter. I wonder if there are better baselines that the authors can compare with.", "questions": "Please respond to my questions in the strengths and weaknesses section.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Clear explanation of the convergence analysis. I appreciate the completeness but I do think some of the proofs can be deferred to the appendix.\n- New setting in simple bilevel optimization problems where the lower-level objective is non-convex. To my knowledge, the general bilevel optimization problems with non-strongly-convex objective have been shown to have some impossibility results. It is good to see that the simple bilevel optimization problems can at least achieve some convergence result.\n\nWeaknesses:\n- Weak baselines in the experiments. Fixed penalty method is known to be not working.\n- Unclear lower bound for the convergence rate. It would be great if the authors can establish some lower bound / impossibility results for the non-convex simple bilevel optimization problems.\n- Most of the analyses are a direct application of DBGD by Gong et al. including the algorithm. The major difference between Gong et al.'s paper and this paper is just the problem setting. Gong et al. considers single level optimization with constraints, and this paper considers simple bilevel optimization that can be reformulated as constrained optimization by the value-based method. The technical novelty is weak.", "was_revised": true, "final_justification": "The explanation of the difference in theoretical analysis compared to prior work makes sense to me. Therefore, I modified the assessment of significance, originality, and the final score.", "rebuttal": "**W1. Weak baselines in the experiments. Fixed penalty method is known to be not working.**\n\n**R1.**  \nThank you for your comment. We would like to note that nonconvex simple bilevel optimization remains largely underexplored, and to the best of our knowledge, no existing discrete-time algorithm is specifically designed for this setting with theoretical guarantees for both levels.\n\nThe effectiveness of the fixed penalty method in the nonconvex simple bilevel setting is still unclear. However, since it has established theoretical guarantees in the convex simple bilevel setting [1, 2], we include it as a baseline in our experiments. Notably, the original DBGD paper [3] also adopts the fixed penalty method as its only baseline.\n\nWhile there are no existing methods specifically tailored to the nonconvex simple bilevel setting, we include two additional baselines—BigSAM [3] and a-IRG [4]—which were originally developed for the convex case. Below we briefly describe the update rules of these algorithms.\n\n**BigSAM** is given by:\n\n$$\ny_{k+1} = x_k - \\eta_g \\nabla g(x_k),\n$$\n\n$$\nz_{k+1} = x_k - \\eta_f \\nabla f(x_k)\n$$\n\n$$\nx_{k+1} = \\alpha_{k+1} z_{k+1} + (1 - \\alpha_{k+1}) y_{k+1},\n$$\n\nwhere $\\eta_f$ and $\\eta_g$ are constant stepsizes, and $\\alpha_k = \\min(\\frac{\\gamma}{k}, 1)$ for some $\\gamma > 0$.\n\n**a-IRG** is given by:\n\n$$\n\\mathbf{x}_{k+1} =  \\mathbf{x}_k - \\gamma_k (\\nabla g(\\mathbf{x}_k) + \\eta_k \\nabla f(\\mathbf{x}_k)),\n$$\n\nwhere $\\gamma_k = \\frac{\\gamma_0}{\\sqrt{k + 1}}$ and $\\eta_k = \\frac{\\eta_0}{(k + 1)^{1/4}}$ for some constants $\\gamma_0$ and $\\eta_0$.\n\nFollowing the same setup as in our original paper, we report the final gradient norms and $\\cos \\theta$ after 1000 iterations. The table below summarizes the performance of the considered algorithms in the first experiment, with parameters chosen via grid search.\n\n| **Method**            | **Final $\\|\\nabla g\\|^2$**       | **Final $\\|\\nabla_{\\perp} f\\|^2$**     | **Final $\\cos(\\theta)$** |\n|-----------------------|----------------------------------|----------------------------------------|---------------------------|\n| DBGD                  | $8.5657 \\\\times 10^{-17}$         | $1.0596 \\times 10^{-16}$               | $-1.0000$                 |\n| Penalty $\\lambda=1$   | $1.8142$                          | $4.4409 \\times 10^{-16}$               | $1.0000$                  |\n| Penalty $\\lambda=10$  | $2.4473 \\times 10^{-1}$           | $1.9800 \\times 10^{1}$                 | $0.2813$                  |\n| Penalty $\\lambda=100$ | $6.3210 \\times 10^{-3}$           | $9.4788$                               | $0.8692$                  |\n| Penalty $\\lambda=1000$| $7.2475 \\times 10^{-5}$           | $1.7477 \\times 10^{1}$                 | $0.7334$                  |\n| BigSAM                | $2.7177 \\times 10^{-4}$           | $2.1026 \\times 10^{1}$                 | $0.4741$                  |\n| a-IRG                 | $9.3776 \\times 10^{-7}$           | $1.9802 \\times 10^{1}$                 | $0.6903$                  |\n\n*Table: Toy Example*\n\nFor the second experiment, we present results using plots generated with various parameter settings in our original paper. Since images cannot be included in the rebuttal, we instead report the averaged results over these parameter settings for each method in the tables below. The total number of iterations is set to $10^6$.\n\n| **Method** | $\\|\\nabla g\\|$         | $\\|\\nabla_{\\perp} f\\|$ | $g(U)$              | $f(U)$     |\n|------------|------------------------|-------------------------|---------------------|------------|\n| DBGD       | $5.59 \\times 10^{-3}$  | $4.72 \\times 10^{-1}$   | $2.73 \\times 10^{-7}$| $129.32$   |\n| Penalty    | $9.79 \\times 10^{-1}$  | $1.06$                  | $1.82 \\times 10^{-2}$| $134.67$   |\n| BigSAM     | $4.54 \\times 10^{-3}$  | $5.71$                  | $3.96 \\times 10^{-4}$| $134.80$   |\n| a-IRG      | $1.89 \\times 10^{-2}$  | $1.81$                  | $1.30 \\times 10^{-4}$| $135.40$   |\n\n*Table: Matrix Factorization $f_1$*\n\n| **Method** | $\\|\\nabla g\\|$         | $\\|\\nabla_{\\perp} f\\|$ | $g(U)$              | $f(U)$     |\n|------------|------------------------|-------------------------|---------------------|------------|\n| DBGD       | $7.12 \\times 10^{-3}$  | $3.95 \\times 10^{-1}$   | $8.15 \\times 10^{-7}$| $37.042$   |\n| Penalty    | $1.109$                | $2.23$                  | $3.57 \\times 10^{-2}$| $48.543$   |\n| BigSAM     | $4.55 \\times 10^{-3}$  | $7.72$                  | $3.96 \\times 10^{-4}$| $51.254$   |\n| a-IRG      | $2.43 \\times 10^{-2}$  | $2.75$                  | $1.05 \\times 10^{-4}$| $52.709$   |\n\n*Table: Matrix Factorization $f_2$*\n\nAs shown in the table, it is not surprising that BigSAM and a-IRG underperform compared to DBGD in terms of our proposed stationarity metrics, as they are not specifically designed for the nonconvex setting. In particular, their performance is similar to that of the penalty method with a large penalty parameter—overemphasizing the lower-level objective while failing to adequately control the upper-level. The failure of algorithms designed for convex simple bilevel optimization when applied to nonconvex simple bilevel problems highlights the necessity of studying the nonconvex setting.\n\n---\n\n**W2. Unclear lower bound for the convergence rate. It would be great if the authors can establish some lower bound / impossibility results for the non-convex simple bilevel optimization problems.**\n\n**R2.** We appreciate this insightful comment. However, we note that nonconvex simple bilevel optimization is still in its early stages of study. Our work provides the first upper-bound complexity result for a discrete-time algorithm that guarantees joint stationarity for both levels in nonconvex simple bilevel problems.\n\nEstablishing lower bounds or impossibility results is indeed an important and interesting direction. While focusing solely on the lower-level or upper-level problem can achieve a rate of $\\mathcal{O}(\\epsilon^{-2})$, in the simple bilevel setting, we must consider both objectives jointly. This introduces a trade-off between the convergence rates of the lower- and upper-level objectives, making the construction of lower bounds fundamentally different from the previous lower bound results and substantially more challenging. \n\n---\n\n**W3. \nMost of the analyses are a direct application of DBGD by Gong et al. including the algorithm. The major difference between Gong et al.'s paper and this paper is just the problem setting. Gong et al. considers single level optimization with constraints, and this paper considers simple bilevel optimization that can be reformulated as constrained optimization by the value-based method. The technical novelty is weak.**\n\n**R3.** \nWhile there are some similarities between the algorithm analyzed in our paper and the DBGD method proposed in [3], we would like to emphasize that our analytical framework and convergence results differ substantially from those in [3]. Below, we explicitly highlight the key differences:\n\n**(1)** In our work, we first introduce a notion of stationarity for nonconvex simple bilevel optimization by decomposing the upper-level gradient into two orthogonal components: one parallel to the lower-level gradient and the other orthogonal to it. This definition admits both an intuitive and rigorous interpretation, analogous to the concept of stationarity in single-level optimization, as demonstrated in Lemma 3.1. Additionally, we explore the connection between our proposed stationarity metric and existing metrics used in constrained optimization and general bilevel optimization. None of these are addressed in [3].\n\n**(2)** In the first part of their results (Section 3.2), [3] assumes that $\\lambda_k$ is uniformly upper-bounded (Assumption 3.4) in the constrained optimization setting, which is not possible in simple bilevel optimization. This assumption also simplifies their analysis substantially, as we noted in line 260.\n\n**(3)** In the second part of their results (Section 3.3), as mentioned in Remark 5.2, [3] analyzes the continuous-time limit of the algorithm. However, their analysis does not account for the additional error arising from approximating $f$ and $g$ using first-order Taylor expansions. Consequently, their convergence result cannot be directly translated into a concrete bound for the discrete-time algorithm. In contrast, our contributions include explicitly addressing this discretization error—requiring the solution of an implicit inequality (cf. Lemma 5.3), careful selection of the step size $\\eta$ and hyperparameter $\\beta$, as well as removing the common assumption of uniformly bounded $\\\\|\\nabla g\\\\|$.\n\n**(4)** Regarding convergence guarantees, Proposition 3.8 in [3] relies on the constant rank constraint qualification (CRCQ), which is known to be difficult to satisfy in bilevel optimization, as discussed in [6]. In contrast, our analysis does not depend on this assumption, as we use a different stationarity metric. For our proposed metric, no additional non-standard assumptions are required. To relate our metric to the one used in [3], an additional local error bound condition is needed—but not the more restrictive CRCQ assumption, as demonstrated in Theorem 3.2.\n\n---\n\nReferences:\n\n[1]. Samadi et al. Achieving optimal complexity guarantees for a class of bilevel convex optimization problems.\n\n[2]. Chen et al. Penalty-based methods for simple bilevel optimization under h\\\"{o} lderian error bounds.\n\n[3]. Gong et al. Bi-objective trade-off with dynamic barrier gradient descent.\n\n[4]. Sabach et al. A first-order method for solving convex bilevel optimization problems.\n\n[5]. Kaushik et al. A method with convergence rates for optimization problems with variational inequality constraints.\n\n[6]. Xiao et al. A Generalized Alternating Method for Bilevel Learning under the Polyak-{\\L} ojasiewicz Condition."}, {"review_id": "oXg008uGHc", "reviewer": "Reviewer_JLoC", "summary": "This paper studies the complexity of finding stationary points in nonconvex simple bilevel optimization problems, where the upper-level objective is minimized over the solution set of a lower-level problem. The authors introduce a notion of \\((\\epsilon_f, \\epsilon_g)\\)-stationarity to measure convergence, capturing points where the upper-level objective cannot be improved without worsening the lower-level objective. They adopt a variant of the Dynamic Barrier Gradient Descent (DBGD) algorithm and establish the first discrete-time complexity guarantee for nonconvex simple bilevel problems, showing that DBGD achieves an \\((\\epsilon_f, \\epsilon_g)\\)-stationary point in \\(\\mathcal{O}(\\max(\\epsilon_f^{-\\frac{3+p}{1+p}}, \\epsilon_g^{-\\frac{3+p}{2}}))\\) iterations, where p \\geq 0 is a tunable parameter. Furthermore numerical experiments validate the algorithm's effectiveness compared to penalty-based methods.", "questions": "NA", "limitations": "NA", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\nThis is a well-written paper that makes a valuable contribution by extending the framework of [46] to a non-convex setting for the low-level function. The authors provide a complete algorithmic solution and rigorously establish convergence guarantees, demonstrating both theoretical and practical advancements over prior work.\n\nWeaknesses: \n\nCould the authors elaborate on the additional technical difficulties arising from the non-convexity of the low-level function in their framework, compared to the convex formulation in [46]? Specifically:  \n1) How does non-convexity affect the theoretical analysis (e.g., convergence guarantees, optimality conditions)?  \n\n2) What algorithmic modifications were required to address these challenges?  \n\n3) Are there measurable performance trade-offs between the two approaches in practice?", "was_revised": true, "final_justification": "Authors have answered my questions.", "rebuttal": "**W. Could the authors elaborate on the additional technical difficulties arising from the non-convexity of the low-level function in their framework, compared to the convex formulation in [46]?**\n\nThank you for the question. The algorithm in [46] is designed for general bilevel optimization and requires the lower-level objective to be strongly convex. In contrast, we consider a slightly different setting—known as simple bilevel optimization—where there is no implicit dependency between the upper and lower-level variables, and the lower-level problem is generally nonconvex and smooth without additional assumptions.\n\nWithin the context of simple bilevel optimization, several works have focused on the convex setting, such as [1], [2], and [3]. Among these, [1] presents the most similar algorithm, and we demonstrate that a variant of it can be viewed as belonging to the same family as DBGD, as shown in Appendix C. We now explain the challenges arising from the nonconvexity of the lower level and address your specific questions below.\n\n**W1. How does non-convexity affect the theoretical analysis (e.g., convergence guarantees, optimality conditions)?**\n\n**R1.** Unlike simple bilevel optimization with a convex lower level, nonconvex simple bilevel optimization remains largely underexplored. In particular, no prior work has proposed optimality or stationarity conditions specifically for the nonconvex simple bilevel setting. Due to the lack of convexity in the lower level, the lower-level solution set can be nonconvex, making it intractable to achieve any form of global optimality. Consequently, as in its single-level counterpart, the primary objective in nonconvex simple bilevel optimization is to find a near-stationary point rather than a near-optimal solution, as defined in [1], [2], and [3]. In Section 3, we introduce a stationarity metric by decomposing the upper-level gradient into components parallel and orthogonal to the lower-level gradient, and we provide a rigorous interpretation of this metric in Lemma 3.1.\n\nRegarding convergence guarantees, we show that a variant of DBGD [4] can solve nonconvex simple bilevel optimization up to joint stationarity for both the upper and lower levels. To the best of our knowledge, this is the first complexity result for a discrete-time algorithm that establishes such joint stationarity guarantees for general nonconvex simple bilevel problems.\n\n---\n\n**W2. What algorithmic modifications were required to address these challenges?**\n\n**R2.** Similar algorithms for solving convex simple bilevel optimization problems [1, 3] use cutting-plane methods to approximate the lower-level solution set. However, these approaches do not extend to the nonconvex setting, as the lower-level solution set may be nonconvex, making it difficult to approximate and impossible to ensure the true solution lies within the approximated set.\n\nAs detailed in Appendix C, both a variant of the algorithm in [1] and our proposed algorithm can be viewed as instances of a shared framework, distinguished by their choice of the parameter function $\\phi(x)$. To adapt this framework to the nonconvex setting, we choose $\\phi(x) = \\beta ||\\nabla g(x)||^{2}$, in contrast to the convex setting where $\\phi(x) = (g(x) - g^{*})/\\eta$ is used. Here, $\\phi(x)$ reflects the suboptimality of the point $x$. Given that global optimality is generally unattainable in the nonconvex case, it is natural to replace the optimality gap with the stationarity measure $||\\nabla g(x)||^2$, which is commonly adopted in nonconvex optimization. This modification leads to the development of our analyzed algorithm and its corresponding analysis.\n\n---\n\n**W3. Are there measurable performance trade-offs between the two approaches in practice?**\n\n**R3.** \nTo assess measurable performance, we include additional baselines originally designed for convex simple bilevel problems. Please refer to R1 to Reviewer oo1n for details. As shown in the tables, these methods underperform compared to DBGD. This performance gap underscores the limitations of convex-based algorithms in the nonconvex setting and highlights the need for dedicated methods tailored to nonconvex simple bilevel optimization.\n\n\n---\n\n\nReferences:\n\n[1]. Ruichen Jiang, Nazanin Abolfazli, Aryan Mokhtari, and Erfan Yazdandoost Hamedani. A conditional gradient-based method for simple bilevel optimization with convex lower-level problem. In International Conference on Artificial Intelligence and Statistics, pages 10305–368\n10323. PMLR, 2023\n\n[2]. Sepideh Samadi, Daniel Burbano, and Farzad Yousefian. Achieving optimal complexity\nguarantees for a class of bilevel convex optimization problems. arXiv preprint arXiv:2310.12247,\n2023.\n\n[3]. Jincheng Cao, Ruichen Jiang, Erfan Yazdandoost Hamedani, and Aryan Mokhtari. An accelerated gradient method for convex smooth simple bilevel optimization. Advances in Neural Information Processing Systems, 37:45126–45154, 2024.\n\n[4]. Chengyue Gong, Xingchao Liu, and Qiang Liu. Bi-objective trade-off with dynamic barrier\n371 gradient descent. In Proceedings of the 35th International Conference on Neural Information\n372 Processing Systems, pages 29630–29642, 2021."}, {"review_id": "X6mpSunq7s", "reviewer": "Reviewer_ygXd", "summary": "This paper studies a simple bilevel optimization problem where both the upper- and the lower-level problems are non-convex. First, the authors introduce a novel notion of stationarity, tailored to the specific problem at hand, and establish its relationship to existing metrics in the bilevel optimization literature. Then, they apply the Dynamic Barrier Gradient Descent (DBGD) algorithm (originally developed for constrained optimization problems) to the nonconvex simple bilevel problem and establish discrete-time stationarity guarantees. We note that this represents the first discrete-time complexity bound that guarantees stationarity at both levels in such problems. Finally, a set of numerical experiments on toy examples and matrix factorization tasks illustrate DBGD method's superior performance over traditional penalty methods.", "questions": "- To situate the method within the existing literature, a table summarizing relevant results about simple bilevel optimization problems (method name, assumptions, optimality metric, complexity, etc.) could be helpful.\n- Is Assumption 3.1 (Local Error Bound) typically used in similar settings (ie simple nonconvex bilevel problems)? Is it a strong assumption? Are there common applications in which this assumptions holds?\n- The definition of stationarity for the proposed problem is a central contribution of this work and should be properly situated within the relevant literature. Has this particular stationarity metric, or a related one, been previously introduced or discussed in the bilevel optimization literature?\n- What approach did you use to tune the penalty parameter (of the penalty method baseline in the experiments) for obtaining the best possible performance and ensuring fair comparisons?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- This paper deals with a challenging bilevel problem. It is a nonconvex simple bilevel problem where both the upper and lower-level objectives are nonconvex functions. \n- A suitable stationarity concept is introduced for the specific nonconvex simple bilevel problem, and its relationship to existing metrics in the bilevel optimization literature is established.\n- The paper provides the first discrete-time complexity bound that guarantees stationarity at both levels of a  nonconvex simple bilevel problem.\n\nWeaknesses\n- Since this is a simple bilevel problem, its applicability is somewhat limited. In fact, the only application discussed in detail is matrix factorization. The authors may wish to provide more information about the potential applications of the specific bilevel problem they are addressing, e.g. by providing specific example applications and their formulations.\n- The experimental evaluation is somehow limited. There is only one baseline, the penalty method and the experiments consist of toy problems and small scale matrix factorization tasks. Are there other bilevel methods that can be used for the solution of this problem? How about methods developed for generic (not necessarily) simple bilevel problems?", "was_revised": true, "final_justification": "The authors addressed my questions. I’m generally satisfied with the response and recommend acceptance of the paper. Specifically, the authors plan to include a discussion in the revised paper on the applications of their problem, and they will expand the experimental section by adding more baselines. However, I still believe a rating of 4 is appropriate.", "rebuttal": "**W1. Since this is a simple bilevel problem, its applicability is somewhat limited. In fact, the only application discussed in detail is matrix factorization. The authors may wish to provide more information about the potential applications of the specific bilevel problem they are addressing, e.g. by providing specific example applications and their formulations.**\n\n\n**R1.** Thank you for your comment!\nAlthough the paper focuses on results on matrix factorization, simple bilevel optimization has many other applications. These include sparse representation learning, fairness regularization, and lexicographic optimization [1]; over-parameterized regression and dictionary learning [2, 3]; and linear inverse problems [4].\n\nBelow, we provide some specific formulations:\n\n*Sparse Representation Learning.* We learn sparse feature representations on a supervised dataset $\\mathcal{D}$ of $(x,y)$ pairs by applying a non-convex $L_p$ regularization:\n\n$$\nf(\\theta) = \\mathbb{E} [\\ell(y, \\phi_{\\theta}(h_{\\theta}(x)))], \\quad\ng(\\theta) = \\mathbb{E} [\\|h_{\\theta}(x)\\|_{p}^{p}]\n$$\n\n\nwhere $\\ell(\\cdot,\\cdot)$ is the data loss, $h_{\\theta}(x) \\mapsto z \\in \\mathbb{R}^{m}$ is a hidden feature map, $\\phi_{\\theta}$ is a prediction head, and $p$ is a power coefficient. \n\n*Fairness Classification.*\nConcretely, the lower-level problem is a logistic regression problem:\n\n$$ \ng(\\beta) = -\\frac{1}{n} \\sum_{i=1}^{n} \\log \\mathbb{P}(\\hat{y}_i = y_i \\mid \\mathbf{x}_i; \\beta) \n$$\n\nwhile the upper-level objective is the squared covariance:\n\n$$\nf(\\beta) = \\left( \\frac{1}{n} \\sum_{i=1}^{n} (v_i - \\bar{v}) \\mathbb{P}(\\hat{y}_i = 1 \\mid \\mathbf{x}_i; \\beta) \\right)^{2}\n$$\n\n*Dictionary Learning.* We aim to find the dictionary $\\tilde{\\mathbf{D}} \\in \\mathbb{R}^{m \\times q}$ ($q > p$) and the coefficient matrix $\\tilde{\\mathbf{X}} \\in \\mathbb{R}^{q \\times n'}$ for the new dataset $A'$, and at the same time enforce $\\tilde{\\mathbf{D}}$ to perform well on the old dataset $A$ together with the learned coefficient matrix $\\hat{\\mathbf{X}}$. This leads to the following bilevel problem:\n$$\nf(\\tilde{\\mathbf{D}}, \\tilde{\\mathbf{X}}) \\triangleq \\frac{1}{2n'} \\sum_{k=1}^{n'} \\| \\mathbf{a}'_{k} - \\tilde{\\mathbf{D}} \\tilde{\\mathbf{x}}_k \\|_2^2\n$$\n\nis the average reconstruction error on the new dataset $A'$, and the lower-level objective  \n\n$$\ng(\\tilde{\\mathbf{D}}) \\triangleq \\frac{1}{2n} \\sum_{i=1}^{n} \\| \\mathbf{a}_{i} - \\tilde{\\mathbf{D}} \\hat{\\mathbf{x}}_i \\|_2^2\n$$\n\nis the error on the old dataset $A$.  \nWe will include this discussion in the revised paper.\n\n---\n\n**W2. The experimental evaluation is somehow limited. There is only one baseline, the penalty method and the experiments consist of toy problems and small scale matrix factorization tasks. Are there other bilevel methods that can be used for the solution of this problem? How about methods developed for generic (not necessarily) simple bilevel problems?**\n\n**R2.** Thanks for the question. To the best of our knowledge, there are no other existing methods for solving non-convex simple bilevel optimization with theoretical guarantees. Our result is the first complexity result for a discrete-time algorithm that guarantees joint stationarity for both levels in nonconvex simple bilevel problems.\n\nRegarding methods for solving general bilevel optimization problems, as discussed in Appendix D (lines 905–920), we highlight the connections between algorithms designed for simple bilevel optimization and those for general bilevel optimization. Specifically, when applied to the simple bilevel setting (where no upper-level variable is present), most existing methods for general bilevel optimization reduce to the penalty method. This is the reason we selected the penalty method as our baseline.\n\nFurthermore, we also include additional baselines—algorithms originally developed for the convex case—which further demonstrate that DBGD outperforms them. Please refer to R1 to Reviewer oo1n for more details.\n\n---\n\n**Q1. To situate the method within the existing literature, a table summarizing relevant results about simple bilevel optimization problems (method name, assumptions, optimality metric, complexity, etc.) could be helpful.**\n\n**A1.** Thank you for the question. To the best of our knowledge, there are no other methods that provably solve nonconvex simple bilevel optimization. Our work provides the first complexity result for a discrete-time algorithm that guarantees joint stationarity for both levels in general nonconvex simple bilevel problems. Regarding the convergence metric, we offer a detailed discussion comparing the guarantees in general bilevel optimization and constrained optimization in Section 3.1, and we also elaborate on this below in response to Q3.\n\nAdditionally, we discuss related work on convex simple bilevel optimization in Section 1.1. If necessary, we can provide a consolidated summary of methods in a table for solving both convex and nonconvex simple bilevel problems.\n\n---\n\n**Q2. Is Assumption 3.1 (Local Error Bound) typically used in similar settings (ie simple nonconvex bilevel problems)? Is it a strong assumption? Are there common applications in which this assumptions holds?**\n\n**A2.** \nSince nonconvex simple bilevel problems are underexplored, there are very few works that have even considered this setting. The local error bound condition is widely used in the constrained optimization literature [3, 4]. We believe this assumption is not strong, as it can be implied by a local PL inequality, which is itself a relaxation of the global PL condition—verified, for instance, for overparameterized least-squares and certain neural network loss functions [5].\n\n---\n\n**Q3. The definition of stationarity for the proposed problem is a central contribution of this work and should be properly situated within the relevant literature. Has this particular stationarity metric, or a related one, been previously introduced or discussed in the bilevel optimization literature?**\n\n**A3.** To the best of our knowledge, no stationarity metric has previously been proposed for this setting. However, related stationarity metrics have been studied in constrained optimization and general bilevel optimization. In Section 3.1, we provide a detailed comparison of the guarantees in these settings. Specifically, our proposed metric implies the commonly used scaled and unscaled KKT conditions in constrained optimization (as shown in Section 3.1.1) and also aligns with a widely adopted metric, KKT conditions for gradient-based reformulation, in general bilevel optimization, as explicitly stated in Theorem 3.2.\n\n---\n\n**Q4. What approach did you use to tune the penalty parameter (of the penalty method baseline in the experiments) for obtaining the best possible performance and ensuring fair comparisons?**\n\n**A4.** Thanks for the question. We use a grid search, which is a common practice for hyperparameter tuning. Specifically, we explored the penalty parameter \n$\\lambda \\in \\\\{ 10^{-k} \\mid k \\in [-5, 5] \\\\}$, and found that the performance is better for $k = \\\\{0, 1, 2, 3\\\\}$.\n\n\n---\n\n\n\nReferences:\n\n[1]. Chengyue Gong, Xingchao Liu, and Qiang Liu. Bi-objective trade-off with dynamic barrier\n371 gradient descent. In Proceedings of the 35th International Conference on Neural Information\n372 Processing Systems, pages 29630–29642, 2021.\n\n[2]. Ruichen Jiang, Nazanin Abolfazli, Aryan Mokhtari, and Erfan Yazdandoost Hamedani. A conditional gradient-based method for simple bilevel optimization with convex lower-level problem. In International Conference on Artificial Intelligence and Statistics, pages 10305–10323. PMLR, 2023.\n\n[3]. Jincheng Cao, Ruichen Jiang, Nazanin Abolfazli, Erfan Yazdandoost Hamedani, and Aryan Mokhtari. Projection-free methods for stochastic simple bilevel optimization with convex lower-level problem. Advances in Neural Information Processing Systems, 36, 2023.\n\n[4]. Shoham Sabach and Shimrit Shtern. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization,27(2):640–660, 2017.\n\n[5]. Xu, Yi, Qihang Lin, and Tianbao Yang. \"Accelerated stochastic subgradient methods under local error bound condition.\" arXiv preprint arXiv:1607.01027 (2016).\n\n[6]. Liu, Hongwei, Ting Wang, and Zexian Liu. \"Convergence rate of inertial forward–backward algorithms based on the local error bound condition.\" IMA Journal of Numerical Analysis 44.2 (2024): 1003-1028.\n\n[7]. Liu, C., Zhu, L., and Belkin, M. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85–116, 2022."}, {"review_id": "H27iUqEoo3", "reviewer": "Reviewer_qGQn", "summary": "This paper studied a smooth nonconvex simple bilevel optimization problem and developed the stationary condition for it. They then proved that dynamic barrier gradient descent algorithm can converge to the defined stationary point in polynomial time. Specifically, to reach an $(\\epsilon_f, \\epsilon_g)$ stationary point, the algorithm needs $\\max(\\epsilon_f^{-\\frac{3+p}{1+p}},\\epsilon_f^{-\\frac{3+p}{2}})$ iterations. Numerical experiments validate the effectiveness of the proposed algorithm.", "questions": "1. Do you intend to show that the proposed stationarity condition implies (6) and (7)? If so, please provide a more detailed explanation.\n2. The domain of $\\lambda$ is unclear. I recommend distinguishing between cases where $\\lambda$ takes a finite value, i.e., $\\lambda \\in \\mathbb{R}_+$, and cases where it may include infinity, i.e., $\\lambda \\in (0, +\\infty]$. For example, in the line below Line 168, the KKT multiplier $\\lambda$ should be finite. However, in equation (3) and the algorithm design, $\\lambda$ can be infinite. \n3. Please refer to Weaknesses 1) and 2) for concerns related to Lemma 3.1.", "limitations": "The main limitation lies in the potential overstatement of the conclusions drawn from Lemma 3.1.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: 1) The problem studied in this paper is significant for both simple bilevel optimization and general bilevel optimization. By removing convexity and PL conditions at the lower level, the authors provide a broader theoretical guarantee for stationarity. 2) The idea of decomposing the upper-level gradient into orthogonal and parallel components is interesting and innovative. 3) The proposed algorithm is supported by a strong convergence guarantee.  \n\nWeakness: (1) The main concern is the correctness—or perhaps overstatement—of Lemma 1. For a smooth function, if the local region is chosen to be sufficiently small (as in the proof, where the radius $r$ is on the order of the target error, i.e., very small), then almost any point could qualify as the \"near-local optimum\" under the authors’ definition. This is especially problematic when the definition’s validity depends heavily on $r$. Additionally, the conclusion of Lemma 1 seems counterintuitive: for a smooth function, a small gradient does not rule out the possibility of being a local maximum. From my perspective, a more robust definition of a near-local minimum should require the existence of a fixed-radius local region where the inequalities in Lemma 3.1 hold. \n\n(2) Another weakness is that I do not understand the second point of Lemma 3.1. It is rigorous to say that for any point with improvement on the lower-level objective, the upper-level objective changes is not to much since $\\delta$ is very small. But I do not see why the improvement on the lower-level will lead to the negative effect on the upper-level, as said in this paper. I quoted the statement here \"the upper-level objective cannot be significantly improved without negatively impacting\". \n\n(3) The above two concerns is on the definition of stationarity. I also do not understand the relations of existing stationary measure in (6), especially there is a strange (ii) in Line 176.", "was_revised": true, "final_justification": "This paper established the stationary condition for nonconvex smooth simple bilevel optimization without any additional assumptions on lower-level problem such as Polyak-Lojaswicz condition. This contribution is significant to bilevel optimization because finding an appropriate stationary condition serves as a foundation to establish algorithm convergence. This paper also analyzed the convergence rate of dynamic barrier gradient descent algorithm under this setting. Since all of my concerns are solved, I increased the score to 4.", "rebuttal": "**W1. The main concern is the correctness—or perhaps overstatement—of Lemma 1. For a smooth function, if the local region is chosen to be sufficiently small (as in the proof, where the radius $r$ is on the order of the target error, i.e., very small), then almost any point could qualify as the \"near-local optimum\" under the authors’ definition. This is especially problematic when the definition’s validity depends heavily on $r$. Additionally, the conclusion of Lemma 1 seems counterintuitive: for a smooth function, a small gradient does not rule out the possibility of being a local maximum. From my perspective, a more robust definition of a near-local minimum should require the existence of a fixed-radius local region where the inequalities in Lemma 3.1 hold.**\n\n**R1.** \nThank you for raising this question. We believe there may be a misunderstanding regarding the first condition in Lemma 3.1. Even if the local region is chosen to be sufficiently small, it is *not* the case that almost any point would satisfy this condition. Specifically, suppose $g$ is $G$-Lipschitz; then for any $x$, we have $g(x) \\geq g(\\hat{x})-G\\\\|\\hat{x}-x\\\\|$. However, our condition in Lemma 3.1 is much stronger: it requires $g(x) \\geq g(\\hat{x})-(1+\\delta)\\sqrt{\\epsilon_g}\\\\|\\hat{x}-x\\\\|$, which replaces the Lipschitz constant $G$ with the much smaller coefficient $\\sqrt{\\epsilon_g}$. As a concrete example, consider $g(x) = x^2$. When \n$x$ is sufficiently large, this condition cannot be satisfied no matter how small the local region is.\n\nThe reviewer is correct that our definition does not preclude $\\hat{x}$ from being a local maximum. Indeed, it measures approximate stationarity via the gradient norm (Definition 3.1), which is standard in nonconvex optimization. Note that our conclusion following Lemma 3.1 remains valid even if $\\hat{x}$ is a local maximum, since due to smoothness, the function value cannot decrease significantly within a small neighborhood in that case either. We also agree that it would be a stronger notion of a near-local minimum if the radius could be chosen independently of the target error $\\epsilon$. However, achieving this appears to be a nontrivial task, even in standard single-level minimization problems.\n\nLastly, to make Lemma 3.1 more precise, such a radius should be treated as an upper bound. Specifically, a point $\\hat{x} \\in \\mathbb{R}^n$ is an $(\\epsilon_f, \\epsilon_g)$-stationary point of SBO if and only if the following holds: for any $\\delta > 0$, there exists a radius $\\hat{r} > 0$ such that for all $0 < r \\leq \\hat{r}$, both conditions in Lemma 3.1 are satisfied. This refinement does not affect the validity of the proof, and such a radius $\\hat{r}$ can be determined based on the analysis provided in Appendix A.\n\n---\n\n**W2. Another weakness is that I do not understand the second point of Lemma 3.1. It is rigorous to say that for any point with improvement on the lower-level objective, the upper-level objective changes is not to much since $\\delta$ is very small. But I do not see why the improvement on the lower-level will lead to the negative effect on the upper-level, as said in this paper. I quoted the statement here \"the upper-level objective cannot be significantly improved without negatively impacting\".**\n\n**R2.** \nThank you for the comment. \nSpecifically, when the second condition is satisfied, then for any $ \\\\|x - \\hat{x}\\\\| \\leq r $, if \n$\nf(x) < f(\\hat{x}) - (1 + \\delta)\\sqrt{\\epsilon_f} \\\\|x - \\hat{x}\\\\|\n$ (i.e., if the upper-level objective is significantly improved), \nit must be that $ g(x) > g(\\hat{x}) $ (meaning the lower level objective is negatively impacted).\nIn this sense, it indicates that we aim to find points where the upper-level objective cannot be significantly improved without negatively affecting the lower-level objective. If such a point is found, approximate stationarity is achieved. \n\nWe are not asserting that this is always the case---if both objectives can be decreased simultaneously, the point is not stationary by our definition. Therefore, the two conditions in Lemma 3.1 should be interpreted jointly, rather than viewed separately. \n\n---\n\n**W3. The above two concerns is on the definition of stationarity. I also do not understand the relations of existing stationary measure in (6), especially there is a strange (ii) in Line 176.**\n\n**R3.** Thank you for the question. We would like to clarify that metrics (5) and (6) are not our proposed metrics; they are convergence metrics commonly used in the constrained optimization literature [1, 2]. As noted in lines 172–176, these works aim to find a point $x$ that satisfies either (5) or (6). In particular, (6) indicates that such a point is stationary but not necessarily globally optimal for $g$. We further elaborate on its connection with our proposed metric in response to your next question below.\n\n---\n\n**Q1. Do you intend to show that the proposed stationarity condition implies (6) and (7)? If so, please provide a more detailed explanation.**\n\n**A1.** Yes. A point satisfying either (6) or (7) is considered stationary in the constrained optimization literature [3]. As noted in lines 178–181, we state that if a point $x$ satisfies our proposed metric, then $x$ also satisfies either (6) or (7), which can be verified directly.\n\nSpecifically, suppose $x$ is an $(\\epsilon_d^2,\\epsilon_d^2)$-stationary point (Definition 3.1). If $ g(x) - g^* \\geq 0.99 \\epsilon_{p} $, condition (6) follows from the first condition in Definition 3.1; otherwise, $g(x) - g^* < 0.99 \\epsilon_{p} < \\epsilon_p$, and condition (7) holds due to the second condition in Definition 3.1.\n\nMoreover, since condition (7) (the unscaled KKT condition) is stronger than condition (5) (the scaled KKT condition), it follows that if $ x $ is an $(\\epsilon_d^2,\\epsilon_d^2)$-stationary point, then $x$ satisfies either (5) or (6) as well.\n\n---\n\n**Q2. The domain of $\\lambda$ is unclear. I recommend distinguishing between cases where $\\lambda$ takes a finite value, i.e., $\\lambda \\in \\mathbb{R}_+$, and cases where it may include infinity, i.e., $\\lambda\\in(0, +\\infty]$. For example, in the line below Line 168, the KKT multiplier should be finite. However, in equation (3) and the algorithm design, \n can be infinite.**\n\n **A2.** Thank you for the question. To clarify, in both our proposed definition and algorithm design, $\\lambda$ is always assumed to be finite,  although we do not impose a uniform upper bound on its value. We will add this point to the paper.\n\n ---\n\nReferences:\n\n[1]. Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. On the complexity of finding first order critical points in constrained nonlinear optimization. Mathematical Programming, 2014.\n\n[2]. Coralia Cartis, Nicholas IM Gould, and Ph L Toint. Corrigendum: On the complexity of finding first-order critical points in constrained nonlinear optimization. Mathematical Programming, 2017\n\n[3]. Ernesto G Birgin, JL Gardenghi, José Mario Martínez, Sandra A Santos, and Ph L Toint. Evaluation complexity for nonlinear constrained optimization using unscaled kkt conditions and high-order models. SIAM Journal on Optimization, 2016."}]

Author rebuttal:

Meta-review: The paper focuses on solving bilevel optimization problems, where the upper-level objective is minimized over the solution set of the lower-level problem. The case where both objectives might be nonconvex is examined. Since the problem is computationally intractable in that regime, the authors introduce a new (reasonable) notion of stationarity and show that a variant of Dynamic Barrier GD achieves approximate stationarity. The paper received mixed reviews but during the rebuttal, the authors provided thorough explanations and made all reviewers having positive or slightly positive opinion. We recommend acceptance and advise the authors to invoke the feedback from the reviewers to their camera ready version.
Decision: Accept (poster)