Functionally Constrained Algorithm Solves Convex Simple Bilevel Problem
Authors: Huaqing Zhang
Lesi Chen
Jing Xu
Jingzhao Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: bilevel optimization
first-order methods
optimal complexity
Primary area: optimization

Abstract: This paper studies simple bilevel problems, where a convex upper-level function is minimized over the optimal solutions of a convex lower-level problem. We first show the fundamental difficulty of simple bilevel problems, that the approximate optimal value of such problems is not obtainable by first-order zero-respecting algorithms. Then we follow recent works to pursue the weak approximate solutions. For this goal, we propose a novel method by reformulating them into functionally constrained problems. Our method achieves near-optimal rates for both 
smooth and nonsmooth problems. To the best of our knowledge, this is the first near-optimal algorithm that works under standard assumptions of smoothness or Lipschitz continuity for the objective functions.

Functionally Constrained Algorithm Solves Convex Simple Bilevel Problems
Huaqing Zhang" 1.2
Lesi Chen' 1.2 Jing Xu
Jingzhao Zhang 4.23
IIIS Tsinghua University
Shanghii Qizhi Institute
'Shanghai Al Lab
(zhanghq22, chenlc23, (aaiin21mmmalll tsinghua, edu. cn j jingzhaoz@mail. tsinghua, edu.
Abstract
This paper studies simple bilevel problems, where convex upper-level function is minimized over the optimal solutions a convex lower-level problem. We first show the fundamental difficulty of simple bilevel problems, that the approximate optimal value such problems is not obtainable by first-order zero-respecting algorithms. Then follow recent works to pursue the weak approximate solutions. For this goal, we propose a novel method by reformulating them into functionally constrained problems. Our method achieves near-optimal rates for both smooth and nonsmooth problems. To the best of our knowledge, this is the first near-optimal algorithm that works under standard assumptions of smoothness or Lipschitz continuity for the objective functions.
Introduction
This work focuses on the following optimization problem:
min
f(x) s.t. E X arg mir m(g(), xe2
(1)
=EZ
where f are convex and continuous functions and Z C R is compact convex set. Such problem often referred to as "simple bilevel optimization" in the literature, as the upper-level objective function is minimized over the solution set of lower-level problem. It captures hicrarchical structure and thus has many applications in machine learning, including lcxicographic optimization
13 15 and lifelong learning [13 [8]. Understanding the structure of simple bilevel optimization and designing efficient algorithms for is vital and has gained massive attention in recent years 1 10
12
14
19
23 27
To solve problem, one may observe that Problem I is equivalent to the convex optimization problem minxxe;; f(x) with implicitly defined convex domain XT. Hence, it is natural to try to design first-order methods to find & E IR." such that
[f()) f*1 S Et, 9(8) 9- S
(2)
where f* is the optimal value of Problem (I) and g" is the optimal value of the lower-level problem (minsez 9())). We highlight the asymmetry in and here. f³ is the minimal in the constrained set Xg. and hence it possible that f(x) f* for some x E Z. On the other hand, g* is globally minimal and hence g" S g(x) for any x Z. Such asymmetry is natural as the role of f.g are inherently asymmetrical for bilevel problems. We call such & (Ebssy)-absolute optimal solution.
Equal contributions.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

When X" is explicitly given, finding such a solution is easy as we can apply methods for constrained optimization problems such as the projected gradient method and Frank-Wolfe method 4 Section 3]. Yet, somewhat surprisingly, our first contribution in this paper (Theorem 4.1 and 4.2) shows that it is generally intractable for any zero-respecting first-order method to find absolute optimal solutions for Problem [ Our negative result shows the fundamental difficulty of simple bilevel problems
compared to classical constrained optimization problems.
As a compromise, most approaches developed for simple bilevel optimization in the literature aim to find a solution IR" such that
f(x) - ct g 9" Cg:
which we call a (Cr, Cg) -wek optimal solution. Much progress has been achieved towards this goal
[10 18 19 23 25 We note all the above algorithms fall in the class of zero-resp algorithms (Assumption 3.4) and hence cannot obtain absolute optimal solutions, unless additional assumptions made. (See Remark4.1 and Appendix for further discussions.)
Our second contribution pushes this boundary by proposing near-optimal lower and upper bounds. We study two settings: (a) f is Cy-Lipschitz and g is C,-Lipschitz, (b) is -smooohth and is -mooth.. We can extend the worst-case functions for single-level optimization to Problem (I to show lower bounds of
1. Ω max (3119, for the setup (a);
2. Ω max V.llee.VLggee for the setup (b).
Given our constructed lower bounds, we further improve known upper bounds by reducing the task of finding (ey, (y)wekk optimal solutions to minimizing the functionally constrained problem:
min f(x), X
s.t. [(x) g(x) - S 0,
(4)
where 3 is approximate solution the lower level problem minxez 9x)) Then further leverage the reformulation by Nesterov (20] Section 2.3.4] which relates the optimal value of Problem (4) to the minimal root of the following auxiliary function, where a discrete minimax problem defines
the function value:
(t) min X
{ (t x) A max (f(x) - tt, t.0(x))}
(5)
Based on this reformulation, we introduce a novel method FC-BiO (Functionally Constrained Bilevel Optimizer). FC-BiO is double-loop algorithm. It adopts bisection procedure t in the outer loop and applies gradient- methods to solve the sub-problem (5). Our algorithms achieve the following upper bounds:
1. ô maxx (0917,081e) for the setup (a);
2. δ (mxx {Vi.see, (g for the setup (b),
where Ô hides logarithmic terms. Both complexity upper bounds match the corresponding lower bounds up to logarithmic factors. In words, we summarize contributions follows:
We prove the intractability for any zero-respecting first-order methods to find a (cf+ absolute optimal solution of simple bilevel problems.
We propose a novel method FC-BiO that has near-optimal rates for finding (cf: Cg) -wek optimal solutions of both nonsmooth and smooth problems. To the best of our knowledge, this is the first near-optimal algorithm that works under standard assumptions of smoothness or Lipschitz continuity for the objective functions. comparison of previous results can be found in Section 2

---

2
Related work
23 27 have been proposed to achieve (cy, fg)-wea optimal solution to simple bilevel problems defined as Equation Below, we review the existing methods with non-asymptotic convergence. For ease of presentation, we state the results for Ey co = c.
In the literature, various methods [
3
6.
TO
12
14
18
19
Prior results on Lipschitz problems Kaushik and Yousefian [4] proposed the averaging iteratively regularized gradient method (a-IRG) for convex optimization with variational inequality constraints, of which Problem (1 is special case. a-IRG achieves the rate of ((1/e"), Shen et al. [25] proposed a method for solving Problem [ with (11/E²) complexity based on the online learning framework. When f is Lipschitz continuous and g is smooth, Merchav and Sabach [19] proposed gradient- based algorithm with ((1/c/((1-a) complexity for any E (0.5, 1). However, none of these methods can achieve the optimal rate of O(E
Prior results on smooth problems Samadi et al. [24] proposed the regularized accelerated proximal method (R-APM) with complexity of (1/ec) Under the additional weak sharp minima condition
on 9. the complexity of R-APM improves to O (1/ve). However, this condition is often too strong and does not hold for many problems. Chen et al. (10) extended the result of (4] to the more general a-Hölderian error bound condition. However, their method achieves the optimal rate only when 1, which reduces the weak sharp minima condition. Jiang et al. [13 developed conditional gradient type algorithm (CG-BiO) with complexity of O (1/e), which approximates X similar to the cutting plane approach. Later on, Cao al. 6 proposed an accelerated algorithm with a similar cutting plane approach to achieve the rate of O (max v }) which can further be improved to O(1/ VE) under the additional weak sharp minima condition. Recently, Wang et al. (28) reduced Problem T to finding the smallest e such that the optimal value of the following parametric problem is g": minxER" g(x), s.t. f() I c. They adopted a bisection method to find such c. To solve this parametric problem, Accelerated Proximal Gradient method is applied on g with projection operator onto the sublevel set F. = {x fx) S c}. which call sublevel set oracles. This leads an upper bound of (1/Ve).. Such an oracle is obtainable for norm-like functions such as fxx || However, it may be computationally intractable for more general functions, such as MSE Joss or logistic loss. It is a very strong oracle that is seldom used in the literature on optimization: the single-level optimization of a function f using sublevel set oracles can be completed in (log(1/e) iterations of bisection procedure. Compared with previous work 66 TO 24 28) our proposed methods achieve the (() rate under standard assumptions, without assuming f is a norm-like function or g satisfies the weak sharp minima condition.
Comparison with Nesterov's methods for functionally constrained problems Based on similar reformulation, Nesterov 220 has proposed algorithms for functionally constrained problems, of which Problem 44) is special case: one for smooth problems in Section 2.3.5, and one for Lipschitz problems in Section 3.3.4. However, Nesterov's 's algorithm for smooth problems relies on the strong convexity of f and g, which does not hold in our bilevel setups. In this case, X would be a singleton, rendering the upper-level problem trivial. Our algorithm does not require the strong convexity assumption, and has a unified framework for both smooth and nonsmooth problems.
3 Preliminaries
For any x E IR"", let Xty represent the j-th coordinate of x for j = 1,.... 1....,,,, n. We use supp(x) = {j e [d] XbI # 03 denote the support of x. The Euclidean ball centered at x with radius R denoted as Bxx, R) A (y lly - x||2 < R). For any closed convex set C C R", the Euclidean projection of x onto C is denoted by (x) ف arg minyee lly x We say a function h is C-Lipschitz in domain Z if []A(x)) h(y) 2| < C||x 2 for all x, E Z. We say a differentiable real-valued function h is L-smooth if it has L-Lipschitz continuous gradients.
We now state the assumptions required in our theoretical results. Assumption 3.1. Consider Problem 7 We assume that
1. Functions f and g R + R are convex and continuous.
3

---

2. The feasible set 2 is convex and compact with diameter D = yez ||x V222.
The compactness assumption ensures that the subprocesses adopted in our method have unified upper complexity bound (see Section We note that other works involving bisection procedures, such Wang et al. (28), may also need to address this issue to derive an explicit dependence on the distance term (although it is not stated formally in their paper), For unconstrained problems, if we know that the initial distance ||x* -xol22 is upper bounded by R. we can simply take Z = B(xo, R).
We use Assumption 13..mmpttioon..houuueeeoeee throughout this paper. but distinguish the following two different settings. Assumption 3.2. Consider Problem ( We assume that I and g are L--smooth and Lg-smooth respectively. We call such problems (L, Lsg-ooh problems.
Assumption 3.3. Consider Problem [ We assume that f and g are -ippsccciitz and Cg g-iisssciit in Z respectively. We call such problems (C₁, Cgy-Liichhitz problems.
To study the complexity of solving Problem 1. make the following assumption the algorithms. Assumption 3.4 (zero-respecting algorithm class). An iterative method A can access the objective functions f and g only through first-order black-box oracle, which takes test point & as the imput and returns 0f (g))., where f (x), ag(x) are arbitrary subgradients of the objective functions at &. A generates a sequence of test points {xx) )
k== with
supp(xx+1) C supp(xo)
U supp (xf(x.)) (upp)))xxx)
(6)
0S*5k
This assumption generalizes the standard definition of zero-respecting algorithm for single- level minimization problems [ (20). Many existing methods that incorporate a gradient
step in the update for Problem (T) clearly fall within this class of algorithms, including
those proposed by IO. 18
19
25. since the gradient step ensures that E
Span(0 (o((x))...................)..).. .0 (xx=))) 0g((xx))))) In the appendix, we show that the proposed algorithm in this paper and the conditional gradient type methods [5] 13) also satisfy the condition (6) when the domain is a Euclidean ball centered at X9 (see Proposition C.I and Remark C.T). which suffices to establish the negative results, including the intractability results for absolute optimal solutions and lower complexity bounds for weak optimal solutions.
The following concept of first-order zero-chain, introduced by Nesterov 20 Section 2.1.2], plays an essential role proving lower bounds for errorrespeciin algorithms. our paper, we leverage the chain-like structure to show the intractability of finding absolute optimal solutions.
Definition 3.1 (first-order zero-chain). We call a differentiable function h(x): 129 R. a first-rrrrr zero-chain if for any sequence {xx }x20 satisfying
supp 11++) S
U supp (Vh(x.)), A 22 1; X = 0,
05.5k
it holds that Xx.[5] = 0, k +1 SJS
Definition 3.] defines differentiable zero-chain functions. We can similarly define non-differentiable zero-chain, by requiring supp(X*+1) to be in Uosogs supp (8h(x.)), where ah(x) is a (possibly adversarial) subgradient of h x.
4 Finding absolute optimal solutions is hard
Faced with Problem (I. a natural initial response is to seek an approximate solution such that f() is as close to f possible, under the premise that g(x) is close to y"" Such a goal is captured by the concept of y (g -absolute optimal solutions as defined in (2). However, it turns out that finding (c),Cg) -absolute optimal solution is intractable for any zero-respecting first-order methods in both smooth and Lipschitz problems as shown in the following theorems.
Theorem 4.1. For any first- order algorithm A satisfying Assumption 3.4 that runs for T iterations and any initial point Xa, there exists a (1, 1) -m-soooth instance of Problem (7) such that the optimal solution x" satisfies l|xo x*112 < and (xxx) - -S" Z 78. For the iterales )T generated by A, the following holds:
f(xx) f(xo), VI < k T.

---

Theorem 4.2. For any first-order algorithm A satisfying Assumption 3.4 that runs for T iterations and any initial point Xa, there exists a (1, --ipschitt instance of Problem ( and some adversarial
subgradients {āf (x())))g(())))))))))) [x= such that the optimal solution x" satisfies ||xo - x*112 S 1 and
[x(x)) - 5* 2 I. For the iterates { (k jk generated by A, the following holds
[(xx) (xx),
v1 k
The proofs of Theorem 4.1 and Theorem 4.2 rely on the concept of worst-case convex zero-chain (Proposition A.I and A.2p. We show that for any first-order zero-respecting algorithm that runs for T iterations, there exists a "hard instance" such that f(x)) remains unchanged from the initial value (xo) throughout the entire process. The complete proof provided in Appendix A
The constructions of the above hardness results are motivated by the work 9 which demonstrated
that for general bilevel optimization problems of the form minlxeR" yER" [xx y) subject to y arg mingeR" (xx z). there exists a "hard instance" in which any zero-respecting algorithm always yields X2 Xp for all S k < T. Although construction has very similar high-level idea to [9]. the f and we construct are different from the functions in 9 since our desired conclusion is different.
provide guarantees for finding (if::g)))bbluut optimal solutions. However, these works assume an additional Hölderian error bound condition f2T) on g. Our near-optimal methods for finding weak optimal solutions, proposed in the next section, also work well under this additional assumption and achieve the best-known convergence rate for absolute suboptimality both in smooth and Lipschitz settings. See Appendix D for further discussions.
Remark 4.1. Some previous works 6
13 24
5 Near-optimal methods for weak optimal solutions
Due to the intractability of obtaining (e,, E, -absolute optimal solutions of Problem ( most existing works focus on developing first-order methods to find (cy. (g) --wak optimal solutions as defined in (3) In this section, establish the lower complexity bounds for finding weak optimal solutions and propose a new framework for simple bilevel problems named Functionally Constrained Bilevel Optimizer (FC-BiO) that achieves near-optimal convergence in both Lipschtitz and smooth settings.
5.1 Lower complexity bounds
We first establish the lower complexity bounds for finding (e,, eg)-weak optimal solution of (Ly. Lsmoohh problems and (C;,Cy)-Lipschinn problems. The results follow directly from existing lower bounds for single-level optimization problems, as simple bilevel optimization is more general framework. Although the proof is straightforward, we present the results because establishing a precise lower bound essential for demonstrating that an algorithm is truly near-optimal.
Theorem 5.1. Given Lgg, Lig D > O. For any first-order algorithm A satisfying Assumption 3.4 and any initial point Xy, there exists a (L,, Ly),,Lo))mmott instance of Problem ( on the do- main 2- B(x,, D) such that the optimal solution x" is contained in Z and A needs at least
Ω max {V V TTa Ey
D)
iterations to find (cg, -weak optimal solution.
Theorem 5.2. Given Cg,Cg, O. For any first-order algorithm A satisfying Assumption 3.4 and any initial point Xo, there exists (C₁, Cypshiicc instance of Problem Q on the do- main B(xx, D) such that the optimal solution x" contained in Z and needs at least
C C² 2 D²)
max
iterations to find a (Ef, -g)-kaak optimal solution.
5.2 Our proposed algorithms
We now present unified framework applicable to both smooth and Lipschitz problems. The proposed algorithms nearly match the lower complexity bounds in both settings up to logarithmic factors.
Problem reformulation We apply two steps of reformulation. First, we relax Problem to
Problem (4) where the constraint x E X; is replaced by a relaxed functional constraint g(x) P g(x) g" < 0 and 8" is an approximate solution to the lower level problem minxez g(x). Denoting f as the optimal value of Problem (4), the following lemma holds:
5

---

Algorithm Functionally Constrained Bilevel Optimizer (FC-BiO)
Require: Problem parameters Xo. D, desired accuracy total number of iterations T, initial bounds l, u, and a subroutine for Problem 7 M..
Set N log2
K T/N. Set x X0.
c/2
2: for k = 0. ..... 3: Set t+
N
do
2
4: Solve with the subroutine (x()) (0)) = -M(x, K)
5: Set x (()
6: if J0 (1)
then
7: Set l =
8: else
9: Set u t.
10: end if
11:
end for
12:
return x (u) the approximate solution.
Lemma 5.1. gf S g S 9 + & and & a (g)),,//))-weel weak optimal solution to Problem (4) i.e.
f(x) c s 6g/ then & is (c,,Cy)- Cy)-weak optimal solution Problem 4
Therefore, it suffices to pursue an approximate solution of Problem Second, Problem (4) is further reduced the problem of finding the smallest root of the following auxiliary function:
(t) = min X
(t, x) 2 max {f(x) g(x))
Such reformulation is introduced in Nesterov 20 Section 2.3] with the following characterization.
Lemma 5.2 (Nesterov (20 Lemma 2.3.41). Let f be the optimal value of Problem (4), and let v/ (1)
be the auxiliary function defined in (7). The following holds:
1. *p² (1) is continuous, decreasing, and Lipschitz continuous with conslant 1.
2. f* is exactly the smallest root of u/² (I).
Bisection procedure Based on the preceding reformulation, we propose Algorithm (FC--Bt) which uses a bisection procedure estimate the smallest root of v For now, we assume that the desired accuracy on upper-level and lower-level problems the same, (i.e. éy = Eg = e). Later we will show in Corollary 5.1 that we can handle the case when é, * fg by simply scaling the objectives.
Algorithm | applies the bisection method within an initial interval [é, u] which contains the smallest root, fr, for N logz // iterations. Similar to 288. the initial interval can be obtained by applying single-level first-order methods. The lower bound is obtained by solving the global minimum of the upper-level objective f over æ E Z, while u = f(xy) serves valid upper bound, where 8,. is an approximate solution to the lower-level problem. Further details can be found in Appendix B.1 In each iteration, we set
É+u To approximate the function value of s/* (t), we apply a first-order algorithm M to solve the discrete minimax problem 7 For the Lipschitz setting. we let M be the Subgradient Method (SGM, Algorithm 2 [4] Section 3.1]. For the smooth setting, we let M be the generalized accelerated gradient method (generalized AGM, Algorithm 3 20 Algorithm 2.3.12]. These methods guarantee to find an approximate solution & of Problem such that
(1) (0)) ( (10) 15
(8)
If (t) > e/2, update & = Conversely, if أه (t) < c/2, set t. For the initial point of M, we exploit a warm-start strategy (see more details in Appendix B.2p. After completing N iterations, return & (() the output. As shown in Lemma 5.3 is guaranteed to be (e, week optimal solution to Problem (

---

Algorithm 2 Solve Problem 7 with SGM (xo, D,
Require: Problem parameters Xo, D, total number of iterations K. Set 1j = (VV), where = max (C,, (C5,Cg)) Cg).
2: for k = 0. ....... K do
3: Obtain subgradient E (1, x) by Proposition 5.1
4: Update X = (x 1/8).
5: end for
6: return X(1) π E X as the approximate solution and (² (xx))
as the approximate value.
We remark that since only solve an approximate value of ei" (t), the upper bound might fall below f during the bisection process. But this is acceptable since we are only in pursuit of weak optimal solution instead of an absolute optimal solution.
Lemma 5.3. iJ satisfies g" S 5J* S S + & and (8) holds for every I. in the process of Algorithm 7 then the approximate solution & returned by Algorithm 7 is (e, e/2)- optimal solution to Problem (4), and therefore a (c, c)-weak optimal solution to Problem by Lemma 5.1
According this lemma, (llog(/o)) iterations of the outer loops sufficient to find (e, e-)weak optimal solution. Next, we will discuss the process and complexity of the subroutines in detail.
5.3 Subroutines and total complexity
To proceed with the bisection process, we need invoke subroutine M to approximate the function value of 1/ (t) = minxez 2 (t, x) in each outer iteration, where (t x) = max(f(x] t, {x)) This reduces discrete minimax optimization problem (Problem for a given t. Below demonstrate the subroutines to solve this problem Lipschitz and smooth settings.
Lipschitz setting When and g convex and Cj and Cy-Lipschitz respectively, it holds that (t, x) is also convex and Lipschitz with constant max { [Cy, Cg). In this case, setting M to be the Subgradient Method (SGM) [4] Section 3.1] applied on (tt,,)) (Algorithm 2 directly achieves the optimal convergence rate. To implement the SGM method, the subgradient of sb(4, x) needs to be computed given in the following proposition:
Proposition 5.1 (Nesterov 220 Lemma 3.1.3]). Consider (),,, = max and g are convex functions. For given I. We have
max( (f(x) - 1, 1x)( where
O))(),
f(x) - > g(x);
0xb((1))) = 0r(x),
f(x) - < ğ(x);
Conv (x)xx
f(x) - -t 5(x).
Algorithm 2 has the following convergence guarantee:
Lemma 5.4 (Bubeck al. 4 Theorem 3.2]). Suppose Assumption
3.1 and 3.3 hold. When > I 30 (t) S 16* (t) +
AD²C² the approximate value 3² (t) produced by Algorithm 2 satisfies 3 2
(t)
where C max Cg)-
We refer to Algorithm with SGM subroutine (Algorithm as FC- Up. Combining with Lemma
5.3
we obtain the following total iteration complexity of FCP
Theorem 5.3 (Lipschitz setting). Suppose Assumption 3.7 and 3.3
hold and 6, =< When
u-E
ET
4 max CC7 D2,
T2
logz
c/2
é2
the approximate solution & produced by FC-BiO a (e, e)-eak optimal solution to Problem 7
Smooth setting The optimal first-order method for optimizing smooth objective functions is the celebrated Accelerated Gradient Method (AGM) (00 Section 2.2] proposed by Nesterov. In contrast to the Lipschitz setting. AGM cannot be applied to ett max(f(xx -t, tx)( directly when
7

---

Algorithm 3 Solve Problem 7 with Generalized AGM (xo, D,I, K)
20
Algorithm 2.3.12]
Require: Problem parameters Xo, D, t, total number of iterations K.
1: Set Xg, ag
2: for = 0.
do
3: Compute X as the solution to 9 by Proposition 5.2
4: Compute ck+1 from the equation of (1 014+1 1
5: Set Bg ca(l-as),
og agtax-1 1 Xx++ (X++1 Xx.)
6: end for
7: return x()) хк as the approximate solution and (1)) max{f(xx) 6, (xx)) as the
approximate value.
and are convex and smooth, as the smoothness condition no longer holds for (t, However, Nesterov (20) Section 2.3] showed that by simply replacing the gradient step in standard AGM with the following gradient mapping (Nesterov 220 Definition 2.3.2])
Xk+1 arg min XE2
v(t,x;y)) & max f(yx)+ (Vf(y))) x yy) + マ 5||x -val
t,
(9)
f(ya) - (Vg(x)), x yu) + yxl1
the optimal rate of O LLVL can be achieved for Problem Here {xx). {yk} are the test point sequences and = m Lgg) Solving X for general discrete minimax problems (where the maximum is taken
potentially more than two objective functions, studied in Nesterov [20) Section 2.2]). reduces to a quadratic programming (QP) problem and may not be efficiently solvable. However, demonstrate that in problem setup, X can be expressed in the form of a projection onto the feasible set 2, or onto the intersection 2 and hyperplane. A similar subproblem also arises in Cao al. [6] Remark 3.2]. When the structure of H is simple, such as when it is a Euclidean ball, the subproblem may admit closed-form solution. Otherwise, Dykstra's projection algorithm can be applied solve [Л]]
Proposition 5.2. Define the descent step candidates
1 ((V())) x2 =2=IT= yk V
x1 = 11 Yk I,
(10)
= Izna yk (
where H C R is hyperplane defined by
= {x f(yx) 7(yx) + (V (yx)) Vğlyx), x yx) - 0}.
Then the solution to is X = arg min (x: (1.233) (tt, x;:)).
We present the generalized AGM subroutine (Algorithm 3 and its convergence rate below.
Lemma 5.5 (Nesterov (20 Theorem 2.3.5]). Suppose Assumption 3.7 and 3.2 hold When K 2
DV 12L the approximate value (t) produced by Algorithm satisfies wf (t) (t) S 60 (t)
where L L,, Lg).
We refer to Algorithm D with generalized AGM subroutine (Algorithm) 3 as FC-BiO whose total iteration complexity is given by the following theorem:
Theorem 5.4 (Smooth setting). Suppose Assumption
3.7 and 3.2 hold and ey Eg When
u -
12 max L Lg) D,
T>
log2
c/2
the approximate solution & produced by FC-BiO is (e, w)-we optimal solution to Problem

---

PC30
MGM
PR.APG
Be8G
10
Bon-Bi
10
10
10"
0
5
10
15
time (s)
timee
compared Figure 1: The performance Algorithm comparreee with other methods in Problem
11
For more general cases when the desired accuracy for the upper-level and lower-level problems is different (i.e. Ef # Eg), we can simply scale the objective functions before applying FC-BiO or FC-BiOsh, resulting in the following guarantee:
Corollary 5.1. Suppose Assumption 3.1 holds. By scaling 9" + and applying FC-BiO or
cy
FC-BiO on functions and g¹, a (Ef; -weak optimal solution to Problem obtained within
the complexity of Ô max
C² C² D2) under Assumption and Ô
max
Lu
D
under Assumption
Our proposed algorithms near-optimal in both Lipschitz and smooth settings the convergence results in Corollary 5.1 match the lower bounds established in Theorem 5.I and Theorem 5.2
Numerical experiments
In this section, evaluate proposed methods on two different bilevel problems with smooth objectives. We compare the performance of FC-BiOsm with existing methods, including a-IRG [4) Bi-SG [19]. [3) AGM-BiO (6, PB-APG[IO], and Bisec-BiO The following problems are also Lipschitz on a compact set Z, so we implement TC-BiO as well. The initialization time of FC-BiO"a, FC-BiO CG-BiO and Bisec- BiO is taken into account and is plotted in the figures. Our implementations of CG-BiO and a-IRG are based on the codes from [13, which is available online
6.1
Minimum norm solution
As in
28 we consider the following simple bilevel problem:
f(x) = |x1 1 9(x) = 2 11Axxxx b1..
(11)
We set the feasible set B 2). We use the Wikipedia Math Essential dataset 22 which contains 1068 instances with 730 attributes. We uniformly sample 400 instances and denote the feature matrix and outcome vector by AA and respectively. We choose the same random initial point Xo for all methods. We set E Eg 10-6 For this problem, to measure the convergence. Figure shows the superior performance of our method compared to existing methods in both leper-level and lower-level. The only exception is Bisec-Bii Bio [28 which shows a comparable performance to our method. This also aligns well with the theory as these two methods have the same convergence rates. We remark that the output of our method satisfies that f(x) < f Thus although (x) l"] > éy. indeed (e <g)x-aa) -eak optimal solution is solved by FC-BiOem em See more experiment details in Appendix E.
explicitly solve x* and f*
6.2 Over-parameterizee logistic regression
We examine simple bilevel problems where the lower-level and upper-level objectives correspond to the training loss and validation loss respectively. Here we address the logistic regression problem

---

10a
10
MCSA I10
100
PIL AFG
10
10
10a
10
10
10"
0
10
15
0
5
10
15
time
Figure 2: The performance of Algorithm [ compared with other methods in Problem (2)
using the "revI.binary dataset from "LIBSVM" 8 [6]. which contains 20, 242 instances with 47, 236 features. We uniformly sample m 5000 instances the training dataset (A* bb"), and m instances the validation dataset (Aval boot). ). We consider the bilevel problem with:
1 f(x)
log(1 exp(-(A)_)) (xxa xxbba)))
1=1
(12)
1 m
g(x) log + exp(- Tx xb.")).
We set the feasible set = (,, 300). We set the initial point Xo for all methods. We set Ef Eg 10-3, Since projecting to the sublevel set of f(x) is not practical, Bisec-BiO [28] does not apply to this problem, thus we only consider other methods. To the best of our knowledge, no existing solver could obtain the exact value of f and g" of Problem [12) Thus only plot function value f (xx) and g(x)). instead of suboptimality. As shown in Figure 2| our method converges faster than other algorithms in both upper-level and lower-level. More details provided in Appendix E.2
7 Conclusion and future work
This paper provides a comprehensive study of convex simple bilevel problems. We show that finding a (cr, Eg)abbolute optimal solution for such problems is intractable for any zero-respecting first-order algorithm, thus justifying the notion of weak optimal solution considered by existing works. We then propose a novel method FC-BiO for finding a (E,, -wekk optimal solution. Our proposed method
achieves the near-optmal rates of Ô [ Le, L and Ô (oax(/LL/EE,, v Lgg/cg) for Lipschitz and smooth problems respectively. To the best of our knowledge, this is the first near- optimal algorithm that works under standard assumptions of smoothness or Lipschitz continuity for the objective functions.
We discuss limitations unaddressed in this work. First, method introduces additional logarithmic factor compared to the lower bounds. We hope future works can further close this gap between upper and lower bounds. Second, our methods cannot be directly applied to stochastic problems [5]. Establishing lower complexity bounds and developing optimal methods for stochastic simple bilevel problems remain an open question for future research.
Acknowledgement
We would like express our sincere gratitude to the anonymous reviewers and the area chair for their invaluable feedback and insightful suggestions. particular, we thank the area chair for suggesting simplifying the proofs of Theorem 5.1 and Theorem 5.2.
10

---

References
[1] Mostafa Amini and Farzad Yousefian. An iterative regularized incremental projected subgradient method for class of bilevel optimization problems. In 20/9 American Control Conference (ACC), pages 4069-4074. IEEE, 2019.
[2] Michael Arbel and Julien Mairal. Amortized implicit differentiation for stochastic bilevel optimization. In ICLR, 2022.
[3] Amir Beck and Shoham Sabach. first order method for finding minimal norm-like solutions of convex optimization problems. Mathematical Programming, 147(():25-46, 2014.
[4] Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357,22 2015.
[5] 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. In NeurIPS, 2023.
[6] Jincheng Cao, Ruichen Jiang, Erfan Yazdandoost Hamedani, and Aryan Mokhtari. An accel- erated gradient method for simple bilevel optimization with convex lower-level problem. In NeurIPS, 2024.
[7] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71-120, 2020.
[8] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1 2011. Software available at http://www.. csie ntu. edu. tx/"cjlin/libsvm
[9] Lesi Chen, Jing Xu, and Jingzhao Zhang. On finding small hyper-gradients in bilevel optimiza- tion: Hardness results and improved analysis. In COLT, 2024.
[10] Pengyu Chen, Xu Shi, Rujum Jiang, and Jiulin Wang. Penalty- baaed methods for simple bilevel optimization under Holderian Error Bounds. In NewrlPS, 2024.
[11] Patrick L Combettes and Jean- Chrishhittephe Pesquet. Proximal splitting methods in signal processing. Fixed-point algorithms for inverse problems in science and engineering, pages 185-212, 2011.
[12] Elias S. Helou and Lucas EA Simões. e-subgradient algorithms for bilevel convex optimization. Inverse problems, 33550,0, 2017.
[13] Ruichen Jiang, Nazanin Abolfazli, Aryan Mokhtari, and Erfan Yazdandoost Hamedani. A conditional gradient-bart based method for simple bilevel optimization with convex lower-level problem. In AISTATS, 2023.
[14] Harshal D. Kaushik and Farzad Yousefian. A method with convergence rates for optimization problems with variational inequality constraints. SIAM Journal on Optimization, 31(3):2171- 2198, 2021.
[15] Matthias Kissel, Martin Gottwald, and Klaus Diepold. Neural network training with safe regularization in the null space of batch activations. In Artificial Neural Networks and Machine Learning, pages 217-228. Springer, 2020.
[16] David D Lewis, Yiming Yang, Tony Rossell-Rose, and Fan Li. Revl: A new benchmark collection for text categorization research. Journal of machine learning research, 5(Apr): 361-397, 2004.
[17] Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. Catalyst acceleration for first-order convex optimization: from theory to practice. JMLR, 18(212) 2018
[18] Yura Malitsky. Chambolle-pock and Tseng's methods: relationship and extension to the bilevel optimization. arXiv preprint wwX.iv1170..22000 2017.

---

[19] Roey Merchav and Shoham Sabach. Convex bi-level optimization problems with nonsmooth outer objective function. SIAM Journal on Optimization, 33(4):3114-3144 2023,
[20] Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
[21] Jong-Shi Pang. Error bounds in mathematical programming. Mathematical Programming, 79 (1):299-338) 1997.
[22] Benedek Rozemberezki, Paul Scherer, Yixuan He, George Panagopoulos, Alexander Riedel, Maria Astefanoaei, Oliver Kiss, Ferenc Beres, Guzman Lopez, Nicolas Collignon, et al. Py- torch 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.
[23] Shoham Sabach and Shimrit Shtern. first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640 660,, 2017.
[24] Sepideh Samadi, Daniel Burbano, and Farzad Yousefian. Achieving optimal complexity guarantees for class of bilevel convex optimization problems. arXiv preprint arX2v:2310.12277, 2023.
[25] Lingqing Shen, Nam Ho-Nguyen, and Fatma Kılınę-Karzan. An online convex optimization- based framework for convex bilevel optimization. Mathematical Programming, 198(2):1519- 1582, 2023.
[26] Mikhail Solodov. explicit descent method for bilevel convex optimization. Journal of Convex Analysis, 14(2):227, 2007.
[27] Mikhail V. Solodov. A bundle method for class of bilevel nonsmooth convex minimization problems, SIAM Journal on Optimization, 18(1):242-259, 2007.
[28] Jiulin Wang. Xu Shi, and Rujun Jiang. Near-optimal convex simple bilevel optimization with bisection method. In AISTATS, 2024.
12

---

A Proofs for Section
A.1 Constructions of first-order zero-chains
We first give the constructions of the zero-chains that are used in our negative results. These zero- chains are the worst-case functions that Nesterov (20) used prove the lower complexity bounds for first-order methods in single-level optimization.
Proposition A.1 (Paraphrased from Section 2.1.2 Nesterov 20 Consider the family of functions hg (x) 1
R:
L
h (()
X
[x)]
x(++ x²y
AXq1))
(13)
The following properties hold for any (x)),(( with q E N+ and L, R 0:
1. It is convex and L-smooth function.
2. It has the following unique minimizer: xi, (1- of1) with norm ||x l2 Rvq.
3. It is differentiable first-order zero-chain defined in Definition 3.7
Remark A.1. In Section 2.1.2 of Nesterov (20), it is shown that L1 is a convex and L-smooth zero-chain. Here we define bg.),.((x) == he (g), Then (2, = I. ) and
(x),, is also convex and I-smooth zero-chain. Similarly, in Proposition A.2 define (x,,, = Rr Rr,.c,1( (xx,(,)),,.. x) Nesterov (20) showed C,1 is a C-Lipschitz zero-chain, which implies that C, R. also a C-Lipschitz zero-chain, since (xx,C,,(X)) V )
Proposition A.2 (Paraphrased from Section 3.2.1 Nesterov (0)). Consider the family of functions (()). 199 + R:
CV max XbI + 2R(1 + /q) |x11 Tx.c.((x)= 1 15S59
C
(14)
The following properties hold for any R(x),,(()) with E N+ and C, R > 0:
1. It is convex function and is C-Lipschitz in the Euclidean ball B(0, Rt..
2. It has a unique minimizer x" = It 1.
V/
3. It is non-differentiable first-order zero-chain.
Remark A.2. The non-differentiable first-order zero-chain presented in Proposition A.2 is slightly different from the one given in Nesterov [20]. Cg,).u(-) is Lipschitz in ((0, R), while the zero-chain presented in Nesterov (20) is Lipschitz in B(x", R)), where x" is the minimizer of the zero-chain.
A.2 Proofs of Theorem and Theorem 4.2
Proof of Theorem 4.7 Consider any first-order algorithm A satisfying Assumption 33.4 3.4 that runs for T' iterations. Without loss of generality, assume the initial point of A is xo 0. Otherwise,
can translate the following construction to f(x xx),g(x xo). Let = 27 and
f(x)
b g(x) hg.11//((x)).
j=1+1
where hg.1.1//a follows Proposition A.1 It is clear from the construction that both f()),(() are convex and 1-smooth. Furthermore, the optimal solution to Problem ① defined by such f. g the unique minimizer of g(x), given by x v
- (1 ( We prove by induction on that the test
points {xx] generated by A satisfies Xx, for < TT $ 27: Suppose for
some k < T, Xt,5] 0 holds for 0 < i < k 1,7 < < 27, we have
vx(x)) = 0515k k- 1 1.
13

---

The zero-respecting assumption of A (Assumption 3.4
leads to
X E
supp
f(x)
U supp((V((x))
0sisk-1
(upp(Vg(x)))
0sisk-1
Since g(x) is a first-order zero-chain, we conclude that
Xx. = 0, k + 1 S $ 2T.
Consequently, fxx)) remains zero for all 0 S k v K. However,
27
f f=
Σ
-=
21
1
4T
2T
+1
j=1+1
1
+1
24
+1
1
48
Thus
1
1f(x)) 17 48'
1skST.
Proof of Theorem 4.2 Consider any first-order algorithm A satisfying Assumption 3.4 that runs for T iterations. We similarly assume that the initial point of is 0. Let q 27 and
2T
f(x)
Σ
x DI
g(x) 12
2
j=741
where 1.) follows the construction in Proposition
A.2 Both 9()) and f(-) are convex and 1-
Lipschitz in (0, 1), and the unique minimizer x o
1 of is the optimal solution to Problem
defined by such f and with norm 12 = 1. Similar to the proof of Theorem 4.1 we prove by adversarial subgradients {ag(xa).
induction on I that there exist
0g(xx 1}} such that the
test points {xx ) generated by AA satisfies Xk. = for
S T. S j S 27: Suppose
for some T. X 0 holds for 0 < < 1,7+15 2T. have
vx(x)) = 0, 0 S
The zero-respecting assumption of A (Assumption 3.4) leads to
U supp(V/(x;)) Usupp(0g(x.) 0sick-1
X E
supp(0g(x:)).
ogigk-1
where (0g(x)), 09((x=1)) are the subgradients returned by black-box first-order oracle. Since g(x) is a first-order zero zero-chain, we conclude that there exists some adversarial subgradients (0g(xo). 0g(xx-1)} such that
* 0, A: k+1
Consequently, f(xx) remains zero for all 0 < k < K. However, f(x)) = 1 Thus
1
(f(x*) fz| 4' 1
14

---

B
Algorithm details
B.1 Determining 3" and the initial interval
To apply the two-step reformulation,
need solve approximate value of the lower-level problem ÿ" such that 9 S 0" S 5-" + Furthermore, to conduct the bisection method of FC-BiO, it necessary to first determine initial interval [e, uj that contains the minimal root of 10 (t), which
exactly f (Lemma 5.2). The following procedure is inspired by Wang et [28]: First, we apply optimal first-order methods for single-level optimization problems subgradient method (SGM) [4 Section 3.1] for Lipschitz functions, and accelerated gradient method (AGM) [20] Section 2.2] for smooth functions to the lower-level objective g to obtain approximate minimum point & IR" such that g" S g(xg) I g + 5.2 We set 9 = g(&g) and define the relaxed constraint function g(x)
in We set u f(Xg), then
(u) (b(u, xx) = max[f($; u. (x,)) O.
Thus is indeed an upper-bound of the minimal root of (-) given that a/ (.) is decreasing.
To derive lower bound of the minimal root f*, we can also apply the optimal single-level min- imization methods to the upper-level objective f to find an approximate global minimum point y E Z such that p¹ < p _ f(&,) S p" + 1.2 where p" is the minimum value of f over Z (i.e., p" - minxez fxx)). Then p² a valid lower bound of f" since
L = ~ 2 St.
Nevertheless, any lower bound for f is acceptable, such when the upper-level objective is non-negative.
The complexity of applying the optimal single-level minimization methods to f and separately is o ( c² - 22) (SGM for Lipschitz problems) or O (V V (
(AGM for smooth
problems), which does increase the total complexity established Theorem 5.3 and 5.4
B.2 Warm-start strategy
For the initial point of the subroutine M (SGM in FC-BiOLip generalized AGM in FC-BiO ) we exploit the warm-start strategy, which uses the last point in the previous round (denoted by x in Algorithm
M as the initial point of the current round. Intuitively, the subproblem (i.e. minimizing mx) ł, (x)} }) does not change significantly in each round since the parameter t does not change too much as and are getting closer. Thus the approximate solution of the last round is supposed to be close to the optimal solution of the current round. Nevertheless, any initial point in Z does not change the complexity upper bound. Such a strategy is widely used in two-level optimization methods (2 17).
Similarly, of Xg as the initial point the first round of the subroutine.
the approximate minimum point &g of g (as descrihed in Appendix B.1 instead
C Proofs for Section
C.1 Proofs of Theorem 5.n and Theorem 5.2
5.2
Recall the lower complexity bounds for single-level convex optimization problems:
Lemma C.1 (Nesterov (20 Theorem 2.1.7D. Given L > 0, D 0. For any first-order algorithm A
satisfying Assumption 3.4 and any initial point Xo, there exists a convex and L-smooth function such that the minimizer x" satisfies |xx" Xxol2 I D and
3LD
f(xT) f(x*) 2 32(T 1)2
15

---

Lemma C.2 (Nesterov 20 Theorem 3.2.1J). Given C >> 0, D >> O. For any first-order algorithm A
satisfying Assumption 3.4 any initial point Xo, there exists convex function f that C-Lipschitz in (xx D), such that the minimizer x" satisfies Ixx
x S D and
CD
- ((x))-((x)2 2(1 VT)
The "hard functions" f()) in the previous lemmas are exactly the zero-chain h2T+1,1,D() and rT,C,D(-) constructed in Proposition A.1 and Proposition A.2 respectively.
Consider any first-order algorithm A satisfying Assumption 3.4 that runs for iterations. Without loss of generality, we assume the initial point of A is X 0. Otherwise, we can translate the following construction to f(x x Xu).
Proof of Theorem 5.7
R2T+1 + R be: If L 2 Le we set the upper-level and lower-level objective f,g: : cf
f(x) = ber+1,,,, g(x) = 0,
where byr+1.L,,D() is defined in Proposition A.1 implies that for any 2 1, we have supp(x*+1) holds that
Then the zero-respecting assumption on A
Uugosk-1 supp (v)().)) From Lemma C.
32 32(T + 1)2
Ef = f(x)) f
which implies that any zero-respecting first-order method needs at least
T T=
= max
11
Lg
D)
Cf
Eg
iterations to solve a (c,, (g) weak optimal solution.
If 1i Iiz, we set the upper-level and lower-level objective f. 2T - R be:
f(x) = O, g(x) = 12T+1,L,,
By similar arguments, any zero-respecting first-order method needs least
( (1 Ian
{
L Ef
Lg
T T=
max
(1
Eg
iterations solve
optimal solution.
Proof of Theorem 5.2
Consider any first-order algorithm A satisfying Assumption 3.4 that runs for
iterations. Without loss of generality, we assume the initial point of A Xo = 0. Otherwise, we can translate the following construction to f(x xo), g(( xo).
C1 Cg. we set the upper-level and lower-level objective f,g: RT R be:
If C5
f(x) (T,C,,,(x), g(x) 0,
where .r. is defined in Proposition A.2 Then the zero-respecting assumption on A implies
that for any t 2 1, we have supp(xx) C U U supp (0f(x.)). From Lemma C.2 it holds that
CyD
E, f(x)) ((xx))='*
2(1 + vT)
which implies that any zero-respecting first-order method needs least
C2 maxx
C²
C
T T= Ω D2
D
f
16

---

iterations to solve a (g), -weak optimal solution.
If Cj Co set the upper-level and lower-level objective f.g R² R be:
's"
xx) 0, g(x) = rxx)..D(x).
By similar arguments, any zero-respecting first-order method needs at least
C D2
C3
C
T=
S2
max
D
2
f
g
iterations to solve a
optimal solution.
C.2 Proofs in Section 5.2 and 5.3
Proof of Lemma 5.7 Any feasible solution to Problem thus fr S l" For any that satisfies
is also feasible solution Problem 4
[(x) + S
Eg 2
we have
f(x) - fr , +Cg.
_ 2
Eg = + Eg.
g(x) = x(x) 3" $
+ g"
2
Thus x is indeed (ef, 6g) -weak optimal solution to Problem
Proof of Lemma
5.3 We first show that E is always lower bound of f The initial lower bound Furthermore, if {8) holds during the bisection process, we always have that O. Given that u0 (-) decreasing, and considering that is the minimal root
satisfies l <
(l) 2 3つ (c) of di* (Lemma 5.2 it follows that é < f*.
As for the upper bound u, the initial upper bound satisfies
$ (u) (u, xg) max x1g(())) = max (0, s
And during the bisection process, we also have that vi (u) mxx( - (x)0((())) S After N = loga
u-t e/2
bisection iterations, it holds that
u 8 S 2
Consider the output of Algorithm
x X (w)- Combining previous inequalities, we have
f(x) S ut setcs5+a
x(8) < 5
Some of the lemmas in this section are adapted from existing results 20 but not exactly the same.
We also provide proof for these lemmas (Lemma 5.2 5.4 5.5
Proof for Lemma 5.2 It's clear the 2 (t) is continuous and decreasing, For any t E R and A > 0.
we have
(1+++A)
(xx) + + AA
xE2
17

---

2 min (ma{{ - [xxx)}}} - -A xe2
(1)
Thus 10 (t) is 1-Lipschitz.
Let X be the optimal solution to Problem 4 then f = f(x²). For any 2 fr, it holds that
(0) S 10 (f*) S w( = max - f g x }} S 0.
Suppose that t < fo and 20 (t) s 0, then there exists x E 2 such that ((x) S 0, f(x) - 0.
Then a feasible solution Problem ( with f(x) S t < f", contradiction to the fact that f is the optimal value to Problem ( Thus for any t < f", holds that 30 (t()) >
Thus f is the smallest root of (t).
Proof for Lemma 5.4 Theorem 3.2 in Bubeck al. 44 states that applying subgradient method to any C-Lipschitz convex function on a compact set Q with diameter D gives
K-1 Σ
DC
h S
VK"
Here h(x) = (t,x)) max(f(x) - t, g(x)), C = max (C,, Cg). Then when K 2 1D*C² that
holds
K-1
(1) = vb
1 K
Σ k=
X;
$ (1)
2
originally states that applying genearlized- gradient method any j--strogly convex and L-smooth convex function gives
Proof for Lemma 5.5
Theorem 2.3.5 in Nesterov 20
((*x) - h² S (70- - (K) + 1)2 (f(xo) - f*+ 7o |x0 x 112)
4L
2
where Yoo )o(aob-1) Here h(x) vi(t, max(f(x)- t,,(x)), L max( Lg)
1-00
Ogg = 2: 70 = 2-
Then
4L L(K 1)2
11100 x21 + x 113 5
6LD
(t,,xx) 35"
K2
Then when K 2
12L D, it holds that V
=11))=((,xH) xx) S (1)
(1)+ +
=
To prove Proposition 5.2 we first present a lemma:
Lemma C.3. For any strictly convex and continuous functions f. g. 18 +R E. we define :p: E R by xx))= = mxx(f((x) g Let x" be the unique minimizer of xp-) on a convex and compact set Z C R" i.e. x arg minxez -(x),, and let X². x²y be the unique minimizer of f() and g(-) on Z respectively. xfx* + xj and x" # Xy, then f(x") = =g(x").
functiion
Proof. Below, we show that [xx) + 4xxx)) leads to contradiction. Without loss of generality, assume [(x") > g(x*). Due to the continuity of I and there exists some 8 > O such that for any
0 < 0 <,
f(x" +(xx - xx')) > g(x" 0(x; x")).
18

---

Furthermore, for any 0 E (0, 1), we have that x + 0(xx -x') E Z and
f(x' + 0(x - xx)) < <0f(x)) (1 f)f(x²) f(x'),
since f is strictly convex.
Then for any E (iim(1,))),
g(x" + [(x} xx)) f(x* +0(x x))) < f(xx) xxxx).
That contradicts the fact that x" is the minimizer of cp.). Thus f(x") = g(x'): )
The previous lemma demonstrates that the minimizer of m ( falls into one of three categories: the minimizer of f. the minimizer of or the case where the function values of and are the same. X1, X2, X3 in Proposition 5.2 corresponds to the three cases respectively.
Proof for Proposition
5.2
Define
y(1 A f(yx) + (VS())), yb) + - yxll2 L
I,
g(x:ya) ((yx) (Vo(yx), x yk) +
2 "111xx 11|-~1113
which can be written as
1
L +
2
f(t,x:yx) = f(yx) -t
[f(yx)]1
x Yk + f((k))
2L
2
L
L
y(x:ya)= = =5(yx)
Vg(yx)
x Yk + L Vg(yn)
2L
2
Thus
arg min x
yk + Vf(yk)
airgmin f(t,x; Vk). XEZ
L
1
X2 arg min x
x yk +
Vg(yk)
arg min xt:
L
x
Assume the minimizer X of (1,1,, x;)k) satisfies X * X1 and X # X2, then Lemma C.3 implies that
X
E(x [(1,x; yn) g(x;ya))
=(x f(yx) - g(yx) + (Vf(v)) Volyx),x- - 0}
=H.
Given that f(t, xx)) g(x: yı) in the subset Z n H, we have
Xk+1 arg min (t, (x) znZ
arg min f(t, x:yx)
xE
1 x Yk + 1 f(yx))
arg min xEZnH
X3-
Thus we conclude that X can only be one of X1, X2, X3.
Proof for Theorem 5.3 Combining Lemma 5.3 and Lemma 5.4 we directly get the result.
Proof for Theorem
5.4 Combining Lemma 5.3 and Lemma
5.5
we directly get the result.
19

---

Proof for Corollary 5.7 A (g) -weak optimal solution to Problem is equivalent to (g),
weak optimal solution to
min f(x), s.t. g²(x) c/ 5(x) 50. XE2
(15)
Eg
When f and are Cj, C. Lipschitz respectively, 9" is FC-BiOLip finds a (e Ey -weak optimal solution Problem
cy Cg Lipschit. According to Theorem 5.3
15
max (C},
C D2 = max
C Ej
C 9
D
ef
iterations. Similarly, when I and are T, -mooth respectively, ÿ" is f1 I. Theorem 5.3 FC-BiOsn finds (cg,,y)-weer optimal solution of Problem 115 in
5, - smooth. According
T= δ (1)
max Lgg, 5/ Lg) D 0)= -00
1)=0( max
(0max
Ls Ef
Lg
(V
Eg
Eg
iterations.
Finally, we prove the claim that our proposed algorithms are zero-respecting algorithms when the domain is Fulidean ball centered at Xo. Proposition C.1. Both FC-BiOLip and FC-BiOss on the domain ((xo, D) satisfy Assumption 3.4
Proof. Without loss of generality, we assume Xg = Note that the warm-start strategy preserves the zero-respecting property in Assumption 3.4. Therefore, it suffices to prove that the subroutines (Algorithm 2 and Algorithm[3] satisfy Assumption 3.4
For Algorithm 2 the subgradient E (t, x) lies in Span(Of(x). [x(x) according to Proposition
5.1 And the projection onto ((0, D) does disrupt the zero-respecting property. Thus, Algorithm
2 satisfies Assumption 3.4
For Algorithm we only need to prove that the gradient mapping X satisfies
Xk+1 E Span Span(V/(xx)) (xxo). Vg(xo), ... (x(x)), Vg(x)))
We denote S₁ Span (V (xx), Vg(xo), ... fxxx), Vg(x+)H According to Proposition 5.2 suffices to prove that the three descent step candidates X1, X2 and x3 are Sg. It clear that
Yk vfly). 1 Vğlvx) E Sk.
Then after projection onto B(O, D), x, X2 are still in Sp.
The case for X3 is slightly more complicated. Let = Yk I V w = -vjy)) and f(y+) g(yk) (w. - t. Then H = fx w x + b 0}. The point x3 is the solution the following convex optimization problem:
min XER
|xx z 2|2
s.t.
|xx|2 < 2
w x =
The Lagrangian for this problem is:
L(x, A. = ||x 2|1 X(||x 2 D2) u(( bb) where À > 0 and μ are dual variables. The KKT conditions give:
VxL(x,X, 1) 2(x3 2) 2Xx; JAW 0.
Thus
2z Pm
2(1 A)
implying that X3 is the linear combination of and Since 2, Sk. it follows that Sk-
0
20

---

Remark C.1. By similar analysis, we can show that the conditional gradient type methods for simple bilevel problems [3] on domain B(xo, D) also fall into the tero-respecting function class. At each deration k their methods relies on the following linear program as an oracle.
Sk arg min (V [xxx; 8)
BEA&
where Xx (s (Vg(xx); --xx) E g(xo) g(xx) }}. According to our proof of Proposition C.1 it suffices to prove that St. linear combination of V f(xx) and Vg(xx) then the remaining proofs are the same. Similarly, this can be seen by the KKT condition when = B(0, D), which is
X
[x(x)) + 2Xx + (X)( 0,
where X 2 0 and μ 0 are dual variables.
D Finding absolute optimal solutions under additional assumptions
In Section 4 we showed that, in general, is intractable for any zero-respecting first-order methods to find an absolute optimal solution of Problem ( However, it is possible to establish lower bound for fxx) f under additional assumptions. Hölderian error bound [2] is well-studied regularity condition in the optimization literature and is utilized by previous works to establish the convergence rate of finding absolute optimal solutions [6 13 24]. Prior to our work, the best- known result is established by Cao et al. [6], whose method achieves a (c,, --)-olluuueee optimal iterations. Below will show that our proposed methods also work well with such an additional assumption and achieve superior convergence rates with regard to absolute suboptimality.
solution for smooth problems in Ô maxx {1/E,"
20 - 11/g
2g 11/6"")
})
Assumption D.1. The lower-level objective g satisfies the Hölderian error bound condition for some and B > 0, i.e.
(ist(xx,X;)* (x( -g", E
where (x, x35) A infyex; ||x yll for arbitrary norm ||-
Intuitively, when the lower-level suboptimality g(x) g" is small, & should be close &2 if Hölderian error bound condition holds for g. Then we can lower bound f(x) f f by the convexity of Jiang et al. [3] formalizes the idea in the following proposition:
Proposition D.1 (Jiang et al. [13] Proposition 4.1J). Assume that f is convex and satisfies Assump- is the dual norm of Then holds
tion D.I Define M maxxex; (x)]]())ll where ||
that
- -M /a(g()) 9-)
for any & E IR..
This proposition shows that when g(x)
(3x)-9- S (1eeg) 0 it holds that f( Combining
with Corollary(5.1 [.1] we obtain:
hold and g satisfies Assumption FC and FC-BiOs find (cf: fg) (g).fg)aa -absolute optimal solution within the complexity of D.
Corollary D.1. Suppose Assumption 3.2 Assumption
3.3
δ max
C2 c² C., C²Mp2=0'
D2) and δ max {v
[T
Lg
D) for Lipschitz and Beg
2 T 322 smooth problems, respectively.
To our knowledge, this is the first result that establishes a convergence rate concerning absolute suboptimality for Lipschitz problems. In smooth setting, our result of Ô mmxx {1/e² 1/e }} is also superior to the convergence rate reported by Cao et al. 6 in both upper-level and lower-level.
E Experiment details
In this section, we provide more details of numerical experiments in Section 6 All experiments are implemented using MATLAB R2022b on PC running Windows 11 with 12th Gen Intel(R) Core(TM) 17-12700H CPU (2.30 GHz) and 16GB RAM.
21

---

E.1 Problem 11
This problem a (Ly, Lg)-Lggooott problem with L, 1, Lg Amax A A).
Experiment setting The original Wikipedia Math Essential dataset [22] contains 1068 instances with 730 attributes. Following the setting of Jiang et [33 and Cao al. 66. we randomly choose one of the columns as the outcome vector and let the rest be the new feature matrix. We uniformly sample 400 instances to make the lower-level regression problem over weerppraameterized. In this case, the upper-level problem is actually equivalent to
min xE2
|x|
s.t. =
The optimal solution x" for this problem can be explicitly solved via the Lagrange multiplier method:
(1
x
b
AT
=
v
where v is the Lagrange multiplier. Then we use f
x 12.1 9" 0 as the benchmark.
Implementation details To be fair, all algorithms start from the same random point Xo of unit length as the initial point. For Algorithm I take slightly different implementation, that instead of setting the maximum number of iterations of the inner subroutine to be T = T T/N, we preset T" 8000. If current X already satisfies (t, xx) S 5. then terminate the inner subroutine directly. We adopt the warm-start strategy as described in Appendix B.2 We set J. = 0 since f(x is nonnegative. For FC-BiOLi, set !j 4. For PB-APG, we set = 10" For Bi-SG, we set a = 0.75 and c = 1- For a-IRG, we
10-4 For AGM-BiO,
set
1 as in 6 Theorem
L,
set 7o 10-3 and To 10-3 For CG-BiO, we set 7 = 0.5/(k: + 1). For Bisec-Bid BiO, we set the maximum number of iterations of the internal APG process to be T' 10000. For FC-BiOss FC-BiOLiP and Bisec-Bid Bio, solving 3" takes 15000 iterations; for CG-BiO, solving g" takes 10000 iterations. The results of such pretreatments are also plotted in Figure]
E.2 Problem 12
This problem a (Ly, ( smooth problem with
L, 4m
1
1 Amax (anaxc((A) (Alaa)) A A"al), Lg 4m
Amax )
((A"))T An).
Experiment setting In this experiment, a sample of 5000 instances is taken from the "revl frevl.bing binarr"" dataset 8 [6] as the training set (A*r, b²r); another 5000 instances sampled as the validation set (Avol, b boa). Each label by" (or byol) is either +1 or 11
Implementation details In this experiment, we set the initial point xn = 0 for all methods. The implementation of our Algorithm is similar to that in the first experiment. We the maximum number of iterations of the subroutine to be T 500 and T" = 1000 for FC-BiO and FC-BiOLip respectively. For FC-BiOLip, we set 1) = For AGM-BiO, we set 1/( 21 2 + 2) in 6 L,
Theorem 4.4]. For PB-APG, set 10 For Bi-SG, set 0.75 and L, For a-IGG, 2 For FC-BiOsa, solving 9 takes 1000 we set = 10 and Yo 0.1. For CG-BiO, we set 7 = k42
iterations; for FC-BiO and CG-BiO, solving ÿ" takes 1500 iterations. As in the first experiment, the results of such pretreatments are also plotted in Figure
22

---

1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction outline our results accurately.
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 contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations and future directions in the last section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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 was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant 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 of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We state all the assumptions we need Section S We provide all proofs in the appendix.
23

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We present all experiment details in Section @ and Appendix E the codes to reproduce our results the supplementary materials.
We also include
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either way to access this model for reproducing the results or way to 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 case 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 have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
24

---

Answer: [Yes]
Justification: We present all experiment details Sen Appendix E We also include the codes to reproduce our results in the supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is 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 run reproduce the results. See the NeurlPS code and data submission guidelines (https /pips.ccc/pulic/guuu guwdes/ddee/eee Cowe/ooodeeeiiseeeeeeee hwtpibbmsssiooooooooiooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We present all experiment details in Section We also include the codes to reproduce our results in the supplementary materials.
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 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, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: We compare the training dynamics of the different algorithms in one graph on the same datasets with the same initialization. All the algorithms are deterministic.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence 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.)
25

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our experiments can be conducted on CPU with a single worker. (Detailed information is provided in Appendix E. We use the training time as the x-axis in the figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well 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 failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
This research follows the NeurlPS Code Ethics in all aspects.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses optimization theory, which has no direct societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal 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.
26

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used 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 (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: The methods proposed by this paper (near-optimal first-order methods for simple bilevel optimization problems) do not pose such risks of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make 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: [NA]
Justification: The paper does not use existing assets.
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 (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.paaersstt
package should be provided. For popular datasets, paperswi thcode. cow/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
27

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions 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 or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "O2MoYHg3fL", "reviewer": "Reviewer_RLu3", "summary": "The paper proposes a method to solve the bilevel problems where both upper and lower level objective functions are convex. The new algorithms, $FCB-BiO^{sm}$ combine bisection with sub-gradient or gradient methods to solve a reformulated problems to find a weak optimal solution. Convergence analyses show that the proposed method achieves the optimal rate up to a log factor. Numerical experiments illustrate the performance of $FCB-BiO^{sm}$ compared to existing works.", "questions": "1. To come up with an intial interval $[\\ell ,u]$, we need to run SGM or AGM applied to $g(x)$. However, to do so, we require knowledge of the Lipschitz constant which might not always be available. How can we come up with the interval in such cases?", "limitations": "The paper does discuss its limitation.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Different from other related work, the paper focuses on the reformulated minimax problem of the original bilevel optimization.\n- To solve the reformulated minimax problem, the paper uses bisection followed by gradient or sub-gradient methods.\n- The assumption in the paper is more relaxed than existing works that use Hölderian error bound condition.", "weaknesses": "- Theorem 4.1 and Theorem 4.2 are not well-motivated and unclear to me. The theorems state that for any algorithm that runs for a fixed budget of T iteration, there exists a problem instance such that we cannot achieve the absolute optimal solution. By showing this, the authors claim that finding absolute optimal solutions for the class of bilevel problem (1) is hard which I disagree. The key point is that, since we only run for T iterations, what if we did not run enough iterations so that the absolute optimal solution is achieved. As shown in the proof of Theorem 4.1 and Theorem 4.2, the authors come up with a problem of dimention $2T$ where the algorithms only run up to T iteration and in each iteration, only 1 component becomes non-zero. What if for the same problem, we allocate more budget of $\\hat{T}$ iteration where $\\hat{T} >> T$?\n- Also, showing that there exists one instance such that when running an algorithms for T iteration cannot lead to absolute optimal solution within T iteration does not mean that the problem cannot be solved for any T iteration for $T\\to\\infty$.\n- Due to the above concerns, the paper does not containt much novelty as the bisection technique has already been proposed in Wang et. al. (2024) [30], and the convergence result of the gradient/sub-gradient methods are known.\n\nMinor comments:\n- Typo at line 279: \"minimmum\" $\\to$ \"minimum\"?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for dedicating their valuable time and effort to evaluate our manuscript. However, there are some misunderstandings in the review that we wish to clarify.\n\n> W1 & W2: In the proof of Theorem 4.1/4.2, what if for the same problem, we allocate more budget of iterations, so that the absolute optimal solution is achieved? \n\n\nWe respectfully disagree with your opinion. Throughout the paper, we adopt the standard oracle complexity framework for first-order methods established by Nesterov and  Nemirovski [1], [4]. A crucial aspect of this framework is that the function class is defined in a **dimension-free** manner (i.e. the dimension of the function can be arbitrarily large).  More specifically, in this framework, all **upper bounds** developed for gradient methods are dimension-free (which is a nature of gradient methods such as GD, SGD, and AGM) , and the **hardness results**, including lower complexity bounds (e.g. Theorem 5.1/5.2) and intractability results (e.g. Theorem 4.1/4.2) should also be dimension-free. Below we list some of such hardness results established in previous works. [1-3]\n\nTherefore, when proving hardness results, it is reasonable to state that for any fixed $T>0$, there exists a \"hard problem\", whose dimension can be large and depend on $T$, that is unsolvable in $T$ steps. In other words, we showed that no zero-respecting first-order methods can solve absolute optimal solutions to simple bilevel problems dimension-freely.\n\nWe also want to highlight that,  similar to our proof, most existing hardness results for first-order methods involve constructing \"hard problems\" whose dimension is larger than $T$. For example:\n\n* Standard lower bound for convex minimization (Theorem 2.1.7 [1]).\n* Standard lower bound for nonconvex minimization (Theorem 1 [2]).\n* Recent intractability result for nonconvex-convex bilevel optimization (Theorem 3.2 [3]). They show that finding small hyper-gradients for nonconvex-convex bilevel optimization is hard for a fixed budget of $T$ iterations. \n\n[1] Nesterov, Yurii. Lectures on convex optimization. Vol. 137. Berlin: Springer, 2018.\n\n[2] Carmon, Y., Duchi, J. C., Hinder, O., & Sidford, A. (2020). Lower bounds for finding stationary points I. Mathematical Programming, 184(1), 71-120.\n\n[3]  Chen, L., Xu, J., & Zhang, J. On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis. In COLT, 2024.\n\n[4] Nemirovskij A. S., Yudin D. B. Problem complexity and method efficiency in optimization. 1983.\n\n\n> W3: Novelty; Similarity with Wang et. al. (2024) [1]\n\nWe appreciate the reviewer's feedback. We have addressed the rationality of Theorem 4.1/4.2 in our previous discussion. Below we would like to clarify the distinctions and contributions of our work in comparison to previous works.\n\nFirstly, while the bisection process in our proposed algorithm $\\texttt{FCB-BiO}$ might appear similar to the approach in Wang et. al. (2024) [1], the underlying motivations and objectives are fundamentally different. In Wang et. al. (2024) [1], the bisection is employed to transform the original problem $\\min f(x) \\ \\text{s.t.}\\  g(x)\\leq g^*$ to a series of  problems $\\min \\ g(x) \\ \\text{s.t.}\\  f(x)\\leq c$ for different $c$. In contrast, in $\\texttt{FCB-BiO}$, the original problem is reformulated to finding the smallest root of a univariate monotone auxiliary function $\\psi^*(t)$. For such one-dimensional root-finding problems, the bisection method is the most standard and straightforward approach.\n\nAdditionally, our reformulation improves the results in Wang et. al. (2024) [1].  Specifically, [1] requires an oracle that efficiently projects $x$ onto the sublevel set of $f$, i.e., {$x|f(x)\\leq t$}. This assumption only holds for a limited class of functions and would otherwise incur additional gradient evaluations. On the other hand, $\\texttt{FCB-BiO}$ does not need this assumption, making it applicable to a broader range of problems.\n\n\nIn summary, we view the main contribution of our work as **introducing the functionally constrained reformulation** to simple bilevel problems and proposing near-optimal method which is simple and effective. We also prove the intractability of finding absolute optimal solutions for zero-respecting first-order algorithms, and establish lower bounds for finding weak optimal solutions, ensuring the comprehensiveness of our study. The bisection search is only a subprocedure in our algorithm. \n\n[1]. Jiulin Wang, Xu Shi, and Rujun Jiang. Near-optimal convex simple bilevel optimization with a bisection method. International Conference on Artificial Intelligence and Statistics, 2024.\n\n> Minor Comments\n\nThanks for pointing out the typo. We will fix it in the revised version.\n\n\n> Q1: To come up with an initial interval $[\\ell,u]$，we need to run SGM or AGM applied to $g(x)$. This requires the knowledge of Lipschitz constant which might not always be available.\n\nThere are two approaches we can take to tackle this problem:\n\nFirst, tune the Lipshitz constant as a hyperparameter, which is also equivalent to tuning the learning rates.\n\nSecond, apply a parameter-free method on $g(x)$, such as [1,2].\n\n[1]  Guanghui Lan, Yuyuan Ouyang, and Zhe Zhang. \"Optimal and parameter-free gradient minimization methods for smooth optimization.\" arXiv preprint arXiv:2310.12139 (2023).\n[2] Itai Kreisler, Maor Ivgi, Oliver Hinder, and Yair Carmon. \"Accelerated Parameter-Free Stochastic Optimization.\" In COLT, 2024.\n\nWe thank the reviewer once again for the effort and time invested in the review. We would love to provide further clarifications if the reviewer has any additional questions.", "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": "52DDr1LQkv", "reviewer": "Reviewer_213i", "summary": "This work proposes a novel and near-optimal method to solve convex simple bilevel problems by finding weak optimal solutions. The author also provides theoretical and numerical guarantees of the convergence of this algorithm.", "questions": "1. What will happen if one of $f$ and $g$ is Lipschitz continuous and the other one is smooth?\n  \n2. What it is \",\" in eq.(5) but \";\" in eq.(6)?\n  \n3. Assumption 3.1.2 does not appear in previous works and seems very strong. Could the author further explain why this assumption is necessary and what the difficulties would be without it?\n  \n4. How does the author determine the initial interval $[l, u]$, and how does this interval affect the convergence?\n\nI would like to change my grade based on the response from the author.", "limitations": "No limitation", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper is easy to follow, with techniques that are rigorously proven and thoroughly explained.\n  \n2. This work is proven without the Hölderian error bound condition, and the lower bounds clearly demonstrate near-optimality in both Lipschitz and smooth settings.", "weaknesses": "1. Since this work focuses only on weak optimal solutions, the title *Near-Optimal Methods for Convex Simple Bilevel Problems* seems somewhat boastful.\n  \n2. There are some minor typos like missing space before \"When\" in line 238 and 261.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for dedicating their valuable time and effort to evaluate our manuscript. Below are our responses to the reviewer’s concerns.\n\n> W1: Since this work focuses only on weak optimal solutions, the title Near-Optimal Methods for Convex Simple Bilevel Problems seems somewhat boastful.\n\n\nIn this paper, we study two solution concepts, absolute optimal solutions and weak optimal solutions. However, when we say \"near-optimal\", we refer specifically to weak optimal solutions, as we have proven that absolute optimal solutions are intractable. \n\n\nWe aim to have a concise title that accurately reflects the focus of our work, and we are open to suggestions from the reviewers to further refine and improve the title.\n\n> W2: minor typos.\n\nThanks for pointing out the typos. We will carefully review and correct the typos in the revised version.\n\n> Q1: What will happen if one of $f$ and $g$ is Lipschitz continuous and the other one is smooth?\n\nThis is an interesting and valuable question. A similar intractability result of finding absolute optimal solutions as presented in Section 4 still holds in this case. The proof would be similar to the one of Theorem 4.1/4.2, by letting the lower-level objective g be a Lipschitz/smooth zero-chain and letting the upper-level function f be a quadratic function that only depends on the last half of the components. \n\nA similar lower bound for finding weak optimal solutions as in Section 5.1 can also be established, as the argument of decoupling the optimization processes for $f$ and $g$ still applies. More specifically, the lower bound would be $\\Omega \\left(\\max\\left(\\frac{L_f}{\\epsilon_f}D, \\frac{C_g^2}{\\epsilon_g^2}D^2\\right)\\right)$ if $f$ is $L_f$-smooth and $g$ is $C_g$-Lipschitz, or $\\Omega \\left(\\max\\left(\\frac{C_f^2}{\\epsilon_f^2}D^2,\\frac{L_g}{\\epsilon_g}D\\right)\\right)$ if $f$ is $C_f$-Lipschitz and $g$ is $L_g$-smooth. \n\nFor the upper bound, a smooth function is also Lipschitz-continuous in $\\mathcal B (\\mathbf x_0,D)$, thus applying $\\texttt{FCB-BiO}^{\\texttt{Lip}}$ directly gives the complexity of $\\tilde O(\\max\\{\\frac{1}{\\epsilon_f^2},\\frac 1 {\\epsilon_g^2}\\})$. If $\\epsilon_f\\asymp \\epsilon_g$, then the dependency on $\\epsilon$ is near-optimal. However, achieving near-optimal dependency on other parameters remains an open question and would be an interesting direction for future research.\n\n> Q2: What it is \",\" in eq.(5) but \";\" in eq.(6)?\n\nThis is a typo, and we apologize for any confusion it caused. The notation in (5) and (6) should be consistent and both signify the maximum of $f(\\mathbf x)-t$ and $\\tilde g(\\mathbf x)$\n\n> Q3: Assumption 3.1.2 does not appear in previous works and seems very strong. Could the author further explain why this assumption is necessary and what the difficulties would be without it?\n\nThe assumption that $\\|\\mathbf x-\\mathbf x_0\\|\\leq D$ is a technical assumption due to the bisection procedure. This procedure involves solving a series of subproblems $\\text{minimize} \\max(f(\\mathbf x)-t,\\tilde g(\\mathbf x))$ with resect to $\\mathbf x$ (Equation 6), the total complexity would depend on $\\max_t \\|\\mathbf x^*_{(t)}-\\bar {\\mathbf x}\\|$, where $\\bar {\\mathbf x}$ is the starting point of the subprocess, and $\\mathbf x_{(t)}^*$ is the optimal solution of the subproblem. The term $\\|\\mathbf x^*_{(t)}-\\bar {\\mathbf x}\\|$ cannot be bounded by the initial distance $\\|\\mathbf x^*-\\mathbf x_0\\|$ because $\\mathbf x^*_{(t)}$ might be far away from $\\mathbf x^*$. To address this, we restrict the domain to $\\mathcal B(\\mathbf x_0,D)$, ensuring that the distance term $\\|\\mathbf x^*_{(t)}-\\bar {\\mathbf x}\\|$ is always bounded by $D$ in each bisection step.\n\n> Q4: How to determine the initial interval $[\\ell, u]$, and how does this interval affect the convergence?\n\nAs mentioned in Line 201, we discuss how to determine the initial interval $[\\ell,u]$ in Appendix B.1. Specifically, we apply single-level optimization methods SGM/AGM to $f$ and $g$ respectively and solve approximate solutions $\\hat {\\mathbf x}_f,\\hat {\\mathbf x}_g$ such that\n$$\np^*\\leq f(\\hat {\\mathbf x} _f)\\leq p^*+\\frac \\epsilon 2,g^*\\leq g(\\hat {\\mathbf x} _g)\\leq g^*+\\frac \\epsilon 2,\n$$\nwhere $p^*,g^*$ are global minima of $f$ and $g$ respectively. Then setting $\\ell =  f(\\hat {\\mathbf x} _f)-\\frac \\epsilon 2\\leq p^*\\leq \\hat f^*$ would be a valid lower bound of $\\hat f ^*$, and setting  $u=f(\\hat {\\mathbf x}_g)$ would be a valid upper bound.\n\nAs presented in Theorem 5.3 and Theorem 5.4, the initial distance $u-\\ell$ affects the convergence rate up to a logarithm term. If $f$ is bounded, then $u-\\ell$ is also bounded. \n\nWe thank the reviewer once again for the valuable and helpful suggestions. We would love to provide further clarifications if the reviewer has any additional questions.", "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": "iC1QjzuH99", "reviewer": "Reviewer_KpB7", "summary": "This paper provides a theoretical proof that first-order zero-respecting algorithms are incapable of approximating the optimal solution for a simple bilevel optimization problem where both the upper-level and lower-level functions are convex. Then they propose a functional constrained reformulation to solve the simple bilevel problem. The method achieves the near-optimal convergence rate and shows good experimental results.", "questions": "Please refer to the weaknesses.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper provides the theoretical proof to show that the zero-respecting first-order methods cannot find absolute optimal solutions.\n\n- They proposed a novel algorithm FCB-BiO to find $(\\epsilon_f, \\epsilon_g)$-weak optimal solutions for non-smooth and smooth cases, and this method achieves the near-optimal rates.\n\n- Compared to [1], this paper gets rid of the weak sharp minima condition.\n\n[1] Cao, Jincheng, et al. \"An Accelerated Gradient Method for Simple Bilevel Optimization with Convex Lower-level Problem.\" arXiv preprint arXiv:2402.08097 (2024).", "weaknesses": "- Can other baselines like [1], [2] find $(\\epsilon_f, \\epsilon_g)$-weak optimal solutions? Actually, they can find absolute solutions with additional conditions, but hard to say they cannot work well for weak optimal solutions.\n\n- The experiments are little bit weak, and they simply specify $f(.)$ and $g(.)$ as quadratic functions. Can it be applied to neural networks? For example, $x$ is the model parameters of a neural network. \n\n- It would be better if authors can show the results on meta-learning or some other typical bilevel optimization problems.  \n\n- For Figure 1 and 2, do they take the warm-up time and initialization time into consideration?\n\n[1] Cao, Jincheng, et al. \"An Accelerated Gradient Method for Simple Bilevel Optimization with Convex Lower-level Problem.\" arXiv preprint arXiv:2402.08097 (2024).\n\n[2] Jiang, Ruichen, et al. \"A conditional gradient-based method for simple bilevel optimization with convex lower-level problem.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for dedicating their valuable time and effort to evaluate our manuscript. Below are our responses to the reviewer’s concerns.\n\n> W1: Can other baselines like [1], [2] find $(\\epsilon_f,\\epsilon_g)$ weak optimal solutions?\n\nActually, while some of the previous works have developed algorithms to find absolute solutions under additional assumptions, most previous methods, including [1], [2], aim to find weak optimal solutions. So yes, they can find weak optimal solutions. However, as we discussed in the \"Related work\" section, previous methods either do not achieve optimal convergence rate (e.g. [2], which only achieves a suboptimal $O(1/\\epsilon)$ rate for smooth problems), or require additional assumptions such as weak sharp minima condition (e.g. [1]). In contrast, our proposed method achieves near-optimal rates without needing such assumptions.\n\n[1] Cao, Jincheng, et al. \"An Accelerated Gradient Method for Simple Bilevel Optimization with Convex Lower-level Problem.\" arXiv preprint arXiv:2402.08097 (2024).\n\n[2] Jiang, Ruichen, et al. \"A conditional gradient-based method for simple bilevel optimization with convex lower-level problem.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2023.\n\n> W2: The experiments are little bit weak, and they simply specify $f$ and $g$  as quadratic functions. Can it be applied to neural networks? \n\nWe would like to clarify that in our second experiment, the objective functions $f,g$ are the loss functions of logistic regression, rather than quadratic functions. We acknowledge that our method is designed for convex simple bilevel optimization problems as in many previous works, thus is not directly applicable to neural networks which are nonconvex. However, we would like to highlight that there is **no existing theory** for simple bilevel problems with nonconvex lower-level objectives.  But we are willing to study it in the future works.\n\n> W3: It would be better if authors can show the results on meta-learning or some other typical bilevel optimization problems.\n\n\nMeta-learning takes the following form:\n$$\n\\begin{align*}\n\\min_{x,y}\\ & f(y)\\\\\\\\\n{\\rm s.t.} \\quad y\\in & \\arg\\min_z g(z)+\\frac \\lambda 2 \\|x-z\\|^2\n\\end{align*}\n$$\nwhich is a more general bilevel setting where the lower-level problem is parameterized by the upper-level variable $x$. See Equation 4 in [3]. This is different from our setup of simple bilevel optimization (Equation 1 in the manuscript).\n\n[3] Rajeswaran, A., Finn, C., Kakade, S. M., & Levine, S. Meta-learning with implicit gradients. In NeurIPS, 2019. \n\n> W4: For Figure 1 and 2, do they take the warm-up time and initialization time into consideration?\n\nYes, as discussed in Appendix E, the initialization time is also taken into account and is plotted in Figure 1 and Figure 2 of the manuscript. In the attached pdf in the general response, the initialization stage is plotted with dashed lines in Figure 1 and Figure 2.\n\nWe thank the reviewer once again for the effort and time invested in the review. We would love to provide further clarifications if the reviewer has any additional questions.", "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": "TSv59Fcf2F", "reviewer": "Reviewer_iPzZ", "summary": "This work studies simple bilevel problems with convex upper and lower level objectives. The paper studies the problem for both smooth and Lipschitz functions. The contribution is two folded: 1- first, it shows that no zero-respecting algorithm can achieve $(\\epsilon_f,\\epsilon_g)$ absolute optimal solutions for limited number of iterations. 2- Second, it proposes the iteration complexity lower bound for first-order zero respecting algorithms and proposes a method that achieves this lower bound up to a logarithmic factor. The proposed method is achieved through relaxing Problem 1 to Problem 4 and solving this problem through a bisection procedure and Lemma 2.3.4 from [20]. Numerical experiments were conducted to study and compare the proposed method.", "questions": "Could you please explain your reasoning and ideas regarding the points raised in the \"Weaknesses\" section? Thanks!", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper has good literature review and good structure. I enjoyed reading it.", "weaknesses": "**Writing:**\n\n1- paragraph starting from line 24: the first and second sentences are opposing each other. Meaning that the second sentence should bring something in contrast to what expressed in the first sentence. This is expected due to the use of \"Yet\". However, the comparison is not correct since the first sentence assumes an explicitly given constraint set while the second sentence is mentioning Problem 1 which does not have an explicit constraint set (which should be the case for bilevel programs).\n\n2- In (5) it feels like a constraint over $x$ is missed in the minimization. Please clarify, thanks!\n\n3- Line 205, the sentence starts with \"And\", but this sentence is connected to the previous sentence. Please fix!\n\n4- Line 309, \"It is open whether ...\" sounds a bit informal, please revise, thanks!\n\n5- Statements of Theorems 4.1, 4.2: \"there exists an (1,1)...\" should be \"there exists a (1,1)...\" to help readability.\n\n\n**Technical:**\n\n1- Discussion below Theorem 4.2 on its proof states that the failure of the algorithms happen when $n\\geq 2T$ where $n$ is the problem dimension and $T$ is the number of calls to the first order oracle. This, however, was not mentioned anywhere else (at least I did not see it). This means that if you go beyond a number of calls to the oracle, then you can actually reach the approximate absolute optimal solutions and your first claim/contribution is falsified.\n\nI'd like to add that the paper is studying the zero respecting property, which enforces coordinate-wise updates at each iteration. Convergence rate of $\\mathcal O(n/T)$ is typical for coordinate methods when applied to convex problems. Thus, the dependency on $n$ (problem dimension) is expected naturally.\n\n2- As a part of the algorithm, the initialization should be, though briefly, explained in the main body of the paper. I kindly suggest considering it.\n\n3- The Bisec-Bio method showed a close behaviour in the first experiment (Figure 1). Due to the similar performance (not the same) between this method and the proposed method it is expected to see a more detailed comparison between these two in the second experiment. Unfortunately, this was skipped. More careful design of the second experiment might be helpful to increase the impact of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for dedicating their valuable time and effort to evaluate our manuscript. However, there are some misunderstandings in the review, and we respond to your concerns one by one.\n\n> Writing\n\nThanks for the valuable suggestions! We will incorporate your advice in the revised version.\n\n> Technical Weakness 1: Theorem 4.1/4.2\n\nWe respectfully disagree with your opinion. Throughout the paper, we adopt the standard oracle complexity framework for first-order methods established by Nesterov and  Nemirovski [1], [4]. A crucial aspect of this framework is that the function class is defined in a **dimension-free** manner (i.e. the dimension of the function can be arbitrarily large).  More specifically, in this framework, all **upper bounds** developed for gradient methods are dimension-free (which is a nature of gradient methods such as GD, SGD, and AGM) , and the **hardness results**, including lower complexity bounds (e.g. Theorem 5.1/5.2) and intractability results (e.g. Theorem 4.1/4.2) should also be dimension-free. Below we list some of such hardness results established in previous works. [1-3]\n\nTherefore, when proving hardness results, it is reasonable to state that for any fixed $T>0$, there exists a \"hard problem\", whose dimension can be large and depend on $T$, that is unsolvable in $T$ steps. In other words, we showed that no zero-respecting first-order methods can solve absolute optimal solutions to simple bilevel problems dimension-freely.\n\nWe want to clarify that our hardness result applies to zero-respecting algorithms, which update all $n$ coordinates simultaneously. This is different from coordinate methods that only update one coordinate at each iteration.\n\nWe also want to highlight that,  similar to our proof, most existing hardness results for first-order methods involve constructing \"hard problems\" whose dimension is larger than $T$. For example:\n\n* Standard lower bound for convex minimization (Theorem 2.1.7 [1].\n* Standard lower bound for nonconvex minimization (Theorem 1 [2]).\n* Recent intractability result for nonconvex-convex bilevel optimization (Theorem 3.2 [3]). They show that finding small hyper-gradients for nonconvex-convex bilevel optimization is hard for a fixed budget of $T$ iteration. \n\n[1] Nesterov, Yurii. Lectures on convex optimization. Vol. 137. Berlin: Springer, 2018.\n\n[2] Carmon, Y., Duchi, J. C., Hinder, O., & Sidford, A. (2020). Lower bounds for finding stationary points I. Mathematical Programming, 184(1), 71-120.\n\n[3]  Chen, L., Xu, J., & Zhang, J. On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis. In COLT, 2024.\n\n[4] Nemirovskij A S, Yudin D B. Problem complexity and method efficiency in optimization. 1983.\n\n\n> Technical Weakness 2: As a part of the algorithm, the initialization should be, though briefly, explained in the main body of the paper. \n\nThank you for the suggestion! We will add a concise explanation in the main body of the paper in the revised version.\n\n> Technical Weakness 3: Comparison with Bisec-BiO method in the experiment.\n\nThe Bisec-BiO method has the same convergence rate as our proposed method FCB-BiO, thus shows a close behavior in the first experiment. However, we highlight that the advantage of FCB-BiO over Bisec-BiO is that its **applicability in a broader range of problems** (instead of a faster convergence on problems that both can solve). That's because Bisec-BiO requires a strong assumption that projection onto the sublevel set of the upper-level objective {$x|f(x)\\leq a$} is easy to compute, while FCB-BiO **does not** rely on such an assumption. In the second experiment, the projection onto the sublevel set of the upper-level objective cannot be solved efficiently, rendering Bisec-BiO inapplicable.\n\nIn summary, the first experiment was designed to illustrate a scenario where both methods are applicable and show comparable performance as expected. The second experiment, on the other hand, highlights a scenario where Bisec-BiO fails to apply,  yet our method is still applicable and shows near-optimal performance.\n\nWe thank the reviewer once again for the effort and time invested in the review. We would love to provide further clarifications if the reviewer has any additional questions.", "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": "dDU40Pf9TR", "reviewer": "Reviewer_EaJT", "summary": "The paper first shows the difficulties of obtaining the absolute optimal solutions to simple convex bilevel problems. The authors also present the lower bound of the first-order methods for solving simple convex bilevel problems. Moreover, the authors proposed a novel framework based on functionally constrained reformulation. Based on the framework, they developed near-optimal algorithms for solving simple convex bilevel problems under smooth and non-smooth settings.", "questions": "See weaknesses.", "limitations": "No negative societal impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper shows the difficulties of obtaining the absolute optimal solutions to simple convex bilevel problems under common assumptions.\n2. The authors present the lower bounds of the first-order methods for solving simple convex bilevel problems, which are $\\Omega(1/\\sqrt{\\epsilon})$ and $\\Omega(1/\\epsilon^{2})$ for smooth and non-smooth settings, respectively.\n3. The authors also present the algorithms for solving these types of problems, which match the lower bounds ignoring the logarithmic factors.", "weaknesses": "1. Many lemmas in this paper are directly quoted from other works, but some, such as Lemma 5.4 and 5.5, are not identical to the original ones. It would be better to provide proof for these lemmas. \n2. In this paper, the authors only consider the unconstrained case, while many other works about simple bilevel optimization consider the constrained case.\n3. In this numerical experiment, the authors should count the time of finding initial $u$ and $l$ and show it on the plots. Otherwise, it is not a fair comparison, as the complexity of finding the initial $u$ and $l$ has the same complexity as the main stage.\n4. The desired accuracy ($10^{-2}$ in Figures 1 and 2) for the experiments is not small enough. It would be better to set them to be smaller than $10^{-6}$ and see the performances of the algorithms for the late stage.\n5. The proposed algorithm requires a predetermined $T$, whereas similar studies do not have this requirement.\n6. The novelty of this work is limited, as the main idea is borrowed from [1] with some extensions, and many of the technical proofs are identical to [2] and [3].\n\nReferences:\n\n[1]. Jiulin Wang, Xu Shi, and Rujun Jiang. Near-optimal convex simple bilevel optimization with a bisection method. \n\n[2]. Yurii Nesterov. Lectures on convex optimization\n\n[3]. Sébastien Bubeck et al. Convex optimization: Algorithms and complexity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for dedicating their valuable time and effort to evaluate our manuscript. Below are our responses to the reviewer’s concerns:\n### W1\nThanks for the suggestion! We will provide self-contained proofs for these lemmas in the revised version.\n### W2\nActually, our method can be extended to the constrained case where the feasible set is convex and compact (as in many previous works, e.g. [1][2]). In our manuscript, we focus on the unconstrained case so as to provide a clearer discussion. \n\nSpecifically, if the feasible set of the problem is a convex and compact set $\\mathcal X$, one only needs to replace the Euclidean ball $\\mathcal B(\\mathbf x_0,D)$ in the original problem with $\\mathcal X$. For Lipschitz problems, computing a projection onto $\\mathcal X$ is needed in each gradient step, which is standard. For smooth problems, one needs to compute the projection onto the intersection of $\\mathcal X$ and a hyperplane (see Proposition 5.2), which is also needed by previous work [1]. \n### W3\nAs presented in Appendix E, the initialization time is already taken into account in the numerical experiments and is shown in the plots. In the attached pdf in the general response, the initialization stage is plotted with dashed lines in Figure 1 and Figure 2.\n### W4\nIn the first experiment (Figure 1), we actually set the desired accuracy $\\epsilon_f=\\epsilon_g = 10^{-6}$. As we noted in Line 628-629, a $(\\epsilon_f,\\epsilon_g)$-weak optimal solution is indeed solved by $\\texttt{FCB-BiO}^{\\texttt{sm}}$, since the approximate solution $\\hat {\\mathbf x}$ found by the algorithm satisfies $g(\\hat {\\mathbf x })\\leq g^*+\\epsilon_g, f(\\hat {\\mathbf x})\\leq f^*\\leq f^*+\\epsilon_f$. However, to present the results more clearly, Figure 1 shows the **absolute optimality gap** $|f(\\hat {\\mathbf x})-f^*|$, instead of the weak optimality gap $f(\\hat{\\mathbf x})-f^*$. Since the aim is to find a **weak optimal solution**, the absolute optimality gap does not converge to a very small level.\n\nThe vertical axis of Figure 2 does not indicate the accuracy. As we remarked in Line 634-636, to the best of our knowledge, no existing solver can solve the exact optimal value $f^*,g^*$ of the second experiment. Thus we plot the function values $f(x),g(x)$, instead of the suboptimality gaps $f(x)-f^*$, $g(x)-g^*$ in Fugure 2.\n\nTo better demonstrate the performances of the algorithms for the late stage, we conducted another numerical experiment. The setup and result of the experiment are presented in the general response and the attached pdf. In this experiment, we set $\\epsilon_g=10^{-9}$ and $\\epsilon_f=10^{-6}$. The results again show the superior performance of our method compared to existing methods in both upper-level and lower-level in the late stage.\n### W5\nFCB-BiO is a double-loop algorithm (bisection as the first level and SGM/generalized AGM as the second level). We need to predetermine a $T$ (which is equivalent to predetermining a desired accuracy $\\epsilon$) to stop the subprocess (SGM/generalized AGM) when it runs for enough time and the approximate solution is accurate enough.  Many previous double-loop methods also need to tackle such issues, such as Catalyst[5].\n\nWe would like to remark that some previous works also need to predetermine the number of iterations $T$ to set the hyperparameters, e.g. learning rate, such as Theorem 4.4 in [1] and Proposition 1 in [3].\n### W6\nWe appreciate the reviewer's feedback and would like to clarify the distinctions and contributions of our work in comparison to previous works.\nFirstly, while the bisection process in our proposed algorithm $\\texttt{FCB-BiO}$ might appear similar to the approach in Wang et. al. (2024) [4], the underlying motivations and objectives are fundamentally different. In Wang et. al. (2024) [4], the bisection is employed to transform the original problem $\\min f(x) \\text{ s.t.}\\  g(x)\\leq g^*$ to a series of  problems $\\min \\ g(x) \\text{ s.t.}\\  f(x)\\leq c$ for different $c$. In contrast, in $\\texttt{FCB-BiO}$, the original problem is reformulated to finding the smallest root of a univariate monotone auxiliary function $\\psi^*(t)$. For such one-dimensional root-finding problems, the bisection method is the most standard and straightforward approach.\n\nAdditionally, our reformulation improves the results in Wang et. al. (2024) [4].  Specifically, [4] requires an oracle that efficiently projects $x$ onto the sublevel set of $f$, i.e., {$x|f(x)\\leq t$}. This assumption only holds for a limited class of functions and would otherwise incur additional gradient evaluations. On the other hand, $\\texttt{FCB-BiO}$ does not need this assumption, making it applicable to a broader range of problems.\n\nIn summary, we view the main contribution of our work as **introducing the functionally constrained reformulation** to simple bilevel problems and proposing a near-optimal method which is simple and effective. We also prove the intractability of finding absolute optimal solutions for zero-respecting first-order algorithms, and establish lower bounds for finding weak optimal solutions, ensuring the comprehensiveness of our study. The bisection search is only a subprocedure in our algorithm.\n\n[1] Cao, Jincheng, et al. An Accelerated Gradient Method for Simple Bilevel Optimization with Convex Lower-level Problem.\n\n[2] Jiang, Ruichen, et al. A conditional gradient-based method for simple bilevel optimization with convex lower-level problem.\n\n[3] Samadi S, et al. Achieving optimal complexity guarantees for a class of bilevel convex optimization problems.\n\n[4] Jiulin Wang, et al. Near-optimal convex simple bilevel optimization with a bisection method. \n\n[5] Lin H, et al. A universal catalyst for first-order optimization. \n\nWe thank the reviewer once again for the effort and time invested in the review. We would love to provide further clarifications if the reviewer has any additional questions.", "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:
We are deeply grateful for the efforts and valuable feedback of the reviewers and area chairs in reviewing our manuscript. 

Combining the suggestions of the reviewers, we conduct an additional numerical experiment to better compare the performance of $\texttt{FCB-BiO}$ with other methods. Following previous works [1],[2], we consider the over-parameterized linear regression problem. We use the Wikipedia Math Essential dataset [24], which contains $1068$ instances with $730$ attributes.  We use $50\%$ of the dataset as the training set $(A^{tr},\mathbf b^{tr})$ and $50\%$ of the dataset as the validation dataset $(A^{val},\mathbf b^{val})$. The problem can be formulated as:

$$
\begin{aligned}
\min f(\mathbf x)&:=\frac 1{2m^{val}} \|A^{val}\mathbf x-\mathbf b^{val}\|^2,\\\\
\text{s.t.}\quad \mathbf x&\in \arg\min_{\mathbf z}g(\mathbf z):=\frac 1 {2m^{tr}}\|A^{tr}\mathbf z -\mathbf b^{tr}\|^2.
\end{aligned}
$$

The result is shown in Figure 3 in the uploaded pdf. The initialization time is plotted with dashed lines.

In this experiment, we set $\epsilon_g=10^{-9}$ and $\epsilon_f=10^{-6}$. The optimal solution of this problem can be solved by Lagrange multiplier method. The result again shows the superior performance of our method compared to existing methods in both upper-level and lower-level. We remark that in this experiment, an $(\epsilon_f,\epsilon_g)$-**absolute optimal solution** is solved by $\texttt{FCB-BiO}$. But this is not a contradiction to our hardness result in Section 4. For this problem, the lower-level objective satisfies the second-order Holderian Error Bound condition. As we discussed in Appendix D, $\texttt{FCB-BiO}$ can solve the absolute optimal solution with the best known rate when the lower-level objective satisfies this additional Holderian error bound condition.

In this experiment, we set the initial point $\mathbf x_0$ to be a random vector of unit length. For $\texttt{AGM-BiO}$, we set $\gamma = 1 /(\frac {2L_g}{L_f}T^{2/3}+2)$ as in Theorem 4.4 [1]. For $\texttt{PB-APG}$, we set $\gamma = 10^5$. For $\texttt{a-IRG}$, we set $\eta_0=1$ and $\gamma_0=10^{-3}$. For $\texttt{CG-BiO}$, we set $\gamma_k = \frac 2 {k+1}$. 

[1] Cao, Jincheng, et al. "An Accelerated Gradient Method for Simple Bilevel Optimization with Convex Lower-level Problem." arXiv preprint arXiv:2402.08097 (2024).

[2] Jiang, Ruichen, et al. "A conditional gradient-based method for simple bilevel optimization with convex lower-level problem." International Conference on Artificial Intelligence and Statistics. PMLR, 2023.

Meta-review: Simple bilinear optimization is the problem of minimizing a function f(x) subject to the constraint that x \in argmin g(x) where f and g are convex functions. This problem is equivalent to solving min f(x) s.t. g(x) <= min_z g(z) (i.e., it is a nonlinear constrained optimization problem with a single constraint).

This paper combines ideas from several different parts of the optimization literature to resolve the complexity of simple bilinear optimization. Experimental results of the proposed algorithm on finding the minimum norm solution of a linear system and overparameterized linear models indicate it is potentially practical. The reviewers appreciated that the paper was well written. There were some concerns raise by the reviewers EaJT about the limited novelty of the work given that it primarily specializes ideas from Nesterov's convex optimization lecture notes to simple bilinear optimization. 

Comments:
-  Definitions of zero-respecting and zero chains are not correct. These terms are defined originally in [8] and are generalization of the ideas of Nesterov, please use them correctly or use other terms.
- It should be made crystal clear in the text that Theorem 5.1 and Theorem 5.2 follows immediately from existing lower bounds. Also the proof can be simplified: it suffices simply to observe which of L_f and L_g is larger and then set the corresponding function to the standard lower bound and the other function to zero.
Decision: Accept (poster)