An Alternating Optimization Method for Bilevel Problems under the Polyak-Łojasiewicz Condition
Authors: Quan Xiao
Songtao Lu
Tianyi Chen
Venue: NeurIPS 2023 poster (2023)
Keywords: Bilevel optimization
nonconvex constrained optimization
convergence analysis
TL;DR: Bilevel optimization with the nonconvex lower-level problem

Abstract: Bilevel optimization has recently regained interest owing to its applications in emerging machine learning fields such as hyperparameter optimization, meta-learning, and reinforcement learning. Recent results have shown that simple alternating (implicit) gradient-based algorithms can match the convergence rate of single-level gradient descent (GD) when addressing bilevel problems with a strongly convex lower-level objective. However, it remains unclear whether this result can be generalized to bilevel problems beyond this basic setting. In this paper, we first introduce a stationary metric for the considered bilevel problems, which generalizes the existing metric, for a nonconvex lower-level objective that satisfies the Polyak-Łojasiewicz (PL) condition. We then propose a Generalized ALternating mEthod for bilevel opTimization (GALET) tailored to BLO with convex PL LL problem and establish that GALET achieves an $\epsilon$-stationary point for the considered problem within $\tilde{\cal O}(\epsilon^{-1})$ iterations, which matches the iteration complexity of GD for single-level smooth nonconvex problems.

A Generalized Alternating Method for Bilevel Optimization under the Polyak- Condition
Quan Xiao
Songtao Lu IBM Research Yorktown Heights, NY, USA songtaodibm.c com
Tianyi Chen
Rensselaer Polytechnic Institute Troy, NY, USA xiaoq5erpi.ent edu
Rensselaer Polytechnic Institute Troy, NY, USA
Mhentiany119@gmaii com
Abstract
Bilevel optimization has recently regained interest owing to its applications emerging machine learning fields such hyperparameter optimization, meta- learning, and reinforcement learning. Recent results have shown that simple alternating (implicit) gradient-based algorithms match the convergence rate of single-level gradient descent (GD) when addressing bilevel problems with a strongly convex lower-level objective. However, it remains unclear whether this result can be generalized to bilevel problems beyond this basic setting. In this paper, we first introduce stationary metric for the considered bilevel problems, which generalizes the existing metric. for nonconvex lower-level objective that satisfies the Dolyak-Lojasiewice (PL) condition. We then propose Generalized ALternating mEthod for bilevel op ommimization (GALET) tailored to BLO with convex PI. LL problem and establish that GALET achieves an c-stationary point for the considered problem within Ö(e-l) iterations, which matches the iteration complexity of GD for single-level smooth nonconvex problems.
Introduction
Bilevel optimization (BLO) is hierarchical optimization framework that aims to minimize the upper-level (UL) objective, which depends the optimal solutions of the lower-level (LL) problem. Since its introduction in the 1970s [5] BLO has been extensively studied in operations research, mathematics, engineering, and economics communities [14], and has found applications in image processing [2] and wireless communications [8] Recently, BLO has regained interests as a unified framework of modern machine-leaming applications, including hyperparameter optimization
(49 21
22 [54,, meta-learning (20), representation learning (3], reinforcement learning 62 (59 continual
learning [55 adversarial learning [73 and neural architecture search (39 see
41
In this paper, we consider BLO in the following form
min wES(()
fxx v)
S.L. S(x) A arg min g(x, v)
yER4
where both the UL objective f(x y) and LL objective g(2, y) are differentiable, and the LL solution set S(x) is not necessarily singleton. For ease of notation, we denote the optimal function value of the LL objective as g" (xx =- min, g(x,y) y) and call it value function.
Although BLO is powerful for modeling hierarchical decision decision-making processes, solving generic BLO problems is known to be NP-hard due to their nested structure [1]. As a result, the majority of recent works optimization theory of BI.O algorithms are centered on nonconvex UL. problems with strongly convex LII problems
which permit the development of efficient algorithms; see e.g. (2 27 32 9 35 10 34 67 66). The strong convexity assumption for
LL ensures the uniqueness of the minimizer and simple loss landscape of the LL problem, but
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

GALET
V-PBGD
BOME
MGBiO
BGS
IAPTT-GM
IGFM
g(2, 4)
PL C
PL
PL
SC
Morse Bott
Regular
PL
Non-singleton S(z)
V
/
V
X
V
/
/
Provable CQ
Relaxed
/
Relaxed
Complexity
O (,5)
O
poly(e
Table 1: Comparison of the proposed method GALET with the existing BLO for non-strongly-come
LL problem (V-PBGI [57], BOME (37]. MGBiO (88, BGS (2. IAPTT-GM [43, IGFM (7). The
notation Ô omits the dependency on log(e-)) terms and poly(e-t) hides the dependency worse than O(. 'C', "SC' and 'Regular' stand for convex, strongly convex and Assumption 3.1 in (43. respectively. PL., Lipschitz Hessian and the assumption that eigenvalue bounded away from 0 in MGBiO imply SC. 'Relaxed' means that they solve a relaxed problem without CQ-invalid issue and 'f' means that CQ is not needed as it based on the implicit function theorem.
excludes many intriguing applications of BLO. In the context of machine learning, the LL objective might represent the training loss of a neural network, which can be non-strongly-come -oonvex [65]
To measure the efficiency of solving nonconvex BLO problems, it is essential to define its stationarity, which involves identifying necessary condition for the optimality of BLO. In cases where the LL problem exhibits strongly convexity, the solution set S(z) becomes a singleton, leading to natural definition of stationarity as the stationary point of the overall objective fzz S(x)), i.c.. f(z, S(r)) 0. However, for BLO problems with non-strongly-comee have multiple solutions, rendering fz, S(x)) ill-posed. This motivates an intriguing question:
LL problems, S(x) may
Q1: What is a good metric of stationarity for BLO with nonconvex LL problems?
To address this question, we focus on the setting of BLO with the LL objective that satisfies the PL condition (nonconvex-PL. PL). The PL condition not only encompasses the strongly convexity condition 24 27 32 9 335 [0)] 34 67 [6] and the Morse -ott condition 22] but also covers many applications learning LQR models [19] and phase retrieval [6].
such overparameterrzed neural networks 38
By reformulating the LL problem by its equivalent conditions, one can convert the BLO problem to a constrained optimization problem. Then with certain constraint qualification (CQ) conditions, a natu- ral definition of the stationarity of the constrained optimization problem is the
(KKT)) point [11] For example, constant rank CQ (CRCQ) was assumed in (37] and linear in- dependence CQ (LICQ) was assumed or implied
44 28 However, it is possible that none of these conditions hold for nonconvex-PL PL. BLO (Section 2.2 In Section 2 we study different CQs on two constrained reformulations of (1) and then identify the best combination. Based on the right CQ on the right constrained reformulation, we prove the inherent CQ and propose new notion of stationarity for the nonconvex- PL BLO, which strictly extends the existing measures in nonconvex-siie wwworeeessttoooyoooooooe
9 relaxing the problem (36 57 We emphasize the importance of defining new metric in Section 2.3
BLO 24 27 32
and nonconvex- noncoooeexx BLO 2 37 28 without
Given a stationary metric, while e-stationary point can be found efficiently in O(e-1) iterations for nonconvex and smooth single-level problem [6]. existing works on the BL.O with non-strongly-conwe
LL problem either lack complexity guarantee [2] 43 36 42). or occur slower rate [57 37 58 77.
Moreover, most existing algorithms update the UL variable x after obtaining the LL parameter y sufficiently close to the optimal set S(x) by running GD from scratch, which is computationally BLO
expensive (37 57]. In contrast, the most efficient algorithm for conconyex-ttrongly-comm
updates z and in an alternating manner, meaning that x is updated after a constant number of updates from their previous values 32]. Then another question arises:
Q2: Can alternating methods achieve the ( complexity for non-stronglyycoovee BLO?
Addressing this question is far from trivial. First, we need to characterize the drifting error of (zx) induced by the alternating strategy, which involves the change in the L.I. solution sets between two consecutive UL iterations. However, we need to generalize the analysis in nonconvex--tronnly-coom
BLO 9 32 24
27
because S(x:) is not singleton. Moreover,
need to select an appropriate
Lyapunov function to characterize the UL descent, as the nature candidate f(r, (x)) is ill-posed without a unique LL minimizer. Finally, since the Lyapunov function we choose for UL contains both x and y, it is crucial to account for the drifting error of y as well.
By exploiting the smoothness of the value function (xx and with the proper design of the Lyapunov function, we demonstrate the Ō(e-)) iteration complexity of our algorithm, which is optimal in terms
2

---

cf e. This result not only generalizes the convergence analysis in nonconvex mencoonye-sttronnyycoo strongly-convee BLO 67 66 to the broader problem class, but also improves the complexity of BLO, specifically ((c-L.5) in 57 and (c in 37:: see [ We present our algorithm in Section 3 and analyze its convergence in Section followed by the simulations and conclusions in Section
24
27 32
35
10
existing works on nonconvex-non-sVWe seatt-sttooggoooyeeeeee
1.1 Related works
Nonconvex BLO. The interest in developing efficient gradient-based methods and their nonasymptotic analysis for nonconvex wetenreee--soooy-ooooo conveex BLO has been invigorated by recent works [24 32 27] (9. Based the different UL gradient approximation techniques they use, these algorithms can be categorized into iterative differentiation and approximate implicit differentiation based approaches. The iterative lnffferentiittinnbassee methods relax the LLL problem by dynamical
system and use the automatic differentiation to approximate the UI. gradient [21 22 25]. while
the approximate implicit differentiation-basse methods utilize the implicit function theory and
approximate the UL gradient by the Hessian inverse (e.g. Neumann series 9 24 27]: kernel-based
methods (26)) or Hessian-vector production approximation methods (e.g. conjugate gradient descent 32 54], gradient descent [35 M. Recent advances include variance reduction and momentum based methods 34 67 [3: warm-started BLO algorithms
35); distributed BLO approaches [63 46 68];
and algorithms solving BLO with constraints [64] 66 Nevertheless, none of these attempts tackle
the BLO beyond the strongly convex LL problem.
Nonconvex-noncoover BLO. While nonconvex-stronge -troeeg-soooglyccoeeex BLO has been extensively studied in the literature, efficient algorithms for BLO with nonconvex LL problem remain under-explored. Among them, Liu et al. 45 developed a BLO method with initialization auxiliary and truncation of pessimistic trajectory; and Arbel and Mairal 2 generalized the implicit function theorem to class of nonconvex LL functions and introduced a heuristic algorithm. However, these works primarily focus on analyzing the asymptotic performance of their algorithms, without providing finite-time convergence guarantees. Recently, Liu et al. (37 proposed a first-order method and established the first nonasymptotic analysis for non-strongly-convex BLO. Nonetheless, the assumptions such as CRCQ and bounded Ifl, l91 are relatively restrictive. Huang [28] has proposed a momentum- based BLO algorithm, but the assumptions imply strongly convexity. Another research direction has addressed the nonconvex BLO problem by relaxation, such as adding regularization in the LL 42 50. or replacing the LL optimal solution set with its c-optimal solutions (36 57. Although
this relaxation strategy overcomes the CQ-invalid issues, it introduces errors in the original bilevel problem (7]. To the best of our knowledge, none of these BLO algorithms handling multiple LL solutions can achieve the optimal iteration complexity in terms of e.
Nonconvex-conver BLO. Another line of research focuses on the BLO with convex LL problem, which can be traced back to [48 [8]. Convex LL problems pose additional challenges of multiple LL BLO. To tackle multiple LL solutions, an aggregation approach was proposed in [56] [0]: a primal-dual algorithm was considered in (58): differencce-f-ccnnees constrained reformulated problem was explored in [72] 23:; an averaged multiplier method was proposed in [45). Recently, Chen et al. has pointed out that the objective of the non-stronglyycooneex LL problem can be discontinuous and proposed a zeroth-order mmoothing-based method; Lu and Mci [47] have solved it by penalized min-max optimization. However, none of these attempts achieve the iteration complexity of Ö( Moreover, although some works adopted KKT related concept as stationary measure, they did not find the inherent CQ condition, so the necessity of their measure to the optimality of BLO is unknown 45 47). In this sense, our work is complementary to them. The comparison with closely related works is summarized in [
solutions which hinder from using implicit-based approaches for nonconvex wwwprreeeesstooy-ooooooo
Notations. For any given matrix A E Rddd we list the singular values of A in the increasing order as 0 S 01 (A) & (A) < ... I (A( and denote the smallest positive singular value of A as o t (A). We also denote A-1 A', 1//2 and A-122 as the inverse of A, the Moore-Penrose inverse of A 29] the square root of A and the square root of the inverse of A, respectively. Ker(A) {x
Ax = 0}. Ran(A) = {Ax} denotes the null space and range space of A.
2 Stationarity Metric of Nonconvex-PL. BLO
We will first introduce the equivalent constraint- of the nonconvex-PLL BLO and then introduce our stationarity metric, followed by section highlighting the importance of our results.
3

---

2.1 Equivalent constraint- of BLO
By viewing the LL problem constraint to the UL problem, BLO be reformulated single-level nonlinear constrained optimization problem. Based on different equivalent characteristics of the LL problem, two major reformulations commonly used in the literature [16). The first approach is called value function-based reformulation, that is
f(r s.t. g( -9" (x) 0. x ZER4 .ER4y
min
Clearly, g(r, gar)) = 0 is equivalent to y S(z) so that (2 is equivalent to (
On the other hand, recall the definition of PL function below, which is not necessarily strongly convex or even convex 133
Definition 1 (PL condition). The function g(z, -) satiisfees the PL condition if there exists My such that for any given I, it holds that V xr y) 1|2 ( y) 9" (a:)), Vy.
According to Definition 1 for PL functions, V Vag(E, y) = implies g(x, y) = 9 (ar). Therefore, the second approach replaces the LLI problem with its stationary condition, that is
min SERdZ.eER
f(x, y)
s.t. Vog(z,
We call (3) the gradient-based reformulation. The formal equivalence of and 3 with I is established in Theorem in Appendix.
For constrained optimization, the commonly used metric of quantifying the stationarity of the solutions the KKT conditions. However, the local (resp. global) minimizers do not necessarily satisfy the KKT conditions [T] To ensure the KKT conditions hold at local (resp. global) minimizer, one needs to assume CQ conditions, c.g., the Slater condition, LICQ, qualification (MFCQ), and the CRCQ [30]. Nevertheless, Ye and Zhu (70) have shown that none of these standard CQs are valid to the reformulation for all types of BLO.
LangassarannFromoovvo
constraint
Optimality gap v.s. iterations
2.2 Stationarity metric
Enp Contanii 2
Initiaiization I
We will next establish the necessary condition for nonconvex-Pl -L BLO via the calmness condition [I]] Definition 6.4. 1J. which is weaker than the Slater condition, LICQ, MFCQ and CRCQ.
Intiaaizationn 2
Definition (Calmness). Let (x* ,y²) be the globul minimizer of the constrained problem
5
10
15
20
25
Iteration
Stationary score v.s. iterations
10
min f(x,y) s.t. h(x,y)= =. I.y
(4)
Stationary sone
Value function based, Initiaiiation
Our stationary metric, Iniialization
Value function haved. Initialization
where h Rda-dy - RRd and d > 1. If there exist
Our stationary metrie, insialization
positive and M such that for any E Rd with
llall S and any [[x',, .v)' - -ax,, y I which
satisfies h(x', d')++ + = one has
5
10
15
20
25
Iteration
f(z',1)) f(x", ...'' M mll 2 0 then the problem 4 said to be calm with M.
(5) Figure 1: Example I under different initial- ization. The solid and dashed lines represent two initialization in both plots. Top: the dis- tance to the global optimal set measured by 446) v.s. iteration. Bottom: the stationary
The calmness of a problem quantifies the sensitivity of the objective to the constraints. Specifically, the calmness conditions of reformulations ( and (3) are defined by setting l(x,, v) g(x,, y) (x) and h(,, v) = Vy (I. v). respectively.
score of (2) and (3) v.s. iteration.
The calmness condition is the weakest CQ which can be implied by Slater condition, LICQ, MFCQ and CRCQ [II]. However, as we will show, even the calmness condition does not hold for the nonconvex-PP PL. BLO when employing the value function- based based reformulation (2).
Example 1. Considering x E R.
[V1, y2l E IR?, and the BLO problem
1
min f(z, v) x² vı sin( s.t. y E arg min g(2, y) 7 + y1 2in( (6) 2.
2
y

---

Lemma 1. Considering the BLO problem in Example and the global minimizers of it are within the set
! the LL objective satisfies the PL condition
wi
{ 0) I = 0.5, = [5i. ,0.5 + 51 sin( =0
(7)
but the calmness condition of reformulatton is not satisfied under all of the global minimizers.
Figure I Iillustrates this fact by showing that the KKT score on the value function-based reformulation does not approach 0 as the distance to the optimal set decreases. This observation implies that the KKT conditions associated with the value function-based reformulation 2 do not constitute a set of necessary conditions for global minimizers for the nonconvex-PL. BLO problems. As a result, the KKT point of is unable to serve as the stationary point for the nonconvex- BLO problems.
Therefore, we adopt the gradient- reformulation 33 Unfortunately, is still possible that the standard CQs do not hold for some of the nonconvex-PP PL BLO problems associated with the gradient- based reformulation (3). To see this, let (x* yy) be the global minimizer of (3). By denoting
[[xx==""""" yy }], the generic CQ V)ng(=", the matrix concatenating the Hessian and Jacobian as VV (x=" yy"), V
conditions are instantiated in the gradient- based reformulation (3) by
LICQ, MFCQ: The rows of [V] Vyyg(a* """, Vi V vv")] are linearly independent; and, CRCQ: 3 neighborhood of (x" y/") ) such that V v), V (1, y)] is of constant rank.
If g( v) is strongly convex over y. then V ( y) is of full rank for any x and y. which ensures the LICQ. MFCQ and CRCQ of the gradient- -based reformulation (3). However, if g(z, y) merely satisfies the PL condition like Example none of the standard CQs hold, which is established next.
Lemma 2. Example 7 violates Slater condition, LICQ, MFCQ and CRCQ conditions of (
Remarkably, the following lemma demonstrates that the gradient- reformulation of the nonconvex-PLL BLO inherits the calmness condition.
Lemma 3 (Calmness of nonconvex-PL. BLO). If g(z.)) satisfies the PL condition and is smooth, and fzz -) is Lipschitz continuous, then (3 is calm at its global minimizer (x", yy)).
The Lipschitz smoothness of g(z, 3) and Lipschitz continuity of f(r, v) over y are standard in BLO 29 24 32 35
34 1 37]. In this sense, nonconvex-PP PL. BLO associated with the gradient-base reformulation (3) is naturally calm so that the KKT conditions are necessary conditions for its optimality [1]] A summary and illustration of our theory is shown in Figure
To benefit the algorithm design (Section 3.2)
we establish the necessary conditions of the optimality for nonconvex-Pe PL BLO by slightly modifying the KKT conditions of (3) in the next theorem.
Theorem 1 (Necessary condition in nonconvex-PL. BLO). go -) satisfies the PL condi- noncoueet tion and is smooth, and f(x, -) is Lipschitz continuous, then 3w + O such that
Rz ,y",, w² = V fx=" , + V V2yg(x" "ou"","") ,y")""1"" =0 =1==
(8a)
Ram Run(""11" ,w) 1 12 ,y¹ (VyJ("', ,v' + V Vegl<", "("""",""")))""""""")))))"")),"" 112=" ===0
(8b)
Ryy ,w²) :=9(>"; .v²) 9" (x")=0 =0
(8c)
hold at the global minimizer ,0'" of
This necessary condition is tight in the sense that is a generalization of stationary measures in the
existing literature for BLOO with LL problem exhibiting strongly convexity [9] [7 24 32]. PL. with singleton CRCQ (37), invertible Hessian and singleton solution (28) and Morse-Boo Bott functions (2] Thanks to
the inherent calmness of PL BLO, result climinates the CRCQ condition in 37 We next show
the connections of our results with other works.
Nonconves-strronll-coneee BLO or PL with invertible Hessian and singleton solution. As ((x) singleton and V (1, y) is always non-singular, the solution (8b) is uniquely given by
"² = 2 g(x S(x*)) V vzf(=" S(x*))
(9)
Therefore, the necessary condition in g is equivalent to
" S(x*)) = Vef(2", ",f((",S(x"") - 2 2 S(x*)) (V (Vzgll" ""<","(((""))) -1 vyf(z", =0
5

---

where the first equality is obtained by the implicit function theorem. Therefore, 8 recovers the necessary condition ff(=". .((*)) for nonconvex nonconvex-strrongyy strongly- BLO.
Nonconvex-Morse- BLO. Morse-Boo Bott functions are special cases of PL functions 22.. this case, V Vzg y) can be singular so that (8b) may have infinite many solutions, which are given by
W = - - mugl"" .r vyf(x" + Ker (er(V ",,=((==")))
V
According to (2] Proposition 6]. for any y E S(x*), Vzgg(=" y²) Ran V Vyg(2" ))), which orthogonal to Ker( Ver Vyggg .y")). As result, although the solution (8b) is not unique, all of possible solutions yield the unique left hand side value of (8a). i.c. Vw* E W
V2 Vayg(a' yy (')"" = - Vigg( ,9") (V Vogl ,v)) vuf("",'")
Plugging into 8a we arrive at
( ,2) V Lygla" v²) (V ( """(x"""")))) ,2)) VyJ "y](x",")) = and Vng(>" y2)
== -V")
where b(xx,,") is the same as the degenerated implicit differentiation in 2
Based on (8) we can define the e- stationary point of the original BLO problem as follows.
Definition 3 (e- stationary point). A point (I, 9) is called e-stationary point of if 2 such that (Z, G. w) S e, R. (1, y. w) S e and R2 ( 1) S. E.
2.3 The importance of necessary conditions for BLO without additional CQs
Next, we emphasize the importance of deriving the necessary condition for the optimality of the nonconvex-PL. BLO without additional CQs.
Gradien-hasc snouh- auo
Calmness
On the one hand, the necessary condition for the optimality of BLO is fundamental to the algorithm design and has been investigated for a long time in the optimization community 770 71 15 [7]. but has not yet been fully understood [69] One of the main challenges is that traditional CQs for constrained op- timization hard check do not hold in BLO As a result, the development of mild CQs and the identification of BLO classes that inherently satisfy these CQs are considered significant contribu- Among those,
Grudirnt-haved PL-BLO
redormmlation
LICU
CRCO
16 (00.
PL-BLO
tions to the field 770 71 15 17
69),
Figure 2: Illustration of our theory: relations of different CQs and BLO reformulation (2) and (3). Slater condition fails for both BLO reformulations so we do not include it.
the calmness condition is the weakest CQ 11].
On the other hand, recent BLO applications in ma- chine learning often involve nonconvex LLI problems, the necessary condition for the solution of which is far less explored in either optimization or machine learning community. In the optimization community, most works focus on proving linear bilevel and sequential min-max optimization satisfy certain CQs [70, [6]. In the machine learning community. works on nonconvex-non nonoonvvxxx BLO either relax the LL problem that introduces error 43 57 or impose assumptions that are hard to verify in practice such as CRCQ (37 Morse-Bott condition 2 To the best of our knowledge, we are the first to propose the necessary condition for the optimality of class of nonconvex nonconvex BLO problems with checkable assumptions. Moreover, algorithms in constrained optimization are always CQ-dependent, e.g. the convergence of an algorithm depends on whether a particular CQ condition is satisfied. As prove that standard CQs invalid for nonconvex-PL BLO, several existing BLOO may become theoretically less grounded 37 28
An Alternating Method for Bilevel Problems under the PL Condition

---

In this section, we introduce our Generalized ALter- nating mEthod for bilevel opTimization with con- vex L.I. problem, GALET for short, and then eluci- date its relations with the existing algorithms.
Algorithm 1 GALET for Donconvex-PL. BLO
1: Initialization {x" .v), stepsizes 1,
2:
for 0 K - do
3:
for n 0 to N 1 do
> y = yd
3.1 Algorithm development
4:
update y A by
To attain the e-stationary point of [ in the sense of Definition we alternately update x and y to re- duce computational costs. At iteration k, we update g by N-step GD on g(x*, 2) with yh and y y as
5:
end for
M+1 k.
N
6:
for
T do
7:
update w by 8: end for
12b
w R.T
y
w
9: calculate dt by 13
10: update - x od
gntt1 k.n WVg(v mn
(10)
end for
While setting N = 1 is possible, we retain N for generality. We then update via the fixed-point equation derived from (8b) and employ V (rg(x, y) (V (Vy (z, + V yyg(a, y)w) as the increment for This increment can be viewed as the gradient of [(z, y, w) defined
((,,,, w) = 1 Vuf(z,
v) (x
v ( w)ll
(11)
which is quadratic w.r.t. w, given x* and 1/²+1
However, unlike the LL objective ((, y). the objective (xx, y, w) is Lipschitz smooth with respect to and y only for bounded w, which makes it difficult to control the change of solution
(I1) under
different x and y. Hence, we update wh via T-seep GD on with w*.0 = 0 and w w... as
R1141 = whit pecti
(12a)
die == V Sagg 1 (V (a*, +)+ + V Vyglaa // * ()))).
(12b)
After obtaining the updated y and wh1 we update x² by the fixed point equation of (8a) as
x++1= x ad with dh vzf(x* xx*+)) + V 22 . "/*+)w**+1
(13)
We summarize our algorithm in Algorithm We choose w. 0 for simplicity, but w - w + is also valid. Same convergence statement can hold since the boundedness and Lipschitz continuity of limit points limy-+00 uA are still guaranteed. From the algorithm perspective. [2] shares similarities with us. However, without recognizing the property of GD converging to the minimal norm solution [52], Arbel and Mairal 2 introduces an additional Hessian into the objective (T., resulting in the calculation of fourth-order Hessian operation, which is more complex than GALET
3.2 Relation with algorithms in nonconver-strongly-oowe BLO
We explain the relation between GALET and methods in the noncomvex-strongly--oowee BLO. First, if g(z, 3) is strongly convex in y, minimizing L(z, y, w) over w yields the unique solution w (x, y) = (Vgg(1 y)) (zf(x,y) y). This means that optimizing L(r. (rr, y, w) corresponds to implicit differentiation in the the optimization of w as the shadow implicit gradient level.
-wrroonyyx--stsogyyy-oyo convex BLO 9
27
24 32 Therefore, refer
0.01
On the other hand, if V2 1z problem over w is equivalent to
(z, y) is positive definite, the
Optimality gap
GALET -Soongly-oovvex method
min {2 w Vigl(,, v)w + T V.f((,))
0.005
(14)
which can be verified by their first-order necessary condi- tions. Thus, one can update w by GD on (14) via
0
10
20
30
40
jk.l = (x ) + V (a k+ ++
(15)
Iteration
Figure 3: The w update in 15 for
Note that the increment in (15) eliminates the extra Hes- manconvee-strongly-come
does not
sian in (2b)) and recovers the updates for nonconvex- work well for nonconvex-PP BLO.
strongly-conee
BLO in B5 27 B2 9 66). Actually, the additional Hessian in (2b) is inevitable for
an algorithm to find the stationary point of the nonconvex-PLe BLO. Figure 3 shows the comparative results of our algorithm with the nonconvex-stronm strneee-sttoogyy-conee BLO algorithm using (1) instead of
(12b) on Example [] where the global optimality is measured by the distance to the global optimal
set (7) with the explicit form stated in (46). We observe that the update (15) fails to find the global
optimizer of the example in Lemma so that the additional Hessian in 12b is unavoidable.
7

---

4 Convergence Analysis
In this section, we provide the convergence rate analysis under convex PL LL settings. We first introduce the assumptions and the challenges. Next, we analyze the descent property and drifting error in LL., the bias of w*1 to the optimal solution of min L(**, y w) and the descent property of UL. Finally, we define a new Lyapunov function and state the iteration complexity of GALET.
Assumption (Lipschitz continuity). Assume that f, Vg and V g are Lipschitz continuous with y,s. f.11 and & g. respectively. Additionally, we assume [z. y) is f.u-Lipschii continuous over y- Assumption 2 (Landscape of L.L. objective). Assume that g(x, y) is pg pg y. Moreover, let og > 0 be the lower-bound of the positive singular values of Hessian, i.e. 0g = inf min (V? Vyyg((z y))}. Remark 1. By definition, singular values are always nonnegative. We use dg denote the lower bound of the non-zero singular values of V yz, y). Assumption 2 means that the non-zero singular values are bounded away from 0 on the entire domain. Given Assumption T that the Hessian is globally Lipschitz, they together potentially rule out negative eigenvalues of the Hessian. However, different from strong convexity (9 27 24 32,228), this assumption still permits V g2, y) to possess zero cigenvalues and includes BLO problems of multiple LL solutions. As example, this includes the loss of the (overparameterizee) generalized linear model [52]. In addition, Assumption 2 is needed only in the convergence rate analysis along the optimization path ensure the sequence (w")
(x,
is well-behaved. Therefore, it is possible to narrow down either the Hessian Lipschitz condition or the lower bound of singular values to a bounded region, when the local optimal sets are bounded.
Challenges of analyzing GALET. The absence of strong convexity of the LL brings challenges to characterize the convergence of GALET. To see this, recall that in recent analysis of BLO such as ()) when gxx, -) is strongly convex, the minimizer LL is unique. Therefore, to quantify the convergence of Algorithm [ one can use the Lyapunov function V == f(x ((x*)) - +Iy - S(x*) where f(=*, (xx*)) and lly* - |l are used to account for the UL. descent and ILL error caused by the alternating update and the inexactness, respectively. However, Vsc is not well-defined when S(z) is not unique. Therefore, it is necessary to seek for a new Lyapunov function.
4.1 Descent of each sequence in GALET
A nature alternative of SSx*) under the PL condition is the LL optimality residual (2*, y²) the evolution of which between two steps can be quantified by
(x y ( R.,, (a . y²) R,, (x
k+1 R2, +*
+ R2 (a 111 Rr, (x", (16)
where the first term characterizes the drifting LL optimality gap after updating x, and the second term shows the descent amount by one-step GD on y. Unlike the strongly convex case where S(x) is Lipschitz continuous, both g (z) and g(x, y) are not Lipschitz continuous, so we cannot directly bound the the first difference term in (T by the drifting of update ||a*+1 x*1 Owing to the opposite sign of g(x. y) and g" (z), we bound the first term in (T)) by the smoothness of g(r, y) and g" (x)) The second term in (16) can be easily bounded by the fact that running GD on PL function ensures the contraction of function value distance.
Lemma 4. Under Assumption
2
let h11 be the point generated by (10) given at and the stepsize
3 < Eg.1 Then it holds that
Ry(a" , 1 S (1 - 8pog) ( (2"""""²")
(17a)
R2 t+ (4t11121) ) (1 (1+ om amiea
R2 Re ,y + +
/abg.1
+ f..1 8.g
L a² |dtt
(17b)
Bg
2m
2
where I.g = 11 + (2,1 and = (1) is constant that will be chosen in the final theorem.
Rearranging the terms in 17ah and using the fact that g(ar, y) 2 g" (xx), the second term in (6) can
be upper bounded by negative term and O (132). Adding (17a) and (7b), letting o, B is the same order and choosing 7/1 (1) properly yield
(18) When we choose in large enough, the second term will be dominated by the negative term -aa))ld given by the UL descent, so it will be canceled out.
Ry (2* y b (x* x²)
(aa) w O(a)]la113
8

---

20-
3000
3000
3500
5. -20
00
500 PT
X-5.0
2000
1500
-10
1000
500
-0
-00 20
20
70
60
211
40 60
(a) UL level: a
(b) Shadow implicit gradient level: T,
(c) LL level: N,
Figure 4: Trajectories of GALET under different choices of the parameters in UL., LM and LL level for Example The æ-axis denotes the value of x* the y-axis represents the first coordinates of y* The color of the point shows the optimality gap measured by (46) with the color bar shown right. The yellow square the starting point and the red star represent the optimal (x","") ,y")
With the iterates generated by GD initialized at O converging to the minimal norm solution of the least squares problem [52], we can characterize the drifting error of using the Lipschitz continuity of its minimal norm solution. The following lemma characterizes the error of w+++ to the minimal-nowe
solution of the shadow implicit gradient level w (I., y) == (V (09 y))² (zf(x,
Lemma 5. Under Assumption
7 2 we let *+* denote the iterate generated by (2a given (a y
and w O, and denote by R+
w wi"x,, * }||- If we choose the stepsize P I Pg then
the shadow implicit gradient error can be bounded by b3 < 2(1 pog)) T f./
Instead of using f (xx S(x)) which is ill- ill-posed, we integrate the increment of x to get F(x, y w) f(x, y) + w V Vag(r, y)- Then by plugging the optimal minimal norm solution wi (ar, v), we choose F(a", y²: suf((e (x* )) as the counterpart of fx* .S(x")) in V sc- We can quantify its difference between two adjacent steps by the smoothness of F(x, 22 w).
Lemma 6. Under Assumption
2 by choosing S min Ahp
Bm 21
one has
F(r
(og,t,uutt - F(**, ; wf; (x (=*,1/ ,²,)
al 9.1 02
Blmlg 2 e 9.1 + 28 1.
LF 3
< a 1
Ry(x".
(19)
Hg
where Lu is the constant defined in Appendix and constant 1/2 will be chosen the final theorem.
4.2 A Lyapunov function
Based on 18 and 19
we can define a new Lyapunov function for the nonconvex-Pe BLO as
V Fa* ( :h: (x* )² )) + (x* .y²)
(20)
where c is chosen to balance the coefficient of the term R, w²) and ||d 1| such that
wk+1_ v < ((a)]la O(a)R o(()) ..")
O(a)6)
(21)
Telescoping to 21 results in the convergence of both || |d and (x (*) By definition, ||b]
Rr, / k))+), so the convergence of R2 (x. y² w*) is implied by the Lipschitz continuity of increments and the fact that * y*11, 1+1 w/1l - Likewise, the convergence of (x n² w*) can be established by recognizing that 62 is sufficiently small when selecting large T. ensuring that Ryd (x* *+1 w*)1) is also small, and consequently, (x* 1 w*). The convergence results of GALET can be formally stated as follows.
Theorem 2. Under Assumption 2 choosing a, p. 3 O(1) with some proper constants and N = O (log( K)) then i holds that
Ralæ .9 =====
Re w =0
1
Σ
R =0
K
K
K
K
K

---

From Definition one need OKT)) O log(c
GALET (911
1.3
V-DUOD
SiiloeRRy 3RRRAIE
IAPETCMM GALET
((E iterations in average to achieve e-stationary point of the BLO problem ① The next re- mark shows that this complexity is optimal.
20"
Text
L.0
20"
0.5
10
500
1000
1500 Beition
2000
2500
30
1000
2000
3000
Remark 2 (Lower bound). The iteration complexity ( in Theorem Z is optimal terms of up to logarithmic factors. This because when f(x, y) is inde- pendent of y and g(r. y) = 0, Assumptions
Derotioe
Figure 5: Convergence results of GALET of hyper-cleaning task on MNIST dataset. Left: test loss v.s. iteration. Right: stationary measure v.s. iteration (the y-axis is in the logarithmic scale).
I and reduce to the smoothness assumption of f on and thus the O(c lower bound of nonconvex and smooth minimization [6] also applies to BLO under Assumptions and
5 Preliminary Simulations and Conclusions
The goal of our simulations to validate our theories and the performance of GALET on actual learning applications. The experimental setting and parameter choices are included in the Appendix.
Our stationary measure is necessary condition of the global optimality. As shown in Figure | GALET approaches the global optimal set of Example T and our stationary measure also converges to 0, while the value-function based KKT score does not.
UL stepsize is the most sensitive parameter in our algorithm. As shown in Figure 4 varying UL stepsize a leads to different trajectories of GALET, while varying parameters in the LL and shadow implicit gradient level only cause small perturbations. This means that is the most sensitive parameter. The fact that GALET is robust to small values of T and makes it computationally appealing for practical applications, eliminating the need tune them extensively. This phenomenon also occurs in the hyper-cleaning task.
Our method converges fast on the actual machine learning application. We compare GALET with BOME B7. IAPTT-GM 4 and V-PBGD [57] the hyper-cleaning task on the MNIST dataset. As shown in Figure 5] GALET converges faster than other methods and the convergence rate of GALET is ()) which matches Theorem 2 Table Shble2ssows that the test accuracy of GALET is comparable other methods.
Conclusions and limitations. In this paper, study BLO with lower-level objectives satisfying the PL condition. We first establish the stationary measure for nonconvex- PL BLO without additional CQs and then propose an alternating op- timization algorithm that generalizes the existing alternating (implicit) gradient- gradient-based algorithms for bilevel problems with strongly convex lower-level objective. Our algorithm termed GALET achieves the (le- iteration complexity for BLO with convex PI. L.I problems. Numerical experiments are provided to verify our theories.
Method
Accuracy
BOME
88.20
IAPTT-GM
90.13
V-PBGD
90.24
GALET 90.20
Table 2: Comparison of the test accuracy.
One potential limitation is that we only consider the deterministic BLO problem and require second- order information, and it is unclear whether our analysis can be generalized handle the stochastic case and whether the same iteration complexity can be guaranteed with full first-order information.
Another limitation Assumption 2 This stipulates that the singular value of the LL Hessian must be bounded away from 0 to ensure the stability of the (w*}.
Acknowledgement
The work of Q. Xiao and Chen was supported by National Science Foundation MoDL-SCALE project 2134168, the RPI-IBM Artificial Intelligence Research Collaboration (AIRC) and Amazon Research Award. We also thank anonymous reviewers and area chair for their insightful feedback and constructive suggestions, which are instrumental in enhancing the clarity and quality of our paper.
10

---

References
[1] Michael Arbel and Julien Mairal. Amortized implicit diffcrentiation for stochastic bilevel optimization. In Proc. International Conference Learning Representations, virtual, 2022.
[2] Michael Arbel and Julien Mairal. Non-convex bilevel games with critical point selection maps. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, 2022.
[3] Sanjeev Arora, Simon Du, Sham Kakade, Yuping Luo, and Nikunj Saunshi. Provable representa- tion learning for imitation learning via bi-level optimization. In Proc. International Conference on Machine Learning, virtual, 2020.
[4] Zalán Borsos, Mojmír Mutny, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. In Proc. Advances in Neural Information Processing Systems, virtual, 2020.
[5] Jerome Bracken and James McGill. Mathematical programs with optimization problems in the constraints. Operations Research, 21(1):37-44, 1973.
[6] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1-2):11-120, 2020.
[7] Lesi Chen, Jing Xu, and Jingzhao Zhang. On bilevel optimization without lower-level strong convexity. arXiv preprint arXiv:2301.00711 2023.
[8] Lisha Chen, Sharu Theresa Jose, Ivana Nikoloska, Sangwoo Park, Tianyi Chen, and Osvaldo Simeone. Learning with limited samples: Meta-learning and applications to communication systems. Foundations and Trends@ in Signal Processing, 17(2):99-008, 2023.
[9] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Proc. Advances Neural Information Processing Systems, virtual, 2021.
[10] Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A single-timescal method for stochastic bilevel optimization. In Proc. International Conference on Artificial Intelligence and Statistics, virtual, 2022.
[11] Frank H Clarke. Optimization and nonsmooth analysis. SIAM, 1990.
[12] Caroline Crockett and Jeffrey Fessler. Bilevel methods for image reconstruction. Foundations and Trends@ in Signal Processing, 15(2-3):121-255 2022.
[13] Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. framework for bilevel optimization that enables stochastic and global variance reduction algorithms. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, 2022.
[14] Stephan Dempe. Foundations of bilevel programming. Springer Science & Business Media, 2002.
[15] Stephan Dempe and Alain B Zemkoho. On the caai--uuuunukkkce reformulation of the bilevel optimization problem. Nonlinear Analysis: Theory, Methods & Applications, 1523):1202-1218, 2012.
[16] Stephan Dempe and Alain Zemkoho. The bilevel programming problem: reformulations, constraint qualifications and optimality conditions. Mathematical Programming, 138(1):447- 473, 2013.
[17] Stephan Dempe Vyatcheslav V Kalashnikov, and Nataliya Kalashnykova. Optimality condi- tions for bilevel programming problems. Optimization with Multivalued Mappings: Theory, Applications, and Algorithms,, pages 3-28, 2006.
[18] Joydeep Dutta and Stephan Dempe. Bilevel programming with convex lower level problems. Optimization with Multivalued Mappings: Theory, Applications, and Algorithms, pages 51-71, 2006.
11

---

[19] Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In Proc. International Conference on Machine Learning, Stockholm, Sweden, 2018.
[20] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. In Proc. International Conference on Machine Learning, Sydney, Australia, 2017.
[21] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-basedd hyperparameter optimization. In Proc. International Conference Machine Learning, Sydney, Australia, 2017.
[22] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimilano Pontil. Bilevel programning for hyperparameter optimization and meta-learning. In Proc. International Conference Machine Learning. Stockholm, Sweden, 2018.
[23] Lucy Gao, Jane Ye, Haian Yin, Shangzhi Zeng, and Jin Zhang. Value function based difference- of-convex algorithm for bilevel byperparameter selection problems. In Proc. International Conference on Machine Learning, Baltimore, MD, 2022.
[24] Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv: 00...100.2222.. 2018.
[25] Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complexity of hypergradient computation. In Proc. International Conference Machine Learning, virtual, 2020.
[26] Ryuichiro Hataya and Makoto Yamada. Nyström method for accurate and scalable implicit differentiation. In Proc. International Conference on Artificial Intelligence and Statistics, Valencia, Spain, 2023.
[27] Mingyi Hong. Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor- critic. SIAM Journal on Optimization, 33(1):147-180, 2023.
[28] Feihu Huang. On momentum- gradient methods for bilevel optimization with nonconvex lower-level. arXiv preprini arXiv:2303.0399 2023.
[29] M James. The generalised inverse. The Mathematical Gazette, 62(420)) 1978.
[30] Robert Janin. Directional derivative of the marginal function in nonlinear programming. Springer, 1984.
[31] Robert G Jeroslow. The polynomial hierarchy and a simple model for competitive analysis. Mathematical programminng (2(2):146-166 1985.
[32] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In Proc. International Conference on Machine Learning, virtual, 2021.
[33] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewicz condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Riva del Garda, Italy, 2016.
[34] Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A npar-optimal algorithm for stochastic bilevel optimization via double-momentum. In Proc. Advances in Neural Information Processing Systems, virtual, 2021.
[35] Junyi Li, Bin Gu, and Heng Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. In Proc. Association for the Advancement of Artificial Intelligence, virtual, 2022.
[36] Gui-Hua Lin, Mengwei Xu, and Jane J Ye. On solving simple bilevel programs with nonconvex lower level program. Mathematical Programming, 144(1-2):2773305 2014.
12

---

[37] Bo Liu, Mao Ye, Stephen Wright, Peter Stone, et al. Bome! bilevel optimization made easy: A simple first-order approach. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, 2022.
[38] Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85-116, 2022.
[39] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In Proc. International Conference Learning Representations, New Orleans, LA, 2019.
[40] Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. generic first- order algorithmic framework for bi-level programming beyond lower-level singleton. In Proc. International Conference on Machine Learning. virtual, 2020.
[41] Risheng Liu, Jiaxin Gao, Jin Zhang, Deyu Meng, and Zhouchen Lin. Investigating bi-level optimization for learning and vision from unified perspective: A survey and beyond. IEEE Transactions on Pullern Analysis and Machine Intelligence, 2021.
[42] Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A value-function-basee interior-point method for non-convex bi-level optimization. In Pruc. International Conference on Machine Learning, pages 6882-6892, virtual, 2021.
[43] Risheng Liu, Yaohua Liu, Shangzhi Zeng, and Jin Zhang. Towards gradient-based bilevel optimization with non-convex followers and beyond. Proc. Advances in Neural Information Processing Systems, 2021.
[44] Risheng Liu, Xuan Liu, Wei Yao, Shangzhi Zeng, and Jin Zhang. Towards extremely fast bilevel optimization with self-governed convergence guarantees. arXiv preprint arXiv:2205.1005. 2022.
[45] Risheng Liu, Yaohua Liu, Wei Yao, Shangzhi Zeng. and Jin Zhang. Averaged method of multipliers for bi-level optimization without lower-level strong convexity, In Proc. International Conference Machine Learning, Honolulu, HI, 2023.
[46] Songtao Lu, Siliang Zeng, Xiaodong Cui, Mark Squillante, Lior Horesh, Brian Kingsbury, Jia Liu, and Mingyi Hong. A stochastic linearized augmented lagrangian method for decentralized bilevel optimization. Proc. Advances in Neural Information Processing Systems, New Orleans, LA, 2022.
[47] Zhaosong Lu and Sanyou Mei. First-order penalty methods for bilevel optimization. arXiv preprint wxXv:2301.007166 2023.
[48] Zhi-Quan Luo, Jong-Shi Pang, and Daniel Ralph. Mathematical Programs with Equilibrium Constraints. Cambridge University Press, 1996.
[49] Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-based hyperparameter opti- mization through reversible learning. In Proc. International Conference on Machine Learning, Lille, France, 2015.
[50] Akshay Mchra and Jihun Hamm. Penalty method for inversion-fres -free deep bilevel optimization. In Asian Conference on Machine Learning, virtual, 2021.
[51] Maher Nouiched, Maziar Sanjabi. Tianjian Huang, Jason D Lec, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. In Proc. Advances in Neural Information Processing Systems, Vancouver, Canada, 2019.
[52] Samet Oymak and Mahdi Soltanolkotabi. Overparameterizze nonlinear learning: Gradient descent takes the shortest path? In Proc. International Conference on Machine Learning, Long Beach, CA, 2019.
[53] Barak Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 6(1): 147-160, 1994.
13

---

[54] Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In Proc. Interna- tional Conference on Machine Learning New York City, NY, 2016.
[55] Quang Pham, Chenghao Liu, Doyen Sahoo, and HOI Steven. Contextual transformation networks for online continual learning. In Proc. International Conference on Learning Repre- sentations, virtual, 2021.
[56] Shoham Sabach and Shimrit Shtemn. first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640-66) 660, 2017.
[57] Han Shen, Quan Xiao, and Tianyi Chen. On penalty-based bilevel gradient descent method. arXiv preprint:23022055 05 185, 2023.
[58] Daouda Sow, Kaiyi Ji, Ziwei Guan, and Yingbin Liang- constrained optimization approach to bilevel optimization with multiple inner minima. arXiv preprint 2rXiv:2203.0/ 2022.
[59] Bradly Stadie, Lunjun Zhang, and Jimmy Ba. Learning intrinsic rewards as a bi-level optimiza- tion problem. In Conference on Uncertainty in Artificial Intelligence, virtual, 2020.
[60] Gilbert W Stewart. On the perturbation of pscudo-inverses, projections and linear least squares problems. SIAM review, 19(4):634-66) 1977.
[61] Ju Sun, Qing Qu, and John Wright. geometric analysis of phase retrieval. Foundations of Computational Mathematics, 18:1 111-11111191 1198, 2018.
[62] Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT press. 2018.
[63] Davoud Atace Tarzanagh, Mingchen Li, Christos Thrampoulidis, and Samet Oymak. FEDNEST: Federated bilevel, minimax, and compositional optimization. In Proc. International Conference on Machine Learning. Baltimore, MD, 2022.
[64] Ioannis Tsaknakis, Prashant Khanduri, and Mingyi Hong. An implicit gradient-type method for linearly constrained bilevel problems. In IEEE International Conference on Acoustics, Speech and Signal Processing, Singapore, 2022.
[65] Paul Vicol, Jonathan Lorraine, Fabian Pedregosa, David Duvenaud, and Roger B Grosse. On implicit bias in overparameterized bilevel optimization. In Proc. International Conference on Machine Learning, Baltimore, MD, 2022.
[66] Quan Xiao, Han Shen, Wotao Yin, and Tianyi Chen. Alternating implicit projected sgd and efficient variants for equality-constaineed bilevel optimization. In Proc. International
Conference Artificial Intelligence and Statistics, Valencia, Spain, 2023.
[67] Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. In Proc. Advances in Neural Information Processing Systems, virtual, 2021.
[68] Shuoguang Yang. Xuezhou Zhang, and Mengdi Wang. Decentralized gossip based stochastic bilevel optimization over communication networks. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, 2022.
[69] Jane J Ye. Constraint qualifications and optimality conditions in bilevel optimization. Bilevel Optimization: Advances and Next Challenges, pages 227-251, 2020.
[70] Jane J Ye and Daoli Zhu. Optimality conditions for bilevel programming problems. Optimization, 33(1):9-27, 1995.
[71] Jane J Ye and Daoli Zhu. New necessary optimality conditions for bilevel programs by combining the MPEC and value function approaches. SIAM Journal on Optimization, 20(4): 1 1885-1905, 2010.
[72] Jane Ye, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. Difference of convex algorithms for bilevel programs with applications in hyperparameter selection. Mathematical Programming, pages 1-34, 2022.
[73] 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 Proc. International Conference on Machine Learning, Baltimore, MD, 2022.
14

---

Supplementary Material for "A Generalized Alternating Method for Bilevel Optimization under the Polyak-Lojasiewice Condition"
Table of Contents
Auxiliary lemmas
15
B Proof of Stationary Metric
16
B.1
Theorem 3 and proof
B.2 Proof of Lemmal
16
B.3 Proof of Lemma
17
Proof Lemma
B.5
Proof Theorem
18
Proof of Lower-level Error
18
Proof Shadow Implicit Gradient Error
D.1 Propositions of [xx, y, w) and L
19
D.2 Proof of Lemma
19
E Proof of Upper-level Error
E.1 Propositions of wi (z.
19
E.2 Proof of Lemma
20
F Proof Overall Descent of Lyapunov Function
23
Additional Experiments and Details
25
A Auxiliary lemmas
We use || || to the Euclidean norm and be the metric space with the Euclidean distance metric. Let X be point and A X be set, we define the distance of a and A as d(x, A) inf || all A).
The following lemma relates the PL condition the error bound (EB) and the quadratic growth (QG) condition.
Lemma 7 (33 Theorem 2)). If (g(x,,) u) is -Lipschit smooth and PL in with Pa. then it satisfies the EB condition with Hg. i.e.
Vgg(2, y)ll 2 Hyd(y, S(x)).
(22)
Moreover: it also satisfies the QG condition with Pg. i.e.
g(x,y) - g" (x) > Mg d(y, S(z))²
(23)
2
Conversely, if g( 1) is -Lipsshch smooth and satisfies EB with pg, then it is PL in with pg/ g
The following lemma shows that the calmness condition ensures the KKT conditions hold the global minimizer.
.y) be the global minimzer of a constrained optimization problem and assume that this problem is calm (x" .y"). Then the KKT conditions hold at
Proposition (III) Proposition 6.4.4).. Let (x",y")
The following lemma gives the gradient of the value function. Lemma (51) Lemma A.5l). Under Assumption 2 and assuming g(æ, v) is lg.1 Lipschitz smooth, g" (x) is differentiable with the gradient
Vg" (x) Vag(a,)) v), Vy E S(x). Moreover, 9" (x) is Li smooth with Lg == (1 + 22,g/)
15

---

B Proof of Stationary Metric
B.1 Theorem and its proof
Theorem 3. For nonconvex-PL. BLO, A point (a","" is a local (resp. global) optimal solution of
if and only if it local (resp. global) optimal solution of 33. The same argument holds for 22
Proof. First, we prove the equivalence of ① and reformulation
According to PL. condition,
V (a, v) 2 My (g y) -9 -²(x)))
Therefore, if V (r, y) 0, it holds that g(z, y) g" (x) which yields g(z, y) g" (x)). On the other hand, if (z. y) = g" (x). the first order necessary condition says Vyg(z, v) = 0. As a consequence, we know that
V p
+ g(r, v) = 9" (x) + S(z).
In this way, for any local (resp. global) optimal solution (x",0") of G3. there exists a neighborhood U such that for any (x..)) U with V Vyg(z, v) O, it holds that f(=",'" S f(x, y)- Since V (z, v) = 0 + E S(x), we know (x",)") is also a local (resp. global) optimal solution of (2). The reverse holds true for the same reason.
The equivalence of Problem and reformulation 2 can be proven in the same way.
B.2 Proof of Lemmal
First, the gradient of g(z y) can be calculated by
V Vog(r, y) = (rr + yn sin(w)))(1, - cos(
Since [[[L, [[1,-cos(( cos( (22) and g" (x)
know
V V 12 (2 y1 cos (g(x,))
(()).
Thus g(x, y) satisfies the PL condition with Hy = 1. Next, the LL problem in Example is equal to + yı sin(y2) 0 so that the BLO of
1
min f(x v) = x² + sin())), s.t. arg min g(,, v) マ (or + 2ı sin()))) 2.8
(24)
is equivalent to
min
[xx v) x² + +11 sin(w2), s.t. 91 sin(y2) = 0. 2.y
so that solving the BLO amounts to solving min(2² - =} with the constraint x + 91 sin(yy) 0. Therefore, the global minimizers of BLO
According to the constraint, we know y1 sin(y2)
are those points (I*,y") where x* 0.5 and y" (vf v5) with vf sin(y)) + 0.5 0.
On the other hand, reformulating
using 2 yields
min f(x, 3) = + 1/1 sin( s.t. g(x,)) g (x) z.y
(25)
the calmness holds for 25 then according to Proposition
[ there exists w* of such that
vaf(x", (ff(("")) + (V .y)) - Vag" (x (x"))" = 0.
(26)
However, for any w" 00, 0. and
Vaf(x" . V=g(=",'') Vag" (x"))"" 2x + (x" + + sin(v")) = 2r- =1
which contradicts 26 Therefore, the calmness condition fails for (24) with reformulation
16

---

Figure 6: Landscape of g(1, y) Example 1 and the red line denotes 5(1). Different choices of only translate the plot and share the same landscape.
B.3 Proof of Lemma 2
Figure 6 shows the landscape g(x, y) when x and the red line denotes its solution set. The figure reveals that g(z, y) is nonconvex in y with multiple LL solutions, and the solution set is closed but nonconvex.
Proof. It is easy to see that S(x) = {y x 3 = sin()))) and (x) = O. First, the Slater condition is invalid because Vyg(zz v) = 0 is an equality constraint. Next, we can compute the Hessian and Jacobian of g(xz, v) as (32) V ( = cos(12) cos2(y2) + (i (r + v1 sin(v2))
V Veng(z = cos(222
Since V (z. y) coincides with the first column of ( y). we know that
(ank([V? y),
V (zng(x,)]] = rank (ay v)),
For any global minimizer (x", of the bilevel problem, it should satisfy the LL optimality, i.e. y" S(x"), and thus xx + vi sin(y)) O. In this way, we have
-oo(yý)
V2yg(2' v²)
cos(
cos2(y5))
Thus, rank V Vn ,y")) = 1 2 which contradicts the LICQ and MFCQ conditions.
Moreover, follows that rank(V) ( u)) = and only
det det ( y)) sin(
sin = 0.
Thus, the CRCQ condition is equivalent that there exists neighborhood of (a ,y") such that either sin(y2) = 0 or I + and search such neighborhood for first. It is clear that finding
(i2 = O holds for any (x. y) in that neighborhood. We fix x"
of y such that sin(y2) impossible due to the nature of sin function. On the other hand, x²' + yı sin(g2) = 0 is equivalent in neighborhood y also unrealistic since otherwise, the solution set S(x*) should be open, which contradicts that S(x) is closed. Thus, (6) violates CRCQ condition.
is
S(x*) so that making + y1 sin
B.4 Proof of Lemma 3
Assume the PL and the Lipschitz smoothness constants of 9(x, :) are My and fg.1, and the Lipschitz continuity constant fxx is fy.-- Consider Vq. and v(x', ((,,,')),n s.t. Vag(z', 1/) q = 0, then letting Vy Projster (v') and according to Lemma one has
||و|| | ya s')l Mally/ Ugll
Since (x", v²) solves 3) and (x', yn) is also feasible to 33. one has f(x", ,1") S f('',,)) Thus,
8f.0 ||q|]-
f( v f(= ."""""")= f(' w') f(a', va) -.ollll vall 2
1g
This justifies the calmness definition in with M == Fro 14
17

---

B.5
Proof of Theorem 1
Proof. By applying Lemma B and Proposition 1 we know that KKT conditions necessary, i...
Vaf("" .y" + va Veyg(o" y '''""" uff(2" "2" + v pyg("" " v'""" =
(27a)
(27b)
vug(2", yy" = O.
(27c)
On the other hand, since
V Vug("", yy) = 0 + g( v²) - 9 (x") = 0 V fzf yy) + V "0g(=", .v )w" = 0 V V v) (Vyf(=", + + V ( = (=0=="
we arrive at the conclusion.
C Proof of Lower-level Error
In this section, we give the proof of Lemma 4 To prove 17a in Lemma 4 by the smoothness of g(x, y) and the update rule, we have
g(a". 1 S g(x", y =r) + (V Vog(a, y " kntt ymn + la.l
11 Aigtitt - 112
2
< g(x", , -.²) - B|| Diyggg" )1 B2
IV Weglet w
2
g(a ,0 (.r) 197--13 -s--8 [.
Vugla" y1
g(a min (2,3 -
(.g.)) -833-Beap
My (im), - g" (x*))
(28)
where (a) results from Assumption] 2 Then subtracting I (at) from both sides of 28
we get
g(ah ) (x*)
S [1 (2 f (g(a*, -/m)) 9" (x*)x)
By plugging in 3 < E..1 and applying N times, we get the conclusion in (7ab.
To prove (17b). we decompose the error by
g(a (artt,yhtl ) g" (x "o(a",y**t1 9" (2*1) + [g(aht1 ,gttt) - g" (2(*tt1)) (g(a*, - (x*))]] (29)
To obtain the upper bound of Jn, we first notice that g(x, g(a, +1) g²(x) is (fg,1 + Lg) -iipshhizzz smooth over x according to the smoothness of g(x, )h+ in Assumption | and g (axx) from Lemma g Therefore, we have
J1 $ (V=g(z* (T) Vg" (2*) ++1 24) + lg, + Lo
x+
|| - 101
2
a a (Z2((z x Vg (x*), d + fg. + Tig
a²
||at
S a Vng(2* , (t)) Vgg (x
| + fg.1
+
Lg
0k ||
2
(2 alg,ndly k+| S((x ((ad)) + fg.1
Lg a² 1/12
2
2 am
2 Eg. d 1 ,((a)))2 + alg,1
Eg. + Lg
||//|12
+
a² a3
27/1
2
W am (g(Ø*) b+1) g" (x**)) + af g.1 ||
f Pg
lg.1 + Lg a2 u
+
(30)
2m
where (a) derived from Lipschitz continuity of V gx, y) and Lemma (b) comes from Cauchy- Swartz incquality, (c) is due to Lemma 7 Plugging 30 into 29) yields the conclusion in (1b).
18

---

D Proof of Shadow Implicit Gradient Error
We first present properties of [(x, y, w) and then prove Lemma We define
L (r, v) - -min L(,, M, w), W(x, y) = arg min ((, w)
w
D.1 Propositions of [(x, y, w) and (x,
Proposition 2. Under Assumption 7 [(x, w) is PL and lg Lipschitz smooth over w.
Proof. According to the definition of f(x,, y, w), we can calculate the Hessian of it as Vin [(r, v. w) V my y) V ( y)-
Since L,, 3 9.. T, we know that (x. y-w) is e Lipschitz smooth with respect to w.
On the other hand, L(x, y: w) is o² PL since 2 Al + b|]2 is strongly convex function composited with linear function which is omi (A)-PL according to 33
D.2 Proof of Lemma
According to Proposition and following the same proof of Lemma (7a). we know that
C(x ++1 w + L' (x* k+1
s (1 p0,))" (c(x", g w L (x" , ))
S (1 po)) 7,0
where the last inequality results from C(* y w²) = V , - f5,0/2 2 and L (0*, x22) 2 0. Then according to the EB condition, we know
22.00 1.0
262
d(w W(x )())) s (1 pag))"
Mg
the other hand, since wht Ran(V Vog )(+ according to the update, then *+1 Ran mog( ,y*+1)) and thus
arg min WEW 3 12)
||w wh k+1 w w(t", ,
As result, the bias can be bounded by
28
Di | w/ (x* y 11111122 d(w M(a 1²2 5( - po?2T
1.0
1gg
E Proof of Upper-level Error
E.1 Propasitions of (x.
Before proving the UL descent, we first present some property of w (xx y).
Lemma 9 (Lipschitz continuity and boundedness of wi (x. y)). Under Assumption 2 for any I2, and y. V1, V2. it holds that
| (xx, b)ll S E50//gg [lw w (12, v2)ll S 1201((21,00) 91) ) (x2, ye)l
with Lu fς1 +
v2
og o2
Proof. First, (v2 (2r w)) is bounded since according Assumption
1
(V v))²
Omin
V (x, v))
0g
19

---

On the other hand, according to 600 Theorem 3.3],
(V My v)) - (V vug(r', 2'))' 1 22 mlx (V (x u)) I1, ll (V wogld' |P
sy)(2, ( - V Vogll' ,y''
22 (1x,,) ('',
o v)) is (v28g.2/0) Lipschitz continuous.
which says
By the definition
32
wl y) (Vig((,))) v)) vf v). Therefore, the boundedness of
wi (z, 3) given by
400 0g
| (z, w)1l < || (V Ve v))
Besides, for any 21, D2 and y1, 92. we have
| (xi /n) wt (x2, 1/23l
|| - V V F1 1/2)
(V (222((2))))) (o
(V 12
V (f
vyf(zz2 V2)1
+ 1
22)ll
(V (11((1,11)) -V
(b)
f.11
g2
[[(21,91) - (122,
0g
g
where (a) is due to D and (b) comes from Lemma
C2 = Ci (() D2(Ci - C2) and Cauchy-Schwartz inequality
9
E.2 Proof of Lemma 6
We aim to prove the descent of upper-level by
F(x+t1, y w (a+t1 )(+l)) 1) F(a "n; wtl ,x²))
F(r y w (x+t1 ))) F Far*t1 1 y ttl w (x+ x²)
Lemma
+ F(zkt1 y wi (Ik x
F(x g wt (xtt y )
Lemma 12
+ Fla", w/ g wt (x*,, y x)))
F(x 6+1 ws (a* ,2)))
Lemma [k]
+ F(a + w (a* sh) F(x s wi (at ()
(31)
Lemma
14
For ease of use, we derive the gradient of F(x, y: wi (z, v)) below.
V F (x, y w/ (It, y)) = val(a, + v 2e y)u! (x, v)
(32a)
FyF(2, w/ (z, v)) vyf(x, 1z www (z, v)
(32b)
Lemma 10. Under Assumption F(I,y; w) is (f f2 | 1) smooth over and y.
Proof. This implied by the Lipschitz smoothness of (x, y) and Vyg(a, v).
Lemma 11. Under Assumption
2 we have
F1 y
w
(x++1
( ((+t)) F (
ytt (at xttl)
Br 9.1 Ry s/
1212
+ (gglwaa ||ak!1
(33)
Pg where dl is constant that will be chosen in Theorem 2
2,312
20

---

Proof. According to the definition of F(x, = f(z,8) v) + w T VVg(a, 3). it holds that
F(x"-1, , ww ,(tl)) F(x ,(attt, (x (x*t,(tt) ))+
(x",
-(ahtt , + (V vogltht , , w/ (alt), , f(att1 (uttt.ye (( (oo( w (x (
-VVglottt, .illaktt,,ttt ,btt),, w/ (xtt1 , - wl (at . x
I (Vuglo g wl (zht1, ) - -w (
so . (0) B12 1V Veg(t* , + a² a² d + ln 1|df/11
+ (Vog(zht), , - Vng(z* ,(t),,
) wewi(a (ahtt
- wat y
2,8722
(9) B ,00) +
L
+ f..1 Innae l
2,812
where (a) is earned by Young's inequality and the Lipschitz continuity of w w", y) and Veg. (b) is resulting from letting y² = arg min yest)) Ilv - y²1l and Lemma]) 7 that is
Vug(" / || = ll Vug(E" , Vyg(u* wx))
e Gaall - y2112 ,,
v 2 (o(a", , - g" 9"((11)
Hy
2
26 g.1 Ry ,²)).
v Ug
(g(a*, x²*) - 99"(x*1)
(g(a",²²)
(34)
Ugg
Lemma 12. Under Assumption 7 2 we have
F(a y kt,; wi (a* )(t1)) - F(x*, - : (ott,t/tt))
5- 2
S s-
_/
a LE 2r) 2
2
al2_1 by
(35)
2
where by : || wt wt( (at,,rtt)) +(+ and the constant Lp is defined as LF = E,,0(1,1+ fg22)/
Proof. Since F(
yr w) is (e,,1 + ln.2 (l2llll Lipschitz smooth with respect to æ, then according to
Lemma 9 we have
F(a y (xt,,,+++1) )(11))
S F(*h, yxt1 (x*, . x + (V>f(=*, g + V gl . g (a* , rht1 241)
LF 10 x112
+ 2
, k+1) + V gz .g / (x* ,xt d + a² LF |
= F(at, xht, w/ (a ( x1) -
2
(0) Flat: .y ykt wll (a* y ((+))) - 1
マ V f xz) + V2 V2y ( yuo (at, 111
a
+ a
3 Glud - vel(a" , ktl v2 gggg(s y b )wl (x+ 3/ + 2112 + a² aZLF 12
2
(6)
Lr a
al2 9.1 by
< F( F wt (=*.,*+11) ((
||d 12 +
2
where (a) is due to (A, B) ||ll + |
||- 2
II
(b) results from
| - vaf(a y x+)
- V2 var g ywl (+,
= VV,f( x + V2 gat yhtz )o Vzf(z g - ol y (u الt
Vige( ) (w w wttt,, (x*,"" ,
21

---

S IV 10 )| wl (x² ,
S Ibga1lu wi (x" ا( bk.
Rearranging terms yields the conclusion.
Lemma 13. Under Assumption
we have
F(x², , w/ (x*, y F Fx* ; ( ,,,,)))= 23N L 6
2.1
Ry (at 3/)
(36)
Mg
Proof. Letting vf" Projssat)(e)) (2 first bound I1y - g²112b0 by
| -1²112 = // - + y -y N + -
- 12
s N
11ght -11i1122 82N V Vyg(E* ,
8ºN N
| Ve9(** .xa,i) Vng(z* 0f)l
N-1
N-1
S 8 N 9.1
11 k. - -iil?= =
Σ 1=0
d(y S
N3 9.1
(( 9" (x(*))
(c) 2,8 N 9.1
(1 3pby) (g(e", (0(=".²²) - g" (z*))
Mg
2 9.1
2 2 R2 9.1
(g(a*, x² - g" (x*))
Ry
(37)
Mg
Mg
where (a) comes from V Vo y.) 0, (b) is due quadratic growth condition in Lemma derived from the contraction in (17a).
(c) is
Then, according to the definition of F F(r. = f(z, v) + w T Vug(z, v). it holds that
F(at, w wi (a*, "u",y/tt +(t)) F(a*: ; (at,t²))
-saa 1 1 + (Vog(ot, " ,( w/ (a+ , f(at,y ) (Vog(a", x(+1), w/ (att ,²")
= (V ( , wi (at, ,(t2) - w/ (a*t (2²))
BNL Vyg(tt |12
L lly 1/2
2
23N
2
Ry, ,*²)
Fi
where (a) resulting from 34 and 37
Lemma 14. Under Assumption 2 we have
230 + L
F(xx, Atl, w (x*,, )² Fax y wi (ot)))))) S
R Rx (x // (38)
Hg
Proof. We can expand F(x, yr w) with respect to y by
k+1, (' ))
I F(**, y² (x )² + (V (V, (x) V2 ga Do (at ,²),, k -/) + LF
11 111
2
22

---

F( : (a", B(Vnf(a" vuglet wn (o","")) Vug(at, x/ + LF 32 / Vog(o" "00"""")"]]
(0)
L Lrlg.11 12
I F(s y w/ (x ,)))
+ Mg
Ru(x". -3(V s0) + V vag Jw' (x*, . V Vyg(a* y²))
J2
where (a) results from 37 Letting y arg yesty) lly y011, the bound of J2 is derived by
J2 (a) B(V o (1* 5²) v mgglat yu' (a* v²) V Vug(at y²) V Vuglut, ,y"))
( BVV 1 /²) + V mug(o" - "w (a", )) V Vogle" 1 (2* - -y"))
-V 3²) v gy9(t* " )²), ) V byglet 5² (x -y²)}
+ 3(V ,, )/++ + V myg(a" D'' (x* ,)), (v (a v²) )- V vugllt ,2')) (1f -y"))
$ 3 )² (V of( 5*) + Vuglle 3 ) (It )) .2 v²)
+ VIV )²) + V b0g("" Vww' (x v² II V (0 x²) Vog(e .3/ d')le - y²1l
2 - BV 20 1² )V,,) (v w/²) + V Vagl vn) w²)) vx - 3²) + f - 101
- 2 1 = f g, S(x²1)²²
2.0. (g(0) 80) - -g" 90(x1)) 230 R R2 yt) U4
(39)
Bg
where (a) is due to v veg(t", (00((=""")=>>"" = 0. (b) is due to the mean value theorem and there exists E [0,
such that y/ ty + (1 too-tty""ooo (c) is due to | AA S 1 and
|| V x²) + Vog( )wo' (x* > |I(I V buele" ,2') (V (V Vol(a""""))
S L *² S t5.
and (d) comes from w (x, y) = - (Vyyll ,)))) v (x,, y) such that
v ga x²) (V, 38 + V Vz 3/ "wo' ,²,)) V (o n²) (1- Vig ) (V? Vogg 2t)) Vas(a" 2/2) =/²==00
= O.
eKer ( (/))
Here, I (y v²) (V? ( )² is the orthogonal projector onto Ker (2 (2 (,ax,²))))))))))))))())))) y²)))
Finally, according to 31 Lemma 6 can be proved in the following way.
Proof. Adding
33
35
366 and 38 we get
F(ah+1 h+1 1/ , w
h+1 x
F : 12
- a L a²
LF LF
- fg (. |1 12+ + al2 9.1 12
2712 3
2
312 9,1 1 nn + 23 2.0 + To 1r12,113 g2
Ry Ry
(40)
Hg
Then by choosing S min 1LF+8Lu
8nz 21
we yield the conclusion.
F
Proof of Overall Descent of Lyapunov Function
Proof. According to 17a 17b) and
29 we know
R,y(Itt p xt1) - R, (x ) = (-8pg + am Eg.1
Rat .//)+ + ( (ab..)
+ la.1 + Lg 202
|1
Mg
2m
2
(41)
23

---

Then since yh Fxx " ; wtt( (z" 1))) + cRy ,²,,, ) then adding (40 and (41) yields
(
(0 a
L a²
LF a² fg Lwo
ca cllg11
+ Lo) x2)
al
gktl 3/h $
||
l
+
2 1/
2
27p B 2
2m1
2
compge11 B122lg11
23N L By 9.1
+ 2.3
cBpu
Ry (9)
Mg
1 a² Lr a² - lyn
allg,1 + Tzg) +1g)
all
a²) ||0t/11
9.l
by
2np
2
2
2
2c al 9.1
+ 312l, 9,1 + 233
5.1 + +33l L
+ -L
cBplg
Ryla* )t
Hg
(
a
L a²
LF a² - lnn c(eg,1 + Log
Lo) (2) 11:2/12 + al
g.
1/
21/2
B
2
2
2
2c all n.1 + Bnelg + LL -Lpl.1182
cBpl
Ry Ryyl" 135))
2
Ng
L
LF a² lg
cla.11 +Tn) Lzg) a²
alg, 0%
|
a
161z2
2
2
9.1
cBpL
Brp22.1 9.1
+ Lr 1,12,113
1132
Ry Roylt..
4
P9
(4)
a
LF a -gg1
o6g.11 + Lg) _o)(²)) 2)
L
|1dt112
+
a22
by
8
2
2
cB1lg
02
Ro
8
Ug
(e)
a
|
112
cBPr
R (2t ,1²)
ab2
9.1
02
(42)
16
16
2
where (a) comes from setting 7/1 = 2el 1, (b) is achieved by 2 max
{
18 2f..
m.l
(c) is
14
"
2
gained by letting 3
S
85
(d) is achieved by
T.2 2
c 2² 2l
1/2
2cl
and (e) is earned by
1
B 5
8(LF + 26 In + c( c(L. Eg,1))
16 9.1
In word, a sufficient condition for (42) is
gf f.0
L.
g.1
L2
max
2L v 1g
1h1 2clg.1.
1/2
212
2el
1
cp
cP2 0.1
1 9
min
16
[L 20,, Lm + c(L, + Lg.13)
8cf2 9.1
9.1
Then rearranging the terms and telescoping yield
K-1
812
Ø-1
16 (a)
ak - 16(1 pozy2 2.n62
1640
Σ b
K
K
Mg
aK
k=
24

---

R
K
K-1
(
-
8l
K-1
b/g
+
1640 (a) cBug
S 16(1 - po al 5ol
9.1
1640
cBpuh K
cBpg
cBpg
K
k=0
where (a) comes from Lemma
Then by choosing
= log (K), we know that
K Σ
K
|| I so
Σ
(, 3²) -
1 K
(43)
K
K
K
Moreover, since Vu , w) is g. -iischiiz smooth over w according to Proposition 2 vwC(s 3², w wi ,))
and
then it holds that
|/ nn C(*" y², w012 V/ 3 wh) vuClot 8r, wt (a* 12)1
S 10,1 w - w (at 12
26 2 1100 - w (xx-11 )12 26 gm111u (x (x² (,""",,"") wt (att w/)1
s 28 bb + 26 a 11
Therefore, averaging the left-hand-side and plugging in the gradient of L yield,
K Σ Rr S w
1 K-1
Σ
v C(
K 0=
K
k=0
s o
212 9.
12 a² K-2
||
1 L(=
v. )1
K
K
k=0
(44)
where the last inequality is due to and the boundedness of I/V , 11
Similarly, we can bound
[[V, v²) + 2 (2t y/" 112
< 11 + 2 V (xt )²) + V2 ) 1/-
$ 2/ + V V
fx y²) vef(I* ,y |12 + V gf
V2
< 122 + a 1112 + 46 22,20211d 1 1112
(0)
< 21/d 21125_1112 + 10, a 2| - 112 + 402 2 2 Plll 112
26 7,00 o2
+
1
K
2PF f.u
1
< 2 + 46 a2 + 402
+
o
1|
02
K
where (a) comes from 1| <
(x )12 + 212
S
20 og
O11/K).
Therefore, using
we know
K K
K-1
(1)
Ro(x" .. ,) =
Σ
8² + Vayg(at M) k 1 s
(45)
K
0=
G Additional Experiments and Details
Synthetic experiments. We test our algorithm GALET on Example with different initialization. To see whether our stationary metric is necessary condition of the optimality of BLO, we need to
25

---

define a value directly reflects whether the algorithm achieves the global optimality or not. By the explicit form of the solution set in 77. the global optimality gap can be measured by
I| - 0.51 + ||0.5 + y1 - sin(
(46)
where the first term correpsonds the distance to the global optimal x-' 0.5 and the second term represents LL optimality, GALET achieves the global minimizers in 7 regardless of the initialization; see the top plot in F The bottom plot in Figure Figure[]shows the stationary score of reformulation (2) and (3). If the KKT conditions of 2 hold, then it is equivalent to say the following
Val(x,y) =0, 0, Vul(a, O, g(x, y) 9 ga())= 0.
(47)
whose proof is attached below.
Proof. First, the KKT conditions of (2 can be written as there exists o² such that V w²) + o (V :w" Vg"(x")) 0
(48a)
Vyf(E' v")
y²) = 0 g(Ø" v²) 9" (x*) =
(48b)
(48c)
4 implies y" E Sa("") For PL function g(r, y). we know that ify" E S(x=),, then V Vug(a (z".
0 and according to Lemma 8 we have V V=g(2= (z)) y²) Vag (x") 0. Therefore, (48a) and (48b)
are reduced to
Vaf(=".0") 0. Vuf(=".
which completes the proof.
Therefore, we can use the stationary score defined by V/ (x. y)
V=f(x, +
(9(x.
g" (x)) to measure whether the point achieves the KKT point of 2 For reformulation (3) our stationary measure is simply defined as the summation of the residual in (8). For both initializations, the stationary score of the value function-based reformulation 2 does not reach 0 whereas our measure based on the gradient-based reformulation (3) does. As the optimality gap of our algorithm converges to O, this implies the KKT condition for the value function-base reformulation (2) does not serve as a necessary condition for optimality. In contrast, our stationary metric does, thereby
validating our theoretical findings in Section 2
We also test the sensitivity of the parameters of our method and show the trajectories starting from the same initialization in Figure 4 We conduct experiments different parameter and the search grid is: UL stepsize a E {0.1, 0.3, 0.5, 0.7, 0.9}: shadow implicit gradient loops and stepsizes T E {1,5, 5 > {0.1, 0.5) and LL stepsizes and loops N E (1,5), E 1,,, The default choice of parameter is that our algorithm is least sensitive the shadow implicit gradient level parameters since all of the combinations of T and lead to almost the same trajectory. For the LL parameters 33 and N, our algorithm is also robust long as the learning rate /3 is neither set too large (3 = divergence) nor too small (B = 0.1, slow convergence). The UL stepsize plays an important role on the convergence of GALET as different choices of lead to distinct paths of GALET. The choices of a = 0.1, 0.3, 0.5 all lead to the convergence of GALET, while slightly larger value (a = 0.5) causes GALET to prioritize optimizing the UL variable x first.
0.3, K = 30, 3 = 1, = 1,7 0.1, = 1. We observe
Real-data experiments. We compare our method with the existing methods on the data hyper- cleaning task using the MNIST and the FashionMNIST dataset (21). Data hyper-cleaning is to train classifier in a corrupted setting where each label of training data is replaced by a random class number with corruption rate Pe that can generalize well to the unseen clean data. Let x: be vector being trained to label the noisy data and y be the model weight and bias, the objective function is given by
min #.))((2)
fz, v (x))
Σ
CE (x); u4, e4)
Deal
s.t. y S(x) arg min g(r v)
Σ
[o(x)), (v: u4, 4)
Drr
where CF denotes the cross entropy loss and a denotes sigmoid function. We are given 5000 training data with corruption rate 0.5, 5000 clean validation data and 10000 clean testing data. The existing
26

---

methods for nonconvex- wwwpeeeeeestooglyyoooo BLO 221 322 often adopts single fully- connected layer with a regularization as the LL problem. but the regularization and the simple network structure always degenerate the model performance. As our algorithm is able to tackle the nonconvex I.I problem with multiple solutions, we can consider more complex neural network structure such two layer MLP without any regularization. Since training samples is fewer than the model parameters, the LL training problem is an overparameterized neural network so that satisfies the PL condition.
Algorithm implementation details. Instead of calculating Hessian matrix explicitly which is consuminn, we compute the Hessian-vectes product via efficient method [53]. Specifically, we can auto differentiate V (I, (x,8) y) "w with respect to and to obtain V Vzyg(z, (z, y) w and V Vy y)w.
Also, let vz,f u) + V Ny y)w which detaches the dependency of over and y the Reesian-veector product V Vyyg(2; (z. y)v can be calculated by auto differentiation of Vyg(z, y)
Parameter choices. The dimension the hidden layer of MLP model is set as 50. We select the stepsize from {0.001, 0.005, 0.01, 0.05, 0.1}, while the number of loops chosen from T E (5, 10, 20, 30, 50) and N E (5, 10, 30, 50, 80}.
{1, 10, 50, 100, 200, 500), {0.1, 0.3, 0.5, 0.8) and
2.0
20
BOME
BOME
1.5
V-PUOD
V-PBGD GALET
V-PBGD [APTT-GM
JAPTT-GM
1.5
GALET
Text Boxs
Text Jook
GALET
1.0
1.0
0.5
1000
2000
3000
5000
1000
2000
3000 Itetttn
4000
Ittration
(a) MNIST, linear model
(b) MNIST, 2-layer MLP model (c) FashionMNIST, 2-layer MLP model
Figure 7: Test loss v.s. iteration.
MNIST
FashionMNIST
Method
Linear model
MLP model
MI.P model
RIG [21
87.83 1 0.17
87.95 1 0.21
81.87 1: 0.31
BOME
88.76 + 0.15
90.01 + 0.18
83.81 = 0.26
IAPTT-GM
90.13 0.13
90.86 1 0.17
83.50 1 0.28
V-PBGD
90.24 0.13
92.16 0.15
84.18 0.22
GALET
90.20 + 0.14
91.48 0.16
84.03 + 0.25
Table 3: Comparison of the test accuracy of different methods on two dataset with different network structure. The results are averaged over 10 seeds and followed by the variance.
The test loss v.S. iteration of different methods is shown in Figure 7 it can be seen that GALET converges fast all of regimes. Moreover, we report the test accuracy different methods Table 3 It shows that GALET achieves comparable test accuracy with other nonconvex-nonconve bilevel methods, which improves that of nonconvex-stree stroeeeeesstooogyyooeeee bilevel method RHG.
27


Reviews:
[{"review_id": "0xjZXDiJFJ", "reviewer": "Reviewer_swWK", "summary": "This paper addresses the bilevel optimization problem, which may feature a non-convex lower-level problem with non-unique optimal function values. The lower-level problem can be transformed into a constraint optimization problem using function value or gradient-based constraints. The paper establishes necessary conditions via calmness to evaluate the optimality of bilevel optimization problems where the inner problem satisfies the PL condition. Based on these conditions, the authors develop the GALET method, which alternately updates the inner and outer variables. The effectiveness of GALET is demonstrated through an experiment involving hyper-data cleaning, which shows that GALET performs comparably to V-PBGD.", "questions": "As mentioned in weaknesses. ", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main strength of this paper is the proposal of a stationary metric to evaluate the optimality of BLO problems with non-convex lower-level problems. This metric enables to achieve optimal iteration complexity.", "weaknesses": "Overall, I have the following concerns and comments about this paper:\n1.  While formulation (2) is directly equivalent to BLO problem (1), the equivalence of the gradient-based formulation (3) only holds under PL conditions. As a result, it is unclear whether the proposed stationary condition is applicable in cases where the inner function of BLO does not satisfy the PL condition. Do you think it is feasible to extend the proposed stationary condition to the more general non-convex setting?\n\n2. As checked, it appears that the values of $\\beta$, $N$ $\\alpha$, and $\\eta_1$  are closely related in the analysis. However, in Theorem 2 and Lemma 4,  the authors merely simplify these parameters to the order of $\\mathcal{O}(1)$. As a result, the theoretical results do not elucidate the relationship between these parameters. It would be helpful if the authors could provide more details on how these parameters are related to each other in the main results.\n\n3. Figure 1 shows the stationary score of function value-based and gradient-based formulations (2) and (3) under different initializations. It is unclear which algorithm is adopted to solve the function value-based problems. It may affect the value of the KKT measure over iteration. Could you provide more information regarding the details of this result?\n\n4.  The main results presented by the authors focus solely on iteration complexity and do not provide information on the gradient oracle complexity or Hessian-vector complexity. Could you provide the complexity of the gradient and Hessian vector? It would be beneficial to include information on how these complexities depend on various Lipschitz constants and the PL constant $\\mu_g$. In addition, the strongly convex function is a special example of the PL function. It would be helpful to compare the results of GALET for strongly convex inner functions to those in the existing literature.\n\n5. The proposed method, GALET, is a second-order method, while the V-PBGD method is a fully first-order method. The authors have claimed complexity improvements over V-PBGD. But, from the numerical experiments, I did not observe any advantages over the first-order V-PBGD method, as expected.  It raised the question of whether the second-order information helped in your experiments. It would be helpful if you could provide additional evidence to clarify the performance of the experiments. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our contribution and the constructive review. Our response to your comments follows. \n\n**Q1: Possibility of extending the proposed stationary condition to the general non-PL nonconvex setting.**\n\nThanks for raising this intriguing point! Currently, generalizing the proposed stationary condition to the general non-PL nonconvex setting is challenging. The difficulties primarily arise from three aspects: 1) The lower-level stationary points are not necessarily feasible for the BLO because they are not necessarily the lower-level optimal points; 2) identifying a valid CQ condition for the non-PL BLO becomes unknown; and 3) The PL condition is currently the most reliable condition, ensuring the existence of an algorithm - gradient descent - that converges to the global optimal sets at a linear rate. However, for a general nonconvex lower-level problem, finding the globally optimal lower-level solution set efficiently remains difficult, letting alone defining a stationary measure. \n\n**Q2: Explicitly show the choices of $\\alpha,\\beta,N,\\eta_1$.** \n\nWe answer it in the **General Response G3**. Hope this can address your concern.  \n\n**Q3: Provide more information regarding Figure 1.** \n\n*Setting of Figure 1.* To generate Figure 1, we run GALET on the Example 1 and report two types of stationary score -- value function based and gradient based -- as a function of iteration index. Due to the space limitation, the calculation of two types of KKT score is detailed in the line 713-734 in Appendix. \n\n*Interpretation of Figure 1.* As the optimality gap (the distance to the global optimal set) of GALET converges to $0$, it means GALET achieves global optimal solutions of Example 1 under both initializations. However, the value function based stationary score does not reach 0, but the gradient-based stationary score does. This implies the KKT condition for the value function-based reformulation does not serve as a necessary condition for optimality. \n\nThank you for raising this point. We will move the details from the Appendix directly into the main paper and add explanations. \n\n**Q4：Complexity of the gradient and Hessian vector and the dependence on Lipschitz constant and $\\mu_g$.** \n\nThank you for this constructive suggestion. \n\nLet $\\operatorname{Gc}(f, \\epsilon)$ and $\\operatorname{Gc}(g, \\epsilon)$ : number of gradient evaluations w.r.t. $f$ and $g$;  $\\mathrm{JV}(g, \\epsilon)$ : number of Jacobian-vector products $\\nabla_{xy} g(x, y) v$; $\\mathrm{HV}(g, \\epsilon)$ : number of Hessian-vector products $\\nabla_{yy}^2 g(x, y) v$. If we define the condition number as $\\kappa_1=\\ell_{g,1}/\\mu_{g}$ and $\\kappa_2=\\ell_{g,1}/\\lambda_{g}$, the gradient and Hessian-vector product complexity is summarized in Table R1. \n|Algorithm |$\\operatorname{Gc}(f, \\epsilon)$ | $\\operatorname{Gc}(g, \\epsilon)$ |$\\operatorname{Jv}(g, \\epsilon)$|$\\operatorname{Hv}(g, \\epsilon)$|\n| :---------- | :--------: | :-------: |:--------: | :-------: | \n|GALET  | ${\\cal O}\\left(\\frac{\\kappa_1^4\\kappa_2^2 }{\\min\\\\{\\kappa_1,\\kappa_2\\\\}}\\epsilon^{-1}\\right)$| ${\\cal O}\\left(\\frac{\\kappa_1^4\\kappa_2^2 }{\\min\\\\{\\kappa_1,\\kappa_2\\\\}}\\epsilon^{-1}\\right)$ | ${\\cal O}\\left(\\frac{\\kappa_1^4\\kappa_2^2 }{\\min\\\\{\\kappa_1,\\kappa_2\\\\}}\\epsilon^{-1}\\right)$| $\\tilde{\\cal O}\\left(\\frac{\\kappa_1^4\\kappa_2^2 }{\\min\\\\{\\kappa_1,\\kappa_2\\\\}}\\epsilon^{-1}\\right)$ |\n|Strongly-convex GALET |${\\cal O}\\left(\\kappa_1^5\\epsilon^{-1}\\right)$| ${\\cal O}\\left(\\kappa_1^5\\epsilon^{-1}\\right)$|${\\cal O}\\left(\\kappa_1^5\\epsilon^{-1}\\right)$|$\\tilde{\\cal O}\\left(\\kappa_1^5\\epsilon^{-1}\\right)$|\n|stocBiO [28]  |${\\cal O}\\left(\\kappa_1^3\\epsilon^{-1}\\right)$| ${\\cal O}\\left(\\kappa_1^4\\epsilon^{-1}\\right)$|${\\cal O}\\left(\\kappa_1^3\\epsilon^{-1}\\right)$|${\\cal O}\\left(\\kappa_1^{3.5}\\epsilon^{-1}\\right)$|\n\n\n*Table R1: Comparison of bilevel deterministic optimization algorithms.* \n\nThe complexity of GALET in strongly-convex case is worse than that of deterministic strongly-convex case in stocBiO [28] in terms of $\\kappa_1$, because GALET necessitates an additional Hessian in the $w$ update, which subsequently enlarges the Lipschitz continuity modulus of the objective in the shadow implicit gradient level. However, as discussed in Section 3.2, the additional Hessian is inevitable for cases that are not strongly convex. \n\n**Q5：Empirical performance versus V-PBGD**\n\nGreat observation! Thank you for this insightful question. As shown in the left figure in Figure 5 and Figure 7 in the Appendix, GALET converges faster than V-PBGD in terms of iterations, thus verifying that GALET's convergence rate of ${\\mathcal O}(\\epsilon^{-1})$ surpasses that of V-PBGD, which is ${\\mathcal O}(\\epsilon^{-1.5})$. However, when it comes to test accuracy, GALET does not outperform V-PBGD due to the following factors that may influence test accuracy. We propose two possible explanations: \n\n1. V-PBGD relaxes the lower-level exact solution by its $\\epsilon$ approximate solution. This relaxation introduces errors into the original bilevel problem (from optimization perspective), but it actually helps prevent the overfitting issues in the simulated hyper-cleaning task as the lower-level problem is a model training problem. \n2. The global optimal solutions of bilevel problem are correlated with validation accuracy (bilevel objective), rather than the test accuracy. Also, attaining the stationary points of the bilevel problem does not necessarily guarantee reaching the global optimum of the bilevel problem, letting alone with the test performance. \n\nThis is also the reason that we plot the stationary score we proposed of GALET and show the iteration complexity of GALET nearly matches ${\\mathcal O}(\\epsilon^{-1})$ in the right figure in Figure 5. This result is more aligned with our improved theory over V-PBGD. \n\nWe hope our clarification addresses your concerns. Thank you once again for your careful review!\n"}, {"review_id": "pOp1QwUlmm", "reviewer": "Reviewer_5R75", "summary": "The paper studies unconstrained bilevel optimization under the PL condition at the lower level. All previous work is limited to strongly-convex lower-level problems. The authors propose a new convergence criterion for this setting based on stationary-point seeking reformulation, supporting it with the calmness and constraint-qualification arguments. The algorithm is a slight variant of recent Hessian-inverse-free methods for strongly-convex lower-level cases. Convergence analysis is performed with standard smoothness assumptions in deterministic settings (with access to true gradients and Hessians). The algorithm is demonstrated via the MNIST data-hyperclearning experiment.", "questions": "- Can a PL function have multiple optimal solutions, and at the same time Hessian-Lipschitz? Because at suboptimal points that is a neighborhood of optimal points, the gradient-growth has to be at least $\\mu$. \n\nOtherwise, which one should be given up? Analysis might be intact if we change the condition to have a unique lower-level solution, but if we give up Hessian-Lipschitzness, I am a little not sure if everything still works. \n\n\n- In the inner loop, w_0 already has to start from 0 to ensure the minimum-norm solution. What can be said if the gradient is not exact or if $w_0$ starts from other points? \n\n\n- Can you at least have Assumption 2 only at the optimal points, and not on all y? \n\n- For (8b) in KKT condition, why not just $||\\nabla f(x^*, y^*) + \\nabla^2_{yy} g(x^*, y^*) w^*||^2 \\le \\epsilon$, instead of having additional $\\nabla^2_{yy} g(x^*,y^*)$?", "limitations": "This paper is theoretical and has no concerns about societal impact.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper extends the existing literature to problems with PL lower level. Bilevel optimization is a fast-moving area, and this extension is a timely contribution to the literature. I haven't seen yet the PL condition considered in the context of Bilevel optimization (even though it appeared several times in min-max literature, and the underlying idea is not quite different). \n\n- The convergence criterion is well-supported by calmness and constraint-qualification arguments. \n\n- Presentation is clear and easy to follow.", "weaknesses": "Overall, the algorithmic idea is essentially the same as previously developed algorithms. \n\n- For instance, the work in [11] considered the same algorithm with strongly-convex lower-level objectives, to avoid Hessian-inverse estimation. The idea is essentially to solve a linear equation efficiently, which can be done in various ways (e.g., by running the GD on a quadratic function). This work does the same, the only difference is to force the initializer $w_0$ to be at 0, so that GD converges to the minimum-norm solution (the pseudo-inverse solution). However, the same argument does not seem to be applicable to SGD or non-zero initialization. Furthermore, this seems why Assumption 2 is required: lower-bound for non-zero singular values for all $y$. Given that the lower-level objective is already $\\mu$-PL, another assumption seems redundant. \n\n- The paper only considers deterministic cases, but most previous work can also handle stochastic gradients and Hessian oracles. Though this paper seems to be hard to be extended to stochastic analysis. \n\n- I think there are several technical issues that need more justification. Please see the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our presentation and recognizing our work as \"a timely contribution to the literature.\" Our response to your comments follows. \n\n**Q1: Concerns on the algorithmic idea.** \n\nThank you for recognizing the necessity to extend bilevel optimization (BLO) to the PL setting, but we want to highlight that it is very different from PL min-max problem as there are fundamental challenges in PL BLO. \n\n1. **PL min-max problem does not have issue of invalid constraint qualification (CQ).** In sequential min-max problem where $g=-f$, once we have the gradient of value function $g^*(x)=\\min_y g(x,y)$, a nature stationary condition is $\\nabla g^*(x)=0$. This is quite different in BLO since the stationary criterion is not naturally defined and we need to find a provable CQ condition ensuring the (weak) KKT conditions are met at the optimality. Actually, sequential min-max problem is a special case of BLO where CQ automatically holds [60]. [33] also mentioned the importance of CQ to ensure the stationarity of BLO but they did not verify the CQ they assumed. We highlight the importance of the provable CQ condition in Section 2.3. \n2. **New proof techniques.** \n**(a)** In min-max problem, previous studies characterize the drifting of the lower-level (LL) optimality residual $\\mathcal{R}_y\\left(x^{k+1}, y^k\\right)-\\mathcal{R}_y\\left(x^k, y^k\\right)$ in (16b) by the identical stationary conditions of $f$ and $g$ coming from $f=-g$. But in BLO, the stationary condition of $f$ and $g$ can be totally different. Instead, we derive (16b) by the smoothness of $g^*(x)$ and use the opposite sign of $g(x, y)$ and $g^*(x)$ ($g(x,y)-g^*(x)$) to cancel out the first order terms in Taylor expansion. \n**(b)** In min-max problem, a natural Lyapunov function for upper-level descent is $\\max_y f(x,y)$, which is not the target objective in BLO. We adopt $f(x, y)+w^{\\dagger}(x,y) \\nabla_y g(x, y)$, which is originated from the KKT increment (8a). Moreover, our proofs are based on the multi-sequence update of the KKT increments instead of the identical stationary conditions of $f$ and $g$ in min-max problem. \n\n**Q2：Can a PL function have multiple optimal solutions and also Hessian-Lipschitz?**\n\nThese assumptions are not contradictory. For example, given an UL variable $x$, a strongly convex and $\\ell_h$ Hessian-lipschitz function $h(x,\\cdot)$ and a matrix $A$ that is not in full rank, the function $g(x,y)=h(x,Ay)$ satisfies these three conditions. We justify it as follows: \n\n**1) PL over $y$.** This is proved by [29, Page 14 Appendix B].  \n\n**2) Hessian Lipschitz.** The Hessian of $g(x,y)$ can be calculated by $\\nabla_{yy}^2g(x,y)=A^\\top\\nabla^2h(x,Ay)A$, where $\\nabla^2h(x,Ay)$ denotes for $\\nabla^2h(x,z)|\\_{z=Ay}$. Then the Hessian Lipschitz continuity of $g(x,\\cdot)$ can be obtained from \\begin{align*}\n\\\\|\\nabla_{yy}^2g(x,y_1)-\\nabla_{yy}^2g(x,y_2)\\\\|&\\leq \\\\|A^\\top(\\nabla^2h(x,Ay_1)-\\nabla^2h(x,Ay_2))A\\\\|\\\\\\\\\n&\\leq \\\\|A\\\\|^3\\ell_h\\\\|y_1-y_2\\\\|. \n\\end{align*} \n\n**3) Multiple solutions.** $g(x,y)$ only depends on the value of $Ay$, so the null space component does not affect the value of $g$. If $A$ is not full rank, for any solution $y^*$ of $g$, $y^*+\\operatorname{Ker}(A)$ is the solution space.  \n\n**Q3：Can $w_0$ be initialized from other points or the gradient is not exact?**\n\nThank you for this interesting question which may help us extend our analysis. \n\n1. **$w^{0}$ can be other points other than $0$ if $w^{k,0}=w^0$ for any $k$.** We answer it in the **General Response G4**.  \n\n2. **The gradient can be inexact if the bias is bounded.** The convergence relies on the boundedness and Lipschitz continuity of limit points. Similar to the non-zero initialization, if the deterministic gradient is inexact but it has bounded bias, then the sequence $\\\\{w^{k,t}\\\\}\\_{t=0}^\\infty$ will converge to a bounded neighborhood of the exact solution. Lipschitz continuity of the biased solution can be earned similarly as the non-zero initialization. \n\n**Q4：Relax Assumption 2 to the optimal points**\n\nIt can be very hard. Assumption 2 is a generalization of the strongly convex assumption in BLO in [8, 23, 20, 28, 1, 11] that has been assumed for any $y$. As it is used in per-iteration analysis of the algorithm, relaxing it may need major change of the analysis. \n\n**Q5：The use of additional Hessian in (8b).**\n\nThank you for raising this question. We answer it in the **General Response G1**.  \n\n**Q6: Possible extension to stochastic setting?**\n\nFor BLO with a strongly convex LL problem, the stochastic setting has been actively studied. But most literature on BLO with nonconvex LL problems [37, 2, 43] focuses on the deterministic case. And even for deterministic case, the iteration complexity does not match that of single-level optimization. \n\nTherefore, in this work, we take the first step to address the fundamental issue if we can achieve the optimal convergence rate for the deterministic nonconvex BLO. Extending this work to a stochastic setting is of high interest yet also nontrivial that involves new analysis of bounding the higher-order stochastic moments (beyond the third order). We will develop new tools to address in our future work. \n\nWith the above clarifications, we sincerely hope the reviewer can reconsider the theoretical contribution of our work and raise the score. Thank you again!  \n\n\n"}, {"review_id": "CDLhcvxFTi", "reviewer": "Reviewer_wxYg", "summary": "This work studies an important problem of bilevel optimization with non-convex lower level function. The authors reformulate the problem as a constraint optimization and prove a constraint qualification (CQ) for the reformulated problem under mild assumptions, and show that other stronger CQ do not hold under the same assumptions. Next, authors introduce the stationarity measure for this problem and propose an algorithm which converges in this measure with minimax optimal rate under the given assumptions. Numerical simulations on synthetic and real data are provided to test the proposed algorithm and compare to other baselines.", "questions": "1. In the proof of Lemma 3, do we need smoothness of $f(x, \\cdot)$? It does not seem to be used in the proof. \n\n2. In theorem 1 (8b), it is unclear to me where the term $\\nabla_{yy}^2 g(x^*, y^*)$ comes from. Is it necessarily positive definite? It would be good to explain why this term is needed. Same question for $\\nabla_{yy}^2 g(x^k, y^{k+1})$ term in (11b). The authors claim \"the additional Hessian in (11b) is inevitable\". Why? \n\n3. Why do we necessarily have $\\lambda_g >0$? for any $x, y$ the Hessian might have negative eigenvalues for PL functions.", "limitations": "The paper makes the fist steps in relaxing assumptions and proving the optimal rate for the fundamental setting of bilevel nonconvex optimization. Authors admit that the extension of the developed techniques to the stochastic setting might require different techniques. \n\n---\nAcknowledgement of the authors' rebuttal. \n\nI thank the authors for the rebuttal and addressing my concerns. It is a little disappointing that in the discussion phase it turned out that the lower level problem cannot be non-convex PL while it was one of the key claims of the paper (it's of course great that other reviewers could detect this during the review period). I believe the key results of this work are still valuable even if they merely apply for convex lower level problems and the condition on the eigenvalues does not seem very natural. I still recommend the acceptance of this work, but am less certain about the decision after the rebuttal/discussion.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and easy to follow. The limitations of previous works are well explained and the goal of the paper is clearly stated. The key contribution of the paper is substantially relaxing the assumptions and proving improved iteration complexity for bilevel problems, which matches with the optimal complexity (even for single level problems) in terms of $\\epsilon$.", "weaknesses": "1. The mathematical clarity of some statements in the main part can be certainly improved. For instance, in Definition 2 (calmness) it is unclear to me if h(x, y) is a function or a map to $\\mathbb R^d$, is $q$ a vector or a scalar? I also assume that the statement should hold for any pair (x', y'), not only for one. Although one can eventually infer the answers to these questions from the proofs in the appendix, it is better to be more rigorous. \n\n2. In Figure 2, I do not understand what is the difference between the blue and the red boxes (Gradient-based PL-BLO reformulation). \n\n3. I suggest to remove the right plot from Figure 5. It does not really make sense to compare the actual convergence rate with the asymptotic theoretical sublunar rate. How the exact constant was chosen? Why GALET is actually faster than theoretically proven 1/K. \n\n4. The intuition for convergence of terms $\\mathcal R_x$ and $\\mathcal R_y$ are well explained before stating Theorem 2. However, why $\\mathcal R_w$ converges is not immediately unclear from (20). I suggest to clarify this in the revision.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our contribution and the constructive review. Our response to your comments follows. \n\n\n**Q1: Rigorous definition of calmness.**\n\nThank you for your suggestions and we will formalize the definition of calmness. To answer your specific confusion, $h(x,y)$ can be function or map and the dimension of $q$ is the same as the output of $h(x,y)$. If $h(x,y)=g(x,y)-g^*(x)$, which is a function, then $q$ is a scalar; if $h(x,y)=\\nabla_yg(x,y)$, which is a map, than $q$ is a vector. The statement should hold for any $(x^\\prime, y^\\prime)$. \n\n**Q2: Typo in Figure 2.**\n\nSorry for the confusion. We made a typo in Figure 2 and the term in red boxes should be \"Gradient based strongly convex BLO reformulation\". We will correct it. \n\n**Q3: Removing the right plot in Figure 5.**\n\nThe purpose of Figure 5 is to show the convergence rate of GALET, with respect to the stationary measure, is approximately ${\\cal O}(1/K)$, as the test loss curve does not directly represent the stationary measure.  We choose the constant of ${\\cal O}(1/K)$ to make it close to the curve of GALET for comparison. We can remove it if it is not suitable.\n\n**Q4: Explain the reason why $\\mathcal{R}_w$ converges.**\n\nThe reasons are that $\\lim_{t\\rightarrow\\infty}w^{k,t}=w^\\dagger(x^k,y^{k+1})$ and $\\mathcal{R}_w(x^k,y^{k+1},w^\\dagger(x^k,y^{k+1}))=0$ according to the stationary condition of $\\mathcal{L}(x,y,w)$ with respect to variable $w$.  \n\n**Q5: Smoothness of $f(x,\\cdot)$ in Lemma 3.**\n\nIn the proof of Lemma 3, it does not rely on the smoothness of $f(x,\\cdot)$ but the smoothness of $g(x,\\cdot)$. The smoothness together with PL condition of $g(x,\\cdot)$ ensures the error bound condition, which plays an important role in the proof of Lemma 3. \n\n**Q5: Additional Hessian in (8b) and (11b).** \n\nThank you for raising this question. We answer it in the **General Response G1**.  \n\n\n**Q6: Does $\\lambda_g>0$ implies nonnegative eigenvalue?**\n\nThank you for raising this clarification question. Since it is also raised by other reviewers, we answer it in the **General Response G2**. \n\nThanks for the careful review and giving favorable recommendation. "}, {"review_id": "FDqG9crgTJ", "reviewer": "Reviewer_k2BT", "summary": "This paper proposed a generalized alternating method for nonconvex bilevel optimization with PL condition in lower level. Meanwhile, it provided convergence analysis for the proposed method under a new stationary metric. Some experimental results demonstrate efficiency of the proposed method.", "questions": "1)\tIn Assumption 2, since $\\lambda_g>0$, clearly, $\\nabla^2_{yy} g(x,y)$ only have positive eigenvalues ?\n\n2)\tIn the equality (11b), can we use \n$$\\nabla^2_{yy} g(x^k,y^{k+1})\\big(\\nabla_y f(x^k,y^{k+1})+\\nabla^2_{yy} g(x^k,y^{k+1})w^{k,t}\\big)$$ instead of \n$$\\nabla_y f(x^k,y^{k+1})+\\nabla^2_{yy} g(x^k,y^{k+1})w^{k,t}$$ ?\n\n3)\tIn the proposed GALET algorithm, since using the multi-step gradient descent to update variable $y$ and introduced variable $w$, why still compute Hessian matrix $\\nabla^2_{yy} g(x,y)$ and Jacobian matrix $\\nabla^2_{xy} g(x,y)$ ?\n\n4)\tIn Theorem 2, how to choose the learning rates $\\alpha$, $\\rho$ and $\\beta$ ? Please detail them.\n\n5)\tIn Theorem 2, why give $S=O(1)$ and $T=O(\\log(K))$ ? In other words, why $T$ is larger than $S$ ?\n\n\n\n---------------------------------------After Rebuttals ------------------------------------------------------------------\n\n\nThanks for authors' responses. However, the authors' responses did not address my main concern: Assumption 2 is very strict. \n\nAdding Assumption 1, i.e. $ \\nabla^2_g$ is Lipschitz continuity, the authors claim that Hessian matrix maybe includes zero eigenvalue (singular value). Clearly, $\\lambda_g$ is very small even approach zero. Thus, the gradient complexity is infinite, **Please the table given in Rebuttal by Authors to Reviewer swWK**. \n\nWhen Hessian matrix does not include zero eigenvalue (singular value), i.e. $\\lambda_g >0$, \nclearly, assumptions 2  and 1 are exactly strong convexity, defeating the whole purpose of the paper.\n\nThus I lower my score.", "limitations": "Not potential negative societal impact.", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper proposed a generalized alternating method for nonconvex bilevel optimization with PL condition in lower level. Meanwhile, it provided convergence analysis for the proposed method under a new stationary metric. Some experimental results demonstrate efficiency of the proposed method.", "weaknesses": "In the paper, some incomprehensible words make it difficult for me to judge whether the conclusion in the paper is correct ? \n\nFor example, clearly, the lines 276-277 of the paper (‘’ Note that $\\lambda_g>0$ allows $\\nabla^2_{yy}g(x,y)$ to have either negative eigenvalues or zero eigenvalues … .’’) are not incorrect. \n\nFrom Table 1, the authors said BOME [33] and MGBiO [24] only studied a singleton on $S(x)$. From [33] and [24], they studied the bilevel optimization problem:\n\n$$  \\min_{x\\in \\mathbb{R}^{d_x}} f(x,y^*), \\quad s.t., \\quad y^* \\in \\arg\\min_{y\\in \\mathbb{R}^{d_y}} g(x,y),$$\n\nwhich equals the bilevel problem (1) given in this paper. Thus, I think the BOME [33] and MGBiO [24] also studied non-singleton on $S(x)$.\n\nForm this paper, the authors point that they introduce and use a new stationary metric in convergence analysis. It is better? Please detail differences between it and other metrics used in [48,33,24,2,38].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reviews. However, we feel the reviewer might have misunderstood some technical points in our paper which leads to the concern on the correctness of the conclusion in the paper. Our response to your comments follows. \n\n**Q1: Does $\\lambda_g>0$ implies positive eigenvalue?**\n\n We answer it in the **General Response G2**. Hope this can address your concern. \n\n**Q2: Singleton assumptions in BOME [33] and MGBiO [24]**\n\nThank you for pointing out this. We are very sorry for the inaccurate description of the related work. Upon double checking BOME [33], we found that it considers two settings: for the singleton scenario, it has a faster rate of ${\\cal O}(\\epsilon^{-3})$; and for the nonsingleton setting, it has a slower rate of ${\\cal O}(\\epsilon^{-4})$; both of which are slower than our rate. We will add this note in our submission. For MGBiO [24], they only consider the singleton case, otherwise $y^*(x)=\\arg\\min_y g(x,y)$, then $f(x,y^*(x))$ would be multivalued, rendering $\\min_x f(x,y^*(x))$ ill-posed and the implicit function theorem would fail. Actually, we adopt the optimistic bilevel optimization formulation in [55,37,2,43]\n$$\\min_{x,y\\in S(x)}f(x,y),\\qquad \\textrm{s.t. } S(x)=\\arg\\min_y g(x,y)$$\ninstead of the singleton bilevel formulation.\n\n\n**Q3: Whether the new stationary metric is better.**\n\n1. The metric in [33,24,2] cannot be applied here.  As we stated in Line 51-55, the proposed stationary metric is a **generalized version** of the existing measure in [33,24,2]. Due to the space limitation, we have mentioned it in Line 188-190 but deferred the detailed discussions in Appendix H.1.  \n2. [48,38] relax the lower-level problem by its $\\delta$- approximate solution or pessimistic trajectory with initialization auxiliary, so the stationary point they achieved are the $\\epsilon$ stationary point of the $\\delta$- approximate problem, i.e. $(\\epsilon,\\delta)$- stationary point of the original BLO. Instead, we proved that (8b) are the necessary conditions to the optimality of the original BLO problem, so the stationary point we achieved is the $\\epsilon$ stationary point to the original BLO problem. \n\nWe also highlight the importance of generalizing the existing measure without additional CQs in Section 2.3. \n\n**Q4: Removing the additional Hessian in the update (11b).** \n\nThank you for raising this question. We answer it in the **General Response G1**.  \n\n**Q5: The reason for computing Hessian and Jacobian.**\n\nImplementing GALET does not require explicitly computing Hessian and Jacobian because we calculate Hessian-vector and Jacobian-vector product instead as shown in Line 760-764 in Appendix and they can be easily computed by auto differential function in pytorch or backpropagation. Also computing Hessian-vector and Jacobian-vector product are standard even in bilevel with strongly convex LL problems such as in [8, 9, 23, 20, 28, 31, 30, 1, 11]. \n\n**Q6: Choices of learning rates $\\alpha,\\beta,\\rho$.** \n\nWe answer it in the **General Response G3**. Hope this can address your concern.\n\n**Q7: Reasons for $T$ larger than $S$.**\n\nIn Theorem 2 of our paper, it appears there is no $S$. We guess that you meant to refer to $N$ instead. We set $N={\\cal O}(1)$ because we use warm start strategy on the update of $y$, i.e. update $y^{k,n}$ starting from $y^k$, but use cold start on the update of $w^{k,t}$ initialized at $0$. To guarantee the convergence of $\\\\{w^{k,t}\\\\}\\_{t=0}^\\infty$ to the minimum-norm solution, one need $T={\\cal O}(\\log(K))$ iterations. The warm strategy is not suitable for $w$-update in PL setting, which is actually one of the key technical challenges we overcome, due to the following reasons. \n\n1. **(Bounded trajectory)** Different from lower-level objective $g(x,y)$, the carefully designed objective $\\mathcal{L}(x,y,w)$ in shadow implicit gradient level is only Lipschitz smooth over $x$ and $y$ for bounded $w$. Therefore, one should ensure the boundedness of $w^{k,t}$ sequence. We achieve this by initializing $w^{k,t}$ from $0$ (cold start strategy) such that it converges to the minimum-norm solution which is bounded. \n2. **(Lipschitz continuous trajectory)** Characterizing the upper-level descent requires the Lipschitz continuity of the limit point of the trajectory of $w^{k,t}$ over $x$ and $y$ (i.e. the Lipschitz continuity of $w^\\dagger(x,y)$ over $x$ and $y$). But the warm start strategy yields a trajectory of $w$ that is not Lipschitz continuous over $x$ and $y$. \n\n\nWith the above clarifications, we sincerely hope the reviewer can reconsider the correctness of our theoretical results!  We are happy to answer any follow-up questions on the correctness. "}]

Author rebuttal:
## General Response ##

We sincerely thank the reviewers for their constructive comments. All reviewers have agreed that our work has substantially relaxed the strongly convex lower-level assumptions in bilevel optimization and proved the optimal complexity in terms of $\epsilon$. Comments from all the reviewers were really helpful, which we believe have been fully addressed in detail in our rebuttal. 

We first clarify the common issues raised by more than one reviewer. 

**G1: The use of additional Hessian in (8b) and (11b).**

Thanks for raising this good question! Adding additional Hessian in the stationary metric and the update rule is actually the key of our algorithm design that enables GALET to converge for bilevel problem (BLP) with PL lower-level problems! 

First, the additional Hessian appears in (11b) because it is the gradient of $\mathcal{L}(x^k,y^{k+1},w)$. If we were to redefine $\mathcal{L}(x,y,w)$ in a different manner, say $w^\top\nabla_y f(x, y)+w^\top\nabla_{y y}^2 g(x, y) w$, this newly defined objective would not satisfy PL condition for non-positive definite $\nabla_{yy}g(x,y)$. Consequently, no existing algorithm could guarantee a global linear convergence rate. 

Second, as updating $w$ by the gradient of $\mathcal{L}(x,y,w)$ cannot guarantee that the null space component of $\nabla f(x^*, y^*)+\nabla_{y y}^2 g(x^*, y^*) w^*$, we project it to the kernel of Hessian of g, i.e., $\operatorname{Proj}\_{\operatorname{Ker}(\nabla_{yy}^2 g(x^*, y^*))}(\nabla_y f(x^*, y^*)+\nabla_{y y}^2 g(x^*, y^*) w^*)$ diminishes. Therefore, we adopt $\\|\nabla_{y y}^2 g(x^*, y^*)(\nabla_y f(x^*, y^*)+\nabla_{y y}^2 g(x^*, y^*) w^*)\\|\leq\epsilon$ in (11b) instead of $\\|\nabla f(x^*, y^*)+\nabla_{y y}^2 g(x^*, y^*) w^*\\|\leq\epsilon$. We prove it is still a necessary and tight condition for the stationary of BLO in Theorem 2. 

Finally, if $\nabla_{yy}g(x^*,y^*)$ is invertible (e.g., in the strongly convex lower-level setting), with and without additional Hessian are equivalent. 

**G2: Does $\lambda_g>0$ implies positive eigenvalue?**

No, it does not. The value of $\lambda_g$ is defined as as the lower bound of the minimal nonzero singular value of the Hessian matrix. Specifically, $\lambda_g=\inf_{x,y}\\{\lambda_{\min}^{\neq 0}(\nabla_{yy}^2g(x,y))\\}$, where $\lambda_{\min}^{\neq 0}(\nabla_{yy}^2g(x,y))$ refers to the smallest nonzero singular value of the Hessian. 

**It's important to differentiate the singular value from the definition of an eigenvalue.** For any matrix $A\in\mathbb{R}^{d\times d}$, singular values of $A$ are the square roots of the eigenvalue of $A^\top A$ so that they are always nonnegative. This is different from eigenvalues, which can be negative. 

As a result, the smallest nonzero singular value of the Hessian $\lambda_{\min}^{\neq 0}(\nabla_{yy}^2g(x,y))$ is always positive and $\lambda_g$ serves as the lower bound for a set of positive numbers, regardless of whether the eigenvalues are positive or nonpositive. Therefore, even if there are nonpositive eigenvalues, $\lambda_g>0$ can still hold. We will rephrase the sentences in the paper to reflect this.

**G3: The choices of $\alpha,\beta,\rho,c,N,\eta_1$.**

Due to the space limitation, we defer the choices of parameters in the Line 701 of Appendix. Let us define the condition number as $\kappa_1=\ell_{g,1}/\mu_{g}$ and $\kappa_2=\ell_{g,1}/\lambda_{g}$, we have
\begin{align*}
&\beta\leq\min\left\\{\frac{1}{\ell_{g,1}},\frac{c\mu_g^2}{16L_{F}\ell_{g,1}^2},\frac{c\ell_{g,1}^2}{\mu_g^2(L_{F}+2\ell_{g,1}L_w+c(L_g+\ell_{g,1}))}\right\\}={\cal O}(\min\\{\kappa_1,\kappa_2\\}), \\\\
&\alpha\leq \frac{\mu_g^2}{8c\ell_{g,1}^2}\beta={\cal O}\left(\frac{\min\\{\kappa_1,\kappa_2\\}}{\kappa_1^4\kappa_2^2}\right),\quad \rho\leq\frac{1}{\ell_{g,1}^2}, \quad c={\cal O}(\kappa_1^2\kappa_2^2), \quad\eta_1=2c\ell_{g,1} 
\end{align*}
where $L_w=\frac{\ell_{f,1}}{\lambda_g}+\frac{\sqrt{2}\ell_{g,2}\ell_{f,0}}{\lambda_g^2},L_{F}=\frac{\ell_{f,0}(\ell_{f,1}+\ell_{g,2})}{\lambda_g}$ and $N\geq 1$ is any constant. 

**G4：Can $w_0$ be initialized from other points?**

Thank you for this interesting questions which may help us extend our analysis. 

**$w^{0}$ can be other points other than $0$ as long as $w^{k,0}=w^0$ for any $k$.** Even though the limit point $\lim_{t\rightarrow\infty}w^{k,t}$ is not the minimum-norm solution $w^\dagger(x^k,y^{k+1})$, it is bounded and Lipschitz continuous because
\begin{align}\lim\_{t\rightarrow\infty}w^{k,t}&=w^\dagger(x^k,y^{k+1})+\operatorname{Proj}\_{\operatorname{Ker}(\nabla_{yy}^2 g(x^k,y^{k+1}))}(w^0)\\\\&=w^\dagger(x^k,y^{k+1})+(I-(\nabla_{yy}^2 g(x^k,y^{k+1})^\dagger \nabla_{yy}^2 g(x^k,y^{k+1}))w^0.
\end{align}
Clearly, the limit point $\lim_{t\rightarrow\infty}w^{k,t}$ is also bounded. Moreover, it is Lipschitz continuous since for any $x_1,x_2$ and $y_1,y_2$, we have
\begin{align*}
&\quad\\|w^\dagger(x_1,y_1)+\operatorname{Proj}\_{\operatorname{Ker}(\nabla_{yy}g(x_1,y_1))}(w^0)-w^\dagger(x_2,y_2)-\operatorname{Proj}\_{\operatorname{Ker}(\nabla_{yy}g(x_2,y_2))}(w^0)\\|\\\\&\leq \\|w^\dagger(x_1,y_1)-w^\dagger(x_2,y_2)\\|+\\|\nabla_{yy}^2 g(x_1,y_1)^\dagger\\|\\|\nabla_{yy}^2 g(x_1,y_1)-\nabla_{yy}^2 g(x_2,y_2)\\|\\|w^0\\|+\\|\nabla_{yy}^2 g(x_1,y_1)^\dagger-\nabla_{yy}^2 g(x_2,y_2)^\dagger\\|\\|\nabla_{yy}^2 g(x_2,y_2)\\|\\|w^0\\|\\\\&\leq \left(L_w+\frac{\ell_{g,2}\\|w^0\\|}{\lambda_g}+\frac{\sqrt{2}\ell_{g,2}\ell_{g,1}\\|w^0\\|}{\lambda_g^2}\right)\\|(x_1,y_1)-(x_2,y_2)\\|. 
\end{align*}
With the boundedness and Lipschitz continuity of limit points, we can prove the same convergence argument. 

Meta-review: This paper tackles the hard problem of bilevel optimization with a non-strongly convex inner problem.

The proposed algorithm is simple and natural, and its convergence is proven, obtaining the same rate as gradient descent in single-level optimization.

The main problem with this paper raised by rev.k2BT is the assumption that all eigenvalues of the hessian are either 0 or bounded away from 0. The authors claim in the original version that this is stronger than simply assuming that the eigenvalues are either 0 or positive and bounded away from 0, which is a classical assumption in several other papers.

However, by continuity, the two assumptions are the same; there cannot be a negative eigenvalue if the eigenvalues cannot change sign. The authors acknowledge this in the discussion. This assumption should, therefore, be rewritten in the final version, as well as the statement in l.277 "so that it 277 is weaker than [24]" which becomes false (although [24] has exactly the same bug in the assumption, the negative eigenvalues cannot suddenly become positive...). I also recommend that the authors clarify the notation regarding eigen / singular values, as this was a major source of confusion: singular values should not be written as $\lambda$.

This minor technical issue does not overshadow the merits of this paper: the problem tackled is hard, the contributions are original, the analysis is sound, and the experiments are conclusive.

Only Reviewer k2BT still advocates for the rejection of the paper; all other reviewers agree that the paper is worthy of acceptance. The concerns of Reviewer k2BT mostly revolve around the previous minor technical point. The authors have responded to these concerns in a convincing way, and the reviewer did not argue further with the authors and focused on this minor point in the reviewer's discussion.
Decision: Accept (poster)