An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization

Authors: jincheng  cao
ruichen  jiang
erfan yazdandoost hamedani
aryan  mokhtari
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 17:10:02

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

Main paper: 
 introduction: 
 In this paper, we investigate a class of bilevel optimization problems known as simple bilevel optimization, aiming to minimize an upper-level objective function over the solution set of a corresponding lower-level problem. This class has recently gained attention due to its broad applications in continual learning [1] , hyper-parameter optimization [2, 3] , meta-learning [4, 5] , and over-parameterized machine learning [6] [7] [8] . Specifically, we focus on the following bilevel optimization problem:EQUATIONwhere, Z is a convex set, and f, g : R n → R are convex, continuously differentiable functions on an open set containing Z. We assume that the lower-level objective function g is convex but not strongly convex, so the lower-level problem may have multiple optimal solutions. Throughout the paper, we use x * to denote an optimal solution of problem (1) . We define f * ≜ f (x * ) and g * ≜ g(x * ), representing the optimal value of problem (1) and the optimal value of the lower-level 38th Conference on Neural Information Processing Systems (NeurIPS 2024).Table 1 : Non-asymptotic results on simple bilevel optimization. ( 1 ⃝: with a first-order Hölderian error bound assumption on g; r ⃝: with an rth-order (r ≥ 1) Hölderian error bound assumption on g; A ⃝: additional assumption implying that the projection onto the sublevel set of f is easy to compute.)f ) Õ(1/ϵ 2r-1 2r g )objective g, respectively. This class of problems is referred to as the "simple bilevel problem" [9] [10] [11] to distinguish it from more general settings with parameterized lower-level problems.The main challenge in solving problem (1) is that the feasible set, i.e., the optimal solution set of the lower-level problem, lacks a simple characterization and is not explicitly provided. This makes direct application of projection-based or projection-free methods infeasible, as projecting onto or solving a linear minimization problem over such an implicitly defined feasible set is intractable. Instead, our approach constructs an approximation set with specific properties, serving as a surrogate for the true feasible set. In Section 3, we detail how this set is constructed. Using this technique and building on the projected accelerated gradient method, we establish the best-known complexity bounds for solving problem (1) .To provide context, the best-known complexity bound for achieving an ϵ-accurate solution in singlelevel convex constrained optimization is O(ϵ -0.5 ), as demonstrated in [17] . This optimal bound was achieved using the accelerated proximal method or FISTA (Fast Iterative Shrinkage-Thresholding Algorithm), which also influenced the development of our algorithm. While the literature on bilevel optimization is not as extensive as that for single-level optimization, there have been recent nonasymptotic results for solving this class of problems, which we summarize in Table 1 .Specifically, these results aim to establish convergence rates on the infeasibility gap g(x k ) -g * and the suboptimality gap f (x k ) -f * after k iterations. In [12] , an iterative regularization-based method demonstrated a convergence rate of O(1/k 0.5-b ) in terms of suboptimality and a rate of O(1/k b ) in terms of infeasibility, where b ∈ (0, 0.5) is a user-defined parameter. Setting b = 0.25 to balance these rates requires an iteration complexity of O(max{1/ϵ 4 f , 1/ϵ 4 g }) to find a solution that is ϵ f -optimal and ϵ g -infeasible. Later, the Bi-Sub-Gradient (Bi-SG) algorithm was proposed in [13] to address convex simple bilevel optimization problems with nonsmooth upper-level objective functions. It showed convergence rates of O(1/k 1-α ) and O(1/k α ) in terms of suboptimality and infeasibility, respectively, where α ∈ (0.5, 1) serves as a hyper-parameter. Balancing the rates by setting α = 0.5 results in an iteration complexity of O(max{1/ϵ 2 f , 1/ϵ 2 g }). Additionally, a structureexploiting method introduced in [14] achieved an iteration complexity of O(max{1/ϵ 2 f , 1/ϵ 2 g }) when the upper-level objective is convex and the lower-level objective is convex and smooth. Imposing additional assumptions on the upper-level function, such as smoothness or strong convexity, does not result in faster rates for this method.• When the feasible set Z is compact, we show that AGM-BiO finds x that satisfies f (x)-f * ≤ ϵ f and g(x) -g * ≤ ϵ g within O(max{1/ √ ϵ f , 1/ϵ g }) iterations, where f * is the optimal value of problem (1) and g * is the optimal value of the lower-level problem. • With an additional r-th-order (r ≥ 1) Hölderian error bound assumption on the lowerlevel problem, AGM-BiO finds x satisfying f (x) -f * ≤ ϵ f and g(x) -g * ≤ ϵ g within Õ(max{ϵ-2r-1 2r f , ϵ -2r-1 2r g })iterations. Moreover, it achieves the stronger guarantee that |f (x) -f * | ≤ ϵ f and g(x) -g * ≤ ϵ g within Õ(max{ϵ-2r-1 2 f , ϵ -2r-1 2r g }) iterations.These bounds all achieve the best-known complexity bounds in terms of both suboptimality and infeasibility guarantees for the considered settings. All the non-asymptotic results are summarized and compared in Table 1 .Discussions on two concurrent works. The authors in [15] proposed a bisection algorithm with a total operation complexity of Õ(max{ϵ -0.5 f , ϵ -0.5 g }) to find an (ϵ f , ϵ g )-optimal solution, assuming the upper-level objective f meets specific criteria. Specifically, Assumption 1(iv) in [15] implies the ability to compute the projection onto the sublevel set of the upper-level function f . However, this assumption may not hold for general functions, such as the mean squared loss function in our over-parameterized regression example in Section 5. In [16] , the authors introduced the penalty-based accelerated proximal gradient method (PB-APG) for solving simple bilevel optimization problems with the r-th order Hölderian error bound assumption on the lower-level objective g. Their algorithm, similar to [8] , runs the accelerated proximal gradient method on a weighted sum of the upper and lower-level objective functions. PB-APG achieves a complexity of O(ϵ -0.5r f ) + O(ϵ -0.5 g ) to find an (ϵ f , ϵ g )-optimal solution. The term O(1/ϵ 0.5r f ) can become significantly large as the order of the Hölderian error bound r increases. In contrast, our algorithm, AGM-BiO, avoids this issue, requiring at most Õ(max{ϵ-2r-1 2r f , ϵ -2r-1 2r g}) iterations to achieve an (ϵ f , ϵ g )-optimal solution. Therefore, regardless of how large r is, the worst-case complexity for AGM-BiO is Õ(max{ϵ -1 f , ϵ -1 g }). Thus, our method achieves a better rate than PB-APG when r > 1.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: We clearly stated our contributions in the introduction aligned with the main claims in the abstract. 
preliminaries: 
 In this section, we state the assumptions and introduce the notions of optimality used in the paper.We focus on the case where both the upper and lower-level functions f and g are convex and smooth. Formally, we make the following assumptions. Assumption 2.1. Let ∥ • ∥ be an arbitrary norm on R n and ∥ • ∥ * be its dual norm. We assume these conditions hold: (i) Z ⊂ R n is convex and compact with diameter D, i.e., ∥x -y∥ ≤ D for all x, y ∈ Z.(ii) g is convex and continuously differentiable on an open set containing Z, and its gradient is L g -Lipschitz, i.e., ∥∇g(x) -∇g(y)∥ * ≤ L g ∥x -y∥ for all x, y ∈ Z.(iii) f is convex and continuously differentiable and its gradient is Lipschitz with constant L f .In this paper, we denote the optimal value and the optimal solution set of the lower-level problem as g * ≜ min z∈Z g(z) and X * g ≜ argmin z∈Z g(z), respectively. By Assumption 2.1, the set X * g is nonempty, compact, and convex, but in general, not a singleton since g could have multiple optimal solutions on Z, as g is only convex but not strongly convex. Moreover, we use f * to denote the optimal value and x * to denote an optimal solution of problem (1).In the simple bilevel problem, the suboptimality of a solution x is measured by f (x) -f * . Similarly, its infeasibility is indicated by g(x) -g * . To ensure minimal suboptimality and infeasibility, we formally define an (ϵ f , ϵ g )-optimal solution as follows. Definition 2.1.((ϵ f , ϵ g ) -optimal solution). A point x ∈ Z is (ϵ f , ϵ g )-optimal for problem (1) if f (x) -f * ≤ ϵ f and g(x) -g * ≤ ϵ g .This definition is commonly used in bilevel optimization literature [6] [7] [8] 13] . Due to the unique structure of bilevel optimization, it is not guaranteed that f (x) -f * will always be positive. To address this, we propose using |f (x) -f * | as the absolute optimal criterion. Definition 2.2.((ϵ f , ϵ g ) -absolute optimal solution). A point x ∈ Z is (ϵ f , ϵ g )-absolute optimal for problem (1) if |f (x) -f * | ≤ ϵ f and |g(x) -g * | ≤ ϵ g .Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: The main limitation is that our algorithm requires the compact domain as we stated in Section 3 and 4. We also explained why such an assumption is necessary in Remark 4.1.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. 
algorithm: 
 Before presenting our method, we first introduce a conceptual accelerated gradient method for solving the simple bilevel problem in (1) . The first step is to recast it as a constrained optimization problem:EQUATIONwhere X * g ≜ argmin z∈Z g(z) is the solution set of the lower-level objective. Conceptually, we apply Nesterov's accelerated gradient method (AGM) to achieve a rate of O(1/k 2 ) on the upper-level objective f . Several variants of AGM have been proposed; see, e.g., [18] . Here, we consider a variant proposed in [19] . It involves three intertwined sequences of iterates {x k } k≥0 , {y k } k≥0 , {z k } k≥0 and the scalar variables {a k } k≥0 and {A k } k≥0 . In the first step, we compute the auxiliary iterate y k byy k = A k A k +a k x k + a k A k +a k z k .Then in the second step, we update z k+1 byEQUATIONwhere Π X * g (•) denotes the Euclidean projection onto the set X * g . Finally, in the third step, we computex k+1 = A k A k +a k x k + a k A k +a k z k+1 and A k+1 = A k + a k . It can be shown that if the stepsize is selected as a k = k+14L f , then the suboptimality gap f (x k ) -f (x * ) of the iterates generated by the method above converges to zero at the optimal rate of O(1/k 2 ). In this case, indeed all the iterates are feasible as it is possible to project onto the set X * g . However, the conceptual method above is not directly implementable for the simple bilevel problem considered in this paper, as the constraint set X * g is not explicitly given. As a result projection onto the set X * g is not computationally tractable. To address this issue, we replace the implicit set X * g in (3) with X k , which can be explicitly characterized, making the Euclidean projection onto X k feasible. Additionally, X k must encompass the optimal solution set X * g . Inspired by the cutting plane approach in [6] , we define X k as the intersection of Z and a halfspace:EQUATIONHere, the auxiliary sequence {g k } k≥0 should be selected such that g k ≥ g * and g k → g * . One straightforward way to generate this sequence is by applying an accelerated projected gradient method to the lower-level objective g separately. The loss function of the iterates generated by this algorithm can be considered as {g k } for the above halfspace. Note that in this case, it is known thatEQUATIONAlgorithm 1 Accelerated Gradient Method for Bilevel Optimization (AGM-BiO)1: Input: A sequence {g k } K k=0 , a scalar γ ∈ (0, 1] 2: Initialization: A 0 = 0, x 0 = z 0 ∈ Z 3: for k = 0, . . . , K do 4: Set a k = γ k+1 4L f 5: Compute y k = A k A k +a k x k + a k A k +a k z k 6: Compute z k+1 = Π X k (z k -a k ∇f (y k )), whereX k ≜ {z ∈ Z : g(y k ) + ⟨∇g(y k ), z -y k ⟩ ≤ g k } 7: Compute x k+1 = A k A k +a k x k + a k A k +a k z k+1 8:Update A k+1 = A k + a k 9: end for 10: Return: x K Hence, the above requirements on the sequence {g k } are satisfied. Two remarks on the set X k are in order. First, the set X k in (4) has an explicit form, making the Euclidean projection onto X k tractable. It can also be verified that X k always contains the lower-level problem solution set X * g . To prove this, let x * be any point in X * g . By using the convexity of g, we obtain g(y k ) + ⟨∇g(y k ), x * -y k ⟩ ≤ g(x * ) = g * ≤ g k . Thus, x * satisfies both constraints in (4), so x * ∈ X k . Now that we have identified an appropriate replacement for the set X * g , we can easily implement a variant of the projected accelerated gradient method for the bilevel problem using the surrogate set X k . We refer to our method as the Accelerated Gradient Method for Bilevel Optimization (AGM-BiO) and its steps are outlined in Algorithm 1. It is important to note that the iterates, when projected onto the set X k , may not belong to the set X * g , as X k is an approximation of the true solution set. Consequently, the iterates might be infeasible. However, the design of X k allows us to control the infeasibility of the iterates, as we will demonstrate in the convergence analysis section.Remark 3.1. The design of the halfspace as specified in (4) should be recognized as a nuanced task. Various alternative formulations of halfspaces could fulfill the same primary conditions, such as {z ∈ Z :g(x k )+⟨∇g(x k ), z-x k ⟩ ≤ g k } and {z ∈ Z : g(z k )+⟨∇g(z k ), z-z k ⟩ ≤ g k }.However, the selection of the gradient at y k for constructing the halfspace is not arbitrary but essential as we characterize in the convergence analysis of our method. Remark 3.2. How to project onto the set X k ? In some cases, such as our over-parameterized regression problem, X k is the intersection of an L 2 ball and a half-space, for which a closed-form solution exists to find the projected iterates. In other cases, such as our linear inverse problem, we may not be able to find X k directly. Instead, we can solve the projection subproblem using Dykstra's projection algorithm [20] . In this case, an additional loop is needed to solve the subproblem.While our paper focuses on the smooth setting, our proposed method can be also extended to the composite setting. Let us consider the composite counterpart of Problem (1):EQUATIONwhere f 1 , g 1 : R n → R are smooth convex functions and f 2 , g 2 : R n → R are nonsmooth convex functions, respectively. To analyze and implement the proximal gradient-based methods, we need the following definition concerning the property of the proximal mapping. Definition 3.1. Given h : R n → (-∞, +∞] and η > 0, the proximal map of h is defined asEQUATIONTo handle the upper-level nonsmooth part f 2 , we change the projection step in Step 6 of Algorithm 1 to a proximal update, which is similar to the accelerated proximal gradient method for single-level problems in [17] .Algorithm 2 Proximal Accelerated Gradient Method for Bilevel Optimization (P-AGM-BiO)1: Input: A sequence {g k } K k=0 , a scalar γ ∈ (0, 1] 2: Initialization: A 0 = 0, x 0 = z 0 ∈ R n 3: for k = 0, . . . , K do 4: Set a k = γ k + 1 4L f 5: Compute y k = A k A k + a k x k + a k A k + a k z k 6:Computez k+1 = P rox a k (f2+δ X k ) (z k -a k ∇f 1 (y k )), whereX k ≜ {z ∈ R n : g 1 (y k ) + ⟨∇g 1 (y k ), z -y k ⟩ + g 2 (z) ≤ g k } 7: Compute x k+1 = A k A k + a k x k + a k A k + a k z k+1 8:Update A k+1 = A k + a k 9: end for 10: Return: x K On the other hand, to deal with the lower-level nonsmooth part g 2 , it is necessary to modify the approximated lower-level solution set X k . Specifically, we keep the linear approximation of the smooth part of the lower-level objective function g 1 while adding the nonsmooth part g 2 as a lower bound of g k to construct X k . Note that the constructed set X k is no longer a halfspace in this setting due to the possibly non-linear nature of g 2 . We refer to our method as the Proximal Accelerated Gradient Method for Bilevel Optimization (P-AGM-BiO) and its steps are outlined in Algorithm 2.Different proximal-friendly assumptions are commonly used in the literature of composite singlelevel/bilevel optimization [8, [15] [16] [17] . The following proximal-friendly assumption is necessary for our method in the composite setting. Assumption 3.1. The function f 2 + δ X k in the Step 6 of Algorithm 2 is proximal-friendly, i.e. the proximal mapping in Definition 3.1 is easy to compute, where δ X k (•) is the indicator function.This assumption implies that f 2 is proximal-friendly and that projecting onto the constructed set X k can be done efficiently. Moreover, the function f 2 + δ X k is the sum of two convex functions, and the study of proximal mappings for such sums is well-documented in the literature [21] [22] [23] [24] . Under this assumption, all analysis for the smooth case can be extended to the composite setting. The details are provided in Section B of the Appendix.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: Our paper provides the full set of assumptions in Section 2.1 and a complete proof in Section A. 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a 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. 
convergence analysis: 
 In this section, we analyze the convergence rate and iteration complexity of our proposed AGM-BiO method for convex simple bilevel optimization problems. We choose the stepsize a k = k+1 4L f , which is inspired from our theoretical analysis. The main theorem is as follows, Theorem 4.1. Suppose Assumption 2.1 holds. Let {x k } k≥0 be the sequence of iterates generated by Algorithm 1 with stepsize a k = k+1 4L f for k ≥ 0 and suppose the sequence g k used for generating the cutting plane satisfies (5) . Then, for any k ≥ 0 we have, (i) The function suboptimality is bounded above by f(x k ) -f (x * ) ≤ 4L f ∥x0-x * ∥ 2 k(k+1).(ii) The infeasibility term is bounded above by g(EQUATIONk+1 .(iii) Furthermore, if the condition f (x k ) ≥ f (x * ) holds, then the infeasibility term is bounded above byEQUATION.Theorem 4.1 shows the upper-level objective function gap is upper bounded by O(1/k 2 ), which matches the convergence rate of the accelerated gradient method for single-level optimization problems. On the other hand, the suboptimality of the lower-level objective which measures infeasibility for the bilevel problem in the worst case is bounded above by O(1/k). In the case where f (x k ) ≥ f * , this upper bound improves to O(1/k 2 ). As a corollary of the worst-case bounds, Algorithm 1 will return an (ϵ f , ϵ g )-optimal solution after at most the following number of iterations O(max{ 1 √ ϵ f , 1 ϵg }). We should emphasize that, under the assumptions being considered, this complexity bound represents the best-known bound among all previous works summarized in Table 1 .Remark 4.1 (The necessity of compactness of Z). For the lower-level objective, we show that 24) in Section A). The main challenge in obtaining an accelerated rate of O(1/k 2 ) for g is controllingA k (g(x k ) -g(x * )) ≤ k-1 i=0 a i (g i -g * ) + Lg 4L f k-1 i=0 ∥z i+1 -z i ∥ 2 ((k-1 i=0 ∥z i+1 -z i ∥ 2 .Without a lower bound on f , this term cannot be bounded by the upper-level suboptimality alone. If f (x k ) ≥ f (x * ), we can achieve the rate of O(1/k 2 ) for g. Otherwise, we use the compactness of Z to achieve O(1/k) for g. Please refer to Section A for more details.Remark 4.2 (Removable log terms). The log terms in all the complexity results can be removed by choosing the auxiliary sequence g k = g K for all 0 ≤ k ≤ K, which satisfies the condition (5) . This eliminates the log term in (24) and all subsequent results. However, this choice of {g k } k≥0 requires predetermining the total number of iterations K.Since the algorithm's output x may fall outside the feasible set X * g , the expression f (x) -f * may not necessarily be non-negative. On the other hand, under the considered assumptions, proving convergence in terms of |f (x) -f * | is known to be impossible due to a negative result presented by [25] . Specifically, for any first-order method and a given number of iterations k, they demonstrated the existence of an instance of Problem (1) where |f (x k ) -f * | ≥ 1 for all k ≥ 0. Thus, to provide any form of guarantee in terms of the absolute value of the suboptimality, i.e., |f (x) -f * |, we need an additional assumption to obtain a lower bound on suboptimality and to provide a convergence bound for |f (x) -f * |. We will address this point in the following section.In this section, we introduce an additional regularity condition on g to establish a lower bound for f (x) -f * . Specifically, we assume that the lower-level objective function g satisfies the Hölderian Error Bound condition, which governs how g(x) grows as x moves away from the optimal solution set X * g . Intuitively, since our method's output x is ϵ g -optimal for the lower-level problem, it should be close to X * g under this regularity condition. We can then use this proximity and the smoothness property of f to establish a lower bound for f (x) -f * . Assumption 4.1. The function g satisfies the Hölderian error bound for some α > 0 and rEQUATIONwhere dist x,X * g ≜ inf x ′ ∈X * g ∥x -x ′ ∥.We note that the Hölderian error bound condition in ( 8) is well-studied in the optimization literature [26] [27] [28] and is known to hold in general when function g is analytic and the set Z is bounded [29] .There are two important special cases of the Hölderian error bound condition: 1) g satisfies ( 8) with r = 1 known as the weak sharpness condition [30, 31] ; 2) g satisfies ( 8) with r = 2 known as the quadratic functional growth condition [32] . By using the Hölderian error bound condition, [6] established a stronger relation between suboptimality and infeasibility, as shown next. M = max x∈X * g ∥∇f (x)∥ * . Then f (x) -f * ≥ -M ( r(g(x)-g * ) α ) 1 r for any x ∈ Z.Hence, under Assumption 4.1, Proposition 4.2 shows that the suboptimality f (x) -f * can also be bounded from below when x is an approximate solution of the lower-level problem. As a result, we can establish a convergence bound on |f (x k ) -f * | by combining Proposition 4.2 with the upper bounds in Theorem 4.1. Moreover, it also allows us to improve the convergence rate for the lower-level problem. To prove this claim, we first introduce the following lemma which establishes an upper bound on the weighted sum of upper and lower-level objectives. Lemma 4.3. Suppose conditions (ii) and (iii) in Assumption 2.1 hold. Let {x k } be the sequence of iterates generated by Algorithm 1 with stepsize a k = γ k+1 4L f , where 0 < γ ≤ 1. If the sequence g k used for generating the cutting plane satisfies (5), then for any λ ≥(2/γ-1)L f and k ≥ 0 we haveEQUATIONThis result characterizes and upper bound of Õ(1/k 2 ) on the expression λ(f(x k )-f (x * ))+g(x k )- g(x *). That said, the first term in this expression, a.k.a., λ(f (x k ) -f (x * )) may not be non-negative for a bilevel problem as discussed earlier. Hence, we cannot simply eliminate λ(f(x k ) -f (x * )) to show an upper bound of O(1/k 2 ) on infeasibility, a.k.a., g(x k ) -g(x *). Instead, we leverage the Hölderian error bound on g and apply Proposition 4.2 to the first term. As a result, we can eliminate the dependence on f in (9) . In this case, we can establish an upper bound on infeasibility. Theorem 4.4. Suppose conditions (ii) and (iii) in Assumption 2.1 hold and the lower-level function g satisfies the Hölderian error bound with r > 1. Let {x k } be the iterates generated by Algorithm 1 with stepsizea k = γ k+1 4L f , where γ = 1/( 2Lg L f K 2r-22r-1 +2) and K is the total number of iterations. Moreover, suppose the sequence g k used for generating the cutting plane satisfies (5) . If we define the constantsC f ≜ 8L f ∥x 0 -x * ∥ 2 , C g ≜ 12L g ∥x 0 -x * ∥ 2 and C ≜ M ( r α ) 1 r, where M ≜ max x∈X * g ∥∇f (x)∥, α and r are the parameters in Assumption 4.1, then the following results hold:(i) The function suboptimality is bounded above byEQUATION) 1 r-1 K 2 2r-1 (iii) The infeasibility term is bounded above by g(x K ) -g(x * ) ≤ max 2C g (ln K + 1) K 2r 2r-1 + 2C f K 2 , (2C) r r-1 K 2r 2r-1Before unfolding this result, we would like to highlight that unlike the result in Theorem 4.1, the above bounds in Theorem 4.4 do not require the feasible set to be compact. Since r > 1, the first result shows f (x K ) -f (x * ) has an upper bound of Õ(( 1 K ) 2r 2r-1 ) and the second result guarantees a lower bound of -Õ(( 1 K ) 2 2r-1 ). These two bounds together lead to an upper bound of Õ(( 1 K ) 2 2r-1 ) for the absolute error |f (x K )-f (x * )|. Moreover, the third result implies that the lower-level problem suboptimality which measures infeasibility is bounded above by Õ(( 1 K ) 2r 2r-1 ).The previous result presented in Theorem 4.4 is applicable when r > 1. However, for the case that 1st-order Hölderian error bound condition on g holds (i.e., weak sharpness condition), we require a distinct analysis and a different choice of γ to achieve the tightest bounds. In the subsequent theorem, we present our findings for this specific scenario. Theorem 4.5. Suppose conditions (ii) and (iii) in Assumption 2.1 are met and that the lower-level objective function g satisfies the Hölderian error bound with r = 1. Let {x k } be the sequence of iterates generated by Algorithm 1 with stepsizea k = γ k+1 4L f , where 0 < γ ≤ min{ 2αL f 2M Lg+αL f , 1}.Moreover, suppose the sequence g k used for generating the cutting plane satisfies (5), and recallM ≜ max x∈X * g ∥∇f (x)∥ and α in Assumption 4.1. If we define the constants C f ≜ 4L f ∥x 0 -x * ∥ 2 and C g ≜ 8L g ∥x 0 -x * ∥ 2 , then for any k ≥ 0: (i) The function suboptimality is bounded above by f (x k ) -f (x * ) ≤ C f γk(k+1) . (ii) The function suboptimality is bounded below by f (x k ) -f (x * ) ≥ - CgM (ln k+1) αk(k+1) - C f γk(k+1) . (iii) The infeasibility term is bounded above by g(x k ) -g(x * ) ≤ Cg(ln k+1) k(k+1) + αC f γM k(k+1) .Theorem 4.5 shows that under the Hölderian error bound with r = 1, also known as weak sharpness condition, the absolute value of the function suboptimality |f (x k ) -f (x * )| approaches zero at a rate of O(1/k 2 ) -ignoring the log term. The lower-level error g(x k ) -g(x * ), capturing the infeasibility of the iterates, also approaches zero at a rate of O(1/k 2 ). As a corollary, Algorithm 1 returns an (ϵ f , ϵ g )-absolute optimal solution after Õ(max{ 1 √ ϵ f , 1 √ ϵg }) iterations.Question: Does the paper fully disclose all the information needed to reproduce the main experimental 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)? Answer: [Yes] Justification: The experimental results are stated in Section 5. The implementation details are included in Section E. The code and data are attached in the supplementary material. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it 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 is 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , 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 to have some path to reproducing or verifying the results. 
numerical experiments: 
 In this section, we evaluate our AGM-BiO method on two different bilevel problems using real and synthetic datasets. We compare its runtime and iteration count with other methods, including a-IRG [12] , CG-BiO [6] , Bi-SG [13] , SEA [14] , R-APM [8] , PB-APG [16] , and Bisec-BiO [15] .Over-parameterized regression. We examine problem (1) where the lower-level problem corresponds to training loss, and the upper-level pertains to validation loss. The objective is to minimize the validation loss by selecting an optimal training loss solution. This method is also referred to as lexicographic optimization [33] . A common example of that is the constrained regression problem, where we aim to find an optimal parameter vector β ∈ R d for the validation loss that minimizes the loss ℓ tr (β) over the training dataset D tr . To represent some prior knowledge, we constrain β to be in some subsetZ ⊆ R d , e.g., Z = {β | β 1 ≤ • • • ≤ β d } in isotonic regression and Z = {β | ∥β∥ p ≤ λ} in L p constrained regression.Without explicit regularization, an over-parameterized regression over the training dataset has multiple global minima, but not all these optimal regression coefficients perform equally on validation or testing datasets. Thus, the upper-level objective serves as a secondary criterion to ensure a smaller error on the validation dataset D val . The problem can be cast asmin β∈R d f (β) ≜ ℓ val (β) s.t. β ∈ argmin z∈Z g(z) ≜ ℓ tr (z)In this case, both upper-level and lower-level objectives are convex and smooth if the loss ℓ is smooth and convex. Since projections onto the sublevel set of f are difficult to compute, Bisec-BiO is excluded from this experiment.We apply the Wikipedia Math Essential dataset [34] which is composed of a data matrix A ∈ R n×d with n = 1068 samples and d = 730 features and an output vector b ∈ R n . We use 75% of the dataset as the training set (A tr , b tr ) and 25% as the validation set (A val , b val ). For both upperand lower-level loss functions, we use the least squared loss. Then the lower-level objective isg(β) = 1 2 ∥A tr β -b tr ∥ 2 2 , the upper-level objective is f (β) = 1 2 ∥A val β -b val ∥ 2 2, and the constraint set is chosen as the unit L 2 -ball Z = {β | ∥β∥ 2 ≤ 1}. Note that this regression problem is overparameterized since the number of features d is larger than the number of data points in both the training set and validation set.In Figures 1(a ) and 1(c), we observe that the three accelerated gradient-based methods (R-APM, PB-APG, and AGM-BiO) converge faster in reducing infeasibility, both in terms of runtime and number of iterations. In terms of absolute suboptimality, shown in Figures 1(b ) and 1(d), AGM-BiO achieves the smallest absolute suboptimality gap among all algorithms. Unlike the infeasibility plots, R-APM and PB-APG underperform compared to AGM-BiO. Note that the lower-level objective in this problem does not satisfy the weak sharpness condition, so the regularization parameter η in R-APM is set as 1/(K + 1). Consequently, the suboptimality for R-APM converges slower than AGM-BiO, as suggested by the theoretical results in Table 1 .Linear inverse problems. In the next experiment, we concentrate on a problem that fulfills the Hölderian Error Bound condition for some r > 1. We aim to evaluate the performance of our method in this specific context and verify the validity of our theoretical results for this scenario. Specifically, we focus on the so-called linear inverse problems, commonly used to evaluate convex bilevel optimization algorithms, which originate from [35] . The goal of linear inverse problems is to obtain a solution x ∈ R n to the system of linear equation Ax = b. Note that if A is rank-deficient, there can be multiple solutions, or there might be no exact solution due to noise. To address this issue, we chase a solution that has the smallest weighted norm with respect to some positive definite matrix Q, i.e., ∥x∥ Q := x ⊤ Qx. This problem can be also cast as the following simple bilevel problem:min x∈R n f (x) ≜ 1 2 ∥x∥ 2 Q s.t. x ∈ argmin z∈Z g(z) ≜ 1 2 ∥Az -b∥ 2 2For this class of problem, if Q, A, and b are generated randomly or by the "regularization tools" like [14, 35] , we are not able to obtain the exact optimal value f * . To the best of our knowledge, no existing solver could obtain the exact optimal value f * for this bilevel problem. Specifically, the existing solvers either fail to solve this bilevel problem or return an inaccurate solution by solving a relaxed version of the problem. Hence, in [14, 35] they only reported the upper-level function value. However, in this paper, we intend to obtain the complexity bounds for finding (ϵ f , ϵ g )-optimal and (ϵ f , ϵ g )-absolute optimal solutions. Without knowing f * , we can not characterize the behavior of |f (x k ) -f * |. Therefore, we choose an example where we can obtain the exact solution. Specifically, we setQ = I n , A = 1 ⊤ n , b = 1,and the constraint set Z = R n + . In this case, the optimal solution x * = 1 n 1 n and optimal value f * = 1 2n . This specific example essentially involves seeking the minimum norm for an under-determined system. Note that the lower-level objective in this problem satisfies the Hölderian Error Bound condition with order r = 2 [36] . Hence, we do not need the constraint set Z to be compact as shown in Theorem 4.4. Due to the unbounded nature of the constraint set, Frank-Wolfe-type methods are not viable options. Consequently, we have opted not to incorporate CG-BiO in this experiment.We explored examples with two distinct dimensions: n = 3 and n = 100, evaluating a total of 2000 gradients. In Figures 2(a ) and 2(c), AGM-BiO shows superior performance in terms of infeasibility. In Figures 2(b ) and 2(d), we compare methods in terms of absolute error of suboptimality. The gap between R-APM and AGM-BiO is smaller for n = 3, but for n = 100, AGM-BiO significantly outperforms all other methods, including R-APM. Since the regularization and penalty parameters in R-APM and PB-APG are fixed, they might get stuck at a certain accuracy level, as seen in Figures 2(a ) and 2(c). In contrast, AGM-BiO uses a dynamic framework for minimizing the upper and lower-level functions, consistently reducing both suboptimality and infeasibility. Although Bisec-BiO theoretically has the best complexity results due to the ease of projecting onto the sublevel set of f , its performance in the last iteration is inconsistent, as shown in Figure 2 .Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: The code and data are attached in the supplementary material. Guidelines:• The answer NA means that paper does not include experiments requiring code. Justification: The paper conforms, in every respect, with the NeurIPS Code of Ethics Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
conclusion: 
 In this paper, we introduced an accelerated gradient-based algorithm for solving a specific class of bilevel optimization problems with convex objective functions in both the upper and lower levels. Our proposed algorithm achieves a computational complexity of O(max{ϵ -0.5 f , ϵ -1 g }). When an additional weak sharpness condition is applied to the lower-level function g, the iteration complexity improves to Õ(max{ϵ -0.5 f , ϵ -0.5 g }), matching the well-known fastest convergence rate for singlelevel convex optimization problems. We further extended this result to an iteration complexity of Õ(max{ϵ-2r-1 2r f , ϵ -2r-1 2r g })when the lower-level loss satisfies the Hölderian error bound assumption. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? 
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 paper poses no such risks.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: [Yes] Justification: The data used in the paper are properly credited and cited in Section 5.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. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model 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. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: To prove Theorem 4.1, we start with the following general lemma that holds for any choice of the step sizes {a k }. Lemma A.1. Let {x k } be the sequence of iterates generated by Algorithm 1 with stepsize a k > 0 for k ≥ 0. Then we haveEQUATIONEQUATION)Proof of Lemma A.1. Let x * be any optimal solution of (1). We first consider the upper-level objective f . Since f is convex, we haveEQUATION)Now given the update ruleEQUATIONCombining ( 12) and ( 13), we haveEQUATIONwhere the last equality follows from the definition of y k . Furthermore, since f is L f -smooth, we haveEQUATION)If we multiply both sides of (15) by A k+1 and combine the resulting inequality with (14) , we obtainEQUATIONwhere we used the fact that a k (z k+1 -z k ) = A k+1 (x k+1 -y k ) in the first equality. Moreover, since x * ∈ X k , we obtain from the update rule in (3) thatEQUATION)Combining ( 16) and ( 17) leads toEQUATIONL f a 2 k A k+1 -1 ∥z k+1 -z k ∥ 2 ,which proves the claim in (10) .Next, we proceed to prove the claim in (11) . To do so, we first leverage the convexity of g which leads to g(y k ) -g(x k ) ≤ ⟨∇g(y k ), y k -x k ⟩ . (18) Also, since g is L g -smooth, we haveEQUATION)By multiplying both sides of ( 18) and ( 19) by A k and A k+1 , respectively, and adding the resulted inequalities we obtainA k+1 (g(x k+1 ) -g(y k )) + A k (g(y k ) -g(x k )) ≤ A k+1 ⟨∇g(y k ), x k+1 -y k ⟩ + A k ⟨∇g(y k ), y k -x k ⟩ + L g A k+1 2 ∥x k+1 -y k ∥ 2 = a k ⟨∇g(y k ), z k+1 -z k ⟩ + A k ⟨∇g(y k ), y k -x k ⟩ + L g a 2 k 2A k+1 ∥z k+1 -z k ∥ 2 = a k ⟨∇g(y k ), z k+1 -y k ⟩ + L g a 2 k 2A k+1 ∥z k+1 -z k ∥ 2 ,where the first equality holds since a k (z k+1 -z k ) = A k+1 (x k+1 -y k ), and the second equality holds sincea k (z k -y k ) = A k (y k -x k ).Lastly, by the definition of the constructed cutting plane, we know that g(y k ) + ⟨∇g(y k ), zy k ⟩ ≤ g k for any z ∈ X k . Hence, ⟨∇g(y k ), z k+1 -y k ⟩ is upper bounded by g k -g(y k ). Applying this substitution into to the above expression would lead to the claim in (11) .Now we are ready to prove Theorem 4.1.Proof of Theorem 4.1. To begin with, note that by our choice of a k , we haveEQUATIONThus, it can be verified that L f a 2 k ≤ 1 2 A k+1 . Then it follows from Lemma A.1 thatEQUATIONEQUATION)We first prove the convergence guarantee for the upper-level objective. By using induction on (21) , we obtain that for any k ≥ 0EQUATION)which impliesf (x k ) -f (x * ) ≤ ∥z 0 -x * ∥ 2 2A k = 4L f ∥z 0 -x * ∥ 2 k(k + 1) .We proceed to establish an upper bound on g(x k ) -g(x * ). By summing the inequality in ( 22) from 0 to k -1 we obtainEQUATIONNote that the second inequality holds due to the condition in (5) . Thus, we obtaing(x k ) -g(x * ) ≤ 4L g ∥x 0 -x * ∥ 2 (ln k + 1) k(k + 1) + 2L g D 2 k + 1 .The above upper bound on g(x k ) -g(x * ) without any additional condition, but next we show that if f (x k ) ≥ f (x * ) the above upper bound can be further improved as we can upper bound k-1 i=0 ∥z i+1 -z i ∥ 2 by a constant independent of k instead of kD 2 . To prove this claim, by summing the inequality in (10) from 0 to k -1 we obtainEQUATIONEQUATION)Thus if replace 24) by 2∥z 0 -x * ∥ 2 , we would obtain the following improve bound:k-1 i=0 ∥z i+1 -z i ∥ 2 in (g(x k ) -g(x * ) ≤ 4L g ∥x 0 -x * ∥ 2 (ln k + 1) k(k + 1) + 4L g ∥z 0 -x * ∥ 2 k(k + 1).Recall Remark 4.1. The main difficulty in obtaining an accelerated rate of O(1/K 2 ) for g is that it is unclear how to controlK-1 k=0 ∥z k+1 -z k ∥ 2 .This, in turn, is because we don't know how to prove a lower bound on f . Instead, we used the compactness of Z to achieve the O(1/K) for g.Proof of Lemma 4.3. Note that by multiplying both sides of (10) by λ > 0 we haveEQUATIONFurther note that in this case we have a k = γ(k+1)4L f and A k+1 = γ (k+1)(k+2) 8L f. Hence, a 2 k /A k+1 is bounded above by γ 2L f . Therefore, we can replace a 2 k /A k+1 in the above expression by γ 2L f to obtainA k+1 (λ(f (x k+1 ) -f (x * ))) + λ 2 ∥z k+1 -x * ∥ 2 -A k (λ(f (x k ) -f (x * ))) + λ 2 ∥z k -x * ∥ 2 ≤ λ 2 γ 2 -1 ∥z k+1 -z k ∥ 2 (28) Similarly, we can replace a 2 k /A k+1 in (11) by γ 2L f to obtain A k+1 (g(x k+1 ) -g(x * )) -A k (g(x k ) -g(x * )) ≤ a k (g k -g(x * )) + γL g 4L f ∥z k+1 -z k ∥ 2 (29)Note if we sum up the two inequalities above, we obtainEQUATIONNote that the last inequality holds since the first term is negative due to the choice of λ. By summing the inequalities from 0 to k -1 we obtainA k (λ(f (x k )-f (x * ))+g(x k )-g(x * ))+ 1 2 λ∥z k -x * ∥ 2 ≤ k-1 i=0 a i (g i -g(x * ))+ 1 2 λ∥z 0 -x * ∥ 2 (31)Now using the condition on g i in ( 5) and the definition of a i we haveEQUATIONBy applying this upper bound into (31) we obtainA k (λ(f (x k )-f (x * ))+g(x k )-g(x * ))+ 1 2 λ∥z k -x * ∥ 2 ≤ γL g 2L f ∥x 0 -x * ∥ 2 (ln k+1)+ 1 2 λ∥z 0 -x * ∥ 2(33) If we drop the 1 2 λ∥z k -x * ∥ 2 in the left-hand side and divide both sides of the resulted inequality byEQUATIONand the proof is complete.Proof of Theorem 4.4. Recall the result of Lemma 4.3 that if a k = γ(k+1)/(4L f ), where 0 < γ ≤ 1 and λ ≥(2/γ-1)L f then after K iterations we haveEQUATIONNow if we replace γ by 1/(2Lg L f K 2r-22r-1 + 2) as suggested in the statement of the theorem, we would obtain λ(fEQUATIONNow we proceed to prove the first claim which is an upper bound on f (x K ) -f (x * ). Note that given the fact that g(x K ) -g(x * ) > 0 and λ > 0 we can show thatEQUATION)If we select λ which is a free parameter asEQUATION)Given the fact that x 0 = z 0 we can simplify the upper bound toEQUATION)Next, we proceed to establish an upper bound on g(x K ) -g(x * ). We will use the following inequality that holds due to the HEB condition and formally stated in Proposition 4.2:EQUATIONNow if we replace this lower bound into (36) we would obtainEQUATIONNext we consider two different cases: In the first case we assume λM ( r α )1 r (g(x K ) -g(x * )) 1 r ≤ 1 2 (g(x K ) -g(x *)) holds and in the second case we assume the opposite of this inequality holds.If we are in the first case and λM ( r α )1 r (g(x K ) -g(x * )) 1 r ≤ 1 2 (g(x K ) -g(x *)), then the inequality in (41) leads toEQUATIONSince λ = K -2r-2 2r-1 , it further leads to the following upper boundg(x K ) -g(x * ) ≤ 8L g ∥x 0 -x * ∥ 2 (ln K + 1) K(K + 1) + 16L g ∥z 0 -x * ∥ 2 K(K + 1) + 16L f ∥z 0 -x * ∥ 2 K 1 2r-1 (K + 1).Now given the fact that x 0 = z 0 , we obtainEQUATIONIf we are in the second case and λM ( r α )1 r (g(x K )-g(x * )) 1 r > 1 2 (g(x K )-g(x *)) then this inequality is equivalent toEQUATIONleading tog(x K ) -g(x * ) ≤ 2K -2r-2 2r-1 M ( r α ) 1 r r r-1 = (2M ) r r-1 ( r α ) 1 r-1 K 2r 2r-1 (46)By combining the bounds in (44) and (46) we realize thatg(x K ) -g(x * ) ≤ max{ 24L g ∥x 0 -x * ∥ 2 (ln K + 1) K 2 + 16L f ∥x 0 -x * ∥ 2 K 2r 2r-1 , (2M ) r r-1 ( r α ) 1 r-1 K 2r 2r-1 } (47)Finally by using the above bound in (47) and the result of Proposition 4.2 we can prove the the second claim and establish a lower bound on f(x K ) -f * which is f (x K ) -f * ≥ -M r α 1 r max{ 24L g ∥x 0 -x * ∥ 2 (ln K + 1) K 2 + 16L f ∥x 0 -x * ∥ 2 K 2r 2r-1 , (2M ) r r-1 ( r α ) 1 r-1 K 2r 2r-1 } 1/r (48) leading to f (x K ) -f * ≥ -M r α 1 r max{ (24L g ∥x 0 -x * ∥ 2 (ln K + 1)) 1/r K 2/r + (16L f ∥x 0 -x * ∥ 2 ) 1/r K 2 2r-1 , ((2M ) r r-1 ( r α ) 1 r-1 ) 1/r K 2 2r-1 } (49)A.4 Proof of Theorem 4.5Proof of Theorem 4.5. To upper bound f (x k )-f (x * ), we follow a similar analysis as in Theorem 4.1. Specifically, first note that by our choice of a k , we havea k = γ k+1 4L f and A k+1 = γ (k+1)(k+2) 8L f, where γ ∈ (0, 1). Hence, we can obtain that L f a 2 k ≤ γ 2 A k+1 . By using Lemma A.1 and the fact that γ ∈ (0, 1), we haveA k+1 (f (x k+1 ) -f (x * )) + 1 2 ∥z k+1 -x * ∥ 2 -A k (f (x k ) -f (x * )) + 1 2 ∥z k -x * ∥ 2 ≤ γ 4 - 1 2 ∥z k+1 -z k ∥ 2 ≤ 0.By using induction, we obtain that for any k ≥ 0EQUATION) Since A k = γ k(k+1)8L f and z 0 = x 0 , this further implies thatf (x k ) -f (x * ) ≤ ∥z 0 -x * ∥ 2 2A k = 4L f ∥x 0 -x * ∥ 2 γk(k + 1).Next, we will prove the upper bound on g(x k ) -g(x * ). By Lemma 4.3, we have for any k ≥ 0EQUATIONMoreover, since g satisfies the weak sharpness condition, we can use Proposition 4.2 with r = 1 to writeEQUATIONCombining ( 51) and ( 52) leads toEQUATIONNote that we can choose λ to be any number satisfying λ ≥(2/γ-1)L f (cf. Lemma 4.3). Specifically, since γ ≤ 2αL f 2M Lg+αL f , we can set λ = α/(2M ) and accordingly (53) can be simplified tog(x k ) -g(x * ) ≤ 8L g ∥x 0 -x * ∥ 2 k(k + 1) (ln k + 1) + 4αL f ∥x 0 -x * ∥ 2 γM k(k + 1).Finally, we use (52) again together with the above upper bound on g(x k ) -g(x * ) to obtainf (x k )-f (x * ) ≥ - M α (g(x k )-g(x * )) ≥ - 8M L g ∥x 0 -x * ∥ 2 αk(k + 1) (ln k + 1) + 4L f ∥x 0 -x * ∥ 2 γk(k + 1) .In this section, we would like to mention the possible extension to the non-smooth/composite setting.In the general non-smooth settings, we believe it is not possible to extend our results and achieve the purpose of the acceleration. This is because, even in the single-level setting, the best achievable rate in the general non-smooth setting is O(1/ √ K) achieved by sub-gradient method. That said, it should be possible to extend our accelerated bilevel framework to a special non-smooth setting where the upper-and lower-level objective functions have a composite structure, i.e., they can be written as the sum of a convex smooth function and a convex non-smooth function that is easy to compute its proximal operator.Note that the properties of smoothness of f and g have only been used in the proof of Lemma A.1 in Section A. None of the other results will break if (10) and (11) in Lemma A.1 still hold in the composite setting. Now, we present and prove the counterpart of Lemma A.1 in the composite setting.Lemma B.1. Suppose f 1 , f 2 , g 1 , g 2 are convex and f 1 , g 1 are L f -smooth and L g -smooth, respectively. Let {x k } be the sequence of iterates generated by Algorithm 2 with stepsize a k > 0 for k ≥ 0. Moreover, suppose Assumption 3.1 holds. Then we haveEQUATION)EQUATION)Proof of Lemma B.1. Let x * be any solution of (6) .We first consider the upper-level objective f . Since f 1 is convex, we haveEQUATION)Now given the update rule A k+1 = A k + a k , we can write 56) and (57), we haveA k+1 (f 1 (y k ) -f 1 (x * )) -A k (f 1 (x k ) -f 1 (x * )) = a k (f 1 (y k ) -f 1 (x * )) + A k (f 1 (y k ) -f 1 (x k )) (57) Combining (EQUATION)where the last equality follows from the definition of y k . Furthermore, sinceEQUATION)If we multiply both sides of (59) by A k+1 and combine the resulting inequality with (58), we obtainEQUATION)where we used the fact that a k (z k+1 -z k ) = A k+1 (x k+1 -y k ) in the first equality. Moreover, from the step 6 in Algorithm 2, we havez k -a k ∇f 1 (y k ) -z k+1 ∈ a k ∂(f 2 (z k+1 ) + δ X k (z k+1 )).Using this, from the definition of subgradients for f 2 + δ X k , we have 60) and (61) leads to⟨x * -z k+1 , z k -a k ∇f 1 (y k ) -z k+1 ⟩ ≤ a k (f 2 (x * ) + δ X k (x * ) -f 2 (z k+1 ) -δ X k (z k+1 )) ⇔ ⟨z k+1 -z k + a k ∇f (y k ), x * -z k+1 ⟩ ≥ a k f 2 (z k+1 ) -a k f 2 (x * ) ⇔ a k ⟨∇f (y k ), z k+1 -x * ⟩ ≤ ⟨z k+1 -z k , x * -z k+1 ⟩ -a k f 2 (z k+1 ) + a k f 2 (x * ) ⇔ a k ⟨∇f (y k ), z k+1 -x * ⟩ ≤ 1 2 ∥z k -x * ∥ 2 - 1 2 ∥z k+1 -x * ∥ 2 - 1 2 ∥z k+1 -z k ∥ 2 -a k f 2 (z k+1 ) + a k f 2 (x * ). (61) The first step holds since x * , z k+1 ∈ X k , i.e. δ X k (x * ) = δ X k (z k+1 ) = 0. Combining (EQUATIONThen we addEQUATIONFinally, by the convexity of f 2 , A k+1 = A k + a k , andx k+1 = A k A k +a k x k + a k A k k z k+1 , i.e. -a k f 2 (z k+1 ) + A k+1 f 2 (x k+1 ) -A k f 2 (x k ) ≤ 0,the first inequality of this Lemma can be obtained.Next, we proceed to prove the claim for the lower-level objective g. To do so, we first leverage the convexity of the smooth part g 1 which leads toEQUATION)Also, since g 1 is L g -smooth, we haveEQUATION)By multiplying both sides of ( 64) and ( 65) by A k and A k+1 , respectively, and adding the resulted inequalities we obtainA k+1 (g 1 (x k+1 ) -g 1 (y k )) + A k (g 1 (y k ) -g 1 (x k )) ≤ A k+1 ⟨∇g 1 (y k ), x k+1 -y k ⟩ + A k ⟨∇g 1 (y k ), y k -x k ⟩ + L g A k+1 2 ∥x k+1 -y k ∥ 2 = a k ⟨∇g 1 (y k ), z k+1 -z k ⟩ + A k ⟨∇g 1 (y k ), y k -x k ⟩ + L g a 2 k 2A k+1 ∥z k+1 -z k ∥ 2 = a k ⟨∇g 1 (y k ), z k+1 -y k ⟩ + L g a 2 k 2A k+1 ∥z k+1 -z k ∥ 2 ,where the first equality holds since a k (z k+1 -z k ) = A k+1 (x k+1 -y k ), and the second equality holds since a k (z k -y k ) = A k (y k -x k ). Lastly, by the definition of the constructed approximated set X k , we know that g 1 (y k ) + ⟨∇g 1 (y k ), zy k ⟩ + g 2 (z) ≤ g k for any z ∈ X k . Hence, ⟨∇g 1 (y k ), z k+1 -y k ⟩ is upper bounded by g k -g 1 (y k ) -g 2 (z k+1 ). Applying this substitution into to the above expression to obtain,EQUATIONBy adding a k g 1 (y k ) -a k g 1 (x * ) on both sides, we have,EQUATIONLastly, we add(A k+1 g 2 (x k+1 ) -a k g 2 (x * ) -A k g 2 (x k )) on both sides to obtain, A k+1 (g(x k+1 ) -g(x * )) + A k (g(x * ) -g(x k )) ≤ a k g k -a k g(x * ) + A k+1 g 2 (x k+1 ) -A k g 2 (x k ) -a k g 2 (z k+1 ) + L g a 2 k 2A k+1 ∥z k+1 -z k ∥ 2 (68)By the convexity of g 2 , A k+1 = A k + a k , andx k+1 = A k A k +a k x k + a k A k +a k z k+1 (outlined in Algorithm 2), i.e. A k+1 g 2 (x k+1 ) -A k g 2 (x k ) -a k g 2 (z k+1 ) ≤ 0,the second inequality of this Lemma can be achieved.Hence, with the additional Assumption 3.1, by replicating the analysis outlined in Section A, we can derive identical complexity results for Algorithm 2 in either the compact domain setting or with the Hölderian error bounds on g.Previous work has explored "asymptotic" results for simple bilevel problems, dating back to Tikhonovtype regularization introduced in [37] . In this approach, the objectives of both levels are combined into a single-level problem using a regularization parameter σ > 0 and as σ → 0 the solutions of the regularized single-level problem approaches a solution to the bilevel problem in (1) . Further, the authors in [38] proposed the explicit descent method that solves problem (1) when upper and lower-level functions are smooth and convex. This result was further extended to a non-smooth setting in [39] . The results in both [38] and [39] only indicated that both upper and lower-level objective functions converge asymptotically. Moreover, the authors in [40] proposed the ϵ-subgradient method to solve simple bilevel problems and showed its asymptotic convergence. Specifically, they assumed the upper-level objective function to be convex and utilized two different algorithms, namely, the Fast Iterative Bilevel Algorithm (FIBA) and Incremental Iterative Bilevel Algorithm (IIBA), that consider smooth and non-smooth lower-level objective functions, respectively. Some studies have only established non-asymptotic convergence rates for the lower-level problem. One of the pioneering methods in this category is the minimal norm gradient (MNG) method, introduced in [41] . This method assumes that the upper-level objective function is smooth and strongly convex, while the lower-level objective function is smooth and convex. The authors showed that the lower-level objective function reaches an iteration complexity of O(1/ϵ 2 ). Subsequently, the Bilevel Gradient SAM (BiS-SAM) method was introduced in [35] , and it was proven to achieve a complexity of O(1/ϵ) for the lower-level problem. A similar rate of convergence was also attained in [42] .In this section, we would like to highlight the connection between our algorithm's projection step (outlined in Step 6 of Algorithm 1) and the Polyak step size. To make this connection, we first without loss of generality, replace g k with g * . It is a reasonable argument, as g k values are close to g * , a point highlighted in (5) . In addition, we further assume that the set Z = R n to simplify the expressions. Given these substitutions, the projection step in our AGM-BiO method is equivalent to solving the following problem:min ∥x -x k ∥ 2 s.t. g(x k ) + ⟨∇g(x k ), x -x k ⟩ ≤ g *In other words,x k+1 is the unique solution of the above quadratic program with a linear constraint. By writing the optimality conditions for the above problem and considering λ as the Lagrange multipliers associated with the linear constraint, we obtain that   x k+1 = x k -λ∇g(x k ) λ(g(x k ) + ⟨∇g(x k ), x k+1 -x k ⟩ -g * ) = 0 λ ≥ 0Given the fact that x k+1 ̸ = x k , we can conclude that λ ̸ = 0, and hence we have   x k+1 = x k -λ∇g(x k ) g(x k ) + ⟨∇g(x k ), x k+1 -x k ⟩ -g * = 0 λ > 0By replacing x k+1 in the second expression with its expression in the first equation we obtain thatλ = g(x k ) -g * ∥∇g(x k )∥ 2 .which is exactly the Polyak step size in the literature [43] . To solve a bilevel optimization problem, we intend to do gradient descent for both upper-and lower-level functions. Tuning the ratio of upperand lower-level step size is generally hard. However, by connecting the projection step with the Polyak step size, we observe that the stepsize for the lower-level objective is auto-selected as the Polyak stepsize in our method. In other words, it is one of the advantages of our algorithm that we do not need to choose the lower-level stepsize or ratio of the upper-and lower-level stepsize theoretically or empirically.In this section, we include more details of the numerical experiments in Section 5. All simulations are implemented using MATLAB R2022a on a PC running macOS Sonoma with an Apple M1 Pro chip and 16GB Memory.Dataset generation. The original Wikipedia Math Essential dataset [34] composes of a data matrix of size 1068 × 731. We randomly select one of the columns as the outcome vector b ∈ R 1068 and the rest to be a new matrix A ∈ R 1068×730 . We set the constraint parameter λ = 1 in this experiment, i.e., the constraint set is given by Z = {β | ∥β∥ 2 ≤ 1}.Implementation details. To be fair, all the algorithms start from the origin as the initial point. For our AGM-BiO method, we set the target tolerances for the absolute suboptimality and infeasibility to ϵ f = 10 -4 and ϵ g = 10 -4 , respectively. We choose the stepsizes as a k = 10 -2 (k + 1)/(4L f ).In each iteration, we need to do a projection onto an intersection of a L 2 -ball and a halfspace, which has a closed-form solution. For a-IRG, we set η 0 = 10 -3 and γ 0 = 10 -3 . For CG-BiO, we obtain an initial point with FW gap of the lower-level problem less than ϵ g /2 = 5 × 10 -5 and choose stepsize γ k = 10 -2 /(k + 2). For Bi-SG, we set η k = 10 -2 /(k + 1) 0.75 and t k = 1/L g = 1/λ max (A ⊤ tr A tr ) = 1.5 × 10 -4 . For SEA, we set both the lower-and upper-level stepsizes to be 10 -4 . For R-APM, since the lower-level problem does not satisfy the weak sharpness condition, we set η = 1/(K + 1) = 1.25 × 10 -5 and γ = 10 -4 ≤ 1/(L g + ηL f ). For PB-APG, we set the penalty parameter γ = 10 4 . Note that the lower-level problem in this experiment does not satisfy Höderian error bound assumption, so there is no theoretical guarantee for PB-APG.Dataset generation. We setQ = I n , A = 1 ⊤n , and b = 1. The constraint set is selected as Z = R n + . We choose a low dimensional (n = 3) and a high dimensional (n = 100) example and run K = 10 3 number of iterations to compare the numerical performance of these algorithms, respectively.Implementation details. To be fair, all the algorithms start from the same initial point randomly chosen from R n + . For our AGM-BiO method, we set the stepsizes as a k = γ(k + 1)/(4L f ), where γ = 1/( 2Lg L f K 2/3 + 2) as suggested in Theorem 4.4. In each iteration, we need to project onto an intersection of a halfspace and R n + . Since halfspaces and R n + are both convex and closed set, the projection subproblem can be solved by Dykstra's projection algorithm in [20] . For a-IRG, we set η 0 = 10 -2 and γ 0 = 10 -2 . For Bi-SG, we set η k = 1/(k + 1) 0.75 and t k = 1/L g . For SEA, we set the lower-level stepsize to be 10 -2 and the upper-level stepsize to be 10 -2 . For R-APM, since the lower-level problem does not satisfy the weak sharpness condition, we set η = 1/(K + 1) and γ = 1/(L g + ηL f ). For PB-APG, we set the penalty parameter γ = 10 4 . For Bisec-BiO, we choose the target tolerances to ϵ f = ϵ g = 10 -4 . For comparison purposes, we limit the maximum number of gradient evaluations for each APG call to 10 2 . In this experiment, L f = 1 and L g = n, where n is the number of dimensions.• 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.Justification: There is no societal impact of the work performed in this paper.Guidelines:• The answer NA means that there is no societal impact of the work performed.• 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). 


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

Reviews: review: paper_summary: paper_summary: This work proposes an accelerated method to solve convex simple bilevel problems, with the author providing both theoretical and numerical guarantees of the algorithm's convergence.
strength_weakness: strength_weakness: Since the main techniques in this work, such as the accelerated gradient method and the cutting plane approach, have already been studied, the contribution of the proposed methods is incremental, and the convergence rate may not be difficult to prove based on existing studies.
questions: questions: - What is the convergence rate without using the accelerated gradient method, relying only on the projection onto the cutting plane?
  
- Since the accelerated gradient method has been well studied recently, what is the unique challenge of applying it to simple bilevel problems?
  
- Will this algorithm demonstrate any advantage in convergence without the assumption of the Hölderian error bound?
  
- How do you find a feasible $X_k$​ in practice? Is an additional loop required to achieve this?
limitations: limitations: No Limitation
paper_summary: paper_summary: The paper introduces a new algorithm called AGM-BiO (Accelerated Gradient Method for Bilevel Optimization) for solving simple bilevel optimization problems where both the upper and lower level objectives are convex and smooth.
strength_weakness: strength_weakness: You provide a modified algorithm (Algorithm 2) that could potentially handle this composite structure. In line 629-line 631 you mention that you can derive identical complexity results for Algorithm 2 in either the compact domain setting or with the Hölderian error bounds on g. I guess formally stating the convergence result in a theorem would strengthen the paper and provide a clear reference point for readers interested in the composite case.
questions: questions: -
limitations: limitations: Yes.
paper_summary: paper_summary: The paper works on the problem of simple convex smooth bilevel optimisation, where ''simple'' means single-variable. The paper achieves the optimal rate for this problem by a combination of Nesterov's acceleration and Jiang-Abolfazli-Mokhtari-Hamedani's cutting-plane method.
strength_weakness: strength_weakness: -
questions: questions: QUESTIONS. 

What limitations do the authors anticipate in extending this technique (acceleration + cutting-plane) to the non-simple case (i.e., when you have an additional variable $y$ in the upper level objective, defined as the optimizer of a parametrized lower-level problem).
limitations: limitations: N/A since it's a theory paper
paper_summary: paper_summary: This work proposes a novel optimization algorithm with improved iteration complexity for convex smooth simple bilevel optimization, and demonstrates its faster convergence using experiments.
strength_weakness: strength_weakness: This work focuses on simple bilevel optimization with both levels being convex and under deterministic setting (with access to full gradients instead of stochastic gradients), so the scope is not wide. Also, as shown in Table 1, the complexity results outperform existing ones only a little since the complexity order is the same as [8] for $r=1$, and the complexity dependence on $\epsilon_g^{-\frac{2r-1}{2r}}$ is worse than $\epsilon_g^{-0.5}$ in [16].
questions: questions: (1) In line 27, you may write down the math formulation for ``more general settings with parameterized lower-level problems'', or refer this formulation to appendix. 

(2) How did you obtain Eq. (5), the condition about $g_k$? How to guarantee Eq. (5) in implementation with unknown $g^*$, $x^*$, $L_g$? 

(3) Does Lemma 4.3 require Assumption 4.1? If yes, add Assumption 4.1 to Lemma 4.3.
limitations: limitations: In the checklist, the authors mention their limitation of compact domain assumption. There is no societal impact of this theoretical work.

Comments: title: The answer to Q2 is clear now.
Reviewer fv8w's further query on Q2
Thank you for your response
comment: Thank you for the response. We're glad your questions and concerns have been addressed! 

Regarding your further query, specifically, the non-accelerated version of our algorithm follows the update rule $x_{k+1} = \Pi_{X_k}(x_k - \eta_k \nabla f(x_k))$, where the set $X_k$ is similarly constructed from a cutting plane as $X_k = \\\{z \in Z: g(x_k) + \langle \nabla g(x_k), z-x_k \rangle \leq g_k \\\}$. To upper bound the lower-level objective, we can apply a similar analysis as in our Lemma A.1, leading to:$$g(x_{k+1}) \leq g(x_k) + \langle \nabla g(x_k), x_{k+1} - x_k\rangle+ \frac{L_g}{2}\\|x_{k+1} - x_k\\|^2 \leq g_k + \frac{L_g}{2}\\|x_{k+1} - x_k\\|^2,$$where the first inequality used the $L_g$-smoothness of $g$, and the second inequality follows from the fact that $x_{k+1} \in X_k$. However, the main challenge is controlling $\\|x_{k+1} - x_k\\|^2$ (see also Remark 4.1 for a related issue in our accelerated methods). If we follow the same strategy as in Theorem 4.1 and upper bound $\\|x_{k+1} - x_k\\|^2 \leq D^2$ by the compactness of $Z$, this results in $g(x_{k+1}) \leq g_k + \frac{L_g}{2}D^2$, which fails to provide a convergence rate for the lower-level objective. Therefore, it appears that acceleration is crucial to achieve the $O(1/k)$ rate for the lower-level objective reported in Theorem 4.1.

That said, we should clarify that this does not rule out the possibility of proving a convergence rate for the lower-level objective under the standard assumptions, though this appears non-trivial and would require a different analysis from the one presented in our paper. Thank you for your question, and we will further explore this topic in future research.
Thanks for the authors' response. 
My concerns and questions are solved so I will raise my score to 6. 
I am still curious about why the non-accelerated algorithm fails to provide any convergence guarantee for the lower-level objective.
Thanks authors.

The answer to Q2 is clear now. 

Reviewer fv8w
Thank you for the follow-up questions!

**Q. For Q2, does $g_k$ denote the function value from the k-th iteration of the Nesterov's gradient method on $g$? $\\{g_k\\}$ is input of Algorithms 1 and 2. Could you remove that input and give the procedure of obtaining $g_k$ in the algorithm body part?**

**A.**
The reviewer is correct: the function value of the $k$-th iteration of the Nesterov accelerated gradient method on $g$ is denoted by $g_k$. However, this is not the only possible choice. In fact, any $\\{g_k\\}$ satisfying Eq. (5) can also be used as an input of our algorithms.

As you mentioned, this input can be removed. Instead, we could obtain the $g_k$ at the beginning of the $k$-th iteration in our algorithm body part and use it to construct our approximated feasible set $\mathcal{X}_{k}$. We will add an instantiation of our algorithm with Nesterov accelerated gradient iterates to the paper, which will be included in the appendix.

To clarify, there are multiple choices for the sequence $g_k$. For instance, one could consider a constant sequence where $g_k$ is set to the function value of the last iterate of AGD for all $k$. This choice has the benefit of shaving a logarithmic factor from the convergence rate, as discussed in Remark 4.2.
Thank you for your response and advocating for the acceptance of our paper!
Hello, authors.

For Q2, does $g_k$ denote the function value from the k-th iteration of the Nesterov's gradient method on $g$? 

{$g_k$} is input of Algorithms 1 and 2. Could you remove that input and give the procedure of obtaining $g_k$ in the algorithm body part? 

Reviewer fv8w
Dear authors,

Thank you for your clear explanation! I acknowledge reading your response and am happy to maintain my score and advocate for acceptance of your paper. 

Best wishes!