On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation
Authors: Jeongyeol Kwon
Dohyun Kwon
Stephen Wright
Robert D Nowak
Venue: ICLR 2024 spotlight (2024)
Keywords: Bilevel-Optimization
Penalty Methods
Landscape Analysis
Non-Asymptotic Analysis
First-Order Methods
Primary area: optimization
TL;DR: We establish a strong connection between the penalty function and the hyper-objective by explicitly characterizing the conditions under which the values and derivatives of the two must be close

Abstract: In this work, we study first-order algorithms for solving Bilevel Optimization (BO) where the objective functions are smooth but possibly nonconvex in both levels and the variables are restricted to closed convex sets. As a first step, we study the landscape of BO through the lens of penalty methods, in which the upper- and lower-level objectives are combined in a weighted sum with penalty parameter $\sigma > 0$. In particular, we establish a strong connection between the penalty function and the hyper-objective by explicitly characterizing the conditions under which the values and derivatives of the two must be $O(\sigma)$-close. A by-product of our analysis is the explicit formula for the gradient of hyper-objective when the lower-level problem has multiple solutions under minimal conditions, which could be of independent interest. Next, viewing the penalty formulation as $O(\sigma)$-approximation of the original BO, we propose first-order algorithms that find an $\epsilon$-stationary solution by optimizing the penalty formulation with $\sigma = O(\epsilon)$. When the perturbed lower-level problem uniformly satisfies the {\it small-error} proximal error-bound (EB) condition,  we propose a first-order algorithm that converges to an $\epsilon$-stationary point of the penalty function using in total $O(\epsilon^{-7})$ accesses to first-order stochastic gradient oracles. Under an additional assumption on stochastic oracles, we show that the algorithm can be implemented in a fully {\it single-loop} manner, {\it i.e.,} with $O(1)$ samples per iteration, and achieves the improved oracle-complexity of $O(\epsilon^{-5})$.

Under review as a conference paper at ICLR 2024
ON PENALTY METHODS FOR NONCONVEX BILEVEL OPTI- MIZATION AND FIRST-ORDER STOCHASTIC APPROXIMATION
Anonymous authors Paper under double-blind review
ABSTRACT
In this work, study first-order algorithms for solving Bilevel Optimization (BO) where the objective functions are smooth but possibly nonconvex in both levels and the variables are restricted to closed convex sets. As first step, study the landscape of BO through the lens of penalty methods, in which the upper- and lower- level objectives combined in weighted sum with penalty parameter particular, we establish strong connection between the penalty function and the hyper-objective by explicitly characterizing the conditions under which the values and derivatives of the two must be -close. A by-product of our analysis is the explicit formula for the gradient of hyper-objective when the lower-level problem has multiple solutions under mild regularity conditions, which could be of independent interest. Next, viewing the penalty formulation as -apra-pproiiiaaionn of the original BO, we propose first-order algorithms that find an e-stationary solution by optimizing the penalty formulation with o = O(c). When the perturbed lower-level problem uniformly satisfies the small- error proximal error-bound (EB) condition, we propose a first-order algorithm that converges to an e-stationary point of the penalty function using in total O(-7) accesses first-order stochastic gradient oracles. Under an additional assumption on stochastic oracles, we show that the algorithm can be implemented in fully single-loop manner, i.e., with O(1) samples per iteration, and achieves the improved craple-complexity of O(e
O. In
INTRODUCTION
Bilevel Optimization (BO) Dempe (2003); Colson et al. (2007); Dempe et al. (2015) is a versatile framework for optimization problems in many applications arising in economies, transportation, operations research, and machine learning, among others Sinha et al. (2017). In this work, we consider the following formulation of BO:
min xEX EY
f(z,v" = [x 8² [)]
s.t. y" E arg min g( v) = Eg E),, vey
where ff and are continuously differentiable and smooth functions, X' C Rd and y S Rd are closed convex sets, and Ç and & are random variables (e.g., indexes of batched samples in empirical risk minimization). That is. (P) minimizes I over E X' and y E 3 (the upper-level problem) when y must one of the minimizers of g(x,,) over y E y (the lower-level problem).
Scalable optimization methods for solving (P) are in high demand to handle increasingly large-scale applications in machine-learning, including meta-learning Rajeswaran et al. (2019), hyper-parameter optimization Franceschi al. (2018); Bao et al. (2021), model selection Kunapuli et al. (2008); Giovannelli et al. (2021), adversarial networks Goodfellow et al. (2020); Gidel et al. (2018), game theory Stackelberg et al. (1952), and reinforcement learning Konda & Tsitsiklis (1999); Sutton & Barto (2018). There is particular interest in developing (stochastic) gradient- deseeettteeeent--ee deeseett-based methods due to their simplicity and scalability to large-scale problems Ghadimi & Wang (2018); Chen et al. (2021); Hong et al. (2023); Khanduri et al. (2021); Chen et al. (2022); Dagréou et al. (2022); Guo et al. (2021); Sow et al. (2022);
al. (2021); Yang al. (2021). One popular approach perform direct gradient-descent on the hyper-objective (xx) defined as follows:
(x) == min f where S(x) arg min g
yES(z)
yEy

---

Under review as a conference paper at ICLR 2024
but this requires the estimation of (ab(2)). which we refer as implicit gradient. Existing works obtain this gradient under the assumptions that g(,, y) is strongly convex in y and the lower-level problem is unconstrained, i.e., 3' F There is no straightforward extension of these approaches to nonconvex and/or constrained lower-level problems (i.e. y C &R is defined by some constraints) due to the difficulty in estimating implicit gradients; see Section A. for more discussion in detail.
The goal of this paper is to extend our knowledge of solving BO with unconstrained strongly-convex lower-level problems
broader class of BO with possibly constrained and nonconvex lower-level problems. In general, however, when there is not enough curvature around the lower-level solution, the problem can be highly ill-conditioned and no known algorithms can handle it even for the simpler case of min-max optimization Chen et al. (2023b); Jin et al. (2020) (see also Example I). In such cases, it could be fundamentally hard even to identify tractable algorithms Daskalakis et al. (2021).
To circumvent the fundamental hardness, there have been many recent works on BO with nonconvex lower-level problems (nonconvex inner-level maximization in min-max optimization literature) under the uniform Polyak-LLjasiewicz (PL)-condition Karimi et al. (2016); Yang et al. (2020; 2022); Xiao et al. (2023a); Huang (2023); Li et al. (2022a). While this assumption does not cover all interesting cases of BO, it can cover situations in which the lower-level problem is nonconvex and where it does not have a unique solution. It can thus be viewed as a significant generalization of the strong convexity condition. Furthermore, several recent results show that the uniform PL condition can be satisfied by practical and complicated functions such as over-parameterized neural networks Frei & Gu (2021); Song et al. (2021); Liu et al. (2022).
Nevertheless, to our best knowledge, no algorithm is known to reach the stationary point of (b(x) (i.e., to find where Vιb(x) 0) under PL conditions alone. In fact, even the landscape of (b(x) has not been studied precisely when the lower-level problem can have multiple solutions and constraints. We take a step forward in this direction under the proximal error-bound (EB) condition that is analogous to PL but more suited for constrained problems'.
1.1 OVERVIEW OF MAIN RESULTS
Since it is difficult to work directly with implicit gradients when the lower-level problem is nonconvex, we consider a common alternative that converts the BO (P) into equivalent constrained single-level problem, namely,
min [xx v) zEX' y
s.t. g(x, S min ((z, =);
(Peon)
=E)
and finds a stationary solution of this formulation, also known as an (approximate)- KKTT solution Lu & Mei (2023); Liu al. (2023); Ye et al. (2022). (Poon) suggests the penalty formulation
min a of v) + (g(2, v) - min g(2, wEX.WE
(P (Ppen)
xE)
with some sufficiently small a > Our fundamental goal in this paper is to describe algorithms for finding approximate stationary solutions of pen))), as explored in several previous works White & Anandalingam (1993); Ye et al. (1997); Shen & Chen (2023); Kwon et al. (2023).
In pursuing our goal, there two important questions to be addressed. The first one is a landscape question: since (Ppen) is merely an approximation of (P), it is important to understand the relationship between their respective landscapes, which have remained elusive in the literature Chen al. (2023b). The second one is an algorithmic question: solving (Ppen) still requires care since it involves a nested optimization structure (solving inner minimization problem over 2), and typically with very small value of the penalty parameter o > 0.
Landscape Analysis. Our first goal is bridge the gap between landscapes of the two problems (P) and pen))). By scaling (P pPp))), we define the penalized hyper-objective vo (x):
1 min (af(x, v) + g(a, v)) - min g(1r yEy
v>(x) =
=E)
As mentioned earlier, without any assumptions on the lower-level problem, it is not possible to make any meaningful connections between the (z) and (xx), since the original landscape (x))) itself may
In the unconstrained setting, EB and PI. are known be equivalent conditions, see e.g., Karimi al. (2016)
2

---

Under review as a conference paper at ICLR 2024
not be well-defined. Proximal operators are key to defining assumptions that guarantee nice behavior of the lower-level problem.
Definition The proximal operator with parameter p and function f()) over è is defined as
prox (0) = arg min =ee
{of(=) + =ll= - -
(3)
We now state the proximal-EB assumption, which crucial to our approach in this paper.
Assumption (Proximal-EB) Let ( = o((x,)) + g(a, :) and T(x,o) arg arg minyey ha (1r, v). We assume thut for all e x and 10, ha (x, satisfies the (μ, 8) -pprrxiimll error bound:
proxpp ph. (z..) (2) 2 p dist(y. T(z,o))
(4)
for all y E y that satisfies p -ly prox
(v) S 8 with some positive parameters pi, 6, ap >
As we discuss in detail in Section 3, the crux of Assumption is the guaranteed (Lipschitz) continuity of solution sets, under which we prove our key landscape analysis result:
Theorem 1.1 (Infrrmal) Under Assumption I (with additional smoothness assumptions), for all E X such that at least one sufficiently regular solution path y (ar,r) exists for E oo) we have
1bb - ====)==== (V) ==)=))==000////
As a corollary, our result implies global ((r) apprxxiiooxi of (hr()) for the special case studied in several previous works (e.g., Ghadimi & Wang (2018); Chen et al. (2021); Ye et al. (2022); Kwon et al. (2023)), where ((r, :) is (locally) strongly-convex and the lower-level prohlem is unconstrained. To our best knowledge, such a connection, and even the differentiability of (zz), is not fully understood for BO with nonconvex lower-level problems with possibly multiple solutions and constraints. In particular, the case with possibly multiple solutions (Theorem 3.1) 1) discussed under the mild assumptions of solution-set continuity and additional regularities of lower-level constraints.
Algorithm. Once we show that V (x) is an O(o)aapproiimmaion of Vıh(z) in most desirable circumstances, it suffices to find e-stationary solution of (z). However, still directly optimizing (x) is not possible since the exact minimizers (in y) of ha (z, y) = ff [z. y) + g( y) and g(x, y) unknown. Thus,
the alternative min-max formulation:
min max vh (,,,,,,=)) ha (x, v) g(x, 2) REX sEy
(P (Paadle
Once we reduce the problem to finding an e-stationary point of the addlee-pint problem (P (Psnddie), we may invoke the rich literature on min-max optimization. However, even when we assume that g(x, :) satisfies the PL conditions globally for all y E Rd,, plug-in min-max optimization method (e.g., Yang et al. (2022)) yields an oralle-copplexity that cannot be better than O Oa-- -4e -t with stochastic oracles Li et al. (2021), resulting an overall ( complexity bound when a O
As pursue e-saddle point specifically in the form of (P (adddd))), show that can achieve better complexity bound under Assumption We list below our algorithmic contributions.
In contrast to previous work bilevel min-mat optimization, (e.g., Ghadimi & Wang (2018); Ye et al. (2022); Yang et al. (2020)), Assumption holds only in neighborhood of the lower-level solution. In fact, we show that only need nice lower-level landscape within the neighborhood of solutions with 088)ppoxiimal error.
While we eventually set o = Oc),, it can be overly conservative to choose such a small value of from the first iteration, resulting in slower convergence rate. By gradually decreasing penalty parameters (ox) polynomially as hm for some >> 0, we save an O(e a -orrrr of oracle-complexity, improving the overall complexity ( (c- with stochastic oracles.
3

---

Under review as a conference paper at ICLR 2024
If stochastic oracles satisfy the mean-squared smoothness condition, i.e., the stochastic gradi- ent is Lipschitz in expectation, then we show a version of our algorithm can be implemented in a fully single-loop manner (i.e., only O(1) calls to stochastic oracles before updating the outer variables 2) with an improved cracle-comllexity of (ce-)) with stochastic oracles.
In conclusion, we show the following result this paper:
Theorem 1.2 (Informal) There exists an iterative algorithm which finds an e-stationary point I. of do (x) within a total OO=-)) access to stochastic gradient oracles under Assumption I with Occ). If the stochastic gradient oracle is mean- saaa---arred smoothness, then the algorithm can be implemented a fully single-loop manner with improved complexity of ()) Furthermore, if the condition required in Theorem 1.1 holds at To then I. is an O ((())sttttiorry point of (x))).
Due to space constraints, in the main text, we only present our landscape analysis of penalty and original formulations, and defer the algorithm specification to appendix.
2 PRELIMINARIES
We state several assumptions on (P) to specify the problem class of interest. Our focus is on smooth objectives whose values are bounded below:
Assumption f and g are twice -ifiiuueusyy-dffffennttbbble and f,11- 14,1 -smoohh jointly in (x. v) respectively, i.e., [ y)ll 4 and [|V2 y)ll S for all X. y
Assumption The following conditions hold for objective functions f and g:
1. f and g are bounded below and coercive, i.e., for all X, f(x, g(..)))))))))))))) o0 -00 for all
y E Y, and fxx v). g(., y) + +oc as llyll - co.
2. v (z, 8)ll S for all E N.y y
We also make technical assumptions the domains:
Assumption The following conditions hold for domains X and y:
1. x,Y are convex and closed.
2. y is bounded. i.e., max,ey ||v|| < Dy for some Dy = (1). Furthermore, we assume that
Cj max [f v)1 0(1 is bounded.
3. The domain Y can be compuctly expressed with at most 2 O inequality constraints {g((y) & Ofie(ma) with convex and twice contimuously -ifiruuuuttddfffeetttabbl gs. and at most m2 2
equality constraints (h,(y) = 0) with linear functions h4-
We note here that the expressiveness inner domain constraints y is only required for the analysis, and not required in our algorithms as long as there exist efficient projection operators. While there could be many possible representations of constraints, only the most compact representation would matter in our analysis. We denote by 1Ix and Hly the projection operators onto sets X' and Y, respectively. Nxx (x) denotes the normal cone of X at point X.
Next, we define the distance measure between sets:
Definition (Hausdorff Distance) Let S1 and S2 be two sets in Rdd, The Hausdorff distance between
Si and S2 is given
dist max
sup inf ||0 02l1. sup inf |00 - 021 00,
0g
6,ES, P1ES
For distance between a point O and S, denote dist(0,S) dist dis)(
4

---

Under review as a conference paper at ICLR 2024
Throughout the paper, Definition measure of distances between sets. We define the notion of (local) Lipschitz continuity of solution sets introduced in Chen et al. (2023b).
Definition (Lipschitz Continuity of Solution Sets Chen et (2023b)) For a differentiable and smooth function f(w, 0) on W x θ, say the solution set S(w) == arg mingge f(w, 0) is locally Lipschitz continuous at w E W if there exists an open-ball of radius
and constant Lg < oo such that for any w' E B(w, 5), we have dist(S(w), S((")) I Ls|[w - w'll-
Constrained Optimization We introduce some standard notions of regularities from nonlinear
constrained optimization Bertsekas (1997). For a general constrained optimization problem Q mingge f()), suppose θ can be compactly expressed with m. inequality constraints {g. < O with convex and twice continuously differentiable gis and m2 2 0 equality constraints (h:(0) = 0)e[mal with linear functions ht.
Definition 4 (Active Constraints) We denote I(0) C [ma] the index of active inequality constraints of 0 E O, Le., I(0)= = (i E [m1]= (.) 03.
Definition 5 (Linear Independence Constraint Qualification (LICQ)) We say Q regular feasible point E @ if the set of vectors consisting of all equality constraint gradients (h;( Vi [m²]] and the active inequality constraint gradients (O), Vi E I()) is a linearly independent set.
solution 0* of Q satisfies the so-called KKT conditions when LICQ holds at 0*: the KKT conditions that there exist unique Lagrangian multipliers X 0 for i I(0") and Vz R for i E [mz] such that
0 O and VS(00) + EiEz(or) A (o(" + Eie(my) v (0, 0.
(5)
For such a solution, define the strict complementary slackness condition:
Definition 6 (Strict Complementarity) Let 0" be solution of Q satisfying LICQ and the KKT condition above, We say that the strict complementary condition is satisfied at 0* if there exist multipliers X3, v² that satisfy (5), and further X >> 0 for all i E I(O").
Other Notation We say Og x by if ag and by decreases (or increases) in the same rate as k -> oc, i.e., limg-+oe ak/by- = ((1. Throughout the paper, || denotes the Euclidean norm for vectors, and operator norm for matrices. [n]] with natural number E N denotes set (1, 21,2.... n]. Let (0) be the projection of point onto a convex set S. We denote Ker(M) and Im(M) to mean the kernel (nullspace) and the image (range) of a matrix M respectively. For symmetric matrix M, we define the pscudo-inverse of M as M == UU MU)- where the columns of U consist of eigenvectors corresponding to all non-zero eigenvalues of M.
3 LANDSCAPE ANALYSIS AND PENALTY METHOD
In this section, we establish the relationship between the landscapes of the penalty formulation (P pen) and the original problem (P). Recalling the definition of the perturbed lower-level problem (x, : fI, y) + g(x, y) from Assumption 1, we introduce the following notation for its solution set: For [0, dul with sufficiently small og > O, we define
1(x, σ) := min ho (x. (I. T(x, σ) = arg min (,. yE)
(6)
yEy
We call [(2, o)) the value function, and T(x, or) the corresponding solution set. Then, the minimization problem (P pen) over the penalty function and v defined in (2) can be rewritten as
min th (x: where (x) 1xx, σ) ((x,0) SE
o
We can view v%a (x) sensitivity measure of how the optimal value mingey g(r,, y) changes when we impose a perturbation of a fxx y) in the objective. In fact, it can be easily shown that
lim vo (x) = do (x, o)lo=o =x))
0
5

---

Under review as conference paper at ICLR 2024
(xx)
4 (2)
(x)
Figure 1: (x)) and the (x) in Examples: (left) Example 1, (right) Example 2. Blue dashed lines compare the (2) the original hyper-objectiive ((x).
However, this formula provides only pointwise asymptotic equivalence of two functions and does not imply the equivalence of the gradients Vah (x) and (eb(z) of the two hyper-objectives. In the limit setting, check whether
82
8² Ordr 1(x, o) l==
Ve(()) = dodo
lim a=
Valee (2)).
(7)
Unfortunately, it is not always true that the above relation (7) holds, and the gradient of Vvl(z) may not even well-defined, as illustrated in Examples and 2 in the following section.
In what follows, derive two assumptions: one concerning solution-set continuity (Assumption 5) and another addressing the regularities of lower-level constraints (Assumption 6). Under these assumptions, establish the main theorem of this section, Theorem 3.1. This, in turn, leads to the derivation the second inequality in our landscape analysis result, as presented in Theorem 1.1 and shown in Theorem 3.7.
3.1 SUFFICIENT CONDITIONS FOR DIFFERENTIABILITY
The following two examples illustrate the obstacles encountered when claiming lim, (i) V (z)(z) or even when simply ensuring the existence of Vzb(z))
Example 1 Consider the bilevel problem with X = y 11,
f(x, 11,,1,,
+ and g(x.1)
ry. Note that lim do (x) + x² + for all x E [-1, {0}. where we have limg the (0) See Figure 1. Therefore (x)) is a pointwise convergent point of th (x). However, neither ((x nor vo (x) is differentiable at x 0.
This example also implies that the order of (partial) differentiation may not be swapped in general. Even when the lever-level objective g( y) is strongly convex in y, the inclusion of a constraint set D, even when compact, lead to nondifferentiable vh, see next.
Example 2 Consider an example with X [-2, - f(x, v) = and g( y) (y x²² In this example, (xx)= = if < -1, (bxx) -I 1-1,, 1]. and vb(x)) = -1 otherwise.
Thus (xx) is not differentiable at x -1 and while Ve. 0 and (- = - for all > 0.
There are two reasons for the poor behavior of (v(z). First, Example the solution moves discontinuously at x = O. When the solution abruptly changes due to small perturbation in x, the problem highly ill-conditioned - fundamental difficulty Daskalakis al. (2021). Second, in Example 2, even though the solution set is continuous thanks to the strong convexity, the solution can move nonsmoothly when the set active constraints for the lower-level problem changes. The result is frequently nonsmoothness of (xr), (+)( may not be defined at such In summary, we need regularity conditions to ensure that these two cases do not happen.
We first consider assumptions that obviate solution-set discontinuity so situations like those appearing in Example will not occur.
Assumption 5 The solution set T(x, σ) := arg min h (x, y) is locally Lipschitz continuous, i.e., T(x, a) satisfies Definition 3 at (z,

---

Under review as a conference paper at ICLR 2024
We note here that the differentiability of the value function (x,, o)) requires Lipschitz continuity of solution sets (not just continuity). When the solution set is locally Lipschitz continuous, it is known (see Lemma D.2) that the value function (xx or) is (locally) differentiable and smooth.
As we have seen in Example 2, however, the Lipschitz-continitty of the solution set alone may not be sufficient in the constrained setting. We need additional regularity assumptions for constrained lower- level problems. Recalling the algebraic definition of y in Assumption 4, we define the Lagrangian of the constrained (o-perturbed) lower-level optimization problem:
Definition 7 Given the lower-level feasibble set satisfying Assumption let { C R. and {
m m2 C. R be some Lagrangian multipliers. The L function (1-,,, 0) R4 x Im x
Rd + R at (x,, σ) is defined by
[(,, y,, o) o f g( + Eielmul >sg:(y) + Eielmal vch((y).
We also define the Lagrangian L2 0) R Izl [m,]:
x R x Rdd - R restricted to set of constraints
CI = of g(( + EiEZ )ggi(v) + Elemma)
(8)
When the context is clear, always let I in (8) be I(y) at given y. The required assumption is the existence of a regular and stable solution that satisfies the following:
Assumption The solution set T(x, o) contains at least one y E T(xx, 0) such that LJCQ (Definition 5) and strict complementary condition (Defimition 6) hold at y², and V L o) (the matrix of second derivatives with respect to all variables XI, v, y) is continuous at (N "r, y)).
Assumption 6 helps ensure that the active set I(y") given in Definition does not change when it or is perturhed slightly.
3.2 ASYMPTOTIC LANDSCAPE
We show that Assumptions 5 and 6 are nearly minimal to ensure the twice-differentiabbliy of the value function ((x, o) which, in turn, guarantees asymptotic equivalence Velo (x)) and Vι(()). In the sequel, we state our main (local) landscape analysis result only under the two assumptions at given point (xr, o), which is given the following theorem:
Theorem 3.1 Suppose T( satisfies Assumption 5 in a neighborhood of (a, a). If there exists at 8²
Uxx least one y E T(I,0) o) that satisfies Assumption 6, then Baöd 10, .)) exists and can be given explicitly by
82
82
dodr 1(x,
0x00 (1.,
(9)
(e (V' oz))
[
(or((r
0
If this equality holds at a = 0t, then vax) is differentiable at x, and lim ( = Vi((t))
Theorem 3.1 generalizes the expression of (z) from the case unique solution the one with multiple solutions, significantly enlarging the scope of tractable instances of BO. Up to our best knowledge, there are no previous results that provide an explicit formula of Vw(z), even when the solution set is Lipschitz continuous, though conjectures have been made in the literature Xiao et al. (2023a); Arbel Mairal (2022) under similar conditions.
Remark 3.2 (Set Lipschitz Continuity) While we require the entire solution set T(x, a)) to be Lips- chitz continuous, the proof indicates that we need only Lipschitz continuity of solution paths passing through y" (that defines the first-order derivative lxx σ) and satisfies other regularity conditions) in all possible perturbation directions of (z. σ). Nonetheless, stick to a stronger requirement of Definition 3, since our algorithm requires a stronger condition that implies the continuity of entire solution sets.
7

---

Under review as a conference paper at ICLR 2024
Remark 3.3 (Lipschitz Continuity in σ) While we require T(x, .)) be Lipschitz continuous in both x and G, well definedness of V((x) requires only Lipschitz continuity of ox. )*) in x (which sometimes can be implied by the PL condition only g as in Chen et al. (2023b); Shen & Chen (2023); Xiao et al. (2023a)). Still, for implementing a stable and efficiens algorithm with stochastic oracles, we conjecture that it is essential to have the Lipschitz continuity assumption the additional axis a.
We conclude our asymptotic landscape analysis with a high-level discussion on Theorem 3.1. The key step in our proof is to prove the following proposition:
Proposition 3.4 (Necessary Condition for Lipschitz Continuity) Suppose T(x,o) satisfies As- sumption 5 at (z, o). For any y E TT, o) that satisfies Assumption 6, the following must hold:
[ I vz,))).
Ye E span span(Im( 2 yirh ho (z, y )), vyf(z.y"))
(10)
Formally, perturbations in (2r, must not tilt the flat directions of the lower-level landscape for T(x, or) to be continuous. While it is easy to make up examples that do not meet the condition (e.g. Example I), several recent results show that the solution landscape may be stabilized for complicated functions such as werrparametterize neural networks Frei & Gu (2021); Song al. (2021); Liu et al. (2022). In Appendix E.5, we prove a more general version of Theorem 3.1 (see Theorem E.4), of possible broader interest, concerning the Hessian of ((z,0).
Remark 3.5 With a more standard assumption on the uniqueness of the lower-level solution and the invertibility of the Lagrangian Hessian, we can provide a sufficiency guarantee for the Lipschitz continuity of solution sets stronger than Theorem 3.1. We refer the readers to Appendix E.I.
3-3 LANDSCAPE APPROXIMATION WITH
(xx, o)) lo=o+ via finite differentiation with respect to a. Assuming that 8² [[x o) exists and is continuous for all small values a, we can deōz
We can view (x) as an approximation of 0 B Bo 8e
apply the mean-value theorem and conclude that (v) Thus, V/ (x) Vv(())] is O(r) whenever
0e0z (xx o') for some o' E [0, a). 8² 1 σ) is well-defined and uniformly Lipschitz Uzön 1xx
8²
continuous over [0, o).
To work with nonzero constant > need the regularity assumptions to hold in significantly larger regions. The crux Assumption is the guaranteed Lipschitz continuity solution sets (see also Assumption 5) for every given x and a, which is also crucial for the tractability of lower-level solutions by local search algorithms whenever upper-level variable changes:
Lemma 3.6 Under Assumption 1, T(x, σ) is (l../p) -ipsshittt continuous in and (L/,0/M)- Lipschitz continuous in a for all E X.O E [0,8/Cy].
An additional consequence of Lemma 6 is that, by Lemma D.2, 1(x, σ) is continuously differentiable and smooth for all I E X and a E [0, 8/,)] This fact guarantees in turn that (x) is differentiable and smooth (though (xx) does not necessarily have these properties).
While Assumption is sufficient to ensure vo (z) is well-behaved, we need additional regularity Therefore when we connect (xx) and th (z), we
conditions ensure that v'(x) also non-as asymptotiii versions of Assumption 5 and 6. The first make two more local assumptions that are non concerns Hessian- Lisiiann.ipsshhztness and regularity of solutions.
For a given x, there exists at least one y E T(x, 0) such that if we follow the solution path y" (a) along the interval a E 00).
Assumption
(1) all y (a) satisfies Assumption with active constraint indices I and Lagrangian multipliers \² (a) of size O(1) and
(2) V S. V2g. 1 are -pssciitt continuous at all (ar, y (a))-
8

---

Under review as conference paper at ICLR 2024
In the unconstrained settings with Hessian-Lipschitz objectivve, Assumption 7 is implied by Assump- tion for all x E 2 E 6/.l
The second assumption is on the minimum nonzero singular value of active constraint gradients.
Assumption 8 For a given x, there exists at least one y E T(x, 0) such that if we follow the solution path (o) along the interval E [0, oo). all solutions y (a) satisfy Definition 5 with minimum singular value Smin > 0. That is. for all E [0, Jol. we have
min 0:
[VV (o)), e (o)), [me]] al1 2 8min-
Note that Smin in the constrained setting depends purely the LICQ condition, Definition 5.
Theorem 3.7 Under Assumptions 1 we have
(x) - +xx) S O (1)
A z0y). If. in addition, Assumptions 7 and 8 hold at given I, then for all x E X and a E [0,
1 $1.00.0
22,12
VV (2) - Vbb())) $
1 min
0.
min
The proof of Theorem 3.7 is given Appendix E.6.
Remark 3.8 (Change in Active Sets) slightly unsatisfactory conclusion of Theorem 3.7 is that when Vxp(x) is not well- well-defined due to the nonsmooth movement of the solution set as Example does not relate Vi (x)) any alternative measure for Vab(1)). Around the point where v/(x) is non-smooth, some concurrent work atlempts to fond a so-called (e, 8) -)oGoddtt stationary point Chen approximation gradients via localized smoothing (but only in the upper-level variables x). While this is an interesting direction, we do not pursue it here. Instead, we conclude this section by stating that an e-stationary solution of too (x) is an O σ -KKK point of (P ( (this claim is fairly straightforwan to check, see for example, Theorem E.5 in Appendix E.7).
al. (2023b), which can be
3-4 FINDING STATIONARY POINT OF th (I:)
Theorem 3.7 explains the conditions and mechanisms under which the penalty methods can yield an approximate solution of the original Bilevel optimization problem (P), providing a rationale for pursuing a weaker criterion of || ( S c with a = O()). In Appendix B, we present algorithms that rely solely access to first-order (stochastic) gradient oracles and find stationary point of the penalty function vo (z) with o Oe). Then we conclude the paper by providing formal versions of Theorem 1.2 in Appendix C.
CONCLUSION
This paper studies a first-order algorithm for solving Bilevel Optimization when the lower-level problem and perturbed versions of it satisfy proximal error bound condition when the errors small. We establish an -(o)-clsss relationship between the penalty formulation th (xr) and the hyper-objective (><))) under the proximal-error bound condition, and then develop a fully first-order stochastic approximation scheme for finding stationary point of tho (z), and study its non non-asymptotic performance guarantees. We believe our algorithm to be simple and general, and useful in many large-scale scenarios that involve nested optimization problems. In Appendix A.2, we discuss several issues not addressed this paper, that may become the subjects of fruitful future research.
ACKNOWLEDGMENTS
This project was partially supported by AFOSR/AFRL grant FA9550-18-1-44 supported by the National Research Foundation Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2023-0025255 10) and the POSCO Science Fellowship of POSCO TJ Park Foundation. SW was supported in part by NSF Awards DMS-2023222 2023239 and CCF-2224213 and AFOSR Award FA9550-21-1-008.
DK was partially

---

Under review as conference paper at ICLR 2024
REFERENCES
G Anandalingam and DJ White. A solution method for the linear static stackelberg problem using penalty functions. IEEE Transactions on automatic control, 35(10):1100-117, 1990.
Michael Arbel and Julien Mairal. Non-convex bilevel games with critical point selection maps. In Advances in Neural Information Processing Systems, 2022.
Fan Bao, Guoqiang Wu, Chongxuan Li, Jun Zhu, and Bo Zhang. Stability and generalization of bilevel programming in hyperparameter optimization. Advances in Neural Information Processing Systems, 34:4529 4541, 2021.
D. P. Bertsekas. Nonlinear Programming. Athena Scientific, second edition, 1999.
Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3):
334-334, 1997.
J Frédéric Bonnans and Alexander Shapiro. Perturbation analysis of optimization problems. Springer Science & Business Media, 2013.
Morteza Boroun, Zeinab Alizadeh, and Afrooz Jalilzadeh. Accelerated primal-dual scheme for a class of stochastic nonconvex-concave saddle point problems. arXiv preprint arXiv:2303.002 2023.
Jerome Bracken and James T McGill. Mathematical programs with optimization problems in the constraints. Operations Research, 21(11:37-44 1973.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357,22 2015.
Lesi Chen, Yaohua Ma, and Jingzhao Zhang. Near-optimal fully first-order algorithms for finding stationary points in bilevel optimization. arXiv preprint arXiv:2306.1488 14855,,, 2023a.
Lesi Chen, Jing Xu, and Jingzhao Zhang. On bilevel optimization without lower-level strong convexity. arXiv preprint arXiv:2301 007100072220000 2023b.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 34: 25294-251 25307, 2021.
Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A single-timescale method for stochastic bilevel optimization. International Conference on Artificial Intelligence and Statistics, pp. 2466-2488. PMLR, 2022.
Benoît Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Annals of operations research, 153(1):235-22) 256, 2007.
Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. arXiv preprint arXiv:2201.134099 2022.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pp. 1466-1478, 2021.
Stephan Dempe. Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. 2003.
Stephan Dempe, Vyacheslav Kalashnikov, Gerardo A Pérez-Valdés, and Nataliya Kalashnykova. Bilevel programming problems. Energy Systems. Springer, Berlin, 10:978-3, 2015.
Lawrence C Evans. Partial differential equations, volume 19. American Mathematical Society, 2022.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riceardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Machine Learning, pp. 1568-1577 PMLR, 2018.
10

---

Under review as a conference paper at ICLR 2024
Spencer Frei and Quanquan Gu. Proxy convexity: A unified framework for the analysis of neural networks trained by gradient descent. Advances in Neural Information Processing Systems, 34: 7937-7949, 2021.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint wrXi::882.002240 2.18.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial networks. In International Conference on Learning Representations, 2018.
Tommaso Giovannelli, Griffin Kent, and Luis Nunes Vicente. Bilevel stochastic methods for optimiza- tion and machine learning: Bilevel stochastic descent and darts. arXiv preprint arXiv:2110000044 2021.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(11):139-14) 144, 2020.
Riccardo Grazzi, Massimiliano Pontil, and Saverio Salzo. Bilevel optimization with lower-level contraction: Optimal sample complexity without warm-start. Journal of Machine Learning Reseurch, 24(167):1-37, 2023.
Zhishuai Guo, Quanqi Hu, Lijun Zhang, and Tianbao Yang. Randomized stochastic variance-reduced methods for multi-task stochastic bilevel optimization. arXiv preprint arXiv:2105.02266, 2021.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang. and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147-188) 2023.
Feihu Huang, On momentum-based gradient methods for bilevel optimization with nonconvex lower-level. arXiv preprint wrXiv:2303.0394. 2023.
Yo Ishizuka and Eitaro Aiyoshi. Double penalty method for bilevel optimization problems. Annals of Operations Research, 34(1):73-88, 1992.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced
design. In International Conference Machine Learning, pp. 4882 4892. PMLR, 2021.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality nonconvex-nonconee minimax optimization? In International conference machine learning, pp. 4880-4889, PMLR. 2020.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and troximal-gradiee methods under the polyak-tojasiewiez condition. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part 16, pp. 795-811. Springer, 2016.
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang, A near-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in Neural Information Processing Systems, 34:30271 -07773, 2021.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
Weiwei Kong and Renato DC Monteiro. An accelerated inexact proximal point method for solving nonconvex-concav min-max problems. SIAM Journal on Optimization, 31(4):2558-25 -2585, 2021.
Dmitry Kovalev and Alexander Gasnikov. The first optimal algorithm for smooth and strongly-convex- strongly-coneave minimax optimization. arXiv preprint arXiv:2205.05653, 2022.
Gautam Kunapuli, Kristin P Bennett, Jing Hu, and Jong-Shi Pang. Bilevel model selection for support vector machines. Data mining and mathematical programming, 45:129-158. 2008
11

---

Under review as a conference paper at ICLR 2024
Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning, pp. 18083- 18113. PMLR, 2023.
Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadbabaie. Complexity lower bounds for nonconvex- strongly-concave min-max optimization. Advances in Neural Information Processing Systems, 34: 1792-1804, 2021.
Jiajin Li, Linglingzhi Zhu, and Anthony Man-Cho So. Nonsmooth composite nonconvex-concave minimax optimization. arXiv preprint arXiv:2209. 10825, 2022a.
Junyi Li, Bin Gu, and Heng Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp.
1426-7434, 2022b.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59: 85-116, 2022.
Risheng Liu, Yaohua Liu, Wei Yao, Shangzhi Zeng, and Jin Zhang. Averaged method of multipliers for bi-level optimization without lower-level strong convexity, arXiv preprint arXiv:2302.03400 2023.
Zhaosong Lu and Sanyou Mei. First-order penalty methods for bilevel optimization. arXiv preprint arXiv:2301.01716, 2023.
Patrice Marcotte and Dao Li Zhu. Exact and inexact penalty methods for the generalized bilevel programming problem. Mathematical Programming. 74:141-1577 1996.
Paul Milgrom and lya Segal. Envelope theorems for arbitrary choice sets. Econometrica, 70(2): 583-601, 2002.
Jaan-Jacques Moreau. Proximité et dualité dans un espace hilbertien. Bulletin de Société mathéma- fique de France, 93:273-299, 1965.
Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first-order nash equilibria in nonconvex-concav. smooth min-max problems. SIAM Journal on Optimization, 31 (4):2508-2538, 2021.
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International confer- ence on machine learming, 737-746. PMLR, 2016.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. Advances in neural information processing systems, 32, 2019.
Han Shen and Tianyi Chen. On penalty- bilevel gradient descent method. arXiv preprint arXiv:2302.051 2023.
Ankur Sinha, Pekka Malo, and Kalyanmoy Deb. A review on bilevel optimization: From classical to evolutionary approaches and applications. IEEE Transactions on Evolutionary Computation, 22 (2):276-295, 2017.
Chachwan Song, Ali HemmzzaniKeebrye Thomas Pethick, Armin Eftekhari, and Volkan Cevher. Subquadratic overparameteriization for shallow neural networks. Advances in Neural Information Processing Systems, 34:1 1217-11277119 2021.
Daouda Sow, Kaiyi Ji, Ziwei Guan, and Yingbin Liang. A constrained optimization approach to bilevel optimization with multiple inner minima. arXiv preprint 12 2022.
Heinrich von Stackelberg et al. Theory of the market economy. 1952.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Kiran K Thekumparampil, Prateck Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. Advances in Neural Information Processing Systems, 32, 2019.
12

---

Under review as conference paper at ICLR 2024
Luis Vicente, Gilles Savard, and Joaquim Júdice. Descent approaches for quadratic bilevel program- ming. Journal of Optimization theory and applications, 81(2):379-393 1994.
Douglas J White and G Anandalingam. A penalty function approach for solving bi-level linear programs. Journal of Global Optimization, 3:397-419, 1993.
Quan Xiao, Songtao Lu, and Tianyi Chen. generalized alternating method for bilevel optimization under the Dolyak-Lojasiewicd condition. arXiv preprint arXiv:2306.0242) 2023a.
Quan Xiao, Han Shen, Wotao Yin, and Tianyi Chen. Alternating projected sgd for equality constriidd bilevel optimization. In International Conference on Artificial Intelligence and Statistics, pp. 987-
1023. PMLR, 2023b.
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance-reduuced optimization for a class of nonconvex nonconcave minimax problems. arXiv preprint arXiv:2002.09621, 2020.
Junchi Yang, Antonio Orvieto, Aurelien Lucchi, and Niao He. Faster single-loop algorithms for mini- max optimization without strong concavity. In International Conference on Artificial Intelligence and Statistics, pp. 5485-5517. PMLR, 2022.
Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34:13670-1366 13682, 2021.
JJ Ye, DL Zhu, and Qiji Jim Zhu. Exact penalization and necessary optimality conditions for generalized bilevel programming problems. SIAM Journal on optimization, 7(2):481-507, 1997.
Mao Ye, Bo Liu, Peter Stone, Stephen Wright, and Qiang Liu, Bome! bilevel optimization made easy:
A simple first-order approach. In Advances in Neural Information Processing Systems, 2022.
Jiawei Zhang. Peijun Xiao, Ruoyu Sun, and Zhiquan Luo. single-loop smoothed gradient descent- ascent algorithm for nonconvex-concar min-max problems. Advances in neural information processing systems, 33:7377-7389, 2020.
13

---

Under review as a conference paper at ICLR 2024
APPENDIX A DEFERRED DISCUSSIONS
A.1
RELATED WORK
Since its introduction in Bracken & McGill (1973), Bilevel optimization has been an important research topic in many scientific disciplines. Classical results tend to focus on the asymptotic properties of algorithms once in neighborhoods of global/local minimizers (see e.g. White & Anandalingam (1993); Vicente et al. (1994); Colson al. (2007)). In contrast, recent results are more focused on studying numerical optimization methods and non-asymptotic analysis to obtain an approximate stationary solution of Bilevel problems (see e.g., Ghadimi & Wang (2018); Chen et al. (2021)). Our work falls into this category. Due to the vast volume of literature on Bilevel optimization, we only discuss some relevant lines of work.
Implicit-Gradient Descent As mentioned earlier, initiated by Ghadimi & Wang (2018), flurry of recent works (see e.g., Chen et al. (2021): Hong et al. (2023); Khanduri et al. (2021); Chen et al. (2022); Dagréou al. (2022); Guo al. (2021)) study
-aaD)-based iterative procedures and their finite-time performance for solving (P) when the lower-level problem is strongly-convex and unconstrained. In such cases, the implicit gradient of hyper-objective (xx) is given by
( V vaf(z,(())) - 2 ",, (x)) (V (x))) (x,
where y" (xx) arg wek's (xx, w). Two main challenges in performing (implicit) gradient descent are (a) to evaluate lower-level solution y" (zz), and (b) to estimate Hessian inverse (V y (z))) For (a), is now well-understood that instead of exactly solving for y (zx) for every 4t iteration, we can incrementally solve for y (xxx, e.gg. run few more gradient steps on the current estimate yk. and use as a proxy for the lower-level solution Chen et al. (2021). As long as the contraction toward the true solution (with the strong convexity of g( -)) is large enough to compensate for the change of lower-level solution (due to the movement in or ) yk: will eventually stably stay around y (arz), and can be used as a proxy for the lower-level solution to compute the implicit gradient. Then for (b), with the Hessian of g being invertible for all given y. we can exploit the Neumann series approximation Ghadimi & Wang (2018) to estimate the true Hessian inverse using yk as proxy for y (Ix).
Unfortunately, the above results are not easily extendable to nonconvex lower-level objectives with potential constraints V. One obstacle is, again, to estimate the Hessian-inverse: now that for some Y E V. the Hessian of g may not be invertible even if V 9x,, (I. y (x)) is invertible at the exact solution. Therefore, in order to use an approximate y/ as a proxy to y" (xxg). we need a certain high- high-probbbbiltyy guarantee (or some other complicated arguments) to ensure that the algorithm remains stable with the inversion operation. The other obstacle, which is more complicated to resolve, is that the implicit gradient formula may longer be the same if the solution is found at the boundary of V In such case, explicitly estimating V Vx((x) would not only require an approximate solution but also require the optimal dual variables for the lower-level solutions which are unknown (see Theorem 3.1 for the exact formula), However, computing the optimal solution as well as the optimal dual variables is even more challenging when we only access objective functions through stochastic oracles. Therefore, is essential to develop first-order method that does not rely on the explicit estimation of the implicit gradient to solve a broader class of BO, aside from the cost of using second-order derivatives in large-scale applications.
Nonconvex Lower-Level Objectives In general, BO with nonconvex lower-level objectives is not computationally tractable without further assumptions, even for the special case of min-max optimization Daskalakis et al. (2021). Therefore. additional assumptions on the lower-level problem are necessary. Arguably, the minimal assumption would be the continuity of lower-level solution sets, otherwise, any local-search algorithms are likely to fail due to the hardness of (approximately) tracking the lower-level problem. The work in Chen et al. (2023b) considers several growth conditions for the lower-level objectives (including PL), which guarantee Lipschitz continuity of lower-level solution sets, and proposes a zeroth-orde method for solving (P). The work in Shen & Chen (2023) assumes the PL condition, and studies the complexity of the penalty method in deterministic settings. The work in Arbel & Mairal (2022) introduces a notion of parameteric Morse-Boo functions, and studies some asymptotic properties of their proposed gradient flow under the proposed condition. In
14

---

Under review as a conference paper at ICLR 2024
all these works well as in work, underlying assumptions involve some growth conditions of the lower-level problem, which is essential for the continuity of lower-level solution sets.
Penalty Methods Studies on penalty methods date back to 90s Marcotte & Zhu (1996); White & Anandalingam (1993); Anandalingam & White (1990); Ye al. (1997); Ishizuka & Aiyoshi (1992), when the equivalence is established between two formulations (P) and (Peen) ) for sufficiently small O. However, these results are often limited relations within infinitesimally small neighborhoods of global/local minimizers. As we aim to obtain a stationary solution from arbitrary initial points, we need a comprehensive understanding of approximating the global landscape. rather than only around infinitesimally small neighborhoods of global/local minimizers.
The most closely related work to ours is recent work in Shen Chen (2023), where the authors study the penalty method under lower-level PL-like conditions with constraints Y' as in ours. However, the connection established in Shen & Chen (2023) only relates (P peenn) and e-relaxed version of (Paon), and only concerns infinitesimally small neighborhoods of global/local minimizers as in older works. Furthermore, their analysis is restricted to the double-loop implementation of algorithms in deterministic settings. In contrast, we establish direct connection between (zb(z) and V (x) when they are well-defined, and our analysis can be applied to both double-loop and single-loop algorithms with explicit oracle-complexity bounds in stochastic settings.
Implicit Differentiation Methods Another popular approach to side-step the computation of implicit gradients is to construct a chain of lower-level variables via gradient descents, a technique often called automatic implicit differentiation (AID), iterative differentiation (ITD) Pedregosa (2016); Yang et al. (2021); 1); Li et al. (2022b); Ji et al. (2021); Grazzi et al. (2023). The benefit of this technique is that now we do not require the estimation of Hessian-inverse. In fact, this construction can be seen as one constructive way of approximating the Rressian-inverss However, when the lower-level problem constrained by compact y, more complicated operations such as the projection may prevent the use of the implicit differentiation technique.
A.2 FUTURE DIRECTIONS
Tightness of Results. Can our complexity result can be improved in terms of its dependence on while using only first-order oracles? Recent work in Chen et al. (2023a) shows that when the lower-level problem is unconstrained and strongly convex, oracle complexity can be improved to O(c-2) with deterministic first-order gradient oracles. Can similar improvements be found in the complexity when stochastic oracles and constraints are present in the formulation?
Lower Level z-Dependent Constraints. When the lower-level constraints depend on x, also possible to derive an implicit gradient formula when the lower level problem is non-degenerate. For instance, Xiao et al. (2023b) has studied the case in which the lower-level objective is strongly convex and there are lower-level linear equality constraints that depend on In general, with z-dependent constraints, we cannot avoid estimating Lagrangian multipliers, as they are needed in the implicit gradient formula. Even to find the stationary point of penalty functions, V1ha (2:) requires Lagrangian multipliers (see the Envelope Theorem Milgrom & Segal (2002)). An interesting future direction would be to develop an efficient first-order algorithm for this case.
General Convex Lower-Level. One interesting special case is when g(x,,) -) is merely convex, not necessarily strongly convex. There have been recent advances in min- max optimization for nonconvex- concave problems: see for example Boroun et (2023); Thekumparampil Gasnikov (2022); Kong & Monteiro (2021); Ostrovskii et al. (2021); Zhang et al. (2020). We note that when g(x,) -) is convex, an e-stationary point of (P saatde is also an KKK solution of (Poon). The first paper to investigate this direction in deterministic settings is Lu & Mei (2023), to our knowledge. An important future direction would to extend their results to stochastic settings.
al. (2019); Kovalev &
Nonsmooth Objectives. We could also consider nonsmooth objectives in both levels where efficient proximal operators are available for handling the nonsmoothness. It would also be interesting in future work to see whether the analysis in this paper needs to be changed significantly in order to handle nonsmooth objectives.
15

---

Under review as conference paper at ICLR 2024
APPENDIX B ALGORITHM
We have the following assumptions on the first-order (stochastic) oracles and efficient projection operators required to develop our algorithms.
Assumption 9 The projection operations II, Hl onto sets X, respectively, can be implemented efficiently.
Assumption 10 We access first-order information about the objective functions via unbiased esti-
mators (z, y; (). Vg(a, y: E), where [(, yi y){) =V] (x. y) and ( y: v) = Vg(r, y).
The variances stochastic gradient estimators are bounded as follows:
BIIVS( Vs(x, v) v) BlIVg(e, - Vg(a, - ozg
for some universal constants o. o
Throughout the rest of the paper, assume that Assumption I holds.
B.1 STATIONARITY MEASURES
Since we showed in the previous section that V (z) is an -ppooopproinnnaiionn of Vel(z) in most desirable circumstances, now we consider finding a stationary point (x","", """,,,"""" =²) of Vel (x). Under Assumption 1, we can show that this is equivalent to finding the stationary point of (P (Paaddle) defined as the following:
(v"), y prox (at. (v"),
prox po(=",)) proxpo(x>>.0 po(=>.)) .)(("); (Vzho .y") Vag(a", 22)) E (x
(11)
where (x* is the normal cone of X' at x² We define a notion approximate stationary points as follows.
Definition 8 We say (x, 22 is an e-stationary point of (Psaddle) if it satisfies the following:
1 y prox ( (w)) S oe, - prox po(x)) (=)] S ae,
1 || IIx fo ppppp(Pp ((Vzho Veg(a, 2)}l| s oe.
p
The lemma below relates the e-stationarity of (P saaddele to the landscape of (v)
Lemma B.1 Let (x" .y" ,²"²"" be an e-stationary point of (Psaddie).
1. For all x E X. (z) is well-defined, and x" a (1 + (11) point of (z
2. Supposing in addition that Assumptions 7 and 8 hold at x", then x² is (1+1ga//))+tLo))
stationary point of (xx),, where L. O (1² 11 10/l1////////////0///// (1²23) s).)).
The first part of the lemma is a consequence of Lemma 3.6, while the second part from Theorem 3.7. Henceforth, aim to find saddle point of formulation (P (Padiil))
B.2 FIRST-ORDER METHOD WITH LARGE BATCHES
We first consider solving a stochastic saddle- Moidee problem by applying (projected) stochastic gradient descent-ascent, alternating between upper-level and lower-level variables, with multiple iterations for the lower-level variables (y, 2) per single iteration in the upper-level variables (x). There are two technical challenges that aim to tackle specifically for the form (P saddle) with Assumption 1.
16

---

Solvers Under review as a conference paper at ICLR 2024
Algorithm Double-Loop Algorithm with Large Batches
Input: total outer-loop iterations: K, step sizes: {ar, Th proximal-smoothing parameters: (3x
3x E (0, 1]). inner-loop iteration counts: {Tk J. outer-loop batch size: {, penalty parameters:
{ proximal parameter: p. initializations: 2ig E X, Yus 20 y
1: Initialize yyy0 = Yo. Wa,0 =
2: for k O...K 1 do
3: # Inner-Loop Froximal-Operiane
4: Uo < k: 0g w..k
5: for ..... Tk do
6:
thit + guy + p (u= - yn))} ut+1 + Ily {2: 7n (o wy
7:
U+41 6 Tly (t Nn (g + p (1; 2x))}
8:
end for
9:
Wy.++1 f- Wr, w, f
# Proximal-Smoothing on Lever-Level Variables
11:
Uk+1 + (1- - 8& 3x) + 9.
12:
Ek+1 + (1 )x + 3RW2ZA+1
13:
# #(Projected) Gradient Descent Upper-Level Variables
14:
#k+1 + 1Ix Th
(on
+ g k.m
Mr
end for
1. Technically speaking, the main difference from many previous works (e.g., Hong et al. (2023); Chen et al. (2021; 2022)) is that now we no longer have global contraction property of inner iterations toward solution sets. To be more specific, when the lower-level objective the PL-condition for all y E RRd, the distance between the current (lower-level) iterates and solution-sets contracts globally after applying inner gradient steps, i.e., if updating Zk+1 + =k- 8g V (2 =x) at the htth iteration before updating Tk. get
E E[dist(z (Z+41, FR) S - (1-Ax) dist (k, T(*,, 0)),
for some As E (0, 1]. However, we assume that the error-bound condition only holds at points with O(8) proximal error. That is, unless y and remain close to the solution set (with high probability if gradient oracles are stochastic), we cannot guarantee that dist T( 0)) is improved (in expectation) as the nnter-iteration & proceeds.
2. Eventually, we want (e)) since (x(x)) is ideally ((a)) ((r))apprxxinna >approximaaioo of (x) up to
first-order. However, to set = O(e) from the first iteration overly conservative, resulting in overall slowdown of convergence. We decrease the penalty parameters {ax) gradually, to improve the overall convergence rates and the gradient oracle complexity.
To address issue 1, we propose a smoothed surrogate of the (I, y, via proximal envelope (often referred to as Moreau Envelope Moreau (1965)) with sufficiently small < 1/1g.1:
1 h y, w) = (2, w) + ||w - y|1
h: (x, v) min wE)
2p
1
(x,
min wEY
g(z, y, w) g( w) + 1/0 =||²
(12)
2p
and consider the following alternative saddle-point problem with proximal envelopes:
max (I, 2) == ha v) (x, 2) =EY
min xEXWEY
(13)
This formulation convenient because the minimiiiniiiiio problem strongly convex, so we always have unique and well-defined lower-level optimizer to chase.
Note that Vh (I. v) Vho (Ir, w where w prox pho (x.)) (v), and similarly, VgJ 2) Vg(z,, w²) where w prox pg(z,,) (z). That is, to apply gradient descent-ascent on the (2,, y, z). we need only solve for proximal operations associated with h, and gzz, .). While we may not be able to compute the proximal operators exactly, introduce intermediate variables Wy.k, Wi.k
17

---

Under review as a conference paper at ICLR 2024
Algorithm 2 Single Loop Algorithm with Momentum Assistance
Input: total outer-loop iterations: K, step sizes: (a
parameters: {3x 3x (0, I}} penalty parameters: {ow}, momentum schedulers: {n m [J], proximal
parameter: p. initializations: zu X, yos Fo E E
1: Initialize y.y0 = yo. W/.00 =
2: for k = O...K do
3: # Proximal-Operation Solvers
4: Wy.k+1 t- 11y Wyyk 7x (o + Twy + (u - wkl)
5: W2,k+1 +- F W=,k >x >x + p (W2,k - ])}
6:
# Proximal-Smoothhe
on Lover-Level Variables
7: Mh++1 < 82 )/ + 2,+11
8: Ek+1 t (1 3x)=E + + Wxt11
9:
# (Projected) Gradient Descent on Upper-Level Variables
Øk+1 + Ix { { ark (o+Ja + Tey T2: T
10:
11:
end for
that chase the solution of proximal envelopes. We then design the inner loop of the algorithm to solve the proximal operation using T3 inner iterations. Later, we make particular choices of the number of inner iterations T& to achieve the best oracle complexity and convergence rates.
To address issue above, we simply choose
-ー* for some chosen constant s >> 0. This rate of decrease of di optimized achieve the best oracle complexity and convergence rates reach an e-stationary point of (ar, y, 2). We summarize the overall double-loop implementation in Algorithm 1, where we define:
(z.
pk.t
wg V of Uei Shin);
Jwy V vag(a uei Ehin))
V Vyggua Uti ck.t),
Faiz
pk.m V ( Wy m Izy
k.m
V V Wy clym),
gi V Lag W2 (h.").
Jz
We mention here that may try Th- M2 0(), in which case Algorithm I becomes single- loop algorithm. However, as we see in the analysis, the optimal scheduling of Ti and Mj should increase with i (see also Remark C.3).
B.3 A FULLY SINGLE-LOOP FIRST-ORDER ALGORITHM
A drawback of double-loop implementation is that we have to wait for an increasingly large number of samples (since we design T& or M& to be increased k) to be collected before we can improve the objective. A natural question is whether we can keep incrementally updating upper-level variables without waiting for too many inner iterations or for the evaluation of large batches. If the stochastic oracle satisfies the mean-squared smoothness assumption and allow two points to be queried simul- taneously, then we can implement the algorithm in single-loop (that replace the inner loops with single step, and avoid the use of large poly(E-! batches):
Assumption 11 Stochastic oracles allow 2 s-mmulttneouss query: the algorithm can observe unbiased estimators of V fx, Vg(a, y) at two different points (æ1, ) (x2, 32) for shared random seed Ç and s. Furthermore, gradient estimators satisfy the mean- wrean-squaeed smoothness condition:
E[[ [ (g (1: Vg(22, U2: 1 < (1 x2l1 + 1l
(x y2: 0)1 < (1 x22 21 + 1191 1/2113)
y/2 11
We define momentum-assiste gradient estimators recursively for the inner loop mroximal-solvert as follows:
*k = V Vor W2 )b.)) + (1 - (Awz V Vyg(#+-1: 12, Ew:))
Ph = Vyl(ER: Wyiki ki cte + 1)) [ Vyf(#k-1, Wy,k st
Pwy Vug(aR, Wy, ) + (1 T)K) (ghy1
Vug(ue-1 Wyy k- sty
18

---

Under review as conference paper at ICLR 2024
where 7 E (0, 1|, and "ju (and thus, ignores (k: 11th terms at & 0). Formulas for the update to upper-level variables z are defined similarly. A single-loop alternative to Algorithm can be defined as in Algorithm 2. Our analysis shows that the momentum-asisted technique leads to improvement in sample-complexity upper bounds.
APPENDIX C
ANALYSIS OVERVIEW
In this section, we provide our main convergence results for Algorithm and Algorithm
C.1 ANALYSIS OF ALGORITHM
We first define the proximal error of and 2 at the th iteration as:
A p (yx= prox (Z..) (v=)), 1 : p- (2k prox pg(x,)
(zx))
For measuring the error in æ. we define"
4 == xIx 2h ax (Vaton (I prox (Fur) (vu)) - V prox pg( (2a)))
A ox (ork tx).
Next, we define
t (x, h h (z, v) 2z(
C -
(14)
with some universal constant C 4, and finallly define the potential function
Ve = (Tkk ykes zx) + Owis (lecy,d prox phr, (w),)) (2n))1 + || prox polwar (2x)
12)
okp
(15)
where C. > is some sufficiently large universal constant, and A := /4pp is a target improvement rate for chasing proximal operators per outer-iteration. We are now ready to state our main convergence theorem.
Theorem C.1 Suppose that Assumptions 1-4 and 9-10 hold, with parameters and stepsizes satisfying the following bounds. for all 2 0:
Tknk cap, p 02/llg,1 o% /
S <1 as S (5p(1114,1111
os cap min(p² 82 D Ba,
ok 0k+1 sepp² min(f? 2 ,88 (²/D3)) Ba,
xkt1
(16)
with some universal constants C1, 02 C3, C4, C5 Co C7 > as well as the following:
p3x as S cg Tir
Vk,
(17)
with some universal constant 0g > O. Then the iterates of Algorithm 1 satisfy
KK
|
p3
(1A + ((EE1))
< <EVV - Vxl
(18)
16
160%
O(())
K-1
Σ
Th ok+1
-
011g1/11 Cw)
K-1 Eov k=
(ak Mr
+ - (oR07 + o
ah+1
k=0
Note that AJ is a stricter stationarity measure than Definition 8 as long as S p. since the function g [0, oc) IR defined by g(s) : ||: xxx {ar + swo) ||/s with any Rd is monotonically nonincreasing
(sce egg., Lemma 2.3.1 Bertsekas (1999))
19

---

Under review as a conference paper at ICLR 2024
The proof of Theorem C.1 is given in Appendix F. We mention here that problem-ddepeneee constants may not be fully optimized and could be improved with more careful analysis. Still, there are two major considerations for the stepsizes: (i) the relations between (i) 3g and ag and (ii) the relations between og (or p.3)) and Tk Regarding (i), the conditions (16) require 04/ /3x x p² min(p, 5/ Dy)². Effectively, this relation determines the number of updates of the yk and i variables for each update of zg. The condition is necessary to ensure that and 2y always remain relatively close to the solution-set T σxk) and T(TK, 0) in expectation, which is crucial to convergence a stationary point of the saddle-poing problem (13). Regarding (ii), the relation between ag and T&?% in (17) is required for approximately evaluating the proximal operators without solving from scratch every outer iteration.
As corollary, with proper design of step-sizes, we can give a finite-time convergence guarantee for reaching an approximate stationary point of tho (2:). To simplify the statement, we treat all problem- dependent parameters as (1) quantities.
Corollary C.2 Let ag -o) -cc(kkt ", and oh - Co (k+ ko)-=, Ts (k ka)² M4 (k ka) with some proper problem-dependent constants Ca Cg: Cyp Co. and kg. Let R be random variable drawn from uniform distribution over {0, K - 1}, and let Øk. Under the same conditions Theorem C.I. the following holds after K iterations of Algorithm 1: for the optimal design of rates, we set b 0, = 1/3, and
(a) if stochastic noises are present in both upper-level objective f and lower-level objective (i.e., of o3 > 0), then let t 4/3.
(b) If stochastic noises are present only in f (i.e., o3 0, o² = 0), then let c = t -m -m=2/3
(c) If we have access to exact information about f and (i... o = = = 0), then let c c =
m O.
Then, we have [
x
log K K with probability at least 2/3. If Assumption 7 and 8 additionally
hold at nR then we also have [v((T)]
log K
K179
Note that the overall gradient oracle complexity (or simply sample complexity) to have ( (c) given by O(K (Mx + Tk)) with K Oc-1//) and Mx Tk O(e7)). Thus, we have O ()) O(e "), and O 2) sample-complexity upper-bounds for fully- stochastic, only upper-level stochastic, and deterministic cases respectively.
Remark C.3 (Single-Loop Implementation with Algorithm 1) While we design Tk Mr O(E=) to achieve the best complexity bound in stochastic scenarios, we can also find different rate scheduling for which Tk MM =(1). For instance, when X = =Rd, we can change the coefficients of noise- variance terms from O (M) to O(az), and schedule the rates of step-sizes noise-variance
such that left-hand side of (18) converges. However, we found that such a single-loop design may result in overall worse complexity bounds unless momentum-assistane techniques are deployed.
C.2 ANALYSIS OF ALGORITHM
In addition to quantities defined before, we also should track the noise-variance terms in momentum- assisted gradient estimators. We first define the expected gradients G Gh Gh as follows:
G m2 = V Vyg(zk, w.,k), Gh := σk V Vyf wy,k) + V Vog(IA, wy,k),
h a V V (#k, (g.b+1) + V V.g(Z wy.++1) V V Ffg(zz (Zk, Ws,b+1).
Next, we define error terms &t et c ct in these gradient estimators follows:
h = ghzz G+t : = on + Twy G c = + (gth ghha) Gt..
Finally, we we redefine the potential function:
Cw
(Iwin prox phin (ce..) ( + 1| prox proxpo(mx.)) (2x)
V = P (or, Uk. 2x) + oap
20

---

Under review as a conference paper at ICLR 2024
Cup² (1e/--112 + | 112 + lle 11²)
(19)
with some properly set universal constants Cwr, C > O. For technical reasons, we require here one additional assumption on the boundedness of the movement in Wy.k-
Assumption 12 For all x E X and y, E , let w = prox ph. (2.) = arg min ha (z, y. w) and = == prox pr(x))((.-)) (2) arg min ( 2, w) where (2, w) and g(x, w) are defined in (12). We assume that
V w S Mw: (u Mw.
for some (problem-dependent)) constant M O(1)
We now ready to state the convergence guarantee for the momentum momentum-assisted fully-single loop implementation.
Theorem C.4 Suppose that Assumptions 1-4, 9-12 hold, with parameters and step-sizes satisfying(10 as well as the following relations for all k 2
pak + O.k S. 0g'lk,
Mk+1 2 cap max
(20)
Then the iterates of Algorithm satisfy the following inequality:
Olk
Bx 160
(llyk w2 11 - w2,ul??)
<VVVo Vkl
160k
K
O(C))++ O(M2))P (ok-0ut1)
0
0k
JR+1
+ Cup
(0203 + tgg)
Cwo
Tk+1
k=
c,,0(p2tg.) [Roo yo. wy,0) - hー ( yo)
g(00, 20, W2,0)
- 97 (z0: 20)
σ
d0
We then give a corollary analogous to Corollary C.2, with proper design of step-sizes. As before, to simplify the statement, treat all problem-dependdnt parameters ((1) quantities.
Corollary C.5 Let = co.((kkko) 3x (o 'Tk = (k+ co
and Ti. (k ko)- with some proper problem-dependent constants Cas CB, Cyp Ca. and ko. Let R be a random variable drawn from a uniform distribution over {0. K - 1), and let c ок- Under the same conditions in Theorem C.4, the following claims hold after K. iterations of Algorithm
(a) If stochastic noise is present in both upper-level objective and lower-level objective (i.e., o7. o 0), then let b 2/5, 1/5, and 4/5. Then ( with probability least 2/3.
log K K175
(b) If stochastic noises are present only in f. let a b= 1/4, 1/4, and n = 1/2. Then x
K with probability at least 2/3.
R174
(c) we we have access exact gradient information, let a b c= 0. = n Then [v)(( x
lng with probability at least 2/3.
Ktys
If Assumption 7 and 8 additionally hold at RR then the same conclusion holds for [
Note that since Algorithm 2 only uses 0(1) samples per iteration, the overall is upper-boundeds by O)e-5), O and O for fully-stochastic, only upper-level stochastic. and deterministic cases respectively. That is, momentum assistance not only enables single-loop implementation, but also improves the overall sample complexity.
21

---

Under review as a conference paper at ICLR 2024
APPENDIX D AUXILIARY LEMMAS
Throughout the section, we take S 01/lg,1 and a < 021g,1/4.1 with sufficiently small universal constants c, C2 (0, 0.00. We also assume that Assumptions 2-4 hold by default.
Theorem D.1 (Danskin's Theorem) Let [(w, 0) be a continuously differentiable and smooth func- tion on W x O Let (w) == minsee f(w, 8) and S(w) == arg mingee f(w (), and assume S(w) compact for all w. Then the directional derivative of (w) in direction v with ||aa| = 1 given by:
I' (w + ōu) - (wo) min (v, [w, (w, 0)). 6E8(w)
Del (w) == lim 5-0
(21)
Lemma D.2 (Proposition 5 in Shen & Chen (2023)) For continuously-fffeeentdaaa and L- smooth function fw,,6 8) in W x O consider minimizer function 1* (w) mingee f(w, 0) and a solution map S(w) arg minaee [w, 0). If ((w) is Ls-Lipschitz continuous wt then 1 (w) is differentiable and L(1 + L -smooth at w, and 7i" (w) = V (wn (*) for any 8 E S(w).
Lemma D.3 For any 21,22 E X, and y1, 122 E y, the following holds:
proxx pater (111 prox poloz,) (v2)) O 11) xz2 1ly1 y2ll-
The same property holds with ho (z. instead of (xx.)).
Lemma D.4 For any x X, y E y and 01 02 o). the following holds:
prox phr, (x,) (y) - prox (t,, (1)l S O(pls,))oo 02l.
Lemma D.5 For the choice of p < 1/(4gg,) and a < c. ly,1//lf, with sufficiently small e > 1i (1, u) is continuously differentiable and 2p- --mooohh jointly in (x, y).
APPENDIX E
DEFERRED PROOFS IN SECTION 3
E.1
SPECIAL CASE: UNIQUE SOLUTION INVERTIBLE HESSIAN
When the Hessian is invertible at the unique solution, the statement can be made stronger since we deduce solution-set Lipschitz continuity from the well-understood solution sensitivity analysis in constrained optimization Bonnans & Shapiro (2013). That is, we can provide strong sufficiency guarantee for the Lipschitz continuity of solution-sets.
Proposition E.1 (Sufficient Condition for Lipschitz Continuity) Suppose y E T(x, о) is the unique lower-level solution at (I,o). Suppose that Assumption 6 holds y" with correspond- ing Lagrangian multipliers Xt, v². Further, suppose that 422 V2 is invertible. Then T(x, o) is locally Lipschitz continuous at (z,
Thus, the uniqueness of the solution along with LICQ, strict complementarity. and invertibility of the Hessian is strong enough to guarantee the Lipschitz continuity solution sets. Therefore, we can conclude that 8² Ux, .)) exists and that the order of differentiation commutes under Assumption 6. 8206
Theorem E.2 Suppose y E T(x, a) is the unique lower-level solution at (x,o). If A'ssumptiin 6 holds y", and C2 is invertible, then 8² Bude d0 o)) exists and can be given explicitly by
82 dodx ((x,0)= Ozdo 1(x,0)
O²
-Ve((x,))) - (z v")] Ly v², y la, o)) (
0
v)((r,)'))
If this equality holds at 0+, then (x) is differentiable at x, and lim Vol(2)) Vv(())
Below, we first provide the proofs of Proposition E.1 and Theorem E.2.
22

---

Under review as a conference paper at ICLR 2024
E.2 PROOF OF PROPOSITION E.1
The proof is based on the celebrated implicit function theorem. See Appendix C.7 in Evans (2022), for instance. We first show that if (xx a) T(x; o)) unique, then there exists ō > and bg such that for all [x(",, ,²) - (I, a)ll < 6, the solution satisfies T(x', o') C B(y", 5y) and is singleton where [yy", 6y) an open ball of radius by centered at y". When the context is clear, we simply denote y (I, 0) as y²
To begin with, we first argue that we can take ò small enough such that solutions cannot happen outside the neighborhood of y². Note that unions of all solution sets are contained in (0,, R) with some finite R < co due to Assumption 4. For any by > O, let qet m Rt)/Byy"(/) /B))",.))) (az y) + g(x, y). y) + Vzg(z, y)ll + f(x. y)) (the fimite maximum exists since f.g are smooth). Since T(x or) singleton, we have q" > [(x, σ). Thus, there exists < 60 < (a" (gx""(xx,))) o)),M, such that for all (x',a') E (B( σ), 66), we have T('', o²) S [By, 6y).
and let M max n)
Next, by regularity and strict complementary slackness of yy, there exists unique (X", such that N > 0 for all E I(y"), ) X = O for all i & I(y"), ) and V VL v" y² ()) = 0. Since we assumed C2 2², yy [z, being invertible, we can apply implicit function theorem. That is, there exists an sufficiently small 6 > 0 such that for all (x', (x',,")) (x) < 6, we can take òx,0, 6g > 0 such that there is a unique (Nz, ,3''
VL2 v/, 1/ 1' = 0,
inside the local region 11 v) (X v²) < 5x.0 and Ily/ - =ll < 6y. Thus, we can take ō > 0 sufficiently small such that ox can be sufficiently small to keep >iz non-negative.
Furthermore, in this local region, T(x', S Byy 5,) for all (a', E B((x,, o') where min(66. 8), which in turn implies that T o') is a singleton and uniquely given by the implicit function theorem. Therefore, T(x, o) is differentiable and thus locally Lipschitz continuous. In addition, T(x, o)) always singleton over (((x, 8').
E.3
PRooF or THEOREM E.2
Recall the local region given in the proof of Proposition E.I. We note that the implicit function theorem further says that in this local region, we can define differentiation of y with respect to æ and such that
dy (z,o) [0 I V v , dg
vof(E,)))
V (2, [0 I V v*, ",0'0,
V2 (2, (2))
As consequence,
0² Boor 1zz o) is given by
82
8 dn
dodr (xx,))
3 (oV (x, (x,
oo dy (z) + V Vayo(e,v"<,,o))
(
-Vf( (I, 0))
do
V.f(e,y' [0
Vayhola, (V
Similarly, differentiation in swapped order is also given by
02 θ
Ord0 (1x,))
Or ((r,)"
-Vzf(z,v' Vey (aaa)
Val(e, jo (x, (V*Ct) V (
82 Hence
3230 [xx σ) exists. If this holds 0+, then we have limg-0 the (x) x(xx)
23

---

Under review as a conference paper at ICLR 2024
E.4 PROOF oF PROPOSITION 3.4
We instead prove the general version of Proposition 3.4:
and L-smooth with W. satisfying Assumption 4. Let (w) mingee f(, 0). Assume the solution map S(w) = arg mingee [ww, 0) is locally Lipschitz continuous at w. For any 0 E S(w) such that (1) 6 satisfies Definition and with Lagrangiann multipliers X", and (2) V L locally continuous (w, X x0) jointly in (w, X, 0). Then the following must hold:
Theorem E.3 Suppose that f(w, 0) in W x θ is continuouty-ddifreentii
Yu E Im (w
E Im V 1("",00000000
Then Proposition 3.4 follows as a corollary.
Proof. We show this by contradiction. For simplicity, assume that Let {gi hez(e-) be set of active constraints of θ at 0". To simplify the discussion, we assume no equality constraints (there will be no change in the argument). Suppose there exists v E Im / 0²)) such that ||||| = 1 and (0, v) is not in the image of Lagrangian Hessian. Let (0, v) "Ker + Vim be the orthogonal decomposition of v into kernel and image of the Hessian of Lagrangian. Note that we can take v such that |e > O. Let (dz, do) be such that 12()) v = bn fww, )")
and LT oo such that for all |dw]] there exists ||d0|| < L such that 6" + d0 E 5(w + dw). We can take small enough such that inactive inequality constraints stay inactive with d8 change. Thus, when considering d', we do not change coordinates that correspond to inactive constraints.
Since Sww) is locally Lipschitz continuous, there exists
We claim that there cannot exist (d), dif) with ||00| < Irō that can satisfy
VC(("* + dA, 0 + d0 + dw) = O.
First, show that dY cannot be too large. Note that
VL(2** + 12,0" (w) VL(A" (w))
Σ (d),) iEI(
(g', iE I(0 iE I(0))
Since we assumed that B is full-rank in columns, the minimum (right) singular value 8min of B is strictly positive, iee, Smin > O. On the other hand, by Lipschitz-continitty of all gradients, perturbations in w, 0 can change gradients of Lagrangian only by order (())
VL(X" + dd, 0r + d0|w w dw)- VL(A" + dd, (ww) <
d| perturbed
+
Σ iEI(O*)
(X + da,)
perturhed by d0
Thus, since (dw, d0) = O6)), we have
(8min (()))| + (())( + 0.
(22)
By taking 8 Smin small enough, and due to the existence of Lagrange multipliers ||^||| oc, we have proven that |dAl|| = O(8) with sufficiently small 6.
Next, we check that
VL + dx, + d0 w + du, θ) - V
dd
= 2()) (WKer + vmm) + 2 L( Iw)
+ o(8).
d0
However, UKer is not in the image of V2C, and o()) terms cannot eliminate 12(5)- Uker if 8 < [Kkeell Thus, VL(** + d', 8* + d0 u + dw, Q) cannot be O, which implies there is feasible optimal solution in 8-ball around 0* if we perturb w in direction dw. This contradicts S(w) being locally Lipschitz continuous. Thus, (10) necessary for S(w) to be locally Lipschitz continuous.
0
24

---

Under review as a conference paper at ICLR 2024
5.5 PROOF OF THEOREM 3.1
Similarly to the proof of Proposition 3.4, we prove the following general version:
and L-smooth with W, & satisfying Assumption 4. Let (w) mingee f(w 8). Assume the solution map S(w) arg mingee [ww 0) is locally Lipschtt continuous at all neighborhoods of w. For E W. Lipschitzzconiinuuuu if there exists at least one 8 E ((w) such that (1) 0" satisfies Definition 5 and 6 with Lagrangiaa
Theorem E.4 Suppose that f(w,0) in W x e is continuoustyddifreentie
multipliers X², and (2) f, V C2 is locally continuous at (w,Xz, 0²) jointly in (w, XI, 0), then
221 (w) exists and given by
V (w, 0n) (o)
(w)) V2 (wc 0*)
[0
V ( 0r) Lz ('))))
(23)
Theorem 3.1 follows as a corollary by only taking
#² Dzde
and
8² Boos
parts with w (a,
Proof. Let 0f E S(w + tv) be the closest solution to l e S(w), and let X; be the corresponding Lagrangian multiplier. Let == I(0") be set of active constraints of θ at 0*. As in the proof of Theorem E.3, to simplify the discussion, we assume there is no equality constraints (including equality constraints needs only a straightforward modification). We first show that the active constraints I does not change due to the perturbation to in when the solution set is Lipschitz continuous. To see this, note that all inactive inequality constraints remain strictly negative gi (0) < 0 for all i o I(0"). For active constraints, due to Definition 6, we have X > for all g, (0")
0 with i I. By the solution-set continuity given as assumption, we have ||0, - -0 || (t). Thus, by the same argument as deriving (22), we have ||^; || O(t) as well for sufficiently small t. Thus, active constraints remain the same with perturbation of amount (t)) as long as < min X;-
Now by the Lipschitzness of the solution map S(0) and Lemma D.2, have (I" (wr, 0), v0 E S(w).
To begin with, for any unit vector v and arbitrarily small t >> O, we consider
V + tv) (w)
6
which approximates (w) Furthermore, due Lemma D.2 and the local continuity of V holds that
VI" (w tv) (w) Vwr(w + to, 07) V f 8*)
t
t tV P f(W, v + V (0, -0") + o(1).
(ww.0) Q) 2 = V²Lz((A") (C=((A))z,0'(uu)) 0"|
is invertible, then by the implicit function theorem,
(At) - -2x)
8: - 0* = (v* Vin (1)) o(t).
In general, let the eigen- -eceomocoooooioonn 4 QEQ of generality, assume that the first columns of Q correspond to non-zero eigenvalues. Let pmin > 0 be the smallest absolute value non-zero eigenvalue, and let U == Qr be the first r columns of Q, and let U, be the orthogonal complement of i.e., U is the kernel basis of 4 C2. We fix U henceforth.
QEQT and let r be the rank V Lz. Without loss
Our goal is to show that
UT
( (X*)z
- -
(C())
V2 [w, (ww00)) 0+) v o(1).
(24)
0 0+
If this holds, then we can plug this into the original differentiation formula, yielding
Vi" (w + tv) Vi* t. V (w, 8t) o o [w, w, (0; 6*) + o
t
t
25

---

Under review as a conference paper at ICLR 2024
(17 -
1. V (w,
8; Hr
+ +0(1)
t
= (w, - ([o V [w) U) (U ( U
(w,
o(1)
Since Im
([
Vhe Wwr (w) C span(U), sending & - O, the limit is given by
vir(w)u= V fw, 8*) ) [0 V w 00] (v2 Cg)
bw, or)
The above holds for any unit vector and we conclude (23). Note that this holds for any 0 S(w) where C(X*, 0* ww, () is locally Hessian- LiisshhtL (jointly in w, and 0), concluding the proof.
[r] 0
We are left with showing (24). For simplicity, let y
and we simply denote [(w,y) :=
Clz(Az, 0 f/w, Q). Consider Ly (w: 2) == C(w, Uz + yo) where yo is projected point of y onto the kernel of Ll Note that since kernel and image are orthogonal complements of each other, y" = U + you where 2"' = U y. We list a few properties of Lu (w, 2):
V. (w, 2) = U VoL(w, Uz + yo),
V #2 (w 2) = U V V (w,, U2 + Uo)
V Ww Lu((,,) Clu, Uz + yo)UU
and Le is locally uniformly Lipschitz continuous at (w, =*) jointly in (w, z).
A crucial observation is that x" is critical point of Lr(w,,), i.e. V2Lu(u,=") (,,(w, = 0, and at (w, =*),
v2 22 Lu (w, =0) = U VooL(w, + 00) = VooCo, O'U,
and min V Lu 2²) )'ull 2 Mmin- Tracking the movement from x" to of with respect to (fv) perturbations in w. by implicit function theorem, we have
= - fo (wc, (V? Lu (w, = })v + o(t).
where 27 is the only O(t) neignborrooodd of 2" that satisfies V.Lu (w + tv, 27) = 0. Note that for any in the neighborhood of 2;,
(V (w + tv, 2) v VuLu(w (w + tu, 21 = 1| Co (w + tv, 2)) z1) + 0(1 x > (Mmin - -(1) +11ii)|= zill O(1 2 11)
Now let v6 be the projection of yt onto the kernel of V (w, 0*). Since vf 0)) E S(w + tv) a global solution for w + to (without active constraints changed thanks to 0 satisfying Definition 6), we have
1 -/
VV + to, tel N
L + te,
I
C(w + tu, v1)
V2
1 V2 IU V + tv, U + (U - U. vi) + (y0 26)) +
1
|U V y C(w + tu, vi +o(t).
(18)
where we used U V + tu. U2; + yo) = VzL(w + tv, v²) 0, continuity of 42 and llvt nO = O(1) in the last equality. To bound (i), we observe that
(i) > IU V2 f(w + tu, U2i + (2) U yi ||| T F + tu, Uzt + vo) vi)l
Le + Wv =; (i] UT bill - 1 (V² by L(w + te, Uzi + vo) - v2 F(w, 21 ))(( - =o)l
2 ((umin O(t) 011 - = =1)00(11 - -U vt II) o(t) - o (t)
((mmm))) UT 0,11 -(()-
26

---

Under review as a conference paper at ICLR 2024
where we used l1 yoll livt y²1l Ott), and assuming Mminn On the other hand,
(ii) = | (V, tu, vτ) vyL(w, y")
- | ( y²) + Sww (v: - y²)) + o() =
where the first cquality follows from the optimality condition of 8", and the last equality is due to necessity condition (Proposition 3.4) for the Lipsethiz-comtinitty of solution maps. Therefore, conclude that
= (V + tu, v(' 2 Ofumi))l - U UTuill o(I),
which can only be true if ||2| - UT y || =(t). This means
Uvi -y)) (U vi = (2i-2")
=- Lu (w, - Lu (w, 2²))²²² o(t),
and thus we get
U Uwi - y²) -1 (w, yn \U) you y ((w,y")) 1 + o(1)
(25)
Note that the constraint does not depend on w, and thus
V2
L(w, y²) 3yt
V yuu (w, (w,y") v*)
On the other hand, the necessity condition given Proposition E.3 implies
Im V (ww, v) Im [(w, v*)) span (U). From the above inclusion and (25), conclude (24).
E.6 PROOF OF THEoReM 3-7
Proof. For simplicity, y2 T(z o), let zp be a projected point of y onto S(x) := T(x, 0). To bound (v)()) (x)),, we first see that
min g(x, = (x) min (J(z,)) v)/o)
yEY
sey
S min (f(z,y) + g(.,)//o)
min zey
x),
min f(x, = (51)). =ES(x)
vES(z)
We first show that g(z, vr) - g(z, 2/ < 8. To see this, note that
of of vo) ga. vz) < of x/) + g(2x,z))
and thus g(x v²) (xxx (f x)) f(x, v,)) < 200,. As long as S $
we have
207
g(x, v=) g(x, 2/ S 8. Then, since we have Assumption 1, we get
Vo (x) = f(x, v=) + g(x, g(x,vC) v.) g(x, 2 f(x, vo) +
plly 2
20
We can further observe that
11 - 2?,1?
11 - =,,1?
f vG) + P1g
f(x 2/) 1hg
4.00l 25
2a
12
17,0
2 s(x, =/))
2 (xx)
σ.
2p.
2p
Thus, we conclude that
17.0
0 <b())) (x( <
24
27

---

Under review as a conference paper at ICLR 2024
Gradient Convergence. As long as the active constraint set does not change, only consider dG. By (4.o/ continuity of solution sets, for all 01, 02 E [0, a.. we can find y (Ø1) E T(z (02) E T(x, 02) such that
(ly)(a)) - =()))))))( -2/--
On the other hand, we check that
VL((2
(o) (
+ Σ
(v ((1)))
EE
iE(mal
A* (²)) - (0
= (
1/ (02)
1/" (0)
0
At the same time, we also know that
S 00 - 01 + 0l1 ((1,)) + (00 - y (a))l-
Since the two must sum up to O, we have
(x (((a)) 1" (02
VL v² (z)
v" (a))
00/,1110//0002 oıl.
0
Thus, with Assumption 8, we have - (170 vf(01)) = 1,0 (18mma)))o2 01|-
Thus, can conclude that
12,66/1 M.mmin
+ Ini2t100
V
l0z 102- 01|.
1
where (V)) is a short-hand for (o)
To check whether Viha (z) well-approximates Vib(x)) any 01, 02 E [0
Jado 2 ((1u,o))ee lozt we first check that for
0²
0²
1(I, (()
Oxdo ((. s(Va)(a. 1 -
Ixdo
\'C [
0
+ 22 my
Mr (x, 1² (o2)) - Vay hon (2.1")
(V (.
+ 0
+
[|[o
V2
Here, we use the explicit formula of meaning of the latter term:
8 Ozda
(x, σ) given in Theorem 3.1. To bound (i), note the
dd/ dy/da
= C(Co( (
where dd//oo dy/do is the movement of y* (a1) to the nearest solution by perturbing projected the
image 2 (a1). By Lemma 3.6, | must not exceed 0(1 p)) Consequently,
dA
dy
(a) [Vhx(y(()), Vi [ma]] do
+ v by (+
do = Vyf(z,
28

---

Under review as conference paper at ICLR 2024
which enforces that |dd/do v
1215 jaswin
by Assumption 8. Thus.
1 4g.1 11.0 10010 02 11,24g,
x
01 02
118mmn
1 8min
Similarly, we can show that
S 42141118000
(idi)
00 02).
pmin
For (fi), note that
(V - (F (oo)))
V my
(x,
(V2C)(0)))) v' (PC (.)
0
(2
9.1 77.0
( C
2
12 7.00
|o2 102-o1h oib
118mm
where the first equality comes from the fact that
(a. c Im (o)).
Im
and similarly,
0 [ Vyf(2. E lt
by Proposition 3.4. Therefore, O2de 1xx o) is Lipschitz-continuous in a, and by Mean-Value Theorem, we can conclude that
(1220% 3
22.00,10..00
Vo)(()) votr)l
min
min
counting the dominating term.
E.7 E-STATIONARY POINT AND KKTT SOLUTION
To simplify the argument, we assume that X' = Rd= Then, define an e-KKT condition of (Poon) as:
V.f(z, v) (V Vz'())) <e e, ,V.f( + Ae Vyg(z, y) + Eie(aa) X (v) Eie(m 11 (v)) < g(x. g"(x) S
for some Lagrangian multipliers X 0 and X 2 0, 1² with some (x,y) E X x
Theorem F.5 Suppose Assumptions 1-3 hold, X Rdd, Then Vika (x) well-defined with S do- If x is an 6-stationary point of vh (x) with a S 1, that is,
[vb((a)] Se,
then is an O(e -KKT solution of (Pon))
29

---

Under review as conference paper at ICLR 2024
Proof. This comes almost immediately from Lemma D.2. Let y and minimizers:
arg min a (x, w) + g(x, w), wey
E arg min g(, w). WE)
Then, by the optimality condition of y, the c-opimallity condition with respect to V, y is automatically satisfied with X₂ 1/a. Furthermore, since T(x, σ) Lipshictz-comtinuuus due Assumption 1 with LT = f μ., we have Vg" (z) = Vzg 2. 2) and Vh (x) Va y) + V,g(z.y) y).
Finally, by the optimality condition, we know that y is the optimal solution a proximal operation prox (m,))
fz y) + g(x, 9) S oa((z g(x,2)
1| y/1 2p
Using (sx (xx Ioolly =|| and ||y =|| LL,, have
g(x,y) - g(x, 2) = g(z v) gZ(x) S ولم + 0²L22
= 0(o²),
2p
as claimed.
APPENDIX F ANALYSIS FOR ALGORITHM
For simplicity, w 9. prox proxphog phos (ze.) (yk) and w = prox pg(xe..) (Fx))
F11 DESCENT LEMMA FOR Wy,kk Wa.k
We first analyze ||W,, prox oh (ee, (yke))(x))) We start by observing that
[1y,k+1 W ++1++ 21 || - w 112 + I1w w. -2 - W W
w
d
4 ||uy,t+1 - wl + (1 (1 N | wl?
I +
(26)
(0)
(16)
where we used (a, b) S c||a|12 following lemmas.
+ de 11111, and d Te/kk/ as defined. They are bounded in two
Lemma F.1 At every hth iteration, the following holds:
Th
E[]lwy,t+1 - w 11 <
7ik 4p
E Flll
+ 2 (o + -3 + og).
(27)
Similarly, also have that
Th E|| - [ + o7+0)) (28)
7kk
W2 " " <
1
4p
Proof. We use the linear convergence of projected gradient steps. To simplify the notation, let
G Vy(onf un sting) + g(Iks uni shigg) + p (we - -yk), and G, = E[G.]. Also let G Vhoz (x, k) + (w - yk). We first check that
|ue41 x| 2 = Tly Ue G/ -Tyy {wG -ma0
<< ur 7x G. - (wi - Gm
30

---

Under review as conference paper at ICLR 2024
7/ |,. G-1|" -77 (u+
|| 1 11
W G. G*).
Taking expectation conditioned on Fu,e yields:
Bll
- Bll u4 - w [x,1 RB]|IT; -G
- 27 (ue - w G2 - G
Note that
G² B 2
2B1|G, + G, (R convex
By co-coercivity of strongly convex function, since the inner minimization is and (1/p)-mmooth, we have
||. - G²1| S (1/p) {ur - w - GC)
1
||ue w 11? S (m w G2 - G*)
3p
Given < we have
E| " Fx,el S
E uu - " 11 + 27 ogg
4p
Applying this for Tk steps, we get the lemma.
Lemma F.2 At every keth iteration, the following holds:
Bl]l ((..+1119(FF) < (1 1
p²17.00
E[ Blllwy,++1
- 11 +0
1o
- 12
dx
pla.1
8 xx112 12+ +
+ 0
||
|1 1/
(29)
Ase
Similarly, we have
d
1217
B - W WI
1 +
- [1 +0
o
0x+1
du
plo.1
+
||
- xx + A
|| -2el12
(30)
As
Proof.
By Lemmas D.3 and D.4, we have
||i w < 0(pl, xxll + 11 yvll + Opp1,,))0x -xt1l-
Take square and conditional expectation, and plug this the bound for (4), (ti) in (26), we get the lemma.
F.2 DESCENT LEMMA FOR Lo.p
Proposition F.3 At every 1tth iteration, we have
αx $ (o ( 11e+ 11 2x+1)
$ (or.p( Uk, 21))
12.0 ao -Ott1l 12 dist (Zx, (zx; T(x,, 0)) + dist (yk, T(xR, on))
S Sip
yk+ 112 +
412
Cil,.1
1 1| sktill2 (c. + -)) (11 z+til2 + dist? (zx, T( 0)))
4ack
Bx
BR
(1ly== -wg 122 + 11 wy.tt1ll 112)
(1lEk wi 12 + 1| ws,a+all2)
4p
P
O 112 (12,1ax, aa + p BBa) (1log wy.k+ill
|| w2.k+all2) + aull G1l2 Tk+1 CiC, (31)
where C₁ = O /ou-OR+1
0k+1
31

---

Under review as a conference paper at ICLR 2024
Proof. To start with, note that
@ Po2t1pp(akt. Mo+1, Zx+1) Por.p(zk yk. yk. = D Po M611, 28+1) L p 2k)
+
11
9k+1, 21+1)
(e1)
Note that by Lemma 3.6, we have dist(T 01), T(22, o2)) S
# 12n |||
x2l +
1 01 σ2 for
all 31, 22
X. 01 02 E [0, 80, Applying this to (32) the subsequent subsection, we obtain that
oh Tk+1 - (1)) 00
Ok0k+1
p-1
Ilvx yk++1 112 + || - Ex+1|1
+
112
1l - xK++ 112 +
112 OR
1.0
ok+1 12
dist? (zk: (Irk 0)) + dist dist?(yk. T (()) } +0 oh obti
(0 ) Cr.
ok
Combining this with the estimation of (i) given in (36), conclude.
E2.1 BOUNDING (ii)
For (it), we realize that for any x, v, with o6t1 <.k.
h (x, g" (I,
1 (x, v) - - (x,,
① 1 (2) $ Pon.o (I,, v)
xkt1
ok
(C- (g)(2,2) (x))
C
C
Tk+1
h (ttt)p((E3)) 9 (I,
hi p v) (1, y)
xk+1
ok
(1ú))
0k - -
(5) v) - -9((x))
ORON+1
(iv)
Cloxk (((ok-owt)) -
OR+1TK
To bound (iit), for any a > 02, note that
[w - y/12
hi (2, & f w5) - g(x, wz) +
h ha (2, v) + (01 02) mz),
2p
1ww-
where w = arg min 02f (xx, w) + g(2, w)
Thus,
2p
- (1 hi 1o v)
(iii)
(h (1 - -iōn (x,,)) v))
0k+1
ok
< 2 Ok
Ck+1
(f w) ok 0k+1 -OCC))
max
Ok
wEY
In order to bound (iv), note that for any 3oe E T(x,
93 u) - 9" (x)
(6) v) h;) (x)) + -" (x)
(Vhho (e vo) y wit + O(p -1)l0~1)011 v. + O(C))).
=0
32

---

Under review as conference paper at ICLR 2024
where V Vyho,o Vā) pv: prox (x.,))) (v:)) = 0 since y is fixed point of prox proxpha(z.)) operation. Taking vi the closest element to y, we get
ak ak+1 dist (Mk+1, T(#++1, O(ox+1
(dv) -
Similarly, can also show that
(w) S - p ddist ( ((E+1.)
0bOh+1
Thus, we can conclude that
0
th xk+1
(oR+1Cs -
dist. (y T (1 p= "ist dist ((x++1
0k0k+1
0h Tk+1
(11E++1 =x11 dist (zk, T (axk 0)) dist (T
OH0K+1
+0
Th -
0++1
p (Ilv++1 - dist T( oR)) dist (is T* oR)))
0k0t+1
Th 0k+1
+0
Cz.
(32)
Ok
F2.2 BOUNDING (i)
Henceforth, simplify the notation, we simply denote ok.
(1) (h ( M6+1) 93 (16+1, 2641) (h (Tkk Uk) 96 (2k, zx)))
(vo, 1.5441) - (oe.
(0)()))1)))11)) (I (
ax) 9" (rx))).
(b)
Bounding (a). It is easy check using Lemma D.2 that
V Vy p (IK,, Uk) = p (yn w(,)):
V V.g zx) = p- 'zx w w(,,)s
Note that 3/++1 Uh = B2( 1l) and thus,
3k (yn wyyk: k: Uh - wy
(V h0 yk), 3 yx) =
3k (1ly: wg 11 wo.++111 1/ wy 11?))
2p
Similarly, 26+1 2k (2
Wz wz1++)). and thus
Bk (2k w 2x Wo.k+1)
(V29 (2), Zx+1 zn)
8k (11z4 w2 + 1| - W2 110 - -w.k411 112)
2p
Using smoothness of hr,p and 9 and noting that
V (hi (IR, yk) (a 2x)) V VaVa, Uk. 24) Vz(ho winx) g(zkk wt,x))
we get (caution on the sign of gf (#x,, 2x.) terms):
O(1)
(a) S (a Varha Uk. 2b), Tx+1 - I&) +
| 12.12
p
33

---

Under review as a conference paper at ICLR 2024
3k
3k
[1 w 2e11 1ll + 2 I1 wy 112)
11 - -Wg.++11
2p
2p
3k
Bk
(I|=x 22 112 + 2||2x w2, 112)
110 W2,,+11
(33)
2p
2p
where we assume 3k
< 1. For terms regarding x, let
Mr
Σ v (onf(ak, Wy " + g( Wy Wg.841i (h - g(rkk Wa W2,k+1i ():"))
MR m=1
and G K[ By projection lemma, we have
((Tx= .4. UK41, Ik+1) S 0,
Vx E X,
and therefore (G, Fb41 x) 1 1 (xx - Ix+1, - Ik+1) for all x E X. Plugging x = vx here,
we have
(G", 2k+1 - -kk) $
1 rb+1 1| (G' - G, -IR)
akk
1
| Ik+1 112 + ark (IGr -GI + -1G--Gi GIl))
S
2ck
Note that
|| Gll S (g,1 (Ilvog, Wy..- + 1w22 W2,+++ll).
In conclusion, omitting expectations on both sides, we have
f& (l
(a) S | - 2xll2
w5 2 + 1l Wy.t+ill 112) |xx+11 - -xx11== + (11=
20%
4p
+ 0(1)
Be
x11 + 1| - wz 112)
+ (11 + Bk
2p (1lwi,, wy,k+ill + || (2.3+1ll3) + axli - G1|2.
(34)
Bounding (b). We realize that in (34), coefficients of proximal error terms z, ie., || = 112 are positive, unlike terms regarding yk- We show that these terms will be canceled out with (b) when Assumption holds. Using Lemma 3.6,
(b) (g) 2k+1) - 9" 1)) ( 2k- (xxx)) + (1) 2x+1) (Fk, 2x))
11.1
(V (V ( # - V (xx) Fx+1 - xx) +0
||0411 - 12
11
(V (Tp 2x) 1사ナ - >イ) + +(p ||| - z4
(35)
Taking conditional expectation on both sides and using sb+1 - 2x = -Bx(Ex - we,k+1) and
[. 2x) = - w
10.1
B[(b)F[]] < - (T 2x+1) - V (2x), Ia+1 xxx) + O
[[]|=++1- - 2x
3x (V ( 2x), 2x w.
11
W2.
||:r x2+1 112
1
10(p-)aacC ddiss d 7 (ITK 0))
+0
E El 1
16Cox
/1
Be (1)zk - w', + || w2 w2,k+ll 112
18
112) +
|| w2.t+1l12
2p
Combining (a) and (b). We take C² 4. Given that oF & 1.. we can conclude
that
4az || - 2x 8K (1ly w.Juu1 + 1lue - (y.x+1113)
3x --:,..llll wI,ll + 11 w2.6+1l1?)
σk (i) <
(11Ex -
4p
+ 0 (12,1 (1,100 0h + pp-1 (1lwgA - b+ 112 + ||w - 122)+112))
+ 0pp -)xz (dist (zx, T( 0)) || - =x+1119) 119) + axllā -
(36)
34

---

Under review as conference paper at ICLR 2024
F3 PROOF THEOREM C.1
Note that
| 2x112 - (ax - - IIx far ox } 112 - a G*12
s 012 )a (110 "yy -1y,++1l ||u W' 222,+1111' ||] Bal G
and also note that
| Ik+1ll 2 | -ixl12 -21l0x x2-1
E||| G
{ + to,).
M
The following lemma is also useful:
Lemma F.4 Under Assumption for all x E EN E y and E 50,5 we have
dist(y, dist(y,T(I,,On T(x,o)) -
[ #
Dy
prox
pho (c.) (t)
Proof. This can be shown with a simple algebra:
dist(y, ((x, s - prox pho (a.,) (a,) (v)l {0 -1y {--1ly prox pho (a,,) (,)(( s 6)
+ Dy {o 111 prox (x,)) (y)l > 8)
and noting that {0 p 11y prox (z.,) (w) o} p p prox ph. (x.,) (w)l)
We now combine results in Proposition F.3, Lemma F.2 and Lemma 3.6, we have (omitting expecta- tions):
3r.
k+1
V
|0 2xll2
80 || 2x+1ll2
(llys w + 112t w 11
16
40
+0
-K-04+1
p- (dist T(rk, σk)) + dist. (EN, T(xx. (1zx)00))
0x0N+1
ak
0)) dist dist? T(rk, 0)) + + [k 1000000000000 (ak-out1 C5
+0
pook)
Ok
+0
(o--obt1) p-1 Ilue - 1142111 11 zx+1 112 +
ah 0k+1
12
9.1 || xx+1l12
17.0
4² oz -x4112
OKTN+1
422
O(1 11.1//1 + Cwpla,l)
O(Cupl?,0)
|1:66111 -x11 Tk
0x - oxtil 12
OkP
1
160 -
pp1ax)) -p
(1ly4 11+111? +112 2x+1l1?)
OkP
CwA
1 σk -o++1 d 0 0112))ocs + 2Bx
(Ilwi Wy Wy.t+1 112 ||05 -2,.+11l1 112)
okp
akt1
Owde
Cudck
201k -G12
wy.kil? 2 + 11 Wa, 12 + (1lwy
T&p
a
Note that w prox phv (Ix..)) (IIc and w = prox po( (ZK)). Using Lemma F.4 and rearranging the terms in the above inequality, we obtain that
[(1+ //./ + Cwplg..)
[
det2
V 1 VA 5
I 2x
|
1x+1ll
160
T&p
80p
akpu?
35

---

Under review as conference paper at ICLR 2024
Bk.
deCs
17.0
+ O(Cupli,))
+
11yk
22ix|1 112+
10 - okt1l
40kp
pok
112
Ok
Bk + dsC8
( p2ox ( )) 1|2s - wx2xil? + ds
C8O
40kp
por
dy
160 - p -p-ass) )) (I19x - -y+++1l 111 + 1| - zk+ 11²)
Tkp
Ohe
45
-k+1 dK + 0 )pre + 2.3 (lwi W W + 1w0.. -2,.+111 112)
1 Ok
TkP
Jkt1
Cuida
AR
200k - G|I2.
(1lwg uy 2
|I x2,x
GG--
TkP
ok
where de 0
Ok (x- Øk+1
)
and Cs = 1 D3 p=2
We state several step-size conditions to keep target quantities be bounded via telescope sum.
1. To keep the ||ar rx+1|l 1 term negative, we need 04 p(1 1/,///+ Gwply,))
2. To keep llyk " 2 term negative, along with Lemma F.4, we require
Ok
ok+1 p p-3 (1 (x-2 D3/12).
Øk+1
3. To keep
||
w term negative, we additionally require
Bg > p (n 1 ork
4. To keep terms on 1 Vk+1 2 and || 2k+1 2 negative, we first require
Bx < Cw pa
and then
1 0k 0k+1
Bg 0k+1
which trivially holds Br o(1) and (ax oxt1/Ok) O(1/k).
Once the above are satisfied, we get
3x (11yk w 122 11=2 - 112)
V *++
V S
|
160
160
(118k= Mk++1 112 + 11 - 21-1
+ 1/1//4 + Cmppla1
(a + axp)
+ -00203 + (ox - -oh-1) O(C,)
+ 0
OkP
Mr
Cw.Ak
+ Tk -0+11
A
0(1 (12,))pox +2
(IIW Wy 1 I1 - 22 112)
+
Tk+1
4
Cwds
CurAk
(Iwwt,
2 || - W2, + o(1/k),,
(37)
OkP
where o(1/k))term collectively represents the terms asymptotically smaller than Ce-0E+1 = O(1/k)
since we use polynomially decaying penalty parameters {ax}. Now we can apply Lemma F. and plug A Tes and using the step-size condition:
4p
Ty ok+1 E Ab, max (plz (p, Ba) < Ow
k++1
36

---

Under review as conference paper at ICLR 2024
get
V 1++
4/ -
0xk:
|1
9k
(112
-wy,x1? + +111 w3
160k
16oap
+0
+
11,11/1 1/1l/1 - Cumple.1
Okk
(0 + ) 0
C2u
Th
( + oz))
P
M&
o
(38)
Arranging terms and sum over l: = 0 K - 1, we have
E
Okk
|
p3x
(14 + (1
160k
160
K
ok - okt1
$ (Vo wx) + 0(C))
0K+1
k=0
Ol1a1/1+ Cwe)
K-1 Σ
Okk
+ p --T
(0R0 00)) 0
Ok"
P
M2
k=0
F.4 PROOF OF COROLLARY C.2
The remaining part to show that k lower-bounded by 0(1), and to check the rates. To see this, recall our definition in (14), and note that
h7 10 y) (x)
V
as long as C 2 1. Then,
liz (z, v) 2 (I, wxkk) + g( w7,h 2 f w7,h + (x),
and therefore V 2 fIx x) Cy by Assumption on the lower bounded value of f.
Now, since as - for some O, we know that
σk ok+1
O(1/k),
0k+1
and thus,
K
E
ak
| +
(11221 + |1
160
160
Olog K) 0
Σ
o
akk M
+p
T
(oR0² + toj))
k=0
Plugging the step-size rates, the right-hand side is bounded by O(log K), and thus we get the corollary.
APPENDIX G ANALYSIS FOR ALGORITHM 2
In addition to descent lemmas for Wy.k and Wr,k. also need descent lemmas for noise variances in momentum-assiste gradient estimators. We define the outer-variable gradient estimators as the following:
7 V (I k+i ( + (1 - -16) ( V f Wy.ki Ctt)
Dxy = Vag(En, Wy ct. + (1 11m)] (Tey
Vzg(EE- 1, Wyiki ctoy)
>k
9 Vag(En, Wy dt + (1 7kk (g
V Wi et
37

---

Under review as a conference paper at ICLR 2024
G.1 DESCENT LEMMA FOR NOISE VARIANCEE
We first show that noise-variances for einy and ex decay.
Lemma G.1 At every ttth iteration, the following holds:
Bille w [13] S (1 7/++1 [ 1 [1²]
21
+ ((222)) [| - 2x11 + +1| -
-| ws,
and similarly,
Billery x+ wy
1 (1 Th+1) 2 ال + 4n (o + og) + +( - ob
+ 0(g,)) (1|= - =x11 + || wy,a
Proof.
We start with
[[lett [|c [1]] = E 11 Gk++11" [[3]
= E [I((V y (T We We, cot Glitt) + 1m++1 - Vyg(EN W2nN (tos)) [11]]
(1 m)+11) 2 [Bll ]
+ [I[(V (ilVv((<++1 ws 2 c G + (1 - mk+1 1k+1) Vug(ERy wa.sr a 1)?]
where the inequality holds since gradient-oracles are unbiased:
Bi Vug(ER+1, Ws,k+ii + G F = 0,
Bl(e Vgg(k, We ( ck+1) - Gh G F = O.
The remaining part is to bound
E [IIVV W2,k+1i : G + TK+1) Vug(oks Woykt : )
< 21/ V,g(( W2,h+11 ( G [|3]
+ M E [I[VV
V Vug(ore W2, sttt)) + (G G ||]
$ 2 (12 1) (1| - xx 1| ||= wz,kl12).
Similarly, we can show the similar result for ekk Let Ghey ou+i (y + Vyg(EEK Wy.)). and we have that
E [||e
k+1 wy 112 = E I1ok+1 7k+1 + Duy - G 11]
(1 mh+1 ) Bllee wn 12] + 2( okt1) E|ll vf (I Wy chitt) Vy (z 2y
+ 2E [|[ (((VV (I &ii ( - Nohor (Ik, Wy,ii cut - (1 - mh+1) ( G
(1 7/o+1 1) 3 - 122] + 2( o2+ + 4m (0203 +
+ +0(,) (||=4+1 xx 2| + |,y,A++1 -y 113,
where we used Assumption 11 to bound
[V yyleeee (I6+11 Wy.+11 cl+1) Vylorrs (2 WhiNi 1)1?]
I M( 12 || wy
We can state a similar descent lemma for et:
Lemma G.2 At every tth iteration, the following holds:
Bllle (illet-1113 (1 m =
+ o 00)++1 001, xx
0(22) (I - Wy.A+1ll + || - ws,4+1l13
The proof follows exactly the same procedure for bounding e and thus omit the proof.
38

---

Under review as conference paper at ICLR 2024
G.2 DESCENT LEMMA Wy.ks W2,k
The strategy is again to start with (26):
||,,,4+1 "y w.ttlll ||
112 1 v. w. 112 -2(2-2220)) 2( 2g Witt+ wo
A
+
| - wy 11 + Xx
| u.
4
(16)
For bounding (ii), we can recall Lemma F.2. For bounding (1), we can slightly modify Lemma F.I.
Lemma G.3 At every k iteration, the following holds:
2 4p
Blllyy,++
B Blll
[1 + 111 (39)
Similarly, we also have that
7kk E Bl[lW,,k wi, 11 O(Hx)) [ (40)
E B 2 1
4p
Proof. We use the linear convergence of projected gradient steps. To simplify the notation, let G oxfey + Fwy + p (Wy,k yk) and G V hor (I,,, wy,k) + p + yx). Also let
G Vhor (xt, wgyk + p (wi. yx). We first check that
|yy,k+1 ".
Ily (uy,A - [x Hl {wg - T
< Wyyk 7n - (wiy G²* ||²
|| - w + 2 [ G² ||²
-27k (10. wa G G*).
Taking expectation conditioned on F& yields:
E|]l B - w x |3] S B - w [N] + REElI - Gr11115N
27 (Wy,k wyik: G G 2y ly w G C3 Fr).
Note that we have
El|i Gr < 2 GH 1 2E[ll [
Tu Bl - w G [)]
Wyy w/, 112 + (
8p
Now again using the co-coercivity of strongly convex function, since the inner minimization is (1((3))-ssroonll) convex and (1/possmooth, have
|[G 1² < (1/p) (Wy,k Wg G --C G"),
1
| wr < (iy, - wy k. G G")). 3p
Given 7 < p. and noting that G G eryy have
E Billwy,++1 " 112)
E Eillug
Wlyk
w 11 O((xp)
4p
Similar arguments can show the bound on
|[,,++11 w",ell.
In addition to the contraction of Wy,k toward the proximal operators, we will also use the following on the bounds expected movements:
Lemma G.4 At every htth iteration, the following holds:
E| B[]lwy,,++ 1y E(hor (æk, yks wy.k) hog (IFk. yos Wy.k+1) ) lltelett. 112). (41)
27k
Similarly for Wa,k. we have
1
[ B[[lwe,k+1 12 E[g( Zk, k.
g 2k, wo. ) + fle 112].
(42)
2%
39

---

Under review as a conference paper at ICLR 2024
Proof.
By 2p
-ssoothhness of hov (2,, y, w), we have
ho (Zk, yk, wy,k+1) I Nov (2 Uk. wy.k) + (V Wollor (Iks Uk. Wy.k), Wy.k1 my.k) + 1
11 - wy
Let Wk Wyyk Yio V Mor (Irk, yk: wy.k) + omyy) and thus V Valoo (Ikr yks wyyk)
74 (wyy6
wk) - -way Plugging this back, we have
hop (2R, yk wy)k+1)= I hos (Iys yki wyik) + No (Wyii Wki wy - wyyk)
(e Wy wyyk) + D
Iluyytt1 1y
hov (I yk, Wy,k)) 7i 1110y, h Wy + 7/k (2 Whe Wy,t+1 wy.k)
+ 4 (l 1== 16y% || Wy,kl 112 + || wy
By projection lemma, (wy,t+1 - Wk Wy,8+1 Wy.k) S 0. and since Yo < p. we have
hag (Ik, Mk, Wy,k+1) S hog (IR, Mke Wyyx)
27m |1 - wy + 4 11?
Arranging this, get (41). (42) be obtained similarly, and hence omit the details.
G.3 DESCENT LEMMA FOR Poopp
For simplicity, let G C Vz [ox wy,++1 + g(rk, (y,k+1) g W..++)) 1)) and G dk Gh. This part follows exactly the same Appendix F.2, yielding the similar result to (36);
x1 + 1l - wy BR (lluke
3x (112x w2 + 1| 11,2+11122)
ok (i) S
4a | 2x11-
4p
P
+ +0 (2,10xx + - (1leg wy Wybttll? + || - ws,b+1113)
+ (p (dist T( 0)) 1| 2++1ll3) + aull - G
G.4 DESCENT IN POTENTIALS
Note again that
B B|| - 2x
||Ixx { [1IIxx
an - 1Ix tzz - ax S a - 1²1
001 (og.)az((lus wy.++1ll 2 || 1 BIl 1
and also note that
|| 42+1 11 | - -xll 21
I4 x4-1
E||l - G =||]]== 11
Similarly to the proof of Appendix F.3, using Lemma F.2, (32), (36), and Lemma F44, and using step-size conditions, we obtain similar inequality to (37), with extra terms on noise-variances:
Va+1
V4 <
Okk
|
3k 16oEp
(I1e wy, + 1| - w
160
(1lyk - Ms++1 112 + ||=x~ - - 11 + (or- - ok+1) O(C,)
16 Bkp
ok
Cu
1+ Tk okt1 d O(12,) pars + 2,3
(llwii Wy 112 ||0", w2,4+1
okP
oR+1
C
Cw
(luig, - x12 12 11 w2,kl1?) 160 - 22
OkP
40

---

Under review as conference paper at ICLR 2024
+ (Cnp²)
1
|=
||
112
112
+ +0
1 1+ 11////1 + Owplail) (ax + p= 11
Ok
(1)
1
+ (Cnp²)
|c0
|| l@all??
0k+17k
Y
(1))
+ (Crp²)
(
1
1 112
l
Tk+17k
(186)
In order to bound ex term, given that
- 1+ 1../K + Cw
M
0k+17k
Cypp²
an 01-k--1)
using Lemma G.2, we have
(i) < Gnp²nk 16-1112 Cgp2. ( + +og) + +0(1, (1,,,))12xx - -2--1
0kTk-1
0
+ Cnppp ((1,))(( Wy
+ || w2,k 1l
0
Similarly, by Lemma G.I,
(i0) S Cnp-me+ |c 122+ Cnpp. (ofo) - | - xx|
-
0
0
((g,))lag,t11 2y
+ CGpp²
0b7k-1
(iit) < Cnp
+
11, xx
1/2 Cmp2.
0
ak
0 0(2,))lwa,,411
w -
+ C2,p²
0b7k-1
Now setting C, 0 and p < 1/1g,1 properly, with an < %ko can keep || negative, and have
xx 12 terms
V
V $
a3 160
|
3x
(11yk w 2 + 11 - x1
160
1|2 11 - 2 + (0x ok+1) O(C,)
Mk++ (llyk
160 3kp
ox
Cu
0k Tkt1 d O(12,1) )axx + 2
1+
(Ilwii Wy 112 1/ -2,b41113
okP
ok+1
Ow
Cv
(1wii - -wy,xl 2 + || 22 320 || - -x+1111 0(22(32))
|| - x x
OkP
CapL (llc/ey) |1
|10y,++1 - Wy 112 + || - wz, 1|2
[|=) 113)+
C,0(pp?2,))
Tk
+ Cnp² 0 (0 + oz)) + ollkk)
Given that
Mc+1 >> (
41

---

Under review as conference paper at ICLR 2024
using Lemma G.4, can manipulate
||wy,,+11 Wy.k and [ss,+11 W2,k terms to be bounded by
8x (11yk wiin 1 1| - x2,)
V k++
v v
|4
160
160
yk+1 112 1|2 - 2k+2113) (ox ok+1) O(C,)
(lyyk
160x 3kP
ok
C
1+
ok okt1
d O 01121)pax )pre + +33x
(Ilwi Wy 112 |1 -22b++11²))
okp
xk+1
Cw
Cv
|| - -x++1ll + 0
(1lig, - wy,xk? + |1 w2,
1 112
okp
320
-
Cap-TI-! (llehop12 1/2++ + 11<==113) + Cup (1h+11)
(0207 og)) + (((l/k)
2017k-1
C,0(p212
how (Ikk, Uk, Wyyk) - Naw (rks Uk, wy.k+1) + g( 2k, W2, - g( 2k- w2,++1)
Ok
(10)
(0)
(43)
To proceed, we note that
(iv) = (hon (Iks ye wiy.k) - li . (I 9k)) - (hon (I yks Wy 11 p (a We))
= (hoz (Ik, yes wyyck) ti sp (Ihs 3k)) - (hox (I 1, Mk+1, Wy.h+1) ) - ho
(T (o
1b+1))
+ hor (I&+1, 1k+11 Wy(k+1) (
(T&+1 1x+1)) - (foz (I ykr Wy - ti oo (Kks 8k
(a)
and the term (a) is bounded as
(a) I (V (hou (Kk, Me: wy,k+1) 11 - 11 hou,p (ou,p(ze (28, y/ y2)); Tk+1 - xR) + lg.1 |x++1 - xxll
+ (V (hon (IK, ybs wy.++1) - h p (2k, )) Uk+1 yk) + 11 11
(hor (#R, (y.k+1) hos (Ix, ( Ib+t m&m 1g.1 1 [x xx
+ p ((y) Wy,k+1) - (y) wy wy;)) 3k++1 - yk) + p ||y 1 - y/ 12
||0++1 2/ 11 + 16,3
S 3212 ark [.g - x1 + 128ax
| w
64 1l 11.112
Thus, we can conclude that
(iv) < (horg, (Jik yh, Wy,k) Nor, (JoK, yk))
(borg
(ITK+1 1o Wy,k+1) 1) 1o (2 21
1
+ 32/2 [[y
w +
||:2-411 xxx11
128a
16 + p
1
[yykt+1
w 112
1bk+1
8/
64,3pp
Similarly, we have
(v) S (g(xN, zk, Wa 26 (x 2x))
(g(0x41, (1112+1524+1,,200 (,,,1W D (Tx+11 2x41))
+ 32/2 2 100 (0 w 11
||04111 xxll?
128Cr
+ 1638 || wi 11
|| - 12.
648kp
Now plugging this back, we have reduced (43) to
V k+1
V/
aj
2
8x (1
w1 + 1| - W.,u'l""
160
160
42

---

Under review as conference paper at ICLR 2024
(ox: - ok+1) 0(C,)
(11yk Mo+1ll
1|2x
2x+11
32 3&P
Ok
C
ok oct1 dv 100,10)ax + 011,3s
1 1+
(llwgi Wy,k+1ll
11w0 W2,k+11] 113)
okp
ox+1
Cx
Cw (llungh - wy,k0? + 11 w2,kll²) - 64TRa
((02(g,1)
|| - xb+1ll2+
1|000-100 - 1006-xk-111 112
okp
Cap ((1Cin 112 + 11 + Cup (1R++1)
(0207 +o²) + ((1/k)
2017k-1
ONT
Nox (I yk wyik) - -o (Iks 8k)
haz (IR+1, 4k+1, wy, - 1i up (xx+1 yk+11)
(,,0(),))))
Ok 2k, Zk, wx (Fk, 2x)
O g( 26+1, W2 9 ( ah+1))
+ +,,0(02gg,)
Ok
0
(44)
Now applying Lemma G.3, along with
O(gaa)ax + (Ba))
7h 4p
As
C..
and
Cwe A
Cun
m 1
C
P
4C,pp2'
we can further bound (44) by
Vk+1
V
8x
(11y w/ + 11zx 11
160
160up
1
O (,11
(11yk 1/++1l 112 1|=x =x+1l1?) 64
|:086 - xx+1l1
xx xk-1 112
BuP
0x
(ak Ok+1) .O(C,) + C.pp Olthtta) (020} + og) + o(1//)
OF
T
Cw.s 160xp (Ilwi
Wy.kkl + 11 x Wz,k l12)
hoo (IKs yk: wy,k) - 1 n (x Uk) how (I Uk+1, Wy.k+1) 1: (2 2k+1)
Tb (g( W2,h) (Fk: g( 2641, w2 - 2 (1
Tk
+ +c,0((212,))
σk
(45)
G.5 PROOF OF THEOREM C.4
Summing the bound (45) for k = 0 K - 1, cancel out || Fx+1
terms given that
0(p22_))ax <
Okk ak+1
Yk-
Leaving only relevant terms the final bound, we get
WK
Vo
<
K-1
ak
||
3k
(llv wi + 11 - w2xx
160
16oxp
0=
43

---

Under review as conference paper at ICLR 2024
0h - ok+1) O(C,) + C O(nh+t) (o + 0z))
Ok
CioAe (1rogix 2y + ||w5 122kk1?))
1600.p (T1oosp
(Now (IrR) yks wyyk)
(uas uk) + glak, 2k; w2,k) 9 (25ks zx))
xk+1
Ok
Non (Fu,, (To, you wg.u) h hoo (oo. Mo) nox (IK, K yKs Wy.k) n/ (I yK
+ +,,0022)))
00
OK-1
(0(20:00 [((0, 20, 20, w.,0) - 97 (20. 20)
O(0K,2K, W,,K) 9 (T(
+ +C,0(022g,)
d0
ØK-1
where the last two lines come from the telescoping sum. Note that
hox (IK, YK, Wy,k) k (ZK, yx) 2 0,
g(zK. 2K, we.k) 9 (2K K 2x) 2 0,
by definition, and furthermore, hov (Ike yke Wy.k) hr (Tkk 4k) V (Vohoz (2k, yk wyit)) Wy,k wy g Tho we,)) (1k 2k) (ang(Ek 2k, w(,)), W2,k w
Here rely Assumption 12 (along with y being compact) to bound them: hog (Ik, yk. wyyk) h (Ik, y&) I Mw Wey, wy k ll g( 2k, Ws,k) Sp (Ik, S Mw 1|,,, w l.
Plugging this back, and using axx br S
8² 4a
we have
Bx
VK Vo
|
(llyk wy + 1122 - xx?)
160k
16
MMIM
[o -k+1)++1
-O(C,) + Crpp² 0(T++t) (0203 + oî))
ORT
O(ME)
Tk -
Th-1
Bho (wo, yo, wy.0)
1: (10. Ho)
g 2o, w2,0) 3 (10, z0)
C,,((p?(.)))
0n
60
Note that Wy.0 = 30, Ws,0 = 20. and thus hoo (xo, yo: wy,o)
(2o vo). Ws.0)
g(Eo, 20). Arranging the terms, we have the theorem.
G.6 PROoF OF COROLLARY C.5
The proof is almost identical to the proof of Corollary C.2 in Appendix F.4, and thus we omit the proof.
APPENDIX H Proofs OF AUXILIARY LEMMAS
H.1 PROOF OF LEMMA 3.6
The Lemma essentially follows the proof of Proposition in Shen & Chen (2023). It to show the
local Lipschitz-continitty of solution-sets. For every #2 E X' such that ||>| x2l E cxpó 1
44

---

Under review as conference paper at ICLR 2024
and 01 02l copó//Loo with sufficiently small constants Cz. Co 0, let Y1 T(21, σ1) and
y = prox, phoz (x2:) (31). Note that y1 = prox phay (m))) By Lemma D.3 and Lemma D.4,
11 71 = prox pho (mn (11) prox (oo.
< (ppl, - x2ll + O 01 021 - pó.
Thus, p-1 1/1
prox
phoz (m2.) (11))(111 6, and applying Assumption 1,
dist(y1, (222 02)) S (0(4,)) x2ll 0(4 - -
proving the (local) 0(1g.1/1) continuity in z and 0(4yo//)-Lipssthhin continuity in of T(z,0).
H.2
PROOF OF LEMMA B.1
Proof. By Danskin's theorem (Theorem D.1), if Vhg and Vg* (x) exist, then they are given by
(x) = Vaho w Vg (a) = Vag(z, w"),
for any wt T(z,o), w E [(x, 0). Let w pro (-)("))))))))))))) w
prox proxpola- ,)(2)) By
Assumption 1, there exists o T(x σ) that satisfies
ac 2 p 11 w/ll 2 mlly" - w ll.
and thus 11y* - w/ S -. Similarly, -|=- - w01 _. Therefore, we have
V Voho (x","") y²) v V (x, wg) + V - Vag(z", w=))
| Wettoo" v',",""""") 2"", V (x")1|
0.1 (1ly* will + || w²ll) 5
21
1
To bound the projection error, note that
IIx fx (Voo(=") 1Ix fx" pV ( v >1 | (,","²²²" (eo(2*)] 5 21 e,
by non-expansiveness of projection operators. Thus,
1 || 11 {x" (V S (1+ 2/,1
concluding that x² is Oct)sttaty point of (t).
The second part comes from the mean-value theorem: by the assumption, there exists o' E [0, a] such that
0, -,,((x,)
32
V (x)
1(.,
Oxdo 1(x, o').
doox
We also assumed I,, Lipschitz continuity of second cross- partial derivatives, and thus
8²
2² Ordo
Oxdo 1(x,0')
1(x, 0)
s Loo' s Loo
which implies || (x) Vxb(x)] < Looo. Using similar projection non-expansiveness argument, we can show that
1
| 11x fx (Vb(2))1 (1 2lg,1/H) Loo,
0
concluding the proof.
45

---

Under review as conference paper at ICLR 2024
H.3
PROOF or LEMMA D.3
Proof.
Note that
prox pg(ar,,) (y1)
prox pa(a)))) (12) I prox pg( (v1)
prox pg(aa.)) (311 )l
prox pg( (y1) prox po(#2.)) (U2))l-
Due non-expansiveness of proximal operators, the second term is less than | y2ll- For bounding the first term, define
wi- prox pg(21.)) (0))))))())) (v1)
arg min ((1 w)
2p || y/ vill?
yEy
3 = prox pg( (81) arg min yE>
( w)
2p ||w y1ll².
Due to the optimality condition, for any p/ 4, we can check that
wi lly (wi 3 v (2), wi) p- (w] -1))
On the other hand, define w' = y { [ - (VV (12, wi) + (w )1) This is one projected gradient-descon step (PGD) for finding wi started from wí. By the linear convergence PGD for strongly convex functions over convex domain Bubeck et al. (2015), since the inner function is -ttop)ytyrongly convex and 1/ /msoohhh by choosing proper p. we have
1|w0 - will S
10 |lo w/ll.
Thus,
|| - will
| w/ll || 110 - wwll
[|Ty [w] - ((Vogla wif + x (w] mn)) - Hy [wi WF(( + +p- p-'(wi - y1 ))}
[ will
10
9 Ilwi w
V wt) v Vyg(oz, w 11
10
9
(,300,.1) | 22/1 +
| will-
10
where the third inequality we used non-expansive property of projection onto convex sets. Arranging the term and plug B = 0/4, we get
[ -w:l O (pl..1) || x211-
H.4 PROOF OF LEMMA D.4
Proof. Again, let wi prox (m.) (v) and wi prox phin (x.,) Using similar arguments to the proof in Appendix H.3, we have
9
|
w S B V hor (x, wi) V Vylos (2r, wr)) [ef)]l+
||w] w/g
10
B| V ( w() 02 V (20 w
|
w ||-
10
where 3 = p/4. Arranging terms and using V willl S Iy.0. get the lemma.
H.5
PROOF OF LEMMA D.5
Proof. By Lemma D.3, we know that the solution of min ho (x, w) + 2p ll y/1 is Oplg..)
Lipschitz-comtinuuus in æ and 1 LLpschitz-continnn in y. Therefore by Lemma D. D.2, since the inner minimization problem is ---moohh,, h² (2. y) is -smooot..
46


Reviews:
[{"review_id": "PM2vh0X3f2", "reviewer": "Reviewer_VYCb", "summary": "This paper addresses bilevel optimization problems that can encompass constraints and nonconvex lower-level problems. It establishes an $O(\\sigma)$-closeness relationship between the hyper-objective $\\psi(x)$ and the penalized hyper-objective $\\psi_{\\sigma}(x)$ under the proximal-error bound condition when the errors are small. Using the penalty formulation, the authors develop fully first-order stochastic algorithms for finding a stationary point of $\\psi_{\\sigma}(x)$ with comprehensive non-asymptotic convergence guarantees.", "questions": "Q1. What is the relationship between the $\\epsilon$-stationary point of $\\psi_{\\sigma}(x)$ and the $\\epsilon$-KKT solution of the constrained single-level problem $P_{\\mathrm{con}}$? Theorem E.5 establishes a one-directional relation. Is the converse of Theorem E.5 also valid? Note that in Theorem E.5, the $\\epsilon$-KKT solution of $P_{\\mathrm{con}}$ should be a pair $(x, y)$.\n\nQ2. Could the requirement of boundedness for $\\max_{x\\in\\mathcal{X},y\\in\\mathcal{Y}} |f(x,y)|=O(1)$ be relaxed or made less restrictive?\n\nMinor Comments:\n\n(1)On page 3, Theorem 1: It would be beneficial to clarify the meaning of $y^*(\\sigma)$.\n\n(2)On page 4, Assumption 3: Is it redundant to consider the coercivity of both $f(x,y)$ and $g(x,y)$ as $|y|\\rightarrow\\infty$, given that $\\mathcal{Y}$ is bounded according to Assumption 4?\n\n(3)On page 7, Definition 7: Does $\\lambda_{\\mathcal{I}}$ implicitely depend on $y$ in Equation (8)? What is the domain of $\\mathcal{L}_{\\mathcal{I}}$?\n\n(4)On page 7, Equation (9): There is a period missing at the end of Equation (9).\n\n(5)On page 9, Assumption 8: Does Assumption 8 implicitly assume that the active set does not change?\n\n(6)On page 17, Equation (13): There is a period missing at the end of Equation (13).\n\n(7)On page 18: check the definition of $g_{xy}^{k,m}$ and $g_{xz}^{k,m}$.\n\n(8)On page 19, C.1, Definition of $\\Delta_k^z$: “$\\rho g(x, \\cdot)$” should be “$\\rho g(x_k, \\cdot)$”.\n\n(9)On page 22, Equation (21): “$D_v \\ell^*(x)$” should be “$D_v \\ell^*(w)$”.\n\n(10)On page 27, Proof of Theorem 3.6, Line 8 from below: Should $\\sigma C_f$ be replaced with $2\\sigma C_f$?\n\n(11)On page 27, Proof of Theorem 3.6, Line 4 from below: $\\mu_g$ should be replaced with $\\mu$.\n\n(12)On page 30, Proof of Theorem E.5: It appears that in the last step of the proof, $g(x,y) - g^*(x)$ is bounded by $O(\\sigma^2)$. Would this observation be useful for improving the convergence rate?\n\n(13)On page 30, Equation (28): There is a period missing at the end of Equation (28).", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "S1. The work is well motivated. Finding a simple yet effective method for large-scale lower-level constrained bilevel optimization problems is both intriguing and significant.  \n\nS2. The paper is well written and easy to follow. The illustrations in Example 1 and Example 2 are helpful in understanding the main difficulties.\n\nS3. The algorithm design is novel, suitable for a broader range of bilevel optimization problems that may involve constraints and nonconvex lower-level problems. Additionally, it provides a comprehensive non-asymptotic convergence analysis.", "weaknesses": "W1. I find the algorithm developed in this paper to be both interesting and important. It seems that the landscape analysis section is quite lengthy. Would it be possible to condense the content and incorporate the first-order algorithm into the main text?\n\nW2. There is a closely related paper that addresses general constrained bilevel optimization problems while assuming the strong convexity of the lower-level objective.\n\n[1]Siyuan Xu, Minghui Zhu. “Efficient Gradient Approximation Method for Constrained Bilevel Optimization.” AAAI 2023.\n\nW3. No numerical experiments are provided.", "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": "", "extra_scores": {}}, {"review_id": "FXZ9LoEc2b", "reviewer": "Reviewer_fS1u", "summary": "The paper discusses the extension of first order methods from bilevel optimisation problems with convex objective to bilevel optimisation problems with non convex objectives", "questions": "A couple of typos:\n\n- Section 3.3. first line: “via finite differentation” —> “via finite differentiation” \n- Section 3.3. “we can apply mean-value theorem” —> “we can apply the mean value theorem”\n- If you check, on both page 3 (below Assumption 1) and page 8, you use the sentence “the crux of assumption 1 is the guaranteed (Lipschitz) continuity of solution sets”\n- Page 8: “With a more standard assumption on the uniqueness of the lower-level solution and the invertability ” —> “invertibility” ?\n\n\n\nPage 1/2\n- You first introduce formuation (P) then you introduce formulation P_con which to me is exactly equivalent to P, isn’t it ? If it is, I would not relabel it but simply emphasize the equivalence between P and this formulation. There are already many formulations. If some of those are exactly equivalent (like I suspect it is the case for P and Pcon, I would not introduce additional notations)\n-  Finally you introduce a relaxation of the constraint in P_pen. intuitively, we understand that for sigma small enough, this relaxation should recover P_con and this is what you formalize by introducing appropriate conditions. So far, this is clear. What I find less clear is the sentence “Although finding the solution of (Ppen) is a more familiar task than solving (P) ”. For small \\sigma, from Theorem 1.1., there must be some conservation of difficulty (at least for some \\sigma). It would be helpful to have some more intuition on that (one or two sentences). I.e. it seems miraculous to end up with a formulation that suddenly becomes so much easier so solve. \n\nPage 2\n- In the formulation P_{pen}, I don’t really understand how you can know the value of min_z  g(x, z) while you don’t have any explicit solution for min_y g(x, y). This should be commented\n\nPage 3\n- The result of Theorem 1 is clearly interesting but it could be expected that a smaller value of sigma would enforce more weight on the penalty and hence ultimately recover the solution to (1)\n- You should define the notion of epsilon-stationnary point. In particular What is the meaning of epsilon in regard to sigma. When you introduce the notion of epsilon-solution you seem to replace the sigma in psi_sigma by the epsillon, but then the two appear simultaneously when discussing the oracle complexity\n- You use the terms “complexity” and “oracle complexity” before clearly defining them. Are you talking about the number of iterations/steps? If yes, this should appear somewhere. The notion of “oracle complexity” is also used in a number of different settings. What are the oracles you are referring to ? What function classes are you considering. This is not self contained (at least on page 3). I can see you clarify this in the statement of Theorem 1.2. but it should appear earlier. In fact I’m wondering if you should not put Theorem 1.2 before Theorem 1.1. Also, is your oracle only given by the noisy/stochastic gradient or do you also assume access to the value of the function? The information that appear in section 3.4. should appear way earlier. \n- What do you mean by the sentence “Assumption 1 holds only in a neighborhood of the lower-level solution ” ? do you mean that Theorem 1.1. only requires Assumption 1 to hold in a neighborhood of y^* ? Then you should clarify this in the statement of Theorem 1. \n\nPage 4\n- You mention the mean-squared smoothness condition before defining it. Either include it in the main part of the paper or remove the second part of the Theorem. The sentence “fully single-loop manner” is also unclear so I would be in favor of removing the second part of the Theorem (at least from the main body of the paper)\n\nPage 5\n- Why not use V for the value function and Y for the solution set ?\n- In section 3, we don’t really understand what you are doing\n- I think you can spare some space by removing the definition of Lipschitz continuity from the main body of the paper (this is a relatively well known concept and it would free some space for some other (perhaps more crucial) explanations — see my other comments)\n\nPage 6\n- I would be in favor of a couple of additional explanatory sentences in Examples 1 and 2. E.g. just clarify the definition of S(x), i.e. S = {-1,1} except at 0 where it is the whole [-1,1] interval, or recall the definitions of S and psi\n- The whole introduction in section 3 is confusing. It is not really clear what you are trying to do do until the last sentences. I.e. we understand you want to show examples in which \\nabla \\psi(x) \\neq \\lim_{\\sigma\\rightarrow 0} \\nabla \\psi_{\\sigma}(x). But it is not completely clear why, especially given that you seem to already have introduced in assumption 1, a condition that ensures that \\nabla \\psi_{\\sigma} can be made arbitrarily close to \\nabla \\psi. \n- Under example 2, when you mention the continuity of the solution set. Do you mean continuity with respect to x ? \n- Before introducing examples 1 and 2, I would add a sentence insisting on the fact that in both examples, the non existence of $\\nabla \\psi$ comes from the discontinuity in $\\psi$. Also I known you don’t have much space but it would help to have a plot of the solution sets for both examples (or perhaps briefly mention the solution sets for both cases ? This would help clarify the fact that the set is )\n\nPage 7\n- Although technically correct, the term “kernel” in the setence “the kernel space of the Hessian …” before Theorem 3.2. can be confusing especially in ML related papers. I would use nullspace instead of kernel space.\n- The central part of section 3, i.e. the part that connects this section to Theorem 1.1. is Theorem 3.2. This theorem should appear way earlier or at least you should clearly explain that you derive the conditions appearing in Theorem 1.1. I would rewrite section 3 as follows. Start by clearly indicating that you will derive conditions for the second relation in Theorem 1.1. to hold (i.e. the fact that \\nabla \\psi_{\\sigma}(x) is a O(\\sigma) approximation of \\nabla \\psi)\n- I would rewrite section 3.1. by giving more intuition on how you derive assumption 6. Just a couple sentences of explanation. (I think readability of the paper would benefit from for example, removing the definition of Lipschitz continuity and replacing it with a more elaborate explanation of the derivation of assumption 6)\n- I would remove Proposition 3.1 or I would make it simpler. The proposition is not clear and neither is its connection to the rest of the paper or its explanation (i.e. Geometrically speaking, perturbations in … ). \n\nPage 8\n- I would simplify section 3.3.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The abstract is neat and the paper is dense and well written. The problem is clearly stated and there is a need for a solution which the authors provide.", "weaknesses": "I would be more straightforward and from the very beginning of the paper emphasize the narrative. My main concern has to do with the fact that the paper might be too dense for a conference. You either have to make it simpler/lighter or you should submit it to a journal. There does not seem to be enough space for you to give the complete details, or if you prefer, we miss some intuitive explanation (i.e there are too many details and the main thread is not always clear). Before providing formal statements, you should be able to explain in simple terms what the main ideas are (e.g. for Proposition 3.1.).  At this point, it appears as if you had a very detailed result and quickly tried to wrap it up as a conference paper.  You took some of the details and put some others in the appendices, but the general organization (the decision of retaining some results instead of others, such as Proposition 3.1) is unclear.. I would be in favor of reducing the amount of mathematical details (see my detailed comments below) and increasing intuitive explanations (at least in the main body of the paper).  You could do a much better job at focusing on your main results. An example of this is section 3 where the reader has to wait the very end of the section to discover the connection to the earlier sections (see my comments below).", "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": "", "extra_scores": {}}, {"review_id": "DGdDHvJ5YD", "reviewer": "Reviewer_ocU5", "summary": "This work studies a penalty method for constrained bilevel optimization, where the objective functions are possibly nonconvex in both levels with closed convex constraint sets. While the penalty technique is not new, its landscape relationship with the original problem was not known. This paper, for the first time, characterizes the conditions under which the value and derivatives of the penalty function is $O(\\sigma)$ close to those of the hyperobjective function of the original problem, making the penalty method more useful theoretically. This paper then suggests efficient (stochastic) first-order methods for finding an $\\epsilon$-stationary solution, by optimizing the penalty formulation with $\\sigma = O(\\epsilon)$. In particular, under the small-error proximal error-bound (EB) condition, that is closely related to the PL condition, the proposed algorithm finds an $\\epsilon$-stationary solution in total $O(\\epsilon^{-7})$ oracle accesses, which is better than the existing method for a relatively easier PL optimization.", "questions": "1. Title: What do you mean by \"first-order stochastic approximation\"?\n2. Page 2: The third paragraph states that there are results under the uniform PL condition, which seemed to imply that there is a method for the PL condition, but the next paragraph claims that there is no algorithm finding the stationary point under the PL condition. Could you clarify this?\n3. Page 2: In the fourth paragraph, how about making the term \"landscape\" more specific? It was not clear to me here, although it becomes clearer later. \n4. Page 3: How about adding \"small-error\" in front of the \"proximal EB\"?\n5. Page 3: It is implied that Assumption 1 guarantees the local Lipschitz continuity of solution sets (Assumption 5), but it seems that it is not explicitly stated (with proof) anywhere. \n6. Page 3: PL and proximal EB conditions are almost identical, and you only assume the proximal EB within the neighborhood of solutions. Then, how were you able to get an improved rate over existing rate for the PL condition? Most of the explanations of the algorithm are deferred to the appendix, and it was not clear for what reason that the proposed algorithm is more efficient even with weaker condition. Could you comment on this?\n7. Page 7: How does Assumption 6 help the active set to not change much?\n8. Page 7: I was not able to follow Proposition 3.1 and its corresponding explanation. Could you help me better understand the context?\n9. Page 9: Can Theorem 3.6 be proven with Assumption 5 rather than Assumption 1?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides a theoretical justification of using the penalty method for bilevel optimization, which is not trivial as seen from Examples 1 and 2. In particular, this paper found minimal(?) conditions, Assumptions 1-4 and 7-8, to show that the value and derivatives of the penalty function are $O(\\sigma)$ close to those of the hyperobjective function of the original problem, which is certainly not trivial.\n\n2. Under the proximal EB condition, this paper presents a (stochastic) first-order method for efficiently finding an $O(\\epsilon)$-stationary solution of the penalty (saddle-point) problem, which is also an $O(\\epsilon)$-stationary solution of the original problem by the previous argument. This result is interesting as its rate improves upon that of the existing method for a similar PL saddle-point problem.\n\n3. This paper provides the first explicit formula of the gradient of the hyperobjective function of the bilevel optimization with multiple solutions for the lower-level problem (under Assumptions 5-6).", "weaknesses": "1. Although the authors claim that they use nearly minimal conditions, they are not few, not simple, and are not guaranteed to satisfy in practice. (Providing an example satisfying those minimal conditions could be useful.)\n\n2. This paper becomes difficult to read towards the end, probably due to the page limit.", "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": "", "extra_scores": {}}, {"review_id": "Dwkv3KIoG2", "reviewer": "Reviewer_dzvn", "summary": "The paper analyzes bi-level stochastic optimization problems where the objectives on both levels are smooth but not necessarily convex.\nThe paper proves a connection between solutions of a penalized reformulation of the problem to solutions of the original objective. Based on this, the authors provide a first-order algorithm with a non-asymptotic guarantee.", "questions": "- Assumption 1: Was this assumption considered in previous work?\nMoreover, the quantifiers are unclear: \"satisfies (4) for all $y$ that satisfies... with some positive $\\mu,\\delta,\\sigma_0$\". Do you mean that  there exist $\\mu,\\delta,\\sigma_0$ so that $y$ satisfies... *implies* (4)? This should be properly revised.\n- Assumption 3 vs. 4: It is assumed that $f,g\\to\\infty$ as $\\|y\\|\\to\\infty$, but then that $\\|y\\|\\leq O(1)$. Why aren't these in contradiction to one another?\n- Assumptions 5-8: As previously mentioned, can the authors elaborate on these assumptions? They are not well-enough motivated. Statements such as \"Assumption 6 helps ensure that the active set does not change when ... is perturbed slightly\" seems to suggest the desired consequence is almost assumed in the first place. Also, in particular, is Assumption 7.1 standard? It seems strong, and I am not aware of such an assumption in previous works (I may be wrong, though would like the authors to clarify).\n- High-level remark: I am not sure whether the authors decision do defer the entire algorithmic aspect of the paper to the appendix is preferable. Of course I acknowledge the strict page quota, and this may be inevitable in a lengthy work such as this, but it seems unsatisfactory that the only result mentioned in the main text is Theorem 3.6, which remains rather un-motivated without the algorithmic contribution. This becomes most clear in the conclusion, when the authors mention that their algorithm is simple, general, useful etc., though the reader did not encounter it at all in the main text. For the author's consideration.\n\nminor comments:\n- 1st paragraph after (P): \"continuously differentiable *and* smooth\" - are these synonymous?\n- \"since this issue is fundamental\" - this phrasing is unclear, I suggest explaining what this means (possibly informally).\n- Throughout the paper only \\citet is used, while \\citep is more adequate whenever the work is not part of the sentence.\n- Theorem 1.1 (Informal): the phrase \"at least one sufficiently regular solution path exists\" is unclear at this point. What is even a solution path (not previously mentioned or defined)?\n- mean squared smoothness condition mentioned without definition or ref. For example, the authors can add \"(as formally defined in Section ...)\".\n- typo: to appendix = to the appendix.\n- Assumption 2 involves a norm, which only later on (in the notation paragraph) is explained to be the operator norm. This should be clarified beforehand.\n- The normal cone is mentioned without definition, I suggest adding a brief reminder (even in a footnote, for example).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Though I am not an expert on bilevel programming, the contribution seems solid and of significance.\nThe authors clearly situate the results with respect to previous work on the topic.\nThe paper is fairly well-written, and pretty easy to follow with most relevant details reminded and cited adequately.", "weaknesses": "The main weakness in my opinion is the sheer amount of assumptions made throughout the paper. While some are standard and minor, some seem to highly hint towards the desired results - especially Assumption 5-8. As a non-expert on the topic, I find it hard to assess whether the assumptions are indeed (approximately) minimal for the results to hold, and how standard they are in this field. They are somewhat unmotivated in my opinion, and possibly ad-hoc.\nThe authors should attempt at explaining why these assumptions are required, and moreover that the results do not simply follow from them in a relatively-trivial manner.", "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": "", "extra_scores": {}}, {"review_id": "8xx2nDpb15", "reviewer": "Reviewer_vCGE", "summary": "This paper studies a class of bilevel problems with a class of nonconvex lower-level problems. It establishes a strong connection between the landscape of the penalty reformulation and the original problem. This gives an interesting explanation about why the penalty method works even with nonconvex lower-level functions. Based on this, a single-loop stochastic first-order algorithm is proposed.", "questions": "1. Prop 3.1. How to get Prop. 3.1 from Thm. E.3? How does the additional ${\\rm Span}(\\,...\\,, \\nabla_y f(x,y^*))$ appear?\n2. Thm. 3.2. Can we derive the explicit form of $\\nabla \\psi(x)$? Or we can only define it implicitly as the limit of $\\nabla \\psi_{\\sigma}(x)$ when  ${\\sigma \\rightarrow 0^+}$?\n3.  Appendix E.6. Proof of Thm. 3.6. After \"Then, since we have Assumption 1, we get\", why we have $2 (g(x,y_{\\sigma}^*) - g(x,z_p^*)) \\ge \\mu \\Vert y_{\\sigma}^* - z_p^* \\Vert^2$. It seems like the QG condition in Karimi et al. (2016), but it seems like this reference only shows that it can be implied by the PL condition in the unconstrained case. But how we can get this in the constrained case? \n4.  Proof of Thm. E.3 in Appendix. Why we always have $\\Omega(\\delta) v = \\nabla^2_{\\theta w} f(w,\\theta^\\ast) {\\rm d}w$? What if $\\nabla_{\\theta w}^2 f(w,\\theta^\\ast)$ is zero, then the RHS is also zero?\n5.  Appendix B.2. Can the authors explain more about the necessity of using the Moreau envelope? What is the benefit of using the Moreau smoothing? What will happen if it is not used? Sorry, I don't fully understand the technical challenge 1. Why it fails if one simply estimate the value of $(\\lambda^*,\\nu^*,y^*)$ for a given $x$ and plug into the expression of $\\nabla \\psi_{\\sigma}(x)$ in Thm. 3.2?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. I found Thm. 3.2 very interesting. It converts the differentiability problem of $\\nabla \\psi(x)$ into the problem of whether the partial derivative of $l(x,\\sigma)$ is commutable. It solves the open problem that was not solved by Chen et al. (2023b), Shen & Chen (2023), and  Arbel & Mairal (2022) in an elegant way.\n2. The algorithm works for the stochastic case, which is not analyzed in Chen et al. (2023b), Shen & Chen (2023), and  Arbel & Mairal (2022).", "weaknesses": "1. (minor) The readability of the proof is not very good, with some typos. An incomplete list：\n*  Page 24: \"perturbations in $x,y,\\sigma$ can change gradients of Lagrangian only by order $O(\\delta)$ \". It seems that from the context $x,y,\\sigma$ should be $\\theta,w$.\n*  Page 24: After \"Next, we check that...\". It seems that $y^*$ in the second line should be $\\theta^*$.\n*  Page 26: After \"We list a few properties of...\". It seems $\\theta_0$ in the second line should be $y_0$.\n*  Page 26: After \"where we use ...\" and before \"continuity of \". It seems that $z_t^*$ should be $y_t^*$.\n\n2. (minor) Assumption 6, 7(1), 8 may not be easily verified in practice. But given their natural appearance in the proof, i think this point does not detract from the main contribution of this paper.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)