An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization
Authors: Jincheng Cao
Ruichen Jiang
Erfan Yazdandoost Hamedani
Aryan Mokhtari
Venue: NeurIPS 2024 poster (2024)
Keywords: accelerated gradient methods
bilevel optimization
Primary area: optimization

Abstract: In this paper, we focus on simple bilevel optimization problems, where we minimize a convex smooth objective function over the optimal solution set of another convex smooth constrained optimization problem. We present a novel bilevel optimization method that locally approximates the solution set of the lower-level problem using a cutting plane approach and employs an accelerated gradient-based update to reduce the upper-level objective function over the approximated solution set. We measure the performance of our method in terms of suboptimality and infeasibility errors and provide non-asymptotic convergence guarantees for both error criteria. Specifically, when the feasible set is compact, we show that our method requires at most $\mathcal{O}(\max\\{1/\sqrt{\epsilon_{f}}, 1/\epsilon_g\\})$ iterations to find a solution that is $\epsilon_f$-suboptimal and $\epsilon_g$-infeasible. Moreover, under the additional assumption that the lower-level objective satisfies the $r$-th Hölderian error bound,  we show that our method achieves an iteration complexity of $\mathcal{O}(\max\\{\epsilon_{f}^{-\frac{2r-1}{2r}},\epsilon_{g}^{-\frac{2r-1}{2r}}\\})$, which matches the optimal complexity of single-level convex constrained optimization when $r=1$.

An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization
Jincheng Cao
Ruichen Jiang ECE Department UT Austin rj rjiang@utexas.cm edu
ECE Department UT Austin jinchengcaouutexas.ee edu
Erfan Yazdandoost Hamedani
Aryan Mokhtari
SIE Department
ECE Department
The University of Arizona
UT Austin
erfany@arizone azinyaaaii.oaa.. edu
mokhtari@auste utexas.ee.... edu
Abstract
In this paper, we focus on simple bilevel optimization problems, where we minimize convex smooth objective function over the optimal solution set of another convex smooth constrained optimization problem. We present a novel bilevel optimization method that locally approximates the solution set of the lower-level problem using a cutting plane approach and employs an accelerated reduce the upper-level objective function over the approximated solution set. We measure the performance of our method in terms of suboptimality and infeasibility errors and provide non-asymptotic convergence guarantees for both error criteria. Specifically, when the feasible set is compact, we show that our method requires at most (max (1/ Vef, 1/<g)) iterations to find a solution that suboptimmal and E, infeeasbbee. Moreover, under the additional assumption that the lower-level objective satisfies the r-th Hölderian error bound, we show that our method achieves
maddient-based update to
an iteration complexity of Ó(mxx(E, 2r-1 2r- }), which matches the optimal :Gg
complexity of single-level convex constrained optimization when
Introduction
In this paper, we investigate class of bilevel optimization problems known simple bilevel optimiza- tion, aiming to minimize an upper-level objective function over the solution set of corresponding lower-level problem. This class has recently gained attention due to its broad applications in contin-
ual learning [1, hyper-parameter optimization 2.3, meta-learning 4 [] and over parameterized machine learning [6-8). Specifically, we focus on the following bilevel optimization problem:
min f(x) XE
s.t.
x E argmin g(z),
zeZ
where, Z is a convex set, and f.g R" - R are convex, continuously differentiable functions on an open set containing Z. We assume that the lower-level objective function g is convex but not strongly convex, so the lower-level problem may have multiple optimal solutions. Throughout the paper, we use x" to denote an optimal solution of problem ① We define f - f(x") and g" g(x"), representing the optimal value of problem and the optimal value of the lower-level
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

Table I: Non-asymptotic results on simple bilevel optimization. (D: with a first-order Hölderian
error bound assumption on g; ①: with an rth-order (r 2 1) Hölderian error bound assumption on g;
A: additional assumption implying that the projection onto the sublevel set of f is easy to compute.)
Upper level
Lower level
Convergence
References
Objective f
Objective g
Feasible set
Upper level
Lower level
a-IRG 12
Convex, Lipschitz
Convex, Lipschitz
Closed
0(1/e))
o0/e)
Bi-SG 13
Convex, Nonsmooth
Convex, Composite
Closed
0(1e))
01/15) ). (0.5. 1)
SEA [4]
Convex
Convex, Smooth
Compact
((1/6))
o1/2)))
CG-BiO 6
Convex, Smooth
Convex, Smooth
Compuct
O(1/ey)
(
R-APM S
Convex, Smooth
Convex, Composite
Closed
O(1/er)
((1/e2))
AGM-BIO (Ours)
Convex, Smooth
Convex, Smooth
Compuct
0(1/49)
(11/s))
R-APM ! g
Convex, Smooth
Convex, Composite
Closed
01/49)
0(1/49))
Bisec-BiO A 15
Convex, Compasite
Convex, Composite
Closed
((max[1/e)
(1/,")
AGM-BIO ! (Ours)
Convex, Smooth
Convex, Smooth
Closed
0(1/49)
0(1/49
PB-APG !
16
Convex, Composite
Convex, Composite
Compact
00
+
-011/49)
AGM-BIO R (Ours)
Convex, Smooth
Convex, Smooth
Closed
0L1e7)
0(1/6)
objective y, respectively. This class of problems is referred to as the "simple bilevel problem" 9111 to distinguish it from more general settings with parameterized lower-level problems.
The main challenge in solving problem II is that the feasible set, i.c., the optimal solution set of the lower-level problem, lacks simple characterization and is not explicitly provided. This makes direct application of dnpectioonbbsed or projection- -ree methods infeasible, as projecting onto or solving a linear minimization problem over such an implicitly defined feasible set is intractable. Instead, our approach constructs an approximation set with specific properties, serving as a surrogate for the true feasible set. Section 3 we detail how this set is constructed. Using this technique and building on the projected accelerated gradient method, we establish the best-known complexity bounds for solving problem
To provide context, the best-known complexity bound for achieving an e-accurate solution in single- level convex constrained optimization O(E 0.5), as demonstrated in [17] This optimal bound was achieved using the accelerated proximal method or FISTA (Fast Iterative Shrinkage-Treeshldding Thresholding Algorithm),, which also influenced the development of our algorithm. While the literature on bilevel optimization is not as extensive as that for single-level optimization, there have been recent non- asymptotic results for solving this class of problems, which we summarize in Table [
Specifically, these results aim to establish convergence rates on the infeasibility gap g(xx) - g and the suboptimality gap f(xx) f after k iterations. In [12], an iterative reguaaizationn-asee method demonstrated convergence rate of (11/10.5-b) in terms of suboptimality and a rate of ((1/k²) in terms of infeasibility, where b E (0, 0.5) is user-defined parameter. Setting b = 0.25 to balance these rates requires an iteration complexity of O(max 1/e,, 1/c])) to find a solution that is E opptimal and eg inifeassiee Later, the Bi-Sub- nub-Gradient (Bi-SG) algorithm was proposed in [13 to address convex simple bilevel optimization problems with nonsmooth upper-level objective functions. showed convergence rates of (11/1' and 0(1 in terms of suboptimality and infeasibility, respectively, where a E (0.5. 1) serves as a hyper-parameter. Balancing the rates by setting a = 0.5 results in an iteration complexity of (max(11e), 1/2 Additionally, a structure- exploiting method introduced in 14 achieved an iteration complexity of ((mxx 1 1/22)) when the upper-level objective is convex and the lower-level objective is convex and smooth. Imposing additional assumptions on the upper-level function, such as smoothness or strong convexity, does not result in faster rates for this method.
Recently, 66 presented a projection-free free conditional gradient method (CG-BiO) that uses a cut- ting plane to approximate the solution set of the lower-level problem. Assuming both upper- and lower-level objective functions are convex and smooth, CG-BiO achieves a complexity of Ommax11 1/tg]). Since the suboptimality gap f(x)- - f" may be negative for an infeasible point x, more desirable metric is the absolute suboptimality gap [f()) - -f'l. To ensure this, [6] introduced the Hölderian error bound condition on g. Specifically, under the r-th order Hölderian
error bound condition, CG-BiO finds a solution & with [f()) -f I ef and g(x) -g S 6g

---

after O(max{1/ef. 1/Eg]) iterations. More recently, 8 introduced the regularized proximal ac- celerated method (R-APM), which runs the proximal accelerated gradient method on a weighted sum of the upper- and lower-level objective functions. Assuming both functions are convex and smooth, they established a complexity bound of ((max (1/e,, 1/Eg3) to find an (g), solution. This bound is worse than the O ( (1/ vEr, 1/ea3) complexity achieved by our proposed AGM- BiO method, assuming the feasible set Z is compact. Additionally, [8] showed that when the lower-level objective function 9 satisfies the weak sharpness property (equivalent
the Hölderian error bound condition with = 1), R-APM finds an (cr, -bbsolute optimal solution after at most O (maxx11/ y 1/ v iterations. This result is comparable to our convergence result for AGM-BiO, which considers a more general Hölderian error bound condition.
Contributions. In this paper, present novel accelerated gradient-base based bilevel optimization method, AGM-BiO, which offers state-of-the non-asymplotic guarantees for both suboptimality and infeasibility. At each iteration, AGM-BiO uses a cutting plane linearly approximate the solution set of the lower-level problem, followed by variant of the projected accelcrated gradient update on the upper-level objective function. Below, we summarize our theoretical guaaaalgggnn guarantees:
When the feasible set Z is compact, we show that AGM-BiO finds & that satisfies f(8)-f" S es and g(x) g Eg within (1 vēz, 1/Eg}) iterations, where f is the optimal value of problem I and g" is the optimal value of the lower-level problem.
With an additional r-th-order (r 2 1) Hölderian error bound assumption on the lower- level problem, AGM-BiO finds & satisfying f(x) f I cs and g(x) g" S Cg within 2m-1 2m-1
(maxxe Egg
}) iterations. Moreover, it achieves the stronger guarantee that
Is(x) l"l S of and g(X) - 0" S fg within O(max(<, 20-1 2r-1 Fgg
iterations.
These bounds all achieve the best-known complexity bounds in terms of both suboptimality and infeasibility guarantees for the considered settings. All the non-asymptotic results are summarized and compared in Table [
Discussions two concurrent works. The authors in 115 proposed a bisection algorithm with total operation complexity of (maxx{ 0.5 : .gg -..)))))) find an (e,, cypootmaall solution, assuming the upper-level objective ʃ meets specific criteria. Specifically, Assumption 1(iv) in [15] implies the ability to compute the projection onto the sublevel set of the upper-level function f. However, this assumption may not hold for general functions, such as the mean squared loss function in our over-pane wee--prameterizeed regression example in Section accelerated proximal gradient method (PB-APG) for solving simple bilevel optimization problems with the r-th order Hölderian error bound assumption on the lower-level objective g. Their algorithm, similar to g runs the accelerated proximal gradient method on a weighted sum of the upper and lower-level objective functions. PB-APG achieves complexity of O 0.5r) + O(e to find an (g -pptimal solution. The term ((1/eg-ár) can become significantly large as the order of the Hölderian error bound increases. In contrast, our algorithm, AGM-BiC avoids this issue, requiring
S In [16], the authors introduced the penalty-basel
at most (m 2r-1 2
}) iterations to achieve an (cfs Eg) -opttmll solution. Therefore, regardless of how large r is, the worst-case complexity for AGM-BiO is Ö(ma(f7 .55 1,5 1)) Thus, our method achieves better rate than PB-APG when > 1.
Cg
2
Preliminaries
In this section, we state the assumptions and introduce the notions of optimality used in the paper.
2.1
Assumptions and Definitions
We focus on the case where both the upper and lower-level functions f and are convex and smooth. Formally, we make the following assumptions
Assumption 2.1. Let ||- || be arbitrary norm on R. and ||+ be its dual norm. We assume these conditions hold:
(i) Z _ is convex and compact with diameter D, i.e., ||x yll S for all y E Z.
3

---

(ii) is convex and continuousty differentiable on an open set containing Z, and its gradient is for all x. Z.
Lg Lipschitz, i.e., [Vg(x) Vg(y))l- S -
l yll
(iii) f is convex and continuously differentiable and its gradient is Lipschitz with constant L
In this paper, we denote the optimal value and the optimal solution set of the lower-level problem as g" m (z)) and X _ argmin g()), respectively. By Assumption 2.1 the set X is nonempty, compact, and convex, but in general, not singleton since 9 could have multiple optimal solutions on 2, as is only convex but not strongly convex. Moreover, we use f to denote the optimal value and x" to denote optimal solution of problem ①
In the simple bilevel problem, the suboptimality of a solution measured by f(x) f", Similarly, its infeasibility is indicated by g(X) - -g" To ensure minimal suboptimality and infeasibility, we formally define an (e,, -,)ootii solution as follows.
Definition 2.1. ((E), Eg) -optimal solution). A point & Z is (E,, copotimal for problem ! if
f(x)- S Ef and g(x) -9" S cg.
This definition is commonly used in bilevel optimization literature 6-8 13
Due to the unique structure of bilevel optimization, it is not guaranteed that f(x) - f will always be positive. To address this, we propose using (f()) f as the absolute optimal criterion.
Definition 2.2. ((E),E)) (afreeg)aabblllaa -absolute optimal solution). A point & E is (e,, Eg) - optimal for
problem ① ffl) 1 Eg and lg(x) -g"l= S Eg.
3 Algorithm
Before presenting our method, we first introduce a conceptual accelerated gradient method for solving the simple bilevel problem in ① The first step is to recast it constrained optimization problem:
min
f(x)
s.t. X X
XER
where X2 A argmingez g(z) is the solution set of the lower-level objective. Conceptually, we
apply Nesterov's is accelerated gradient method (AGM) to achieve a rate of ((1/k²) on the upper-level objective f. Several variants of AGM have been proposed; see, e.g., [18. Here, we consider variant proposed in [19. It involves three intertwined sequences of iterates {xx |200 {y*))20, {Z ) k20 and the scalar variables {a2 and {Ax 1220 In the first step, we compute the auxiliary iterate yk
As by Yk An+an Xy. +
tat Zk.
ag
Then in the second step, we update Z by
Zk+1 Ix; (Zg ag ff(x)),
where Nxy (-) denotes the Euclidean projection onto the X Finally, in the third step, we compute As Xe + Actos Z++1 and A&+1 = A + ag- It can be shown that if the stepsize is Xk+1 Actos k+1, selected as dg = "Ly" then the suboptimality gap f(xx) - f(x*) of the iterates generated by the the optimal rate of (11/k²). In this case, indeed all the iterates
method above converges are feasible as it is possible to project onto the set X However, the conceptual method above not directly implementable for the simple bilevel problem considered in this paper, as the constraint set
Xg is not explicitly given. As a result projection onto the set X' is not computationally tractable.
To address this issue, replace the implicit set X in (3) with Xx, which can be explicitly char- acterized, making the Euclidean projection onto 2₂ feasible. Additionally, Xi must encompass the optimal solution set X Inspired by the cutting plane approach in (6), intersection of Z and a halfspace:
we define X's as the
Xx A ( Z: g(yx) + (V yv) S gm
Here, the auxiliary sequence {gk) A220 should be selected such that Ob 2 g" and 9 + g" One straightforward way to generate this sequence is by applying accelerated projected gradient method to the lower-level objective separately. The loss function of the iterates generated by this algorithm can be considered as {gx} for the above halfspace. Note that in this case, it is known that
2T. Ixn - 11
0 < gk - g" S
Vk Vk 2
(5)
(k + 1)2

---

Algorithm Accelerated Gradient Method for Bilevel Optimization (AGM-BiO)
1: Input: A sequence {gk K
scalar ? (0,
2: Initialization: Ag = 0, X Zo E Z
3: for k == O...., K do
4: Set
K+11 17,5
5: Compute
Yk
Aot
Al X3: +
Autax
Bt Zk
6: Compute
1x+1
xx (2x- on ()y))())) where
x A {z E Z :><yx) + (Vg(yx), yk) S gk
7: Compute
X = Actos
A Xx + B1
Aktax 1k+1
8: Update
Ak+1 Av + 0kk
9: end for
10:
Return: XK
Hence, the above requirements on the sequence {ma are satisfied. Two remarks on the set X₂ are in order. First, the set NE in (4) has an explicit form, making the Euclidean projection onto X3. tractable. It can also be verified that Xe always contains the lower-level problem solution set X2. To prove this, let X* be any point in X². By using the convexity of g. we obtain g(yx) + (Vg(y)), yu) S
g(**)= 9" S 9k- Thus, X satisfies both constraints in (4. s0 X* E Xg.
Now that we have identified an appropriate replacement for the set X we can easily implement variant of the projected accelerated gradient method for the bilevel problem using the surrogate set Nx.. We refer our method as the Accelerated Gradient Method for Bilevel Optimization (AGM-BiO) and its steps are outlined in Algorithm]] It is important to note that the iterates, when projected onto the set Xx, may not belong to the set X as A₂ is an approximation of the true solution set. Consequently, the iterates might be infeasible. However, the design of X's allows us to control the infeasibility of the iterates, as we will demonstrate in the convergence analysis section.
Remark 3.1.
The design of the halfspace as specified in (4) should recognized as a nuanced task. Various alternative formulations of halfspaces could fulfill the same primary conditions, such as {z E 2 ((xx) + (Vg(x;), ),, z Xx} S 9 and (z the selection of the gradient yı for constructing the halfspace is not arbitrary but essential characterize in the convergence analysis of our method.
g(zz) (Vy(zz): -2} S 9k). However,
Remark 3.2. How to project onto the set X ? In some cases, such as our over-parameterized regression problem, X is the intersection of an L2 ball and half-space, for which closed-form solution exists to find the projected iterates. In other cases, such as our linear inverse problem, we may not be able to find X3 directly. Instead, can solve the projection subproblem using Dykstra's projection
algorithm 20 In this case, an additional loop is needed to solve the subproblem.
3.1 Algorithm for the Composite Setting
While paper focuses on the smooth setting, our proposed method can be also extended to the composite setting. Let us consider the composite counterpart of Problem (
min [(x) [1(x) (x(
E argmin g(z) 91 (1()) + 92(2),
(6)
xER"
ZER"
where f1.91 R + IR are smooth convex functions and f2, R" + R are nonsmooth convex functions, respectively. To analyze and implement the proximal gradient- based methods, we need the following definition concerning the property of the proximal mapping.
Definition 3.1. Given h R + (-20, +ool and > 0. the proximal map of h is defined as
Prox,gh (x) A argmin uER"
||u x||2 + h(u)).
21
To handle the upper-level nonsmooth part f2, we change the projection step in Step 6 of Algorithm ] to proximal update, which is similar to the accelerated proximal gradient method for single-level problems in [1]].
5

---

Algorithm 2 Proximal Accelerated Gradient Method for Bilevel Optimization (P-AGM-BiO)
1: Input: A sequence {gk ) k= scalar ? (0,
2: Initialization: Ao = 0, X Zo E R"
for k ...... . K do
4: Set ak 4
Ak Xx + A& + a 2%
aj
5: Compute
y& Ax + ak
6: Compute
2k+1 = Prot (f2 t8x, (Zk - as V (y:)), where
N - {zE R" :91 (vx) + (Vgi(y)), ya) + g2(z) S gk}
Ak
a 2x+1
7: Compute
X As + ak
Xk +
As + a
8: Update
AR+1 = A& + Ok
9: end for
10:
Return: Xx
On the other hand, to deal with the lower-level nonsmooth part J2. is necessary to modify the approximated lower-level solution set Xx Specifically, we keep the linear approximation of the smooth part of the lower-level objective function 91 while adding the nonsmooth part 92 as lower bound of g to construct Xg. Note that the constructed set Xg is longer halfspace in this setting due to the possibly non-linear nature 92- We refer to our method as the Proximal Accelerated Gradient Method for Bilevel Optimization (P-AGM-BiO) and its steps outlined in Algorithm P
Different proximal-friendly assumptions are commonly used the literature composite single- level/bilevel optimization [5-77. The following proximal-friendly -riindlfrellyy assumption is necessary for our method in the composite setting.
Assumption 3.1. The function fo + 8x, in the Step 6 of Algorithm 2 is proximal-friendly, i.e. the proximal mapping in Definition 3.1 is easy to compute, where 8x (-) is the indicator function.
This assumption implies that f2 is proximal-frient friendly and that projecting onto the constructed set X can be done efficiently. Moreover, the function fz + 8x, is the sum of two convex functions, and the study of proximal mappings for such sums is dell-decu in the literature (21 Under this assumption, all analysis for the smooth case can extended to the composite setting. The details are B of the Appendix.
provided in Section
4 Convergence Analysis
In this section, we analyze the convergence rate and iteration complexity of our proposed AGM-BiO method for convex simple bilevel optimization problems. We choose the stepsize d4 inspired from our theoretical analysis. The main theorem is as follows,
k+1 which
Theorem 4.1. Suppose Assumption holds. Let {xx)<20 be the sequence of iterates generated by Algorithm 7 with stepsize ax AT., for k > 0 and suppose the sequence gt used for generating the cutting plane satisfies (5). Then, for any 2 we have,
k-1
(i) The function suboptimality is bounded above by f(xx) - f(x*) S 1L Xo-
klk+1)
(ii) The infeasibility term is bounded above by g(xx) g(x*) 4kallxo (n(++1) k(++l)
2L, D2 k+1
(iii) Farthermore, if the condition f(xx) 2 f(x*) holds, then the infeasibility term bounded above
by g(xx) 9(x*) < 8L, Xx xx xx" In(k+1)
x(++1)
Theorem 4.1 shows the upper-level objective function gap is upper bounded by O(1/k²), which matches the convergence rate the accelerated gradient method for single-level optimization prob- lems. On the other hand, the suboptimality of the lower-level objective which measures infcasibility

---

for the bilevel problem in the worst case is bounded above by O(1/k), In the case where f fxx)) > f- this upper bound improves to (1) As a corollary of the worst-case bounds, Algorithm will return an f, <g -optimal solution after at most the following number of iterations (max V }).
We should emphasize that, under the assumptions being considered, this complexity bound represents the best-known bound among all previous works summarized in Table []]
Remark 4.1 (The necessity of compactness of 2). For the lower-level objective, we show that La
Ax(g(x)) 9(x))) S Σ ai(:: g") + aL, Ex [4411 1 224 in Section A The main
challenge obtaining an accelerated rate of (11kk2 for g controlling Σ Zi+1 - z l1? Without a lower bound on f. this term cannot be bounded by the upper-level suboptimality alone. If fxxx 2 [xx*), we can achieve the rate of O (11/k²) for g. Otherwise, we use the compactness of Z to achieve (1/kk) for y. Please refer to Section A for more details.
Remark 4.2 (Removable log terms). The log terms in all the complexity results can be removed by choosing the auxiliary sequence gi = 9K for all 0 S & S K, which satisfies the condition (5). This climinates the log term in (24) and all subsequent results. However, this choice of {gr J220 requires predetermining the total number of iterations K.
Since the algorithm's 's output & may fall outside the feasible set x the expression f(x) f may not necessarily be non non-negative. On the other hand, under the considered assumptions, proving convergence in terms of [x( - i is known be impossible due to negative result presented by [25]. Specifically, for any first-order method and a given number of iterations k. they demonstrated
the existence of an instance of Problem [ where [xxx - f*I 2 for all 2 0. Thus, to provide any form of guarantee in terms of the absolute value of the suboptimality, i.e., If(x) f" we need
an additional assumption obtain lower bound on suboptimality and to provide convergence
bound for [x( - f'I. We will address this point in the following section.
4.1 Convergence under Hölderian Error Bound
In this section, we introduce an additional regularity condition on g to establish a lower bound for f(x) - ff" Specifically, we assume that the lower-level objective function g satisfies the Hölderian Error Bound condition, which governs how g(x) grows as x moves away from the optimal solution set Xz. Intuitively, since our method's s output x is cg opttmmll for the lower-level problem, it should be close to X2 under this regularity condition. We can then use this proximity and the smoothness property of f to establish lower bound for fxx)
Assumption 4.1. The function g satisfies the Hölderian error bound for some 0 and 2 1, i.e,
at dist (x, xz)) S g(x) - -g", VX E 2,
(8)
where dist (x, x;) e ex; ||x - x
We note that the Hölderian error bound condition in (8) is well-studied in the optimization literature
(26 and is known to hold in general when function g is analytic and the set Z is bounded [29].
There are two important special cases of the Hölderian error bound condition: 1) g satisfies (8) with
r 1 known as the weak sharpness condition 30 31; ; 2) g satisfies (8) with r 2 known as
the quadratic functional growth condition 32) By using the Hölderian error bound condition, established stronger relation between suboptimality and infeasibility,
shown next.
Proposition 4.2 (16) Proposition 1]). Assume that f is convex and g satisfies Assumption 4.7 and
define M maxxex; [x)] Then f(x) - f" - (((((())-g))) for any & E 2.
a
Hence, under Assumption 4.1 Proposition 4.2 shows that the suboptimality f(x) - f can also be bounded from below when x is an approximate solution of the lower-level problem. As a result, we can establish a convergence bound on [f(x)) f'1 by combining Proposition 4.2 with the upper bounds in Theorem 4.1 Moreover, it also allows us to improve the convergence rate for the lower-level problem. To prove this claim, we first introduce the following lemma which establishes an upper bound on the weighted sum of upper and lower-level objectives.
Lemma 4.3. Suppose conditions (ii) and (ii) in Assumption 2.7 hold. Let {xx be the sequence of k+1 iterates generated by Algorithm 7 with stepsize aj= = AAL,'' where 0 < < S 1. If the sequence 9k
7

---

used for generating the cutting plane satisfies (5). for any À 2 12/7-1)1, and k 2 0 we have
11
x(f(x)) f(x)) + g(xx) - g(xx)xxxx)))))r))) ) 5 41 Xo x"1 In(k: +1)
4AI, ||00 x 11?
(9)
k(k + 1)
>k(k +
This result characterizes and upper bound of (1) on the expression ((f(x))-(( [(xx)) g(xx)=
g(x"). That said, the first term this expression, a.k.a., {(f(x;) - f(xx))
may not be non-negative for a bilevel problem as discussed earlier. Hence, we cannot simply eliminate {(f(xx) f(x") to
show an upper bound of ((1/k²) on infeasibility, a.k.a., g(xx) g(x"). ). Instead, we leverage the Hölderian error bound the dependence on f in ( In this case, we can establish an upper bound on infeasibility.
and apply Proposition 4.2 to the first term. As result, we can eliminate
Theorem 4.4. Suppose conditions (ii) and (iit) in Assumption 2.7 hold and the lower-level function satisfies the Hölderian error bound with r>>, Let } be the iterates generated by Algorithm ! with stepsize 0ę- Y k+1,
'L," where = -1/(2, (2hg K + and K is the total number of iterations. Moreover, suppose the sequence Oh used for generating the cutting plane satisfies (5). we define the constants C2 a || - 112 Cg & 12Lg||xo - xx 112 and C & M()),, where M & maXxex; [()
and are the parameters in Assumption 4.1 then the following results hold:
(i) The function suboptimality is bounded above by
f(xx) (xx)) < Cg(In + 1)
C₁ K2
K I--I
(ii) The function suboptimality is bounded below by f(xx) - f(xx) 2 -C max
120,(tn) K + 1)) K
(2C,)²
(2C)
K²
K K
(iii) The infeasibility term is bounded above by
2C, (In K + +1)
2C
(2C)
g(xx) - g((x)= S max
K K
Before unfolding this result, we would like to highlight that unlike the result in Theorem the above bounds in Theorem (4.4)d not require the feasible set be compact. Since r 1, the first result shows f(xx ) - f(x") has an upper bound of Ō(( 1 K )=="r and the second result guarantees a lower bound of 5((( 1 I). These two bounds together lead an upper bound of Ō(( k ((())==²)) >
for the absolute error (xx) - fxx")) Moreover, the third result implies that the lower-level problem
suboptimality which measures infeasibility is bounded above by ((})) a
The previous result presented in Theorem 4.4 is applicable when r >> 1. However, for the case that 1st-order Hölderian error bound condition on 9 holds (i.e., weak sharpness condition), require distinct analysis and a different choice of y to achieve the tightest bounds. In the subsequent theorem, we present our findings for this specific scenario.
Theorem 4.5. Suppose conditions (ii) and (iii) in Assumption 2.1 are met and that the lower-level objective function g satisfies the Hölderian error bound with 1. Let { be the sequence of k+1, iterates generated by Algorithm ] with stepsize a₃: = "L4'' where 0 < 7 S min 20 1}. Moreover, suppose the sequence 9k used for generating the cutting plane satisfies (5). and recall M a maxxex; [x)] and a in Assumption 4.1 we define the constants C, - 4Ly||x0 - x*1 112
and C2 e &L x" 112, then for any k zz0 0:
C₁ (i) The function suboptimality is bounded above by f(xx) - f(x') < .K(K+IJ
(ii) The function suboptimality is bounded below by fxxx - f(x)) CyMiin k+1) GF
o J[(++T-
(ii) The infeasibility term is bounded above by g(xx) g(x") S Colnx+1) + 7MR(+I]
ac,
R(++1)
Theorem 4.5 shows that under the Hölderian error bound with r = 1, also known as weak sharpness condition, the absolute value of the function suboptimality (f(x)) - f(xx)) approaches zero at a rate
of (1/k²) ignoring the log term. The lower-level error g(xx) 9(x*), capturing the infeasibility
of the iterates, also approaches zero at a rate of (11k²). As a corollary, Algorithm returns an
(e c -absollute optimal solution after Ó(max Vep Ve. }} iterations.
8

---

11000
Infeas. time
(b) Subopt. vs. time
(c) Infeas. iterations
(d) Subopt. vs, iterations
Figure I: Comparison of a- a-I CG-BiO, Bi-SG, SEA, R-APM, PB-APG, and AGM-BiO for solving the over-parameterized regression problem.
Numerical Experiments
In this section, evaluate AGM-BiO method on two different bilevel problems using real and synthetic datasets. We compare its runtime and iteration count with other methods, including a-IRG [12]. CG-BiO 16). Bi-SG [13, SEA [14), R-APM (8) PB-APG [16], and Bisec-BiO [15].
Over-parrmeetrrized regression. We examine problem ① where the lower-level problem corre- sponds to training loss, and the upper-level pertains to validation loss. The objective is to minimize the validation loss by selecting an optimal training loss solution. This method is also referred to as lexico- graphic optimization [33] A common example of that is the constrained regression problem, where we aim to find an optimal parameter vector B E Bdd for the validation loss that minimizes the loss (3) over the training dataset Dr... To represent some prior knowledge, we constrain 33 to be in some subset Z C iRd c.g., Z = {3] 31 ... < 3a} in isotonic regression and Z = [ || S }} in Ip constrained regression. Without explicit regularization, an over- porr-arameterzzed regression over the training dataset has multiple global minima, but not all these optimal regression coefficients perform equally on validation testing datasets. Thus, the upper-level objective serves secondary criterion to ensure smaller error on the validation dataset Deal. The problem can be cast
min f(3) - (B)
s.t. B E argmin g(z) A (zr(2)
BERd
ZEZ
In this case, both upper-level and lower-level objectives convex and smooth if the loss & is smooth and convex. Since projections onto the sublevel set of f are difficult to compute, Bisec-BiO is excluded from this experiment.
We apply the Wikipedia Math Essential dataset 34 which composed data matrix E Raax with n 1068 samples and d 730 features and output vector R". We use 75% of the dataset as the training set (Atr: by.) and 25% as the validation set (A bval). For both upper- and lower-level loss functions,
use the least squared loss. Then the lower-level objective is
((3) = 2 A - b the upper-level objective is f(3) = 2 3 b l1ž, and the constraint set is chosen the unit Lzlball Z {3 || 1}. Note that this regression problem is over- parameterized since the number of features is larger than the number of data points in both the training set and validation set.
In Figures 1(a) and (c)), we observe that the three accelerated gradient-based methods (R-APM, PB-APG, and AGM-BiO) converge faster in reducing infeasibility, both in terms of runtime and number iterations. terms of absolute suboptimality, shown in Figures 1(b) and I(d), AGM-BiO achieves the smallest absolute suboptimality gap among all algorithms. Unlike the infcasibility plots, R-APM and PB-APG underperform compared to AGM-BiO. Note that the lower-level objective in this problem does not satisfy the weak sharpness condition, the regularization parameter 7) in R-APM is set as 1/(K + 1). Consequently, the suboptimality for R-APM converges slower than AGM-BiO, as suggested by the theoretical results in Table
Linear inverse problems. the next experiment, we concentrate on a problem that fulfills Hölderian Error Bound condition for some > 1. We aim to evaluate the performance of our method this specific context and verify the validity of our theoretical results for this scenario. Specifically, we focus the so-called linear inverse problems, commonly used to evaluate convex

---

(a) Infeas. (n = 3)
(b) Subopt. (n = 3)
(c) Infeas. (n = 100)
(d) Subopt. (n 1000
Figure 2:
Comparison of a-IRG, Bi-SG, SEA, R-APM, PB-APG, Bísec-BiO, and AGM-BiO for solving the linear inverse problem.
bilevel optimization algorithms, which originate from [35] The goal of linear inverse problems is to obtain a solution x E R" to the system of linear equation Ax = b. Note that if A is rank-deficient, there can be multiple solutions, or there might be no exact solution due to noise. To address this issue, we chase solution that has the smallest weighted norm with respect to some positive definite matrix Q, i.e. ||x|Qq == /x Qx. This problem can be also cast as the following simple bilevel problem:
min (x) xEX
[ 2
argming(2) (z) A Az b xEZ
For this class of problem, if Q, A, and b are generated randomly or by the "regularization tools" like [14 351, we are not able to obtain the exact optimal value f³. To the best of our knowledge, no existing solver could obtain the exact optimal value f for this bilevel problem. Specifically, the existing solvers either fail to solve this bilevel problem or return an inaccurate solution by solving they only reported the upper-level function value. However, in this paper, we intend to obtain the complexity bounds for finding (c,, (o)ottimalll and (cy, cybbolute optimal solutions. Without knowing f", we can not characterize the behavior of [x f Therefore, we choose an example where we can obtain the exact solution. Specifically, we set Q = I,, A A b 1. and the constraint set 2 = RT. In this case, the optimal solution x" 1,1, and optimal value === 1 minimum norm for an under-determined system. Note that the lower-level objective in this problem satisfies the Hölderian Error Bound condition with order
relaxed version of the problem. Hence, 14 35
2n This specific example essentially involves seeking the
[36]. Hence, we do not need the constraint set to be compact as shown in Theorem 4.4 Due to the unbounded nature of the constraint set. Frank-Wolfe-type Wolfe-type methods are not viable options. Consequently, we have opted not to incorporate CG-BiO in this experiment.
We explored examples with two distinct dimensions: n = 3 and n = 100, evaluating total of 2000 gradients. In Figures 2(a) and 2(c), AGM-BiO shows superior performance terms of infeasibility. In Figures 2(b) and 2(d), we compare methods in terms of absolute error of suboptimality. The gap between R-APM and AGM-BiO is smaller for n 3, but for = 100, AGM-BiO significantly outperforms all other methods, including R-APM. Since the regularization and penalty parameters in R-APM and PB-APG are fixed, they might get stuck at a certain accuracy level, as seen Figures 2(a) and 2(c). In contrast, AGM-BiO uses dynamic framework for minimizing the upper and lower-level functions, consistently reducing both suboptimality and infeasibility. Although Bisec-BiO theoretically has the best complexity results due to the ease of projecting onto the sublevel set of f. its performance in the last iteration is inconsistent, as shown in Figure
Conclusion
In this paper, we introduced an accelerated gradient- based algorithm for solving specific class of bilevel optimization problems with convex objective functions both the upper and lower levels. Our proposed algorithm achieves computational complexity of O(max 005 .251) }). When an additional weak sharpness condition is applied to the lower-level function g, the iteration complexity improves to Ō(max(e, .., .,,,5)), matching the well-known fastest convergence rate for single- level convex optimization problems. We further extended this result to an iteration complexity of 2r-1 2r-1
Ō Ōmaxxfe
.g when the lower-level loss satisfies the Hölderian error bound assumption.
10

---

Acknowledgements
The research Cao, R. Jiang, and A. Mokhtari is supported in part by NSF Grant 2127697 and the NSF AI Institute for Foundations of Machine Learning (IFML) at UT Austin. The research of E. Yazdandoost Hamedani is supported by NSF Grant 2127696.
References
[1] Zalán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for contin- ual learning and streaming. Advances in Neural Information Processing Systems, 33:14879 14890, 2020.
[2] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference Machine Learning, pages
PMLR, 2018.
[3] Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back- propagation for bilevel optimization. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1723-1732. PMLR, 2019.
[4] Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. Advances neural information processing systems, 32, 2019.
[5] Luca Bertinetto, Joao F Henriques, Philip HS Torr, and Andrea Vedaldi. Meta-learning with differentiable closed-form solvers. arXiv preprint arXiv:1805.081. 2018.
[6] Ruichen Jiang, Nazanin Abolfazli, Aryan Mokhtari, and Erfan Yazdandoost Hamedani. A conditional bradient-based method for simple bilevel optimization with convex lower-level problem. In International Conference on Artificial Intelligence and Statistics, pages 10305- 10323, PMLR, 2023.
[7] Jincheng Cao, Ruichen Jiang, Nazanin Abolfazli, Erfan Yazdandoost Hamedani, and Aryan Mokhtari. Projection-free methods for stochastic simple bilevel optimization with convex lower-level problem. Advances in Neural Information Processing Systems, 36, 2024.
[8] Sepideh Samadi, Daniel Burbano, and Farzad Yousefian. Achieving optimal complexity guarantees for a class of bilevel convex optimization problems. arXiv preprint arXiv:2310.1222 2023.
[9] Stephen Dempe, Nguyen Dinh, and Joydeep Dutta. Optimality conditions for a simple con- vex bilevel programming problem. Variational Analysis and Generalized Differentiation in Optimization and Control: In Honor of Boris Mordukhovich, pages 149-161, 2010.
[10) Joydeep Dutta and Tanushree Pandit. Algorithms for simple bilevel programming. Bilevel Optimization: Advances and Next Challenges, pages 253-291, 2020.
[11] Yekini Shehu, Phan Tu Vuong, and Alain Zemkoho. An inertial extrapolation method for convex simple bilevel optimization. Optimization Methods and Software, 36(1):1-19, 2021.
[12] Harshal Kaushik and Farzad Yousefian. A method with convergence rates for optimization problems with variational inequality constraints. SIAM Journal on Optimization, 31(3):2171- 2198, 2021.
[13] Roey Merchav and Shoham Sabach. Convex bi-level optimization problems with non-smooth outer objective function. arXiv preprint arXiv:2307.0824; 2023.
[14] Lingqing Shen, Nam Ho-Nguyen, and Fatma Kulmę-Karzang An online convex optimization- based framework for convex bilevel optimization. Mathematical Programming. 198(2):159- 1582, 2023.
[15] Jiulin Wang, Xu Shi, and Rujun Jiang. Near-optimal convex simple bilevel optimization with bisection method. arXiv preprint 4.21v:2402.05415. 2024.

---

[16] Pengyu Chen, Xu Shi, Rujun Jiang, and Jiulin Wang. Penalty-based methods for simple bilevel optimization under h) ((o} Iderian error bounds. arXiv preprint arXiv:2402.02/55, 2024.
[17] Amir Beck and Mare Teboulle. A fast iterative thrinkage-thresholdinn algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-203) 2009.
[18] Alexandre d' Aspremont, Damien Scieur, Adrien Taylor, et al. Acceleration methods. Founda- tions and Trends@ in Optimization, 5(1-2):1 2021.
[19] Paul Tseng. On accelerated proximal gradient methods for convex-concave optimization. submitted to SIAM J. Optim., 2008
[20] Heinz H Bauschke, Regina S Burachik, Patrick L Combettes, Veit Elser, D Russell Luke, and Henry Wolkowiez. Fixed-point algorithms for inverse problems in science and engineering. volume 49. Springer Science & Business Media, 2011.
[21] Yao-Liang Yu. On decomposing the proximal map. Advances in neural information processing systems, 26, 2013.
[22] Nelly Pustelnik and Laurent Condat. Proximity operator of sum of functions; application to depth map estimation. IEEE Signal Processing Letters, 24(12):1827-183) 2017.
[23] Heinz H Bauschke, Minh N Bui, and Xianfu Wang. Projecting onto the intersection of a cone and sphere. SIAM Journal on Optimization,
(1::)218821888 2018.
[24] Samir Adly, Loic Bourdin, and Fabien Caubet. On decomposition formula for the proximal operator of the sum of two convex functions. Journal of Convex Analysis, 26(2):699-718, 2019.
[25] Lesi Chen, Jing Xu, and Jingzhao Zhang, On bilevel optimization without lower-level strong convexity. arXiv preprint arXiv:2301.0077 2023.
[26] Jong-Shi Pang. Error bounds in mathematical programming. Mathematical Programming, 79(1-3):299-332, 1997.
[27] Jérôme Bolte, Trong Phong Nguyen, Juan Peypouquet, and Bruce Suter. From error bounds to the complexity of first-order descent methods for convex functions. Mathematical Programming, 165:471-507, 2017.
[28] Vincent Roulet and Alexandre d' Aspremont. Sharpness, restart and acceleration. Advances in Neural Information Processing Systems, 30, 2017.
[29] Zhi-Quan Luo and Jong-Shi Pang. Error bounds for analytic systems and their applications. Mathematical Programming, 67(1-)):-- 1994.
[30] James V Burke and Michael C Ferris. Weak sharp minima in mathematical programming. SIAM Journal on Control and Optimization, (1(5)) 1993.
[31] James V Burke and Sien Deng. Weak sharp minima revisited, part ii: application to linear regularity and error bounds. Mathematical programming, 104:235-261, 2005.
[32] Dmitriy Drusvyatskiy and Adrian S Lewis. Error bounds, quadratic growth, and linear conver- gence of proximal methods. Mathematics of Operations Research, 43(3):919 948, 2018.
[33] Chengyue Gong and Xingchao Liu. Bi-objective trade-off with dynamic barrier gradient descent. NeurlPS 2021, 2021.
[34] Benedek Rozemberczki, Paul Scherer, Yixuan He, George Panagopoulos, Alexander Riedel, Maria Astefanoaei, Oliver Kiss, Ferenc Beres, Guzmán López, Nicolas Collignon, et al. Pytorch geometric temporal: Spatiotemporal signal processing with neural machine learning models. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 4564-4573, 2021.
[35] Shoham Sabach and Shimrit. Shtern. first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640-660, 2017.
12

---

[36] Ion Necoara, Yu Nesterov, and Francois Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, 175:69-107, 2019.
[37] Andreï Nikolaevich Tikhonov and VIAK Arsenin. Solutions ill-posed problems. (No Title),
1977.
[38] Mikhail Solodov. An explicit descent method for bilevel convex optimization. Journal of Convex Analysis, 14(2):227, 2007.
[39] Mikhail V Solodov. A bundle method for class of bilevel nonsmooth convex minimization problems. SIAM Journal on Optimization, 18(1):242-259, 2007.
[40] Elias Helou and Lucas EA Simöes. e-subgradient algorithms for bilevel convex optimization. Inverse Problems, 33(5)005500,, 2017.
[41] Amir Beck and Shoham Sabach. A first order method for finding minimal norm-like solutions of convex optimization problems. Mathematical Programming, 147((-2):25-46, 2014.
[42] Yura Malitsky. Chambolle-pock and tseng's ss methods: relationship and extension to the bilevel optimization. arXiv preprint arXiv:1706.02660 page 3, 2017.
[43] Boris T Polyak. Introduction to optimization. 1987.
13

---

Appendix / supplemental material
A Proof of the Main Results
A.1 Proof of Theorem
To prove Theorem 4.1 we start with the following general lemma that holds for any choice of the step sizes {ax}-
Lemma A.1. Let { be the sequence of iterates generated by Algorithm | with stepsize as > 0
for k 2 O. Then we have
1 2x - x-11 (Ae(](Xx)) (=(e=((e(((xx)))
[(x")( + 1
Akt1 ()(x+1))) - s(()))
E1lz2 xx1²))
(10)
-2) || 2221
2Ax+1
2)
Ab+1 (g(x(())) - -((x') (x(x(x)) g(x')) S au (gt - -x(x)) + Loag
|| =xll? (11)
2Ac+1
Proof of Lemma A. Let be any optimal solution of ①T. We consider the upper-level objective f. Since f is convex, we have
f(yx) f(x") S (Vf(yk). - xx),, f(yx) - f(x)) = (Vf(yk). - Xx). (12)
Now given the update rule A As + ak. we can write
Ak+1 (J(yx) f(xx)) ( (f(xx) [(x*) ax([(y))) [xx)) An(s(y)) -((x)) (13)
Combining 12 and 13). we have
1f - f(x')) -
S <ax((V((x=)) x')) A AL(//(()))) xx))
(14)
(VV((v)), a&YA + As(y: - -xx) axx")
ag (Vf(y)), -xx).
where the last equality follows from the definition of yı- Furthermore, since f is smooth,, have
(x++11 S f(yx) + (VI(y)), X yu) + 1/ [|xx+t - y=1l..
2
(15)
If we multiply both sides of (15) by Ak+1 and combine the resulting inequality with 14 we obtain
A++1 f(x'(() A& (f(x)) - f(x)))
< (Vf(yk), x") + Ax+1 (Vf(y)), X4+1 - -yk) +
|
yxll2
2
Li
(16)
(Vf(y*), 2₁ ) + (V ffx)), Zb+1 -za) +
||
1
2A
Lya
az (V]())), 26+1 x") +
| 2x
2A
where we used the fact that as (2++1 2x,)
1k+1
(x++1 yk) in the first equality. Moreover, since
x* E Nr. we obtain from the update rule in
3
that
(Zk+1 Z₁ + ag fy(x)), x" Zk 2 0
V ff(x)) Z++1 >x) < (2++1 Z₁, x
zk+1)
(17)
1
1
0k V Zk+11 x²) S 124 x" x12
1k+11 - xx -x1 1|z111-2111 2x11a.
2
Combining (16) and 17 leads to
(Aa(f(xe) - f(x*)) + 1 +51 x²112)
A (f(x(1)) f(xx(()))))))))))) マ Zx+1 - x21
L Lia -1) ||zu+1 - 2x113
s 2 A
14

---

which proves the claim in (TO).
Next, proceed to prove the claim in 11 To do so, we first leverage the convexity of g which leads to
s(yx) g(xx) S (Vo(ye), xx).
(18)
Also, since g is Lg-smooth, we have
g(x++1) S 9(yx) + ( yu) + Lg
2 XK+1 -yxll
(19)
By multiplying both sides of (18) and (19) by A& and AR+1, respectively, and adding the resulted inequalities we obtain
A 1 g(yx)) (x((())) 9(xx))
AgARt1 ||xx+1
A (Vg(yk), Xk+1 yk) + A (Vg(yk). - -xa) +
yxll
2
= ak (Vg(yk), B6+1 2x) + A (Vg(y)),y= - -xx) + Lga's
2
1
2% 1|
2Ax+1
a (Vo(yn), Z6+1 ya) + 2A /k++1 2xl1?
where the first equality holds since au (Zx+1 Zu) = A&+1 (X++1 yk), and the second equality holds since ag (Zy- yk) As(ys xx). Lastly, by the definition of the constructed cutting plane,
we know that g(yx) + (Vg(ya), yk) S Ik for any z E Xx.- Hence, (Vg(yx), Z+++1 yx) is
upper bounded by gk (y%). Applying this substitution into the above expression would lead to the claim in
Now we are ready to prove Theorem 4.1
Proof of Theorem
4.1 To begin with, note that by our choice of os, we have
++1 and AR+1
(I: + 1)( + 2)
ak AL,
(20)
8Lf
Thus, it can be verified that L 1 A Then it follows from Lemma A.l that
Ast1
- -xx==)x)))x)))))))))))))))))))))
1
11 (A<(f(x)) - [(xx)) + 2 g122 xx11²)
2
(21)
LgaR
| - -xx1??
2A
2
Lg
( - -x(x))- (x(x(x)) - g(x*)) S a (gk - g(x*)) + 2A
|| 2xll². (22)
We first prove the convergence guarantee for the upper-level objective. By using induction on 21 we obtain that for any k: 2 0
1 -|z00 xx 112, (23)
(xx - f(x')((x)))))) + 2 ||z= - x11 <
- -((x))
+ - -x²112= =
2
which implies
||z0 1x1
41,51120 - 1x1
f(xx) f(x')
2A
k(k++] + 1)
We proceed establish an upper bound on g(xx) - gx(x)). By summing the inequality in (2 from
0 to k - 1 we obtain
Lg
A-1
As(g(x)) g(x*)) x
a:(9: -9")+ +
Σ
|z11 -
21
4Lg
i 2L - xx112
Lg k-1
Σ D²
(24)
+
4L,
(i+1)2
4LB i=0
1=
Lg l|x0
Lg D²
x" x1 k
+
2L
4L,
15

---

Note that the second inequality holds due to the condition in (5). Thus, we obtain
g(xx) =(x²)) 4Tgg X - x (1n +1
21 n2
+ k ++1
k(k+ +1
The above upper bound on g(xx) g(x)) without any additional condition, but next show that if f(xx) ) 2 f(x*) the above upper bound can be further improved as we can upper bound
E 2++1 zz by constant independent of & instead of kD2 To prove this claim, by summing the inequality in (10) from to h - we obtain
k-1
Σ
2:11 S
200 12 (A&(((x))-
((x)) l1ee - -x11²) (25)
4 1=0
Hence, if fxxx) 2 f(x'), then it holds
2:11² S 2||zo x²1 Zif1
(26)
Thus replace Σx=0 ||z
2:l in 24 by 2|
x" 1|? we would obtain the following improve
bound:
5 4Zg X
11 1)
41g 11z x²1 k + 1)
g(xx)- - g(xx)=
+1)+1)
Recall Remark 4.1 The main difficulty in obtaining an accelerated rate of (11/K2) for g is that unclear how to control E || zx.l². This, in turn, is because we don't 't know how to prove lower bound on f. Instead, we used the compactness of Z achieve the (1/KK) for g.
A.2 Proof of Lemma
Proof of Lemma 4.3 Note that by multiplying both sides of (10) by we have
X
A - f(x"))) |z - x=1 (A(()(((x)) f(xx)()))))))))))))){)))))))ff
" 1|z x x11²3
Lyak
-1) ||z+1
z
Ak+1
(27)
Further note that in this case we have og = 2( and AR+1 = 7 ()+++)
8L, Hence, og 02/AAg Ax41 is
aL,
bounded above by z.. Therefore, we can replace /
7 / As+1 in the above expression by 2L, to obtain
A f(xx))) | x²1
(AL(X(((E)) - -f(xx))) 2/1 IIz x²133
$ (2-1) ||zet1 - 2x112
(28)
Similarly, we can replace A//A in (IT by 7 obtain
21,
A A - g(xxxx))))))))))))) (g((x) g(x*) S (o - g(xx)) + 2Lg
2641 - 2x (29)
4L.
Note if we sum up the two inequalities above, we obtain
A
- f(xx)((xx))))))))))) g(xx+1) g(x²)) + |2x+1 - x11
- (AA(AC((s))- -xx)xxxxx)x))))))))))))()))))))) + g(xx)) - 9(x*)) + - 112 1x²112
(30)
S <(x2 1 } + 2 2مي | - 2111 + a (gx - g(x*)) S ax (gr g(x*))
IL.
16

---

Note that the last inequality holds since the first term is negative due to the choice of X. By summing the inequalities from obtain
k-1
1 >
1 211200 -x111 (31) -111 Σ -a g(xx)()))))))
Now using the condition gi in (5) and the definition of we have
k-1 Ea,(a s(x")) 2
7(1 + 1) 2L |xx - -x11
244 2h.
xo x (1 (32)
4T.5
(i+
By applying this upper bound into 31 we obtain
2hg 2h,
12
xx112
|x0=x"(((
21112o -x"1'
(33)
If we drop the 1 { x2
[2221 in the left-hand side and divide both sides of the resulted inequality by k(k+1)
Ag which is equal to A₁ = 7 8L,
we obtain
4Lg 1100 - x" 121 +1) + 42L ||20 - x=
x(f(x)) - f(x')) + g(xx) 9(x*) S
(34)
k(k +
rk(k:
and the proof complete.
A.3 Proof of Theorem
Proof of Theorem 4.4 Recall the result of Lemma that if az = =xkk++))/(AAp)) where 0 < S
and x 2 12/7-1)L;
Lg then after K iterations have
x(f(xk) f(x')) + g(xx) 9(xx)= 4Lg1 x" I [ +
4XL I|zo - 1x11 kK +1)
(35)
K(K +1)
Now if we replace by 1/( 2Ly K -ー + 2) as suggested in the statement of the theorem, we would obtain
A([(x)) - [(x"(x + g(xx) g(x")
4Lg1 Xu= - (Inn +1) +
81 Le K 2r-1
2r-2
+ +=) 2x11
-
(36)
K(K +1)
K(K +
Now we proceed to prove the first claim which is an upper bound on f(xx) - f(x"). Note that given the fact that g(xx) g(x") and À O we can show that
4Lg 4Lgg|x0 |Xo x" (Inn +1)
8(( K + 1))L,l1zo - x2
f(xx) f(x') <
+
(37)
AK(K 1)
K K(K +1
20-2 2 (2/7-1)) 1)br
we select À which a free parameter as = K
then we obtain
f(xx) - f(x)) 4I.g Xn - x" 1 K +1)
8Lgg|10 |20 x21
8L,1120 - x21
+
(38)
Ka-1 (T 11)
K K (T + 1)
K(K +1)
Given the fact that Zo we can simplify the upper bound to
f(xx) - f(x*) 12Lg|Ixo
x (In + 1)
8L, Zo - x21
(39)
K K
K2
Next, we proceed establish upper bound g(xx) g(x"), ). We will the following inequality that holds due to the HEB condition and formally stated in Proposition 4.2
f(xk) - fr 2 -M r(g(xx) g(x*)) )))
(40)
a
17

---

Now if we replace this lower bound into 36) we would obtain
(M( (g(xx)) ( g(x }} + g(*k) g(xx)
8(( 3= + 1))ALS |200 12
(41)
ALgl|x00 x (I + 11 K(K 11)+
K(K+
Next we consider two different cases: In the first case we assume (M (g(xx) - g(x*))+ v
(g(xx) 9(x))) holds and the second case we assume the opposite of this inequality holds.
If we are in the first case and (M(E)+(((K)) -(x*)) S (g((x)) 9(x*)), then the inequality
leads
2 (((xk) - g((x)) - 4gg xo x²1 II + +)
8(( K by
+ 1))ALs 1Z0 x"1
(42)
K(K +
K(K +
K 7 it further leads to the following upper bound
Since
g(xx) g(x") s Xo xx" (mn + 1)
16L (6Ly||zo 1x K(K +
16L Zo x=11
(43)
K(K + 1)
K
(K + 1)
Now given the fact that Xy Zo. obtain
x x" 121 +
16L ||x, - x211
g(xx) - 9((x)) <
+
(44)
K2
K Kar=t
2m
If we are in the second case and (g(xx))((x))) =(0(xx)-g(x') then this inequality equivalent
(g(xx) - -(x))) 5
(45)
leading to
(2)
g(xk) - g(xxxxx+x))))))"))) < 2K 22K 1 ~
(46)
K2
By combining the bounds in 44 and (46
we realize that
g(xK) - g(x') S max{ 24L Xo
| K +1)
16L, |xo - 1=1 (2. (9) -M
K2
K I
(47)
Finally by using the above bound in (47 and the result of Proposition claim and establish a lower bound on (xx) - f which is
4.2 we can prove the the second
f(xx) -
24T. |xo
121 In K +1)
16T,,11x0 x²1
(2M)
(2M)
1/r
- - maxt
K2
K 2"
K 2r
(48)
leading to
f(xK) - - (+)
(24Lg11x0 - x" (1n K + 1)
(16L, ||x -x0-x11131 1111//1/1 ((2M) = (1)= - 1/r
max
+
K2/r
K -
(49)
18

---

A.4 Proof of Theorem 4.5
Proof of Theorem 4.5 To upper bound f(x)) we follow similar analysis as in Theorem 4.1
Specifically, first note that by our choice of ag, we have ag = 7 k+1 and Ax+1 = 7 8ky
(x+1)( where
aL,
7 E (0, 1). Hence, we can obtain that T.yal S 3 AA++I- By using Lemma A.1 and the fact that
(0, 1), we have
A ((((xxx))--((x7 + 1z -x111 (A)((((())))) - -((x)) + 1 2/ - x 1p)
2
1 - |
zxl1 ===00 5..
By using induction, obtain that for any k 0
1
Ax(s(xx) - [(x"() + I1zs x" 112 2 Ao(s f(x'(()))
20 -x111
x x=1,,, (50)
2
1) and Zo Xo. this further implies that Since AІ = 8L,
f(xx) - f(x)) |zo x" 12
4L - x211
2AA
>k(kk + +)
Next, we will prove the upper bound on g(xx) - g(x"). By Lemma 4.3
we have for any k 2 0
((f(x)) ((x)) g(xx) g(xxxxx==)))))))))) 4Lg ||gg|>x X2 x21 (:k 1)
x" 1 /
(In + 1)
(51)
ck(k + 1)
Moreover, since g satisfies the weak sharpness condition, we can use Proposition
4.2 with
to
write
M f(xx) - f² 2 (g(xx) - g").
(52)
Combining (51) and (52) leads to
-X (g((x)) g(xx)) )) + g (xx) - x(x*)== S 4L - x=1 112
M
kik + (Ink+ 4XL, ||x0
x"1 *k(k: + +1)
(53)
Note that we can choose À to be any number satisfying 2 since
1)T. (cf. Lemma 4.3 Specifically,
S 2M 2Mbytaby' we can set À = a<(2M) and accordingly
20L,
(53) can be simplified to
g(xx) g(xxxxxxx)))))) 8Lg |x1 11
4aL, [x0 x²
(In
k-k 1)
71/k(k +1
Finally, we use
(52 again together with the above upper bound on gxxx) - g(x*) to obtain
M
-
(8MLg) Xo x²12
(In + + 4L, [xo xx x=1 21(h + 1)
- [(xx)-((x))
(xxx))-g(x*))
ak(k + 1)
B Extension to the Non-smothh/ompooste Setting
In this section, we would like to mention the possible extension to the non-smooth/ccmpposie setting. In the general non-smooth settings, we believe it is not possible to extend our results and achieve the purpose of the acceleration. This is because, even in the single-level setting, the best achievable rate in the general non- non-smooth setting is O /K) achieved by sub- sub-gradient method. That said, should be possible to extend our accelerated bilevel framework to special non-smooth setting where the upper- and lower-level objective functions have a composite structure, i.e., they can be written as the sum of convex smooth function and convex non-smooth function that is easy to compute its proximal operator.
Note that the properties of smoothness of and have only been used in the proof of Lemma A. in Section A None of the other results will break if (TO) and (T)) in Lemma A.T still hold in the composite setting. Now, present and prove the counterpart of Lemmal A.I in the composite setting.
19

---

Lemma B.1. Suppose f2. 91 92 are convex and f1, 91 are Ly and L smoothh respectively.
Let {xe} be the sequence of iterates generated by Algorithm with stepsize ag 0 for 2
Moreover, suppose Assumption 3.7 holds. Then we have
(f+1(((X++1) f(
2 2x -x11
x
(f((((x))) - f(x*)) + 22 z11lz xx1²)
(54)
Lyak
2 | =x/l
2Ax+1
Ak+1 (g(xx+)))) - gg(x")) Ax(g(xx) g(x")) S ax (gk g(xx)) + Lg 2
| zxll?. (55)
2Ax+1
Proof of Lemma B.1 Let x be any optimal solution of 6
We first consider the upper-level objective f. Since f1 is convex, we have
fi(yx) fi(x)) - (Vfi)y)), yk - -x)), fi(y)) fi(x)) S (V -xx). (56)
Now given the update rule Ak+1 A& + ag. we can write
1 1
- (fi(()))-i((t
- fi(x') = - + + A (xxx)) - -x)
- (57)
Combining (56) and (57). we have
( - (x(x)) - (xx) - si((x))
S
A xx))
(58)
= =VV)(()),, a&Yx As(yx -xx Xb) .xx")
an (yw),
where the last equality follows from the definition of yı. Furthermore, since S1 is smooth,, we have
(x++1) S (yx) + (y)), Xa+1 - ya) + L
X - yxll2.
(59)
2
If we multiply both sides of (59) by Ag+1 and combine the resulting inequality with (58) we obtain
As+1 (fi1(fi (f((x++1) fx(x)) )) - (x() - (x)))
S 0g (V.f( 2g x*) + Ak+1 (V Xk+1 - -yk)
|xx+1 - -
2
= 04 (V)) 2z x*) + a (V (yx): 2b+1 - -26) + L
(60)
|z
2/ 11
2Ax+1
-a (V)( Zo+1 x*) + Ly
|B - -2
2AR+1
where we used the fact that on [ 2x) AR+1 (xx+1 - yk)) in the first equality. Moreover, from the step 6 in Algorithm 2 we have 2₁ ag. V/ - 2k+1 E axx (x0(f2(2c+1) + 5x, (2++1)). Using this, from the definition of subgradients for f2 + 5x², we have
(x" 1 2s - ag (yr) - zx+1) < as (f2(xx)) ) + 6x, (x")= - f2((x+1)= - 8xx. (22+1))
(Z Zk + ax vf -z++1) fz (2x+1) az f2xf(xx") (x))
Og (V](y)), 2x+1 - -x)== S (26+1 - 22, x* - 2-1) (2x52(2x+1) + +xx[2(xx)
1
1
ag (Vf(yk), Zk+1 -x')= < 2
|zz -x"1' / ||xx11 - -x111
|zx+1 2/z 1|
a fz (2(+2)) + fxx2(xx).
(61
The first step holds since x", Zb+11 E X's i.e. 8x (xx) 5xx (Zx+1) 0. Combining (60) and 61 leads to
A++ 1 (fi (Xx+1) - fi (x())) + _ ||zet1 - x1122 (Al(fi(xe) - fi())) + 2 lz xx x'113)
(62)
1 Lyag
-1) || - 22112 - ax az + axfe(x").
< 2 Au+1
20

---

Then we add (A6+1f2(x*+11) -=xf2(xx)) Axf2(x))) on both sides to obtain,
AR+1 1f - f(x')(xx)))))))))))))))))))) + +) 10xx+11x1111
-x111 1 (Au(f(x)) - f(xx)) + 1
2 Z - x xx1)
(63)
$ 1 Ly Lyae -1)
||z+11 zkll² -xff(zx+1) AR+1f2(X(+1) - Ax5e(
Ak+1
Finally, by the convexity of f2. As+1 = A + ags and X
A Xx + Actog 1k+1. i.c. Au+oo -a=52(Z++1) + Ax+1/((xx+1) Ax)2(xx) S O. the first inequality of this Lemma can be obtained.
Next, proceed to prove the claim for the lower-level objective g. To do so, we first leverage the convexity of the smooth part 91 which leads to
91 (yx) 91 (xx) S (Vgi(y)). xx)
(64)
Also, since gi is by -mooth, we have
(xx+++1) S (y() + (Vgi(yk), Xx+1 yK) + Lg
||xx+1 -yall?
(65)
2
By multiplying both sides of (64 and (65) by A& and AR+1, respectively, and adding the resulted inequalities we obtain
A (x (1 + (4 - 91 (xxe)
AggA4+1
S AR+1
A (Vgi(N)).))) xx)
|x++1 -
T.ga
0g (Vgr(y*), Zk+1 21) + A (yx). xx) +
1,,+1 -zxl1
2Ax+1
L
=a (Vg) (yx) 244), ya) +
2AA+11 1z zzll
where the first equality holds since ag (zx441 2x)) Ak+1 (x&+1 Yk), and the second equality holds since (z yk) (y(y: X4). Lastly, by the definition of the constructed approxi- mated set Xt. we know that (yx) + (Vgi (yk), 2 -vx) + 92(z) S 9r for any z E Xz. Hence, (Vgi (yx), Ba+1 y& is upper bounded by 9b 91 (y&) 92(2x+1) Applying this substitution into to the above expression to obtain,
A (x)(1))))) 9)(())) (y( 91 (xx))
Lggg
(66)
Saa9k aggi a2g2 (2
Zk-11 Zz
2Ax+1
By adding aggi (yw) angl (x*) on both sides, we have,
Akt1 (g) (Xx+1) 91 (x")) Ax(gi(x') 91 (x(x))
aiggk 0xg1(x") axg2(Zx+1) Lg
(67)
|zx+1
Zz 2
2Ax+1
Lastly, we add (Ak- (x++1) xx Angz(xx)) both sides to obtain,
A (g(xx+1) - 9(x')) + Ax(g(x') o(xx))
Lg 2A
(68)
ax.ik axg(x") + AR+ 19+192(Xx+1) ARgz(xx)) a2gg2(244)) (2641)
2
1|
By the convexity of g2. A = Aş + axs and Xt-1 = As X₁. + Ao Ze+1 (outlined in Actoz
4
Algorithm 2. i.c. Ax+102(x441) - A 04g2(Zz41) S O, the second inequality of this Lemma can be achieved.
Hence, with the additional Assumption 3.1 by replicating the analysis outlined in Section A we can derive identical complexity results for Algorithm 2 in either the compact domain setting or with the Hölderian error bounds on g.
21

---

C
Additional related work
Previous work has explored "asymptotcc"" results for simple bilevel problems, dating back to Tikhonov- type regularization introduced in [37]. In this approach, the objectives of both levels are combined into a single-level problem using regularization parameter a > 0 and as a - the solutions of the regularized single-level problem approaches solution to the bilevel problem in T.. Further, the authors in [8 proposed the explicit descent method that solves problem (T) when upper and lower-level functions are smooth and convex. This result was further extended to non-smooth setting
in [39]. The results in both [38] and [39] only indicated that both upper and lower-level objective functions converge asymptotically. Moreover, the authors in [40] proposed the e-subgradient method to solve simple bilevel problems and showed its asymptotic convergence. Specifically, they assumed the upper-level objective function to be convex and utilized two different algorithms, namely, the Fast Iterative Bilevel Algorithm (FIBA) and Incremental Iterative Bilevel Algorithm (IIBA), that consider smooth and non-smooth lower-level objective functions, respectively.
Some studies have only established non-asymptotic convergence rates for the lower-level problem. One of the pioneering methods in this category is the minimal norm gradient (MNG) method, introduced in 41. This method assumes that the upper-level objective function smooth and strongly convex, while the lower-level objective function is smooth and convex. The authors showed that the lower-level objective function reaches an iteration complexity of (()/e²). Subsequently, the Bilevel Gradient SAM (BiS-SAM) method was introduced in [35] and it was proven to achieve complexity of (1//e) for the lower-level problem. similar rate of convergence was also attained in
42
D Connection with the Polyak Step Size
In this section, we would like to highlight the connection between our algorithm's 's projection step (outlined in Step 6 of Algorithm[]] [ and the Polyak step size. To make this connection, we first without loss of generality, replace Ol: with g² . is a reasonable argument, as gk: values are close to g", point highlighted in (5). In addition, we further assume that the set 2 = IR to simplify the expressions. Given these substitutions, the projection step in our AGM-BiO method equivalent to solving the following problem:
min |X 1x-1 s.t. g(xx) + (Vg(xe), xx.) g
In other words,X is the unique solution of the above quadratic program with a linear constraint. By writing the optimality conditions for the above problem and considering the Lagrange multipliers associated with the linear constraint, we obtain that
X++1 X Vx((x) A(g(xx) + (Vg(x)), X X&) -x)-9")) =0 120
g-))
Given the fact that X++11 * Xx. we can conclude that À * 0, and hence we have
X = X - (xxx))
g(xx) + (Vg(x)), X - -xa) -g" =
A >>0
By replacing X the second expression with its expression in the first equation we obtain that
x<x) g"
V
which is exactly the Polyak step size in the literature 433 To solve a bilevel optimization problem, we intend to do gradient descent for both upper- and lower-level functions. Tuning the ratio of upper- and lower-level step size is generally hard. However, by connecting the projection step with the Polyak step size, we observe that the stepsize for the lower-level objective auto-selected as Polyak stepsize in our method. In other words, it is one of the advantages of our algorithm that we do not need to choose the lower-level stepsize or ratio of the upper- and lower-level stepsize theoretically or empirically.
22

---

E Experiment Details
In this section, we include more details of the numerical experiments in Section 5 are implemented using MATLAB R2022a on PC running macOS Sonoma with an Apple M1 Pro chip and 16GB Memory.
All simulations
E.1 Over-parametrized Regression
Dataset generation. The original Wikipedia Math Essential dataset 34 composes data matrix of size 1068 731. We randomly select one of the columns as the outcome vector b E IR 181068 and the rest to be a new matrix A E IR 1068 x 730 We set the constraint parameter À = 1 in this experiment,
i... the constraint set is given by Z {3 ||]| - 1}.
Implementation details. To be fair, all the algorithms start from the origin as the initial point. For our AGM-BiO method, set the target tolerances for the absolute suboptimality and infeasibility to é = 10- and Eg = 10-4, respectively. We choose the stepsizes as d₃ = 10 2(k + 1)L In each iteration, which has closed-form solution. For a-IRG, we set ? = 10-3 and 7o = 1003 For CG-BiO, obtain initial point with FW gap of the lower-level problem less than / x 10-5 and set 77 10-2/(k 1) 1,0075 and f = 1/
need to do projection onto intersection of L2-ball and halfspace,
choose stepsize " 10 2 (k: 2). For Bi-SG, 1/ A/Amaz (A,, A.r) 1.5 10 4. For SEA, we set both the lower- and upper-level stepsizes to be 10 4, For R-APM, since the lower-level problem does not satisfy the weak sharpness condition, we set 1/ + 1) 1.25 x 10-5 and y 10 < 1/(L, nL For PB-APG, set the penalty parameter y 10 Note that the lower-level problem in this experiment does not satisfy Höderian error bound assumption, so there no theoretical guarantee for PB-APG.
F,2 Linear inverse problems
Dataset generation. We set Q = L. A A= 1,, and b = =0 1. The constraint set is selected as Z = R We choose low dimensional (n = 3) and a high dimensional (n 100) example and run K = 103 number of iterations to compare the numerical performance these algorithms, respectively.
Implementation details. To be fair, all the algorithms start from the same initial point randomly chosen from RT. For our AGM-BiO method, we set the stepsizes as dg > 1)/(4g,), where
= 1/4 22/33 + 2) as suggested in Theorem 4.4 In each iteration, we need to project onto an intersection of halfspace and RT. Since halfspaces and I2 are both convex and closed set, the projection subproblem can be solved by Dykstra's 's projection algorithm in (20). For a-IRG, we set No 10 and % 10-2 For Bi-SG,
=
set 77&- = 1/(k- 1)0.76 and t = 1/L.- For SEA, set the lower-level stepsize to be 10-2 and the upper-level stepsize to be 10-2 For R-APM, since the lower-level problem does not satisfy the weak sharpness condition, we set = = + 1) and 7 = 1/ + r) For PB-APG, we set the penalty parameter 10 For Bisec-BiO, we choose the target tolerances to ef = 6g = 10-4. For comparison purposes, we limit the maximum number of gradient evaluations for each APG call to 102. In this experiment, L, = 1 and Lg = n, where n is the number of dimensions.
23

---

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

---

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

---

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

---

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

---

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

---

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


Reviews:
[{"review_id": "0xdhBQvz5Z", "reviewer": "Reviewer_R6Rr", "summary": "This work proposes an accelerated method to solve convex simple bilevel problems, with the author providing both theoretical and numerical guarantees of the algorithm's convergence.", "questions": "- What is the convergence rate without using the accelerated gradient method, relying only on the projection onto the cutting plane?\n  \n- Since the accelerated gradient method has been well studied recently, what is the unique challenge of applying it to simple bilevel problems?\n  \n- Will this algorithm demonstrate any advantage in convergence without the assumption of the Hölderian error bound?\n  \n- How do you find a feasible $X_k$​ in practice? Is an additional loop required to achieve this?", "limitations": "No Limitation", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This work makes a theoretical contribution to the convergence analysis, and the algorithm demonstrates an advanced convergence rate under the Hölderian error bound.\n  \n- The analysis are detailed and concrete. The whole work is easy to follow.", "weaknesses": "Since the main techniques in this work, such as the accelerated gradient method and the cutting plane approach, have already been studied, the contribution of the proposed methods is incremental, and the convergence rate may not be difficult to prove based on existing studies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and valuable questions!\n\n**R.** \nTo address your concern in the weakness section, please refer to our answers to your first two questions. As stated in A1, the non-accelerated version of the projection-based algorithm yields unsatisfactory results. Thus, the accelerated gradient method is essential and significantly improves the convergence rates. In A2, we emphasize that constructing the correct approximated set is not as straightforward as in [6]. It requires a careful selection of the norm vector of the half-space, which can be interpreted as the descent direction of the lower-level objective $g$.\n\nFurthermore, the proof of the convergence results differs from that for the single-level counterpart. Specifically, in the proof of the main descent Lemma A.1, we employed different potential functions for the upper- and lower-level objectives, carefully selected the coefficients $A\\_k$ and $a_k$, and utilized the properties of the constructed approximated set several times. In Lemma 4.3, we characterized the convergence rate by considering a weighted sum of the upper- and lower-level functions. We then presented our formal theorems under the Hölderian error bound by selecting the appropriate weight. However, this weight does not appear explicitly in the algorithm, as it can be controlled by the step size.\n\n---\n**A1.** \nThat is a great question. Our initial idea was to develop a projection-based algorithm without using the acceleration technique to solve simple bilevel problems. However, the non-accelerated version of the algorithm did not produce satisfactory results. Specifically, it achieves $\\mathcal{O}(1/K)$ for the upper-level objective but fails to provide any convergence guarantee for the lower-level objective. On a related note, we would like to mention that a recent work [Devanathan and Boyd (2024)] proposed the Alternating-update Polyak Minorant Method (PMM), which is similar to the non-accelerated simple bilevel algorithm relying only on the cutting plane. It involves projecting onto the approximated sublevel sets of the upper- and lower-level objectives alternatively, assuming $f^{\\*}$ is known. However, they only provide asymptotic convergence without any rate guarantees under common assumptions.\nTo some extent, this also demonstrates the challenge of solving simple bilevel problems and the complexity of integrating the cutting plane technique with projection-based methods. \n\n---\n**A2.**\nA naive implementation of AGM for simple bilevel optimization requires access to the lower-level solution set $\\mathcal{X}_g^\\*$, which is typically not available in closed form. Therefore, one must either use regularization by mixing the two objective functions or approximate the lower-level solution set. \n\nThe former approach, as studied by [8], involves determining a proper regularization parameter, which is challenging in practice and only provides a $\\mathcal{O}(1/K)$ convergence guarantee on both levels without further assumptions even with the accelerated gradient method.\n\nFor the latter approach, the design of the approximated lower-level solution set $\\mathcal{X}_k$ is a nuanced task. If we project onto a set much larger than $\\mathcal{X}_g^{\\*}$, then the iterate may deviate from the optimal solution set, leading to a large error for the lower-level objective. \n\nFurthermore, as we mentioned in Remark 3.1, there are three intertwining sequences $\\\\{x_k\\\\}$, $\\\\{y_k\\\\}$, and $\\\\{z_k\\\\}$ in AGM, and depending on where we linearize the objective function, various alternative formulations of halfspaces could contain the optimal solution set of the lower-level problem $\\mathcal{X}_{g}^{\\*}$, such as $\\\\{z \\in \\mathcal{Z}: g(x_k) + \\langle\\nabla g(x_k), z-x_k\\rangle \\leq g_k\\\\}$ and $\\\\{z \\in \\mathcal{Z}: g(z_k) + \\langle\\nabla g(z_k), z-z_k\\rangle \\leq g_k\\\\}$. However, our choice of using the gradient at $y_k$ to construct the halfspace is not arbitrary but essential for showing convergence guarantees for the lower-level objective. \n\nFor single-level optimization problems, we can project onto the feasible set in each iteration to keep all the iterates feasible. However, for simple bilevel optimization, the feasible set $\\mathcal{X}_g^{\\*}$ may not have an explicit form. By projecting onto the approximated set $\\mathcal{X}_k$, the iterates could be infeasible, introducing additional error in the lower-level objective convergence analysis. As a result, the condition that $f(x_k) \\geq f^{\\*}$, which always holds in single-level problems, can be violated in bilevel problems. This also leads to challenges in our convergence analysis, and we cannot achieve the desired results for the lower-level objective unless $f(x_K) \\geq f^{\\*}$.\n\n---\n**A3.**\nAs we showed in Table 1, without the Hölderian error bound assumption, our method achieves the complexity $\\mathcal{O}(\\max(\\frac{1}{\\epsilon_f^{0.5}}, \\frac{1}{\\epsilon_g}))$, which is better than the others under similar settings.\n\n---\n**A4.**\nThe constructed set $X_k$ has an explicit form, i.e.,  $X_k \\triangleq \\\\{ z \\in \\mathcal{Z}: g(y_k)+\\langle \\nabla g(y_k),z-y_k \\rangle \\leq g_k\\\\}$, which always contains the lower-level problem solution set $\\mathcal{X}_g^*$ (the feasible set of the upper-level problem) as stated in line 154-158.\n\nHow to project onto the set $X_k$ is another question you may be interested in. In some cases, such as our over-parameterized regression problem, $X_k$ is the intersection of an $L_2$ ball and a half-space, for which a closed-form solution exists to find the projected iterates $z_k$. In other cases, such as our linear inverse problem, we may not be able to find $z_k$ directly. Instead, we can solve the projection subproblem using Dykstra's projection algorithm [43], as mentioned in line 701. For this scenario, an additional loop is needed to solve the subproblem.\n\n---\nReference:\n- Devanathan, N. and Boyd, S., 2024. Polyak Minorant Method for Convex Optimization", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "et3KRN64fC", "reviewer": "Reviewer_B2N7", "summary": "The paper introduces a new algorithm called AGM-BiO (Accelerated Gradient Method for Bilevel Optimization) for solving simple bilevel optimization problems where both the upper and lower level objectives are convex and smooth.", "questions": "-", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and easy to follow. The assumptions are clearly stated. The dependence of the convergence rates on everything seems to be explicitly written out.\n\n2. The proposed algorithm seems to be easy to implement, and it achieves the best-known complexity bounds for both suboptimality and infeasibility in the considered settings.\n\n3. Experiments are conducted to validate the strength of the proposed algorithm.", "weaknesses": "You provide a modified algorithm (Algorithm 2) that could potentially handle this composite structure. In line 629-line 631 you mention that you can derive identical complexity results for Algorithm 2 in either the compact domain setting or with the Hölderian error bounds on g. I guess formally stating the convergence result in a theorem would strengthen the paper and provide a clear reference point for readers interested in the composite case.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comment and the positive feedback!\n\n**W. You provide a modified algorithm (Algorithm 2) that could potentially handle this composite structure. In line 629-line 631 you mention that you can derive identical complexity results for Algorithm 2 in either the compact domain setting or with the Hölderian error bounds on g. I guess formally stating the convergence result in a theorem would strengthen the paper and provide a clear reference point for readers interested in the composite case.**\n\n**R.**\nAs we mentioned in the Appendix B, Algorithm 2 designed for proximal setting can achieve the same results as Algorithm 1 in either the compact domain setting or with the Hölderian error bounds on g. The major difference lies in the main Lemma A.1. Therefore, we provided a detailed proof of a new Lemma B.1 for the composite setting. By replacing Lemma A.1 with Lemma B.1, all the proofs in our paper will hold. As the reviewer suggests, we will add the formal theorems for the composite setting in the revised version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ANcy1xzIeB", "reviewer": "Reviewer_1z4b", "summary": "The paper works on the problem of simple convex smooth bilevel optimisation, where ''simple'' means single-variable. The paper achieves the optimal rate for this problem by a combination of Nesterov's acceleration and Jiang-Abolfazli-Mokhtari-Hamedani's cutting-plane method.", "questions": "QUESTIONS. \n\nWhat limitations do the authors anticipate in extending this technique (acceleration + cutting-plane) to the non-simple case (i.e., when you have an additional variable $y$ in the upper level objective, defined as the optimizer of a parametrized lower-level problem).", "limitations": "N/A since it's a theory paper", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "STRENGTHS. \n\n1. The paper achieves an optimal rate for an important problem class. \n\n2. The paper is very well-written.", "weaknesses": "-", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank the reviewer for the insightful question!\n\n**Q1. What limitations do the authors anticipate in extending this technique (acceleration + cutting-plane) to the non-simple case (i.e., when you have an additional variable in the upper level objective, defined as the optimizer of a parametrized lower-level problem).**\n\n**A1.** First of all, most of the work on general bilevel problems requires strong convexity for the lower-level function. In the case of the simple bilevel problem, this assumption would make the feasible set a singleton, rendering the problem trivial since it would amount to solving the lower-level problem only.\n\nThe general bilevel problem, when featuring a convex lower-level problem, is widely recognized as challenging in its most generic form. In this case, the optimal solution set of the lower-level problem will change as the upper-level variable changes with each iteration. Specifically, following a similar construction of the half-space, we cannot ensure that our constructed set always contains the optimal solution set of the bilevel problem, which is a key property in our proof. Therefore, to enhance computational tractability and adapt our framework to address the general bilevel problem effectively, we may need to introduce some additional assumptions, which is a compelling direction for future research.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NThzbP2Uef", "reviewer": "Reviewer_fv8w", "summary": "This work proposes a novel optimization algorithm with improved iteration complexity for convex smooth simple bilevel optimization, and demonstrates its faster convergence using experiments.", "questions": "(1) In line 27, you may write down the math formulation for ``more general settings with parameterized lower-level problems'', or refer this formulation to appendix. \n\n(2) How did you obtain Eq. (5), the condition about $g_k$? How to guarantee Eq. (5) in implementation with unknown $g^*$, $x^*$, $L_g$? \n\n(3) Does Lemma 4.3 require Assumption 4.1? If yes, add Assumption 4.1 to Lemma 4.3.", "limitations": "In the checklist, the authors mention their limitation of compact domain assumption. There is no societal impact of this theoretical work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The presentation is very clear. The literature review looks comprehensive. The algorithm and complexity results look reasonable.", "weaknesses": "This work focuses on simple bilevel optimization with both levels being convex and under deterministic setting (with access to full gradients instead of stochastic gradients), so the scope is not wide. Also, as shown in Table 1, the complexity results outperform existing ones only a little since the complexity order is the same as [8] for $r=1$, and the complexity dependence on $\\epsilon_g^{-\\frac{2r-1}{2r}}$ is worse than $\\epsilon_g^{-0.5}$ in [16].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and great questions!\n\n**W. This work focuses on simple bilevel optimization with both levels being convex and under deterministic setting (with access to full gradients instead of stochastic gradients), so the scope is not wide. Also, as shown in Table 1, the complexity results outperform existing ones only a little since the complexity order is the same as [Samadi et al. (2023)] for $r = 1$, and the complexity dependence on $\\epsilon_{g}^{-\\frac{2r-1}{2r}}$ is worse than $\\epsilon_{g}^{-0.5}$ in [Chen et al. (2024)].**\n\n**R.** \nWe would like to mention that most of the prior works focus only on either deterministic setting or stochastic setting, as the algorithms designed for one of the settings are not easy to be extended to the other setting. One of the works in stochastic simple bilevel optimization is [Cao et al. (2023)]. The strategy in [Cao et al. (2023)] is designed to manage the errors between the actual gradients and their estimates, as well as the errors between the true function values and their estimates. This methodology could be adapted for our AGM-BiO algorithm. However, we are uncertain if such an extension would lead to an acceleration. Another challenge lies in selecting appropriate gradient and function value estimates, crucially impacting the sample complexities based on the errors between the actual gradients and their estimates. Therefore, adapting our algorithm to the stochastic setting requires a careful choice of these estimates and a comprehensive convergence analysis. Indeed, this presents a compelling direction for future research. \n\nUnder the Hölderian error bound assumption, our result is the same as the result in [Samadi et al. (2023)] when $r = 1$. However, [Samadi et al. (2023)] did not provide any results for $r > 1$. Note that [Chen et al. (2024)] is a concurrent work. The convergence rate in [Chen et al. (2024)] is $\\mathcal{O}(\\epsilon_{f}^{-0.5r}) + \\mathcal{O}(\\epsilon_g^{-0.5})$, while our convergence rate is $\\mathcal{O}(\\max(\\epsilon_{f}^{-\\frac{2r-1}{2r}},\\epsilon_{g}^{-\\frac{2r-1}{2r}}))$. If $\\epsilon_f = \\epsilon_g$, our rate is better than theirs. Only when $\\epsilon_g < \\epsilon_f^{r/2}$, their result is better than ours. Furthermore, their results require the Lipschitz continuity of the upper-level objective (Assumption 2.1.1 in [Chen et al. (2024)]) and the compactness of the domain (a hidden assumption of Lemma 3.2 in [Chen et al. (2024)]), whereas our results under the Hölderian error bound assumption do not require either of these conditions.\n\nWe will add a remark about the above discussion to the revised paper. Thanks for your feedback.\n\n---\n\n**Q1. In line 27, you may write down the math formulation for 'more general settings with parameterized lower-level problems', or refer this formulation to appendix.**\n\n**A1.** \nThanks for pointing this out. We will add a formulation for the general bilevel problem in our revised vision.\n\n\n---\n\n**Q2. How did you obtain Eq. (5), the condition about $g_k$? How to guarantee Eq. (5) in implementation with unknown $g^{\\*}$, $x^{\\*}$, and $L_g$?**\n\n**A2.** \nAs we mentioned in line 151, we can generate this sequence $ \\{ g_k \\} $ independently from the main algorithm by applying an accelerated projected gradient method to the lower-level problem $\\min_{z\\in \\mathcal{Z}}~g(z)$. The Eq. (5) is the convergence result of the accelerated projected gradient method for solving the single-level problem [Nesterov (2018)]. To perform the single-level accelerated gradient method on $g$, we do not need to know the $g^\\*$ and $x^\\*$. Note that $g$ has to be convex and $L_g$-smooth to guarantee the Eq. (5) holds which are also the assumptions of our method. Hence, given our assumptions, we are able to generate a sequence $g_k$ satisfying the Eq. (5). We will add a remark about this point and provide necessary reference for the convergence rate. \n\n---\n\n**Q3. Does Lemma 4.3 require Assumption 4.1? If yes, add Assumption 4.1 to Lemma 4.3?**\n\n**A3.** No. Lemma 4.3 does not require the Assumption 4.1. Assumption 4.1 is only required for Theorems 4.4 and 4.5.\n\n---\n\nReferences:\n\n- Samadi, S., Burbano, D. and Yousefian, F., 2023. Achieving optimal complexity guarantees for a class of bilevel convex optimization problems.\n- Chen, P., Shi, X., Jiang, R., and Wang, J., 2024. Penalty-based methods for simple bilevel optimization under holderian error bounds.\n- Nesterov, Y., 2018. Lectures on convex optimization.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper tackles the bilevel optimization problem where the goal is to minimize a convex smooth objective function over the optimal solutions of another convex smooth constrained problem. The authors introduce a novel method that approximates the solution set of the lower-level problem using a cutting plane approach and applies an accelerated gradient-based update to minimize the upper-level objective. They offer non-asymptotic convergence guarantees for both suboptimality and infeasibility errors, and under the r-th Holderian error bound assumption, they achieve an enhanced convergence bound. Given that all reviewers endorsed acceptance, this paper should be accepted. However, a concern is the difficulty in solving the subproblem (line 6 of Algorithm 1), as noted by Reviewer R6Rr. I suggest the authors provide a detailed discussion on this in the main part of the paper rather than in the appendix.
Decision: Accept (poster)