First-Order Methods for Linearly Constrained Bilevel Optimization
Authors: Guy Kornowski
Swati Padmanabhan
Kai Wang
Zhe Zhang
Suvrit Sra
Venue: NeurIPS 2024 poster (2024)
Keywords: Constrained bilevel optimization
first-order methods
nonsmooth nonconvex optimization
bilevel optimization
nonconvex optimization
nonsmooth optimization
Goldstein stationarity
Primary area: optimization

Abstract: Algorithms for bilevel optimization often encounter Hessian computations, which are prohibitive in high dimensions. While recent works offer first-order methods for unconstrained bilevel problems, the constrained setting remains relatively underexplored. We present  first-order linearly constrained optimization methods with finite-time hypergradient stationarity guarantees. For linear equality constraints, we attain $\epsilon$-stationarity in $\widetilde{O}(\epsilon^{-2})$ gradient oracle calls, which is nearly-optimal. 
For linear inequality constraints, we attain $(\delta,\epsilon)$-Goldstein stationarity in $\widetilde{O}(d{\delta^{-1} \epsilon^{-3}})$ gradient oracle calls, where $d$ is the upper-level dimension. 
Finally, we obtain for the linear inequality setting dimension-free rates of $\widetilde{O}({\delta^{-1} \epsilon^{-4}})$ oracle complexity under the additional assumption of oracle access to the optimal dual variable. Along the way, we develop new nonsmooth nonconvex optimization methods with inexact oracles. Our numerical experiments verify these guarantees.

First-Order Methods for Linearly Constrained Bilevel Optimization
Guy Kornowskit
Swati Padmanabhan'
Kai Wang
Jimmy Zhang
Suvrit Sra
Abstract
Algorithms for bilevel optimization often encounter Hessian computations, which are prohibitive in high dimensions. While recent works offer first-order methods for unconstrained bilevel problems, the constrained setting remains relatively un- derexplored. We present first-order linearly constrained optimization methods with finite-time hypergradient stationarity guarantees. For linear equality constraints, we coterl--ppimal.... For linear inequality constraints, we attain (6, e)GGldstti stationarity O(d8-1= gradient oracle calls, where d is the upper-level dimension. Finally, obtain for the linear inequality setting dimension-free rates of 0(8-te-4) oracle complex- ity under the additional assumption of oracle access to the optimal dual variable. Along the way, we develop new nonsmooth nonconvex optimization methods with inexact oracles. Our numerical experiments verify these guarantees.
attain e-stationarity in Ö(E ?) gradient oracle calls, which
1 Introduction
Bilevel optimization [1-4], an important problem in optimization, is defined as follows:
minimize,rex F(x) = [xx y (x)) subject to (x) E arg minyeS(w) g(x, v).
(1.1)
Here, the value of the upper-level problem at any point depends on the solution of the lower- level problem. This framework has recently found numerous applications in meta-learning [5-8], hyperparameter optimization [9-11], and reinforcement learning [12-15]. Its growing importance has spurred increasing efforts towards designing computationally efficient algorithms for it.
As demonstrated by [16], key computational step in algorithms for bilevel optimization is estimating dy" (x)/dx, the gradient of the lower-level solution. This gradient estimation problem has been extensively studied in differentiable optimization [17, 18] by applying the implicit function theorem to the KKT system of the given problem [19-24]. However, this technique typically entails computing (or estimating) second-order derivatives, which can be prohibitive in high dimensions [25-27].
Recently, [28] made big leap forward towards addressing this computational bottleneck. Restricting themselves to the class of unconstrained bilevel optimization, they proposed fully first-order method with finite- time stationarity guarantees. While a remarkable breakthrough, [28] does not directly extend to the important setting of constrained bilevel optimization. This motivates the question:
Can we develop a first-order algorithm for constrained bilevel optimization?
Full version: https//arrivvon//ab/4444....22 GK, SP, KW, 77. contributed equally; authors ordered
alhaabttcaall..
Weizmann Institute of Science. gu.. www.kkowkkkkweeeiiaaaaa...
Massachusetts Institute of Technology- paut@mit.ed
5 Georgia Institute of Technology. kwang6928gatech. edu
Purdue University. zhan51 2han5111@purdus 11purruue. edu
Massachusetts Institute Technology. suvrit@mit.co
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Besides being natural from the viewpoint of complexity theory, this question is well gllludddddd in applications such as mechanism design [29, 301, resource allocation [31-34], and
under uncertainty [20, 35, 36]. Our primary contribution is affirrmative answer to the highlighted question for bilevel programs with linear constraints, an important problem class often arising in adversarial training, decentralized meta learning, and sensor networks (see [37]). While there have been some other recent works [37-39] on this problem, our work is first-order (as opposed to [37]) and offers, in our view, stronger guarantee on stationarity (compared to [38, 39]) cf. Section 1.2.
1.1 Our contributions
We provide first-order algorithms (with associated finite-time convergence guarantees) for linearly constrained bilevel programs (Problem 1.1). By "first-order", we mean that we use only zeroth and first-order oracle access to f and g. Our assumptions for each of our contributions are in Section 2.1.
(1) Linear equality constraints. As our first contribution, we design first- algorithms for solving Problem 1.1 where the lower-level constraint set S(x) := {y Ar By - b 0} comprises linear equality constraints, and X' a convex compact set. With appropriate regularity assumptions on and g. we show in this case smoothness in of the hyperobjective F. Inspired by ideas from Kwon et al. [40], we use implicit differentiation of the KKT matrix of a slightly perturbed version of the lower-level problem to design first-order approximation to F.. Constructing our first-order approximation entails solving a strongly convex optimization problem on affine constraints, which can be done efficiently. With this inexact gradient oracle in hand, we then run projected gradient descent, which converges in Ō(c²2 iterations for smooth functions.
Theorem 1.1 (Informal: cf. Theorem 3.1). Given Problem 1.1 with linear equality constraints (xx) = {y Ax By- b ===) 0} and X a convex compact set, under regularity assumptions on f and 9 (Assumptions 2.2 and 2.3), there exists an algorithm, which in Ōcc²2) oracle calls to f and g. converges to an e-stationary point of F.
For linear equality constrained bilevel optimization, this is the first first-order result attaining 6- stationarity of F with assumptions solely on the constituent functions f and g and none on F cf. Section 1.2 for a discussion of the results of Khanduri et al. [37] for this setting.
(2) Linear inequality constraints. Next, we provide first-order algorithms for solving Problem 1.1 where the lower-level constraint set S(x) := {y: : Az By S 0} comprises linear inequality constraints, and the upper-level variable is unconstrained.
Our measure of convergence of algorithms in this case is that of (6, c) -ttationnryity [41]: for a Lipschitz function, we say that point is (6. e) -)-stationary if within 8-ball around there exists a convex combination of subgradients of the function with norm at most e (cf. Definition 2.1).
To motivate this notion of convergence, we note that the hyperobjective F (in Problem 1.1) as a function of x could be nonsmooth and nonconvex (and Lipschitz, as we later prove). Minimizing such a function in general is known to be intractable [42], necessitating local notions of stationarity. Indeed, not only it impossible to attain e-stationarity in finite time [43], even getting near an approximate stationary point of an arbitrary Lipschitz function is impossible unless the number of queries is exponential in the dimension [44]. Consequently, for this function class, (ò, -)stttiionyrity has recently emerged [43] to be a natural and algorithmically tractable notion of stationarity. We give the following guarantee under regularity assumptions on f and g.
Theorem 1.2 (Informal: Theorem 4.1). Consider Problem 1.1 with linear inequality constraints
S(x) == {y: Ax - By- - < 0}. Under mild assumptions on f and g (Assumption 2.2) and the lower-level primal solution y" (Assumption 2.4), there exists an algorithm, which converges to (8, (dttttstaai point of F in Ö(d8-1e oracle calls to I and g, where d is the upper-level variable dimension.
To the best of our knowledge, this is the first result to offer a first-order finite-time stationarity guarantee on the hyperobjective for linear inequality constrained bilevel optimization (cf. Section 1.2 for a discussion of related work [37-39]). We obtain our guarantee in Theorem 1.2 by first invoking a result by Zhang and Lan [45] to obtain inexact hyperobjective values of F using only Õ(1) oracle calls to I and g. We also show (Lemma 4.3) that this hyperobjective F is Lipschitz. We then employ our inexact zeroth-order oracle for in Algorithm designed to minimize Lipschitz, nonsmooth nonconvex functions (in particular, F), with the following convergence guarantee.

---

Theorem 1.3 (see Theorem C.I), Given L-Lipschitz F RR + R and [F() F(.) S there exists an algorithm, which, in ((dā-1c-3) calls to F(.), outputs n with Eldist Og Fx= S 2c.
While such algorithms using exact zeroth-order access already exist [46], extending them to the inexact gradient setting is non-trivial; we leverage recent ideas connecting online learning to nonsmooth nonconvex optimization by Cutkosky, Mehta, and Orabona [47] (cf. Section 4).
(3) Linear inequality under assumptions on dual variable access. For the inequality setting (i.e., Problem 1.1 with the lower-level constraint set S(z) == {y: Ax - By - b < 0}), we obtain dimension-free rates under an additional assumption (Assumption 2.5) on oracle access to the optimal dual variable X of the lower-level problem. We are not aware of a method to obtain this dual variable in first-order fashion (though in practice, highly accurate approximations to X are readily available), hence the need for imposing this assumption. We believe that removing this assumption and obtaining dimension-free first-order rates in this setting would be an important direction for future work. Our guarantee for this setting is summarized below.
Theorem 1.4 (Informal; Theorem 4.4 combined with Theorem 5.3). Consider Problem 1.1 with {y Ax By - S 0} and unconstrained upper-level
linear inequality constraints S(x) variable. Under mild regularity assumptions on f and (Assumption 2.2), on y² (Assumption 2.4), and assuming oracle access to the optimal dual variable X (Assumption 2.5), there exists an algorithm, which ((8-1(-A) oracle calls to f and converges to a (6, c)-staiionary point for F.
We obtain this result by first reformulating Problem 4.1 via the penalty method and constructing an inexact gradient oracle for the hyperobjective F (cf. Section 5). We then employ this inexact gradient oracle within an algorithm (Algorithm 3) designed to minimize Lipschitz. nonsmooth nonconvex functions (in particular, F), with the following convergence guarantee.
Theorem 1.5 (Informal; Theorem 4.4). Given Lipschitz F' Rd + R and ([F
S there exists an algorithm that, in T = 06--1e-)) calls to VF, outputs a (ò, 2e)-stationary point of F.
Our Algorithm 3 is essentially a "first-order" version of Algorithm 2. Similar to Algorithm 2, despite the existence of algorithms with these guarantees with access to exact gradients [48], their extensions to the inexact gradient setting are not trivial and also make use of the new framework of Cutkosky, Mehta, and Orabona [47]. We believe our analysis for this general task can be of independent interest to the broader optimization community. Lastly, we also use a more impleneenattion-friendde variant of Algorithm 3 (with slightly worse theoretical guarantees) in numerical experiments.
1.2 Related work
The vast body of work on asymptotic results for bilevel programming, starting with classical works such as Anandalingam and White [49], Ishizuka and Aiyoshi [50], White and Anandalingam [51],
Vicente, Savard, and Júdice [52], Zhu [53]. and Ye and Zhu [54]. typically fall into two categories:
those based on approximate implicit differentiation: Amos and Kolter [17]. Agrawal et al. [18],
Domke [55], Pedregosa [56], Gould et al. [57], Liao et al. [58]. Grazzi et al. [59], and Lorraine, Vicol, and Duvenaud [60] and those via iterative differentiation: Franceschi et al. [9], Shaban et al. [10], Domke [55], Grazzi et al. [59], Maclaurin, Duvenaud, and Adams [61], and Franceschi et al. [62]. Another recent line of work in this category includes Khanduri et al. [37], Liu et al. [63], Ye et al. [64], and Gao et al. [65], which use various smoothing techniques.
The first non-asymptotic result for bilevel programming was provided by Ghadimi and Wang [16], which was followed by a flurry of work: for example, algorithms that are single-loop stochastic: Chen, Sun, and Yin [66], Chen et al. [67]. and Hong et al. [68], projection free: Akhtar et al. [69], Jiang al. [70], Abolfazli et al. [71], and Cao et al. [72], use variance-reduucionn and momentum: Khanduri et al. [73], Guo et al. [74], Yang, Ji, and Liang [75], and Dagréou et al. [76], those for
single-variable bilevel programs: Jiang et al. [70]. Sabach and Shtemn [77], Amini and Yousefian [78,
79], and Merchay and Sabach [80], and for bilevel programs with special constraints: Khanduri et al. [37], Abolfazli al. [71], Tsaknakis. Khanduri, and Hong [81], and Xu and Zhu [82].
The most direct predecessors of our work are those by Khanduri et al. [37], Yao et al. [38], Lu and Mei [39], Kwon et al. [40], and Liu et al. [63]. As alluded to earlier, Liu et al. [28] recently made a significant contribution by providing for bilevel programming a fully first-order algorithm with timte-time stationarity guarantees. This was extended to the stochastic setting by Kwon et al. [40]
3

---

(which we build upon), simplified and improved by Chen, Ma, and Zhang [83], and extended to the constrained setting by Khanduri et al. [37]. Yao al. [38], and Lu and Mei [39].
The works of Yao et al. [38] and Lu and Mei [39] study the more general problem of bilevel programming with general convex constraints. However, they use KKT stationarity proxy to the hypergradient stationarity. Our Theorem 1.4 is restricted to linear inequality constraints, we provide stationarity guarantees directly in terms of the objective of interest. Moreover, Yao al. [38] assumes joint convexity of the lower-level constraints in upper and lower variables to allow for efficient projections, while we require convexity only in the lower-level variable.
The current best result for the linearly constrained setting is that of Khanduri et al. [37]. However, this work requires Hessian computations (and is therefore not fully first-order). Moreover, Khanduri et al. [37] imposes strong regularity assumptions on the hyperobjective F, which are, in general, impossible to verify. In contrast, Theorem 1.1 imposes assumptions solely on the constituent functions f and g- none directly on F, thus making substantial progress on these two fronts.
Preliminaries
We follow standard notation (see Appendix A), with only the following crucial definition stated here. Definition 2.1. Consider locally Lipschitz function f IRd - R. a point x E Rd, and parameter 5 > O. The Goldstein subdifferential [41] of f at x is the set 0zf(x) ==
y f(y)), where (x) = conv (lima-sse [((x)) Ty, - 2. In E domm (V} } is the Clarke subdifferential [84] of I and B3xx)) denotes the Euclidean ball of radius ö around x. A point is called (ò, )-stationaay if (0, 0af(a)) S e, where dist(r, 5) == infyes 1|x ja--yll
2.1 Assumptions
We consider Problem 1.1 with linear equality constraints (Section 3) under Assumptions 2.2 and 2.3 and linear inequality constraints (Sections 4 and 5) under Assumptions 2.2, 2.4 and 2.5. We assume the upper-level (UL) variable x E Rd,, lower-level (LL) variable E Rd,, and A E Rd, xd. Assumption 2.2. For Problem 1.1, we assume the following for both settings we study:
(i) Upper-level: The objective is Cy-smooth and L--Liscchitz continuous in (x. (ii) Lower-level: The objective g is Cg-smooth. Fixing any x E X, g(x,-) is (4g Pg-strongly convex. (iii) We assume that the linear independence constraint qualification (LICQ) condition holds for the LL problem at every x and y. i.e., the constraint h(I,y) == Ax By has a full row rank B. Assumption 2.3, For Problem 3.1 (with linear equality constraints), we additionally assume that the set X is convex and compact, and that the objective g is Sy Sy-Hessian smooth, that is, V²g(z,)) y) V g 7)ll S Sy [1( y) (ž. F)l Vz, E X, and y. ÿ RRd.
Assumption 2.4. For Problem 4.1 (with linear inequality constraints), we additionally assume that y is Lip-schht in x, where y² is the LL primal solution y" (x), (T(,,)) where h(x, u) = Ax By- - b.
arg max, minzz0 g(, u)
Assumption 2.5. We provide additional results for Problem 4.1 under additional stronger assumptions stated here: Denote the LL primal and dual solution y² (x), (x) arg max, ming20 g(2, y) + +3Th(x,y)) h)) where h(x,y) = AA By By-By-b b; then, we assume exact access to X* and that [X*())] R.
Assumptions 2.2(1) and 2.2( are standard in bilevel optimization. Assumption 2.2(1ii is the same as the complete recourse assumption in stochastic programming [85], that is, the LL problem is feasible y for every E Rd=, Assumption 2.3 is used only in the equality case and guarantees smoothness of F. Assumption 2.4 used the inequality case and implies Lipschitzness of F. We need the stronger assumption in Assumption 2.5 for our dimension-free result for the linear inequality case.
3 Lower-level problem with linear equality constraint
We first obtain improved results for the setting of bilevel programs with linear equality constraints in the lower-level problem. Our formal problem statement is:
minimizezex F(x)= == f(z y (x)) subject to y" (I)) E arg 0
(3.1)

---

where f. h(x.y) == By-By and X' satisfy Assumptions 2.2 and 2.3, The previous best result on Problem 3.1 providing finite-time e-stationarity guarantees, by Khanduri et al. [37], required certain regularity assumptions on F as well as Hessian computations. In contrast, our finite-time guarantees require assumptions only on I and 9, not on F; indeed, in our work, these desirable prop- erties of F are naturally implied by our analysis. Specifically, our key insight is that the hypergradient
Vyf(r,y" y²) for Problem 3.1 is Lipschitz-contimuous and admits an easily computable - yet highly accurate - finite-difference approximation. Therefore, O(E-2) it- erations of gradient descent on F with this finiteddifference gradient proxy yield an e-stationary point.
VF(2) = vz, y²)+
ddy"(x)) (ar) dir
Specifically, for any fixed X, our proposed inite-difference gradient proxy approximating the (d)
non-trivial-to- co-opuut component
V Vyf v*) of the hypergradient is given by
dx
Uz Valg(a, v3) (A3,
Vzlg(a, v²) + (X,,,(x,))
(3.2)
where (vz: AB) are the primal and dual solutions to the perturbed lower-level problem:
ye == arg (in)))(a g(2,y) + 55 v)-
(3.3)
We show in Lemma 3.2 that v in (3.2) approximates (x) (a, v²) up an -dd)-additive
dar
error, implying the gradient oracle construction outlined in the pseudocode presented in Algorithm 1.
Our full implementable algorithm for solving Problem 3.1 is displayed in Algorithm 5.
Algorithm 1 Inexact Gradient Oracle for Bilevel Program with Linear Equality Constraint
1: Input: Current accuracy e, perturbation 5 e2.
2: Compute y" (as in Problem 3.1) and corresponding optimal dual A (as in (B.1))
3: Compute yg (as in (3.3)) and and corresponding optimal dual \3 (as in (B.7))
4: Compute Vy as in (3.2)
Approximates (dy" (s)/da) T (x,(x,")
5:
Output: VF = U22 + V vz)
Notice that the diffe-eiifereene term in (3.2) avoids differentiating through the implicit function y" Instead, all we need to evaluate it are the values of (y", '",,"""" yg: Aラ) (and gradients of g and h). Since (y", X*) are solutions to smooth strongly convex linearly constrained problem, they can be approximated at a linear rate. Similarly, since the approximation error in (3.2) is proportional to 5 (cf. Lemma 3.2), small enough 8 in the perturbed objective 9 5f in (3.3) ensures that it is dominated by the strongly convex and smooth g. whereby accurate approximates to (y/ Az) can also be readily obtained. Putting it all together, the proposed finite-difference hypergradient proxy in (3.2) is efficiently computable, yielding the following guarantee.
Theorem 3.1. Consider Problem 3.1 I under Assumption 2.2, and let k = Cg/ be the condition number of g. Then Algorithm 5 finds an e-stationary point (in terms gradient mapping, see (B.14)) after T O(Cp(F(z))) inf F) 2) oracle calls to f and g. where Cp == 2 + Cs S,, + ||Al)) is the smoothness constant of the hyperobjective F.
We now sketch the proof of Theorem 3.1. The complete proofs may be found in Appendix B.
3.1 Main technical ideas
We briefly outline the two key technical building blocks alluded to above, that together give us Theorem 3.1: the approximation guarantee of our finite-different gradient proxy ((3.2)) and the smoothness of hyperobjective F (for Problem 3.1). The starting point for both these results is the following simple observation obtained by implicitly differentiating, with respect to x, the KKT system associated with y² = arg min ((x, v) and optimal dual variable X":
dg' (a)
V Ving(,, vx)
V Vyh(r, "2)
v2 Vmnl(1,
da (z) =
Vyh(a,y)*
v,h(x,y")
(3.4)
5

---

The invertibility of the matrix in the preceding equation is proved in Corollary B.3: essentially, this invertibilityy implied by strong convexity of g and v,h(x,y") B having full row rank. This in conjunction with the compactness of X' implies that the inverse of the matrix is bounded by some constant Ch (cf. Corollary B.3 for details). Our hypergradient approximation guarantee follows: Lemma 3.2. For Problem 3. under Assumption 2.2, with 12 in (3.2), the following holds:
T (vf(z.))) )
(x) du
SO(C))).
U22
Proof sketch; see Appendix B. The main idea is that the two terms being compared are essentially the same by the implicit function theorem. First, use the expression for dy"(x) (x) from (3.4):
dy (ar) (a) dx
- V V,h( v
Vah(a,
Vyf Vyf(z,v")
0
We now examine limg->0 Ya (xlotz.w))+AA) MIV, (+((" Aha..y "
For simplicity of exposition, we instead consider which, by the fundamental theorem error. Note that this expression is:
of calculus and Assumption 2.3, equals up to an
Eyz(( y*) dy d6
dip d6
Veh(r,y")
(3.5)
Since y is minimizes a strongly convex function over a linear equality constraint (3.3), the reasoning that yields (3.4) also gives the following, which, when combined with (3.5), finishes the proof:
dy (a)
V Vun((yy) V)((
Vyh(x,y")
V vvf(z,)))
(3.6)
dA
0
db
6=
Having shown the construction of the hypergradient approximation, we now state smoothness of the hyperobjective F (proof in Appendix B), crucial to getting our claimed rate.
Lemma 3.3. The solution yf (as defined in Problem 3) is O(CH (C, + -ippsiii continuous and (C Sg (Cg + [ )-mooth as a function of x. Thus the hyper-objective F is gradient- Lipschitz with a smoothness constant of CF == O{Ls + C2 C2 S, + ||A])))
Nonsmooth nonconvex optimization with inexact oracle
We now shift gears from the case of linear equality constraints to that of linear inequality constraints. Specifically, defining h(., y) = Ax By - b, the problem we now consider is
minimize, F(x) = f(x, y (x:) subject y (x)) E arg git. ((x,)) y)-
(4.1)
As noted earlier, for this larger problem class, the hyperobjective can be nonsmooth nonconvex, necessitating our measure of convergence to be the now popular notion of Goldstein stationarity [43].
Our first algorithm for solving Problem 4. presented in Algorithm 2, with its convergence guarantee in Theorem 4.1. I. At a high level, this algorithm first obtains access to an inexact zeroth-order oracle to F (we shortly explain how this is done) and uses this oracle to construct a (biased) gradient estimate of F. It then uses this gradient estimate to update the iterates with a rule motivated by recent works reducing nonconvex optimization online optimization [47]. We explain this in Section 4.1.
Cot be the condition number of g. Then combining the procedure for Lemma 4.2 with Algorithm run with vepp" and 1) = θ (1 outputs out such that E E0,ist(O, O₂ (x s t with T oracle calls to f and 9, where:
Theorem 4.1. Consider Problem 4. under Assumptions 2.2 and 2.4. Let
p= = min {8 F(za)-inf F.)
p=20"
2> L,,L, ; V 8 8-p, = 1,13
(vid.((((a)) inf F).
dr d.
1) log(L,/a))
17 + +
T ==
863
82
(F(zo) inf F)2

---

Algorithm 2 Nonsmooth Nonconvex Algorithm with Inexact Zero-Order oracle
Input: Initialization zо E R clipping parameter D >> step size rj > smoothing parameter
P > O, accuracy parameter v > iteration budget T e inexact zero-order oracle F IR R.
2: Initialize: A
3: for 1- 1,..., T do
4: Sample
Un, 1), wn Unil(Sa-1) 5: It = 11 A,, 2t = xt-1 + 8,
6:
Tr 3p
d (z + pw)) - F(zz pw))
7:
D++1 = c (A. 79t)
clipp(>) min(1, ||] }
8: M 1 K |
T
M
9: for 1 ..... K do
M
10:
Th 2m=1 2(k 1k-1))m-m
11: Sample x zot ~ Unif FI....,FKI!
12: Output: oou
Algorithm 2 is a variant of gradient descent with momentum and clipping, with Gr the inexact gradient, A, clipped accumulated gradient (hence accounts for past gradients, which serve as a momentum), and the clipping ensuring that consecutive iterates of the algorithm reside within 5-ball of each other. While similar algorithms have appeared in prior work on nonsmooth nonconvex optimization (e.g. [47]), none of them account for inexactness in the gradient, crucial in our setting.
4.1 Nonsmooth nonconvex optimization with inexact zeroth-order oracle
We can obtain inexact zeroth-order oracle access F because (as formalized in Lemma 4.2) despite potential nonsmoothness and nonconvexity of F in Problem 4.1, estimating its value F(z) at any point x amounts to solving a single smooth and strongly convex optimization problem, which can be done can be done in (() oracle calls to f and g by appealing to a result by Zhang and Lan [45].
Lemma 4.2 (Proof in Appendix C.I). Given any using O (V Mg log(L, / /a)) first-order oracle calls to f and g.
return F(x) such that ((x))=((x)) S
Having computed an inexact value of the hyperobjective F, we now show how to use it to develop an algorithm for solving Problem 4.1. To this end, we first note that F, despite being possibly nonsmooth and nonconvex, is Lipschitz and hence amenable to the use of recent algorithmic developments in nonsmooth nonconvex optimization pertaining Goldstein stationarity.
Lemma 4.3. Under Assumption 2.2 and 2.5, F in Problem 4.1 is L in r.
With this guarantee on the Lipschitzness of F, we prove Theorem C.1 for attaining Goldstein stationarity using the inexact zeroth-order oracle of a Lipschitz. function. Our proof of Theorem C.1 crucially uses the recent online-to-none no-nccove- framework of Cutkosky, Mehta, and Orabona [47]. Combining Lemma 4.2 and Theorem C.1 then immediately implies Theorem 4.1.
4.2 Nonsmooth nonconvex optimization with inexact gradient oracle
In Section 5, we provide way to generate approximate gradients of F. Here, present algorithm that attains Goldstein stationarity of Problem 4.1 using this inexact gradient oracle. While there has been long line of recent work on algorithms for nonsmooth nonconvex optimization with convergence to Goldstein stationarity [43, 48, 86-88J, these results necessarily require exact gradients. This brittleness any егтоr in gradients renders them ineffective our setting, where our computed (hyper)gradient necessarily suffers from an additive error. While inexact oracles are known be effective for smooth convex objectives [89], utilizing inexact gradients in the nonsmooth nonconvex regime presents nontrivial challenge. Indeed, without any local bound on gradient variation due to smoothness, or convexity that ensures that gradients are everywhere correlated with the direction pointing at the minimum, it is not clear priori how control the accumulating price of inexactness throughout the run of an algorithm. To derive such results, we use the recently proposed connection between online learning and nonsmooth nonconvex optimization by Cutkosky, Mchta,

---

and Orabona [47]. By controlling the accumulated error suffered by online gradient descent for linear losses (cf. Lemma C.3), we derive guarantees for our setting of interest, providing Lipschitz optimization algorithms that converge Goldstein stationary points even with inexact gradients.
This algorithm matches the best known complexity in first-order nonsmooth nonconvex optimization [43, 47, 48], merely replacing the convergence to (6, - point by (6, e + -sstaionnar, where o is the inexactness of the gradient oracle.
Algorithm 3 Nonsmooth Nonconvex Algorithm with Inexact Gradient Oracle
1: Input: Initialization 2g RR, clipping parameter D > 0, step size > O, accuracy parameter > 0, iteration budget T E N, inexact gradient oracle FF F + R
2: Initialize: A
3: for / 1,..., do
4: Sample
Unif = Ft-1 + 8
5: It = T4-1 A.,
6:
9: (z+))
7:
A++1 = clip (A, 199)
> clipp(2) = min(1,
D
8:
M 1 K
T
M
9: for L..... K
do
10: IK M
Σm 1= -(K-1)MM-
Sample gut
Unif [T1...., FK}
12: Output: ru
Theorem 4.4. Suppose F F + R is L- L-Lipschitz and that (VF(-)- VF(.)) S a. Then running
Algorithm 3 with D O 6c2 ); 0 ( ), outputs point you such that Eldist(() (0, (x s
e c a, with T = 0 (F( -inf inf F)L?
calls to FF()).
5c3
We defer the proof of Theorem 4.4 to Appendix C.I. Plugging the complexity of computing inexact gradients, as given by Theorem 5.3, into the result above, we immediately obtain convergence to (6, (..e))sstee --statioonay point of Problem 1.1 with ((6-1e-1) gradient calls overall.
Implemeentafon-frieedlly algorithm. While Algorithm 3 matches the best-known results in nons- mooth nonconvex optimization, could be impractical due to several byperparameters which need tuning. Arguably, a more natural application of the hypergradient estimates would be simply plugging them into gradient descent, which requires tuning only the stepsize. Since F is neither smooth nor convex, perturbations
required guarantee differentiability along the trajectory. We therefore complement Theorem 4.4 by analyzing perturbed (inexact) gradient descent in the nonsmooth noncon- vex setting (Algorithm 7) and state its theoretical guarantee in Theorem C.4. Despite its suboptimal worst-case theoretical guarantees, we find this algorithm easier to implement in practice.
5 Inequality constraints: constructing the inexact gradient oracle
Computing stationary point of F of Problem 4.1 via any first-order method would require:
VF(x) Vzl(x,v")
(x)
(z,
(5.1)
dr.
for which the key challenge lies in computing dy' (dx) This requires differentiating through an argmin operator, which typically requires second-order derivatives. Instead, here we differentiate (using the implicit function theorem) through the KKT conditions describing y (I)) and get:
2 V + V 9y
Vyhi 0
dg (x)
V2 y + (X*) diag (ogg(A;VV) V
ya
(5.2)
diag ({;)))))))))
V
di
where given æ, we assume efficient access to the optimal dual solution X (x: the L.I. problem in Problem 4.1. In (5.2), use I (i e [da] ha(a,v) v) 0, 0} denote the set of active
8

---

constraints with non-zero dual solution, with hg == [h,]sez and X2 = Dilkez being the constraints and dual variables, respectively, corresponding I.
Observe that as currently stated, (5.2) leads to second-order computation of dy (f)/dr. In the rest of the section, we provide fully first-order approximate hypergradient oracle by constructing equivalent reformulation of Problem 4.1 using penalty function.
5.1 Reformulation via the penalty method
We begin by reformulating Problem 4.1 into single level constrained optimization problem:
[g v) + (X*xz) ((()))))())))))))))( S (x) (h(x, y) S
minimizez.y y (x. y) subject to
(5.3)
where 9* (a) millyh(ar s ( y) g( y (x)) and X (x) is the optimal dual solution. The equivalence of this reformulation to Problem 4.1 is spelled out in Appendix D. From (5.3), we define the following penalty function, crucial to our analysis:
Cx,,00 [xx, v) + an (g(2,v) (A7) ((, n" (x)) + |
(5.4)
where = [01,02] 02) 2 0 are the penalty parameters. Notably, we can compute its derivative with respect to of (5.4) in a fully first-order fashion by the following expression:
a
= (z. y) +on
y) T by (z, y).
To give some intuition for our choice of penalties in (5.4), we note that the two constraints in (5.3)
behave quite differently. The first constraint g(r, y) + >")x) >>())>>(T;;) y) S g"(x)) is one-sided, i.e., can only be violated or met, and hence just needs penalty parameter 01 to weight the "violation". As to the second constraint h(x, y) & O, it can be arbitrary. To allow for such a "two-sided" constraint, we penalize only the active constraints I, i.e., we use |/z I|
to penalize deviation.
Next, we define the optimal solutions to the penalty function optimization by:
yx (x) == arg min, Lx- axx-,aaf (z, y).
(5.5)
We now show that this minimizer is close the optimal solution of the LL problem, while suffering only a small constraint violation.
Lemma 5.1. Given any x, the corresponding dual solution X (x), primal solution (x) of the lower optimization problem in Problem 4.1, and vx- (x) as in (5.5), satisfy:
( (z) y" (x)]] s 0(aT)) and || Vs- (=)) - O(aa 1/2 2²12/
(5.6)
The proof of Lemma 5.1 is based the Lipschitzness of f and strong convexity of g for sufficiently large a1. The aforementioned constraint violation bound on 1r(21, y) is later used in Lemma 5.2 to bound the inexactness of our proposed gradient oracle.
5.2
Main result: approximating the hypergradient
The main export of this section is the following bound on the approximation of the hypergradient. This, together with the bounds in Lemma 5.1, validate our use of the penalty function in (5.4).
Lemma 5.2. Consider F as in Problem 4.1, L as in (5.4), fixed x, and Vi+ as in (5.5). Then under Assumptions 2.2 and 2.5, we have:
VVF()) VaCx- (x, .a)l 0(aT') O(a 1a111/220))
1/2 -/ ,1/3 0 - -1/3) O(a 3/2 1/2
02
The proof can found in Appendix G. With this hypergradient approximation guarantee, we design Algorithm 4 to compute an inexact gradient oracle for the hyperobjective F.
Theorem 5.3. Given any accuracy parameter o > 0, Algorithm 4 outputs F.F(x) such that [[VF(z) VF(x) & a within ((a=)) gradient oracle evaluations.
The full proof of this result may be found in Appendix H.

---

Algorithm 4 Inexact Gradient Oracle for General Inequality Constraints
1: Input: Upper level variable æ; accuracy a, penalty parameters on a 02 a-
2: Compute y", X", and active constraints
the constrained LL problem Man ((2,
3: Define penalty function Lx- (2, y) by (5.4)
4: Compute the minimizer Vλ-.or arg miny Lx- a (2. y) (as in (5.5)).
5: Output: VF = Vehxx VX
cxppybyer
F2CBA 07=0.0001
cxxpbbyer
1 oap
(Algorithm
Gradieen error
Optimalty gap
F2CBA gi=0.001 001
F2CBA gf=0.01
F2CBA
F2CBA a²-0.1
F2CBA g1=1.0
Iteration
dimrension
(a) Convergence and gradient ror of Fully First-order Constrained Bilevel Algorithm (F2CBA) com- pared to ovxpylayer [18].
(b) Convergence analysis with vary-
(c) Computation
per gradient step of varying problem size dy. We vary dy from 100 to 1000 to mea- sure the computation cost.
ing gradient inexactness mea-
sure the tradeoff' of accuracy and
convergence.
Figure 1: We Algorithm 3 using Algorithm the bilevel optimization in the toy example in Problem L.1 with d 100, d, 200, Tecuss d,/5, and accuracy a 0.1. Figure 2a, Figure 2b, Figure vary of iterations, gradient exactness a, and dy respectively, to compare the performance under different settings.
Experiments
We generate instances of the following constrained bilevel optimization problem:
1 ming c_ "" + 0.01 | 0.01 || y" = arg min www...ggg...ws.. /リ Qy + Py, (6.1)
where (<x y) Ay is dii linear constraint. The PSD matrix Q E Rd, c 12,, P Rd=xd, and constraints A E Rd, xdy, E RR,, are randomly generated from normal distributions (cf. Appendix K). We compare Algorithm with a non-fully first-order method using cvxpyLayer [18]. Both algorithms use Adam [90] to control the learning rate, and are averaged over 10 random seeds.
Figure 2a shows that both the algorithms converge to the same optimal solution at the same rate. Simultaneously, the colorful bars represent the gradient differences between two meth- ods, showing the inexactness of our gradients. Figure 2b additionally varies this inexactness to demonstrate its impact on convergence with standard deviation plotted. Figure 2c com- pares the computation costs for different lower-level problem sizes. Our fully first-order method significantly outperforms, in computation cost, the non-fully first-order method im- plemented using differentiable optimization method. The implementation can be found in https://gi //ghbub../ttt//g./// www/ wwwguakaicconsteaaaeeeaaaoeeeeee wtw.cnatrraaaeeeeeeeeeeeeeeeeeee bioeelloppiiiiiitttiiii
7 Limitations and future directions
One limitation to our approach is that the inexact gradient oracle we constructed in Section requires access to the exact dual multiplier X*. For a first-order algorithm, the closest proxy could get to this would be a highly accurate approximation (which could be computed up to e emro in (log(1/e)) gradient oracle evaluations). Removing this "exact dual access" assumption (Assumption 2.5) would be an important result.
Another important direction for future work would be to extend the hypergradient stationarity guarantee of Theorem 1.4 to bilevel programs with general convex constraints. To this end, we conjecture that the use of a primal-only gradient approximation oracle could be potentially effective.
Finally, our current rate of Ō(5-1e-1) oracle calls for reaching (ō, -Gooddstein stationarity is not necessarily inherent to the problem; indeed, might be the case that an alternate approach could improve it to the best known rate of (0--1e-3) for nonsmooth nonconvex optimization.
10

---

Acknowledgments
GK is supported by an Azrieli Foundation graduate fellowship. KW is supported by Schmidt Sciences AI2050 Fellowship and NSF IIS-240324.. SS acknowledges generous support from the Alexander von Humboldt Foundation. SP is supported by NSF CCF-21 12665 (TILOS AI Research Institute) and gratefully acknowledges Ali Jadbabaie for many useful discussions. ZZ is supported by NSF FODSI Fellowship.
References
[1] Jerome Bracken and James TT McGill. "Mathematical programs with optimization problems in the constraints". In: Operations research 21.1 (1973), pp. 37-44 (cit. on 1).
[2] Benoît Colson, Patrice Marcotte, and Gilles Savard. "A "An overview of bilevel optimization", In: Annals of operations research 153 (2007), pp. 235-256 (cit. on p. 1).
[3] Jonathan F Bard. Practical bilevel optimization: algorithms and applications. Vol. 30. Springer Science & Business Media, 2013 (cit. on p.
[4] Ankur Sinha, Pekka Malo, and Kalyanmoy Deb. "A review on bilevel optimization: From classical to evolutionary approaches and applications". In: IEEE transactions on evolutionary computation 22.2 (2017), pp. 276-291 (cit. on p. 1).
[5] Jake Snell, Kevin Swersky, and Richard Zemel. "Prototypical networks for few-shot learning".
In: Advances in neural information processing systems 30 (2017) (cit. on p. 1).
[6] Luca Bertinetto, Joao F Henriques, Philip HS Torr, and Andrea Vedaldi. "Meta-leaming with differentiable closed-form solvers". In: ar preprint arXiv:/805.0811 (2018) (cit. on 1). [7] Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. "Meta-learning with implicit gradients". In: Advances in neural information processing systems 32 (2019) (cit. on
p. 1).
[8] Kaiyi Ji, Jason D Lee, Yinghin Liang, and H Vincent Poor. "Convergence of meta-learning with task-specific adaptation over partial parameters". In: Advances Neural Information Processing Systems 33 (2020), pp. 11490-11500 (cit. on p. 1).
[9] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. "Bilevel programming for hyperparameter optimization and meta-learning" In: International conference on machine learning. PMLR. 2018, pp. 1568-1577 (cit. on pp. 1)
[10] Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. "Truncated back- propagation for bilevel optimization" In: The 22nd International Conference on Artificial Intelligence and Statistics. PMLR. 2019, pp. 1723-1732 (cit. on pp. 1,
[11] Matthias Feurer and Frank Hutter. "Hyperparameter optimization" In: Automated machine learning: Methods, systems, challenges (2019), pp. 3-33 (cit. on p. 1).
[12] Vijay Konda and John Tsitsiklis. "Actor-critic algorithms". In: Advances neural information processing systems 12 (1999) (cit. on p. l).
[13] Richard S Sutton and Andrew Barto. Reinforcement learning: An introduction. MIT press,
2018 (cit. on p. 1).
[14] M Hong, H Wai, 7. Wang, and 7. Yang. "A two-timescale framework for bilevel optimization: Complexity analysis and application actor-critic. arXiv e-prints, art". In: arXiv preprint arXiv:2007.08 0.07///55/5/ 70 (2020) (cit. on p. 1).
[15] Haifeng Zhang, Weizhe Chen, Zeren Huang, Minne Li, Yaodong Yang, Weinan Zhang, and Jun Wang. "Bi-level actor-critic for multi-agent coordination". In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. 05. 2020, pp. 7325-7332 (cit. on p. 1).
[16] Saeed Ghadimi and Mengdi Wang. "Approximation methods for bilevel programming". In: arXiv preprint arXiv: arXiv:/802.00 /80.0024622 (2018) (cit. on pp. 1, 24).
[17] Brandon Amos and J Zico Kolter. "Optnet: Differentiable optimization layer in neural networks". " In: International Conference on Machine Learning. PMLR. 2017, pp. 136-145
(cit. pp. 1).
[18] Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and Zico Kolter. "Differentiable convex optimization layers". In: Advances in neural information processing systems 32 (2019) (cit. on pp. 1, 3. 10, 37, 38).

---

[19] Priya Donti, Brandon Amos, and J Zico Kolter. "Task-based end end-to-end model learning in stochastic optimization". In: Advances in neural information processing systems 30 (2017)
(cit. on p. 1).
[20] Bryan Wilder, Bistra Dilkina, and Milind Tambe. "Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization". In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. 01. 2019, pp. 1658-1665 (cit. on pp. 2).
[21] James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, and Bryan Wilder. "End-to-end constrained optimization learning: A survey". In: arXiv preprint arXiv:2103. (2021) (cit. on p. 1).
[22] Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto. "Meta-learning with differentiable convex optimization", In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2019. pp. 10657-10665 (cit. on p. 1). [23] Bo Tang and Elias B Khalil. "Pyepo: A pytorch-based end-to-end predict-then-optimizz library for linear and integer programming". In: arXiv preprini arXiv:2206. 142.3444.. (2022) (cit. on p. 1).
[24] Shaojie Bai, Zico Kolter, and Vladlen Koltun. "Deep equilibrium models", In: Advances in neural information processing systems 32 (2019) (cit. on p. 1).
[25] Akshay Mehra and Jihun Hamm. "Penalty method for inversion frree deep bilevel optimization". In: Asian conference on machine learning. PMLR. 2021, pp. 347-362 (cit. on p. 1).
[26] Kaiyi Ji, Junjie Yang, and Yingbin Liang. "Bilevel optimization: Convergence analysis and enhanced design". In: International conference on machine learning. PMLR. 2021, pp. 4882- 4892 (cit. on p. 1).
[27] Kai Wang. Sanket Shah, Haipeng Chen, Andrew Perrault, Finale Doshi-Velez, and Milind Tambe. "Learning mdps from features: Predict-hhen-optimize for sequential decision making by reinforcement learning". In: Advances in Neural Information Processing Systems 34 (2021), pp. $795-8806 (cit. on p. 1).
[28] Bo Liu, Mao Yc, Stephen Wright, Peter Stone. and Qiang Liu. "Bome! bilevel optimization made easy: A simple first-order approach". In: Advances in neural information processing systems 35 (2022), pp. 17248-17262 (cit. on pp. 3).
[29] Kai Wang, Lily Xu, Andrew Perrault, Michael K Reiter, and Milind Tambe. "Coordinating followers to reach better equilibria: End-to-end gradient descent for stackelberg games". In: Proceedings of the AAAI Conference Artificial Intelligence. Vol. 36. 5, 2022, pp. 5219-5227 (cit. on p. 2).
[30] Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David C Parkes, and Sai S Ravindranath. "Optimal auctions through deep learning". In: Communications of the ACM 64.8 (2021), pp. 109-116 (cit. on p. 2).
[31] Jiuping Xu, Yan Tu, and Ziqiang Zeng. "Bilevel optimization of regional water resources allocation problem under fuzzy random environment". In: Journal of Water Resources Planning and Management 139.3 (2013), pp. 246-264 (cit. on p. 2).
[32] Walter J Gutjahr and Nada Dzubur. "Bi-objective bilevel optimization of distribution center locations considering user equilibria". In: Transportation Research Part E: Logistics and Transportation Review 85 (2016), pp. 1-22 (cit. on p. 2).
[33] Yue Zhang, Oded Berman, Patrice Marcotte, and Vedat Verter. "A bilevel model for preventive healthcare facility network design with congestion". In: IIE Transactions 42. 12 (2010), pp. 865-
880 (cit. on p. 2).
[34] Amir M
Mostafa HajiaghaaiiKeshiee Reza Tavakkoli-Moghaddann and Neale R Smith. "Bi-level programming for home health care supply chain considering outsourcing". In: Journal of Industrial Information Integration 25 (2022), p. 100246 (cit. on p. 2).
[35] Adam N Elmachtoub and Paul Grigas. "Smart "predict, then optimize"'. In: Management Science 68.1 (2022), pp. 9-26 (cit. on p. 2).
[36] Miguel Angel Muñoz, Salvador Pineda, and Juan Miguel Morales. "A bilevel framework for decision-making under uncertainty with contextual information". In: Omega 108 (2022),
p. 102575 (cit. on p. 2).
[37] Prashant Khanduri, Ioannis Tsaknakis, Yihua Zhang, Jia Liu, Sijia Liu, Jiawei Zhang, and Mingyi Hong. "Linearly constrained bilevel optimization: A smoothed implicit gradient approach". In: International Conference on Machine Learning. PMLR 2023, pp. 16291
16325 (cit. on pp. 2-5).
12

---

[38] Wei Yao, Chengming Yu, Shangzhi Zeng, and Jin Zhang. Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithm. 2024. arXiv: 2401. 16164 [cs LG] (cit. on pp. 2-4).
[39] Zhaosong Lu and Sanyou Mei. First-order penalty methods for bilevel optimization. 2024.
arv: 2301 01716 [math. [C] (cit. on pp. 2-4).
[40] Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. "A fully first-order method for stochastic bilevel optimization" In: International Conference on Machine Learning.
PMLR. 2023, pp. 18083-1811 13 (cit. on pp. 2, 3).
[41] AA Goldstein. "Optimization of Lipschitz continuous functions", In: Muthematical Program- ming 13 (1977), pp. 14-22 (cit. on pp. 2, 4).
[42] Arkadij Semenovič Nemirovskij and David Borisovich Yudin. "Problem complexity and
method efficiency in optimization". In: (1983) (cit. on p. 2).
[43] Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaie. "Complexity of finding stationary points of nonconvex nonsmooth functions". In: International Conference
on Machine Learning. PMLR. 2020, pp. 11173-11182 (cit. on pp. 2, 6-8).
[44]
Guy Komnwski and Ohad Shamir. "Oracle complexity in nonsmooth nonconvex optimization". In: Journal of Machine Learning Research 23.314 (2022), pp. 1-44 (cit. on p. 2).
[45] Zhe Zhang and Guanghui Lan. "Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization", In: arXiv preprint arXiv:2210.05807
(2022) (cit. on pp. 2, 7, 24, 34).
[46] Guy Kornowski and Ohad Shamir. "An algorithm with optimal dimension- for zero-order nonsmooth nonconvex stochastic optimization", In: Journal of Machine Learning Research 12.122 (2024), pp. 1-14 (cit. on pp. 3, 25).
[47] Ashok Cutkosky, Harsh Mehta, and Francesco Orabona. In: International Conference on Muchine Learning. PMLR. 2023, pp. 6643-6670 (cit. on pp. 3, 6-8, 26).
[48] Damek Davis, Dmitriy Drusvyatskiy, Yin Tat Lee, Swati Padmanabhan, and Guanghao Ye. "A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions". In: Advances in neural information processing systems 35 (2022), pp. 6692-6703
(cit. on pp. 3. 7, 8).
[49] G Anandalingam and DJ White. "A solution method for the linear static Stackelberg problem using penalty functions". In: IEEE Transactions on automatic control 35.10 (1990), pp. 1170-
1 1773 (cit. p. 3).
[50]
Yo Ishizuka and Eitaro Aiyoshi. "Double penalty method for bilevel optimization problems". In: Annals of Operations Research 34.1 (1992), pp. 73-88 (cit. on p. 3).
[51] Douglas J White and G Anandalingam. "A penalty function approach for solving bi-level linear programs". In: Journal of Global Optimization 3 (1993), pp. 397-419 (cit. on p. 3).
[52] Luis Vicente, Gilles Savard, and Joaquim Júdice. "Descent approaches for quadratic bilevel programming". In: Journal of Optimization theory and applications 81.2 (1994), pp. 379-399
(cit. on p. 3).
[53] DL Zhu. "Optimality conditions for bilevel programming problems". In: Optimizution 33.1 (1995), pp. 9-27 (cit. on p. 3).
[54] JJ Ye and DL Zhu. "Exact penalization and necessary optimality conditions for generalized bilevel programming problems". In: SIAM Journal optimization 7.2 (1997), pp. 481-507 (cit. on p. 3).
[55] Justin Domke. "Generic methods for optimization based modeling". In: Artificial Intelligence and Statistics. PMLR. 2012, pp. 318-326 (cit. on p. 3).
[56]
Fabian Pedregosa. "Hyperparameter optimization with approximate gradient". In: International conference machine learning. PMLR. 2016, pp. 737-746 (cit. on 3).
[57] Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. "On differentiating parameterized argmin and argmax problems with application to bi-level optimization". In: arXiv preprint arXiv: 05447 (2016) (cit. on P. 3).
[58] Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang, KiJung Yoon, Xaq Pitkow, Raquel Urtasun, and Richard Zemel. "Reviving and improving recurrent back paok-propagttion" In: Inter- national Conference on Machine Learning. PMLR. 2018, pp. 3082-3091 (cit. on p. 3).
13

---

[59] Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. "On the iteration complexity of hypergradient computation". In: International Conference on Machine Learning.
PMLR. 2020, pp. 3778-3755 -3558 (cit. on p. 3).
[60] Jonathan Lorraine, Paul Vicol, and David Duvenaud. "Optimizing millions of hyperparameters by implicit differentiation". In: International conference on artificial intelligence and statistics. PMLR. 2020, pp. I 1540-1552 (cit. on p. 3)
[61] Dougal Maclaurin, David Duvenaud, and Ryan Adams. "Gradient-basel hyperparameter optimization through reversible learning". In: International conference on machine learning.
PMLR. 2015, pp. 2113-2122 (cit. on p. 3).
[62] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. "Forward and reverse graddett-bbad hyperparameter optimization". In: International Conference on Machine Learning. PMLR. 2017, pp. 1165-1173 (cit. on p. 3).
[63] Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. "A value-function- based interior-point method for non-convex bi-level optimization". . In: International Confer- ence on Machine Learning. PMLR. 2021, pp. 6882-6892 (cit. on p. 3)).
[64] Jane J Ye, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. "Difference of convex algorithms for bilevel programs with applications in hyperparameter selection". In: Mathematical Pro- gramming 198.2 (2023), pp. 1583-1616 (cit. on p. 3).
[65] Lucy L. Gao, Jane Ye, Haian Yin, Shangzhi Zeng, and Jin Zhang. Moreau Envelope Based Diffeerence-o-wwealll--CCCoo Conver Reformulation and Algorithm for Bilevel Programs. 2024. arXiv: 2306. 16761 [math. OC] (cit. on p. 3).
[66] Tianyi Chen, Yuejiao Sun, and Wotao Yin. "Closing the gap: Tighter analysis of alternat-
ing stochastic gradient methods for bilevel problems". In: Advances in Neural Information Processing Systems 34 (2021), pp. 25294-25307 (cit. on p. 3).
[67] Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. "A stochastic bilevel optimization" In: International Conference on Artificial Intelligence and Statistics. PMLR. 2022, pp. 2466-2488 (cit. on p.p... 3).
method for
[68] Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. "A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application actor- critic". In: SIAM Journal on Optimization 33.1 (2023), pp. 147-180 (cit. on p. 3).
[69] Zeeshan Akhtar, Amrit Singh Bedi, Srujan Teja Thomdapu, and Ketan Rajawat. "Projection- free stochastic bi-level optimization", In: IEEE Transactions on Signal Processing 70 (2022). pp. 6332-6347 (cit. on p. 3).
[70] Ruichen Jiang, Nazanin Abolfazli, Aryan Mokhtari, and Erfan Yazdandoost Hamedani. "A conditional gradient- based method for simple bilevel optimization with convex lower-level problem".. In: International Conference on Artificial Intelligence and Statistics. PMLR. 2023, pp. 10305-10323 (cit. on p. 3).
[71] Nazanin Abolfazli, Ruichen Jiang, Aryan Mokhtari, and Erfan Yazdandoost Hamedani. "An Inexact Conditional Gradient Method for Constrained Bilevel Optimization". In: arXiv preprint arXiv:2306.00 022422336.024229 (2023) (cit. on p. 3).
[72] Jincheng Cao, Ruichen Jiang, Nazanin Abolfazli, Erfan Yazdandoost Hamedani, and Aryan Mokhtari. "Projection-fres methods for stochastic simple bilevel optimization with convex lower-level problem". In: Advances in Neural Information Processing Systems 36 (2024) (cit. on p. 3).
[73] Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. "A near-optimal algorithm for stochastic bilevel optimization via double-momentum" In: Advances in neural information processing systems 34 (2021), pp. 30271-30222 (cit. on 3)
[74] Zhishuai Guo, Quanqi Hu, Lijun Zhang, and Tianbao Yang. "Randomized stochastic variance-reduced methods for multi-task stochastic bilevel optimization". In: arXiv preprint arXiv:210S.00 02266 (2021) (cit. on p. 3).
[75] Junjie Yang, Kaiyi Ji, and Yingbin Liang. "Provably faster algorithms for bilevel optimization".
In: Advances in Neural Information Processing Systems 34 (2021), pp. 13670-13682 (cit. on
p. 3).
[76] Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. "A framework for bilevel optimization that enables stochastic and global variance reduction algorithms".. In: Advances in Neural Information Processing Systems 35 (2022), pp. 26698-266 2078882666111 10 (cit. on p. 3).
14

---

[77] Shoham Sabach and Shimrit Shtern. "A first order method for solving convex bilevel opti- mization problems". In: SIAM Journal on Optimization 27.2 (2017), pp. 640-660 (cit. on
p. 3).
[78] Mostafa Amini and Farzad Yousefian. "An iterative regularized incremental projected sub- gradient method for a class of bilevel optimization problems". In: 2019 American Control Conference (ACC). IEEE. 2019, pp. 4069-00777 (cit. on p. 3).
[79] Mostafa Amini and Farzad Yousefian. " "An iterative regularized mirror descent method for ill ill-posed nondifferentiable stochastic optimization". In: arXiv preprint arXiv: 109500 (2019) (cit. on p. 3).
[80] Roey Merchav and Shoham Sabach. "Convex Bi-level Optimization Problems with Nonsmooth Outer Objective Function". In: SIAM Journal on Optimization 33.4 (2023), pp. 3114-3142 (cit. on p. 3).
[81] loannis Tsaknakis, Prashant Khanduri, and Mingyi Hong. "An implicit gradient-type method for linearly constrained bilevel problems". In: ICASSP 2022-2022 IEEE International Con- ference on Acoustics, Speech and Signal Processing (ICASSP). IEEE. 2022, pp. 5438-5442 (cit. on p. 3).
[82] Siyuan Xu and Minghui Zhu, "Efficient gradient approximation method for constrained bilevel optimization", In: Proceedings of the AAAI Conference Artificial Intelligence. Vol. 37. 10. 2023, pp. 12509-12517 (cit. on p. 3).
[83] Lesi Chen, Yaohua Ma, and Jingzhao Zhang. "Near-Optimal Fully First-Order Algorithms for Finding Stationary Points in Bilevel Optimization". In: arXiv preprint arXiv:2306.1483 14853 (2023) (cit. on 4).
[84] Frank H Clarke. "Generalized gradients of Lipschitz functionals". In: Advances in Mathematics 40.1 (1981), pp. 52-67 (cit. on p. 4).
[85] Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszezynski. Lectures on stochastic
programming: modeling and theory. SIAM, 2021 (cit. on p. 4).
[86] Michael Jordan, Guy Kornowski. Tianyi Lin, Ohad Shamir, and Manolis Zampetakis. "De- terministic nonsmooth nonconvex optimization". In: The Thirty Sixth Annual Conference on Learning Theory. PMLR. 2023, pp. 4570-4597 (cit. on p. 7).
[87] Siyu Kong and AS Lewis. "The cost of nonconvexity in deterministic nonsmooth optimization". In: Mathematics of Operations Research (2023) (cit. on p. 7).
[88] Benjamin Grimmer and Zhichao Jia. "Goldstein Stationarity in Lipschitz Constrained Opti- mization". In: arXiv preprint arXiv:2310.03600 (2023) (cit. on p. 7).
[89] Olivier Devolder, François Glineur, and Yurii Nesterov. "First-order methods of smooth convex optimization with inexact oracle". In: Mathematical Programming 146 (2014), pp. 37-75 (cit. on p. 7).
[90] Diederik P Kingma and Jimmy Ba. "Adam: A method for stochastic optimization", In: arXiv preprint arXiv: 241..6441.6990 6980 (2014) (cit. on pp. 10, 38).
[91] Guanghui Lan. First-order and stochastic optimization methods for machine learning. Vol. 1. Springer, 2020 (cit. on p. 23).
[92] Ohad Shamir. "An optimal algorithm for bandit and zero-order convex optimization with two- point feedback". In: The Journal of Machine Learning Research 18.1 (2017). pp. 1703-1713 (cit. on p. 24).
[93] Simon S Du and Wei Hu. "Linear convergence of the primal-dual gradient method for convex- concave saddle point problems without strong convexity". In: The 22nd International Confer- ence on Artificial Intelligence and Statistics. PMLR. 2019, pp. 196-205 (cit. on p. 36).
[94] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. "Pytorch: An imperative style, high-performance deep learning library"" In: Advances in neural information processing systems 32 (2019) (cit. on p. 37).
[95] Steven Diamond and Stephen Boyd, "CVXPY: A Python-embedded modeling language for convex optimization". In: Journal of Machine Learning Research 17.83 (2016), pp. 1-5 (cit. p. 37).
15

---

Appendix
A Notation
We use (+-)) to denote inner products and || for the Euclidean norm. Unless transposed, all vectors are column vectors. For f: IR=2 + Rdd its Jacobian with respect to x E IRd is V E R4 1ddixde, For f: I R. we overload V to refer to its gradient (the transposed Jacobian), a column vector. We use v to denote partial derivatives with respect to x.
A function f R" T is L-Lipschitz if for any J. have [[f(()) - f(y))l S Li yll- A differentiable function f : R" + R is convex if for any 2,y E R" we have fly) 2 f(x) fx)) (y z);; it j-sttrnggy convex if 2 2? convex; it is 3-smooth f 3-Lipschitz.
For Lipschitz function f, point x is (ó. -stationnyy if within a d-ball around x, there exists a convex combination of subgradients of f with norm at most e. For differentiable function J, we say that x is e-stationary if [+)]] S e.
B Proofs from Section 3
In this section, we provide the full proofs of claims for bilevel programs with linear equality constraints, as stated in Section 3. We first state few technical results using the implicit function theorem that we repeatedly invoke in our results for this setting.
Lemma B.1. Fix a point x. Given y = arg minggh(z.a)) g(, y) where g is strongly convex and X is the dual optimal variable for this problem, define Lee (x. v. A) g(x,v) + (X, h)x, Then, we have
my (e. x²) yy)(r
Vyh(x.v") 0
V2 B v0 (1 (,,,,,",,,7)) M(x,00)) -vah(z,y")
H. linear equality constraints
Proof. Since g is strongly convex, by linear constraint qualification, the KKT condition is both sufficient and necessary condition for optimality. Hence, consider the following KKT system obtained via first order optimality of y", with dual optimal variable A":
Vyg(a, y² + ( Maa,,, y² 0, and 1(x, v²) =0 0.
(B.1)
Differentiating the system of equations in (B.1) with respect to x and rearranging terms in matrix- vector format yields:
V2 V2 y + v2
by (X* (Zz,"")
Vyh(I,
V (a, (X Mx.
V Vgh(z,8)
-Vah(a,)))
(B.2)
Noting that 2 by Len (I, yr A) Vigl(, 42 (A, Mx,, we can write (B.2) in the form shown in the lemma.
Lemma B.2. Consider the setup in Lemma B.I. The matrix H defined in (3.4) is invertible if the Hessian V2 LeyLoa vy (2, (z y² X*) = V2 (0z y²) + V (X* "t,h(,,'") satisfies V Vyy (2, y", X*) > over the tangent plane T = {y: : Vyh (x, y yy = 0} and v,h has full rank.
Proof. Let A]. We show that Hu = 0 implies u = 0, which in turn implies invertibility of H. v "yh(,,y") "y + O, then by construction of u and H, we must also have Hu + 0. Otherwise V V,,(x, 3² y = 0 and y + O, the quadratic form u' T Hu is positive, as seen by
u Hu 2 Ceg v" >²)y 0,
where the final step is by the assumption of Lez being positive definite over the defined tangent plane T {y: Vy Vyh(z,y")
0). If y = 0 while Hu = O. then V,h having full rank implies X Combined with y = 0. this means u = 0, as required when Hu = 0. This concludes the proof. L
16

---

Corollary B.3. For Problem 3.1 under Assumption 2.2 and Assumption 2.3. the matrix H (as defined in (3.4)) is non son-singllar. Further, there exists a finite Cи such that || -1 S Cn.
Proof. Since we are assuming strong convexity of g. Lemma B.2 applies, yielding the claimed
invertibility of H. Combined with the boundedness of variables (per Assumption 2.3) and continuity of the inverse implies bound on ||
B.1 Construction of the inexact gradient oracle
We now show how to construct the inexact gradient oracle for the objective F in Problem 3.1. As sketched in Section 3, we then use this oracle in projected gradient descent algorithm to get the claimed guarantee.
Lemma B.4. Consider Problem 3.1 under Assumption 2.2 and Assumption 2.3. Let y be as defined (3.3). Then, for any [0, A] with S Pg/22 the following relation is valid:
2
2L
1 - v01 S (x)6, with M(x)= =
M4
Mg
Proof. The first-order optimality condition applied to g(x, v) + 6 y) at 3² and v gives
(V yτ) (z. v" --) 2 0,
which upon adding and subtracting ygJ(r: y²) transforms into (V,9(z, vτ) + V.V (z) - V v=] vV v ,²),""""" - vb) 2 0.
(B.3)
Similarly, the first-order optimality condition applied to 9 y" and y gives
(Vyg(z, y" yB - x²) 2 0.
(B.4)
Adding Inequality (B.3) and Inequality (B.4) and rearranging yields
(Vng(a,, vi) V uD (2. y²) oiV f, v )), vI -v" S (0V (x, )'²""" -ā)-
Applying to the left side above a lower bound via strong convexity of g + 8f and to the right hand side an upper bound via Cauchy-Schwar inequality, we have
=|lyš y" S 8 (f,
(B.5)
where 8 is the strong convexity of + o.. Since f is Cy-smooth, the worst case value of this is 2C Cf Mg/ 2, which when plugged in Inequality (B.5) then gives the
Bg 8C, Pg claimed bound.
Lemma B.5. Consider Problem 3.1 under Assumption 2.2 and Assumption 2.3. Then the following relation is valid.
V La (x)) Agh(x, y²)
V ig(g(a (x)) -*h(z,
ddy(xx) dx
lim 8 8-0
V
Proof. Recall that by definition, g is strongly convex and y² arg min ( y). Hence, we can apply Lemma B. Combining this with Lemma B.2 and further applying that lincarity of implies V2 h 0 and V V2gh h O, we obtain the following:
dy
V2 ((r,v")
[
v (l.. (((
v))
So we can express the right-hand side of the claimed equation in the lemma statement by
dy (x)
(
V (os(o,v"(0))
(dx))
dyy"
dA" der
dx
0
which can be further simplified
V2 Veng(a, v*) Vyh(a,
Vyh(a,))) T
V
-Vah(z,8))
(B.6)
0
17

---

We now apply Lemma 1 to the perturbed problem defined in (3.3). We know from Lemma B.4 that lim y y The associated KKT system is given by
vv, V vz vā) + ( h(x, vī)) and h(x, v3) O.
(B.7)
Taking the derivative with respect of (B.7) gives the following implicit system, where we used the fact that h is linear and hence V 0:
2 fa, yz) + vp (0, yg) by Vyh(z, 23)
Vyh(x,38 V
dug
V v(,
(B.8)
0
H1
For a sufficiently small 6, we have V by (r, 25) + VV f y3) - I, which implies invertibility of Hs by application of Lemma B.2. Since Lemma B.4 implies lims- y yy, we get
V Vyh(2,v')
AB
Is 8=
So we can express the left-hand side the expression in the lemma statement by
Velg(a, 2x(x)) h(x y") )>
V V2lg(a, (x)) + (X*, ,(,, y²)
lim
6-20
dy
dAz d6
2yg(s, 3²)
db + Vah(a,y"
V Ving(a.y y*) ("(
Vyh(x..r)
V (x,)"))
(x,,()"") veh(z,v")T]
0
which matches (B.6) (since (V V thus concluding the proof.
Lemma 3.3. The solution yf" (as defined in Problem 3.1) is OCCH- (C, + [[All)) continuous and ( Sg (C, + | as a function of x. Thus the hyper-objective F is gradient- Lipschitz with a smoothness constant of CF = O[(Ls + C + Cg) Sy( + [|A[))
Proof. Rearranging (3.4) and applying Corollary B.3, we have
V2
TT - V gzng( -Vah(zz)")
B
dxr
This implies a Lipschitz bound of Cи (C2+ (AAI). Next. note that in the case with linear equality constraints, the terms in (B.2) involving second-orde derivatives of are all zero; differentiating (B.2) with respect to we notice that the linear system we get again has the same matrix H from before. We can therefore again perform the same inversion and apply the bound on || and on the third-order derivatives of y (Assumption 2.3) to observe that || d''y" S O(Crr S, dz 1=)= O Sg- (C, + [|]]]))), where
hiding numerical constants in the Big-Oh notation.
As result, we can calculate the Lipschitz smoothness constant associated with the hyper-objective F by
(VF()) VF(F]I
dy
V (,,((,,"(x))) dzy(3) dr
+ (C + |All) + (T. + ||^|1) 2 +L,0,,, + |141)]]|= =Il
dx V
+I,, + CCCC(L + +|A||)]| T||
$ Cr
+ ||||])² || =||-
18

---

Lemma 3.2. For Problem 3.1 under Assumption 2.2, with U2 as in (3.2), the following holds:
dyy (x)
T
Vuf(z,)0) 5O(C,)).
U2
dx
Proof. For simplicity, we adopt the following notation throughout this proof: Gay(I, y) = V2yg. and Gryy denotes the tensor such that its ijk entry is given by 0n, involving By the fundamental theorem of calculus, we have
8²g
We first consider the terms
V v=g(2,0((=)) - V2g(z,v [ Ioy (2, vi (x))
dyp (x) dt.
dt
As result, we have
V Va 1z( (2)) - Vag(a, yx) (x:)
dyt (x)
(xy v² (x))
1t=0
8
dt
1
8
(x, vi (x)) dy, (x)
dyf dy)
8
di
Iav (r, y (x))
dl
1==0
dt
0
1
(eg((; y8 (I:) dy)(x) (x)
dy:
8
Bay (x, gay
(x:)
dt
1=0
dl
1
r
dyt (a)
1
8
( (duj (x)
dyī (x)
(Jny(a, (x)) gay x" (x)))
dl +
Jay Day " (x)) (x)))
k-0 dl.
8
dt.
8
dt
dt
1=
==
(B.9)
We now bound each of the terms on the right-hand side of (B.9). For the first term, have
dyt (x)
(gey
(2 y² (x)) yi (x))
5
dt
dy, (I)
dy (x)
<
||
l (x, v-
ds dt
dt
ds
1=0
1
8
dyt (I)
dy (x)
max sE(0,5]
11 (5, ut (z))
||ddt
dt
ds
1
dyf (x) 1|2
max
Many (x, Vo (x))1
82 max
||
wE(0.8]
rE(0,6)
dl
dyf (x) ||2
8.
|1:= (x, v (x))l
WE (0,6)
dt
6- Sy M
(B.10)
where My is the Lipschitz bound on y as shown in Lemma 3.3, and S, is the smoothness of from Assumption 2.3, For the second term on the right-hand side of (B.9), we have
1 / (x (z))) 15
(dyf (x) (def(())
dy (x)
1
0=0 1 1 (w))(ds))))) dt
1 3d (x)))l
dt
dt
8
1
1
d² Uz2 (x)] 8²
8
I (z. y (x))
max (0
d² d v. (x)]
88.
Il (z, (z))]
max x
8. C. Cy,
(B.11)
19

---

where Cg is the bound smoothness of g as in Assumption 2.3, and Cyy is the bound from Lemma 3.3. For the terms involving the function ht we have
|| diy"
X
X
dx3
dxi
dxi
1-0
olll
8
dó
8 J t=
dl
d6
d
X
Allds
dt
8
dg
1
d2
d2
$
max
X
8
S
max
X!1l ds²
ds
sE(U,6]
8 Ct,
(B.
where C2 is the bound on ity (B.11), I), and Inequality (B.12), along with Lemma B.5, Corollary B.3, and Lemma 3.3, we have that overall bound is
A from Lemma 3.3. Combining (B.9), Inequality (B.10), Inequal-
8 M, + C.CC - Ct) 5000 (Sg C3 + (1A)2 (C, + Ly))).
B.2 Cost of linear equality constrained bilevel program
Algorithm 5 The Fully First-Order Method for Bilevel Equality Constrained Problem
1: Input: Current To, accuracy 6, perturbation
2 (2/8CR.R Rx with CF 2( + Cf SL + [|A]])?, accuracy for the lower level problem 5 2(C + ||A11))??
2: for 10,,,,,... do
3: Run Algorithm 6 to generate 8-accurate primal and dual solutions (f", X²) for
min g(r.. y)
Au By mb
4: Run Algorithm 6 to generate 8- d-accurate primal and dual solutions (0ō, {g) for
min y By=b ((12, v) + (x),8)
5: Compute 62 := (e V [g( +',(( set
FF(x)) == o² + (x,
6: Set
Je+1 3e+1
arg minzex ||= - (5t- ( (
Theorem 3.1. Consider Problem 3. I under Assumption 2.2, and let k. = Cgg/yg be the condition number of g. Then Algorithm 5 finds an e-stationary point (in terms of gradient mapping, see (B.14)) after T ((Cp(F(zg)) inf / 2) oracle calls I and g. where Cp := 2(L, Cs n (L + || is the smoothness constant of the hyperobjective F.
C2
Proof. We first show the inexact gradient F(())) generated in Algorithm 5 is an 8-accurate approxi- mation to the hyper-gradient Fz(z,). Consider the inexact gradient defined in (3.2)
||u. - &ell < 5 [I[[ 07) Valg(æ,,0)) - (V (2, vτ)) - velg(ze.
+ 1スا - --- (Ag AI)
2
< 8 10, + |1A1]/ō.
20

---

Thus we get
dy dx
[))()))) VF(2))] - [V,f(z,, - v=f(xz, 11 2²1l + l1
V v
- cjp + 8 [. + |||11| + Cr-
20
$ 1Cy + +C + +|||||| Cpp
?
$ RC
Applied to the Cm-smooth hyper-objective F, such inexact gradient oracle satisfies the requirement for Proposition B.6. Thus an e-stationary point with 1[9r((') S < (see Eq. (B.14) for the definition iterations. Noting the evaluation of inexact solutions (Ø", X- 07 Xz) requires Ó(VCo/ (g)) first order oracle evaluations, we arrive at total oracle complexity of Ö(VC)) /Cg/Ug C for finding an e-stationary point.
of gradient mapping) must be found in N 0 ((Cr(F(4))
B.3 The cost of inexact projected gradient descent method
In this subsection, we state the number of iterations required by projected gradient descent method to find an e-stationary point using inexact gradient oracles. Specifically, we consider the following non-convex smooth problem where the objective F assumed be Cy-Lipschitz smooth:
minimizeze. (xx)-
(B.
Since the feasible region X' is compact, we use the norm of the following gradient mapping GF as stationarity criterion
r 1-1V vF()))
GF (x) Cp(x - x+) where x arg min =E
(B.14)
CF
Initialized to some Tp and the inexact gradient oracle V F, the updates of the inexact projected gradient descent method is given by
For 11,,..... N do:
1
FF(
(B.15)
Set Ft <- arg min =EX
: x1-1 CF
The next proposition calculates the complexity result.
Proposition B.6. Consider the constrained optimization problem in 13) with F being Ci-Lipschitz smooth and X having radius R. When supplied with a 6 = e² /ACr R -inexact gradient oracle
F, that is, Fx) F(x))l < the solution generated by the projected gradient descent method (B.15) satisfies
CF(F(zo) - F*) + 8C'R,
|F((2)1 2 (E[N]
min
N
that is, it takes most 0 CF(FF())
iterations generate some z with [[=r(x)]] s
Proof. By Cr-smoothness of F, we have
1 (r(z))) & f(x))
f(1(+1) f(x: CF
(Vf(z) + (5
Cr
2CF
1
=((x))
1 (x:
-
2CF
Cp
(B.16)
21

---

We now show that (Gp(()) vf(z))) = 0. Let ir = CF
(Gf(x))
1 Fz(z), and let yr
Tt
OF Va())). Then have that
1 (F(2))
(( ( - CF(x; ( (yt projx (Ht))
CF
Cr(xt projx (ūt) )) (ūi- projx (i+)) Crr projx (ī+)) (ve ū.)
S Cp( projx (Ux) (ye 3t)
I R.
where the penultimate inequality uses the fact that A' is convex set, and R is the diameter of the set X. Combining this with Inequality (B.16), we have that the function decrease per iteration is
F(1++1) S F(x))
2CF [+ + 8CpR.
Summing over N iterations telescopes the terms, we get
min [E[N] | N - + R.
Substituting in N CF(((2))) F*) and the choice = e² R we get
e²
min (2))1 1 2
(E|N)
we obtain the Taking into account the fact that (1))(x)) -zx (x()))) s [VF(2*) FF('')) S desired result.
n
B.4 The cost of generating approximate solutions to the linearly constrained LL problem
In this subsection, we address the issue of generating approximations the primal and dual solutions associated with the lower-level problem in Problem 3.1. These approximations are required
for computing the approximate hypergradient in Algorithm For notational simplicity, we are going to consider the following constrained strongly convex problem:
minimize,ER** g(v)
(B.17)
subject to By= b.
We propose the following simple scheme to generate approximate solutions to Problem B.17.
Compute a feasible ý such that || ="'l S 5. Then solve
-= = arg min XER
| Vvg(0)) B BT XlI.
(B.18)
The following lemma tells us that is close to X" if B has full row rank.
Lemma B.7. Suppose Problem B. 17 is C,--iipshiizz smooth, and the matrix B has full row rank such that the following matrix MB is invertible
BT
Mn
B BO-
Then the approximate solution (), û) from (B. satisfies I| - X1I < | + C2)o.
|[1
Proof. Since (X*, yy*) satisfy the KKT conditions, they are the solution to the following linear system
I
B
y
V Vog(v") + Ty"
B
=
(B.19)
MB
22

---

That is
Vvg(v") Ty"
Mn
On the other hand, the approximate solutions (v, X) in (B.18) satisfies
I
B
= B X Tū
B
A
We show the right hand side (I.h.s) of the above equation to be close to the r.hs of (B.19). Let : { x: X R") denote the subspace spanned by the rows of B. We rewrite B X as the projection of V Vg( onto S. that is,
B T 1 = arg min SES
V Vyg(ū) =s|²
-Vogly)) = = arg min SES
V Vyg("") - =|1²;
where the second relation follows from the KKT conditon associated with (A*,y") Since the projection an non-expansive operation, we have
B A (-V (-Vg((')) | BT & VV000) Vg(w")| C, y0ll C,
We can rewrite (Ø, X) as solutions to the following linear system with some || S (1 + C₂)6.
V Vyg("")
+ 1y -
X
Mp
b
Thus get
y/ ||
y"
= M
0)
s <1>M5*10 11(1 + Cg)o.
Now we can just use the AGD method to generate close enough approximate solution ý and call up the Subroutine in (8) to generate the approximate dual solution X.
Algorithm 6 The Projected Gradient Method to Generate Primal and Dual Solutions for a Linearly Constrained Problem
1: Input: accuracy requirement >> 0 and linearly constrained problem miny: By g(v)-
2: Starting from yd = ( and using := {y E IR By = b} as the simple feasible region.
3: Run the Accelerated Gradient Descent (AGD) Method (Section 3.3 in [91]) for N
LL/Cg// log [|v" M|la (I)C,++11) iterations.
Age
4: Use the N as the approximate solution generate Å according to (B.18).
5: return (i, 2)
Proposition B.8. Suppose the objective function is both Lg -smooth and stroonyygly convex, and that the constraint satisfies the assumption in Lemma B.7. Fix an E > 0, the solution (ğ, X) returned by the above procedure satisfies ||y" - ~ S and 1| X+|| S In another words, the cost of generating e-close primal and dual solutions are bounded by O(v log 4)-
Ca
Proof. With N [4/C e/I| [I(1 + Lg). Then can apply Lemma B.7 obtain the desired bound.
Mg log IIv" MII [1CL,
Theorem 3.7 in [91] shows that Il Ø <
Mgg
23

---

C Proofs for Section
Our algorithms are based on the Lipschitzness of F, which we prove below.
Lemma 4.3. Under Assumption 2.2 and 2.5, F in Problem 4.1
in x.
Proof. By Lemma 2.1 of [16], the hypergradient of F computed with respect to the variable may expressed as FxF(2) = v=f(z, +
du (x)
(f Since we impose
di
Lipschitzness on f and y", we can bound each of the terms of (x) by the claimed bound. C
C.1 Faster algorithm for low upper-level dimensions
In this section we analyze Algorithm 2, which as stated in Section 4, requires evaluating only the hyperobjective F (as opposed to estimating the hypergradient in Algorithm 3).
The motivation for designing such an algorithm, is that while evaluating VF up to a accuracy requires ((a-)) gradient evaluations, the hyperobjective value can be estimated at a linear rate:
Lemma 4.2 (Proof in Appendix C.I), Given any can return F(x) such that (F(x)-F(x)) S
-
using O (V//// Mg log(L, /a)) first-order oracle calls to f and g.
Proof of Lemma 4.2. We note that it suffices to find ÿ such that 11 - (x))] S a since setting F(x) == f(x, ÿ²) will then satisfy [f(z) - F(x) = (z (2 f
S L f, =
by Lispchitzness of f. as required. Noting that y (x) arg min (ar, y) the solution to constrained smooth, strongly-convex problem with condition number C //g is possible to approximate up to a/Ls with (( /Cg/P, log(Ly/oj) first-order oracle calls using the result of Zhang and Lan [45].
Accordingly, we consider Algorithm 2, which is zero-order variant of Algorithm 3, whose guarantee is summarized is the theorem below.
Theorem C.1. Suppose F Rd R is L-Liscchitz, and that (F(-) FF-)) S a.
Then run-
ning Algorithm 3 with p min 6 F(mo)-inf ve [dp (4p-1220202
L j.v 8 p, D O (3p1"+a- .n
outputs point out such that Eldist F,F (z S E e with
T=0 d(F((z)) - inf F)
(1++09 d + (F(zo) - inf my (
dL?
)) calls to F().
de3
82
Combining the result of Theorem C.I with the complexity of hyperobjective estimation, as given by Lemma 4.2, we obtain convergence to (6, -)sttioionary point of Problem 4.1 with 5d -3) gradient calls overall.
C.1.1 Proof of Theorem C.1
Denoting the uniform randomized smoothing Fç(x) := E [= + p p-2)] where the expectation, here and in what follows, is taken with respect to the uniform measure, it is well known [92, Lemma 10] that
E 10
||
+ pw) F(x (kkr-pw)ppr ) (F,()),
2 - dI.².
E || 11
VF
2 (F(x - pw) F(x- pwo))ul
d
(C.1)
We first show that replacing the gradient estimator with the inexact evaluations F(-) leads to a biased gradient estimator of F. Lemma C.2. Suppose [F(-) F(-) S a. Denoting
Is 20 (F(r + pw) - F(x pw))u,
g. 20 (F(r pw) F(x pw))
24

---

it holds that
ad
a²
E || 1
Jzll
S
and
Bi|l||=1
1 10 x
+ dI.²
pe
Proof. For the first bound, we have
d ||0||| [1
ad
|w l1 - Toll 5 2p
while for the second bound
d²
Bi 0z 2| = E w = 11 9x + Ixll S 21 |||||= 11 -2rl1++ + (wl =1 11ae11
x a +dI?
p²
where the last step invoked (C.1).
are now ready to analyze Algorithm 2. We denote a' p
G / a2
+ dL2. Since
It It-1 + As, we have
Fạ(11) - Fp(x(-1)= = / (VFp( sAi,, ds
Uns ( s, A.] (((FF(())), A+)
By summing over t E [T] = [K x MJ. we get for any fixed sequence U1,- uK E RRd
inf F, S FT(TT) Fa(2F)
E (V))
M
FF((a)) +
Σ
E
-u))]
k=1
K M
E
k=1m=1
M
F0(21)) +
Rugg((u)) +
Σ
E
(VF
Am m=1
M (V -1) uz)}
$ Fo(xo) + KDCVM + Kd'DM +
m=1
where the last inequality follows by combining Lemma C.2 and Lemma C.3. By setting un ==
EM m=1
rearranging and dividing by DT DKM we obtain
Emm
K
M
FØ(1o) inf G
E
Σ
(F(((((-)))+m))
S
+
K
M
DT
VM
k=1
m=1
Fo(xo) - inf Po
Vo a²d
o
L2d
ad
+
Kv
VM
P
Fœ( inf F.
ad
LVd
ad
(C.2)
Kv
VM
VM
P
Finally, note that for all m E [M]
||=(-1)M++ - Fzll S .DDS v, therefore V (15(((-))) e (Tx) C F.,((I)), where the last containment is due to [46, Lemma 4] by using our assignment
p = 8. Invoking the convexity of the Goldstein subdifferential, this implies that
M
(P)((((-))Mmm))) F)F(Tt)
M
25

---

thus it suffices to bound the first three summands in (C.2) by in order to finish the proof. This happens long as Falzn)-inf Fr
g. and Lyd
VM S 3. which imply K ~ Fa(za) ((lza)-iuff Fg.
Kv
M 2 dd and M 2 p
L'd c
By our assignments of p and v, these result in
FØ(2o) - inf Fn.
a² L'd
== KM = =
De
12
2
(F(10) - inf F)d
add
=0
p + +1.2 1??
6c3
(F(xo) - inf F)d
L
) + L2 12
=0
add max
de3
82
(F(rn) inf F)2
completing the proof.
C.2 Proof of Theorem 4.4
We recall Theorem 4.4 below to keep this section self-contained.
Theorem 4.4. Suppose F Rd + L-Lipschitz and that [VF()) VF(III S a. Then running
Algorithm 3 with D O
6c ). .
O ( outputs point x such that E]dist(O, Fz ))] S
+ a, with T = O (F(
F calls to F.)))
5z
Our analysis is inspired by the reduction from online learning to nonconvex optimization given by [47]. To that end, we start by proving a seemingly unrelated result, asserting that online gradient descent minimizes the regret with respect to inexact evaluations. Recalling standard definitions from online learning, given sequence of linear losses ly (-) = (gmm 1) if an algorithm chooses
Ai...., AM denote the regret with respect
M
Regar (w)
(ams Am u)) m=l
Σ
Consider update rule according to online projected inexact gradient descent:
Am+1 == clip (4m 7m9m).
Lemma C.3 (Inexact Online Gradient Descent). In the setting above, suppose that (Tm M are
possibly randomized vectors, such that E ll9m 9mlll S and E |1mm| 11 S G2 for all m [M]. Then for any [|u||| S holds that
D2
M Em
IE [Reg (w))
mm + aDM,
JM
where the expectation is with respect to the (possible) randomness of M In particular, setting D
Tm Gv55 yields
E [Rega (w) DŌVM + DDM.
Proof. For any m E [M]
|mm+1 - u/1 = |ccip (Am 7m]mm) - -ul1
< Am 7mmm - u11 = 11 ru|22 1/ 1 11 27m (Am u. Iml)
thus
Gm, Am u) 5 11mm u||² -111 |1 u|l Tmm l10m 1|
27/m
from which we get that
E. (gm, Am u) E (Im, A. m
u) + E. {mm
Im. Am u)
Am u/l [mm+1 - 2112
Mm
|1 1 +E Elmm - -āmll 11 u/l
27/m
2
Am u1/2 1-14 Amm+1 w/l2
Um 7 aD.
2mm
2
26

---

Summing over E [M]. we see that
M
(1
G M
Reg (u)l - E
A m
u1/
+
Σ m=
mm
MaD
mm
7m
2
m=m
D
7m + aDM
M1
The simplification for 7mm
readily follows.
GVM
We are now ready to analyze Algorithm 3 in the inexact gradient setting. Proof of Theorem 4.4. Since Algorithm 3 has Ft Iz-1 D., have
F(x) F( [
(V s A,) ds
Ra. (V (VF( 8, s, A:) (VF((())
By summing over / E (T] [K MJ. we get for any fixed sequence "1, "KK E RRd
inf F F(IT) & F(xo)= +
E ((V
1=1
M
F(oo)
Σ
((-
K
M
ux)]
m=1m=1
K Σ
< F((oo) +
Rega (ux)
E
(F 1) un))
k=
m=1
K
S F((o))+ + KDGVM KaDM
Σ
E (VF(E
k=1
where the last inequality follows from Lemma C.3 for G V " GVM
since
1h VF(2))) S (deterministically) for all E [T] by assumption. Letting u =
MM VF(F (F( mm)
rearranging and dividing by DT = DKM, we obtain
K
M
F(r.) inf
(F(2(K1))M+m))
<
+
+a
K
M
DT
VM
m==1
F(wn) - -inf F
+ a.
(C.3)
K8
VM
Finally, note that for all E [K].m [M] ||=x--1JM++ - TR
< MD < 8, therefore
(3( E 0&F (zz). Invoking the convexity of the Goldstein subdifferential, we see
that
1
VF(2(1-1)M44) FzF(TT) M
thus it suffices to bound the first summands the right-hand side in (C.3) by in order to &
F(zo)-inf K3
finish the proof. This happens as long as
< $. These are equivalent to < &
and
JM
K 2(F -ifrg)-nnff- inf F) and M 2 1² which results in
dc
F((o) inf F
1 12+a0
(F(zo) inf F)
T T=MM- =0
de
22
dc3
27

---

completing the proof.
C.3 An implemenntation-frienddll algorithm and its analysis
Algorithm 7 Perturbed Inexact GD
1: Input: Inexact gradient oracle F Rd - R&, initialization vo IR. spatial parameter >
step size > 0, itcration budget 7' E N.
2: for ................................ ... T 1 do
3: Sample W ~ Unif(Sa-1)
4: 9i F + 8 wi)
5: 2++1 = 2t 79h
6: Output: you ~ Unif 1)
Theorem C.4. Suppose F TRd - I--Lipschitz, and that [[VF() VF S a. Then
([F(mo) inf ( /)+221)//28//2)
running Algorithu 7 with 7) θ
outputs point x such that
El 0g ou ))] S 6 + val. with
T=0 (F(zo) inf F 5L)
calls to VF(-).
Se4
Proof. Throughout the proof we denote = xt + 8 wy Since F is L-Lipschitz, Fş(a) == EnwUnit(S 1)(F(z + 8 w)] is L-Lipschitz and
By smoothness get
Lvd
Fo(x(+1) - Fo(x,) < (V:3( #141 - -x)) +0
|| - 2r11
8
17 LLV
- (VP +0
|| 1
I2I
- = (VF. (VF.
VF +0
8
Noting that [=())(=)]] = (22 and that |i < 1 that
S a + L, we see
I2Lvd (a
E( - - - [V +La
aa)) L)3
which implies
E (V [[Fa(a:)] -B(3((221))) + Lo O nIIvdlar L)²
17
Averaging over 0...., and noting that Fs(2o) -nf
inf Fs S (F(xo) - inf F) + 5L results in
B| (F(zn) inf F) + ST.
+La+0 (nTvalaa + 1.)
E V our 1|
T Σ
nT
By Jensen's inequality and the sub- sub-additivity of the square root,
(1
(F(an) inf F) 8L
/ + L)2
(z <
VLa+O
n/T
8
28

---

(((F((o)) F)+61)6 yields the final bound
Setting
VTLVi(a+DY
B [z $ ((F(x)))
inf F) + /2/
(a L) VLo,
81/471/4
and the first summand is bounded by for 7 0 (l) ())
D Reformulation equivalence
Theorem D.1 (Reformulation equivalence), When X matches an optimal dual solution to the lower level problem y² arg miny (22,3) v) s.I. h(x, u) s O, we show that for each x, the reformulation hus the same feasible region of y.
Proof. We first show that lower-level feasibility implies feasibility of the reformulated problem. Let y" X* min max g(z, y) + 3 h(x,1) be the primal and the dual solution to the lower level problem A20 with parameter æ. We can verify that y satisfies all the constraints the reformulation problem. The feasibility condition h(r, v²) is automatically satisfied. We just need to check:
g" (x) min (2x 8) (X*) h(x, 0)
= g(x, y²) + (>*TT<(z,)) (<xv"))
(D.1)
Therefore, 2, y² is feasible point to the reformulation problem.
We now show the other direction, i.e., that feasibility of the reformulaed problem implies that of the lower-level problem. Given X", let us assume y satisfies g( y) S 9 (z) and (xx y) I 0. On the other hand, assume y X min max g(x, y) + 3 h(x, y) be the primal and the dual solution. We can show that:
$20
( v) + (A*) h(,, v) (z) men g(x, + (x))T<(x, 0).
(D.2)
By the strong convexity of + (A*)Th, h, we know that matches to the unique minimum y", which implies that y y² is also a feasible point to the original bilevel problem.
E
Active constraints in differentiable optimization
By computing the derivative of the KKT conditions in Section 2.1, we get:
V dy
dx*
(V
( ya h) + (V 9 (X*)
h) dr
+ (V,h)
0
(E.1)
dx
dy" dr
dA*
diag ( v + diag A V h
+ diag(h) dx
0. (E.2)
Let I = E [da] /(x y² 0, 0, > 0} be the set of active constraints with positive dual solution,
and Z, (i]l((r, (a, y²) * 0} be the set of inactive constraints and Iz = [i]h(r, y²); = 0, X = 0). We know that = In U UZ. For each i I,, due to complementary slackness, we know that X; 0.
For i I, in (E. have X V h (x, y/"" + ,,,,,, v²), d' +h(x, y" der 0, which implies 1(x, y²" dx: 0 because X O. This in turn implies dA; 0 because h(x, 2² < 0. That means 2 for any index i E Ij. Therefore, we can remove row i E Ig in (E.2) and obtain A; = 0 and dA;
dxi
de
the dual variable X = 0 and has zero gradient dA;
de
dx For Iz the KKT condition in (E.2) is degenerate. Therefore, di can be arbitrary, i.e., non- differentiable. As a subgradient choice, set
dA;
for such i. This choice will also eliminate de
29

---

its impact on the KKT condition in (E.1) because di is set to be O. By this choice of subgradient,
di
we can also remove row i E Ia (E.2).
Thus (E.2) can be written as the following set of equations, for hy [Ayliez and A = [Xp]ezz
diag(A VVag(A"VV.lla 2 - diag(A))))))))) /r dy
dii dx
+ diag(hz)
=0
dr
dy"
diag(A") h diag Ai
V
0
(due to hz(x, 0)
(E.3)
dr
In (E.1), due to dz
dA;
0 for all E I, we can remove
dai dr
Vi (E.1) by:
Byy h) dy
dx*
( 9 + (A*) yon h) 9
(Vyh)
dr
dr
dy
dii
(V yn. + V h) + (V B + (A*)
V
+ (V ht)
(E.4)
dr
dx
Combining (F.4) and (F.3), get:
dy"
dii
(V 9 + (
و h) + ( 9 (2*)
2
+ (Vyhz)
dx
dr dy O,
diag(M > VV 11 + diag (1z) V hi dx
which can be written in its matrix form:
V vy g + (A-) T V Vyhi
V g V
(A*) T y
wy
(E.5)
diag diag(A;) V
diag diag(A;))))))) V
This concludes the derivation of the derivative of constrained optimization in (5.2).
F
Inequality case: bounds on primal solution error and constraint violation
Lemma 5.1. Given any x, the corresponding dual solution X (2)), primal solution y²() of the lower optimization problem in Problem 4.1, and yx- aa (2) as in (5.5), satisfy:
V (x) y" (x)]l s ((T and || a (x)) s O(aa 1122,,777 2/13)
(5.6)
Proof. We first provide the claimed bound on [lvā, - (x)ll.
Part I: Bound on the convergence of
Since vi a minimizes Laex (I, y), the first-order condition gives
0 = VyLa,>- (I, ax)
Similarly, we can compute the gradient of Ca, (x. y) at y":
VyCa(I, (z) = V vuf(a,y) + ai Vxg(z,)") + ( vyh(x,)')) + as (yhr(e,"") hz y²)
(z,(,,""),
where the second step due the property of the primal and dual solution: Vyg(z, y²)
y²) by the stationarity condition in the KKT conditions, and by definition of
the active constraints lız where the optimal y" must have fr(x,, 8²) = O.
Since, for sufficiently large a1, the penalty function is 01llg L5 on strongly convex in y. we have:
01fg yズ aal - V (z, (x.8") VyCa. (z. 84 a = V (,f((, (2,y") Ly.
2
Therefore, upon rearranging the terms, we obtain the claimed bound:
2h
110" - Va
a144
30

---

Part 2: bound on the constraint violation.
When plug y² into (5.4), get:
f(a, =0)) (x)) 2
22.
[b<(,,"")1 = f(2.8)).
22
Plugging in Va we may obtain:
La, V2. a = VI. (a 02 (1z a)l
2
=f vx tar(0(, + (1*) h(,, (. g(z,4()))))))))))))))))(()) (x*) h(r, (
+ hT Vz- va-
02
2
2 (z, ad
Mg
Ilu VR 1|2 + 2
02 2
where we used the strong convexity (with respect to y) of g(x, v) + TM) y) and the optimality of y² for g(z, + (X*) h(2, y). By the optimality of ys- for Laxd,, we know that
02 La, 2 La.x (z, aa) 2 f(x, Vx- vx- + an Mg 110 vx-,aal 1
h2 uxx 112
2
Therefore, by the Lipschitzness of the function f in terms of y, and the bound |1y/ - Vā- S we know that:
26
axpe
hz(a,, vx
S ((x, a)ll
(x, vx-.a) an Mg 11y* vx
$ 1 Ily* vi.aal
-01 2/2 Il1e all
Pgg
S 1, 1 yx- all
= 0(a 1)
Rearranging terms then gives the claimed bound.
The bound on the constraint violation in Lemma 5.1 is an important step in the following theorem.
G Proof of Lemma 5.2: gradient approximation for inequality constraints
Lemma 5.2. Consider F as in Problem 4.1, C as in (5.4), fixed x, and Vi-,a as in (5.5). Then under Assumptions 2.2 and 2.5, we have:
VF(()) VaLx all s (0( O(a 0(1 -1/3 O(a 1/2 022 11/2 0(a 3/2 1/2
022
Proof. First, recall (5.4) here:
Lx = f(z, v) ())
h(x,)) gz())) + || 1 + an (g(x, v) + (X*)T(((,,)
Next, recall from Equation D.I, we can express g" (x) = g(x, ))) (2*) which we use in the first step below:
31

---

vaF(T)- - d
Lx aalisii
dx
Vas(z, dy
dx Vullew))) - aa) a) v "
-ai(Vag(z,V)) X+) + az "r
= -Va[(r,y)) - Vas(o,
(G.1)
+ dy'
Vof(z.8") dy"
Vyl(z,
(G.2)
dx
dx
dy
V V + (1t)
Vi y²
+ dæ
Vyf(z.v/s.o)) an
diag( (lag(>))Ve Vz)
yx
0
added term
V2 vng + (A*) /1 1 diag V
T -xx
0
02
Vanr
(Z v5..aa
(G.3)
added term
+
Veg(z,0") - Vug(E, VZ.
Vah(a,)") va)
Ving ynn (A*) V diag (1)) Vrhz
Vi- y²
+
(G.4)
0
addeed
V2 y diag( V
T h yz
0 diag(1 //g)) Vx
02 V V,hr(a, N +2
adided term
(G.5)
According to (5.2) and (E.5), let
V2 2 TV diag (X* V
V
H
y9 V hy
which is invertible by Assumption 2.2(i and by the fact that we remove all the inactive constraints. We now bound the terms in (G.1), (G.2), (G.3), (G.4), and (G.5).
Bounding (G.1) and (G.2): (G.1) can be easily bounded by the smoothness of f in terms of x and and the bound on by" )(xx)),al s O(aT)) from Lemma 5.1. Therefore, we know:
Vof(z,)) Vof(E, s Cy 100 visy vo s sc,-0(77))
Similarly, given Assumption 2.5 by which y" (x:) is Lipschitt in z. we have the bound Therefore, (G.2) can be bounded by:
dy de
S I.y
dyy dy dx Vyf(a,v") dx Vyl(E, SC, dr |
dy"
-C
Bounding (G.3):
32

---

V y + ((A*)*) diag((>*)) 22z
7
Using (5.2) to solve
H
we can write:
dz
dy
V2 V ((1)"))
Vyl(a, a
(H-1)
dx
=
diag (A*) (
0
dy
Veg(a, Vary,,) V vyh(a, Mary Maraa
a1
dx
+02
(G.6)
where we use the optimality of V(x-)= from (5.5):
VyJ(a, (ix)))))) + tn (Veg(z, )a) + V va, aa)
(G.7)
+ 02 V y M(x-)aa) " (1 M(x-)=,)) 0.
Further, recall that H non-degenerate by Assumption 2.2, as a result which, the added term in (G.3) can be modified as follows:
Ving (V M V
To (x-)ra -b
0
Ving + ((^*)*) V
aa (H - 8r)
(1I HT
diag(( (X*)²) V
ya! 0 + ((2)*) V yall diag(() (X }})) hzz
[V g + (i (1 (M(a))a -1' (G.8)
(H-1)T
=01
Vyhr(E y²
-8²) )) -1r)
The added term 2 in (G.3) can be expanded to:
V yz9 + ((***) ( h( diag (X* ) 2hz
Ma + TV diag(()*) (x*) V Zzz
=02
12
( diag(1 (0ng(1((>")))raa ((x) (G.9)
ya9 + ((^*)) V
M/ h(*))
(H-1)T Vghh( 3 hr hz s(r)) a
=02
diag( " V.hr
Therefore, we can compute the difference between (G.6), (G.8), and (G.9) to bound (G.3), and the fact that Vyg(E, v²) + (x*) vyh(r,y") = 0:
use
dy Vyf(x, Vx a added term 1 added term dx
Ving + (1*) V2 (H-1)T an diag (2;) 1
V Vog(I, v .a) Vvg(e,
V (0)x,,"")( ("i -
0
(G.10)
V 1 Tx-
M() ( - -yy)
+ a1
(G.1l)
a1 (' v-)
(G.12)
V Vybi(I vi. a) Thr vx
V h vx- The aa))
+ 0g
(G.13)
The terms in 10) and (G.11) both be bounded by ai C1CyLyllyS..o y² and a R1 - y 112 by the smoothness of and h T X*. Further, plugging in I1y" - v S O(a; from Lemma 5.1 bounds both these terms by Oaa )..
33

---

To bound the term in (G.12), we use:
|1,z(z; v²=,a)) hx (2, y2 - Cn llvt. -
Therefore, we have:
|| (1,hi( (V--, -2>'|l x [ リズ
|| v Cho( -
s (aa - 1/2 1/2
02
+
+
= 0 1/2 -122 )
Q2
which upon scaling by a gives the following bound on the term in (G.12):
V NI v - y')ll - O(a 02
1/2 + +ajt).
The term in (G.13) can be bounded by:
Q2
V (zz Vi-
.)) ) h2 aa) (2,z(x,)) (z,z") "eaee""""""aa,eeee"e" (2,
Wz Vx- - (zh yn)| (1)
=02
O(ai "((a) 1/2
a2 1/2)
00
=0 3/2 0:2 /
(G.14)
Bounding (G.4); This can be easily bounded by the smoothness of g and h, and the bound on the dual solution ||^]]| S Thus (G.4) can be bounded by R O(aT²) =((T))
Bounding (G.5): By the same argument in (G.14), we get:
h Sa0 V NI (A) Va,z(a, y²) |1
Q2 V nI VA- a hr(z, V a - Vyhz(z,1")) hz vx ui
=02 O (aaa a/ 1/2)
=0 3/2 2/2)
Combining all upper bounds gives the claimed bound.
H Proof of the main result (Theorem 5.3): convergence and computation cost
Theorem 5.3. Given any accuracy parameter a > 0, Algorithm 4 outputs V, Fx)) such that [VF(x) (7F())-V(()) S a within ((a=)) gradient oracle evaluations.
Proof. First, given the bound Lemma 5.2, we choose a1 = a -2 and 02 = a- to ensure the inexactness of the gradient oracle is bounded by In the later analysis, we will still use 0n and 02 in the penalty function for clarity.
Now estimate the computation cost of the inexact gradient oracle:
Lower-level problem. Given the oracle access the optimal dual solution X (ar), recover the primal solution y (x) efficiently (e.g, by [45]). Therefore, we can use the primal and dual solutions construct the penalty function Lx-,a (z. y) in (5.4).
Penalty function minimization problem. The second main optimization problem is the penalty minimization problem in Line 4 of Algorithm 4. Recall from (5.4) that
Lxaa (x, y) = f(x, y) + a1 (g(z. y) + A h( v) -g" (z)) + 02 (, 1)1
(H.1)
where we use the approximate dual solution À as opposed to the optimal dual solution X
Given IH, solve the penalty minimization problem:
Sha (x) = arg min (x,a(x,)))
The penalty minimization is unconstrained strongly convex optimization problem, which is known have linear convergence rate. We further analyze convexity and smoothness below to precisely estimate the computation cost:
34

---

The strong convexity of (2: is lower bounded by 2yd = O(a1).
The smoothness of ( iz y) is dominated by the smoothness of 02 [ v) since 02 > 01. By Lemma 5.2, we know that the optimal solution must lie an open ball Bly" 0(1/aa)) with center y" (inner optimization primal solution) and radius of the order of ( This implies that we just need to search over a bounded feasible set of y/ which we can bound y y)ll I La and h(x,y) v) S H within the bounded region y E Bly", ((1/a))) We can show that h² is smooth (gradient Lipschitz) within the bounded region by the following:
V 1
M + v V & / + v V & HCh + Ih
wW
which also implies h is also smooth (gradient Lipschitz). Therefore, anद is (HOn + L 02 O smooth.
Choosing = + and 02 a.. the condition number of La,2(1,) v) becomes x = O(02/a1) = (( Therefore, by the linear convergence of gradient descent in strongly convex smooth optimiza- tion, the number of iterations needed to get to a accuracy is O(va x log( 22) = O 2 log( )) Therefore, we can get a near optimal solution V²,a with inexactness a in ( oracle calls.
Computation cost and results. Overall, for the inner optimization, we can invoke the efficient optimal dual solution oracle to get the optimal dual solution X (xx) and recover the optimal primal solution y (ar) from there. For the penalty minimization, we need ( oracle calls to solve an unconstrained strongly convex smooth optimization problem to get to accuracy. In conclusion,
combining everything in Appendix H, we run (L1) oracle calls to obtain an a accurate gradient oracle
a to approximate the hyperobjective gradient V fz)(x). This concludes the proof of Theorem 5.3. O
Remark H.1. The following analysis quantifies how the error in the optimal dual solution propagates to the inexact gradient estimate. This is not needed if such a dual solution oracle exists. But in practice the oracle may come with some error, for which bound the error.
Bounding the error propagation in error in dual solution and the penalty minimization. First, we not get an exact optimal dual solution, the error in the dual solution with ||^ X² S a will slightly impact the analysis in Lemma 5.2. Specifically, in Appendix G, the approximate À will impact the inexact gradient VaCx, (z, vh computation and the analysis in (G.4) and (G.7). In (G.4), to change À to X*, we get an additional error:
a1 V..h(,,/ (A- 1 TT x2))
(H.2)
=V 1/- ((h(),((aa))
SanCn 11v - 2/all (1- 22)
50(01a = 0(a),
where the last inequality due | vクa S Oaa that based on a similar analysis in Lemma 5.1 with a near-optimal vh.a under a² (r) accuracy.
Therefore, the error incurred by inexact À in (G.4) is at most O(a), which is of the same rate as the current gradient inexactness O(a).
In (G.7), the optimality holds approximately for the approximate X. Therefore, by the near optimality of vh,aa (strongly convex optimization), we know that the following gradient is also a-close to 0, i...
| f(r vh + (V vh,a) + V Vy,(z, V(, Vs.a) TA) hz(a, 1/ al |l S a,
(H.3)
a2 V yThh( J
whose inexactness matches the inexactness of the gradient oracle a, and thus we do not ineur additional order of inexactness here.
35

---

Moreover, there is an additional error because we need X as opposed to near-optimal À to make the analysis Appendix G work. The error between using À and X in (H.3) can be bounded by: (H.4)
S L,
where we use the local Lipschitzness of the function h in an open ball near y². Therefore, the additional error is also O(a). which matches the inexactness of the inexact gradient oracle.
Therefore, we conclude that in order to bound the inexactness of the gradient oracle, we just need an efficient inexact dual solution with accuracy.
I Practical oracle to optimal (approximate) dual solution
Here we discuss how practical the assumption on the oracle access to the optimal dual solution is.
For linear inequality constraint h(x, y) Ax - By- bb, b, the LL problem is a constrained strongly convex smooth optimization problem. To show that we can compute an approximate solution the optimal dual solution for linear inequality constraints, we apply the result from [93]:
Corollary I.1 (Application of Corollary 3.1 in [93]). When h(x, y) Ar By + b linear y. the primal and dual solutions can be written as:
y X* arg min max g (z, v) + (X*) (T)TT((,,w)) g(x,v) (x-) By R(x)
7
y" X arg min max g(x: (2 v) (X*) By
(I.1)
y
where g is strongly convex in and B is of full rank by Assumption 2.2. According to Corollary 3.1 from [93], the primal-duat gradient method guarantees linear convergence. More precisely, in
t t= O(log 2) iterations, we get:
11 - y1'l S a and | S a.
(1.2)
Given Corollary I.1, we can efficiently approximate the primal and dual solutions up to high accuracy with Ollog a oracle calls when the inequality constraints are linear. This gives us an efficient approximate oracle access to the dual solution.
Remark I.2. Under the assumption of an optimal dual solution oracle, all the analyses mentioned in Section 5 hold for the general convex inequality constraints. However, the main technical challenge that the dual solution oracle for general convex inequality cannot be guaranteed in practice. In fact, to the best of our knowledge, there is no iterate convergence in the dual solution Afor general conver inequality constraints. Most of the literature in strongly-convex-comee only guarantees dual solution convergence terms of its duality gap or some other merül functions. We are not aware of any successful bound the dual solution iterate convergence, which is important research question to answer by itself. This is the main technical bottleneck for general convex inequality constraints as well.
saddle point convergence
Remark I.3. On the other hand, we need the dual solution iterate convergence with rate O(1/a) to ensure the error to be bounded. But this is not necessary condition. To ensure bound on the error propagation, we just need to bound some forms of merit functions ((H.2) and (H.4)) of the dual solutions, which believe that this is much more tractable than the actual iterate dual solution convergence. We leave this as a future direction and this will generalize the analysis from linear inequality constraints general convex inequality constraints.
J The role of X'(x)) in the derivative of Equation (5.4)
Notice that Equation (5.4), we treat the dual solution X >²(x)) as a constant to define the penalty function derivative. Yet, the dual solution (x) is in fact also a function of æ. Therefore, in theory, should also compute its derivative with respect to x.
However, notice that the following:
dl(x) dr
v=(("<z)) (A())))((()))))) = vah(a,v)
1(I,y)
(J.I)
The later term in Equation (J.1) can be divided into two cases:
36

---

For active constraint E I with h(x,3") = O, we know that X is close to y² by
Lemma 5.1. Therefore, the derivative
dA(=) da h(x, (i,a) & LaLsar = O(ai) = 0(a2)
by the local smoothness of h near y" and the Lipschitzness assumption of X in Assump- tion 2.5.
For inactive constraint i E I and x > 0, we can solve the KKT conditions and get dA(z) 0. Therefore, the second term becomes O.
For inactive constraint E I and X O, the KKT system degenerates and we need to use subgradient. By solving the KKT system, find that dA(z) 0 is valid subgradient. dr
Therefore, by choosing this subgradient, the second term also vanishes.
Therefore, do need compute the derivative of X the terms involved its derivative is negligible compared to other major terms.
K Experimental setup
All experiments were rum on a computing cluster with Dual Intel Xeon Gold 6226 CPUs @ 2.7 GHz and DDR4-2933 MHz DRAM. No GPU used, and we used I core with 8GB RAM per instance of the experiment. The cutoff time for running the algorithms is set to be hours. All and averaged
experiments
10 different random seeds. All parameters in the constrained bilevel optimization in Section 6, including the objective parameters and the constrain parameters, randomly generated from normal distribution with O-mean and standard deviation
For our fully first-order algorithm, we implement Algorithm 3, where the inexact gradient oracle subroutine is provided by implementing Algorithm 4. All algorithms are implemented in PyTorch [94] to compute gradients, and using Cvxpy [95] to solve the LL problem and the penalty minimization problem. We implement with certain accuracy requirement, and use PyTorch to compute the inexact gradient discussed in Section 5. We implement the non-fully first-order method using the CvxpyLayer [18], which is Cvxpy compatible library that can differentiate through the LL. convex optimization problem.
fully first-order method based the solutions returned by Cvxpy
L Additional Experimental Results
cvspylayer (Alporithmm
F2CBA g²=0 0003
cxxpybayer
1.5
Opstmaitt gap
F2CBA e0-0.001
30
F2CBA
a1e0.01
2.00
1
F2CBA e'=1.0
F2CBA e²-0.1
0.0g
700
Beertion
ltration
Inner level dimension
(a) Convergence and gradient er-
(b) Convergence analysis with vary-
(c) Computation cost per gradient step of varying problem size dy. We set 100 measure large-scale computation cost.
of Fully Fider Constrained ing gradient inexactness We the tradeoff of accuracy and convergence.
Bilevel Algorithms (F2CBA). We dx 100
set d 20
Figure 2: We run Algorithm 3 using Algorithm on the bilevel optimization in the toy example in Problem L. 200, and the Figure 2a, Figure 2b, Figure vary of
with varying upper-level variable dimensions da, fixed lower-level variahle dimension number of constraints Nesar d,/5 40, and accuracy a iterations, gradient exactness a, and d,,, respectively, to compare the performance under different settings.
We generate instances of the following constrained bilevel optimization problem:
minimize, cT y + 0.01 ||x|| + 0.01 | subject to y arg min z Qu + + Ppy (L.1) y:h(..w)
where h2(2, y) x A,y DT Vi [da] is dim bilinear constraint, where the constraint bilinear matrix A, Id by d for all [dr] are randomly generated from normal
37

---

distributions. The bilinear (nonlinear) constraint of the lower-level problem is the major difference compared the experiment Section 6. We are interested in whether our algorithms work beyond the linear constraints where our theory guarantees.
The rest of the parameters are the as in Section 6. The PSD matrix Q E R4, IRy P E Rd xdy, We compare our Algorithm 3 with a non-fully first-order method implemented using cvxpyLayer [18]. Both algorithms use Adam [90] to control the learning rate in gradient descent. All the experiments are averaged over ten random seeds.
NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We provide algorithms and corresponding theoretical guarantees for all our claims in the abstract. We provide experiments (and relevant code) as claimed.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
This is discussed in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they seale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
38

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, 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 impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The assumptions, theorem statements, and proof sketches are included in the main paper. The full proofs are included in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide our full code in the supplemental material, and it can be used to reproduce the experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data 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 large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
39

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code is included in the supplemental material and can be used to reproduce the experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/ public/ mublic/guides/ "oodeSumisssionn conoolicy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. wwtppcccpc//ccccccccccccccccctct wwwpc//gg///////eeocoooccc
/ttgg/de////oouubbiiiiinnnne Cooe/ubmiiieeeeeeeecc wwwsssssiiooooooooooo for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide this information in Appendix K.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
40

---

Justification:
We provide this in Section 6
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide this information in Appendix K.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics atttss://eeus wttpriipp..cppuubeee cctpublic/Ethtitiic heabblii/tthissuuiieee celuideeselllleeee ines?
Answer: [Yes]
Justification: Yes, the research conducted in 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 deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
41

---

Answer:
[NA]
Justification:
There is no societal impact of this work.
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 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 that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets g.g code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
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 used and, possible, include URL.
42

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.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, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing or research with human subjects is involved.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
43

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the 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.
44


Reviews:
[{"review_id": "aSOznU4PZY", "reviewer": "Reviewer_wH2u", "summary": "This paper studies the linearly constrained bilevel optimization problem and provides a fully first-order method with solid theoretical analysis. To approximate hypergradient, the penalty method seems novel to me and it is applied in two settings where the LL problem is linear inequality or equality constraints.", "questions": "1. Could the authors explain the design of Algorithm 2? Why is there a clip? \n2. Why do authors not include the experiment of Algorithm 4? \n3. Could authors compare the method in [a] though it studies the unconstrained bilevel optimization problem?\n[a] Yang Y, Xiao P, Ji K. Achieving ${O}(\\epsilon^{-1.5}) $ Complexity in Hessian/Jacobian-free Stochastic Bilevel Optimization.", "limitations": "Please check weaknesses and problems.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The presentation is pretty good and I feel easy to follow.\n2. Theoretical analysis is solid and rigorous.\n3. Code is provided.", "weaknesses": "1. The experiment does not seem sufficient.\n2. The checklist should be behind the appendix as I memorize.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very grateful to the reviewer for their effort in reviewing our submission and are encouraged by their positive assessment of our theory and presentation.\n\n---\n# Response to Questions\n\n\n---\n1. ## Intuition behind clipping\n\nIntuitively, the clipping ensures that consecutive iterates of the algorithm **reside within a $\\delta$-ball** of each other — this in turn allows for a guarantee in terms of $(\\delta, \\epsilon)$-Goldstein stationarity (which, as we recall, is defined in terms of gradients in a $\\delta$-ball). We remark that following this intuition, all previous papers on Goldstein stationarity, as discussed in the paper, also utilize normalized and/or clipped steps (a notable exception is [1], where the clipping was dropped by relaxing the stationarity notion accordingly).\n\n---------------------------------------------------------------\n\n2. ## Implementation \n\n We acknowledge that the implementation and testing of our algorithm for the setting in question is an extremely important task. That said, our focus in this section was primarily theoretical since before our result, there did not exist any work at all with finite-time theoretical guarantees using a first-order oracle for the problem in question. We hope to implement our algorithm and perform large-scale experiments in follow-up works. \n\n---------------------------------------------------------------\n\n\n3. ## Comparison with Yang-Xiao-Ji [2]\n\nThe core idea in both our paper and that by Yang-Xiao-Ji (and indeed, by all papers on bilevel optimization) is an efficient approximation of $\\frac{dy^\\ast}{dx}^{\\top} \\nabla_y f(x, y^\\ast)$. Recall that this term simplifies to $$\\frac{dy^\\ast}{dx}^{\\top} \\nabla_y f(x, y^\\ast)=-\\nabla_{xy}^{2}g(x,y^{\\ast})\\cdot\\nabla_{yy}^{2}g(x,y^{\\ast})^{-1}\\nabla_{y}f(x,y^{\\ast}).$$\n\nThe way the paper of Yang-Xiao-Ji handles this term is by **separately approximating parts** of this product: in particular, it approximates\n$\\nabla_{xy}^{2}g(x,y^{\\ast})$ via a finite-difference method and \nthe term $\\nabla_{yy}^{2}g(x,y^{\\ast})^{-1}\\nabla_{y}f(x,y^{\\ast})$\nby a linear system solver.\n\nIn contrast to this method, our paper **approximates the entire term**  via a novel application of the implicit function theorem. We now elaborate on this point by illustrating our method for the unconstrained setting. \n\nAs stated in our Equation (5.2), our approximation (for this unconstrained setting) of the term $\\frac{dy^\\ast}{dx}^{\\top} \\nabla_y f(x, y^\\ast)$ is \n$v_{x}:=\\frac{\\nabla_{x}g(x,y_{\\delta}^{\\ast})-\\nabla_{x}g(x,y^{\\ast})}{\\delta}$. To see the validity of this approximation, we first note that $\\lim_{\\delta\\rightarrow0}\\frac{\\nabla_{x}g(x,y_{\\delta}^{\\ast})-\\nabla_{x}g(x,y^{\\ast})}{\\delta}=\\nabla_{xy}^{2}g(x,y^{\\ast})\\cdot\\frac{dy_{\\delta}^{\\ast}}{d\\delta}\\vert_{\\delta=0}$.\nNext, to approximate $\\frac{dy_{\\delta}^{\\ast}}{d\\delta}\\vert_{\\delta=0},$ we\nobserve that $y_{\\delta}^{\\ast}:=\\text{argmin} (g(x,y)+\\delta f(x,y)).$\nApplying first-order optimality of $y_{\\delta}^{\\ast}$ and \ntaking the derivative with respect to $\\delta$ yields $\\frac{dy_{\\delta}^{\\ast}}{d\\delta}\\vert_{\\delta=0}=-\\left(\\nabla_{yy}^{2}g(x,y^{\\ast})\\right)^{-1}\\nabla_{y}f(x,y^{\\ast}).$ Combining this with the first step proves the claimed approximation. \n\nFinally, when measured according to the stationarity criterion of Yang-Xiao-Ji (in the unconstrained setting), our work's **oracle complexity** is $O(\\epsilon^{-1})$ (improving upon their result of $O(\\epsilon^{-1.5})$). \n\n----------------------------------\n\n# Conclusion\n\nWe again thank the reviewer for their time and effort. Please let us know if there are any further questions that we could help clarify!\n\n---------------------------------------\n\n# References \n\n[1] Zhang, Qinzi, and Ashok Cutkosky. \"Random scaling and momentum for non-smooth non-convex optimization.\" arXiv preprint arXiv:2405.09742 (2024).\n\n[2] Yang, Y., Xiao, P., & Ji, K. (2023). Achieving O (ε-1.5) complexity in hessian/jacobian-free stochastic bilevel optimization. In Proceedings of the 37th International Conference on Neural Information Processing Systems.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dfGqCI79pS", "reviewer": "Reviewer_pjir", "summary": "The paper provides algorithms for bilevel optimization with linear equality and inequality constraints. The main contribution is that the algorithms are fully first order and do not require Hessian computations. This is achieved by reformulating the linearly constrained bilevel optimization problem using the penalty method and assuming access to the upper-level variable $x$ and approximate dual optimal solution. In this setting an inexact gradient oracle for the problem is constructed. The authors provide stationarity guarantees for their algorithms under certain standard assumptions. They also describe how to use their inexact gradient oracle for non-convex non smooth optimization. The algorithms and theoretical results are backed by small set of proof-of-concept experiments.", "questions": "There is a lot of literature available on approximating Hessian computations faster for 2nd order methods (for example using iterative sketching etc.) though not necessarily for bilevel optimization. I would appreciate it if you can comment on such methods when compared to yours in terms of practicality.", "limitations": "Yes, the limitations have been clarified in the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1) Typically, hessian inverse computation is quite expensive and hence coming up with a fully first order method with guarantees for an optimization problem has both good theoretical and practical significance. The paper will be of interest to the community.\n2) The paper is written very nicely. There is a lot of clarity regarding the related works, notations, main contributions and techniques. Proof sketches are also provided for some results in the main paper. Though the paper is heavy on technical material, the organization makes it somewhat easier for the reader to follow the arguments. I am not exactly from the same research area but could follow most of the paper. \n3) I could not check all the proofs in details, but the main claims of the paper appear correct.\n4) Nonconvex non smooth optimization is encountered in many ML problems these days. The applicability of the inexact gradient oracle to these problems with guarantees may be of practical significance.", "weaknesses": "1) There are no experiments highlighting the effectiveness of Algorithm 2.\n2) The experiments given here are also only of a proof -of -concept nature and are not comprehensive. Some more comparisons with existing algorithms (based on time) and ablation studies may provide more insights regarding the practical applicability of the methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very grateful to the reviewer for their effort in reviewing our submission and are encouraged by their positive assessment of the theory, presentation, and significance of our work.\n\n---\n# Response to Weaknesses\n\n---\n1. ## Implementing Algorithm 2 \n\nIn our paper, we implemented the simpler algorithm (Algorithm 3). Per the reviewer's suggestion, we additionally implemented Algorithm 2 and repeated our experiments --- we have added the results in the pdf with our top-level response. These experiments show that Algorithm 2 outperforms both Algorithm 3 and the baseline cvxpylayer in terms of convergence, as suggested by our theory (see Theorem 4.2 and Theorem 4.3). We appreciate the reviewer’s suggestion and will update the paper with these experiments.\n\n---\n2. ## Large-scale implementation \n\nWe acknowledge the importance of testing our algorithms with large-scale experiments. However, our focus has primarily been theoretical since prior work had far weaker theoretical guarantees for our choice of stationarity and oracle. As the reviewer notes, our experiments indeed mainly provide a proof of concept for our algorithms.\n\nIn the code, we also have results on bilevel problems with bilinear constraints (in figures/exp_bilinear); in follow-up work, we hope to expand our implementation to a wider range of problems and large-scale experiments.\n\n---\n# Response to Questions \n\n---\n1. ## Hessian approximations \n\nThe key step in algorithms for bilevel programming is that of computing $\\frac{d y^\\*}{dx}$, which in turn is composed of the product of a matrix, an inverse Hessian, and vector --- this therefore is the primary computational bottleneck in these algorithms. As the reviewer suggests, there have been many approaches for Hessian approximations, including in the context of bilevel programming. \n\nFor instance, [1] uses conjugate gradient to compute the Hessian-inverse-vector product, [2] uses Neumann approximation (essentially a geometric series for approximating matrix inverse) to approximate the inverse Hessian, and [3] uses a method inspired by Gauss-Newton to approximate the Hessian as the outer product of the corresponding gradients. However, all these works deal with unconstrained bilevel programming. In constrained settings (e.g., the ones we consider), the Hessian becomes significantly more complicated, and it is unclear if these techniques would apply to them (but would, nevertheless, be an interesting question to consider). \n   \nAnother line of Hessian-free approaches by [4-6] uses value-function reformulation to circumvent the use of Hessians. Finally, we also mention the approach of [7], which approximates the Hessian-inverse-vector product by a linear system solver in conjunction with a finite difference. As we detail in our response to reviewer wH2u, the runtime of our algorithm (when applied in the unconstrained setting) improves upon that of this algorithm by [7]. It would be interesting to extend these approaches to the constrained setting we consider with our choice of stationarity and oracle access. \n\n\n---\n# Conclusion\n\nWe again thank the reviewer for their time and effort in raising thoughtful questions. Please let us know if there are any further questions that we could help clarify! \n\n---\n# References \n\n[1] Pedregosa, F. (2016). Hyperparameter optimization with approximate gradient. In International conference on machine learning. PMLR.\n\n[2] Lorraine, J., Vicol, P., & Duvenaud, D. (2020). Optimizing millions of hyperparameters by implicit differentiation. In International conference on artificial intelligence and statistics. PMLR.\n\n[3] Giovannelli, T., Kent, G., & Vicente, L. N. (2021). Bilevel stochastic methods for optimization and machine learning: Bilevel stochastic descent and darts. arXiv preprint arXiv:2110.00604.\n\n[4] Liu, B., Ye, M., Wright, S., Stone, P., & Liu, Q. (2022). Bome! bilevel optimization made easy: A simple first-order approach. Advances in neural information processing systems.\n\n[5] Kwon, J., Kwon, D., Wright, S., & Nowak, R. D. (2023). A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning. PMLR.\n\n[6] Yao, W., Yu, C., Zeng, S., & Zhang, J. Constrained Bi-Level Optimization: Proximal Lagrangian Value Function Approach and Hessian-free Algorithm. In The Twelfth International Conference on Learning Representations.\n\n[7] Yang, Y., Xiao, P., & Ji, K. (2023). Achieving O (ε-1.5) complexity in hessian/jacobian-free stochastic bilevel optimization. In Proceedings of the 37th International Conference on Neural Information Processing Systems.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jE5EsaFgGF", "reviewer": "Reviewer_GkWW", "summary": "This works deals with constrained bilevel optimization problems where the lower-level has linear inequality or equality constraints. A set of algorithms is developed that does not require access to the Hessian, but only to zeroth and first-order information. In the case of inequality constraints, convergence is established to an $(\\delta,\\epsilon)$-Goldstein stationary point, due to the non-smoothness of the problem, using $O(\\delta^{-1}\\epsilon^{-4})$ or $O(d\\delta^{-1}\\epsilon^{-3})$ oracle calls (d: dimension of the upper-level).For equality-constrained problems, the convergence rate is nearly optimal with a rate $O(\\epsilon^{-2})$.", "questions": "* In the gradient of the penalty function (3.5.), there is the term $\\nabla_x g^{\\ast}(x)$. How do you compute this gradient given that $g^{\\ast}(x)$ is a min function? The authors should explain this. \n* The authors should explain in more detail Algorithm 2. It is not clear what the utility of each step is.\n* The authors derive the equations for the gradient of $F$ and $y^{\\ast}(x)$ (eq. 3.3). However, as they note in section 1.1, the hyperfunction $F$ is non-smooth. Then, how can we derive a formula for the gradient of $y^{\\ast}(x)$? How do we determine if a given point is differentiable?\n* Perhaps the least common assumption in literature is Assumption 2.3. The authors should justify whether this assumption is easy to be satisfied. For instance, is it typically the case that the dual solution is bounded? How about the Lipschitz property of $y^{\\ast}(x)$? Are there other relevant (bilevel) works that use the same or similar assumption?\n* How does the cvxpyLayer baseline work? This is not explained clearly in the text, besides a minor reference in the Appendix. As this is the only baseline currently used, I believe that some more details are required.", "limitations": "* See weaknesses above.\n* The authors discuss limitations of their work in section 7.\n* No negative societal impact", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* This work makes progress in the topic of constrained (in the lower-level) bilevel problems, which is a challenging class of problems, much more difficult than unconstrained problems.\n* The development of first-order algorithms for bilevel problems with linear constraints in the lower-level. On the contrary, typically implicit gradient methods for (unconstrained or constrained) bilevel problems require access to the Hessian. In addition, for the case of inequality constraints there are no assumptions involving second-order derivatives.\n* The design of algorithms that deal with the non-differentiability of the hyperobjective F.\n* Some of the proposed algorithms (e.g., Algorithm 3) appears to be simple and easy to implement.", "weaknesses": "* A major weakness of this work is the small number of experiments. There is only a single example bilevel problem over which experiments are performed. In addition, there are no experiments on real applications (e.g., in machine learning).\n* In the experiments section the proposed method is compared only with a single baseline, which does not correspond to any published bilevel method. Why aren’t there any comparisons with other bilevel algorithms that deal with constrained bilevel problems? There are both value function and implicit gradient methods that can, at least in theory, deal with the example problem used here, e.g. [37,38]. \n* The algorithms require access to exact solutions of certain problems, such as $y^{\\ast}(x)$ of the lower-level or $y_{\\lambda^{\\ast},\\alpha}^{\\ast}(x)$ of problem (3.6). This is not the case in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are extremely grateful to the reviewer for their thoughtful questions and are encouraged by their positive assessment of our contributions, soundness, and presentation. \n\n---\n# Response to Weaknesses \n---\n1. ## Limited experiments.\n\nWe acknowledge the importance of testing our algorithms with large-scale experiments. However, our focus has primarily been theoretical since prior work had far weaker theoretical guarantees for our choice of stationarity and oracle. \n\nIn the code, we also have results on bilevel problems with bilinear constraints (in figures/exp_bilinear). Per reviewer pjir's suggestion, we have now implemented additional experiments for Algorithm 2 (please see the top-level response), which we will add to our paper. In follow-up work, we hope to expand our implementation to a wider range of problems and large-scale experiments.\n\n---\n2. ## Access to $y^\\*$ \n\nOur algorithm for the inequality setting indeed requires access to $\\lambda^\\*$ (the lower-level dual solution). In practice, though, we can easily approximate $\\lambda^\\*$ to high accuracy due to the linear convergence of strongly convex problems with linear constraints --- our experiments demonstrate our algorithm's robustness to the use of such approximations as proxy for the exact solution. That said, we believe that developing an algorithm for this problem without this assumption is an important direction for future work. \n\n---\n# Response to Questions \n\n---\n1. ## Computing $\\nabla_x g^*(x)$ \n\nWe compute this gradient as \n$\\nabla_x g(x,y^\\*) + \\nabla_x h(x,y^\\*)^\\top \\lambda^\\*$. \n\nFor some intuition, note that $g^\\*(x) := \\min_y \\max_{\\lambda \\geq 0} g(x,y) + \\lambda^\\top h(x,y),$ to which applying Theorem 4.13 from [1] immediately yields the claim. We will add this explanation in the text. \n\n---\n2. ## Explaining Algorithm 2\n  \nAlgorithm 2 is a variant of **gradient descent with momentum and clipping**, where $\\tilde{g}\\_{t}$ is the inexact gradient, $\\Delta\\_{t}$ is a clipped accumulated gradient (hence accounts for past gradients, which serve as a momentum), and the main iterate is updated as $x_{t+1}=x_t+\\Delta_t$. Similar algorithms have appeared in prior work on nonsmooth nonconvex optimization (e.g. [2]). However, none of them accounted for _inexactness_ in the gradient, crucial in the bilevel setting. We will add this in the final version. \n\n---\n3. ## Computing $\\nabla y^*(x)$ \n\nOur algorithm does not require actually computing $\\nabla y^*(x)$. The only place where $\\nabla y^*(x)$ appears is in our analysis when bounding the difference between our inexact and the actual hypergradients. We use $\\nabla y^*(x)$ to mean a Clarke subgradient of $y^{\\ast}$. We will clarify this better.\n\n---\n4. ## Assumption 2.3 \n  \nWe acknowledge that this assumption is somewhat technical — however, prior work also imposes similar assumptions. For instance, Khanduri et al [3] assume (weak/strong) convexity of the *hyperobjective* $F$ to obtain finite-time guarantees --- our assumption is strictly weaker. Further, Yao et al [4] also assume boundedness of the optimal dual variable. \n\nAs to $y^\\*(x)$ being Lipschitz, there are some useful settings with this property: e.g., if the lower level feasible region $Y(x):=\\\\{y: h(x,y) \\leq 0\\\\}$ is independent of $x$, an argument in [5] shows it to be $\\frac{C_g}{\\mu_g}$ Lipschitz. The situation is more complicated when $Y(x)$ changes with $x$. If $g(x, y)$ is quadratic in $(x,y)$ (e.g., in model predictive control),  $y^\\*(x)$ is piecewise affine and Lipschitz [6]. For more general settings, this is related to sensitivity analysis, and some constraint qualifications can establish the property [7].  \n\n---\n5. ## cvxpyLayer\n  \ncvxpylayer is a Python library [8, 9] that uses a second-order method to compute the derivative of the optimal solution $y^*(x)$ of a parametric convex program with respect to the parameter $x$. We invoke cvxpylayer on the lower-level problem (which is parametrized by $x$) to compute $\\frac{dy^*(x)}{dx}$. We will add more details in the text. \n\n---\n# Conclusion \n\nWe again thank the reviewer for their time and effort in bringing up pertinent questions; we will incorporate these answers in our paper.\n\nPlease let us know if any questions remain. If we adequately answered all the questions, we would like to respectfully ask the reviewer to re-consider their score. We are happy to answer any further questions.\n\n---\n# References \n\n[1] Bonnans, J. F., & Shapiro, A. (2013). Perturbation analysis of optimization problems. \n\n[2] Cutkosky, A., Mehta, H., & Orabona, F. (2023). Optimal stochastic non-smooth non-convex optimization through online-to-non-convex conversion. ICML\n\n[3] Khanduri, P., Tsaknakis, I., Zhang, Y., Liu, J., Liu, S., Zhang, J., & Hong, M. (2023). Linearly constrained bilevel optimization: A smoothed implicit gradient approach. ICML\n\n[4] Yao, W., Yu, C., Zeng, S., & Zhang, J. (2024) Constrained Bi-Level Optimization: Proximal Lagrangian Value Function Approach and Hessian-free Algorithm. ICLR.\n\n[5] Nesterov, Yu. Smooth minimization of non-smooth functions. Mathematical programming (2005).\n\n[6] Borrelli, F., Bemporad, A., & Morari, M. (2017). Predictive control for linear and hybrid systems. \n\n[7] Minchenko, L. I., and P. P. Sakolchik. Hölder behavior of optimal solutions and directional differentiability of marginal functions in nonlinear programming. Journal of optimization theory and applications (1996).\n\n[8] Amos, Brandon, and J. Zico Kolter. Optnet: Differentiable optimization as a layer in neural networks. ICML, 2017.\n\n[9] Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., & Kolter, J. Z. (2019). Differentiable convex optimization layers. Advances in neural information processing systems.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7p7VhPOVuo", "reviewer": "Reviewer_c7kZ", "summary": "This paper studies fully first-order methods for bilevel optimization with strongly convex lower-level objectives and linear lower-level constraints, including both inequality constraints and equality constraints. For linear inequality constraints, the paper used a penalty methods to construct hypergradient estimators and demonstrate the approximation error. Then combined with a gradient method for nonsmooth nonconvex optimization to obtain a Goldstein stationarity point. While for linear inequality constraints, the paper proposed to use zeroth-order approximation of the hyper-gradient and demonstrate complexity.", "questions": "1. In the Alg 3 perturbed GD, what is the intuition to use perturbed GD instead of just inexact GD $\\tilde \\nabla F(x_t)$. In other words, why one needs to perturb using samples from sphere distribution?\n2. In Sec 3, although the problem is nonsmooth and nonconvex, given Thm 3.3, I would assume that the $\\nabla F(x)$ exists but it is not Lipschitz continuous? \n3. Please be specific about Lipschitz, i.e., does it mean Lipschitz continuous or Lipschitz smooth.\n4. What is the reason to consider zeroth-order methods in the linear equality constrained setting? Is it possible to derive fully first-order gradient estimator for the linear equality constrained setting? If possible, why not do it? \n5. In Sec 3.1, assuming knowing $\\lambda^*$ means that one also knows $y^*$ and $g^*$. \n6. The definition of complexity is not very clear. In line 229, it says solving a single smooth and strongly convex optimization problems amounts to $\\tilde O(1)$ oracle calls. But line 226 implies that one of such oracle call requires $\\epsilon^{-1}$ gradient evaluations. Then in line 322, the complexity seems to become $O(log(1/\\epsilon))$. Please specify how expensive to obtain $y^*$ and $\\lambda^*$ in an $\\epsilon$ error and clean oracle calls and complexity bounds in a consistent manner. \n7. What is the motivation of (5.3) the perturbed lower-level problem? \n8. Alg 1 requires computing $y^*_{\\lambda^*,\\alpha}$, this requires either $f$ to be convex in $y$ or requires $\\alpha$ to be large enough to ensure $\\mathcal{L}$ is convex in $y$. Please specify explicitly the requirements. Is $\\mathcal{L}$ strongly convex in $y$?\n\nI am happy to raise the score if these issues are well-addressed.", "limitations": "The paper includes several settings. Yet why adapting a specific strategy to solve each setting is not sufficiently motivated. Such as why one needs to use Alg 2 and Alg 3 instead of directly using the hypergradient estimator with gradient descent. Why one needs to use zeroth-order oracle for the linearly equality constrained setting instead of first-order oracle?", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "1. The paper considered both linear inequality and equality constraints. \n2. The hypergradient construction in the linear inequality constraint setting is interesting and the paper provides approximation guarantees. It would be useful for follow-up papers. \n3. Obviously, the complexity bounds are not yet optimal. But the paper has contributed several interesting directions that worth further exploration. \n3. Algorithm 5 uses zeroth-order oracle is very smart as in many bilevel problems, the dimension of the upper-level is small such as hyperparameter optimization. \n3. The finite-difference gradient proxy for the linear equality constrained case is also interesting.", "weaknesses": "1. How to solve linear inequality constrained case with simple gradient methods to achieve optimal complexity bounds still remain unknown. The current algorithm is a bit complicated and hard to tune in practice. \n2. It is unclear if the complexity bounds are optimal for both linearly inequality and equality constrained settings. Following the conventional notation for stationarity such that $||\\nabla F(x)||\\leq \\epsilon^2$, the complexity bound for Alg 1 is $O(\\epsilon^{-8})$, for Alg 2 is $O(\\epsilon^{-10})$ if further taking into account the complexity to get $tilde \\nabla F$, and for Alg 3 is $O(\\epsilon^{-4})$. Note that the paper consider deterministic bilevel optimization, it implies that there are a lot of room for improvements. The paper should mention comparison to unconstrained lower-level bilevel optimization so that readers know the results can be improved. Despite the complexity bounds, I still believe that this paper makes good contribution to the community of bilevel optimization.\n3. The methods proposed in the paper are not aligning with each other well. Despite the constrained lower-level bilevel optimization setting, the paper lacks a coherent narrative in terms of algorithmic design.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are extremely grateful to the reviewer for their thoughtful questions and are encouraged that they found numerous aspects of our contribution interesting and useful for follow-up papers.\n\n---\n# Response to Weaknesses\n---\n1. ## Complexity of Algorithms.\n\n    We agree with the reviewer that some of our results are probably suboptimal in terms of convergence rates. Nonetheless, we wish to point out that our rate for the linear equality case is in fact optimal. Moreover, despite this suboptimality, ours is the first result with dimension-free rates for these settings for our choice of stationarity and oracle. We will add an explicit comparison with the unconstrained setting.\n\n---\n2. ## Coherence of narrative.\n\n    We thank the reviewer for raising this valid point. Our algorithm for the linear *equality* case crucially relies on our novel observation that the hyperobjective $F$ is smooth; in contrast, this does not necessarily hold in the linear *inequality* case. Therefore, the two cases require different approaches, and unifying them would be an interesting future direction. We will clarify this better.\n\n---\n# Response to Questions\n---\n1. ## Need for perturbation.\n\n      Because we do not assume a bound on the smoothness of the hyperobjective (a strong assumption by several prior works), it is known [1] to be impossible to optimize $F$ directly in general – in particular by inexact GD, as suggested. \n\n   Since the hyperobjective is Lipschitz (cf. Lemma 4.1), it is differentiable almost everywhere by Rademacher's theorem; we can therefore implicitly optimize its uniform smoothing via random perturbations. This method of using perturbations to avoid non-differentiable points is widely used in the literature on nonsmooth optimization. We will clarify this.\n\n---\n2. ## Meaning of ${\\nabla} F$.\n  \n   We thank the reviewer for pointing out this subtlety, which we will better explain: As correctly noted, $F$ can be nonsmooth nonconvex; in this setting, algorithms generally require a subgradient, i.e., an element of the Clarke subdifferential (see Definition 2.1), which is what we mean by $\\nabla F$ (which, as the reviewer notes, is not Lipschitz continuous). Furthermore, the $\\tilde{\\nabla} F$ we construct is such that its distance to some subgradient of $\\nabla F$ is at most $\\alpha$.\n\n---\n3. ## Lipschitz notation.\n    \n    We acknowledge the confusion caused by our notation and will switch all notations to either $L$-Lipschitz or $S$-smooth. \n\n---\n4. ## Zeroth-order approach for linear equality setting.\n\n    We apologize for the confusion: Please note that for the linear equality case, our algorithm accesses $\\nabla f$ and $\\nabla g$, which makes it first-order. So, even though it *looks* like a zeroth-order approach (due to the finite differences), it is actually a first-order method. We will clarify this. \n\n---\n5. ## Assumption on $\\lambda^\\*$.\n\n    Access to $\\lambda^\\*$ indeed implies access to $y^\\*$. That said, the core difficulty in bilevel programs is access to $\\frac{d}{dx}y^\\*$. Our technical novelty is precisely to approximate this first-order oracle. Moreover, in practice, we can easily approximate $\\lambda^\\*$ to high accuracy due to the linear convergence of strongly convex problems with linear constraints --- our experiments demonstrate our algorithm's robustness to the use of such a proxy for $\\lambda^\\*$. \n\n---\n6. ## Clarifying complexity.\n\n    The notation $\\tilde{O}(1)$ in Line 229 refers to $\\log(1/\\epsilon)$, matching the cost in Line 322 — We apologize for our oversight in not stating this and will fix it. Next, the complexities in Lines 226 and 229 are for different operations: Line 226 is the cost of estimating $\\nabla F(x)$ and Line 229 that of estimating $F(x)$. For the linear inequality case, the ACGD method in [2] implies linear rate to obtain $y^\\*$ and $\\lambda^\\*$. We will explicitly state these. \n\n---\n7. ## Motivating the perturbed lower-level problem.\n\n   For intuition on the perturbation, we demonstrate our method in the unconstrained setting. Let $y_{\\delta}^\\*:=\\text{argmin} (g(x,y)+\\delta f(x,y)).$  Optimality of $y_{\\delta}^\\*$ and differentiating w.r.t. $\\delta$ yields $$\\frac{dy_{\\delta}^\\*}{d\\delta}=-\\left(\\delta\\cdot\\nabla_{yy}^{2}f(x,y_{\\delta}^{\\ast})+\\nabla_{yy}^{2}g(x,y_{\\delta}^{\\ast})\\right)^{-1}\\nabla_{y}f(x,y_{\\delta}^{\\ast}), \\implies \\frac{dy_{\\delta}^{\\ast}}{d\\delta}\\vert_{\\delta=0} = -\\left(\\nabla_{yy}^{2}g(x,y^\\*)\\right)^{-1}\\nabla_{y}f(x,y^\\*).$$\n\n   Therefore, \n   $$v_{x}:=\\frac{\\nabla_{x}g(x,y_{\\delta}^{\\ast})-\\nabla_{x}g(x,y^{\\ast})}{\\delta}\\approx \\lim_{\\delta\\rightarrow0}\\frac{\\nabla_{x}g(x,y_{\\delta}^{\\ast})-\\nabla_{x}g(x,y^{\\ast})}{\\delta}=\\nabla_{xy}^{2}g(x,y^{\\ast})\\cdot\\frac{dy_{\\delta}^{\\ast}}{d\\delta}\\vert_{\\delta=0} = \\frac{dy^\\*}{dx}^{\\top} \\nabla_y f(x, y^\\*)$$ is a valid gradient proxy. Thus, the motivation behind the perturbation is to allow for the construction of a hypergradient approximation by an application of the implicit function theorem. \n\n---\n8. ## Strong convexity of $\\mathcal{L}$.\n\n    $\\mathcal{L}$ is strongly convex when $\\alpha_1 > C_f / \\mu$. This may be deduced from the smoothness and strong convexity of the components of $\\mathcal{L}$. We will clarify this.\n\n---\n# Conclusion\n\nWe again thank the reviewer for their effort in raising pertinent questions; we will incorporate these answers in our paper. \n\nPlease let us know if any questions remain. If we adequately answered all the questions, we would like to respectfully ask the reviewer to re-consider their score. We are happy to answer any further questions.\n\n---\n# References\n\n[1] Kornowski, G., and Shamir, O. Oracle complexity in nonsmooth nonconvex optimization. JMLR (2022).\n\n[2] Zhang, Z., & Lan, G. (2022). Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We are grateful to all the reviewers for well-thought-out reviews of our submission, appreciation of our ideas, and constructive efforts in helping us strengthen our work. We address all questions and remarks by responding directly to each review (and will incorporate all suggestions). Here we briefly reiterate our key contributions.

---
# Contributions 

1. For linear-equality-constrained bilevel problems, we provide a first-order method via a novel application of the implicit function theorem. Our rate of convergence for this problem is optimal.

2. For linear-inequality-constrained bilevel problems, assuming access to the optimal dual variable, we provide a first-order method with finite-time guarantees on convergence to a Goldstein stationary point of the hyperobjective. 

3. Along the way, we design an algorithm for nonsmooth nonconvex optimization with an inexact gradient oracle, which could be of independent interest. 

---
# Additional Experiments 

Following reviewer pjir's suggestion, we implemented our algorithm for nonsmooth nonconvex optimization with an inexact gradient oracle (Algorithm 2). As suggested by our theory, Algorithm 2 outperforms both Algorithm 3 and the baseline cvxpylayer in terms of convergence rate. We provide these results in the attached PDF and will include them in our paper.

In the code, we also have results on bilevel problems with bilinear constraints (in figures/exp_bilinear). Overall, our experiments mainly provide a proof of concept for our algorithms. In follow-up work, we hope to expand our implementation to a wider range of problems and large-scale experiments. 


---

Meta-review: This work studies constrained bilevel optimization problems, for which it presents fully first-order methods (thereby avoiding Hessian computations). There is overall consensus among the reviewers that this is an interesting work that is worthy of acceptance, and I am inclined to agree. It would be strongly suggested that, for the camera-ready version, the authors clarify the presentation/conventions of the convergence bounds, in order to better facilitate comparison with existing upper and lower bounds.
Decision: Accept (poster)