Linearly Constrained Bilevel Optimization: A Smoothed Implicit Gradient Approach
Authors: Prashant Khanduri
Ioannis Tsaknakis
Yihua Zhang
Jia Liu
Sijia Liu
Jiawei Zhang
Mingyi Hong
Venue: Submitted to ICLR 2023 (2023)

Abstract: This work develops analysis and algorithms for solving a class of bilevel optimization problems where the lower-level (LL) problems have linear constraints. Most of the existing approaches for constrained bilevel problems rely on value function based approximate reformulations, which suffer from issues such as non-convex and non-differentiable constraints. In contrast, in this work, we develop an implicit gradient-based approach, which is easy to implement, and is suitable for machine learning applications. We first provide in-depth understanding of the problem, by showing that the implicit objective for such problems is in general non-differentiable. However, if we add some small (linear) perturbation to the LL objective, the resulting problem becomes differentiable almost surely. This key observation opens the door for developing (deterministic and stochastic) gradient-based algorithms similar to the state-of-the-art ones for unconstrained bi-level problems. We show that when the implicit function is assumed to be strongly-convex, convex and non-convex, the resulting algorithms converge with guaranteed rate. Finally, we experimentally corroborate the theoretical findings and evaluate the performance of the proposed framework on numerical and adversarial learning problems. To our knowledge, this is the first time that (implicit) gradient-based methods have been developed and analyzed for the considered class of bilevel problems.

Under review as a conference paper at ICLR 2023
LINEARLY CONSTRAINED BILEVEL OPTIMIZATION: A SMOOTHED IMPLICIT GRADIENT APPROACH
Anonymous authors
Paper under double-blind review
ABSTRACT
This work develops analysis and algorithms for solving class of bilevel optimization problems where the lower-level (LL) problems have linear constraints. Most of the existing approaches for constrained bilevel problems rely on value function based approximate reformulations, which suffer from issues such as non- convex and non-differentiable constraints. In contrast, in this work, we develop an implicit gradient- gradient-based approach, which is easy to implement, and is suitable for machine learning applications. We first provide an in-depth understanding of the problem, by showing that the implicit objective for such problems is in general -on-differentiable. However, if we add some small (linear) perturbation the LL objective, the resulting implicit objective becomes differentiable almost surely. This key observation opens the door for developing (deterministic and stochastic) gradient-based algorithms similar to the state-of-the-arr ones for unconstrained bi-level problems. We show that when the implicit function assumed to be strongly-conves, convex and weakly-convex, the resulting algorithms converge with guaranteed rate. Finally, we experimentally corroborate the theoretical findings and evaluate the performance of the proposed framework learning problems. To our knowledge, this is the first time that (implicit) gradient- based methods have been developed and analyzed for the considered class of bilevel problems.
numerical and adversarial
INTRODUCTION
Bilevel optimization problems (Colson al. 2005 Dempe & Zemkoho 2020) can be used model an important class of hierarchical optimization tasks with two levels of hierarchy, the upper-level (UL) and the lower-level (LL). The key characteristies of bilevel problems are: 1) the solution of the UL problem requires access to the solution of the LL problem and, 2) the LL problem is parametrized by the UL variable. Bilevel optimization problems arise in a wide range of machine learning applications. such as meta-lcarning (Rajeswaran et al.) 2019 Franceschi et al. 2018). data
hypercleaning (Shaban et al. 2019), hyperparameter optimization (Sinha et al.) 2020 Franceschi
et al. 2018. 2018.2017] Pedregosa 2016), adversarial learning (Li et al. 2019 Liu et al.] |021a] Zhang ct al. 2021), as well as in other application domains such as network optimization (Migdalas 1995 J
economics (Cecchini et al., 2013), and transport research (Didi-Biha et al., 2006 Kalashnikov et al. 2010). In this work, we focus on a special class of stochastic bilevel optimization problems, where the LL problem involves the minimization of strongly conver objective over set of linear inequality constraints. More precisely, we consider the following formulation:
min G(x) = f(x,y (x)) = Re[F(xx xx (x): xEX
(1a)
s.t. (x) E arg min
{ [xxx))) | Ay - b).
(Ib)
yER*
where { ~ DD represents stochastic sample of the objective f(,, :), X C Rd is convex and closed set, f: : x d - R is the UL objective, h : X' x Rd - R is the LL objective, and f. h are smooth functions. We focus the problems where h(x, y) is strongly convex with respect y. The matrix A E Axd, and vector b E R define the linear constraints. In the following, we refer to (Ta) as the UL problem, and (lb) as the L.I one.

---

Under review as a conference paper at ICLR 2023
The success of the bilevel formulation and its algorithms in many machine learning applications can be attributed to the use of the efficient (stochastic) gradient- based methods (Liu et al. 2021a). These methods take the following form, in which an (approximate) gradient direction of the UL problem is computed (using chain rule), and then the UL variable is updated using gradient descent (GD):
GG(x) ~ V= + V [x)]² Vxf((xx" (x)) GD Update:x" -x- (2)
The gradient of G(x) often referred as the implicir gradient. However, computing this implicit gradient not only requires access to the optimal y yx)), but also assumes differentiability of the mapping y" (x) : X + _dd,, One can potentially solve the LL problem approximately and obtain an approximation (xx such that (xx) R y" (x), and use it to compute the implicit gradient (Ghadimi & Wang 2018). Unfortunately, not all solutions y" (x) are differentiable, and when they are not the above approach cannot be applied.
It is known that when the LL problem is strongly convex and unconstrained, then Vy (x) can be easily evaluated using the implicit function theorem (Ghadimi & Wang 2018). This is the reason that
the majority of recent works have focused on developing algorithms for the class of unconstrained
bilevel problems (Ghadimi & Wang. 2018 Hong al.) 2020 Ji et al. 2021 Khanduri et al.) [202bb]
Chen et al.
2021a). However, when the LL problem is constrained, Vy" Vy*(x) might not even exist. In
that case, most works adopt value function-based approach to solve problems with LL constraints methods typically transform the original problem into a single-level problem with non-convex and non- non-differentiable constraints. To resolve the latter issue these approaches regularize the problem by adding a strongly- convex penalty term, altering the problem's 's structure. In contrast, we introduce a perturbation-base smoothing technique, which at any given x E X makes y (x) differentiable almost surely, without practically changing the landscape of the original problem (see (Lu et al. 2020, pg. 5)). It is important more suited for deterministic implementations,
(Luu et al.
2021b: Sow et al.. 2022 Liu et al. (021c).. calle-function-baane
to note that the value function-based approaches and therefore is difficult to use such algorithms for large scale applications and/or when the data sizes are large. On the other hand, the gradient-based based algorithms developed in our work can easily handle stochastic problems. Finally, there is a line of work (Amos & Kolter 2017]] Agrawal et al. 2019: Donti et al. 2017 Gould al., 202T) about implicit differentiation in deep learning literature. However, in these works the setting (e.g. Tayers of neural network described by optimization tasks) and the focus (c.g.. on gradient computation and implementation, rather than on algorithms and analysis) is different. For more details see Appendix A
Contributions. In this work, we study a class of bilevel optimization problems with strongly convex objective and linear constraints in the LL. Major challenges for solving such problems are the following: 1) How to ensure that the implicit function G(xx is differentiable? and 2) Even the implicit function is differentiable, how to compute its (approximate) gradient in order to develop first-order methods? Our work addresses these challenges and develops first-order methods to tackle such constrained bilevel problems. Specifically, our contributions are the following:
We provide an in-depth understanding of bilevel problems with strongly convex linearly constrained L.L. problems. Specifically, we first show with an example that the implicit objective G(x) is in general non non-differentiable. To address the non-differentiabiiity we propose a perturbation- based smoothing technique that makes the implicit objective G(x) differentiable in an almost sure sense, and we provide closed-form expression for the (approximate) implicit gradient.
The smoothed problem we obtain is challenging, since its implicit objective does not have Lip- schitz continuous gradients. Therefore, conventional gradient based algorithms may no longer work. To address this issue, we propose the Deterministic Smoothed Implicit Gradient (DD]SGGD) method that utilizes an (approximate) line search-based algorithm and establish asymptotic con- vergence guarantees. We also analyze [S]SIGD for the stochastic version of problem (I (with fixed/diminishin step-sizes) and establish finite-time convergence guarantees for the cases when the implicit function is weakly-
strongly-comee and convex (but not Lipschitz smooth).
Finally, we evaluate the performance of the proposed algorithmic framework via experiments on quadratic bilevel and adversarial learning problems.
Bilevel problem I
captures several important applications. Below we provide two such applications.
Adversarial Training, The problem of robustly training a model o(x; c), where x denotes the model parameters and the input to the model; let {(c,, d with e; E RR4,, d, E R be the training set (Zhang al. 2021 Goodfellow et al. 2014). It can be formulated as the following bilevel problem:
2

---

Under review as a conference paper at ICLR 2023
N h +y),
N
+ di) s.t. (*(x)
arg min
min KERdy
i=1 s.t. -b-ysb
y, 4
(3)
where y = -X] E IR with y; Rel, denotes the attack on the 1hh example and we have Σ N de, = de. Moreover, : x R + denotes the loss function for learning the model parameter X, while h4 : R x IR - R denotes the adversarial objective used to design the optimal attack y. Note that the linear constraints in the I.I. problem -b S S models the attack budget.
Distributed Optimization. In distributed optimization (Chang et al. 2020 Yang et al. 2019), set of N agents aim to jointly minimize an objective function Gix) over an undirected graph G (V, E).
We consider the following distributed bilevel problem
min (xxEX]Ax=0)
{G(x) = Σ (X s.t. (x) E arg min yER's
Σ h (x, s.t. Ay = 0}.
XN] and y Yyl. Each agent i E [N] has access to Si and h;, The constraint Ay (resp. Ax = 0) introduced to ensure the consensus LL (resp. UL) variables. Such problems arise in signal processing and sensor networks (Yousefian (021). This formulation also models a decentralized meta learning problem where the training and validation data is distributed among agents while each agent aims to solve the meta learning problem globally (Ji et al. 2021).
where x =
2 PROPERTIES AND IMPLICIT GRADIENT OF BILEVEL PROBLEM 1
2.1 PRELIMINARIES
In this section we study the properties of problem ! First, let us define the necessary notations. Let A(y) be the matrix that contains the rows S(y) (1,---,k)) k.) of A that correspond the active constraints of inequality Ay < b in the LL problem, that is we have A(y)y b(y), where b(y) contains the elements vector that corresponds to the active constraints at yx( Next, we introduce some basic assumptions.
with indices in S(y). Also, we denote with X (xx the Lagrange multipliers
Assumption 1. We assume that the following conditions hold for problem
(a) yxx,y) is continuously differentiable, and h(x, y) is twice continuously differentiable. (b) X is closed and convex; y {y 1Rd Ay S b} a compact set.
(c) y( is strongly convex in y, for every E X, with modulus ph-
(d) There exists y E [R such that Ay < b.
(e) Aly" (x)) is full row rank, for every E 2
The Assumptions ][ a (b) and [c] are standard assumptions in bilevel optimization literature and are required to ensure the continuity of the implicit function (Proposition (1. Assumption c ensurrs that the implicit function G(x) is well defined as the LL problem returns a single point. Assumption
d(d) ensures strict feasibility of the LL problem, while Assumption [[ implies that the rows of A corresponding to the active constraints are linearly independent. Note that this assumption is necessary to ensure the differentiability of the implicit function (Lemma 12 Also note that there are some special cases in which Assumption [[ is automatically satisfied. For instance, consider problem where the I.I. problem has box constraints, i.e., a S y S Then for any y E y the only possible non-zero values in the matrix A(y) are +1, 11, and there is only one non-zero value at each column. Therefore, A(y) is full row rank. Next, we utilize the above assumptions to analyze the properties mapping y" (x).
Proposition (Appendix D.I.Ib. Under Assumption 1 the mapping y (x) X implicit function G(x) are both continuous.
I and the
Proposition I ensures that y (x) and G(x) are both continuous. Now if can ensure differentiability of y" (x), then we should be able to implement a gradient-based update rule to solve 1 However,
as the following example illustrates, y" (x) and thus G(x) are not differentiable in general.
This LJCQ condition Rersekas 1998 the problem. used to ensure the optimal solutions satisfy KKT conditions.
3

---

Under review as a conference paper at ICLR 2023
Example. Consider the following problem
min x + V (x) s.t. D7' (a)) arg min { - 22) 3/5 S S 1). se[0.11
(4)
yER
Orginal
The mapping ("(x) is 1
(x) (z)
x. if E I/3/5, 1). and T (x)
v3/5. if æ E [0, 3//5.. . In Figure | we plot this mapping. Notice that at the point x 3/5 5 the mapping (and thus the implicit function) is -on-differentiable.
0.80
0.88
To address the non-differentiabiiit issue, we introduce a perturbation-baset "smoothing" technique. Specifically, for any fixed x E X, we modify the L.I objective 1xx, with the addition of the linear perturbation term q" y, where q is a random vector sampled from some continuous distribution Q. We use the following notation for the "smoothed" LL objective
0.70
0.75
0.60
0.6
Figure I: Plot of y (x).
g(x. y) = h(x, y) + q and (x) == arg min(g(x,)) Ay S b).
(5)
yER"
Also, we denote F(x) == y(x,,"(x) (x)) as the respective "smoothed" implicit function. Such a perturbation is used to ensure that at given x E X, the striet complementarity (SC) property holds for the LL problem with probability 1 (w.p. 1); see the lemma below for the formal statement.
y
Lemma 1. (LLu et al. 2020 Proposition 1)) For a given N. y is a KKT point of problem giny g(x, y), : q is generated from continuous measure, and Aly" (x)) is full row rank, then the SC condition holds at x. with probability (w.p. 1).
Combining SC ensured by Lemmal I with Assumption 1, we can show that the implicit mapping y (x) is (almost surely) differentiable, which further implies that the implicit function F(x) is differentiable at given X, and obtain closed-form expression for the gradient (Lemma 2). We would like to stress that the properties mentioned above (i.e., SC and differentiabilityy) are defined locally, at a given point x E X. These properties will be used later to design algorithms that approximately optimize the original problem ( Finally, it is worth noting that, in the absence of such perturbation term, we would have to introduce the SC property as an assumption.
2.2 IMPLICIT GRADIENT
In this section, we derive closed-form expression for the gradient of the implicit function F(x).
Lemma (Implicit Gradient, Appendix D.1.2). Under Assumption 7 for any given x E X, we have
Vx*()) = [V 1 (x))
[ --
v2 2 V
(x)) A VX (x)
(6)
VA (x) = [A[V v V (x)) ' [A (x (x))
2n (x))
(7)
where we set A = (x)).
Note that when LL problem (b)) does not have the LL constraints, the implicit gradient derived in
Lemma becomes exactly same as the one in Ghadimi & Wang (2018); Ji et al, (2021) Moreover, if
the LL problem has only linear equality constraints, the differentiability of y yx() follows from the implicit function theorem under Assumptions
[ and
[[]] along with full row rankness of A. In
fact, the expression of the implicit gradient stays the same as in Lemma with 7 and X Xx(x) replaced by A and X (x), respectively (i.c., we use the full matrix A). Finally, using Lemma above we now have expression of the implicit gradient
VF(x) =
(Vy (,))""
2.2.1 APPROXIMATE IMPLICIT GRADIENT
Note that computing V Fxx) requires the precise knowledge of y (x) which is not possible for many problems of interest. Therefore, practice we define the approximate implicit gradient as
F( V. (x.((x
(xx))))
(9)
4

---

Under review as a conference paper at ICLR 2023
where (x) is defined by setting the approximate LL solution f(x) in place of the exact one y (x)
in expressions (6) and (7). In order to ensure that (9) returns a useful approximation of the (exact) implicit gradient, impose few assumptions on the quality of the estimate (xx).
Assumption 2. The approximate solution of (perturbed) LL problem
5 (xx) satisfies the following
Vx E X:
(a) 18((x) - y")x)l & 6 for > 0,
(b) f(x) is a feasible point, i.e., AA(x) S b.
(c) It holds that A(y
(()()))
The LL problem requires the solution of a strongly convex linearly constrained task. As a result, Assumption A (b) can be easily satisfied. Specifically, we obtain approximate feasible solutions of given aecuracy with known methods, such as projected gradient descent, or by using some convex optimization solver; in section [B the Appendix we provide one such method. Moreover, Assumption
[[ will be satisfied if we find a "sufficiently accurate" solution (x). Specifically, from Calamai & Moré (1987 Theorem 4.1) we know that if 5 (x) y is an arbitrary sequence that converges to a non-degenerate (i.e., Assumption
e and SC holds) stationary solution y" (x), then
there exists an integer ko such that A(y (x)) A(y (x)). Ak > ko-
Remark 1. There are certain special cases where we can obtain an upper bound for kn- For instance,
in the case of non-negative constraints y 2 0 it can be shown P that La log (2Lnlly" -y" -x(x))l/T) iterations of the projected gradient descent method suffice to ensure that the active set of the approximate solution y(x) coincides with the active set of the exact one y" (x) (see et al. (001
pa
Corollary 1)), where T = millie Sty"ssi"""" (x)) V ",,((xy"" (x)) and y" is the algorithm' 's initialization. A similar result can be derived for the case with bound constraints a S b.
Next, we introduce additional assumptions that are required to analyze the properties of ! Assumption 3. We assume that the following holds for problem Vx, X E X' and y. E R (a) f has bounded gradients, i.e., [x, y) II S Ly.
(b) f has Lipschitz continuous gradients, i.e., fx, (xx,))) S L,ll(x yll
(c) h has Lipschitz continuous gradient in y, i.e., |1 vy,((xy)) - V, y) S LA lly y/1.
(d) h has Lipschitz continuous Hessian in i.e., V/ un h(x,y) - - F) S L lly F/1
(e) & has Lipschitz continuous Jacobian, i.e. V h(xx - Vay 3) S L ll y11-
x3y h(x, Y) S T.key- ()) h has a bounded Jacobian, V
Assumption Biss standard in bilevel optimization literature (Ghadimi & Wang 2018 Hong et al. 2020 Chen et al. a0 Ji al. 2021) and is used to derive some useful properties of the (approximate)
implicit gradient (Lemmal 3 Appendix D.I.3). It is easy to see that Assumptions a and hold
directly for the perturbed objective (5) with constants Hg = -hh Ln. Ly Lowx Liy Lgzy
Lhaa Iggay = -Inay: we also assume that Assumption [() holds for the perturbed LL problem 5
Lemma 3 (Appendix D.1.3). Suppose that Assumptions 123 hold. Then, for every x E X the following holds
[[FF(x)] S LF, where LF Ly + by- Ly + LyL and LF Ly- Ly; the constants Ly=, Ly- are defined in Lemmas respectively, provided in the Appendix.
[(F(() VF S -
[VF(()] & LF and
2.2.2 STOCUASTIC IMPLICIT GRADIENT
In the stochastic setting, the (approximate) stochastic implicit gradient is computed as:
()(x (x + (x)) V,, {x)):
(10)
Also, we make the following assumption on the stochastic gradients of the UL problem.
Assumption We assume that the stochastic gradients are unbiased, i.e. BelV](x, =
Vf(x,)) and have bounded variance, i.e., Eg V vf(x,))] = of for some of > 0.
Under the assumption that V Vx, (x)) > 0, Vi e S(y (x)).
5

---

Under review as a conference paper at ICLR 2023
Algorithm 1 [Deterministic] Smoothed Implicit Gradient Descent (DD]SGGD)
Input: Initial parameter xº, # of iteration T, LL solution accuracy, 8", o, measure 2,
2: Sample Q and perturb LL problem
3: for 0, ,....:
do
4: Find an approximate solution y(x") s.t. Assumption is satisfied.
5: Compute V Fxx") using ( d' = x x" with x proj (x" -
6: Select a" s.t. the following Armijo-type rule condition is satisfied
F(x") F('' a" d"d") -o a ("(" e
(I1)
where r)) depends on 8", a and problem-dependent parameters; F(.) = ((:3()).
7:
Perform one projected gradient step: x x" + a d'
8:
end for
Algorithm 2 [Stochastic] Smoothed Implicit Gradient Descent ([S]SIGD)
1: Input: Initial parameter x". # of iterations T, step-sizes {8r) 1T= LL solution accuracy
2: Sample q ~ 2 and perturb LL problem
do 4: Find an approximate solution f(x") s.t. Assumption 2 is satisfied.
3: for r 0, o.... T
.......T
5: Compute v {") using 10
6: Perform one stochastic projected gradient descent step: x=+1 (x F('FF(xx;
7: end for
Assumption 4 is typical assumption required ensure that the approximate implicit stochastic gradient is also unbiased and has finite variance (Ghadimi & Wang 2018 Hong et al. 2020 Chen
al. 2021a) as shown in Lemma Dellow..
Lemma 4 (Appendix) D.1.4. Under Assumptions 7213 and 4 the stochastic gradient estimate in
10) is unbiased, i.e., Ee [xx: = FF(x) and has bounded variance i.e., Eg F(x;
Fx)) S o7. where of 20 + oIy- where Ly- is defined in Lemma 7 in the Appendix.
THE SIGD ALGORIHTMM AND CONVERGENCE ANALYSIS
3.1 THE PROPOSED ALGORITHMS
In this section, we develop gradient-based methods for solving problem [ by leveraging the smoothing based technique introduced in the previous section. Recall that for any X, we can introduce perturbation to make the optimal solution (x) of the perturbed LL problem differentiable. Next, to proceed with the algorithm design, there are two options available. First, generate perturbation for each E X'' encountered in the algorithm. Second, generate single perturbation at the beginning of the algorithm, and use throughout the execution of the algorithm. It is worth mentioning that, both approaches perform equally well in our numerical experiments. However, for the case of analysis, we adopt the second approach. To justify such an approach, below we show that, just sampling single q is suffice to make F()) differentiable (almost surely) at sequence of countable points.
Lemma 5 (Appendix D.2.Ip. Let {x= X be an arbitrary sequence. Consider the implicis function F(x) ;= f(x, (x)), where y yx)) is defined in (5), where single perturbation is used. Then F(-) differentiable all the points (x") j w.p.
Due to this result, in the following analysis, we assume that the almost sure differentiability will also be satisfied for the iterates generated by our algorithms as suggested by Lemma 5) Further, our algorithm design is guided by the fact that, unlike bilevel programs with unconstrained LL tasks (see Lemma 2.2(c) Ghadimi & Wang (018)). ), the implicit gradient F in (8) is not Lipschitz smooth in general. This implies that algorithms that provably converge only under the Lipschitz assumption, will not work in our case, particularly when the implicit function non-convex. Towards
this end, propose the [Deterministic] Smoothed Implicit Gradient Descent (DDJIGD)) method

---

Under review as a conference paper at ICLR 2023
(Alg. D determinstic line-search-base method, which does not require Lipschitz smoothness or another special structure (c.g., convexity), and show asymptotic convergence (Theorem DT. Moreover, for the cases where the implicit function is weakly-convex, convex or strongly convex (but still not Lipschitz smooth) the [Stochastic] Smoothed Implicit Gradient Descent ([SJSIGD) method (Alg. 2 is developed, a stochastic praddeet-based method, for which finite-time convergence guarantees
derived (Theorem 234
3.2 CONVERGENCE ANALYSIS
As discussed above, the context of algorithm design and analysis we sample single perturbation q. and keep it fixed during the algorithm execution. As a result, the algorithm is effectively optimizing the following smooth surrogate of the original problem [
min F(xx) f(x, y" (x)) [fx (x):1)
(12a)
s.t. y" (x) E arg min { g(x,y) = h(x.y) + प Ay 1 b).
(12b)
yER4
where q E Id is generated from continuous measure only once and thus is considered fixed. Next, we show that the original problem (T) and the smoothed surrogate problem (12) are "close". Specifically, we show below that the original implicit function G(x) and the "smoothed" implicit function F(x) differ by quantity that is controlled by the size of the perturbation vector q.
Proposition (Appendix D.2.2). Under Ass.
and
we have: [G(x) F(x) s Ly |all| Vx X.
Note that the only requirement on is that it is generated from a continuous measure. Therefore we can always choose a distribution such that [|q|| is arbitrarily small. Next, let us analyze Alg. [ We have the following asymptotic result.
Theorem (Appendix D.2.3]. Suppose that Ass. 3 hold. At each iteration r Alg. 1
we find 0 < a < 1 such that the Armijo-type condition (II) is satisfied with c(ō:r)
L + IrLFa 8 + Lygr+1 + L'Fo0"" (8r)² + 2LFLFoo'd 8". Further, we select 8 such that Ass. is satisfied, lim,- 8" = O, and it holds that 8" /a O (c"). where c" is some sequence with lim,- -200 c² = O. In addition, the sequence d' is selected such that it is gradient related to & Fxx"), ie., "for any subsequence {x" JrER converging to a non-stationry point, the correxponding subse-
quence (r') is bounded and satisfies lim sup, eq. 1.13). Then w.p. 1 the limit point & of the sequence of iterates generated by the [DJSIGD Alg. is stationary point.
[F(())]
T d' < 0" (Bertsekas 1998
Note that in Theorem I only asymptotic convergence is guaranteed. However, this is the best we can do since we do not impose any Lipschitz smoothness or convexity assumptions. On the other hand, in the special cases where the implicit function is weakly-conve,, strongly convex or convex (but still not Lipschitz smooth), is possible to derive fnite-time convergence guarantees as presented next. Towards this end, we need to impose the additional assumption that the set X' is bounded; combining this property with Assumption I limplies that X' is compact. So, in the following results we assume that X' is compact set with diameter Dx == suPx,8ex ||x x||-
Weakly Convex Objective. We make the following assumption on the implicit function F(-). Assumption 5. We assume that for some p > 0 the implicit function F(x) satisfies: F(z) 2
F(x) F(x)), x) [ x|| / x, E Rdd...
Assumption 5 implies that the function F(x) + 2 |x|| for X P is convex while for P > is strongly convex with modulus أ - p. Many problems of practical interest satisfy the weak-convexity, for example, phase retrieval (Davis et al., 2020), covariance matrix estimation (Chen et al. 2015). dictionary learning (Davis& & Drusvyatskiy 2019), Robust PCA (Candès et al. 2011) etc. (please see (Davis & Drusvyatskiy 2019) and (Drusvyatskiy 2017) for more details). For providing guarantees for the [SJSIGD algorithm we utilize a Moreau envelope based analysis. For this purpose, we first rephrase the UL problem as unconstrained one: minxegd. H(x) == F(x) + Lx(x)) where Ix (x)
is the indicator function of set Y' defined as: Lx(x) == 0 Difx x E X' and [x(x) = oo if & X. Below we define the Moreau envelope of (x)).
7

---

Under review as a conference paper at ICLR 2023
Definition 1. Given À > 0, the Moreau envelope of (x) is defined
Hx(x) = min zER
H()))
1xx
2112
min =E
1 F(z) +
2A 1|xx - z||3]
2A
where the second equality follows from the definition of H(x). Moreover, we denote the proximal map of H (x) as x == prox 1 (x) which is defined as
{H(z)
1 - - 21²)
{ F((2)
2/ 2A
||x 2|(²}
arg min
arg min
zERde
xEX
The norm of the gradient of the Moreau envelope satisfies the following:
||x x||
(x)Il
= S Hxx), and dist(O;@H(st)) & [x)lx)]]
(13)
where 00 (x)) [ (x;
v) and H' (x; denotes the directional derivative of H at x in direction v. Note that small gradient V (x)]) implies that x is near some point & that is nearly stationary (Davis & Drusvyatskiy 2019). Then we have the following result.
Theorem 2 (Appendix D.2.4). Under Ass.
and 5 with step-sizes ,3r 3 for all r
(O...., T -11 1} and for any constant p > 2, the iterates generated by Algorithm 2 satissy (w.p. 1)
Σ B 3
2p
H Hx)p(x H
30(08 Tzp) + P 13,02 2p
2p
3p
BT
Theorem implies that with the choice of = O(IVVT), the [SJSIGD algorithm converges to stationary point at a rate of ((L/VT) with an additive error determined by the accuracy the LL problem's solution å (see Assumption 2).
Strongly Convex and Convex Objective. Next, we provide the guarantees for the case when the implicit function is strongly convex. We make the following assumption.
Assumption 6. We assume that the objective Fxx) is pu-strongly convex, i.e., F(z) 2 F(x) xx - z|12 Vzz x E X. Note that for PF 0, the objective becomes convex.
(VF(x), z x) + Rr
2
Theorem (Appendix D.2.5 Under the Assumptions of step-sizes 8"
3 Land 2 with μr > O and the choice (r(r+1) the iterates generated by Algorithm satisfy the following (w.p. 1),
(07 + Lp)
log(T)
B(F(x) F*]
DxLpp.
Hr
T
Theorem 4 (Appendix D.2.6).
3 and о with pF = O, and step-sizes 8" = f. r E {O..... IT, the iterates generated by Algorithm satisfy the following (w.p. 1),
Under Assumption
|x 122
[ - F11
+ 23 + I DxLF8, where Σx X
ST
The results of Theorems and iimply that the implicit function F(x) converges to the optimal value at a rate of O(1/T) for strongly-convex objectives with diminishing step-sizes, and at a rate of O(I/VT) for convex objectives with 3 (I/VTT). Note that convergence is shown neighborhood the optimal solution where its size determined by the size of the LL error
4 EXPERIMENTS
In this section, we evaluate the performance of [gn via numerical experiments. First, compare the performance of [DJSIGD to the recently proposed PDBO (Sow et al.) (022) for constrained bilevel optimization on a quadratic bilevel problem. Then in the second set of experiments, evaluate the performance of [SJSGG against popular adversarial training algorithms.
Quadratic Bilevel Optimization. Consider the quadratic bilevel problem of the form 1 with
y(x,y) - |x||
1 1xl + 1T + 1Ty + and h(x, y) = -xy |llll + m + y2, (14)
10x
8

---

Under review as a conference paper at ICLR 2023
and linear constraints of the form M/l < 1, {1, 2)
Here, x = [41, x2l". = [2]" with 24, Yi E R for i e {1, and 1 11.1"" . The evaluation criterion is
DSSEDD [P]SIco
PDBO
the stationarity gap [F)]]
[[TF(X]||
15
On this problem execute [D]SIGD (Algorithm TT, [S]SIGD (Algorithm 2 and PDBO (Sow et al.] 2022). In the first two cases, we solve the inner-level problem using 10 steps of projected gradient descent with stepsize 10-1. For the stepsize of [SJSIGD, we choose 3 0.1, while in [D]SIGD we find the proper Armijo step-size by successively adapting (by increasing m)) the quantity
10
20
40
80
iterations
Figure 2:
[V)( vs # of iterations.
a, = (0.9) until condition (11 is met. In PDBO we select 10-1 for the stepsizes of both the primal and dual steps, and the number of inner iterations set to 10. In Figure we plot the convergence curves for the three algorithms with respect to number of iterations; the results are averaged over 10 runs. Note that the line search [DJSIGD method outperforms the fixed step-size [S]SIGD and PDBO while [S]SIGD performs similar to PDBO.
Adversarial Learning. We consider an adversarial learning problem of the form given in (3). For the
perturbation focus the e-tolerant lox -norm attack constraint, namely y { E Rd by x0
c), which can easily be expressed as a linear inequality constraint as in the LL problem of (3) We consider two widely accepted adversarial learning method as our baselines, namely AT Maadry et al. 2017) and TRADES (Zhang et al., 2019b). Also, we consider two representative datasets CIFAR- 1LFAR-I0/100 (Krizhevsky et al. 2009) and adopt the ResNet- 18 (He et al. (016)) model; the results studied two widely used, (Marry et al.) 2017 Wong et al. 2020) attack budget choices E (8/255, 16/255) In the implementation of our [S]SIGI method, we adopt perturbation generated by Gaussian random vector q with variances from the following list o² E (2e-5, 4e,,, 5, 5, 1e-4, ). in order to study different levels of smoothness. Moreover, for solving the LL problem in each iteration we select fixed batch of samples. We choose f; to be cross-entropy loss and h, -f 1 |||y?l?? for hyper-parameter À >> O. For [S]SIGD, we follow the implementation of (Zhang et al. 202T but with perturbations in the LL problem. We evaluate the robustly trained model with two metrics, namely the standard accuracy (SA) and robust accuracy (RA), where we evaluate the accuracy of the robustified model on the clean and attacked test set, respectively; the attacked set is generated using PGD-50-10 10 (Madry et al.) 2017) (i.c., 50-step PGD attack with 10 restarts). Desirably, a well trained model possesses high RA while maintaining simultaneously the SA at high level. Table shows the performance overview of our experiments. We make the following observations. First, a low level of perturbation variance (e.g.. o² E (2 4)) in general improves both SA well RA,, which presents an enhanced RA-SA trade-off. For example, in the setting (CIFAR-10) 100, c = 16/255) our algorithm boosts the RA by over 0.3% and the SA by 2%. Second, high level of perturbation variance harms the robustness but results in high SA. This is reasonable, since the stochastic gradient becomes too noisy with large variances. Third, our method outperforms AT and closely matches the performance of the stronger baseline TRADES. However, we would like to stress that the intent of our work is not to design specialized adversarial learning method, and thus robustness gap between our method and the strong baseline does not diminish the value of our method. Additional details are provided in Appendix C.2
for CIFAR-10 are provided in Appendix C In particular,
Table 1: Performance overview of different methods on 1TFAR- et al. 2009) with ResNet-18 He et al. (2166). The result a:s represents the mean value with standard deviation of b over 5 random trials.
CIFAR- 100.
8/255
[S]SIG (Gaussian variance o²)
Metrics
AT
TRADES
2e-5
de-5
6e-5
8e-5
le-4
SA
13.8310.19
53.33L0.18
53.88 10.222
54.01 10.24
53.79
57.7410.22 27.14
54.44_0.11
RA
27.36
28. 28.4440.17
27. 17.4320.12
28.2240.10
12
25.2240.18
16/255
SA
42.06
42.19 2
44.06
45.6640.25
46.57+0.2
47.46+0.4 -
RA
15.10
16.59 20.25
15.51
14.1840.22
13.9220.2
13.54_a.18
13. 13.42.0.26

---

Under review as a conference paper at ICLR 2023
REFERENCES
Amin Abedi, Mohammad Reza Hesamzadeh, and Franco Romerio. An acopf-based bilevel optimiza- tion approach for vulnerability assessment of a power system. International Journal of Electrical Power & Energy Systems, 125:106455, 2021. ISSN 0142-0615.
Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J Zico Kolter. Differentiable convex optimization layers. Advances in neural information processing systems, 32, 2019.
G. B. Allende and G. Still. Solving bilevel programs with the kkt-approach. Mathematical Program- ming, 138:309-332, 2013.
Brandon Amos and J Zico Kolter. Optnet: Differentiable optimization as layer in neural networks. In International Conference on Machine Learning, pp. 336-145. PMLR, 2017.
Maksym Andriushchenko and Nicolas Flammarion. Understanding and improving fast adversarial training. Advances in Neural Information Processing Systems, 116004--60555 2020.
D. A. Arias, A. A. Mota, I.. M. Mota, and C. Castro. A bilevel programming approach for power system operation planning considering voltage stability and economic dispatch. In 2008 IEEE/PES Transmission and Distribution Conference and Exposition: Latin America, pp. 1-6, 2008. doi: 10.1109/TDC-LA.2008 4641078.
Quentin Bertrand, Quentin Klopfenstein, Mathieu Blondel, Samuel Vaiter, Alexandre Gramfort, and Joseph Salmon. Implicit differentiation of lasso-type models for hyperparameter optimization. In International Conference on Machine Learning, pp. 810-821. PMLR, 2020.
Quentin Bertrand, Quentin Klopfenstein, Mathurin Massias, Mathieu Blondel, Samuel Vaiter, Alexan- dre Gramfort, and Joseph Salmon. Implicit differentiation for fast hyperparameter selection in non-smooth convex learning, ArXiv, abs/2105.01637, 2021.
Dimitri Bertsekas. Nonlinear programming. 2nd ed. Athena Scientific Belmont, MA, 1998.
Paul H Calamai and Jorge Moré. Projected gradient methods for linearly constrained problems. Mathematical programming, 39(1):93-116, 1987.
Emmanuel Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):1-37, 2011.
Mark Cecchini, Joseph Ecker, Michael Kupferschmid, and Robert Leitch. Solving nonlinear principal- agent problems using bilevel programming. European Journal of Operational Research, 230(2): 364-373, 2013.
Tsung- Hui Chang. Mingyi Hong. Hoi-To Wai, Xinwei Zhang, and Songtao Lu. Distributed learning in the nonconvex world: From batch data to streaming and beyond. IEEE Signal Processing Magazine, 37(3):26-38, 2020. doi: 10. 10.1000//S..222.2900000
Tianyi Chen, Yuejiao Sun, and Wotao Yin. A single-timescale stochastic bilevel optimization method, 2021a.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Tighter analysis of alternating stochastic gradient method for stochastic nested problems. arXiv preprint arXiv:2 106. 13781, 2021
Yuxin Chen, Yuejie Chi, and Andrea J Goldsmith. Exact and stable covariance estimation from quadratic sampling via convex programming, IEEE Transactions on Information Theory, 61(7): 4034-4059, 2015.
Benoît Colson, Patrice Marcotte, and Gilles Savard. Bilevel programming: A survey. 4or, 3(2): 87-107, 2005.
Damek Davis and Dmitriy Drusvyatskiy, Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1 29)7)2077- 2019.
10

---

Under review as a conference paper at ICLR 2023
Damek Davis, Dmitriy Drusvyatskiy, and Courtney Paquette. The nonsmooth landscape of phase retrieval. IMA Journal of Numerical Analysis, 40(())2652 2695, 2020.
Stephan Dempe and Alain Zemkoho. Bilevel optimization. Springer, 2020.
Mohamed Didi-Biha, Patrice Marcotte, and Gilles Savard. Path-based formulations of bilevel toll setting problem. pp. 29-50. Springer US, Boston, MA, 2006. ISBN 978-0-387-34221-44 doi: 10.100770-388-34421--22
Priya Donti, Brandon Amos, and Zico Kolter. Task-based end-to-end model learning in stochastic optimization. Advances in neural information processing systems, 30, 2017.
Dmitriy Drusvyatskiy. The proximal point method revisited. arXiv preprint arXiv: 171.006612000338 2017.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning, pp. 1165-1173. PMLR, 2017.
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, pp. 1568-1577. PMLR, 2018
T.L. Friesz and D. Bernstein. Foundations of Network Optimization and Games, Complex Networks and Dynamic Systems. Springer US, 2015. ISBN 978 1784999975
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.022 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and hamnessing adversarial examples. arXiv preprint 1rXiv:14/2.65722 2014.
Stephen Gould, Richard Hartley, and Dylan Camphell. Deep declarative networks. IEEE Transactions on Pottern Analysis and Machine Intelligence, 44(8):3988 4004, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedingy of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Mingyi Hong. Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic, arXiv preprint 17X 2020.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pp. 4882-4892. PMLR, 2021.
Dr. Vyacheslav Kalashnikov, José- Fernando Camacho- -amacho-Vallejo, Ronald Askin, and Nataliya Kalash- nykova. Comparison of algorithms for solving bi-level toll setting problem. International journal of innovative computing, information & control: IJICIC, 6:3529-3549 08 2010.
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A momentum-assisted single-timescale stochastic approximation algorithm for bilevel optimization, 2021a.
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. near-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in Neural Information Processing Systems, 34, 2021b.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Gérard Lebourg. Generic differentiability of lipschitzian functions. Transactions of the American Mathematical Society, 256: 166:125-144 144, 1979.
Lecture. 5: Correspondences and berge's maximum theorem. Math Camp Notes, Department of Economics, Yale University, 2017.
11

---

Under review as a conference paper at ICLR 2023
Yi Li, Lingxiao Song, Xiang Wu, Ran He, and Tieniu Tan. Learning bi-level adversarial network with global and local perception for makeup-invan invariant face verification. Pattern Recognition, 90: 99-108, 2019.
Gui-Hua Lin, Mengwei Xu, and Jane J. Ye. On solving simple bilevel programs with nonconvex lower level program. Math. Program., 144(1-2)2277300, April 2014.
Risheng Liu, Jiaxin Gao, Jin Zhang, Deyu Meng, and Zhouchen Lin. Investigating bi-level op- timization for learning and vision from unified perspective: A survey and beyond. arXiv, 2021a
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 Conference Machine Learning, pp. 6882-6892. PMLR, 2021b.
Risheng Liu, Xuan Liu, Shangzhi Zeng, Jin Zhang, and Yixuan Zhang. celue-functioo-beee sequential minimization for bi-level optimization. arXiv preprint arXiv:2110.04974, 2021c.
Songtao Lu, Meisam Razaviyayn, Bo Yang, Kejun Huang, and Mingyi Hong. Finding second-orde
stationary points efficiently in smooth nonconvex linearly constrained optimization problems. Advances in Neural Information Processing Systems, 11-2811-2882. 2020.
Zhi-Quan Luo, Jong-Shi Pang, and Daniel Ralph. Mathematical programs with equilibrium con- straints. Cambridge University Press, 1996.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: 1706.06083, 2017.
Julien Mairal, Francis Bach, and Jean Ponce. Task-driven dictionary learning. IEEE transactions on paltern analysis and machine infelligence, 34(4):791-804, 2011.
Patrice Marcotte, Gilles Savard, and D. Zhu. A trust region algorithm for nonlinear bilevel program- ming. Oper. Res. Lett., 29:171-1797 2001. doi: (000016801167-3370000000099
Athanasios Migdalas. Bilevel programming in traffic planning: Models, methods and challenge. Journal of global optimization, 7(4):311440 1995.
James A Mirrlees. The theory of moral hazard and unobservable behaviour: Part i. The Review of Economic Studies, 66(1):3-22 21, 1999.
Seyed-Mohsen Moosavi- Dezfooll, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robust- ness via curvature regularization, and vice versa. In Proceedings the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 9078-9086, 2019.
Julie Nutini, Mark Schmidt, and Warren Hare. "active-set complexity" of proximal gradient: How long does it take to find the sparsity pattern? Optimization Letters, ((4):645-655 2019.
Francesca Parise and Asuman Ozdaglar. Sensitivity analysis for network aggregative games. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pp. 3200-3205. IEEE, 2017.
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International conference on machine learning, pp. 737-746. PMLR, 2016.
Arvind U Raghunathan and Lorenz T Biegler. Mathematical programs with equilibrium constraints (mpees) in process engineering. Computers Chemical Engineering, 27(10) 2003.
ISSN
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. In Advances in Neural Information Processing Systems, volume 32, Curran Associates,
Inc., 2019.
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, pp. 1723-1732, PMLR, 2019.
12

---

Under review as a conference paper at ICLR 2023
Ankur Sinha, Pekka Malo, and Kalyanmoy Deb. A review bilevel optimization: from classical to evolutionary approaches and applications. IEEE Transactions on Evolutionary Computation, 22 (2):276-2955 20176777...117.
Ankur Sinha, Tanmay Khandait, and Raja Mohanty. A gradient-based bilevel optimization approach for tuning hyperparameters in machine learning. arXiv preprint 20Xiv:2007.11022,, 2020.
Daouda Sow, Kaiyi Ji, Ziwei Guan, and Yingbin Liang. A constrained optimization approach to bilevel optimization with multiple inner minima. arXiv preprint arXiv:2203.01123, 2022.
Heinrich Von Stackelberg and Stackelberg Heinrich Von. The theory of the market economy. Oxford
University Press, 1952.
Eric Wong, Leslie Rice, and J Zico Kolter. Fast is better than free: Revisiting adversarial training. arXiv preprint 1rXiv:2001.0399. 2020.
Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34, 2021.
Tao Yang, Xinlei Yi, Junfeng Wu, Ye Yuan, Di Wu, Ziyang Meng, Yiguang Hong, Hong Wang, Zongli Lin, and Karl H Johansson. A survey of distributed optimization. Annual Reviews in Control, 47:278-305. 2019.
JJ Ye and DL Zhu. Optimality conditions for bilevel programming problems. Optimization, 33(1):
9-27, 1995.
Farzad Yousefian, Bilevel distributed optimization directed networks. In 2021 American Control IEEE, 2021.
Conference (ACC), pp.
Dinghuai Zhang, Tianyuan Zhang, Yiping Lu, Zhanxing Zhu, and Bin Dong. You only propagate once: Accelerating adversarial training via maximal principle. Advances in Neural Information Processing Systems, 32, 2019a.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference on machine learning. pp. 7472-7482, PMLR, 2019b.
Yihua Zhang, Guanhua Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, and Sijia Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. arXiv: 22. 12376, 2021.
13

---

Under review as a conference paper at ICLR 2023
A RELATED LITERATURE
Bilevel optimization problems, initially encountered in the context of Stackelberg (lcader-follower)
games (Von Stackelberg & Von 1952), find applications in a multitude of areas, including machine
learning (Liu et al.) 200 economics (Mirrlees] 1999). power systems (Abedi et al.) [021] Arias
ct al.
2008), chemical industry (Raghunathan & Biegler (003), transport research (Didi-Biha et al.
2006
Kalashnikov et al. 2010); see (Colson et al., 2005| Dempe & Zemkoho 2020 |Sinha et al.
2017
Liu et al.) 202 a) for a number of survey papers. The "classical" approaches for solving
bilevel problems include the use of approximate descent methods (Shaban et al., [219 Ghadimi &
Wang 2018 Franceschi et al. (017). penalty methods (Lin et al.) 2214), KKT reformulations based
approaches (Allende & Still 2013), value function- methods (Ye & 'hhu 1995 Sow al.)
2022), and trust-region algorithms (Marcotte et al.] 200T). In addition, bilevel problems are known to
be related to mathematical programs with equilibrium constraints (MPEC) (Luo et al. 1996).
Recently, motivated by machine learning applications, gradient-based approaches have gained popular- ity for solving bilevel optimization problems (Liu al., 2021a), e.g.. in hyperparameter optimization
(Shaban et al. 2019; Franceschi et al. 2017 2018), and meta learning (Rajeswaran et al. 2019
Franceschi al. 2018). The majority those works are focused on solving bilevel problems with
unconstrained strongly convex LL problem, for both stochastic and deterministic objectives (Ghadimi
Wang 2018: Hong et al. 2020; Khanduri et al. 2021a b) Chen et al. 2021 et al. | Chen et 20.2 Yang et al. (021). An attractive property of such problems is the existence and easy computability of the implicit gradient. Moreover, under mild assumptions, the implicit gradient for
these problems can be shown to be Lipschitz smooth (e.g., see (Ghadimi & Wang, 2018 Lemma 2.2)
and (Khanduri et al. 20216 Lemma 3. I). In contrast, for bilevel problems with linear LL constraints the implicit gradient in general might not exist, and even if it exists computing it in closed-for form is challenging task. As discussed earlier, we develop perturbation- baaeed smoothing framework for the constrained L.I. problem that ensures the existence of the implicit gradient in almost sure sense, and allows us to compute an expression for the implicit gradient.
In Liu et al. (2021c) and (Sow et al. (2022) the authors have considered bilevel optimization with (general) constraints in the LL problem. Both papers develop a value function-based framework that leads to a single level problem with non-convex constraints. In Liu et al. (2021c) sequential minimization approach is followed where the value-function and the LL constraints are incorporated into the objective using penalty or barrier functions. In (So et al.] (2022) a fimaal-uull-ased framework is proposed in which the problem is regularized with the addition of a strongly-convex penalty term, while a constant error term is added to make the constraint set strictly feasible. In contrast, our approach relies only on small linear perturbation which can be made arbitrarily small without practically changing the landscape of the LL problem.
There is also line of works (Amos& & Kolter, 2017 Agrawal et al., 2019 Donti al. 2017 Gould al. 202T) about implicit differentiation in deep learning literature. These works Deep- Learning-tyy (DL-type) are indeed related to ours, in the sense that at the core of both of them lies the computation of the gradient/Jacobian of the solution of an optimization problem. However, there are some key differences. First, in our work consider a constrained bilevel optimization problem and we interested in analyzing this problem from an optimization perspective. On the other hand, in the DL-type works the optimization problems that are studied describe the input-output relationships of neural networks layers and the main focus lies in deriving Jacobians for the backward pass, Secondly, in our work we study special bilevel problem (the constraints are linear) and derive closed form expression for the implicit gradient. On the contrary, in the DL-type works the underlying problems have more general constraints and the Jacobian is usually computed using numerical methods (e.g.. solving iteratively a system of KKT equations), rather than analytically. Finally, in our work the focus is on studying the properties of the bilevel problem (e.g. differentiability, approximation errors), developing (deterministic and stochastic) algorithms, and performing convergence analysis. On the other hand, DL-type works focus mainly on the Jacobian computation and its implementation.
Finally, there is number of works on implicit differentiation non-smooth problems (Mairal et al. 2021: 2020). However, these works typically deal with special (non -oooshh LL problems, e.g., in Mairal et al. (201T): |Bertrnnd et al. (2020) the non-smooth term in the LL is the fo-norm, and in Bertrand et al. (202I) the non-smooth term is separable. On the contrary, in our work are considering smooth I.I. problems and general linear inequality constraints.
2011 Bertrand et al.
14

---

Under review as a conference paper at ICLR 2023
B SOLUTION METHODS FOR THE LL PROBLEM
The LL problem is a strongly convex linearly constrained optimization task. As result, there exist many efficient ways to find its solutions. In order to discuss about them, we consider two different classes of problems depending on the exact form of the linear constraints and the difficulty of computing the respective projection operator: 1) the projection has a closed-form solution, 2) the projection requires the solution of an optimization problem. Before we proceed, we would like to stress that the problem we are solving, i.e., the bilevel problem with linear constraints in the LL., is a very challenging one, regardless of the specific form and the exact way approach the solution of the LL problem.
In the first class of problems, where the projection can be computed in closed form, we have problems with special linear constraints. One characteristic example is box constraints, i.e. constraints of the form S y b, where the inequalities apply in component-win manner. These constraints appear in applications, such as adversarial learning (see the motivating applications in the main text). In this case, we can some first-order iterative algorithm to solve the LL problem and project each iterate onto the constraint set using the closed-form expression (which only incurs a constant cost per iteration). For instance, we can use the projected gradient descent method which probably converges to the optimal solution with linear rate.
In the second class of problems, the projection operator does not possess closed-fore form expression. In this case we can approach the LL problem as convex optimization task, and solve it using some convex optimization solver (e.g. employing interior-poim methods) to obtain highly accurate solution with complexity of O (p(d), k) log(ds/e)) where p(-) is some polynomial and is solution accuracy. Alternatively, as mentioned in the previous case, we can use projected gradient descent- type method that enjoys a linear convergence rate guarantee. Differently from the previous case though the projection operator computed at each iteration requires the solution of an optimization problem. Nonetheless, the projection task we referring to is (strongly convex) quadratic linearly constrained problem, that is special quadratic programming task, which is easy to solve in practice. In algorithm 3 we describe the solution of the LL using a projected gradient descent algorithm.
Algorithm 3 Projected Gradient Descent (PGD)
1: Input: Initial parameter y", Current iterate x, # iter T. step-sizes {TT Constraints A, b
2: for 0, 1,.... T
do
3: y=+1 y V Vx, y")
4: Project y to y = (y E Rd |Ay S b} by solving the following QP:
min ||y - ---+t111 12 s.t. Ay S b
(15)
yER4,
5: end for
C ADDITIONAL EXPERIMENTS
In this section, include additional experiments on quadratic bilevel optimization problems and Adversarial training along with the implementation details. First, we evaluate the performance of the [DJSIGD and [SJSIGD quadratic bilevel optimization problems.
C.1 NUMERICAL. RESULTS
We consider the following linearly constrained quadratic bilevel problems of the form II with the UL and the L.L objectives defined as:
1 f(x,y) = - ||x||/
1 [1s11 h(x,y) _
1
2x y + 1
1
+ 5x y
|1
(16)
4
- 1=1111 + +2x"x
1 |x11 h(x,y) =x=xxxxx- + 11y11 |xy
1
(17)
15

---

Under review as a conference paper at ICLR 2023
12
SSIGO 13 POBO
[S]S/SD
[D]SCD
P3BO
[|0F(x]]
20
40
60
80
10
30
40
50
iterations
iterations
(a) Problem 16
(b) Problem
33SIGD 13/ICD
POBO
10
iterations
(c) Problem
18
Figure 3: Convergence curves w.r.t. number of iterations.
1 f(x,y)= - 2x - 11x111 +1, 1(x,)) = x²y |lll +1'x+11x++ (18)
In the first two cases, we have d, = 2, and the linear constraints in the LL are of the form -1 < yi < 1, E [1,2]. In the third example, we have du = di = 2. and the linear constraints in the LL. are of the form 5 S y I 5, i (1,2). -5 -5 y1 + U2 < 5. We compare the performance of SIGD algorithms to recently proposed PDBO (Sow et 2022). In Figures 3a 3b and [3c| we present the evolution of the stationarity gap [Xx]] during the execution of the three algorithms, for the problems (16) 17) and (18), respectively. The results are averaged over 10 random runs, and variance of the results across these runs is reflected on shaded region across the convergence curves. In our experiments, we choose the step-size using the backtracking line search for [D]SIGD as stated in Algorithm D while for [SJSIGD we choose a constant step-size. Note that since all problems are deterministic [S]SIGD utilizes gradient estimator with variance.
In problem (6)), we solve the LL problem using 10 steps projected gradient descent with stepsize 0.1; in the case of [D]SIGD the stepsize is 1. For the stepsize of [S]SIGD, choose = 0.1, while in [DJSIGD we find the proper Armijo step-size by successively adapting (by increasing m) the quantity 0, = (0.9)" until condition (1I) is met. In PDBO select 0.1 for the stepsizes of both the primal and dual steps, and the number of inner iterations set to 10. In problem (17), we solve the LL problem using 20 steps projected gradient descent with stepsize 0.1: the case of [D]SIGD the number of steps is 10 and the stepsize is 1. For the stepsize of [S]SIGD, we choose 3 = 0.1. while [D]SIGD we find the proper Armijo step-size by successively adapting (by increasing m) the quantity a, (0.95)m until condition (11) is met. In PDBO we select 0.1 for the stepsizes of both the primal and dual steps, and the number of inner iterations set to 20. problem (18). we solve the LL problem (of both [D]SIGD and (SJSIGD) using 10 steps of projected gradient descent with stepsize 0.1. For the stepsize of [S]SIGD, we choose 3 = 0.1, while in [D]SIGD we find the proper Armijo step-size by successively adapting (by increasing m) the quantity a,, (0.9)" until condition (TT is met. In PDBO we select 0.1 for the stepsizes of both the primal and dual steps, and the number of inner iterations is set to 10.
16

---

Under review as a conference paper at ICLR 2023
C.2 ADVERSARIAL LEARNING
In this section, we present some additional results along with the implementation details for the adversarial learning problem. As noted earlier, we consider the adversarial learning problem of form 3 For learning the perturbation y" (x), focus the e-tolerant & -norm attack constraint, i..., y = (y E Rd | S c). Note that this constraint can easily be expressed as a linear inequality constraint as the L.L problem (3). In particular, we evaluate the performance of [S]SIGD on two
widely used attack budget choices of 88/25,, 16 | (Madry et al. 2017 Zhang et al. 2019b Wong et al. 2020 Andriuschhenko & Flammarion 2020 Zhang et al.) 2019a). In the implementation of our [S] SIGD method, adopt perturbation generated by Gaussian random vector q with variances from the following list o² E {2e-5, 5, 6,-5, Se-
1e- 4, }. in order to study different levels of smoothness. We choose Sa be cross-entropy loss and h2
[i A/|y:|12 with À >> 0 as hyper-parameter. For solving (3). in each iteration we select a fixed batch of samples for both the UL and L.L. problems. Also, note that the ReI.U-based neural networks commonly lead to a piece-wise linear decision boundary w.r.t. the inputs (Moosavi-Dezfooli et al. 2019). This implies that the implicit gradient (T)) can be further approximated using Hessian free implementation, where the Hessian of the LL problem can be approximated by XI (Zhang et al. 2021 Eq. (25)). Note that these approximations are common in practice and do not lead to performance degradation compared the case when full Hessian is used to compute the amplicit-gradien (Zhang al. 2021] Table 5). Next, we analyze the effect of adding different perturbations q in the LL problem on the performance of [SJSIGD. Specifically,
choose q ~ NN, o II) and evaluate the performance of [S]SIGD with o².
In Figure we plot the robust accuracy (RA) and the standard accuracy (SA) with respect to the variance of the Gaussian perturbation vector used in the LL problem. As can be seen, the RA increases as the variance increases within a certain range. However, with stronger noise (i.e., o² >> 10-4), the RA drops sharply, while the SA increases. This is reasonable, since high variance makes the true LL gradient noisy. For easier observation, in Figure 5]w we zoom in the part of Figure where o² E [0,8- 10 10- It can be clearly seen that adding small perturbation q helps in improving the RA.
90
70
Tea Accurayy
70
60
50
50
40
40
30
Accuncy
20
Test Acsuuay
Standan Test Accuracy
Staddad Test
10
le4
20-5 6c.5 1o44
Goussian
Variance
(a) 8/255
(b) c 16/255
Figure 4: The influence of Gaussian variance on the RA and SA. The experiments are based on CIFAR-10 with ResNet-18 18 model.
Next, we compare the performance of [S]SGGD against two widely accepted adversarial learning methods as baselines, namely AT (Madry et al., 2017) ) and TRADES (Zhang et al., 2019b). Here. we present the results for CIFAR-10 10 dataset (Krizhevsky et al. 2009) and adopt the ResNet-18 (He) al. 2016). In Table 2 we compare the performance of [S]SIGD for different perturbation variances with classical AT (Madry et al. 2017) algorithm and TRADES (Zhang et al. 2019b). Note that for appropriate choice of perturbation variance [S]SIGD outperforms the classical AT algorithm while performs is only slightly worse compared to TRADES, especially, for higher attack budget of 16/255.
17

---

Under review as a conference paper at ICLR 2023
52.0
83.8
51.8
83.6
51.6
Teat Asturacy
R3.4
51.4
83.2
83.0
51.0
82.6
Accuracy
Accuracy
82.4
4o-5
No-5
20-5
66-5
Variance
Noise Variance o²
(a) c 8/255, CIFAR-10
73.00
32.5
72.75
72.50
32.0
Test Accunay
Tos Accumey
72.25
31.5
72.00
31.0
30.5
Standard Accuracy
Robeat Accuracy
71.00
20-5
8e-5
2x-5
4e-5
o²
o²
(b) c = 16/255, CIFAR-10
Figure 5: The influence of Gaussian variance on the RA and SA.
Table 2: Performance overview of different methods on CIFAR-10 Krizhevsky et al. 2009) with ResNet- 18 (He et al. 2016). The result ags represents the mean value a with standard deviation over 5 random trials.
CIFAR-IO, 8/255
[S]SIGD (Gaussian variance o²)
Metries
AT
TRADES
2e-5
4e-5
6e-5
8e-5
le-4
SA
80.78 50.71
80.23 51.1710.19
80.70
81.20+0.22 51.15
81.52+0.21
83. 83.1940.24
85.08 44
RA
20.21
50.5940.18
49.83
47.8 47.83
16/255
SA
70.31
70.22
71.43
72.7940.24
73.50
73.98
75.31 40.33
RA
32.12 1
33.35
32.72
31.73
29.9740.14
29.394o.15
27.67
D PROOFS
D.1 PROOFS OF SECTION 2
D.1.1 PROOF OF PROPOSITION
Note that the goal of Proposition I is to establish the continuity of the mapping y (x) and the implicit function G(x) = f(x, y [x)). In the following, we will show that under Assumption 1 y (x) in fact continuous, which will then utilize to establish the continuity of G(x). Before starting the proof we need few definitions. Consider the LL problem (1b) and let denote the set = {y E Rd. [Ay < b}. Note that in general the constraint set y can depend on the UL variable Y X - R and is referred to a correspondence. However, for the bilevel problem in (Ia) and (lb) the correspondence y is independent x E X and fixed set. Also, define the upper-semi continuity (USC) and the lower-semi continuity (LSC) for the correspondence (xx). To define these notions of continuity, we will utilize the notion of an e-ball defined below.
E X. For such cases, J'(x) is set valued map
18

---

Under review as a conference paper at ICLR 2023
Definition 2 (c-Ball), For y Rd and given > O, we define the open ball about y
B(()) = E lly - y' < for some y' Ey}.
where || the standard Euclidean norm.
Using the e-ball define the Upper Semi-Continuity (USC) of the correspondence y Definition 3 (Upper Semi-Continuity (USC)). The correspondence X IR is USC for every X E X and e > 0, there exists a 8 O such that (xx) Bx()(x)))) if E X and Ixx x'Il < 8.
Next, we define the notion of Lower Semi- Coni-Continuity (LSC).
Definition 4 (Lower Semi-Continuity (LSC)). The correspondence y :X - Rede is LSC if for any sequence X, in X that converges to a point x E X, and y E yxx), there exists a sequence Yn such that yn E (x,),, for all n E N, and lim y.
Theorem 5 (Berge's Theorem of Maximum (Lecture 2017)) Let X C Rd be non-empty set. Also, let y : + Id a correspondence such that the set V(x) is compact and non-empty for all X, and y is USC and LSC. Then, ifg X x R R is continuous function with y" (x) defined as
y" (x) arg min arg { (9(x,)) y M(x)).
yERd
the correspondence y (x) is nop-ympty for all x E X, and USC. Remark 2. Ify (x) is singleton, then USC implies the continuity of the map (x) - V. n7
Next, we present the proof of Proposition
Proof. The proof of proposition follows from the application of Berge's theorem.
To begin with, note that for our problem the set to verify the conditions of Theorem 5 First, note from Assumption I bb) that the set ) is non-empty and compact. Then, is easy to see that y B ()), for every c O, and that implies the LSC of ) Moreover, since the set y is independent of X and compact, for every sequence x,, x in X. we can always find a sequence Yn + y, such that Yn, y E y. Therefore, y is LSC. Finally, using Assumption a) we that the function g(x.y y) is continuous. Then, Theorem implies that the set y' (x) is non empty and the correspondence USC.
fixed set independent of x E X. We are going
claim that y*()) will be a singleton, and thereby continuous mapping. Then, the continuity of (*(x) implies the continuity of G(x) = f(x,y" (x)) since the composition of two continuous functions continuous. The proof is now complete.
Using the conoe-ty of g(x,y) with respect y (Assumption
D.1.2 PROOF OF LEMMA 2
Proof. In this proof we follow reasoning similar (Parise Ozdaglar 2017 Thm. 1). However, differently from that work we consider bilevel problems rather than Nash games. To begin with, consider the Lagrangian of problem (5), i.e.,
L(x, y, A) y(x,)) X (Ay b).
Then, for some fixed x E X, consider KKT point (x), X (x)) of for which holds that,
Vyl(x,y" X (x)) V y TT (x)
(**())) (Ay - 00
X²(x) 2
Ay"(x) - 0.
19

---

Under review as a conference paper at ICLR 2023
Now, consider the active constraints at X (x)),, and to simplify notation let us set À := A(y (x)). Using the notations defined in Section 2 and the SC property, the KKT conditions given above can be equivalently rewritten as
Vn (x)) + A X (x) -0, Ax"(x) O, A (x) 0,
(19)
where À (x) is the subvector of A (xx that contains only the elements whose indices correspond to the active constraints at y = y (x). Moreover. notice that the point (y"(x),, A (x)) is unique. The
uniqueness of y" (x) follows from the strong convexity of g(x, :): the uniqueness of X* results from the fact that matrix A has full row rank (which guarantees regularity, e.g., see Bertsekas (1998)
As mentioned in section 2 the SC condition (from Lemma D combined with Assumption [ iimpliss that the mapping y" (x) is differentiable almost surely (Friesz & Bernstein] 2015 Theorem 2.22). As
a result, at any given point x, we can consider a sufficiently small neighborhood around it, such that the active constraints A remain unchanged. Then, we can compute the gradient of (T9) using the implicit function theorem as follows
(x, y (x)) V
A vX)x
(20)
Avy (x) = 0.
(21)
Solving the (20) for Vy (x) yields
Vy xx) ( y (x))
-- (x)) - A" VX (x)
(22)
where exploited the fact that the Hessian matrix V V y" (x)) is positive definite and thus invertible. Substituting (22) into (T)
gives
A 2 (x y
(x, y" (x))
- T VA (x) =0
VX (x)
[
g y
"
A by y (x)) 22 xx, y" (x)) xx))
Finally, note that the KKT point y" (x) corresponds to the unique global minimum of (5) due the strong convexity of 9xx, The proof is now complete.
D.1.3 THE PROOF OF LEMMA K
The proof of Lemma B requires several intermediate results which we provide below. Note that under Assumption c holds that Aly (x)) (x))x);; for simplicity we will denote these matrices as A in the derivations of this subsection. Moreover, for any given matrix A we will denote with LA the maximum value of the quantity | (y (x) Il. across all x E X.
Lemma 6. Suppose that Assumption 223 hold. Then for any x E X, we have:
(a)
2 ( y)
-1
1 Nyy
Vy E Rdc
(b)
1 y (x)) (x)) V2 g( F(x)) < (vg Lg
(1)²
(c)
A V ( y)] 7
LA. Vy E R
(d)
y (x))
A"
2 xxx 'A'
I L jog L
Proof. a) We know that g( (xx y) is strongly convex in y with modulus (gg- Therefore, for any x E X we have
V2 g y) ž Mgt > 0, Vy E Rd
V22 1 -1 I, Vy Rd
Hg
- >1[V2L((x,>)]
-_- Vy e Rd
1
(23)
Hg
20

---

Under review as a conference paper at ICLR 2023
b) To begin with, notice that for arbitrary square invertible matrices Q we have
-
P)Q 1(P -2) ' |
(24)
Then, using the above inequality we get
| V V y" (x)) - -v b [(x)] 1|
V (x, y (x)) | (x, yx))) V e (x, ( (xx ||
Lgg Ily s(x)1l
Mg
Tgg 6,
Mg
where in the second inequality we used the result from Lemma and the Lipschitz Hessian property of g yy (Assumption dd
in the third inequality we use the Assumption aa) for yxx..
c) In our problem we have that g strongly convex in y and Lipschitz gradient in y. Thus, for any
X have
Ty T 2 V2 yx) t Mg! > 0
0 < - 1 90
- pl
1, R
Ly
Also, for every x E X, we have that
z R
AA
A AA |z21 ,, Vz E Rd
Using the above two lower bound we get
A V (xx -1 -'A'Z'' Ly Amin (AA)||2] O, vz e Rd {(0).
where the last inequality follows from the fact that A is full row rank which implies that Amin (AA") 0, Vx X.
Since the above inequality holds for every z E Rd (0). it VX E A' we get that
Amin (AA')
A [ [
1x y)]
*
I 0 Ly
Ly
(x,
A"
Amin (AA
[ (x,((
x"]
-
Ly
Amin (AA") T
Finally, for the given matrix A, consider the submatrix A A()(x)) generated by consider- ing only the subset of its rows corresponding to the active constraints at (x)). From Assump- tion [c) we know that Ax)(x)) is full row rank for every x X. and so we can ensure that Amin A()(()) > Vx E X. Then, we denote with Amin the minimum value of the quantity Amen (A A across x E X. Therefore, we conclude that
'X'
by
T.A Amin
21

---

Under review as a conference paper at ICLR 2023
d) Applying formula (4 with P= A [ ex -1 x" by 'A""
we
get
pyg(x, (xx)]
<
A
'
A V
'
A" A 2 (x 3(x)) 81x)] "A
A V (x, (x())
A V 1 |1
A (xx))
"
A D yxxxx,
A²
A (x, [xx))
$
2 xxx)) "=']]
||| y
A'
A
V [x,
1
Lgw 6,
where in the final inequality we used the bounds derived in Lemma b) || S L.A-
C
and the bound
The proof is now complete.
Now let us bound the norm of the gradients of the mappings (x) and (x).. Lemma 7. Under Assumptions 7
2 following bounds for every x E X.
the gradients of the mappings X (x) and y" (x) satisfy the
VVXX (x)] S Ix.,
|
s Lxx
[ S Ly,,
( S IIy
where Lx- = I.LALA gey and Ly 1 Pig
My (I + LaIxx). Note that PX (x) and V (x) are
obtained by substituting the estimate fxx) in place of y" (x) in the expressions VX (x) and Vy*(x) respectively (Please see Lemma
Proof. From Lemma 2 we have
VX (x)
A yx,,
A 'A'
A 2 [ x(xx
V2 (x, y
Then, taking the norm of this quantity we get,
VX (x)
A 2 2 (x)) -
A P (x, (x))
V V
=
A 1x y (x)) -1 A")
2 (x. (xx)) By g y' (x))
1 Ig..
IALA
Fg
where in the last inequality we used Lemma a)
C and Assumption f
Similarly, for /| | (x)]l we have that
FX (x) = || V
(x [(x))]
A"
-1 A
2 1
(x,
8(x))]
(x {(x))]
1 -ooe = Lx
< LALA
ug
22

---

Under review as a conference paper at ICLR 2023
Moving to the bound of VV (x)Il, we know from Lemma 2 that the formula of the gradient of y" (x) is
Vy*(x)= = [ xxx)]
V2 [
(X)
(25)
Then, we have that
[x)]+
V 9 x. y (x)) (xx, VX (x)
(x))
Ny x y (x))
V2yl(xy'' (x)) '" VX (x)
(1 1 (x, y (x)) + || |
2g
1
5 (L + LALx.) == Ly":
14g
where in the second inequality we used we used Lemma a
the third inequality follows from
Assumption f and the bound for VX (x)
we derived above.
Similarly, for V y (x))
we can obtain the following bound
Vy(x)
1x [(x)) -1 [- V2 F2 {(x)) - F' (x)
( x, {(x) + || (x)(x)
Hg
1 (L + LA(x-) =Iy..
Hg
The proof is now complete.
In the next two results we going to present bounds for the difference of the exact and approximate gradients of the mappings X (x) and Vy" (x).
Lemma 8. Suppose that Assumptions 22 3 hold. Then, the following bound holds
[VA (x)(x)] S Lx-
where Lx- = =(2) [/g LAL3L " Ig. + N9
I.LLLLe + ( LALALgo Lgao
Proof. Using the derivation of VX (x) from Lemma 2 and its approximation VX (x) where we substitute y" (x) with (xx in the formula of the former, that is,
Vx (x)
A 2 b 9x [())]
x²|
A 2 (x,
[()))
V2 (x {(x)))
we obtain
VX (x) 6x (xx) = A x (x))) A²]
(xx))
A [ ox, (x))
V2 ( (x)))
A V 1 [x))] -
[ [ [ f(x))
9 8 [xx)
Below, we use the following notation in order to simplify the derivations.
(x) = A [ (x)) 4'] G(x) = [V))((x,><<))]] (M(x)))))
MM(x) = (xyj((x,y((x))
(x) = A A") ((() = ((xx(x (M = (2,0(x,88x))
23

---

Under review as a conference paper at ICLR 2023
Then, have that
(x)
(x)]
11 1 -1
1 (x)AG( (x)
(x) - -
+
11 (x) - 7 [1]]
+ (x)) A ((x) -(x))
3 H (x)
A --0 [|1[0())111M<(]]]
+ A (x)
- G(()) ((x))))) (xx))))) (x)))
1 H (x)
-x) [[
+ (x)
||A|||| M(xx) - T7(x) + (x) | ||a|| |[(x) - G(x)) [xxx
2 L
(2)
1 Ig + LALA -
(1)
2
Love SLA
Ly 8 LAtea
-
Lgvy 8L
(1gg)
1gg
pig
Mlg
T.A 1. 1.
To
+
1 TAAAA +
11 (1)
T.AlAAlgae Toger
8.
Pg
big
In (a) we add and subtract the term (x) and apply the triangle inequality. In (b) we
add and subtract the term G(x) (x) and apply the triangle inequality. In (c) Lemma d for
| [x)) - (x)]. the bound ||A||| S LA, Lemma a for |G Lemma for || (x)l
and || (x)]l. Assumption for [x)]] and (x) Assumption
c for M Mx) M (x)]] ||.
and finally Lemma b) for [G(x) G(x)]..
The proof is now complete.
Lemma 9, Suppose that Assumptions 123 hold. Then, the following bound holds
Vy (x) Fy(x)] s Ly
(1)² where Ly. = 11
Lazy + (1)²
Lano Laen + Po
Log LAbss + LALA-
14
Proof. From Lemma 2 we have that
Vy (x) = 1 y (x))
- - vX((x))
We can also get Vx(x) by substituting fxx) place of y* (x) in the above formula, i.c..
Vy(x)=
(x - A GX (x0)
+x)())
24

---

Under review as a conference paper at ICLR 2023
Then, we have that
(x) - Fy(x)
V Vn y" (x))]
Vay((x (x)) A" VX (x)
=
1 x [x))]
V vx,g(x (xx)) ; (xx
V2 1x y" (x))
V V
2n (x, [(x))) V xx, {(())
y' (x))
(x) V 3 (x)
A AX (xx
vy (x))
V m (x y (x)) V v
V "x (x))
1x {(x))] 1 Vayg(x, y (x)) V 1 [(x)
22 f(x))
(x))
7" (x)
V 1
イ VX (x)
[x))]
A T VA (x)
V Vg
- (x)
< O y (x))
V by
[x ((x))) V (x. (x))
+ 1x [x))]
| xx y" (x)) vxyg(x
+
(x, y (x))]
Vin 8 [x)) |||
[x)
+
(x, [(x))
-11
VA (x)
FX Fx((x)
By
2
1
1
2
Lgw SLALx + 1 LALx-0
La &gg
+
8
+
j4g
1g
Ugg
Pi
((-)
1
2
Lyvu
Iuge
+
1
Ligeu
+
1
2
Lgu LATx + 1 [ 8.
Pgg
Bgg
Ngg
Fgg
In (a) the triangle inequality was used. In (b) 1x {(x)) V Xx (x)) and [v2 (x,, X" V (x) in the first and second the bound |A|| < LA.
we add and subtract the expressions
terms, respectively. In (c) we apply Lemma (a) b) Assumption Lemmas 7 and g
The proof is now complete.
Now we have all the results needed to prove Lemma
Proof of Lemma 3 To begin with, the exact and approximate (due to the inexact solution of the LL problem) implicit gradients of the objective F Fx),, are given below.
VF(x) (x)( IVy (x)]" vxf(x,y (x)) FF(x) V-f(x, + [x(x) F(x()
25

---

Under review as a conference paper at ICLR 2023
Then, compute the norm of their difference.
- -VF()) = [Vx](xx -
+ [V((x)' (x.
Vxf(xxyy(xs) VV
v (x))
(o) (xx((, yx
+
yx)(x,
Vx)(x,8(x)) - V.
+ v., - ( V (x,(x, F(x))]
+ [ (x)] Vx ((()) - [Vy (x)]" (x,
1) - (x))]] /)()(x)) Vy (xx F(x))|
V V (7(x)) vxf(xxy
1x)1((x) - y'
Vy (x) 8(x)1I
+ Ly Vy (xxxx
(c)
S Ljd + Ly og, + 6
(I.g Tuy- T.g + I. TTy- = L,d,
(26)
where L5 ر Ly. L, + L L Also, in inequality (a) above we apply the triangle incquality; in (b) we add and subtract the term [Vy*(x) (x)]" (x, fx)). and use triangle inequality; in (c) and
(d) we the Lipschitz gradient property of f (Assumption [ bb) in (e) we apply Assumptions and [[a) and Lemmas] 7 and
a)
Now consider the expression
Fx)]]]. We have that
|VF(()]
+X)) V (x))
- V (x))II + IIV (x)]I (x, (x)
< (1 + Ly-) L Lp,
where we applied Assumption
and Lemma Similarly, we can see that
|
nt [xx f(x))
[vx(x) Fx)((x((x))
< V f (x, (x)) + | (x,
$ + Tuy.) ) Toj T.r.
Therefore, the proof is completed.
1.1.4 PROOF OF LEMMA
Proof.
From the definition of the stochastic gradient in 10 we have
F)(; V=)((x((x);{)
VV,
Taking expectation on both sides and utilizing Assumption we get
E [ = E& //
Eg +1
1,. -FF()).
26

---

Under review as a conference paper at ICLR 2023
Similarly, for the variance of the stochastic implicit gradient, we have
(xx 3 3 (ttp://...///lll0o"x"""""""aa/a.
+ [,
-
V Vxf(xx
+ 2 Vy (x)]lI
- V vxx,
20 + 2 or oî:
where (a) follows from xx + y1? s 2|xx|| ||| and (b) results from Assumption 4 and the application of Lemma Therefore, have the proof.
D.2 PROOFS OF SECTION 3
D.2.1 PROOF OF LEMMA 5
Proof. Let [x"] with x" E be a given arbitrary countable sequence of points. Lemma (adapted from (Lu et al., [020 Proposition 1)) states that for any given point x" in the above sequence, the SC condition holds w.p. for the LL problem [12.. assuming that q is generated from a continuous measure and Axy"(x")) is full row rank. This further implies that the mapping
y"(x), and thereby, the implicit function, F(x) is differentiable w.p. for each given x" in the above sequence (please see the discussion after Lemma I ie.. we have
P(F(x) differentiable at x") for each r = {0, 10,,,,,.0,0....
(27)
This further implies that we have
TP ((x) is differentiable for all (x") (x"];=0)
TP (P (F(x) is differentiable at x"))
1
[F(x) is non-differentiable at x")
r=0
8
2
((F(x) is non-differentiablle at x x"])
r=
where the second equality follows from the fact that P(w E A) = 1- P(w E A*) where A denotes the complement of a measurable event A; the inequality uses the union bound; and the final equality utilizes (27) above.
D.2.2 PROOF OF PROPOSITION
Proof. From Assumption we know that ((x,y) (and thus y(x,y) is strongly convex in with modulus B2 = ph. As result we have that
1(x, y (x)) 1 y (x)) VV,((x g(x,5(xx) 2 g(x,y, y (x)) + (Vgg(x (x)) (x) (x)) + M | (x) (x) (29)
(x) y²(x)) + Mg Ily (x) (x)]1 (28)
2
By definition (x) is the global minimum of the objective y), and so it holds that (V [V,n(x, (x)). yx) - y²(()) 2 Similarly, y is the global minimum of the objective y),,y), and it holds that (V yx y²)))"())))) (x) (x)) 0. Then, using the above inequali-
27

---

Under review as a conference paper at ICLR 2023
ties and adding 28 and 29
get
+ + y 2 x(x (000: < -xxx)
- (xx (M0 -
yx))11 V --y' (x) + +
(x) xx(x)]1 q" ( (x) yx)))
(x) - -x(xx] 1 y (x) (x)
Ny
|||||
(x) - y" (x)l =
Fg
Using the above bound and the fact that f is Lipschitz continuous (it follows from the bounded gradient assumption E a)) it is easy to see that
[F(x - G(x) = (s(x, (x)) -(x. Lyyly" xx)il S L, |lll
Vg
Therefore, the proof is complete.
D.2.3 PROOF OF THEOREM
Lemma 10. Under Assumption 7 I, for any given x E X.
V F() is almost surely continuous at neighborhood around
Proof. To begin with, we already established in Lemma 2 that F is almost surely differentiable at any given x E X. Therefore, for any X' there exists (almost surely) a neighborhood around such that the matrix A corresponding to the active constraints at y (x) remains unchanged, where the gradient Vx*(x) is defined in eq. 66. 7 Further, since A is locally (i.e., around any given x) constant, and the formulas in (6). can be seen as the results of a number of continuous operations over continuous functions, it is implied that Vy" (x) is also continuous function neighborhood around x almost surely. As a result, (x vaf(x, y (x)) + [Vy (x)]² V v (x. y (x)) is almost surely continuous locally around any given x E X.
Proof of Theorem Here we follow reasoning similar to the proof of (Bertsekas 1998 Prop. 1.2.1). However, there are a number of differences that make this proof more challenging. First, in our setting we optimizing an inexact version of the objective F(x) f(x, (x)). using an approximate version of the gradient Fxx). Since the approximate gradient we are using not the gradient of the objective F(x) (the gradient of this function might not even exist), we consider a modification of the standard Armijo rule where additional error term is present. Secondly, in the proof below the (classical) mean value theorem (Bertsekas) 1998 Prop. 1.23) cannot be applied, since cannot ensure that F (surely) differentiable at any given interval over x. As we are going to show below, we use an alternative mean value theorem that does not require such assumption.
To begin with, we know that for the exact implicit objective Fxx) and gradient FF(x) (quantities which we do not have access to) we can find at each iteration a step-size a" such that the following condition holds
F(x") - F(x + a a'd") 2 -aa" [VF((T)) d',
(30)
where d' - with x projx VF(x)))
Next, the difference between the (approximate) objective values of two successive iterates (for simplicity will use the notation x+1 x" + a'd gr+1 x" a'd'; dr is defined in
28

---

Under review as a conference paper at ICLR 2023
Algorithm 1 is
F(x') 1(
= F(x)) - F(x) + F(x)) - F(x + F(x - F(x + F(x - F((
=((x,, -(xxx(((x)) - (x)) F(x) - F(x F(x F(
+ 1 ,y
y' (x++1) 1(8- ,((++))))))))))))
2 -Lylly((x) - 5(x")| + =(()) - 1(x -1
+2 11
- -Lylly((x** - 8(x*+111
2 L oa' [VF(x']] d' - IFa"lld" -
2 L - oa" [VF('') I" d' - L - L-0
-oa" [VF(x')) d' - (ō;r),
(31)
where we set e (8;r) 1 + LF + L,0 In the first inequality, we used the Lipschitz continuity of f and F; in the second inequality Assumption a) and condition (30) were applied: in the third inequality the non-expansive property of the projection operator was used.
Also, we have that
(VF(x) FF(x) "F(x)) T (a' - -
VJ. F(x )d
(VF(x)) FF(xT) (a' a') (FF(x)) +F())) T àà
+ [FF(X)) T / (d' (d'- ar) + [FF(T)]
)" T ar
- VF((x) - VF(x")ll -d'll || + -[VF(()) FF('")
+ +IVF(**)ll - -r [Qx(')) )'ar
s Li (87)² LFI + LFIF5 + [DF(xT)]* a
[ "a (b(rr))
(32)
where (2(5:))
I.Z (8r)²= 2L LT Notice that the results in the second inequality follow from
Lemma 3
Then, combining
31 and 32p we get
F(x") F(x 2 -oa" (FF())) T )²
- - oa"e2(0;r)
= -aa" [&F(*)) T à c((6r))
where <(ōrr) (ō + oan (d;r)();)); notice that lim <6) = In conclusion, we can follow
6-0
this (inexact) Armijo-type rule in our inexact problem; the existence of the (Armijo) step-size is guaranteed by its existence for the exact problem (30).
Now let us move to the main part of the proof, which follows the reasoning used in (Bertsekas) 1998
Prop. 1.2.1). Let (x"} E X be the iterate sequence of our algorithm, and let x E X' be a limit point; the existence of such point is guaranteed by the closedness the set X. Moreover, it is established in Proposition
1 that Fxx) is continuous, and as result it holds that lim,-++00 F(x") = F(X). The
latter results combined with the fact that all convergent sequences are also Cauchy sequences, implies that lim,++so (F(x") F)x*+)))= O.
We want to show that X is a stationary point of F(x). We are going to show that by assuming that the opposite holds, i.e., X is not stationary point of Fxx), and arriving at contradiction. From the Armijo rule of our problem we have that
F(x") - F(x*+1) -oa" [FF(')] T à' -c6:r))
(33)
29

---

Under review as a conference paper at ICLR 2023
Then, consider the following
F(x') - F(x--1)- - F(x") - F(x) + + +
( -
F(x++1) ((x
[(x", -(x",((x)) - (x'))"(x))) + ( - F(x - F(2
+ f(x"' yy (x**))) f(x* (((**)))))))))
L 9(x') + F(x") [(x*=1)++ + - 8
+ L
5(x
$ L1g8 + F(x') - F(x*+1), + Ippa d' - -arl + L,p0+11
I F(x") - F(x + 1,5" + LpLpa' 5 + L,8
Fxx)) F(x cd:rr)
In the first inequality, we used the Lipschitz continuity of f and F; in the second inequality As- and condition (30) were applied: the third inequality the non-expansive property
sumption Ta and
of the projection operator was used. Using the above derivation we can bound the left-hand side of inequality (33 as follows
F(x') F(x*t) (1;r)) F(x') F(x -oa" (fF(x)) T a
a' c(6:r).
It is easy that the left-hand side in the above inequality tends to O. Therefore, lim, +0 (-oa" (FF(x)) T àr -((:rr) < O. In addition, we know that lim, c(); r) = 0
and -0a" [FF(x)] T dr 2 0, Vx E X. From the above statements we can conclude that
lim σa r+ooo
[FF())]
d" ===0.
(34)
Moreover, from the gradient-related assumption we know that for non-stationary point x we have that
lim ER
[tF(T))"
àr <0.
(35)
where(x") J is subsequence with
lim ER.
x" = x. Then, the conditions (34) (35) imply that
lim TE
a" ==00
In the subsequence R we can find an index F 2 O such that
F(x') - $
F'x''''x'' x"
a'
d'
<
a"
TCT DJ - - RR
(36)
8
Similarly with the proof of (Bertsekas)
1998
Prop. 1.2.1) let us introduce the following sequences:
d'
a²1 |
p
|drl
3
The first sequence {p"} is bounded and it admits limit point p with ||pl| 1, that is lim, + p" p. where R denotes the indices of subsequence of R. In addition, tak- ing into account the facts that lim a" 0 and the fact that the sequence [[|d"]] ll is bounded we can easily see that lim, ā" = O.
Dividing both sides of (36 by ā" and using the definitions of f and a from above we get
F(x") F (x" + a p'pp)
-a [F(x"] p e((;r), RR,>F
(37)
a"
30

---

Under review as a conference paper at ICLR 2023
Then, have that (for convenience adopt the notation x* +
-1x -
-(x)) F F( P - [(8--1)
f(x', j(xx)xxx)))))))))))))) f(x' y (x - -
+ + y' (x((++)) - (((++1))
2 - F(x")) L - -((x*t) |]|l F(x) F(
2 F(x') F(X - -
(38)
where the first inequality above follows the Lipschitz continuity of f. and the second incquality an application of Assumption a Incorporating inequality (38 into (37) results to
F(x") F(x" a'p') 0r
8" + [F(x')]
T
Ls
Vr ER (39)
ar
Lebourg's mean value theorem (Lebourg 1979
Theorem 1.7) implies that
F(x" F Fxx")
u Tp'
0r
with u E Fx + a"p*) and n" E [0, where (F()) the Clarke subdifferntial of F. We know that F is almost surely continuously differentiable (Lemma 10) at any x" + ā "'p" E X, and so the Clarke subdifferential at x" + a p' becomes w.p. 1 equal to F + a'pp p")). Note that the we cannot use here the (classical) mean value theorem (Bertsekas) 1998 Prop. 1.23), in the proof of (Bertsekas
Prop. 1.2.1), because it requires that the function F F(x) is (surely) differentiable on the interval x + p").
1998
Then, we can rewrite the expression in 39 as follows
-b, 8 + 8"+1
VF + + p <-o (FF(x)] p' p(-r();)), Vr RR,
ar |
where ā" E [0,ā")
Using the assumption that 0 < 8" O(e"), where c" is some sequence with lim r C² 0,
and the fact that lim,- d''l * 0 (because of the assumption that the sequence x" converges to non non-stationary point), we compute the limit in the above expression and get
-VF(()) p < - - (VF(x)) p
0 (1 (1-o)
0 0 VV p.
(40)
However, note that (x((*)] T pr= = F( a and therefore if we take limits in both sides we obtain
[drl||
lim sussup.c +
6 F(x))
[VF())]T p
(41)
lim lim sup, |d'
due to the gradient-related assumption. We notice that expressions 40 and tion. Therefore, x is a stationary point of Fxx).
41 lead contradic-
The proof is complete.
31

---

Under review as a conference paper at ICLR 2023
D.2.4 WEAKLY-CONVER OBJECTIVE: PROOF OF THEOREM 2
Proof. Define X = arg min (((2) + (
2 fix-- =1²}
Using the definition of Moreau envelope, we
=ERde
have
B[H1//((x ]] E F(*))
xx - xT]]]
2
(a) E F(*))
+ 0
|proixx - | -VF(())))) - (x)))
2
(b) E [(*)) 11x - (FF(((E) - -
-(x*) + f -x'11 2(x' -x" -1
2 (( + Li
[Ix" x112 - 2(xx - -x,0V1('';e)
2
+ + (F(( 5 - (F(x")] + 233 (((()) ||}
(d) I F(x*) + 0 ||x x11 28(x'' x", VF )) + 20 +[pr]
2
< F(X)) + 0
||x -x 23 (x x VF(x')
+ +23 (x FF VF(x") -282 (07 + 1²7)
Tomn 11
(42)
where (a) follows from the fact that + E X' and x" E X:; (b) results from the non-expansiveness of the projection operator; (c) uses ||a bl| 2||a|| |lb| and (d) results from the application
of Lemmas and 4
Next, considering Term I and Term separately in 442 above. For Term we get using the weak convexity of F())
Term I = -x" -X"'xVVV((") + 2,111x - -1122
- +
We bound Term II using the Young's 's inequality
Term Il = (x" - x", Fx(x) VF(x')
|x" - 12 + 1 [IFF(x") VF(x')
2p
(c) L 2
61 x11 1.202
2p
where (c) follows from Lemma using the definition of x", we get
3 Next, substituting the bounds of Term I and Term II in 42 and
Bl S F(*) + - +T [(()) F(x") + pl|x* - xx1[]]
p3 13. + 38p(08 + +TT)
2p
+ 03 13.88 + +00000 + Lzz
S (11p(x") + PB [((') - F(x") + p||x -
2p
Temm
(43)
32

---

Under review as a conference paper at ICLR 2023
Next, we bound Term III in 43) above.
Term III = F(x') ) F(x') + p||x"* 2
P 1xx
22p-A p |x x111
F(x)
2
3p - 20
3p- 2p
|x 11
|1
|VH2)p(x")1]
2
2/²
where the last equality follows from
13 and the first inequality follows from the fact that F(x) +
f "|1x" -x12 is (p- p)-strongly convex. This implies the following
F(X") + 2 1xx - x2 F(xx) - (VF((s)) + p(x" - x²),,² 87) 0 3-7---1 p '|x" - 11
2
p x - x1
where the second inequality results from the definition of x*. Finally, substituting Term III in (43 and rearranging the terms we get:
8 2p- -p 20
| (x')((x()('')'" I| S E (x)))x)) H1za(x ) + p0p + +bT))
P3
2p 1.7002
Summing over all r E (0,1,.... T 1) and dividing by T, we get
T [HH1)(("))1 <
2
H1/0(x9) H-
3T + 3p + D2)) + P
12202
2p 3p
2p
Therefore, we have the result.
D.2.5 STRONGLY-CONVEX OBJECTIVE: PROOF OF THEOREM 3
Proof. Using the update rule of the Algorithm 2 we have
E x|xx+11_ - x11 = L projx (x" 3r FF((xx - x" 112
-x"1
EE Ellproix (x" 3" FF(('())) proix(x'))1
(a)
E||x" 5r FF(x')) x"
x 1 (8") V - xx, (F(("))))
E
|x - + -F(x)))
+2(8") 21I - -23 -x", ((('))
E 211x -x 2(3)) BB) 23 -xx -x,, x}F((T))
Xx + B3) 2x -xx''''XVVVX xVVF()))
-,8 -x'xxx,
-x', VF(x') VF(X))
x - +(()) + BB} 233 F((") - -F*) - 1--00" - 12
+ 2 x" - -x" -x'1)(F(X")) VF(''I]
E (1 (1- 3r X - 2 - BB) 23 F( - F* + 2 DxLro)
where in (a) the non-expansive property of the projection operator is applied, in (b) we add and subtract the term F(x"), the well-known inequality ||a bll2 2||a|12 2||b| and in
33

---

Under review as a conference paper at ICLR 2023
the last term we utilize Lemma 4 (c) results from the application of Lemmas 3 and 4 (d) uses
connexitty (Assumption of F()) and Schwartz inequality; finally, (e) results from the application of Lemma 3 and Assumption lbb).
Rearranging the terms, we get
2,9" Fx - FM] I E
(1
uE )1)x")
-x-1-x112- 2(5)) + BB)) + +38 Dx L 25 |x | - x21 + 88 ( + B3) + Dx
B[F(x") - F*] v E
PF
||x x=1
23
2
Summing over E {0..... T 1). multiplying by 1/T and using the fact that 3r / we get
T Σ E[F(x) F*] -
r||x x112 (r 1)[[x
x²13
T-1 1
+
Σ
3r ()} + B3)) + D
Telescoping the sum we get the following
(o +B++ log(T)
T Σ B[F(X*) FM]
s
MF
|x2 - 1x1
+ DxLp8
2
MF
T
( + BB) log
log(T) (T)
+ DxLFE.
PF
T
Therefore, we have the proof.
D.2.6 CONVEX OBJECTIVE: PROOF OF THEOREM
Proof. From the update rule of Algorithm 2 we have for 3 = 3 for all a E (0,1....., T- 1}
E x1 x" || E [||opr - FVF((x; x11
(a)
Elllproj (x" - (VF(("); - x |1
El[|x" - FFF(" (") 1²]
E[||x" xx1|| 112 82 / : 23(x x", (F(x'
Ei||x" - x || + 2,3 Fxx ;-) -
-23(x- -x,, VF(x') 23((x - xx, VF(x') VFF(x))
[[[[x - x11 2.3 2/ 23(F(x') - F*)
+ + xl11 [[F((*)) - VF(*"|II
[[||x x x 1 228 + ET-) 26( F LF
where (a) follows from the fact that x" X:: (b) results from the non-expansiveness of the projection operator; (c) uses ||a - b11² = ||] + |b|² 2(a, b): (d) utilizes the fact that |a 2
2||a||² + 2| bil² and unbiased gradient from Lemma (e) results from Lemmas and the
convexity assumption of the implicit function (Assumption 6 with μF = 0) and the Cauchy Schhwrrtz inequality; and (f) results from Assumption bb) and Lemma
Summing over r E {0, 10.....,2. T 1}, multiplying by 1/T and rearranging the terms, we get
|x'-x*11
B[F(x") - F'
+ 3(0
Itp) + DxLrō.
T
2ST
34

---

Under review as a conference paper at ICLR 2023
Using Jensen's 's inequality and denoting 1/2 Er=o x', we get
-
|x|
x-1
+ 3(o + Itp) + DxLF
2,37
Therefore, have the proof.
35


Reviews:
[{"review_id": "q8ciW4gmpLv", "reviewer": "Reviewer_YhfE", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "Authors extend implicit differentiation to constraint bilevel optimization problem. Assuming usual qualification conditions, they provide a implicit differentiation formula. Experiments are proposed on toy  bilevel problem, and real adversarial learning.\n", "summary_of_the_review": "I think that differentiating efficiently constrained optimization problem is extremely important.\nMy current score is due to some important references missed in the literature review, as well as problems which can be solved with preexisting techniques in the experiments. **If authors solved these two issues (which can take some time I agree) I will raise my score**.", "strength_and_weaknesses": "Weaknesses:\n\n**Literature review** Non-smooth optimization\n- The provided results are very interesting and seems to extend older and more restrictive results [1] [3] [9]. More recent results on implicit differentiation for non-smooth problems also include [5] and [6].\n- In particular, assumptions 1c and 1e seem to imply assumption 7 of [3] or assumption 2 of [4]. For Lasso-type problems, [1] and [3] restricts the linear system to solve only to the non-zeros coefficients (ie the non-active constraints in the dual). It seems that you observe the same kind of computational speedups for $\\nabla {\\bar \\lambda}^*(x) $, but not for $\\nabla_{y^*}(x)$. Could you comment on this?\n- Related to the previous point, could you comment on the algorithmic complexity of the proposed methods? (formula in Lemma 2 for instance). It feels like one could inverse a linear system of size the dimension of the active constraints (using the tangent space of the projection operator as in [4])\n- In the same vein, if the constraint in the inner bilevel optimization problem is rewritten as an indicator over a set, would it be possible to apply the framework of [4] to your problem?\n\n**Literature review** Convex programming differentiation:\n- It seems that other works previously obtained implicit differentiation for quadratic programming [7] and more general constrained optimization problems [8]. How does the proposed implicit differentiation formula compares to this previous approaches?\n\n\n**Proposition 1**: Proposition 1 seems misleading to me, it requires Assumption 1 to be true for all $x$, which is very strong. It seems to me that Assumption 1 is true for almost every $x$, and thus the $x \\mapsto G(x)$ is continuous by part, not on all $\\khi$. Could authors comment on this.\n\n**Assumption 3** is very strong, and is usually assumed only locally, see assumption 4 of [3], or Assumption 3 of [4].\n\n**Experiments**\n- I found it underwhelming that authors do not propose experiments on problem with non-separable matrix constraints. The proposed constrained problems are separable: on these examples one could use [3] and [4] to compute the hypergradient. **In other words: the problems considered in the experiments could be solved with preexisting techniques**.\n- I think there are plenty of other interesting non-separable problems, I was wondering if authors considered experiments on more complex problems, and if authors planned to released open-source code, potentially compatible with pytorch?\n- I am not sure what is the takeaway message from the *Adversarial Learning* part, could authors comment on it?\n\n\nTypos:\np27 in appendix \"Proof of theorem1\" >> \"Proof of Theorem 1\"\n\n\n\n[1] Mairal, J., Bach, F. and Ponce, J., 2011. Task-driven dictionary learning. IEEE transactions on pattern analysis and machine intelligence, 34(4)\n\n[2] Deledalle, C.A., Vaiter, S., Fadili, J. and Peyré, G., 2014. Stein Unbiased GrAdient estimator of the Risk (SUGAR) for multiple parameter selection. SIAM Journal on Imaging Sciences, 7(4), pp.2448-2487.\n\n[3] Bertrand, Q., Klopfenstein, Q., Massias, M., Blondel, M., Vaiter, S., Gramfort, A. and Salmon, J. Implicit differentiation for fast hyperparameter selection in non-smooth convex learning. JMLR 2022.\n\n[4] Mehmood, S. and Ochs, P., 2022. Fixed-Point Automatic Differentiation of Forward--Backward Splitting Algorithms for Partly Smooth Functions. arXiv preprint arXiv:2208.03107.\n\n[5] Bolte, J., Le, T., Pauwels, E. and Silveti-Falls, T., 2021. Nonsmooth implicit differentiation for machine-learning and optimization. Advances in neural information processing systems, 34, pp.13537-13549.\n\n[6] Bolte, J., Pauwels, E. and Vaiter, S., 2022. Automatic differentiation of nonsmooth iterative algorithms. arXiv preprint arXiv:2206.00457.\n\n[7] Amos, B. and Kolter, J.Z., 2017, July. Optnet: Differentiable optimization as a layer in neural networks. In International Conference on Machine Learning (pp. 136-145). PMLR.\n\n[8] Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S. and Kolter, J.Z., 2019. Differentiable convex optimization layers. Advances in neural information processing systems, 32.\n\n[9] Bertrand, Q., Klopfenstein, Q., Blondel, M., Vaiter, S., Gramfort, A. and Salmon, J., 2020, November. Implicit differentiation of Lasso-type models for hyperparameter optimization. In International Conference on Machine Learning (pp. 810-821). PMLR\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "p3qgkqSxXFL", "reviewer": "Reviewer_1APN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper provides gradient descent-based for solving bi-level optimization problems where the lower-level problem has a strongly convex objective and linear inequality constraints, using implicit gradients. The authors derive conditions under which the implicit objective is differentiable, and propose a perturbation-based smoothing technique to address non-differentiable cases. The authors also propose adaptive step sizing techniques for the gradient descent procedure to ensure convergence. They empirically demonstrate the efficacy of their method on two test cases: (1) linearly constrained quadratic bilevel problems, and (2) adversarial training.", "summary_of_the_review": "This paper provides a simple, powerful, and principled approach for addressing a class of bi-level optimization problems using gradient descent, specifically leveraging implicit gradients (combined with perturbation-based smoothing and adaptive step sizing). The authors could do a better job situating their work within the literature on implicit layers/differentiable optimization - in my impression, the existence of that literature serves to diminish some of the empirical contributions of the present work, but enhances the significance of some of the theoretical contributions.", "strength_and_weaknesses": "Strengths:\n* The approach is simple yet powerful. It leverages implicit differentiation and gradient descent to address an important class of bi-level optimization problems, and does so in a very principled manner - establishing theoretically for which cases differentiation-based techniques are likely to work, introducing perturbation-based smoothing to expand the set of problems for which such methods might (approximately) work, and then utilizing techniques such as adaptive step sizing to ensure convergence in a wide variety of cases.\n* The experiments, though not overwhelmingly convincing, do reasonably demonstrate the efficacy of the proposed method.\n* The paper is accessible and clearly written.\n\nWeaknesses:\n* The authors do not seem to be aware of the large body of work in implicit differentiation of optimization problems within the deep learning literature - see, e.g., the list below. The authors should be sure to discuss and situate their work within this literature, as it is very closely related. In particular, [8] below also uses implicit differentiation to address a class of bilevel optimization problems via gradient descent.\n* Minor: In Equation (1a), it would be cleaner if the notation $f$ were not overloaded.\n* Minor: The paper is missing a Conclusion section, which is standard for such papers.\n\nOverarching note: On the one hand, the existing literature on implicit layers diminishes the contribution of this work from an empirical perspective. On the other hand, this paper perhaps inadvertently fills several gaps in the implicit layers literature (which often lacks principled analyses), thus contributing to the strengths of the present work. For instance, these works often do not contain analysis of the quality of the gradient under an approximate solution to the optimization solution, but the present work does.\n\nExample literature on implicit differentiation of optimization problems:\n* [1] Brandon Amos and J Zico Kolter. “OptNet: Differentiable optimization as a layer in neural networks.” International Conference on Machine Learning. 2017.\n* [2] Josip Djolonga and Andreas Krause. “Differentiable Learning of Submodular Models.” Advances in Neural Information Processing Systems (NeurIPS). 2017.\n* [3] Priya L. Donti, Brandon Amos, and J. Zico Kolter. “Task-based End-to-End Model Learning in Stochastic Optimization.” Advances in Neural Information Processing Systems. 2017.\n* [4] Sebastian Tschiatschek, Aytunc Sahin, and Andreas Krause. “Differentiable submodular maximization.” International Joint Conference on Artificial Intelligence. 2018.\n* [5] Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J Zico Kolter. “Differentiable convex optimization layers.” Advances in Neural Information Processing Systems (NeurIPS). 2019.\n* [6] Stephen Gould, Richard Hartley, and Dylan Campbell. “Deep declarative networks.” IEEE Transactions on Pattern Analysis and Machine Intelligence 44.8 (2021), 3988–4004.\n* [7] http://implicit-layers-tutorial.org/\n* [8] Priya L. Donti, Aayushya Agarwal, Neeraj Vijay Bedmutha, Larry Pileggi, and J. Zico Kolter. “Adversarially Robust Learning for Security-Constrained Optimal Power Flow.” Advances in Neural Information Processing Systems. 2021.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "H3taXajJIK", "reviewer": "Reviewer_gXua", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors consider the problem of bilevel optimization when the lower level optimization (LL) problem is strongly convex and has to satisfy some linear constraints. The main issue with the constraints in the lower level optimization problem is that the solution of the LL problem might not be differentiable and hence applying standard gradient based method to the upper level optimization is not possible. The authors claim that:\n  1. They provide a randomized smoothing procedure that makes the LL problem differentiable. Then they show that there is a way to compute the derivatives of the solution of the LL problem approximately and that this is enough for solving the bilevel problem.\n  2. The authors then provide experiments that illustrate the advantage of their method compared to state-of-the art.", "summary_of_the_review": "  Above I explained an issue that I have with the current presentation of the paper. I feel that I don't understand something very important and this makes it difficult for me to judge the overall contribution of the paper. Since ICLR gives us this opportunity I would like to first discuss about the following issue and if this is resolved I commit to updating fast my review to address the contributions of the paper.", "strength_and_weaknesses": "Strengths\n======================\n  - The problem of finding provably convergent methods for bilevel optimization problems with constraints on the LL problem is very well-motivated.\n\n\nComments to the authors\n========================\n\n  Below I explain an issue that I have with the current presentation of the paper. I feel that I don't understand something very important and this makes it difficult for me to judge the overall contribution of the paper. Since ICLR gives us this opportunity I would like to first discuss about the following issue and if this is resolved I commit to updating fast my review to address the contributions of the paper.\n\n  My issue is that I don't see how the addition of the term $q^T y$ makes the function $y^*(x)$ smooth. In particular, I don't even see how this works for the example in page 4. Let me explain with the following simpler example.\n\n$\\min_{x \\in [0, 1]} x + y*(x) s.t. y^*(x) = \\arg\\min ((y - x)^2 | 1/2 <= y <= 1) (1)$\n\n  This is almost the same example as in page 4 expect that I slightly changed the objective and the boundaries of y, which I don't understand why they are so complicated in the example in the paper. Now the solution $y^*(x)$ of the LL problem in $(1)$ is similar to the example of the paper. $y^*(x) = 1/2$ for $x <= 1/2$ and $y^*(x) = x$ for $x > 1/2$. So, indeed $y^*(x)$ is not differentiable at $x = 1/2$. Also, unless I am missing something, (1) satisfies Assumptions 1 and 2. Now let's consider the perturbed problem\n  $y^*(x) = \\arg\\min {(y - x)^2 + q y| 1/2 <= y <= 1}$\n  where $q$ is sampled from some distribution. In this case, the solution $y^*(x)$ becomes $y^*(x) = 1/2$ for $x <= (1 + q)/2$ and $y^*(x) = x$ for $x > (1 + q)/2$. So, $y^*(x)$ is still non-differentiable with some constant probability, assuming that the distribution of q has constant probability in the interval $[0, 1]$. The only thing that changed is the point where $y^*(x)$ is non-differentiable. I get exactly the same behavior when solving the example of page 4 in Mathematica it is just that the closed form solution is much more involved.\n\n  The only way that I can see to make $y^*(x)$ smooth is if we define\n  $y_q^*(x) = \\arg\\min \n9(y - x)^2 + q y| 1/2 <= y <= 1)$\n  and then $y^*(x) = \\mathbb{E}_q[y_q^*(x)]$, then maybe there is a way to show that $y^*(x)$ is smooth, at least this is indeed happening in the example of page 4 and the above example. But:\n  1. the authors never mention that they take the expected value with respect to q, and\n  2. looking in Algorithms 1 and 2, the authors seems to first sample q from its distribution and then proceed with a fixed value of q for the rest of the algorithm as if $y^*(x)$ is smooth. If they indeed want to take the expected value with respect to q then they need to get a different sample q every time they compute the gradient of $y^*(x)$. Also, they need to argue that this additional stochasticity does not affect their algorithm.\n\n  I am very confused with the above. I apologize in advance if I am missing something trivial here and I am looking forward to your response.\n\n(I apologize for the format issue in my review, I just realized and fixed it)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "2Sun2oWRhso", "reviewer": "Reviewer_eqw3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies a special class of bilevel optimization, where the inner problem has linear constraints. For this problem, one major difficulty is that outer (main) problem might be non-differentiable. The authors elegantly address this challenge by constructing a smoothed approximation of the original problem via adding noise to the inner problem. The show their smoothed version is a good approximation of the original problem, and has differentiable gradients. They then developed implicit gradient methods on the smoothed problem, and prove nice convergence rates for the original problem.  ", "summary_of_the_review": "I find the smoothed technique for constrained bilevel optimization is novel and interesting, and I vote for acceptance.", "strength_and_weaknesses": "On the smoothing technique:\nThis paper proposes a very novel way of smoothing the constrained bilevel optimization problem by slightly perturbing the objective function of the inner problem. The perturbation only has a small influence on the main problem (Proposition 2), but it makes the problem smooth and differentiable. I think the idea is novel and interesting, and may also be useful in other related optimization problems.\n\n\nOn the convergence guarantees: \n1)\tThe non-convex non-smooth problem is in general NP-hard, and it is a bit supervising that the algorithm can still converge to the stationary point (Although asymptotically). But I have a hard time understanding Theorem 1, especially the definition of $hat{d}^r$. Can the authors help me understand this condition (e.g., intuitively, what is $hat{d}^r$? and why the algorithm can still converge when the problem is non-convex non-smooth)?\n2)\tOn the other hand, when the functions are non-smooth by convex/strongly convex, I am not sure about the significance of the proposed algorithm: It seems to me that, now since we have a closed form of gradient, we could just to GD (or other more advanced algorithms) and still have similar rates. What are the advantages of the proposed methods? \n\nOn the writing: \nThis paper is in general very easy to read. \n\n\nOther comments:\nThis work reminds me of Nesterov’s excessive gap technique [1]/ Nesterov’s smoothing technique [2] for bilevel (min-max) constrained optimization problem. For the inner function, they added a smoothed regularizer to smooth the function instead of using perturbation. Moreover, some recent work shows that in some cases perturbation and regularization are strongly related [3]. I wonder if the authors could add some comments on this point? \n\n\n\n[1] https://epubs.siam.org/doi/pdf/10.1137/S1052623403422285\n[2] Smooth minimization of non-smooth functions. \nhttp://luthuli.cs.uiuc.edu/~daf/courses/Optimization/MRFpapers/nesterov05.pdf\n[3] Perturbation Techniques in Online\nLearning and Optimization https://dept.stat.lsa.umich.edu/~tewaria/research/abernethy16perturbation.pdf\n\nThere are two definitions of y^*(x) (1b and 5b), one is the exact inner solution and the other one is the approximation. I wonder if the authors could use different notions for the two to make it more clear?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject