Functionally Constrained Algorithm Solves Convex Simple Bilevel Problem

Authors: huaqing  zhang
lesi  chen
jing  xu
jingzhao  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 04:43:33

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 novel near-optimal methods for smooth and nonsmooth problems by reformulating them into functionally constrained problems.

Main paper: 
 introduction: 
 This work focuses on the following optimization problem:EQUATIONwhere f, g are convex and continuous functions and Z ⊆ R n is a compact convex set. Such a problem is often referred to as "simple bilevel optimization" in the literature, as the upper-level objective function f is minimized over the solution set of a lower-level problem. It captures a hierarchical structure and thus has many applications in machine learning, including lexicographic optimization [12, 14] and lifelong learning [12, 17] . Understanding the structure of simple bilevel optimization and designing efficient algorithms for it is vital and has gained massive attention in recent years [1, 5, 6, 10-13, 18, 22-26] .To solve the problem, one may observe that Problem (1) is equivalent to the convex optimization problem min x∈X * g f (x) with implicitly defined convex domain X * g . Hence, it is natural to try to design first-order methods to find x ∈ R n such thatEQUATIONwhere f * is the optimal value of Problem (1) and g * is the optimal value of the lower-level problem.We highlight the asymmetry in f and g here. f * is the minimal in a constrained set, and hence it is possible that f (x) < f * for some x ∈ R n . On the other hand, g * is globally minimal and hence g * ≤ g(x) for any x ∈ R n . Such asymmetry is natural as the role of f, g are inherently asymmetrical for bilevel problems. We call such x a (ϵ f , ϵ g )-absolute optimal solution.When X * g 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 (1) . 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 x ∈ R n such thatEQUATIONwhich we call a (ϵ f , ϵ g )-weak optimal solution. Much progress has been achieved towards this goal [10, 17, 18, [22] [23] [24] . We note all the above algorithms fall in the class of zero-respecting algorithms (Assumption 3.4) and hence cannot obtain absolute optimal solutions.Our second contribution pushes this boundary by proposing near-optimal lower and upper bounds.We study two settings: (a) f is C f -Lipschitz and g is C g -Lipschitz, (b) f is L f -smooth and g is L g -smooth. We can extend the worst-case functions for single-level optimization to Problem (1) to show lower bounds of1. Ω max C 2 f /ϵ 2 f , C 2 g /ϵ 2 gfor the setup (a);2. Ω max L f /ϵ f , L g /ϵ g for the setup (b).Given our constructed lower bounds, we further improve known upper bounds by reducing the task of finding (ϵ f , ϵ g )-weak optimal solutions to minimizing the functionally constrained problem:EQUATIONThen we further leverage the reformulation by Nesterov [19, 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:EQUATIONBased on this reformulation, we introduce a novel method FC-BiO (Functionally Constrained Bilevel Optimizer). FC-BiO is a double-loop algorithm. It adopts a bisection procedure on t in the outer loop and applies gradient-based methods to solve the sub-problem (5) . Our algorithms achieve the following upper bounds:1. Õ max C 2 f /ϵ 2 f , C 2 g /ϵ 2 gfor the setup (a);2. Õ max L f /ϵ f , L g /ϵ 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 our contributions as follows:• We prove the intractability for any zero-respecting first-order methods to find a (ϵ f , ϵ g )absolute optimal solution of simple bilevel problems.• We propose a novel method FC-BiO that has near-optimal rates for finding (ϵ f , ϵ g )-weak optimal solutions of both nonsmooth and smooth problems.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. 
related work: 
 In the literature, various methods [1, 3, 6, 10-13, 17, 18, 22-26] have been proposed to achieve a (ϵ f , ϵ g )-weak optimal solution defined as Equation (3) . Below, we review the existing methods with non-asymptotic convergence. For ease of presentation, we state the results for ϵ f = ϵ g = ϵ.Prior results on Lipschitz problems Kaushik and Yousefian [13] proposed the averaging iteratively regularized gradient method (a-IRG) for convex optimization with variational inequality constraints, of which Problem (1) is a special case. a-IRG achieves the rate of O(1/ϵ 4 ). Shen et al. [24] proposed a method for solving Problem (1) with O(1/ϵ 3 ) complexity based on the online learning framework. When f is Lipschitz and g is smooth, Merchav and Sabach [18] proposed a gradient-based algorithm with O(1/ϵ 1/(1-α) ) complexity for any α ∈ (0.5, 1). However, none of these methods can achieve the optimal rate of O(ϵ -2 ).Prior results on smooth problems Samadi et al. [23] proposed the regularized accelerated proximal method (R-APM) with a complexity of O(1/ϵ). Under the additional weak sharp minima condition on g, the complexity of R-APM improves to O (1/ √ ϵ). However, this condition is often too strong and does not hold for many problems. Chen et al. [10] extended the result of [23] to the more general α-Hölderian error bound condition. However, their method achieves the optimal rate only when α = 1, which reduces to the weak sharp minima condition. Jiang et al. [12] developed a conditional gradient type algorithm (CG-BiO) with a complexity of O (1/ϵ), which approximates X * g similar to the cutting plane approach. Later on, Cao et al. [6] proposed an accelerated algorithm with a similar cutting plane approach to achieve the rate of O(1/ √ ϵ) under the weak sharp minima condition. Recently, Wang et al. [27] reduced Problem (1) to finding the smallest c such that the optimal value of the following parametric problem is g * : min x∈R n g(x), s.t. f (x) ≤ c. They adopted a bisection method to find such a c. To solve this parametric problem, Accelerated Proximal Gradient method is applied on g with projection operator onto the sublevel set F c = {x | f (x) ≤ c}, which we call sublevel set oracles, which we call sublevel set oracles. This leads to an upper bound of Õ(1/ √ ϵ). Such an oracle is obtainable for norm-like functions such as f (x) = 1 2 ∥x∥ 2 . However, projection onto sublevel sets may be hard for more general functions, such as MSE loss or logistic loss. Compared with prior works [6, 10, 23, 27] , our proposed methods achieve the Õ(1/ √ ϵ) rate under standard assumptions, without relying on the weak sharp minima condition or the sublevel set oracles.Comparison with Nesterov's methods for functionally constrained problems Based on similar reformulation, Nesterov [19] hasve proposed algorithms for functionally constrained problems, of which Problem (4) is a special case: one for smooth problems in Section 2.3.5, and one for Lipschitz problems in Section 3.3.4. However, the first algorithm relies on the strong convexity of f and g, which does not hold in our setups. Moreover, both algorithms require quadratic program (QP) sub-solvers, which are inefficient in large-scale problems: the first algorithm uses it to iteratively move t to the root of ψ * (t), while the second algorithm uses it to project onto the sublevel set of a piecewise linear approximation of ψ(t, x). In contrast, our proposed algorithms have the following advantages: (a) require no strong convexity assumption; (b) require no QP solvers that lead to additional computational cost; (c) have a unified framework for both smooth and Lipschitz problems.Bisection procedure Based on the preceding reformulation, we propose Algorithm 1 (FC-BiO), which uses a bisection procedure to estimate the smallest root of ψ * (•). For now, we assume that the desired accuracy on upper-level and lower-level problems is the same, (i.e. ϵ f = ϵ g = ϵ). Later we will show in Corollary 5.1 that we can handle the case when ϵ f ̸ = ϵ g by simply scaling the objectives.Algorithm 1 applies the bisection method within an initial interval [ℓ, u] which contains the smallest root, f * , for N = log 2 u-ℓ ϵ/2 iterations. Similar to [27] , 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 , while u = f (x g ) serves as a valid upper bound, where xg is an approximate solution to the lower-level problem. Further details can be found in Appendix B.1. In each iteration, we set t = ℓ+u 2 . To approximate the function value of ψ * (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) [19, Algorithm 2.3.12] . These methods guarantee to find an approximate solution x(t) of Problem (7) such thatEQUATION) If ψ * (t) > ϵ/2, we update ℓ = t. Conversely, if ψ * (t) ≤ ϵ/2, we set u = t.For the initial point of M, we exploit a warm-start strategy (see more details in Appendix B.2). After completing N iterations, we return x = x(u) as the output. As shown in Lemma 5.3, x is guaranteed to be a (ϵ, ϵ)-weak optimal solution to Problem (1).We remark that since we can only solve an approximate value of ψ * (t), the upper bound u might fall below f * during the bisection process. But this is acceptable since we are only in pursuit of a weak optimal solution instead of an absolute optimal solution. Lemma 5.3. If ĝ * satisfies g * ≤ ĝ * ≤ g * + ϵ 2 and (8) holds for every t in the process of Algorithm 1, then the approximate solution x returned by Algorithm 1 is a (ϵ, ϵ/2)-weak optimal solution to Problem (4), and therefore a (ϵ, ϵ)-weak optimal solution to Problem (1) by Lemma 5.1.According to this lemma, O(log( 1 /ϵ)) iterations of the outer loops are sufficient to find a (ϵ, ϵ)-weak optimal solution. Next, we will discuss the process and complexity of the subroutines in detail.Algorithm 2 Solve Problem (7) with SGM (x 0 , D, t, K) Require: Problem parameters x 0 , D, t, total number of iterations K.1: Set η = D/(C √ K), where C = max{C f , C g }. 2: for k = 0, • • • , K -1 do 3: Obtain a subgradient s ∈ ∂ x ψ(t, x) by Proposition 5.1. 4: Update x k+1 = Π Z (x k -ηs). 5: end for 6: return x(t) = 1 K K-1 k=0x k as the approximate solution and ψ * (t) = max{f (x (t) )-t, g(x (t) )} as the approximate value.* = -R √ q 1.3. It is a 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 [19] . r q,C,R (•) is Lipschitz in B(0, R), while the zero-chain presented in Nesterov [19] is Lipschitz in B(x * , R), where x * is the minimizer of the zero-chain.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 in 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 a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
preliminaries: 
 For anyx ∈ R n , let x [j] represent the j-th coordinate of x for j = 1, • • • , n. We use supp(x) := {j ∈ [d] : x [j] ̸ = 0} to denote the support of x. The Euclidean ball centered at x with radius R is denoted as B(x, R) ≜ {y | ∥y -x∥ 2 ≤ R}. For any closed convex set C ⊆ R n , the Euclidean projection of x onto C is denoted by Π C (x) ≜ arg min y∈C ∥y -x∥ 2 . We say a function h is C-Lipschitz in domain Z if ∥h(x) -h(y)∥ 2 ≤ C∥x -y∥ 2 for all x, y ∈ 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 (1) . We assume that 1. Functions f and g : R n → R are convex and continuous.The feasible set Z is convex and compact with radius D = sup x,y∈Z ∥x -y∥ 2 .The compactness assumption ensures that the subprocesses adopted in our method have a unified upper complexity bound (see Section 5.3). We note that other works involving bisection procedures, such as Wang et al. [27] , may also need to address this issue to derive an explicit dependence on the distance term (although they did not state it formally in their paper). For unconstrained problems, if we know that the initial distance ∥x * -x 0 ∥ 2 is upper bounded by R, we can simply take Z = B(x 0 , R).We use Assumption 3.1 throughout this paper, but distinguish the following two different settings. Assumption 3.2. Consider Problem (1) . We assume that f and g are L f -smooth and L g -smooth respectively. We call such problems (L f , L g )-smooth problems. Assumption 3.3. Consider Problem (1) . We assume that f and g are C f -Lipschitz and C g -Lipschitz in Z respectively. We call such problems (C f , C g )-Lipschitz problems.To study the complexity of solving Problem (1), we make the following assumption on the algorithms. Assumption 3.4 (zero-respecting algorithm class). An iterative method A can access the objective functions f and g only through a first-order black-box oracle, which takes a test point x as the input and returns ∂f (x), ∂g(x), where ∂f (x), ∂g(x) are arbitrary subgradients of the objective functions at x. A generates a sequence of test pointsEQUATIONThis assumption generalizes the standard definition of zero-respecting algorithm for singlelevel minimization problems [7, 19] . Many existing methods that incorporate a gradient step in the update for Problem (1) clearly fall within this class of algorithms, including those proposed by [10, 17, 18, [22] [23] [24] , since the gradient step ensures that x k ∈ x 0 + Span{∂f (x 0 ), ∂g(x 0 ), . . . , ∂f (x k-1 ), ∂g(x k-1 )}. In the appendix, we show that the proposed algorithm in this paper and the conditional gradient type methods [5, 12] also satisfy the condition (6) when the domain is a Euclidean ball centered at x 0 (see Proposition C.1 and Remark C.1).The following concept of first-order zero-chain, introduced by Nesterov [19, Section 2.1.2], plays an essential role in proving lower bounds for zero-respecting algorithms. In 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) : R q → R a first-order zero-chain if for any sequence {x k } k≥0 satisfyingsupp(x t+1 ) ⊆ 0≤s≤t supp (∇h(x s )) , k ≥ 1; x 0 = 0, it holds that x k,[j] = 0, k + 1 ≤ j ≤ q.Definition 3.1 defines differentiable zero-chain functions. We can similarly define non-differentiable zero-chain, by requiring supp(x t+1 ) to be in 0≤s≤t supp (∂h(x s )), where ∂h(x) is a (possibly adversarial) subgradient of h at x.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Justification: We state all the assumptions we need in Section 3. We provide all proofs in the appendix.Answer: [Yes] Justification: We present all experiment details in Section 6 and Appendix E. We also include the codes to reproduce our results in the supplementary materials. Guidelines: Justification: This paper focuses on optimization theory, which has no direct societal impacts. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
finding absolute optimal solutions is hard: 
 Faced with Problem (1), a natural initial response is to seek an approximate solution x such that f (x) is as close to f * as possible, under the premise that g(x) is close to g * . Such a goal is captured by the concept of (ϵ f , ϵ g )-absolute optimal solutions as defined in (2) . However, it turns out that finding a (ϵ f , ϵ g )-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 x 0 , there exists a (1, 1)-smooth instance of Problem (1) such that the optimal solution x * satisfies ∥x 0 -x * ∥ 2 ≤ 1 and |f (x 0 ) -f * | ≥ 1 48 . For the iterates {x k } T k=0 generated by A, the following holds:f (x k ) = f (x 0 ), ∀1 ≤ k ≤ T. Theorem 4.2.For any first-order algorithm A satisfying Assumption 3.4 that runs for T iterations and any initial point x 0 , there exists a (1, 1)-Lipschitz instance of Problem (1) and some adversarial subgradients {∂f (x k ), ∂g(x k )} T -1 k=0 such that the optimal solution x * satisfies ∥x 0 -x * ∥ 2 ≤ 1 and |f (x 0 ) -f * | ≥ 1 4 . For the iterates {x k } T k=0 generated by A, the following holdsf (x k ) = f (x 0 ), ∀1 ≤ k ≤ T.The proofs of Theorem 4.1 and Theorem 4.2 rely on the concept of worst-case convex zero-chain (Proposition A.1 and A.2). We show that for any first-order zero-respecting algorithm that runs for T iterations, there exists a "hard instance" such that f (x t ) remains unchanged from the initial value f (x 0 ) throughout the entire process. The complete proof is 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 min x∈R n ,y∈R m f (x, y) subject to y ∈ arg min z∈R m g(x, z), there exists a "hard instance" in which any zero-respecting algorithm always yields x k = x 0 for all 1 ≤ k ≤ T . Although our construction has a very similar high-level idea to [9] , the f and g we construct are different from the functions in [9] since our desired conclusion is different. Remark 4.1. Some previous works [6, 12, 23] provide guarantees for finding (ϵ f , ϵ g )-absolute optimal solutions. However, these works assume an additional Hölderian error bound condition [20] 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.5 Near-optimal methods for weak optimal solutions Due to the intractability of obtaining (ϵ f , ϵ g )-absolute optimal solutions of Problem (1), most existing works focus on developing first-order methods to find (ϵ f , ϵ g )-weak optimal solutions as defined in (3) . In this section, we 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. 
lower complexity bounds: 
 We first establish the lower complexity bounds for finding a (ϵ f , ϵ g )-weak optimal solution of (L f , L g )-smooth problems and (C f , C g )-Lipschitz problems. The results follow directly from existing lower bounds for single-level optimization problems, as simple bilevel optimization is a more general framework. Although the proof is straightforward, we present the results because establishing a precise lower bound is essential for demonstrating that an algorithm is truly near-optimal. Theorem 5.1. Given L f , L g , D > 0. For any first-order algorithm A satisfying Assumption 3.4 and any initial point x 0 , there exists a (L f , L g )-smooth instance of Problem (1) on the domain Z = B(x 0 , D) such that the optimal solution x * is contained in Z and A needs at leastΩ max L f ϵ f , Lg ϵgD iterations to find a (ϵ f , ϵ g )-weak optimal solution. Theorem 5.2. Given C f , C g , D > 0. For any first-order algorithm A satisfying Assumption 3.4 and any initial point x 0 , there exists a (C f , C g )-Lipschitz instance of Problem (1) on the domain Z = B(x 0 , D) such that the optimal solution x * is contained in Z and A needs at leastΩ max C 2 f ϵ 2 f , C 2 g ϵ 2 gD 2 iterations to find a (ϵ f , ϵ g )-weak optimal solution.We now present a unified framework applicable to both smooth and Lipschitz problems. The proposed algorithms nearly match the lower complexity bounds in both settings.We apply two steps of reformulation. First, we relax Problem (1) to Problem (4), where the constraint x ∈ X * g is replaced by a relaxed functional constraint g(x) ≜ g(x) -ĝ * ≤ 0. Denoting f * as the optimal value of Problem (4), the following lemma holds: Lemma 5.1. If g * ≤ ĝ * ≤ g * + ϵg 2 and x is a (ϵ f , ϵ g /2)-weak optimal solution to Problem (4), i.e. f (x) ≤ f * + ϵ f , g(x) ≤ ϵ g /2, then x is a (ϵ f , ϵ g )-weak optimal solution to Problem (1) .Therefore, it suffices to pursue an approximate solution of Problem (4). Second, Problem (4) is further reduced to the problem of finding the smallest root of the following auxiliary function:EQUATION)Algorithm 1 Functionally Constrained Bilevel Optimizer (FC-BiO) Require: Problem parameters x 0 , D, desired accuracy ϵ, total number of iterations T , initial bounds ℓ, u, and a subroutine for Problem (7) M.1: Set N = log 2 u-ℓ ϵ/2 , K = T /N . Set x = x 0 . 2: for k = 0, • • • , N -1 do 3: Set t = ℓ+u 2 . 4:Solve with the subroutine (x (t) , ψ * (t)) = M(x, D, t, K).Set x = x(t)6: if ψ * (t) > ϵ 2 then 7:Set ℓ = t. Set u = t.10:end if 11: end for 12: return x = x(u) as the approximate solution.Such reformulation is introduced in Nesterov [19, Section 2.3] with the following characterization. Lemma 5.2 (Nesterov [19, Lemma 2.3.4] ). Let f * be the optimal value of Problem (4), and let ψ * (t) be the auxiliary function as defined in (7) . The following holds:1. ψ * (t) is continuous, decreasing, and Lipschitz with constant 1.To proceed with the bisection process, we need to invoke a subroutine M to approximate the function value of ψ * (t) = min x∈Z ψ(t, x) in each outer iteration, where ψ(t, x) = max{f (x) -t, g(x)}. This reduces to a discrete minimax optimization problem (Problem ( 7)) for a given t. Below we demonstrate the subroutines to solve this problem in Lipschitz and smooth settings.Lipschitz setting When f and g are convex and C f and C g -Lipschitz respectively, it holds that ψ(t, x) is also convex and Lipschitz with constant max{C f , C g }. In this case, setting M to be the Subgradient Method (SGM) [4, Section 3.1] applied on ψ(t, •) (Algorithm 2) directly achieves the optimal convergence rate. To implement the SGM method, the subgradient of ψ(t, x) needs to be computed as given in the following proposition: Proposition 5.1 (Nesterov [19, Lemma 3.1.13] ). Consider ψ(t, x) = max{f (x) -t, g(x)} where f and g are convex functions. For given t. We have We refer to Algorithm 1 with SGM subroutine (Algorithm 2) as FC-BiO Lip . Combining with Lemma 5.3, we obtain the following total iteration complexity of FC-BiO Lip : Theorem 5.3 (Lipschitz setting). Suppose Assumption 3.1 and 3.3 hold and∂ x ψ(t, x) =    ∂f (x), f (x) -t > g(x); ∂g(x), f (x) -t < g(x); Conv {∂f (x), ∂g(x)} , f (x) -t = g(x).ϵ f = ϵ g = ϵ. When T ≥ log 2 u -ℓ ϵ/2 4 max{C 2 f , C 2 g } ϵ 2 D 2 ,the approximate solution x produced by FC-BiO Lip is a (ϵ, ϵ)-weak optimal solution to Problem (1) .The optimal first-order method for optimizing smooth objective functions is the celebrated Accelerated Gradient Method (AGM) [19, Section 2.2] proposed by Nesterov. In contrast to the Lipschitz setting, AGM cannot be applied to ψ(t, x) = max{f (x) -t, g(x)} directly when f and g are convex and smooth, as the smoothness condition no longer holds for ψ(t, •). However, Nesterov [19, Section 2.3] showed that by simply replacing the gradient step in standard AGM with the following gradient mapping (Nesterov [19, Definition 2.3.2])EQUATIONAlgorithm 3 Solve Problem (7) with Generalized AGM (x 0 , D, t, K) [19, Algorithm 2.3.12] Require: Problem parameters x 0 , D, t, total number of iterations K.1: Set y 0 = x 0 , α 0 = 1 2 . 2: for k = 0, • • • K -1 do 3:Compute x k+1 as the solution to (9) by Proposition 5.2.Compute α k+1 from the equation α 2 k+1 = (1 -α k+1 )α 2 k .Setβ k = α k (1-α k ) α 2k +α k+1 , y k+1 = x k+1 + β k (x k+1 -x k ). 6: end for 7: return x(t) = x K as the approximate solution and ψ * (t) = max{f (x K ) -t, g(x K )} as the approximate value.the optimal rate of O( L/ϵ) can be achieved for Problem (7) . Here {x k }, {y k } are the test point sequences and L = max{L f , L g }. Solving x k+1 for general discrete minimax problems (where the maximum is taken over potentially more than two objective functions, as studied in Nesterov [19, Section 2.2]), reduces to a quadratic programming (QP) problem and may not be efficiently solvable. However, we demonstrate that in our problem setup, x k+1 can be expressed in the form of a projection onto the feasible set Z, or onto the intersection of Z and a hyperplane.Proposition 5.2. Define the descent step candidatesEQUATIONwhere H ⊂ R n is a hyperplane defined byH = {x | f (y k ) -g(y k ) + ⟨∇f (y k ) -∇g(y k ), x -y k ⟩ -t = 0}.Then the solution to ( 9) is x k+1 = arg min {xi|i∈{1,2,3}} ψ(t, x i ; y k ).We present the generalized AGM subroutine (Algorithm 3) and its convergence rate below. We refer to Algorithm 1 with generalized AGM subroutine (Algorithm 3) as FC-BiO sm , whose total iteration complexity is given by the following theorem: Theorem 5.4 (Smooth setting). Suppose Assumption 3.1 and 3.2 hold andϵ f = ϵ g = ϵ. When T ≥ log 2 u -ℓ ϵ/2 12 max{L f , L g } ϵ D,the approximate solution x produced by FC-BiO sm is a (ϵ, ϵ)-weak optimal solution to Problem (1).For more general cases when the desired accuracy for the upper-level and lower-level problems is different (i.e. ϵ f ̸ = ϵ g ), we can simply scale the objective functions before applying FC-BiO Lip or FC-BiO sm , resulting in the following guarantee:Corollary 5.1. Suppose Assumption 3.1 holds. By scaling g• = ϵ f ϵg g and applying FC-BiO Lip or FC-BiO sm on functions f and g• , a (ϵ f , ϵ g )-weak optimal solution to Problem (1) is obtained within the complexity of Õ maxC 2 f ϵ 2 f , C 2 g ϵ 2 g D 2 under Assumption 3.3 and Õ max L f ϵ f , Lg ϵg D under Assumption 3.2.Our proposed algorithms are near-optimal in both Lipschitz and smooth settings as the convergence results in Corollary 5.1 match the lower bounds established in Theorem 5.1 and Theorem 5.2. 6 Numerical experimentsjf (x k ) ! f $ j FC-BiO sm FC-BiO Lip AGM-BiO PB-APG Bi-SG a-IRG CG-BiO Bisec-BiOf (x k ) FC-BiO sm FC-BiO Lip AGM-BiO PB-APG Bi-SG a-IRG CG-BiOIn this section, we evaluate our proposed methods on two different bilevel problems with smooth objectives. We compare the performance of FC-BiO sm with existing methods, including a-IRG [13] , Bi-SG [18] , CG-BiO [12] , AGM-BiO [6] , PB-APG [10] , and Bisec-BiO [27] . The following problems are also Lipschitz on a compact set Z, so we implement FC-BiO Lip as well. The initialization time of FC-BiO sm , FC-BiO Lip , 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 [12] , which is available online1 . 
minimum norm solution: 
 As in [27] , we consider the following simple bilevel problem:EQUATIONWe set the feasible set Z = B(0, 2). We use the Wikipedia Math Essential dataset [21] , which contains 1068 instances with 730 attributes. We uniformly sample 400 instances and denote the feature matrix and outcome vector by A and b respectively. We choose the same random initial point x 0 for all methods. We set ϵ f = ϵ g = 10 -6 . For this problem, we can explicitly solve x * and f * to measure the convergence. Figure 1 shows the superior performance of our method compared to existing methods in both upper-level and lower-level. The only exception is Bisec-BiO [27] , 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 |f (x) -f * | > ϵ f , indeed a (ϵ f , ϵ g )-weak optimal solution is solved by FC-BiO sm . See more experiment details in Appendix E.1.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 using the "rcv1.binary" dataset from "LIBSVM" [8, 15] , which contains 20, 242 instances with 47, 236 features. We uniformly sample m = 5000 instances as the training dataset (A tr , b tr ), and m instances as the validation dataset (A val , b val ). We consider the bilevel problem with:EQUATIONWe set the feasible set Z = B(0, 300). We set the initial point x 0 = 0 for all methods. We set ϵ f = ϵ g = 10 -3 . Since projecting to the sublevel set of f (x) is not practical, Bisec-BiO [27] 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 we only plot function value f (x k ) and g(x k ), instead of suboptimality. As shown in Figure 2 , our method converges faster than other algorithms in both upper-level and lower-level. More details are provided in Appendix E.2. 
conclusion and future work: 
 This paper provides a comprehensive study of convex simple bilevel problems. We show that find a (ϵ f , ϵ g )-absolute 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 framework FC-BiO for finding a (ϵ f , ϵ g )-weak optimal solution. Our proposed methods achieve the near-optmal rates ofÕ max{1/ϵ 2 f , 1/ϵ 2 g } and Õ max{1/ √ ϵ f , 1/ √ ϵ g } forLipschitz and smooth problems respectively.We discuss some limitations unaddressed in this work. First, our method introduces an 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.A Proofs for Section 4A.1 Constructions of first-order zero-chainsWe first give the constructions of the zero-chains that are used in our negative results. These zerochains are the worst-case functions that Nesterov [19] used to prove the lower complexity bounds for first-order methods in single-level optimization. Proposition A.1 (Paraphrased from Section 2.1.2 Nesterov [19] ). Consider the family of functions h q,L,R (x) : R q → R:EQUATIONThe following properties hold for any h q,L,R (x) with q ∈ N + and L, R > 0:1. It is a convex and L-smooth function.2. It has the following unique minimizer:x * [j] = R 1 -j q+1 with norm ∥x * ∥ 2 ≤ R √ q.3. It is a differentiable first-order zero-chain as defined in Definition 3.1. Remark A.1. In Section 2.1.2 of Nesterov [19] , it is shown that h q,L,1 is a convex and L-smooth zero-chain. Here we define h q,L,R (x) := R 2 h q,L,1 ( x R ). Then ∇ 2 h q,L,R (x) = ∇ 2 h q,L,1 ( x R ), and h q,L,R (x) is also a convex and L-smooth zero-chain. Similarly, in Proposition A.2, we define r q,C,R (x) := Rr q,C,1 ( x R ). Nesterov [19] showed r q,C,1 is a C-Lipschitz zero-chain, which implies that r q,C,R is also a C-Lipschitz zero-chain, since ∇r q,C,R (x) = ∇r q,C,R ( x R ). Proposition A.2 (Paraphrased from Section 3.2.1 Nesterov [19] ). Consider the family of functions r q,L,R (x) : R q → R:EQUATION)The following properties hold for any r q,L,R (x) with q ∈ N + and C, R > 0:1. It is a convex function and is C-Lipschitz in the Euclidean ball B(0, R). 
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, or 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 no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.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 package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: Proof of Theorem 4.1. Consider any first-order algorithm A satisfying Assumption 3.4 that runs for T iterations. Without loss of generality, we assume the initial point of A is x 0 = 0. Otherwise, we can translate the following construction to f (x -x 0 ), g(x -x 0 ). Let q = 2T andf (x) = 1 2 q j=T +1 x 2 [j] , g(x) = h q,1,1/ √ q (x),where h q,1,1/ √ q (•) follows Proposition A.1. It is clear from the construction that both f (•), g(•) are convex and 1-smooth. Furthermore, the optimal solution to Problem (1) defined by such f, g is the unique minimizer of g(x), given by x *[j] = 1 √ q (1 -j q+1 ). We prove by induction on k that the test points {x k } T k=0 generated byA satisfies x k,[j] = 0 for 0 ≤ k ≤ T , T + 1 ≤ j ≤ 2T : Suppose for some k ≤ T , x i,[j] = 0 holds for 0 ≤ i ≤ k -1, T + 1 ≤ j ≤ 2T , we have ∇f (x i ) = 0, 0 ≤ i ≤ k -1.The zero-respecting assumption of A (Assumption 3.4) leads tox k ∈ 0≤i≤k-1 supp(∇f (x i )) ∪ supp(∇g(x i )) = 0≤i≤k-1 supp(∇g(x i )).Since g(x) is a first-order zero-chain, we conclude thatx k,[j] = 0, k + 1 ≤ j ≤ 2T.Consequently, f (x k ) remains zero for all 0 ≤ k ≤ K. However,f * = 1 2 2T j=T +1x * 2[j] = 1 4T 2T j=T +1 1 - j 2T + 1 2 = 1 24 • T + 1 2T + 1 ≥ 1 48 . Thus |f (x k ) -f * | ≥ 1 48 , 1 ≤ k ≤ T.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 A is x 0 = 0. Let q = 2T andf (x) = 1 2 2T j=T +1 x 2 [j] , g(x) = r 2T,1,1 (x),where r 2T,1,1 (•) follows the construction in Proposition A.2. Both g(•) and f (•) are convex and 1-Lipschitz in B(0, 1), and the unique minimizer x * = -1 √ q 1 of g is the optimal solution to Problem (1) defined by such f and g, with norm ∥x * ∥ 2 = 1. Similar to the proof of Theorem 4.1, we prove by induction on k that there exist some adversarial subgradients {∂g(x 0 ),• • • , ∂g(x k-1 )} such that the test points {x k } T k=0 generated by A satisfies x k,[j] = 0 for 0 ≤ k ≤ T, T + 1 ≤ j ≤ 2T : Suppose for some k ≤ T , x i,[j] = 0 holds for 0 ≤ i ≤ k -1, T + 1 ≤ j ≤ 2T , we have ∇f (x i ) = 0, 0 ≤ i ≤ k -1.The zero-respecting assumption of A (Assumption 3.4) leads tox k ∈ 0≤i≤k-1 supp(∇f (x i )) ∪ supp(∂g(x i )) = 0≤i≤k-1 supp(∂g(x i )),where {∂g(x 0 ), • • • , ∂g(x k-1 )} are the subgradients returned by a black-box first-order oracle. Since g(x) is a first-order zero-chain, we conclude that there exists some adversarial subgradients {∂g(x 0 ),• • • , ∂g(x k-1 )} such that x k,[j] = 0, k + 1 ≤ j ≤ 2T. Consequently, f (x k ) remains zero for all 0 ≤ k ≤ K. However, f * = f (x * ) = 1 4 . Thus |f (x k ) -f * | ≥ 1 4 , 1 ≤ k ≤ T.To apply the two-step reformulation, we need to solve an approximate value of the lower-level problem ĝ * such that g * ≤ ĝ * ≤ g * + ϵ 2 . Furthermore, to conduct the bisection method of FC-BiO, it is necessary to first determine an initial interval [ℓ, u] that contains the minimal root of ψ * (t), which is exactly f * (Lemma 5.2). The following procedure is inspired by Wang et al. [27] : 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) [19, Section 2.2] for smooth functions -to the lower-level objective g to obtain an approximate minimum point xg ∈ R n such that g * ≤ g(x g ) ≤ g * + ϵ2 . We set ĝ * = g(x g ) and define the relaxed constraint function g(x) as in (4) . We set u = f (x g ), thenψ * (u) ≤ ψ(u, xg ) = max{f (x g ) -u, g(x g )} = 0.Thus u is indeed an upper-bound of the minimal root of ψ * (•) given that ψ * (•) is decreasing.To derive a lower bound of the minimal root f * , we can also apply the optimal single-level minimization methods to the upper-level objective f to find an approximate global minimum pointxf ∈ R n such that p * ≤ p * ≜ f (x f ) ≤ p * + ϵ 2, where p * is the minimum value of f over the whole space R n (i.e., p * ≜ min x∈R n f (x)). Then ℓ = p * -ϵ 2 is a valid lower bound of f * sinceℓ = p * - ϵ 2 ≤ p * ≤ f * .Nevertheless, any lower bound for f * is acceptable, such as 0 when the upper-level objective f is non-negative.The complexity of applying the optimal single-level minimization methods to f and g separately is O C 2 f ϵ 2 D 2 + C 2For the initial point of the subroutine M (SGM in FC-BiO Lip or generalized AGM in FC-BiO Sm ), we exploit the warm-start strategy, which uses the last point in the previous round (denoted by x in Algorithm 1) as the initial point of the current round. Intuitively, the subproblem (i.e. minimizing max{f (x) -t, g(x)}) does not change significantly in each round since the parameter t does not change too much as ℓ and u 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 B(x 0 , D) does not change the complexity upper bound. Such a strategy is widely used in two-level optimization methods [2, 9, 16] .Similarly, we can use the approximate minimum point xg of g (as described in Appendix B.1) instead of x 0 as the initial point of the first round of the subroutine. ). Given L > 0, D > 0. For any first-order algorithm A satisfying Assumption 3.4 and any initial point x 0 , there exists a convex and L-smooth function f such that the minimizer x * satisfies ∥x * -x 0 ∥ 2 ≤ D andf (x T ) -f (x * ) ≥ 3LD 2 32(T + 1) 2 , Lemma C.2 (Nesterov [19, Theorem 3.2.1]). Given C > 0, D > 0.For any first-order algorithm A satisfying Assumption 3.4 and any initial point x 0 , there exists a convex function f that is C-Lipschitz in B(x 0 , D), such that the minimizer x * satisfies ∥x * -x 0 ∥ 2 ≤ D andf (x T ) -f (x * ) ≥ CD 2(1 + √ T ) ,The "hard functions" f (•) in the previous lemmas are exactly the zero-chain h 2T +1,L,D (•) and r T,C,D (•) as constructed in Proposition A.1 and Proposition A.2, respectively.Proof of Theorem 5.1. Consider any first-order algorithm A satisfying Assumption 3.4 that runs for T iterations. Without loss of generality, we assume the initial point of A is x 0 = 0. Otherwise, we can translate the following construction to f (x -x 0 ), g(x -x 0 ).If L f ϵ f ≥ Lg ϵg, we set the upper-level and lower-level objective f, g : R 2T +1 → R be:f (x) = h 2T +1,L f ,D (x), g(x) = 0,where h 2T +1,L f ,D (•) is defined in Proposition A.1. Then the zero-respecting assumption on A implies that for any k ≥ 1, we have supp(x k+1 ) ⊆ 0≤s≤k-1 supp (∇f (x s )) . From Lemma C.1, it holds thatϵ f = f (x T ) -f * ≥ 3L f D 2 32(T + 1) 2 ,which implies that any zero-respecting first-order method needs at leastT = Ω L f ϵ f D = Ω max L f ϵ f , L g ϵ g Diterations to solve a (ϵ f , ϵ g )-weak optimal solution.IfL f ϵ f ≤ Lg ϵg, we set the upper-level and lower-level objective f, g : R 2T +1 → R be:f (x) = 0, g(x) = h 2T +1,Lg,D (x).By similar arguments, any zero-respecting first-order method needs at leastT = Ω L g ϵ g D = Ω max L f ϵ f , L g ϵ g Diterations to solve a (ϵ f , ϵ g )-weak optimal solution.Proof of Theorem 5.2. Consider any first-order algorithm A satisfying Assumption 3.4 that runs for T iterations. Without loss of generality, we assume the initial point of A is x 0 = 0. Otherwise, we can translate the following construction to f (x -x 0 ), g(x -x 0 ).If C f ϵ f ≥ Cg ϵg, we set the upper-level and lower-level objective f, g : R T → R be:f (x) = r T,C f ,D (x), g(x) = 0, where r T,C f ,D (•) is defined in Proposition A.2.Then the zero-respecting assumption on A implies that for any k ≥ 1, we have supp(x k ) ⊆ 0≤s≤k-1 supp (∂f (x s )). From Lemma C.2, it holds thatϵ f = f (x T ) -f * ≥ C f D 2(1 + √ T ) ,which implies that any zero-respecting first-order method needs at leastT = Ω C 2 f ϵ 2 f D 2 = Ω max C 2 f ϵ 2 f , C 2 g ϵ 2 g D 2iterations to solve a (ϵ f , ϵ g )-weak optimal solution.IfC f ϵ f ≤ Cg ϵg, we set the upper-level and lower-level objective f, g : R T → R be:f (x) = 0, g(x) = r T,Cg,D (x).By similar arguments, any zero-respecting first-order method needs at leastT = Ω C 2 g ϵ 2 g D 2 = Ω max C 2 f ϵ 2 f , C 2 g ϵ 2 g D 2iterations to solve a (ϵ f , ϵ g )-weak optimal solution.C.2 Proofs in Section 5.2 and 5.3Proof of Lemma 5.1. Any feasible solution to Problem ( 1) is also a feasible solution to Problem (4), thus f * ≤ f * . For any x that satisfiesf (x) ≤ f * + ϵ f , g(x) ≤ ϵ g 2 ,we havef (x) ≤ f * + ϵ f ≤ f * + ϵ f , g(x) = g(x) + ĝ * ≤ ϵ g 2 + g * + ϵ g 2 = g * + ϵ g .Thus x is indeed a (ϵ f , ϵ g )-weak optimal solution to Problem (1).Proof of Lemma 5.3. We first show that ℓ is always a lower bound of f * . The initial lower bound satisfies ℓ ≤ f * . Furthermore, if (8) holds during the bisection process, we always have that ψ * (ℓ) ≥ ψ * (ℓ) -ϵ 2 > 0. Given that ψ * (•) is decreasing, and considering that f * is the minimal root of ψ * (Lemma 5.2), it follows that ℓ < f * .As for the upper bound u, the initial upper bound satisfiesψ * (u) = ψ(u, xg ) = max{f (x g ) -u, g(x g )} = max{0, 0} ≤ ϵ 2 .And during the bisection process, we also have that ψ * (u) = max{f (x (u) ) -u, g(x (u) )} ≤ ϵ 2 .After N = log 2 u-ℓ ϵ/2 bisection iterations, it holds thatu -ℓ ≤ ϵ 2 .Consider the output of Algorithm 1 x = x(u) . Combining previous inequalities, we havef (x) ≤ u + ϵ 2 ≤ ℓ + ϵ ≤ f * + ϵ, g(x) ≤ ϵ 2 .Some of the lemmas in this section are adapted from existing results [4, 19] , but not exactly the same. We also provide a proof for these lemmas (Lemma 5.2, 5.4, 5.5).Proof for Lemma 5.2. It's clear the ψ * (t) is continuous and decreasing. For any t ∈ R and ∆ > 0, we haveψ * (t + ∆) = min x∈Z {max{f (x) -t, g(x) + ∆}} -∆ ≥ min x∈Z {max{f (x) -t, g(x)}} -∆ = ψ * (t) -∆. Thus ψ * (t) is 1-Lipschitz.Let x * be the optimal solution to Problem (4), then f * = f (x * ). For any t ≥ f * , it holds thatψ * (t) ≤ ψ * ( f * ) ≤ ψ( f * , x * ) = max{f (x * ) -f * , g(x * )} ≤ 0.Suppose that t < f * and ψ * (t) ≤ 0, then there exists a x ∈ Z such that g(x) ≤ 0, f (x) -t ≤ 0. Then x is a feasible solution to Problem (4), with f (x) ≤ t < f * , contradiction to the fact that f * is the optimal value to Problem (4). Thus for any t < f * , it holds that ψ * (t) > 0.Thus f * is the smallest root of ψ * (t).Proof for Lemma 5.4. Theorem 3.2 in Bubeck et al. [4] states that applying subgradient method to any C-Lipschitz convex function h on a compact set Q with diameter D givesh 1 K K-1 i=0 x i -h * ≤ DC √ K .Hereh(x) = ψ(t, x) = max(f (x) -t, g(x)), C = max(C f , C g ). Then when K ≥ 4D 2 C 2 ϵ 2 , it holds that ψ * (t) = ψ t, 1 K K-1 i=0 x i ≤ ψ * (t) + ϵ 2 .Proof for Lemma 5.5. Theorem 2.3.5 in Nesterov [19] originally states that applying genearlizedgradient method to any µ-strongly convex and L-smooth convex function h givesh(x K ) -h * ≤ 4L (γ 0 -µ)(K + 1) 2 (f (x 0 ) -f * + γ 0 2 ∥x 0 -x * ∥ 2 2 ),where γ 0 = α0(α0L-µ). Here h(x) = ψ(t, x) = max(f (x) -t, g(x)), L = max(L f , L g ), µ = 0,α 0 = 1 2 , γ 0 = L 2 . Then ψ(t, x K ) -ψ * ≤ 4L 1 2 L(K + 1) 2 L 2 ∥x 0 -x * ∥ 2 2 + L 4 ∥x 0 -x * ∥ 2 2 ≤ 6LD 2 K 2 .Then whenK ≥ 12L ϵ D, it holds that ψ * (t) = ψ(t, x K ) ≤ ψ * (t) + ϵ 2 .To prove Proposition 5.2, we first present a lemma: Lemma C.3. For any strictly convex and continuous functions f , g : R n → R, we define φ : R n → R by φ(x) = max{f (x), g(x)}. Let x * be the unique minimizer of φ(•) on a convex and compact set Z ⊂ R n , i.e. x * = arg min x∈Z φ(x), and let x * f , x * g be the unique minimizer of f (•) and g(•) on Z respectively. Ifx * ̸ = x * f and x * ̸ = x * g , then f (x * ) = g(x * ).Proof. Below, we show that f (x * ) ̸ = g(x * ) leads to contradiction. Without loss of generality, assume f (x * ) > g(x * ). Due to the continuity of f and g, there exists some δ > 0 such that for any 0 < θ < δ,f (x * + θ(x * f -x * )) > g(x * + θ(x * f -x * )).Furthermore, for any θ ∈ (0, 1), we have thatx * + θ(x * f -x * ) ∈ Z and f (x * + θ(x * f -x * )) < θf (x * f ) + (1 -θ)f (x * ) < f (x * ), since f is strictly convex.Then for any θ ∈ (0, min(1, δ)),φ(x * + θ(x * f -x * )) = f (x * + θ(x * f -x * )) < f (x * ) = φ(x * ).That contradicts the fact that x * is the minimizer of φ(•). Thus f (x * ) = g(x * ).The previous lemma demonstrates that the minimizer of max x∈Z {f (x), g(x)} falls into one of three categories: the minimizer of f , the minimizer of g, or the case where the function values of f and g are the same. x 1 , x 2 , x 3 in Proposition 5.2 corresponds to the three cases respectively.Proof for Proposition 5.2. Definef (t, x; y k ) ≜ f (y k ) + ⟨∇f (y k ), x -y k ⟩ + L 2 ∥x -y k ∥ 2 2 -t, ḡ(x; y k ) ≜ g(y k ) + ⟨∇g(y k ), x -y k ⟩ + L 2 ∥x -y k ∥ 2 2 ,which can be written asf (t, x; y k ) = f (y k ) -t - 1 2L ∥∇f (y k )∥ 2 + L 2 x -y k + 1 L ∇f (y k ) 2 , ḡ(x; y k ) = g(y k ) - 1 2L ∥∇g(y k )∥ 2 + L 2 x -y k + 1 L ∇g(y k ) 2 .Thusx 1 = arg min x∈Z x -y k + 1 L ∇f (y k ) = arg min x∈Z f (t, x; y k ), x 2 = arg min x∈Z x -y k + 1 L ∇g(y k ) = arg min x∈Z ḡ(t, x; y k ).Assume the minimizer x k+1 of ψ(t, x; y k ) satisfies x k+1 ̸ = x 1 and x k+1 ̸ = x 2 , then Lemma C.3 implies thatx k+1 ∈{x | f (t, x; y k ) = ḡ(x; y k )} ={x | f (y k ) -g(y k ) + ⟨∇f (y k ) -∇g(y k ), x -y k ⟩ -t = 0} =H.Given that f (t, x; y k ) = ḡ(x; y k ) in the subset Z ∩ H, we havex k+1 = arg min x∈Z∩H ψ(t, x; y k ) = arg min x∈Z∩H f (t, x; y k ) = arg min x∈Z∩H x -y k + 1 L ∇f (y k ) = x 3 .Thus we conclude that x k+1 can only be one of x 1 , x 2 , x 3 .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.Proof for Corollary 5.1. A (ϵ f , ϵ g )-weak optimal solution to Problem ( 4) is equivalent to a (ϵ f , ϵ f )weak optimal solution toEQUATIONWhen f and g are C f , C g -Lipschitz respectively, g• isϵ f ϵg C g -Lipschitz.According to Theorem 5.3, FC-BiO Lip finds a (ϵ f , ϵ f )-weak optimal solution of Problem (15) inT = Õ    max{C 2 f , ϵ 2 f ϵ 2 g C 2 g } ϵ 2 f D 2    = Õ max C 2 f ϵ 2 f , C 2 g ϵ 2 g D 2iterations. Similarly, when f and g are L f , L g -smooth respectively, g• isϵ f ϵg L g -smooth.According to Theorem 5.3, FC-BiO sm finds a (ϵ f , ϵ f )-weak optimal solution of Problem (15) inT = Õ   max{L f , ϵ f ϵg L g } ϵ f D   = Õ max L f ϵ f , L g ϵ g D iterations.Finally, we prove the claim at the end of Section 5 that our proposed algorithms are zero-respecting algorithms.Proposition C.1. Both FC-BiO Lip and FC-BiO sm on the domain B(x 0 , D) satisfy Assumption 3.4.Proof. Without loss of generality, we assume x 0 = 0. 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 s ∈ ∂ x ψ(t, x) lies in Span{∂f (x), ∂g(x)} according to Proposition 5.1. And the projection onto B(0, D) does not disrupt the zero-respecting property. Thus, Algorithm 2 satisfies Assumption 3.4.For Algorithm 3, we only need to prove that the gradient mapping x k+1 satisfiesx k+1 ∈ Span{∇f (x 0 ), ∇g(x 0 ), • • • , ∇f (x k ), ∇g(x k )}.We denote S k = Span{∇f (x 0 ), ∇g(x 0 ), • • • , ∇f (x k ), ∇g(x k )}. According to Proposition 5.2, it suffices to prove that the three descent step candidates x 1 , x 2 and x 3 are in S k . It is clear thaty k - 1 L ∇f (y k ), y k - 1 L ∇g(y k ) ∈ S k .Then after projection onto B(0, D), x 1 , x 2 are still in S k .The case for x 3 is slightly more complicated. Letz = y k -1 L ∇f (y k ), w = ∇f (y k ) -∇g(y k ), and b = f (y k ) -g(y k ) -⟨w, y k ⟩ -t. Then H = {x | w T x + b = 0}.The point x 3 is the solution to the following convex optimization problem:min x∈R n ∥x -z∥ 2 s.t. ∥x∥ 2 ≤ D 2 w T x + b = 0.The Lagrangian for this problem is:L(x, λ, µ) = ∥x -z∥ 2 + λ(∥x∥ 2 -D 2 ) + µ(w ⊤ x -b)where λ ≥ 0 and µ are dual variables. The KKT conditions give:∇ x L(x, λ, µ)| x=x3 = 2(x 3 -z) + 2λx 3 + µw = 0.Thusx 3 = 2z -µw 2(1 + λ) ,implying that x 3 is the linear combination of z and w. Since z, w ∈ S k , it follows that x 3 ∈ S k .Remark C.1. By similar analysis, we can show that the conditional gradient type methods for simple bilevel problems [5, 12] on domain B(x 0 , D) also fall into the zero-respecting function class. At each iteration k, their methods relies on the following linear program as an oracle.s k = arg min s∈X k ⟨∇f (x k , s⟩,whereX k = {s ∈ Z : ⟨∇g(x k ), s -x k ⟩ ≤ g(x 0 ) -g(x k )}.According to our proof of Proposition C.1, it suffices to prove that s k is a linear combination of ∇f (x K ) and ∇g(x k ) then the remaining proofs are the same. Similarly, this can be seen by the KKT condition when Z = B(0, D), which is ∇f (x k ) + 2λx + µ∇g(x k ) = 0, where λ ≥ 0 and µ ≥ 0 are dual variables.In Section 4, we showed that, in general, it is intractable for any zero-respecting first-order methods to find an absolute optimal solution of Problem (1). However, it is possible to establish a lower bound for f (x k ) -f * under additional assumptions. Hölderian error bound [20] is a 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, 12, 23] . Prior to our work, the bestknown result is established by Cao et al. [6] , whose method achieves a (ϵ f , ϵ g )-absolute optimal solution for smooth problems inÕ max 1/ϵ 2α-1 2 f , 1/ϵ 2α-1 2αg iterations. Below we will show that our proposed methods also work well with such an additional assumption and achieve superior convergence rates with regard to absolute suboptimality. Assumption D.1. The lower-level objective g satisfies the Hölderian error bound condition for some α ≥ 1 and β > 0, i.e.β α dist(x, X * g ) α ≤ g(x) -g * , ∀x ∈ R n ,where dist(x, X * g ) ≜ inf y∈X * g ∥x -y∥ for arbitrary norm ∥ • ∥. Intuitively, when the lower-level suboptimality g(x) -g * is small, x should be close to X * g if Hölderian error bound condition holds for g. Then we can lower bound f (x) -f * by the convexity of f . Jiang et al. [12] formalizes the idea in the following proposition: f (x) -f * ≥ -M α(g(x) -g * ) β 1 α for any x ∈ R n .This proposition shows that when g(x)-g * ≤ 1 M ϵ f α β α , it holds that f (x)-f * ≥ -ϵ f . Combining with Corollary 5.1, we obtain: Corollary D.1. Suppose Assumption 3.2 or Assumption 3.3 hold and g satisfies Assumption D.1. FC-BiO Lip and FC-BiO sm find a (ϵ f , ϵ g )-absolute optimal solution within the complexity of Õ maxC 2 f ϵ 2 f , C 2 g ϵ 2 g , C 2 g M 2α α 2 β 2 ϵ 2α f D 2 and Õ max L f ϵ f , Lg ϵg , LgM α α βϵ α f D for Lipschitz andsmooth problems, respectively.To our knowledge, this is the first result that establishes a convergence rate concerning absolute suboptimality for Lipschitz problems. In a smooth setting, our result of Õ max 1/ϵα 2 f , 1/ϵ 1 2g is also superior to the convergence rate reported by Cao et al. [6] in both upper-level and lower-level.In this section, we provide more details of numerical experiments in Section 6. All experiments are implemented using MATLAB R2022b on a PC running Windows 11 with a 12th Gen Intel(R) Core(TM) i7-12700H CPU (2.30 GHz) and 16GB RAM.This problem is a (L f , L g )-smooth problem with L f = 1, L g = λ max (A T A).Experiment setting The original Wikipedia Math Essential dataset [21] contains 1068 instances with 730 attributes. Following the setting of Jiang et al. [12] and Cao et al. [6] , 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-parameterized. In this case, the upper-level problem is actually equivalent tomin x∈Z 1 2 ∥x∥ 2 2 s.t. Ax = b.The optimal solution x * for this problem can be explicitly solved via the Lagrange multiplier method:A O I A T x * ν = b 0 ,where ν is the Lagrange multiplier. Then we use f * = 1 2 ∥x * ∥ 2 2 , g * = 0 as the benchmark.Implementation details To be fair, all algorithms start from a random point x 0 of unit length as the initial point. For our Algorithm 1, we take a slightly different implementation, that instead of setting the maximum number of iterations of the inner subroutine to be T ′ = T /N , we preset T ′ = 8000.If current x k already satisfies ψ(t, x k ) ≤ ϵ 2 , then terminate the inner subroutine directly. We adopt the warm-start strategy as described in Appendix B.2. We set L = 0 since f (x) is nonnegative. For FC-BiO Lip , we set η = 3 × 10 -4 . For AGM-BiO, we set γ = 1 as in [6, Theorem 4.1] . For PB-APG, we set γ = 10 5 . For Bi-SG, we set α = 0.75 and c = 1 L f . For a-IRG, we set η 0 = 10 -3 and γ 0 = 10 -3 . For CG-BiO, we set γ k = 0.5/(k + 1). For Bisec-BiO, we set the maximum number of iterations of the internal APG process to be T ′ = 10000. For FC-BiO sm , FC-BiO Lip and Bisec-BiO, solving ĝ * takes 15000 iterations; for CG-BiO, solving ĝ * takes 10000 iterations. The results of such pretreatments are also plotted in Figure 1 .This problem is a (L f , L g )-smooth problem withL f = 1 4m λ max ((A val ) T A val ), L g = 1 4mλ max ((A tr ) T A tr ).Experiment setting In this experiment, a sample of 5000 instances is taken from the "rcv1.binary" dataset [8, 15] as the training set (A tr , b tr ); another 5000 instances is sampled as the validation set (A val , b val ). Each label b tr i (or b val i ) is either +1 or -1.In this experiment, we set the initial point x 0 = 0 for all methods. The implementation of our Algorithm 1 is similar to that in the first experiment. We set the maximum number of iterations of the subroutine to be T ′ = 500 and T ′ = 1000 for FC-BiO sm and FC-BiO Lip respectively. For FC-BiO Lip , we set η = 2. For AGM-BiO, we set γ = 1/( 2LgL f T 2 3 + 2)as in [6, Theorem 4.4] . For PB-APG, we set γ = 10 4 . For Bi-SG, we set α = 0.75 and c = 1 L f . For a-IRG, we set η 0 = 10 3 and γ 0 = 0.1. For CG-BiO, we set γ k = 2 k+2 . For FC-BiO sm , solving ĝ * takes 1000 iterations; for FC-BiO Lip and CG-BiO, solving ĝ * takes 1500 iterations. As in the first experiment, the results of such pretreatments are also plotted in Figure 2 .• 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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.https://github.com/Raymond30/CG-BiO 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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$?
- 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$.
- 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.

Minor comments:
- Typo at line 279: "minimmum" $\to$ "minimum"?
questions: 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: limitations: The paper does discuss its limitation.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. Since this work focuses only on weak optimal solutions, the title *Near-Optimal Methods for Convex Simple Bilevel Problems* seems somewhat boastful.
  
2. There are some minor typos like missing space before "When" in line 238 and 261.
questions: questions: 1. What will happen if one of $f$ and $g$ is Lipschitz continuous and the other one is smooth?
  
2. What it is "," in eq.(5) but ";" in eq.(6)?
  
3. 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?
  
4. How does the author determine the initial interval $[l, u]$, and how does this interval affect the convergence?

I would like to change my grade based on the response from the author.
limitations: limitations: No limitation
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

- 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. 

- It would be better if authors can show the results on meta-learning or some other typical bilevel optimization problems.  

- For Figure 1 and 2, do they take the warm-up time and initialization time into consideration?

[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.
questions: questions: Please refer to the weaknesses.
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: **Writing:**

1- 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).

2- In (5) it feels like a constraint over $x$ is missed in the minimization. Please clarify, thanks!

3- Line 205, the sentence starts with "And", but this sentence is connected to the previous sentence. Please fix!

4- Line 309, "It is open whether ..." sounds a bit informal, please revise, thanks!

5- Statements of Theorems 4.1, 4.2: "there exists an (1,1)..." should be "there exists a (1,1)..." to help readability.


**Technical:**

1- 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.

I'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.

2- 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.

3- 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.
questions: questions: Could you please explain your reasoning and ideas regarding the points raised in the "Weaknesses" section? Thanks!
limitations: limitations: yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 
2. In this paper, the authors only consider the unconstrained case, while many other works about simple bilevel optimization consider the constrained case.
3. 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.
4. 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.
5. The proposed algorithm requires a predetermined $T$, whereas similar studies do not have this requirement.
6. 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].

References:

[1]. Jiulin Wang, Xu Shi, and Rujun Jiang. Near-optimal convex simple bilevel optimization with a bisection method. 

[2]. Yurii Nesterov. Lectures on convex optimization

[3]. Sébastien Bubeck et al. Convex optimization: Algorithms and complexity.
questions: questions: See weaknesses.
limitations: limitations: No negative societal impact.

Comments: title: Response to authors
Could you kindly let us know if your concerns have been addressed?
Could you kindly let us know if your concerns have been addressed?
Could you kindly let us know if your concerns have been addressed?
Could you kindly let us know if your concerns have been addressed?
Could you kindly let us know if your concerns have been addressed?
comment: Dear Reviewer RLu3,

Thank you for your thoughtful feedback and for adjusting the score. We appreciate your additional comments and will clarify the points you mentioned in the revised version.
Dear Reviewer EaJT, 

Thank you for your response. We greatly appreciate the time and effort you put into providing constructive feedback. We think your main concern is still the comparison to [1].

We want to highlight that the sublevel set oracle (i.e. projecting onto the sublevel set of $f(\mathbf x)$: $\text{prox}_{f,c}(\mathbf x)=\arg \min _{f(\mathbf y)\leq c}\Vert\mathbf y-\mathbf x\Vert^2$) used in [1] is a **strong assumption**. For example, when $f(x)$ is the mean square loss or logistic loss as in our Experiment 2, projecting onto the sublevel set cannot be computed efficiently.

In another example, we consider the single-level optimization of $f$ using such an oracle. In this case, one can simply solve this optimization problem using a binary search to identify $f^*$, which only requires $\mathcal{O}(\log(1/\epsilon))$ complexity to achieve $\vert f(x) - f^* \vert \le \epsilon$ (see also Remark 3 in \[1\]), even breaking the standard lower complexity bound $\Omega(1/\sqrt{\epsilon})$.

In contrast, our method only uses the **standard gradient oracle** to achieve the $\tilde {\mathcal{O}}(1/ \sqrt{\epsilon})$ rate. We think this is a significant improvement over \[1\], and we hope that the reviewer can acknowledge our contributions.

\[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.
Thank you for the rebuttal. I still believe the novelty of this paper is not significant. Both this paper and [Wang et al. (2024)] use an oracle of solving single-level problems and apply a bisection approach to tackle an associated 1-D problem. The only distinction is that this paper uses bisection to solve a different 1-D problem. Thus, I will maintain my score.
Thank you for the authors' response and efforts. I'd prefer to maintain my current score. Additionally, it would be great to see a relaxed assumption in place of Assumption 3.1.2.
Thanks for your response. I would like to keep my rating.
Thanks for your responses. Considering your reponses to my comment and the Reviewer RLu3, I think the concerns are addressed. The score was adjusted accordingly.
Dear authors,

Thank you for providing responses to my comments. I have additional comments below:

- I believe that the hardness results in [3] is the closest setting to this paper where they show that under zero-chain assumption, the solution stays at 0 at any iteration.
- Line 149-154 in the paper confused me at the beginnning mainly from the statement "Due to the zero-respecting property, only one component of $x_k$ is activated (i.e. becomes nonzero) per iteration." If this happens, then at a certain iteration large enough, we would be able to arrive at the optimal solution. However, in the proof the authors actually prove that the solution stays at 0 if the initial point is 0. I suggest clarifying this in the paper.

As my concerns have been mostly addressed, I have adjusted the score accordingly.
Dear Reviewer EaJT:

We sincerely appreciate the time and effort you have dedicated to reviewing our manuscript.  As the discussion period draws to a close, we kindly ask if you could let us know whether your concerns have been satisfactorily addressed. If you have any additional questions, we will be more than willing to provide further explanations.

We would highly value any additional feedback you may provide.
Dear Reviewer iPzZ:

We sincerely appreciate the time and effort you have dedicated to reviewing our manuscript.  As the discussion period draws to a close, we kindly ask if you could let us know whether your concerns, particularly regarding Theorem 4.1/4.2, have been satisfactorily addressed. If you have any additional questions, we will be more than willing to provide further explanations.

We would highly value any additional feedback you may provide.
Dear Reviewer KpB7:

We sincerely appreciate the time and effort you have dedicated to reviewing our manuscript.  As the discussion period draws to a close, we kindly ask if you could let us know whether your concerns have been satisfactorily addressed. If you have any additional questions, we will be more than willing to provide further explanations.

We would highly value any additional feedback you may provide.
Dear Reviewer 213i:

We sincerely appreciate the time and effort you have dedicated to reviewing our manuscript.  As the discussion period draws to a close, we kindly ask if you could let us know whether your concerns have been satisfactorily addressed. If you have any additional questions, we will be more than willing to provide further explanations.

We would highly value any additional feedback you may provide.
Dear Reviewer RLu3:

We sincerely appreciate the time and effort you have dedicated to reviewing our manuscript.  As the discussion period draws to a close, we kindly ask if you could let us know whether your concerns, particularly regarding Theorem 4.1/4.2, have been satisfactorily addressed. If you have any additional questions, we will be more than willing to provide further explanations.

We would highly value any additional feedback you may provide.