SLM: A Smoothed First-Order Lagrangian Method for Structured Constrained Nonconvex Optimization
Authors: Songtao Lu
Venue: NeurIPS 2023 poster (2023)
Keywords: Functional constrained optimization
bilevel optimization
primal dual method
Lagrangian method

Abstract: Functional constrained optimization (FCO) has emerged as a powerful tool for solving various machine learning problems. However, with the rapid increase in applications of neural networks in recent years, it has become apparent that both the objective and constraints often involve nonconvex functions, which poses significant challenges in obtaining high-quality solutions. In this work, we focus on a class of nonconvex FCO problems with nonconvex constraints, where the two optimization variables are nonlinearly coupled in the inequality constraint. Leveraging the primal-dual optimization framework, we propose a smoothed first-order Lagrangian method (SLM) for solving this class of problems. We establish the theoretical convergence guarantees of SLM to the Karush-Kuhn-Tucker (KKT) solutions through quantifying dual error bounds. By establishing connections between this structured FCO and equilibrium-constrained nonconvex problems (also known as bilevel optimization), we apply the proposed SLM to tackle bilevel optimization oriented problems where the lower-level problem is nonconvex. Numerical results obtained from both toy examples and hyper-data cleaning problems demonstrate the superiority of SLM compared to benchmark methods.

SLM: A Smoothed First-Order Lagrangian Method for Structured Constrained Nonconvex Optimization
Songtao Lu
IBM Research, Thomas J. Watson Research Center Yorktown Heights, NY 10598 songtaoßibm.com com
Abstract
Functional constrained optimization (FCO) has emerged as powerful tool for solving various machine learning problems. However, with the rapid increase applications of neural networks in recent years, it has become apparent that both the objective and constraints often involve nonconvex functions, which poses sig- nificant challenges in obtaining high-quality solutions. In this work, we focus a class of nonconvex FCO problems with nonconvex constraints, where the two optimization variables nonlinearly coupled in the inequality constraint. Lever- aging the primal-dual optimization framework, we propose a smoothed first-order Lagrangian method (SLM) for solving this class of problems. We establish the theoretical convergence guarantees SLM to the Karush-Kuhn-Tuuceh Kuhn-Tucker (KKT) solutions through quantifying dual error bounds. By establishing connections be- tween this structured FCO and equilibriun-constrainee nonconvex problems (also known bilevel optimization), we apply the proposed SLM tackle bilevel opti- mization oriented problems where the lower-level problem is nonconvex. Numer- ical results obtained from both toy examples and hyper-data cleaning problems demonstrate the superiority of SLM compared to benchmark methods.
Introduction
In this paper, we consider a structured constrained optimization framework that has broad applica- tions in diverse machine learning problems. The goal of this problem is to minimize the objective function using two blocks optimization variables which are coupled in the functional constraint. More formally, express this class of nonlinear constrained programming problems as follows:
min f(x v). s.t. g( - (xxx) 5 =EX.y
where feasible set X' is convex and compact, the objective function f(z y) is smooth and noncon- vex, constraint gax, y) is smooth and nonconvex and it also satisfies the Polyak-Lojasiewit (PL. condition with respect (w.rt.) y, g" (x) A miny g(x, y) (which also called value function [1]) obtained by minimizing g(z, over y, and constant 8 > O.
When d O, problem (I) reduces to the classic bilevel optimization (BO) problem (aka mathemati- cal programs with equilibrium constraints [2]). More specifically, it takes the form of
min (a. =EX,y
y S(x) A arg min g(2, v/),
where y(x and g(x.,)) denote the upper-level (UL) and lower-level (LL.) objective functions, S(x) represents the set that contains the global optimal solutions of the LL problem w.r.t. the block- v'. This BO formulation has been shown be useful framework for modeling various multi-task
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table I: Comparison of existing related representative works nonconvex functional constrained and/or bilevel optimization, where non singleton: the existence of multiple global optimal solutions the LL problem. oracle: requirements of accessing first-order and/or second-orde derivative of either UL or LL loss functions, LL/C: the property that the LL objective funciton/constraint satisfies in problem (2) or (I), Ó: denotes that the iteration complexity hides the dependence on the hyperparameters, c.g., 6, cvx: convex, nevx; nonconvex,
scvx: strongly convex.
Algorithms
Problem
Opt. Framework
Oracle
Non- Mon--Siglctoo
LL/C
Rate
ConEx [12]
primal-dual
first-order
O
ITD/AID [13]
(2)
ITD/AID
second-order
SCVX
F'SA [14]
(2)
penalty
first-order
SCVX
1
3/2
1
BOME [15]
(2)
penalty
first-order
PL
V-PBGD [16]
(2)
penalty
first-order
PL
(:)
SLM
(1)
primal-dual
first-order
PL Ö (1)
machine learning problems, e.g., hyper- parameter optimization [3, 4), actor-critic schemes in rein- forcement learning [5], meta-learning [6. 7], AUC maximization [8], distributed bilevel optimization [9, 10, 11], etc. In these scenarios, the decision/optimization variables are coupled in both levels of the minimization problems and the evaluation of the UL gradient depends on the optimal solution the LL.. Consequently, it is necessary to optimize the UL and LL loss functions jointly w.r.t. the block variables r and y.
1.1 Related Work
Bilevel Optimization. Motivated by the numerous applications of BO, developing the efficient solvers for handling these problems has attracted great interest in the optimization community. There are two major directions: 1) focus on solving the BO problem in a general manner; 2) improve the computation or iteration complexity of the BO algorithms. has been shown in [17] that a first-order method can find the global optimal solution when the UL objective function is strongly convex and the LL problem is convex. However, the strong convexity assumption restricts the applicability of the algorithm to many real-world machine learning problems. In contrast, some recent works have considered the case where the UL objective function nonconvex and have shown that, given an oracle that computes the Jacobian and the inverse of Hessian matrices of the LL objective function, the complexity of finding an e-stationary point gradient descent. But this setting is still restrictive they still assume that the LL problem is strongly convex.
O -1) [18, 13], which is the same as that of
Non-Singleton at the LL. When the LL problem is not strongly convex, the computation of the UL gradient fz S(x)) can become ill-posed due the presence of multiple optimal solutions. To address this issue, a new metric called (6. GoGldssten stationary point was introduced in [19], which aims to capture the discontinuity of (x, Under the assumption that f(x, and g(x, -) are convex, it was shown that an inexact gradient-free free method can find the Goldstein stationary point rate of ()) In addition to the new metric used for theoretical convergence analysis, the concept of Hölderian error bound was employed in [20], which imposes further conditions on the shape of the LL objective function. For a class of simple BO problems where only one set of block variables needs to be optimized, the conditional gradient-baser bilevel optimization (CG-BiO) algorithm proposed in [20] was shown to converge to stationary points at a rate of O(E=)) or ( depending whether the Hölderian error bound holds.
In [21], the author considered the case of nonconvex LL objective function but with an assump- tion that eliminates the presence of zero eigenvalues of the LL Hessian matrix. Another property used characterize the landscape of the LL function is the PL condition. Based on the formulation in (1), researchers [16, 15] developed penalty methods for solving BO problems and discussed the relationship between local/global optimal solutions of the penalized problem formulation and the constrained problem (2) (i.e., when 5 in (1)) It was shown that the value-gap-based penalty- based bilevel gradient descent (V-PBGD) algorithm [16] can converge to stationary points of the reformulated single-level problem. Additionally, under the assumption of the constant rank con-

---

straint quantification condition, the bilevel optimization made easy (BOME) algorithm developed in [15] can achieve Karush-Kuhn- Juhn-Tucker (KKT) points of the BO problem in (2).
Computational Issue. Another line of research focuses on reducing the computational complexity of implementing BO optimization algorithms. As mentioned earlier, computing the UL gradient can be computationally expensive. Existing works have employed strategies such as the Neumann series for calculating the inverse of Hessian matrices [18], or utilized reverse-mode iterative differen- tiation (ITD) and approximate implicit differentiation (AID) techniques [22, 13] for hypergradient computation. However, these strategies introduce a double-loop structure in the algorithm design, requiring users to specify hyperparameters for the inner loop subroutine. Subsequently, single-loop BÒ algorithms have been developed [23, 24]. which alleviate the burden of hyperparameter tun- ing in the inner loop. Nevertheless, they still require the computation of the Jacobian matrix and Hessian-vector product.
To circumvent these computations, some existing works reformulate the BO problem as a single- level functional constrained optimization (FCO) problem, as shown in (I), and apply well- established constrained optimization techniques, such as primal-dual methods, for solving the BO problem using only gradients. In [25], was shown that when the UL problem is strongly convex and the LL problem is convex, the primal-dual algorithm can find the global optimal solution at a rate of ((-1/)). For the case where the UL problem is nonconvex, the fully first-order stochas- tic approximation (F2SA) method proposed in [14] can find an e-stationary solution at rate of O(e-3/3 when the LL problem is strongly convex. Similarly, penalty methods [26, 16] also just require the computation of UL and LL gradients while achieving the desired optimization results.
Functional Constrained Optimization. The formulation based on function values establishes a connection between FCO and BO [1. 27, 28). By leveraging existing well-developed constrained optimization methods [12, 29, 30), efficient solutions to the BO problem can still be obtained. When the block variables x and y are linearly coupled, the alternating direction method of multipliers (ADMM) [31] has emerged as a successful approach by decoupling the optimization process into subproblems. Recent advancements in smoothed augmented Lagrangian methods [30, 32, 33] have improved the convergence rates for solving nonconvex linearly constrained problems. For nonlin- car functional constraints with one block of variables, the constraint extrapolation (ConEx) method [12] has shown promising results in finding KKT points with a convergence rate of (c22)/2 for nonconvex smooth functions. Besides, the properties of PE. functions studied in min-max optimiza- tion problems [34] are expected to be useful in demonstrating the continuity of V (x, (xx) for BO problems within the framework of primal-dual methods. A comparison between our work and closely related previous works on FCO and BO is shown in Table 1.
1.2 Main Contributions of This Work
In this work, we propose a novel approach called the smoothed first-order Lagrangian method (SLM) to tackle the FCO problem presented in (I). The key advantage of SLM is that it only requires the computation of gradients. making it computationally efficient. Remarkably, under mild assumptions and a local regularity condition, we establish strong error bound for SLM solve this class of problems, and prove that SLM can converge to the KKT points even when the nonconvex objective in the constraint has multiple optimal solutions. To summarize, the main contributions of this work are highlighted as follows:
This class of structured FCO problems is generic and can be used to formulate multiple machine learning problems. The proposed SLM is computationally efficient as it relies only on the gra- dient of the objective functions. Moreover, the obtained convergence rate of the proposed SLM, which is ((e ). is optimal for finding the <-KT points of this class of problems.
SLM can be applied solve nonconvex bilevel related optimization problems in the presence of nonconvexity and non-singleton at the lower level, when the LL objective function satisfies the PL condition.
The numerical results showcase the competitiveness of the proposed SLM compared to state-of- the-art BO algorithms in both toy example and a data hyper-cleaning problem w.r.t. conver- gence speed and achievable test accuracy.
Due to space constraints, all technical proofs are provided in the supplementary material.
Notations: The distance between y and the set S(x) is defined ds(.) (v) & minyyes(a)) llv - v'll- A high-dimensional ball with radius of R is denoted as B(R).
3

---

2 Smoothed First-Order Lagrangian Method
In this section, we will introduce the three-layer structure our first-order method designed to solve problem (I), Towards this end, we can write the Lagrangian of this constrained problem as follows:
C(x, y: X) _ v( X(((z, v) g (z) 6)
(3)
where the nonnegative A denotes the Lagrange multiplier or dual variable. Next, it is natural to have
V V, = v.I(2, + X(V (g V (x))
(4a)
V Ca, y; vuf(z,u)+ +
(4b)
VaC y: A) = p(z,,))--(C
8.
(4c)
In contrast the classical primal-dual algorithm design, here, g (x) is typically unknown. Based on the definition of (z), it is not hard to know that obtaining a closed-form expression for Vgg (æ) requires the computation of the Jacobian matrix and the inverse of Hessian matrice even for the case when ( y) is strongly convex w.r.t. y. Although many existing works have provided the iterative methods of computing these quantities for each iteration [13, 23, 24), the calculational cost and/or memory budget are still high for large-scale problems. Hence, it is motivated to have an efficient way of approximating the value and gradient of g" (2) in the algorithm design.
2.1 Bottom-Layer
One of the most straightforward approaches is generate sequence ue indexed by inner loop to obtain u" (x) & arg min,
(x, u)) When the objective function g(z,)) y) satisfies certain properties, such as the PE condition or the strongly convex condition, applying gradient descent can lead to finding the global optimal solution of this subproblem with linear convergence rate [35].
Let r denote the index of the outer iteration steps. Then, the approximate of u (ar) at each iteration, i.e., u", can be estimated through the following process:
u u/ 7 Vug(("" ,ug("",;()))
(5)
where of represents the /th iterate of the inner loop, denotes the step-size, and wi is initialized within bounded ball (which will ensure the boundedness of the iterates). After running this algo- rithm for 2" iterations at each step, we set u un. for updating the subsequent optimization variables.
2.2 Medium-Layer
Given that the quality of (x) can be guaranteed, the most interesting part lies in solving the con- strained problem w.r.t. block y. Even if we assume that g(2, y) follows the PL condition, the nonconvexity of f(x,,) still poses challenges for the first-order methods in finding the optimal so- lution. address this, we propose adding the quadratic proximal terms that renders the Lagrangian w.r.t. and strongly convex, as follows:
K (x, y, w. z; A) A Mi + 2 1 - w|l - - 2112.
(6)
Here, K(x, y, w. 2; A) can be regarded as a modified Lagrangian for this problem. Let Ly and Lg denote as the smoothness constants of f and g. respectively. Choosing a sufficiently large value for p (specifically, p , + )Lg)) ensures that K (x. y, w, 2; A) becomes strongly convex.
Subsequently, we can develop the following gradient-basee primal-dual algorithm for solving this constrained subproblem:
1+ P+ A- +VVAR((",, V. wi F. (x)] /² = - -oV,K( ,', , x+t))
(7a)
(7b)
11 2- + z²),
(7c)
where R(x, y, W, u; A E(x, V, u: A) + || - w 1 + f11 - 212 and 2(x,, y, u; A) - s(x v) +
Ma((1, y) g(x, u) (). 3 are the step-sizes, and P. denotes the projection of the dual variable onto box constraint. In particular, P_[ is given by P. [A] = 0 0: P+[ Xif X A; P+[N] A A A.

---

Remark 1. The auxiliary sequence 2" is defined as an exponentially weighted average sequence of y which has been previously used in smoothed gradient descent ascent for nonconvex min-max optimization [36, 37] problems and in the smoothed proximal augmented Lagrangian method for linearly constrained nonconvex objective problems [32]. However, to the best of our knowledge, this is the first time that the smoothed primal-dual method is applied to solve nonconvex objective problems with nonlinear functional constraints.
2.3 Top-Layer
After updating the variables ys 2, u. and X, the variables x and updated follows:
x r- = Px x" 7/ R( t² w", z=t t x
(8a)
wt r-1 = w" + 3(x w')
(8b)
where Px denotes the projection operator, and 1) is the step-size. The detailed algorithm description is provided in Algorithm
Algorithm Smoothed first-order Lagrangian Method (SLM)
Initializatin:: step-sizes: T, 7/, o; 8, 7, variables: at, wt, y² 27, A
1: for r == 1,,,, ,T do
2:
for f=rt=00 0, 1,2. T 1 do
3:
Initialize un E ((
4:
u141 = un
ug "ngg(" (z", uF
bottom layer
5:
end for
6:
un+1 =ufi -ujir
7:
X =P+ [X' + (g(2", ,y) g(x",22*1) -
dual variable update
8:
B +1 = y aa (V (I" ,y") )²² - X x V vgl"z,
",0(2",1)) 15" +py 22))
P medium layer
9:
2' +l = x- + + +1 - -²²)
x +1 -xx -1 (VaJ (x", , x21 X (V 1(th) (att)-vagle Vag(x", u x(+1)) + + w²))
11:
w w = w" + f(x w²)
b top layer
12: end for
3 Theoretical Convergence Results
Before presenting the theoretical convergence guarantees SLM, it is necessary to introduce the following main classes of assumptions. These assumptions are essential in establishing the descent properties of some quantifiable (potential) function, enabling SLM converge KKT points of this class of nonconvex FCO problems. More detailed definitions and properties regarding these assumptions are deferred to the supplement.
3.1 Assumptions
The assumptions are mainly related the continuity and boundedness of the objective function, as well as the mathematical property of the constraint.
A1.
(Smoothness) Assume that functions fxx u), 1), v) are differentiable and jointly smooth with constants Ly, Ly w.r.t. both x, y.
A2. (Compactness) The feasible set (projection friendly) is convex and compact.
A3. (Boundedness) Assume that the objective function f(r, y) is lower bounded and denoted as f.
A4. (Coercivity) The set {ulf(z, y) S R. g(z, v) g=" < 8} is bounded for any R > 0. A5. (PL condition) Function g(z.y) y) satisfies the PE condition, i.c., there exists a constant Hy such that Vyg(z, 1) 2 2,, v) - g (x)), Vx,y.
Remark 2. Assumptions A1-A3 are standard in the optimization literature, while A4, also referred to as coerciveness, is commonly used assumption in theoretical convergence analyses to guarantee boundedness of the iterates, observed in methods like smoothed-GDA [36], ADMM [38], BO algorithms [39, Assumption 3], asynchronous algorithms [40, Assumption 5], etc. practice, reg- ularization terms are often included in the objective function, which can ensure that the level set is
5

---

bounded [41]. For instance, as suggested in [39], introducing a small l2 p--ennllyy to a non non-negative loss (e.g. cross-entropy or mean-squared loss) can establish boundedness for both the level set and the iterates. An example involving neural networks can be found in [42, Theorem 2]. A5 is rea- sonable and practical assumption for neural network applications. Previous studies, such as [43], have demonstrated theoretically that when neural networks are overparametrized, the loss function satisfies the PL condition. Other examples include the nonconvex discounted return objective in reinforcement learning [44], and the loss function of specific class of linear quadratic regulator models [45, Lemma 3].
Local Regularity Condition. Let (w, 2). 8" (w, 2) be the KKT solution of problem minz.9 f(x, y) fl - w|l? + Elly - =II² s.t. g(2, u) I (x) + 6. Then, there exist positive constants á and such that when || x- (w, 2] + --=---- (w, 1 < 0. the following inequality holds g(" 1j" (w, 2)) 2 9 (.*(w, 2)) + + z). where 6(w, z) 2 5.
Remark 3. Given the feasibility of achieving the global optimal solution of g" g" (i" 2)) and the re- quirement for variable y to minimize both objective functions, it is reasonable to expect that ÿ" (w,*) can be close to arg min g( (w, z). 3) up to some very small constant. It is worth noting that this assumption is fairly mild, as we only require this condition hold in the neighborhoods of the KKT points.
Given these assumptions, we now in position to provide the following theoretical convergence guarantees for SLM.
3.2 Convergence Rates of SLM
Let (x"", y²" be defined as 9(x", v("),"") A - (P=x - -1 Vall", (';x"))) VyL(a", {²)] We denote [|9("", s/"|l the stationary gap.
Theorem 1. (Convergence Rate of SLM to the KKT Points of problem (1)) Suppose that AI-A5 are
satisfied, and the local regularity condition holds. Assume that the iterates {x', {x',y", w", z², u², X²
are generated by SLM. If the step-sizes are chosen as 17, a ~ (11XX",, 7 = (1/Lgg) ) p = O(x)), (11), 8 ( when 0- < 8 < 1, and = (() when ō > 1, and T ((log(AA)) A 0(1/ then, o == OVV)) and the following results hold
Al. Every limit point of {a", .,', Vf, w", , 2 w. N generated by SLM is a KKT point of problem (1).
A2.
1 T
19((", (((x","")11 w/') =
(9a)
T
+
19(0" ,v²) 99'(x") - 812 0
(T)
1
(9b)
1 T
Σ (g(x .V) (20) =0 -0())
(9c)
T
where 1. takes the positive part, and T denotes the total number of iterations.
Remark 4. From Theorem 1, we can conclude that the iteration complexity of SLM to reach an e- KKT stationary point is (1/cc. It is also worth noting that this convergence rate is optimal in terms of c, as matches the lower bound established by the first-order method for finding an c-stationary point of nonconvex smooth optimization problems [46].
Corollary 1. (Convergence Rate SLM to K-K Solutions of the BO problem (2)) Suppose that Al- AS hold and the local regularity condition holds. Assume that the iterates {x", yy, w", ,²""""" ","", X² are generated by SLM. Given the condition that d = e and assuming ö = c, if the step-sizes n) a O(L/X), 3 = (5) Y = (L) T = (1), T" = (ilog(1/e)) and P.A = (11 then e = (Vv)) and the iteration complexity of SLM for finding an KKKT stationary solution is O11/c3.5)
Remark 5. Here, an e-KKT stationary solution of this FCO problem refers a point {x*, .y} that satisfies [] ("""","")) , < and 1g(2", yy") -"" (x*) -|2 812 < e, and [g([", ,y²) -""=="""" -x*) (6)") Se

---

4 Proof Sketch
In this section, we will present the main theorem proving techniques employed establish the results in Theorem 1. Let
D(w, - min (I,,,, wEX'y
(10a)
P(w,2) - min max y, (, =EX OSASA
(10b)
x² (w, zi A), 1² (w, 2; A)
arg min WI, =EXX.y
(10c)
xx (w,,)) 2), D- (w, 2) arg min max (2x y, w; 2; A).
(10d)
aEX. OSASA
These four quantities are associated with the dual error bounds. The first two quantities, given by (10a) and (10b), define the optimal values of x, y given w, z, and X, while the last two quantities, defined by (10c) and (10d), represent the optimal solutions for these intermediate subproblems.
It is obvious that when p is sufficiently large, K (a, y, w, 2; A) strongly convex jointly w.r.t æ and First, under Al and A5, we can easily show that
Ster)(u55.)) S Mgg 2/4r ) (o(x", 24) - gx"))
(11)
so under A2 and the assumption that u" is initialized within a bounded set, it follows that d(s (u)--) decreases to at a linear rate. This inequality (11) is instrumental in quantifying the bias term (x") 9(x", 2/2 that arises due to the inaccurate estimation of arg min, g(2;, y). Next, we will present the following three lemmas which play a crucial role in establishing the proof of Theo- rem 1.
4.1 Descent Lemmas
After one round update of SLM (i.e., from (x", w", ,","", (²) to (x+11 1ettl,,rtt ,ytt1 wrrt 1 ,,++1), we can obtain the following result.
Lemma 1. Under A I-A5, suppose that the sequence is generated by SIM. When o, v S 0(1/A+11),
0 B < 1, T" ((log(r(+1)) and p > L., there exists constant such that
2(x .y r1 w r+ 12 2rt1 : - 22ax,, .
w" ,0',,"" ;²)
(eg + EZ)
9T
||1"t1- -x11-- 2a
11 - -/1
4n
112
a²
(² + D-L + (3660t ||a - -2"113 p
2p
(1
+ 2p
p L )) |10 - w01 -2'l
(
2B
23
+ +3ppC (lly" (w", : ((=",²))) (w", ,²'))² + ||I x Ar+1 (ww",
x "1''t",,,,"" (w",x")) ;²))) 1 (w", ,
48p[02/
19(x"(w", ; ). v0 (w", 22,x,++)+) g" (w"(",, "w"",";;>"""" (²;x((()) - -12
56
+ (Hg L2 + 20²)
Ds
1
1
- - 2712
(12)
,2
4T
where 01 A (p- L)/P. 02 = (p+ L)/(p- - L., 03 == 1/pp T. I. + X(2 + /2// / (2 X+ 2) = <Val*+V>(<>'> (w, z; A),yy (w, z; >), w, z; X)1, Eg Cy denote Lipschitz constant of g(x, y) and 9" (x) respectively, the potential function function
Q(x", 3², w", x²) A K(2 3", w. ,'),"";'== 2D(w", ,² (') + 2P 22),,
(13)
and Dg 2 2 (maxg(x, un) - ming (I)) Vo E X, un E B(R).
can be observed that the coefficients in front of the terms ||I x² Il, [|8 1²12 12, ||a = (-+1)) g" (x"("" (w" x²+ 8/2 can
I" || - w/ 2| and gg(= (w"""""","""" =²; xx+1), ""(",,, x²;; be negative when the step-sizes are properly chosen and the bias term can be summed up to a constant. Hence, to ensure sufficient decrease of Q(x", yy, ("),) it necessary to bound the positive terms w.r.t. 11 (w", z"; X (w", 2²)) 5" (w", (w",>")]l² and [|x" x (w", ;;,)))
a ("(w,, 22 To accomplish this, two novel dual error bounds are provided as follows.
7

---

4.2 Dual Error Bounds
Lemma 2. (Weak Dual Error Bound) Under Al-A3 and A5, suppose that the sequence fo" v", w u }
is generated by SLM. Then, it holds that
(w"" (""; x² X4 1 (w", 22)) - ""("","")'"" + || (w", ,2"; X X (w",, S Tweak
220)12
,2") - x'(",, ,00,2"100
|| - x x= (w", ,2 1'I :aAA(w")))== - x (w',, 22))
(14)
where
1 + T2C, + +g 10002 27(p- L.
@weak
X( arg max K( 21, (u, w, 2; OSASA
(15)
Although (14) has quantified the variations between v""", 2""; X7 (w",2") and (w", 2²" and between x" (w", =²; (w",²")) and n² (w", =²) when the dual variable is perturbed', this bound a non-homogeneous form. Therefore, is not sufficient to demonstrate the O /c) convergence rate of the sequence generated by SLM. Fortunately, under the local regularity condition, we can obtain the following stronger result, which provides further insight.
Lemma 3. (Strong Dual Error Bound) Under AI-A3, A5 and the local regularity condition, suppose that the sequence {x ,y",,, ,","",""" w. } } is generated by SLM. Then, there exists constant stong such that
11y" (w", 2² 2 (w"",") - I (w", 22')] + ||0 (w", 22: aatttwu ,2))) - x (w",,"" (w",²")
22)]]
S 20 stron Flon 2"", x"; ),y (w", 2 ()++)))) -g" (x" (w 2';"=)) -61
(16)
where
L + p ALg
o Strrong
Oweak
/2
(17)
Given this inequality, we can quantify the sufficient descent of the potential function, which further leads to the convergence rate of SLM.
5 Numerical Results
In this section, we evaluate our proposed algorithm for solving the bilevel optimization related prob- lems and compare the performance of our proposed SLM with the state-of-the-ar art methods.
5.1 Toy Example
First, we consider the following toy example
min fxx, v) x² + 1² + 3x sin (v), s.t. g(x,y) - 9 (x) S =c(1.2)
(18)
where the LL objective function is g(x, y) a xy² 3z sin' (y) and 5 x 10 10-3 It can be easily checked that function 9(x, y) satisfies the PE condition w.r.t. variable y and function f(z, y) is nonconvex w.r.t. I and y jointly.
In the numerical results, we initialize variables as x=1 = y² = w² = 1 and choose the step-sizes for updating these variables (u, y, x) as 10-3 for all the compared methods. Additionally, we set p 1 and 3 = 0.5 for SLM. It can be seen from Figure I that SLM provides the advantage
AA (w", =²") is perturbation of 1-1
00nerrr1 violation
STM
BOME
Jowar- Jovel jootett value
V.PRGDI
ROME
appee levell objoe Live value
V-PBOD
BOME
12
12"
150
Dummbbr of iterations
Duunbber Of Aoesatios
Dumbber of iteratioon
(a) Constraint violation
(b) LL objective value
UL objective value
Figure 1: Convergence performance of SLM. BOME [15], and V-PBGD [16] on the toy example.
8

---

of enforcing the constraint to be satisfied even the LL objective is noncovnex. Moreover, all the algorithms converge to the global optimal solution of the LL problem. It worth noting that SLM achieves the lowest UI. objective value compared to the other methods. This can be attributed to the relaxation introduced by in achieving the optimal solution of the L.L problem, which provides more flexibility in searching for lower UL objective values.
5.2 Data Hyper-Cleaning
Next, we further evaluate SLM for the data hyper- cleaning problem, which has gained widespread adoption in the machine learning community [3, 16]. The goal of this learning task is to identify and selec- t the clean data samples from the polluted ones, en- abling the pre-trained model to generalize effectively on the clean test dataset. The optimization problem is commonly formulated as follows:
upper-level objective value
SLM V V-PBG
min e"T (v), S.t. y E arg min grain (x, (19) a.y
20.00
15.00
2.00 2000
xamberr of Iterationn y
where gaa and grain represent the validation (at the UL) and training (at the LL) losses, respective-
Figure 2: Comparison between SLM and V- PBGD on the data hyper-cleaning task over the MNIST dataset.
ly. The LL loss function is defined as ftrain & Ei= (xzz)[(y), where m denotes the total number of training data samples, (ar) the sigmoid function, and y denotes the weights of the neural net- work. Adhering to the experimental settings used to test the V-PBGD as shown in [16], we are given 5, 5,000 training data samples from the MNIST dataset. Among these samples, 50% are randomly polluted with incorrect labels. Additionally, we have a validation dataset consisting of 5, 000 sam- ples and a separate test set comprising 10, 000 samples. The model parameter y includes the neural network weights of a hidden layer with size of 10 x 784 and bias terms with size of 10.
It has been shown in [16] that V-PBGD outperforms significantly the sate-of-the-arr methods, in- cluding BOME [15], IAPTT-GM [47], RHG [3], T-RHG [4], for this particular example. We adapt the code used to implement V-PBGD to evaluate the performance of SLM and set = p 20, 3 = 0.5, 5 = 1.2 for SLM. From Figure 2, it can be observed that SLM initially converges at sim- ilar rate to V-PBGD in terms of the test loss values. However, after a certain number of iterations, SLM achieves smaller loss values. The reason behind this observation is that once the constraint is satisfied, the optimization variables primarily focus on minimizing the UL objective values, leading to lower test losses in this example. Although SI.M achieves a test accuracy similar to V-PBGD, with the highest test accuracy of 90.44%, when the number of iterations becomes large (e.g.. exceed- ing 3. 000 in the figure), the model begins to overfit the training data. However, SLM maintains test accuracy of 88.8%, while V-PBGD can only attain 88.1%.
As for the constraint violation, we define Cerro A quain (vr, v) v(x). where v(ar) is computed through the updating process of variable u. This measure represents the distance between the LL objective value and the optimal value. V-PBGD results in a Cerrer value of approximately 0.68, whereas SLM achieves a (Cenor 5) value of 0.001 when the total number of iterations exceeds 2, 000 in the figure. This further reinforces the fact that due to the presence of the optimization variables appearing in both levels or the coupling between the LL and UL. variables, it is highly challenging for in the BO formulation to find the global optimal solution of the LL problem. In contrast, SLM can find KKT solutions for this class of structured FCO problems as long as the hyper- param-arreettr 5 is appropriately defined.
5.3 Neural Network on MNIST Data Set
We also evaluate the performance of these algorithms on a 2-layer neural network. The size of the first layer is 784 x 300, and the size of the second layer is 300 x 10. The activation function used is the sigmoid function. For all the compared algorithms, we set the step-sizes of the block-r and block- updates to 1. The step-size y for the auxiliary block-u update is set to 0.1. Additionally, choose - = 0.01, 3 = 0.5, and p = 20 for SLM, while for BOME, we use r = 0.1. The remaining settings remain the same as mentioned in the main text for the linear case.
The results, averaged over 5 independent trials, are presented in Figure 3. can be observed from Figure 3(a) that SLM with 8 = - achieves the lowest test loss and converges faster compared to

---

SLM BOME V-PUGD
0.5
145
test accuracy
test loss
223
#2.
SLM 1.0 SLM BOME V-PBGD
10"
91
222
220
200
700
922
number of iterations T
number of iterations
(a) Test Joss
(b) Test accuracy
Figure 3: Convergence performance of SLM, BOME [15], V-PBGD [16] on neural network.
When & = 0.5, the convergence rate of SLM becomes slower. Both of these observations align with the theoretical convergence analysis. The test loss obtained by V-PBGD initially decreas- es and then increases, which is reasonable this method optimizes both the UL (validation) and LL (training) loss values, with the penalty parameter increasing as the number of iterations rises. In contrast, SLM primarily minimizes the objective loss values, specifically the validation loss in this case, leading to better generalization performance as long as the constraint satisfied. The con- straint tolerance parameter 6 and the dual variable implicitly play the tradeoff between the training and validation losses.
BOME.
Regarding the test accuracy shown in Figure 3(b), SLM with 5 = achieves minimum of 94.74 + 0.04%, which is the lowest among all the algorithms compared. V-PBGD can reach 94.65 + 0.09% but converges slower than SLM with 8 = 1. SLM with = 0.5 and BOME converge relatively quickly initially and reach peak accuracies of 94.53 0.06% and 94.52 + 0.11%, respectively. However, is evident that the test accuracy achieved by BOME decreases rapidly as the algorithm proceeds, even though the test loss continues to decrease, forming clear U-shape. This implies that BOME overfits the validation data when the number of iterations is large. In contrast, the test accuracy achieved by SLM remains relatively stable, or at least does not decline as rapidly as that attained by BOME. This further confirms that the of structured constraints in this class aids in improving the generalization performance of bilevel models.
Concluding Remarks
In this work, we focused on solving a class of structured nonconvex FCO problems, where the functional constraint satisfies the PL condition w.r.t. one block of variables. In practical applications, this class of FCO problems can effectively model a wide range of nested or hierarchical learning problems, including data hyper-cleaning. meta-learning, corset selection, and more. To address these challenges, we developed a smoothed primal-dual algorithm based on the Lagrangian method. The proposed algorithm achieves convergence rate of O(c-1) )) to the c-KKT solutions of this problem by utilizing only the first-order oracles for both the objective function and the constraint.
The major difficulty from theoretical perspective lies in showing the dominance of the descent achieved by the algorithm over the ascent induced by enforcing the nonconvex functional constraint. To the best of our knowledge, this is the first result showcasing that the dual error bound also holds for solving this class of nonlinear constraints. We conducted extensive numerical experiments to evaluate the performance of the proposed SLM against benchmark nonconvex BO methods. The results demonstrate that SLM not only ensures the satisfaction of the functional constraint but also achieves small objective values.
is important to note that this work focuses on the scenario with single constraint. Future research endeavors will explore the extension of the algorithm design and theoretical results to more general settings. Addressing this limitation will contribute broader applicability the proposed method.
10

---

References
[1] R. Liu, X. Liu, X. Yuan, S. Zeng, and J. Zhang, "A malue-function-bard interior-poin method for non-convex bi-level optimization," in Proceedings of International Conference on Machine Learning (ICML), pp. 6882-6892, 2021.
[2] Z.-Q. Luo, J.-S. Pang, and D. Ralph, Mathematical Programs with Equilibrium Constraints. Cambridge University Press, 1996.
[3] L. Franceschi, M. Donini, P. Frasconi, and M. Pontil, "Forward and reverse gradient-based hyperparameter optimization." " in Proceedings of Advances in Neural Information Processing Systems (NeurlPS), pp. 1 1165-1173, 2017.
[4] A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots, "Truncated back-propagation for bilevel op- timization," in Proceedings of International Conference on Artificial Intelligence and Statistics 2019.
(AISTATS), pp.
[5] S. Qiu, Z. Yang, J. Ye, and Z. Wang. "On finite-time convergence of actor-critic algorithm." IEEE Journal on Selected Areas in Information Theory, vol. 2, no. 2, pp. 652-664, 2021.
[6] A. Rajeswaran, C. Finn, S. M. Kakade, and S. Levine, "Meta-lcarning with implicit gradients," Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2019.
[7] S. Lu, "Bilevel optimization with coupled decision-dependdnt distributions," in Proceedings of International Conference on Machine Learning (ICML), pp. 22758-22789 2023.
[8] Q. Hu. Y. Zhong, and T. Yang. "Multi- min-max max bilevel optimization with applications in multi-task deep AUC maximization." " Proceedings of Advances Neural Information Processing Systems (NeurlPS), pp. 29552-29565, 2022.
[9] S. Lu, S. Zeng, X. Cui, M. Squillante, L. Horesh, B. Kingsbury, J. Liu, and M. Hong, "A stochastic linearized augmented lagrangian method for decentralized bilevel optimization." in Proceedings of Advances in Neural Information Processing Systems (NeurIPS), pp. 30638- 30650, 2022.
[10] S. Yang. X. Zhang, and M. Wang, "Decentralized gossip-based stochastic bilevel optimization over communication networks," in Proceedings of Advances in Neural Information Processing Systems (NeurIPS), pp. 238-252, 2022.
[11] X. Chen, M. Huang, S. Ma, and K. Balasubramanian, "Decentralized stochastic bilevel opti- mization with improved per-iteration complexity." in Proceedings of International Conference on Machine Learning (ICML). pp. 4641-4671 2023.
[12] D. Boob, Q. Deng, and G. Lan, "Stochastic first-order methods for convex and nonconvex functional constrained optimization," Mathematical Programming, vol. 197, 1, pp. 215- 279, 2023.
[13] K. Ji, J. Yang, and Y. Liang, "Bilevel optimization: Convergence analysis and enhanced de- sign," in Proceedings of International Conference on Machine Learning (ICML), pp. 4882- 4892, 2021.
[14] J. Kwon, D. Kwon, S. Wright, and R. Nowak, "A fully first-order method for stochastic bilevel optimization," " in Proceedings of International Conference on Machine Learning (ICML), p- 18083-1811 13, 2023.
[15] B. Liu, M. Ye, S. Wright, P. Stone, and Q. Liu, "BOME! bilevel optimization made easy: A simple first-order approach," in Proceedings of Advances in Neural Information Processing Systems (NeurIPS), vol. 35, pp. 17248- 2022.
[16] H. Shen and T. Chen, "On penalty- based bilevel gradient descent method," in Proceedings of International Conference on Machine Learning (ICML), pp. 30992-31015, 2023.
[17] Sabach and S. Shtern, "A first order method for solving convex bilevel optimization prob- lems," SIAM Journal on Optimization, vol. 27, no. 2, pp. 640-660, 2017.
[18] S. Ghadimi and M. Wang, "Approximation methods for bilevel programming." arXiv preprint arXiv: 1802 02246, 2018.
[19] I. Chen, Xu, and Zhang, "On bilevel optimization without lower-level strong convexity," 2rXiv:2301.00712, 2023.

---

[20] R. Jiang, N. Abolfazli, A. Mokhtari, and E. Y. Hamedani, "A conditional brase method for simple bilevel optimization with convex lower-level problem," in Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 10305-10323, 2023.
[21] F. Huang, "On momentum-basn based gradient methods for bilevel optimization with nonconvex lower-level." arXiv preprint arXiv:2303 2234:423303.3394, 2023.
[22] R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo, "On the iteration complexity of hypergradi- ent computation," in Proceedings of International Conference on Machine Learning (ICML), pp. 3748-3483333 -778,, 2020.
[23] M. Dagréou, P. Ablin, S. Vaiter, and T. Moreau, "A framework for bilevel optimization that enables stochastic and global variance reduction algorithms," in Proceedings of Advances in Neural Information Processing Systems (NeurIPS), pp. 16698-26711 2022.
[24] J. Li, B. Gu, and H. Huang. "A fully single loop algorithm for bilevel optimization without hes- sian inverse," in Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), vol. 36, pp. 7426-7434, 2022.
[25] D. Sow, Ji, Z. Guan, and Y. Liang, "A constrained optimization approach to bilevel opti- mization with multiple inner minima," arXiv preprint arXiv:2203.01122 2022.
[26] A. Mehra and J. Hamm, "Penalty method for inversion-free deep bilevel optimization,"" in Proceedings of Asian Conference on Machine Learning (ACML), pp. 347-362, 2021.
[27] J. V. Outrata, "On the numerical solution of class of stackelberg problems," Zeitschrift fül Operations Research, vol. 34, pp. 255-277, 1990.
[28] R. Liu, Liu, W. Yao, S. Zeng, and Zhang, "Averaged method of multipliers for bi-level op- timization without lower-level strong convexity," in Proceedings of International Conference on Machine Learning (ICML). pp. 21839-218888
2023.
[29] Lu, "A single-loop gradient descent and perturbed ascent algorithm for nonconvex functional constrained optimization," in Proceedings of International Conference on Machine Learning (ICMI.), pp. 14315-14357, 2022.
[30] J. Zhang and Z.-Q. Luo, "A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization," SIAM Journal on Optimization, vol. 32, no. 3, pp. 2319-2346, 2022.
[31] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, et al., "Distributed optimization and statis- tical learning via the alternating direction method of multipliers," Foundations and Trends in Machine learning, vol. 3, no. 1, pp. 1-122, 2011.
[32] J. Zhang and Z.-Q. Luo, "A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization," SIAM Journal on Optimization, vol. 30, no. 3, pp. 2272- 2302, 2020.
[33] J. Zhang, W. Pu, and Z.-Q. Luo, "On the iteration complexity of smoothed proximal ALM for nonconvex optimization problem with convex constraints," arXiv preprint arXiv:2207. 06304, 2022.
[34] M. Nouiched, M. Sanjabi, T. Huang. J. D. Lee, and M. Razaviyayn, "Solving class of non- convex min-max games using iterative first order methods," in Proceedings of Advances in Neural Information Processing Systems (NeurIPS), vol. 32, 2019.
[35] H. Karimi, J. Nutini, and M. Schmidt, "Linear convergence of gradient and proximal-gradient methods under the Polyak- condition." in Proceedings of Machine Learning and Knowledge Discovery in Databases: European Conference (ECML PKDD), pp. 795-811, 2016.
[36] J. Zhang, P. Xiao, R. Sun, and Z. Luo, "A single-loop smoothed gradient descent- al- gorithm for snrconvex-concayy min-max problems." " in Proceedings of Advances in Neural Information Processing Systems (NeurIPS), pp. 7377-7389, 2020.
[37] T. Lin, C. Jin, and M. Jordan, "On gradient descent ascent for nonconvex-concave mini- max problems," in Proceedings of International Conference on Machine Learning (ICML), pp. 6083-6093, 2020.
12

---

[38] Y. Wang, W. Yin, and J. Zeng, "Global convergence of admm in nonconvex nonsmooth opti- mization." " Journal of Scientific Computing. vol. 78, pp. 63. 2019.
[39] M. Arbel and J. Mairal, "Non-convex bilevel games with critical point selection maps." Pro- ceedings of Advances in Neural Information Processing Systems (NeurIPS), vol. 35, pp. 8013- 8026, 2022.
[40] L. Cannelli, F. Facchinei, V. Kungurtsev, and G. Scutari, "Asynchronous parallel algorithms for nonconvex optimization." " Mathematical Programming, vol. 184, pp. 121-154, 2020. net-
[41] X. Xie, H. Kong, Wu, W. Zhang, G. Liu, and Z. Lin, "Maximum-annd-oonaatuin works," in Proceedings of International Conference on Machine Learning (ICML), pp. 10483- 10494, 2020.
[42] S. Liang, R. Sun, and R. Srikant, "Revisiting landscape analysis in deep neural networks: Elim- inating decreasing paths to infinity," SIAM Journal on Optimization, vol. 32, no. 4, pp. 2797- 2827, 2022.
[43] C. Liu, L. Zhu, and M. Belkin, "Loss landscapes and optimization in over-parameterized non- linear systems and neural networks," Applied and Computational Harmonic Analysis, vol. 59, pp. 85-116, 2022.
[44] J. Mei, C. Xiao, C. Szepesvari, and D. Schuurmans, "On the global convergence rates of soft- max policy gradient methods," in Proceedings of International Conference on Machine Learn- ing (ICML), pp. 6820-6829, 2020.
[45] M. Fazel, R. Ge, S. Kakade, and M. Mesbahi, "Global convergence of policy gradient methods for the linear quadratic regulator," in Proceedings of International Conference on Machine Learning (ICML), pp- 1467-1476, 2018.
[46] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford, "Lower bounds for finding stationary points
i," Mathematical Programming, vol. 184, no. 1-2. pp. 71-120, 2020.
[47] R. Liu, Y. Liu, S. Zeng, and J. Zhang, "Towards gradient-based bilevel optimization with non- convex followers and beyond," Proceedings of Advances in Neural Information Processing Systems (NeurIPS), vol. 34, pp. 8662 8662-8675, 2021.
[48] R. R. Tyrrell, Convex Analysis. Princeton University Press Princeton, 1996.
[49] S. Kakutani, "A generalization of brouwer's fixed point theorem," Duke Math. J., vol. 8, no. 3, pp. 457-459, 1941.
[50] D. Bertsekas, A. Nedic, and A. Ozdaglar, Convex Analysis and Optimization, vol. 1. Athena Scientific, 2003.
[51] M. Hardt and M. Simchowitz, "Course notes for EE227C (spring 2018): Convex optimization and approximation," 2018.
[52] R. Liu, X. Liu, S. Zeng, J. Zhang, and Y. Zhang, V'alue-function-bae based sequential minimiza- tion for bi-level optimization," IEEE Transactions on Pattern Analysis and Machine Intelli- gence, 2023.
13

---

Supplementary Material
A Preliminaries
In this section, provide some technical preliminaries for the proofs of the lemmas and theorems claimed in the main body of this paper and the supplementary material, including parameter defini- tions and supporting results.
A.1 Inequalities
Basic inequalities used in the proof include
Strong Convexity: function fx) is strongly convex with modulus μ., then
f(z) f(x') z 11 || - x'11?
(20)
2
2. Young's inequality with parameter 0 > 0:
(x. v) S 20 | + 2 Elull?
Var,
(21)
3. Triangle inequality and reverse triangle inequality:
| + wll s | + Ilvll
|| wll
|
|1
(22)
4. Cauchy-Schwarz inequality
(x, 8) S ||
(23)
A.2 Notations
The definitions of the parameters and assumptions are further listed in Table 2.
Note that under A2 (i.e., compactness of the feasible set 2) the Lipschitz continuity of (ar,y) g(r, y) w.r.t. x holds. In Section C.3, we will demonstrate that the iterates (such as y" .y (w", z²") for which we need to evaluate the gradients or function values of g(r, y). (x),. and f(x, v) are bounded, which implies that the corresponding Lipschitz continuity holds. To be more precise, & Lg. Eg lg and others are listed in the section of notations in Table 2.
A.3 Primal Error Bounds
Recall that the definition of K K(x, y. we 2; 2)
K K(x, y, 2; X) fæx v) M(g(x,v) g" -z) -
| w|l2
F1ly =11
(24)
2
Based on the assumptions listed Table we have that f.g are gradient Lipschitz continuous. Further, it has been shown in [34, Lemma A5] that Vg"(x) = Veg(z. for any y" e S(x) and g" (x) is Lipschitz smooth with modulus Ly + (2/1g)- Therefore, the Lagrangian L(x, y: X) gradient Lipschitz continuous with parameter
13
L L L
2Lg +
(25)
241
Subsequently, function K K(x, y. w, 2; A) is strongly convex of z and y with parameter p and gradient Lipschitz continuous with parameter
Lx A I L
(26)
Given these property and the assumptions listed in Table 2, we can obtain the following primal error bounds that have been studied in [33, Lemma 5], [32, Lemma 3.5 and Lemma 3.10] and [36, Lemma
14

---

Table 2: Summary of Definitions. ("Lips.": Lipschitz; "grad."; gradient; "const."; constant; "opt.": optimal: *." represents the gradient is taken w.r.t. either z or y; "[æ; y)" symbolizes the concatenation of x and y; PEB: primal error bound; DEB: dual error bound.)
A1
Definition
Annotation
VV y) V V.f('', Ly x x'1
grad. Lips. const. of f(z, y) w.r. I grad. Lips. const. of f (zz y) w.r.t
Li
V y) V.S(E, S Lylly s'll
Li
V Vug(2, y) - Vug(o,z))1 / Lglly I'll
grad. Lips. const. of g w.r.. y
A2
Definition
Annotation
X'
closed and bounded
imply (grad.) Lips. of fig w.r.t
A5
Definition
Annotation
Pg
|V vl, v)1 2 2p-(9(2,)) 9x)))
PE. condition
Parameter
Definition
Annotation
ds(z)(1)
eise) 1ly 1/ll
min distance from y S(x)
Ds
max, d2
((x) (w) (cf. (33))
upper bound of d (u)
Dww, X)
mill,yy K(x, 1, W,
x" (w, 2;
arg min,,y [ V, w, 2;
opt. solution of D(w, 2; X) w.r.t. x
y" (w,
arg min [(x, y, W. z; X)
opt. solution of D(w, z; X) w.r.t. y
P(w, 2)
minz,9 maxogAgA (x. y, W; 2) arg min,, maxosAgA K (I, w, 2; arg minn,y maxogAgA w,, (w,2)
E (w,
opt. solution of P(w, 2) w.r.t.
V" (w,22
opt. solution of P(w, 2) w.r.t. y abbreviation of w,
Notation
Definition
Annotation
f
I(x, f(x 5 Eylly v'll
Lips. const. of f(x y) w.r.t. y grad. Lips. const. of g(x, y) Lips. const. of g(z, y) w.r.t. y Lips. const. of g(v, v) w.r.t. x Lips. const. of g" (z) w.r.t.
Lg
[V.g(z, y) V.g(2',))1 _ Lg x I'll
19 y) ((x,v\)l <4y111
t
(19(x,)) 1000gg((',) ,(x', < x'Il
e
[1g((x) g='))" = (cf. [34])
[V -V Vi'''.
grad. Lips. const. of L() w.r.. x, grad. Lips. const. of K() w.r.t. 2, const. of PEB w.r.t
(cf. (25))
LK
L + (26))
σi
L) (27a))
02
(p + Lpp-- - L) (ef. (28a))
const. PEB w.r.t.
03
(p (p- L)-1 (cf. (29a))
const. of PEB w.r.t x" or y
Teaa
(1+ + (,) (T) L)) (cf. (80)
const. of weak DEB
Faux
(Ly + + ALg)/ / / /2p (ef. (94))
const. of auxiliary DEB const. of strong DEB
O Ustrong
0 weank T aux (cf. (100)
B.2]. To more specific, from [36, Lemma B.2] we have
(w, 2; - y" (w, 2' S
p
||
2 ||
(27a)
L
_
|| (w, 2; x" (w', 2; A)
σ1 || w/
(27b)
11 (w, 2) (w z') < σ || z'11.
(27c)
| (w, (w',,, x) < σ || w ||.
(27d)
Similarly, following [36, Lemma B.2], we can also have
15

---

11 (w, - vw,, X)I < p L
1
XII
(28a)
[w, 2; 2) - x=' (w, 2; X) - 02 A
XII:
(28b)
and from [32, Lemma 3.10] [33, Lemma 5] can directly get
11 - v²ll
(29a)
|x (w", ; - x'|| 5
03
1 x'|1
(29b)
11
+ aep - 1,)
ll 20:", - -1 v
110 - 8"11.
(29c)
a(p L)
1 + 1p - L)
[w="("" (w",,";;"""" x+;)+++) r +|||| S
||0 =1'1l
(29d)
1p L)
where the primal error bounds (29b) and (29d) hold as R (which used for updating x)) is also (p- L)-strongly convex and (p L)-Lipschitz smooth.
A.4
Outline of the Proof
We will begin by presenting the contraction property of the block-u update in Lemma 4. Next, we will show the primal descent in Lemma 5, dual ascent in Lemma 6, and proximal descent in Lemma 7 by following the update rule of SLM, which will be used to construct the potential function. However, these lemmas alone are insufficient to establish the decrease of the potential function to achieve the (1) convergence rate, as mentioned in the main text. Hence, we prove the strong dual error bound Lemma 3 by combining the weak dual error bound presented in Lemma 2 and the key auxiliary lemma in Lemma 8, which ensures the homogeneity of the dual error bound.
With the strong dual error bound established, we can demonstrate the sufficient decrease of the potential function in Lemma 9. This, in turn, leads to the final convergence results shown in Section Section D. Throughout the process of proving the lemmas and theorems, we initially assume the boundedness of the dual variable, as well as y 5" 20", y² (w", = =>"1). We then verify these assumptions through mathematical induction, which are shown Lemma 11 and Lemma 12.
B Convergence Analysis
We now present the proofs, related results, and technical details that establish the lemmas and theo- rems of our convergence analysis.
We first show that the contraction property of u-update for the value function.
B.1 Contraction of Auxiliary Variable
Lemma 4.
Under AI, A2, and A5, Assume that the sequence {x" y", w", x" w. N,, Vr) is generated by SLM. When
1
S min
(30)
I.g 211g )
we have
2 (1 2711y) TxT (g(x", - (x"))))
d' (w (1)
(31)
Further, obtain
& SSter( (1 s (1 - 27/14) T" Ds Yr
(32)
where
Ds A 2p, (max (x, un) min (x:))" ta No E B(R).
(33)
16

---

Proof. According to the gradient Lipschitz continuity of function g(2, y)
w.r.t. (cf. A1), we have
g(0", 2/+1) S g(0", u4) - >VV u,), u441 - -47) + 9
(34)
2
(a) S g( u4) V ut 2f 122 9 VVug((" "u](""
(35)
S g0 ( 2 V uf]l
(36)
where in (a) we apply (5), (b) holds when S 1/ Lg
Under A5, have g(x 1141 (x") S g(0", , u,) - 9 (x") 27 (g(x", u() - (x")) s (1 2)))) (g(x", u/) 9 (x')
(37)
(38)
From [35, Theorem 21, we know that the PL condition implies the error bound with the same con-
stant, i.e., d3 ss(or) (uf) S 2/Lggg(x' uf) - g=(('") which yields
d S5er) (u +1
(a)
Ls (u7..)
2 (g(x", u(t1)) - g²
(39)
Mg
2 (1 27H4n)" TM (9(x", ug) 9" (x²))
(40)
Pg
where (a) holds due to the line 7 of Algorithm 1. Combining the facts that X is compact and u" is initialized within a ball gives this lemma directly.
B.2
Descent Lemmas and Dual Ascent
B.2.1
Primal Descent Lemma
Lemma 5.
(Primal Descent) Under Al-A5, suppose that the sequence {x", (,",v", w", ,²,""," ,==,u", , N", Vr3 is gen- erated by SLM. When
0 O<Ta5 LK" o<B5l, and T" 2 -2log (-0(1)2700))0 (X (X+11 11 Vir),
(41)
then the primal descent inequality holds, namely.
K [(x++1 +1*+1_ -=+11 ,1+1, x K(x", .v, ,²²²=;²²)
1
S | - x x11 + (g(x", ,3²) ) g" (x²) )- 8, x - x²)
4n
Mg DgL
110"t1 - y211
p 2 rr1 - =2r122 p 11 - 10 +
(42)
2a
233
2
p2
Proof. x-update; First, recall
V Rx"" t w", r+1 u 11 x x
A V (x",""" "1=") - (Vg(("), - V.g(=", ((((x,,=+))) urt1)) + p(x - w²).
(43)
From (8a), one step of the projected gradient descent step gives
K(x++1 y ++1 w", rt, x-11)= K(x", +1 w", r1,, x²11
(0)
Lx
<V (x", ++ r+,, x x r+1 x²) +
|
r+1
x² 1|2
(44)
2
Lxx
<(VR (x", +1 11 r+ X ((11), r+ x²)
|| x² 12
2
+ (VK(x" n. (h4 - vk (x" tt w +1 w x ar xxr) (45)
17

---

where (a) is because gradient Lipschitz continuity of K (xx, U, (, 2; is with parameter LK.
From the optimality condition of (8a), we have
(V R(=", ( v w², 2 u ( xr x²) S - | x0111
(46)
Regarding the last term at the right hand side (RHS) of (45), we have
(VK(w', yf t w", tt A-11)= vR(x", y²t w', xz u x ), x-- x²)
$ <n/V V w", 2 x (R("", y w. 20 wtt1, 2|1 + 11 - x²1
4n
where we apply Young's 's inequality with parameter 2.
For the first term at the RHS of the above inequality, we can further have
IVK((", y w" 2 1 VR(a", , w², 211 u + yrt111²
$ <A
Vg(e", ut )²
(47)
$ (Ar+1)21, I ((rr) (u 11
(48)
(32)
< (N L (1 27,gg' "M Ds
(49)
(2) Mg D2
(50)
mr²
where in (a) we take T 2 2 (17(1))) (A*+1 Vir).
Substituting (46) and (50) back to (45) gives
K(**+1 y 2 x K(x", n1 , S -- -1
- x²12 --
D
Mg
(51)
x²
where we select S 1/LK-
w-update: From (6), we have
K (x: -y=!! - 1,=1, (1+t1) - K k(xtt1 ..rt..rr "ott,,w ",, 2rt1 (rt1)
P (11=+11 112 || w' 1
(52)
2
2 (w" r1 1 =+1 + x - w')
(53)
p
1 w0
(54)
2
where (a) holds due
(w0 w011 , x x- rr1 + x-+1_ -w")
(w" =+1 ,200 x0+11 w + n" w x w²)
(55)
1 - 2
|10 - 11
(56)
and (8b) for 3 S
X-update: According to the dual variable update (7a), we have
K(x", .y",, w", x²; K("", y", w", ="; XT) (g(x", v²) 9" (x") 5, 1r N³. (57)
y-update: The update of y shown in (7b) is the standard gradient descent, which gives K(x", tl, w x+) k(x", 1², w", 2"; (
< (VK(x', .v w xx;x++11 + - w" + LK |1 - -
(58)
2
1 || - y² 2
s 2a
(59)
18

---

where a S $1/LK.
z-update: Similar the w-update. From (7c), we have
k(x", K(=,v"* "y w", t x+t1) - K(x", v +1 w², ,²; x S
p 2
|1= - -2112. (60)
B.2.2 Dual Ascent Lemma
Lemma 6.
(Dual Ascent) Under AI-A5, suppose that the sequence {a", V", ,"", by SLM. When p > L, the dual ascent inequality holds, namely,
,,,,,,, w,, Nr Vry is generated
D(w+1 , ,
1,=2) D(w ;²)
(A*+1 X² x²' (w", ,² x 8 (w" ;2;; xx+11) - g" (2 6))
P (2 xrt + =" 2y (w", ;
+
p fwwtt1 -w", w + w² 2x (w" (w"+) tt ;
+
(61)
Proof. Recall
(,, 2; & L(x, y: A)+ + P |I - w/12 + - lly - 2112.
(62)
2
2
Then, we can have
D(w", 2"; (*+1) - D(w",2'; x² K( (w", ;1:1011,, 1, 1n (w" , ;2; ( w², , ;1121
K(x (w", 2²:; ;²),y' "y (w² ;
2 X²), wi, ,2/;²²)
(63)
K(x (w", 22 ;1; ), n (w) zi; x(++ w² z²; (1t1)
K( (w", 2²; xx+)),, ) (w" 25: x w", :²:2²)
(64)
-X N", g(x" (w", : x ,, (w" , ;x )) - -g" (x" (w" (1=;=(;1~') -0-))
-))
(65)
where in (a) we use the definition of y" (w", 23; x+1) for L. Similarly, we have
D(w", 22",, (rt1) - D(w", 2"; (1;
=K(x" (w", ,rtt; :,rtt), ),y, (w 2 ( w., ztt ( )
KK(x(w", (w", ,2; ;²; (1++t),, ), (w", ,z; xrt1), wi "2 (1-1)
(66)
2 K K(x ( x ),y (w) t1 ( wm 2 1tt t (tskk
- K(x"(",, ,1 x ), 3/ (w", r1 ( ) w", :²; (
(67)
P (Ilv (w", (,""=""""" ; ( = + 112 1/ (w", _1 (1+1 - =='1(2)
(68)
2
r+ = P/ (2 - 2", 2t + - -2y (w", 2 ,1, x x ))
(69)
2
and
D(w ,2t11 xx+1)-- - D(w" /132 (ik (iii
)
hiikk iiii 'itut m i = K(x'(w"*3 , x '/' m1 t1 ///h t1,, )
- K(x'(1i (w", rrt : x ). /8 (w) 11t + (1t) )
(70) (70)
> K(xt(wtt1, , , x ), 1/ (w0 t1t n
' tinug  (1)
?
)t11 ( ا
- K(x (w -+1, x-1 m2) tt1 t1,, i
(
mm )
(71)
P (1I="(u) (w r1t,, ( x w 1 - || (w T1 ttt )
-
mm 133)
(72)
2
P (10- w., w + w0 - 2x 2w"(w" (wr+1 _ ; x(+1)))
(73)
2
19

---

which give the desired result.
B.2.3 Proximal Descent Lemma
Lemma 7.
(Proximal Descent) Under AI-A5, suppose that the sequence fx² yf w²,,, ,²",,"" erated by SLM. Assume that y" is bounded and p >> L, then the proximal descent inequality holds, namely.
u. X Vr) is gen-
P(w*+1 ,uu"+1,2+t1 ,2 P(w",2)
S pp(=+t1 (=" - -jj -j(((' (w", ,²²)) + p(w0+1 - w w='' - , 2z)1))
+ 2 p
p p- -T +1) +1)++1 (11= 101 + 11w0 w0 11))
(74)
Proof. First, note that (xx y. w, 2; A) is strongly convex w.r.t. x and y jointly with parameter p L. Under A2, A5 and the assumption that y" is bounded, we can obtain that V V(P("", ;"("""")) p(=" ""w"","" by applying the Danskin's theorem in the convex analysis [48]. Then, using the primal error bound (27c), we can show that V=p(=") has a Lipschitz constant, i.e.,
P 21 VP(w", ,2)) S
P p p- L
11 +1
- -
(75)
Therefore, it is straightforward that
P(w", ( - x²) S p(z - (2 x²=
P
p -- + +1)
p
(76)
2
L
Similarly, we have
V V , - P(w", , S S
(
p p- +1
p
| will
(77)
which gives
P(w*t1, ,0+,,,,2+1))) - P(w",2""" 22+ S p(w - -ow""t--""''
- x² (w"
p D-L L 1 |110t1 - w²1
p
(78)
B.3
Dual Error Bounds
B.3.1 Proof of Weak Dual Error Bound (Lemma 2)
Lemma 2 (Formal)
Under AI-A5, suppose that X, 5" (w, 2) are bounded and p L, then the weak error bound holds, namely,
1 (w, 2; A4 (w, 2)) - 8d (w, 2)2 + (w,, 2; X+ (w, 2)) - x² (w, 2)12
S &weak
|| \ (w. =]][||(w,,> 2) A (w, 2)
(79)
where
1 1 T(2 + 22)02
and 02 p+p L
weaak
2r(p - L)
p L
(80)
Proof. First, let
(+) = P. VV (o (1 2)]
(81a)
A(e) E arg max K( K(='(v) (v). A))
(81b)
OSASA
20

---

Based on the strong convexity of (x,,,, w. X) ",, and K(. w, A), we have
2;
(1) K( (e; A+ (v)). (1)) (1))
Σ p L
(v) (82a)
K(= (GTT0AAA4))))0)000000)0000
2 P L
-1) - (82b)
2
(o K(o (c: X+ (v)): (1),
- ((), (+))) (82c)
2 D-L
2
2 p I
|a (x)=: (82d)
2
Note that (v) is the maximizer of the following problem.
7K(x" (v; (+)), v A+ (v)), v; (0 OSASA
max
(83)
where
= + (0)
- (x" (o: A). (v: 2);
(84)
According to the Lipschitz continuity of V,K, we have
A < (1) - All + + X+ (v)), (v;
(+))) (0)
- (w:
+ Tllg" (x= (x: A))I
(85)
(a)
2 (1 + (26, + ()))) | (v)ll
(86)
where in (a) we use the primal error bounds (28a), (28b), and apply the Lipschitz continuity of g(.) and g" ().
Based on the definition of (v) (ef. (8la)), we have <K(x (v; {= (w)) y (o; X4 e; ((
<TK(x (1; X+ (v)), (r)) (o)
(87)
Subsequently, we can obtain
<K( (v: A (v)). ( (10p::/00kkkk0kkkk///raooaaa/aaa
- S (A())) (v))² X( (86) $ (|((w) - (+)Il (1 + ((2g + Ey 02) /| (v)l
(88)
(89)
According to the definition of X(v) (cf. (81b)), we have
K (v). (w), v; A(v)) > (O)
(90)
Combing (82a) to (82d), and (90) yields
2r(p L) (1ly (v;
5 21 (x)))))
< [|A(() - (v)] (1+ + (2) - (+))l
(91)
Therefore, we have
11 (w", ,²x;; A (w", z²)) (0(" ",,,2")](== ||00 (w" , 1 A (w" ,²²)) 3z' 3"(w", 21
1 T22,, y + ly 02 | ,,",,,='' ,²²) - \ (w","")] ,²')]]-
(92)
2T(p- I.)
Bawsk
21

---

B.3.2 Proof of Auxiliary Dual Error Bound
Lemma 8.
Assume that A1-A3, A5 are satisfied and that the local regularity condition holds. Suppose that X, 22 (w; X) are bounded, then the following inequality holds.
[1 2) x+ (w,z) 2)ll
Jaur (1lv" (w, 2; X4 (w, 2)) - (w,,2) 2)1l + 11=== 2; X (w, - x² (w,,, 2)1)
(93)
where
L + ALg
Fnnt
22
(94)
Proof. From the optimality condition of the block-y update and by following the notations defined in the proof of Lemma 2, we have
fx)( (v)) A(e) g (v) (v). p() 2) 0,
(95a)
V vyf(2"
(u)), (1;
(u; A+ (o)))
+ Vo)gv (u; (o; (o: (u))))) +pw
(1; (4:44(0) - =0 (95b)
Taking difference of these two equations and using the Lipschitz continuity Vyg(s), have
(A(v)) - (v)) V (v))
(1;
+ "A V (1)) A+ (v))) + (l)) y v0( (o;)+(1)))
< (L, + + AL,) (v) - (" (v)) |1** (x)
(96)
Further, we know that the left hand side (LHS) of (96) has lower bound, i.e.
[(A(v) A+ vo ("))ll
(A(u))
(v), (+)) - -()))-
(97)
& A(v)) - (u)l 24p
(98)
where in (a) we apply the PL condition, and (b) results from the regularity condition.
B.3.3 Proof of Strong Dual Error Bound (Lemma 3)
Lemma 3 (Formal)
Assume that A1-A5 are satisfied and that the local regularity condition holds. Suppose that X, o (w, 2), Vr are bounded and >> L,, then the strong error bound holds, namely, there exists constant O arong such that
Ily (w", 2² X++ 22)) - (w"'2"")l + || (w", 2² Nx+ "w" (2"))))) ""))""(w'' ,²')] 9" (w" 2² (2+))++)))= -
(w"",, (w",²"
S 20 arang (g (w", z²; ;; ), (w" x(;A++1))
(99)
where
L + p + ALg
Tstrong
Tweak Taask
Oweak
(100)
/ 2pn
Proof. Under the assumptions that p > I., and X", """", 7" (w""w,"" are bounded, combing (14) and (93) yields the following strong error bound.
2 Nx: (w",=")) I" (w", "00", + || (w=" (//"""""""" 2²; a (1"))"))) x² (w", (=w'=""0 x²)) 2
< Tweuk: aux || \w =z)o]l
(w",,";;" N,"""(""",""" ,,n))""") - 5 (w", 22"22" + (w",,,,,,,, "00")"")) - x² "w" ,((,)))))))
22

---

which gives
lly"(",, 2²;47 (w=, - F'("", + || ("",,";;,"""
24;47 (w0,2 x² (")
< stson |1 xx"1(2",, (w²,2"))
(101)
(81a)
< 20 stong T (x (2" (w", '²"; ;²;1 3" (w" , ,";;
(102)
< strong g0x (w", , x "0 (w' , ((: 9" (x" (T: -|.
(103)
B.4 Proof of Potential function (Lemma 1)
Lemma 1 (Formal)
Assume that A 1-A5 are satisfied. Suppose that the sequence {x" .y, w", 2", ut, N², Vr) is gen- erated by SLM, p > L, and X ,3",, .ū" (w", x²") are bounded. When T, a, T" respectively satisfy (41) and T -2 (1 2214)) (VFr), then, there exists a constant Ç such that
2(x t1 wt" r+ , :
2(x", ,y" ,w,," ;²=;²")))
(7r (e2 + 23)00
11r"tt-x"0
9r
903
1 11g y012
41
n12
2a
a²
1
2p
+ 30ço4) ||a 2=112 P
1
(1
p-=)) 110 w0ll
2p
P 2B
+
p p-L)
p-b
23
+ 36pc ( ,00,2'' :z';,²7 x (w", ,2)) - ='(w",, ,=)11
+ 36pc 11y (w", x² x+ ;")) - 5 (w", 21)
56 48p
v((x(w"' 2'' ; (w", ;2 (2 (w",2";11)1)) 812
Ds
L | - XlI2
+ (ngLig + 2(g)
1-
(104)
72
where
Q Q(1 v. " 2;,2 A K(x", 21:2) - 2D( x 2P(w", (")) (105)
Proof.
Recall that
=-= =K=",>,, v", w x")="; - 2D(w", ,0'=,";))) 2P(w,2z')
(106)
Merging (42), (61), and (74) gives
@++1_ Qr
1 |1 - x211²+ 1
1/" - -1112+ + P
11 |12 - -0,1++1-2211 -2711++ 11 w011
4n
2a
2
233
+ (g(x" -4²) - (x²) 6, -²)
2(x+1 N², "x," (x' (w" ; 3 (w" 2=: ((++1)) -='=0""('"p00> (x"("" , (r+21) -8))
-p(2++1 2" x" r + x" - 2y (w" - x )) 2p(2** r+1 - =²"" (1" (w" ,=²) - =²)
27:
p(w=+1 w,, +11 + w - 2x (1++1 21 ((+1)) 2p(w"+1 - (x"
(w" (w",2+11 w")
S
p p- T. +1) (1 - =0111 + || w=1l2) + M 1 Ds
+ p
(107)
p2
23

---

First, we can get the upper bound of term Ti as follows:
T (2 2 -2 -2 (2 (V"(,, 1 ; - (w", (2²)))))
-2(2 -2",2"+1 -2- -2 23"(w( (w", (2"","t :2 ;,++1)=== y2 (w", wu',z" 2²;1)))))
- -p -0'.0 ;
: - 1f (w",=") ,²")
(108)
=-pllz-t1 - ==112 + 2p (srt1 - =²", y (w",,, , = - 1f (w" (,;=,)))))))
- -p(="t1 - =²",0" (w", "==,,"";"""""""" x1;++ 5J (w", ,²))
(109)
For the last term of the above inequality, we can further have
p (2 2",,,' 3" (w", 2 2=; - (w",,²")
p1|=+t1 20122 DC
2( + 2
lw"" , Vy ,2""2,"")11
(110)
For the second term of (109), we can get
+1 2², 1 ( ,2 - (w", :² :2::a+11))
(4)
|| | =5 =111l1>* (w", z ; 1/' (w", ; x
(111)
(1) p
|| - 211
(112)
p L
where (a) is true by applying the Cauchy-Schward inequality, in (b) we use the primal error bound (27a). Similarly, we have
T2 (w w", wr=1 w" -2 2 (x'2(((1)))))))) (1 ( x² (w,, 2r+1)))
-p (w w", w w -2 2xx (w 1 xx" (w" xrt21 , ((tttt
- w0 10 2p (w"tt - ww,, x² (w r+ , ) "x (w, ; (113)
p pw w", xx (w",2"t1, ,, :1+11)
(w" ,r
- (w w", x ='(w,, , - 3 (w", ))+
(114)
For the last term of the above inequality, we can further have
p( w",""""," xx=
xz (w",,"+1) ,2"+1)) ",,""" (w", x² ,==,,==+++++ ;1>+1)===-
p|lw-+1 w01 pc ||- (w" , +1; ..' (w", 2
(115)
25
In addition, we have
(wr+1_ wt, xx
xx=xx((n (wr :3:t1;+t1 - yww,, (w", 2111;
WV (6 (a)
1 w/ w"ll|| (w]l="(w"++ ett xr+1) x "w", (
(116)
p
| 11 11rrt1-0001 10
(117)
p
where (a) is true by applying the Cauchy- Cauchy-Schward Schwarz inequality, (b) we use the primal error bound (27b).
24

---

Substituting (110), (112), (115), (117) into (107) yields
2
1
-
+1
x2
+
111 - 1²(13)
41
20x
1
2p
+
1| - =1
23
5
p L
2p
+ p L
|1 - w0
23
MoLiDD Ds
+ pC (10"(w", ,
; x ,
- =w'",, , ,2 + ",=""""";;""" 5/ (w", 20))3)
p2
+ (a(("" .1" - (x²) - 6, x X")
- 2(A - ,', g(xx(( (w", , ; yn (w", x1 - g0=
(x* (w" 22:2 8)). (118)
Second, we will give an upper bound of the last two terms of (118) follows.
Step 1.) From the update of the dual variable, we can have
1 11 - (g(x", ,V¹ g0 w tt 8, x N2
(119)
7
which is equivalent
-(g(t", .1²) g0 - - -2) S 1 1 - 2r11..
-,
(120)
Therefore, we can obtain
(o(2", ,0) g' 6,2 -
(o(x",1") g" (x") 6, x' -X"> + (g(0", ,1" "(0""20+) - -6, - A7)
(0(x", ,v¹) 9((x, ) -6,r+41_ 27
(121)
2(g(x" .v") - -9" (x") 6, X²) + (x²) g( , ,, 2,, X²)
-1 11
(122)
Subsequently, we can derive an upper bound for the sum of the last two terms in (118) as follows.
2(g(2", .2") g¹ (x*), -")
2((g(0 (w", ; ( ), / ; ( - (x" x ;1tt X7)
+ +ar+1 - N6 (x") -X g(0", x(+))) - -11-- 2r11
(123)
(4)
< 47 (Ila("", w²) - 96 (x") - (g(x" ;= ), 30 (w", 2 ;1; (x (w"",,,, ,"',, ())
+ +xllg"(x") - g(,", w² 11 )11 2T
|| -x112
(124)
88 (2(e) + ( || (w", ,2;,; x²; - x=11 + + 1 2 (1: - -1(1
1 | 22
+ (x") - g(,", w (rtt)) )11
(125)
2-
(1)
2((2 22)
12
$ 2TO
r x² 12
+
+1 112
n1
a
TTllg" g( wr+ 2
- 2112
(126)
2T
where in (a) we use the Cauchy-Schvee inequality, in (b) we apply the primal error bounds (29a) and (29b).
25

---

Step 2.) Applying the reverse triangle inequality, we can get
|| - 2112 || - x (w', (2" + x -
(127)
| (w²,=")= 2-12 || (w",
(128)
According to the definition of d (wo, 2²) (cf. (8la)), we have
|1 - - (w=,,"))²
(2)
1 || + =0((x" .v" g(x"=1 g(x", ,ut - | + + (UO {r1
2|| - -2111
27² (119(2", .y"" - g(0", u w²t (0(x=(00;;
(v ;10=;=+]] x - g0 (((;xx)))
I 2|| x²11²= + 67 (2(gg + f9)1l=² - 20"0 (0"; (- 6 yy" - 3 (=(
+ Gr 11g(", ut 1 g" (x
(129)
where (a) is true due to the nonexpansiveness of the nonnegative projection operator. Also, we have
|A XT+ 22'²"
D - [1rt1 + TV>K(a (x"; (u"; 3/ (v"; ) u"; ; x*1
(130)
(U' y² uf
- (131)
2
Combining (128), (129), and (131) gives
7
| 21122
2
|TVnK(>* (0'; (0', (0"; 00
4
- (2 + 19)1==" - x" x +
- - (1
- -673119(0", "00(""","""1 - 2x
(132)
Applying the primal error bounds (29a) and (29b), we can obtain
47 1 -
- V>K(x + +,,,),,, ), (1==)++))))) ), {1
56
37 (2(6, + 11) - x (u"; x M12 + Ello" -5 \1 + (la((", w - 9" (ax)) (13)
7
(133)
T1 (10","",, ,,;"; (1;++)), ) (w", 2"; Ar=))111) g" (x (w" 25: 6112
56
37
2(e2 + 22 103
|,""" +1 12
9
2
11 - + 11 1l9(=",('t)) g" (x
g=((=((") (0)))p)
172
a²
(134)
26

---

Step 3.) Substituting (134) and (126) back to (118) gives
Φ+1
1
17T
+
230
1
97 2
-x"11 ||
11y y²12
417
112
2a
a²
1
2p
11 -=-112 D
1
p p-L) L ) 1100 |100
2p
2)))
w0ll
p
23
(
p- L
p
2B
6 +
+ Upc (Ilv* (w", ,2
(w",, ;2)) + |1="("", , ,2
x= (w", )1²)
T
10(5 (w", ,"";,";,">>"=""="<<,,' ; v/' (w", ; xx+))) (x" (w", ,²;; ;=;; ((+))) 512
56
Mg Ly
+ 2rl1g(x', w w(th g" (x |2 -
(135)
p2
Finally, by observing the weak dual error bound, we need to further quantify I1v"((",, 2"=","";'+') - y (w",, (0u,,"")] )1? + +1Ix0
(w", , : 5" (w", t )|( as follows. Note that
(w",,, ,²;) - D" (w",,, = 011 + || (w" _ ( x² (w", , )1
S 11 (w", :=;;; (1-11)- - g"("" , 2²) 212 + 3|12* (w" 20: 1- x² (w", ,²' !1
+ (wl,, tt, ; - x² (w", 20;
|| + 31 (w² ; x² "w", 2
(136)
(0)
3 211y* (w", ,²'; x (w", 2²)) 8 (w", x 1| + 61|z (w", ,²; x , - xz (w", 1²))
+ 211y" (w", =5; x 15 (w", z x (w" == )1
+ +611=* (w", x x² (w", 25: x (w 2n) 1| 60 - - 2-12
(137)
(6)
_ 2/1y" (w", ;²; X (w" , ;) - "" (w" , ; ;²1)] + 6112 z"; xx+ (w", ,-T) x (w",, )1??
+ Sožr² (1g(x" 2²; x=11),, ) 34 (w" ,f; x)+1)) g(0" (w", x 1 b1|
+ + -| - 111
(138)
where in (a) we use the primal error bounds (27a) and (27c), (b) holds as we first apply the primal error bounds (28a) and (28b) and then use the definition X+ (wr, 2) as follows
||^++1 x (w", ,"')]]
= =1 - P20 [xr+] + TV (K (w5, ( 1. (w",, ;2;; 22;, II
(139)
$ <T <T|1g(>'('' 2";; ) yn (w", 22: - g(a""("," ( - 611
(140)
As result, we can get
Q²+1_ º"
(e7 + E23003
97 0g
|1 - -x"13-
|1 - -22
4n
1/2
2ax
a²
(² + p + 336022 11=+t-=²11
2p
23 - (7 + 1 )) || |1u0t1 -
11
2p
- ==112= - P
P 2B
+ +3ppC (1ly* (w", : (w0", x²)) 8- (w", ; + 1| (w" ; "
(ww", ,²²)) - (no", ,
48p(o3r) 19(x"("", (w", ; ). 1/ (w x1; 9" (z"(w' (w",2";;""""" ((xx() - 2)2
56
My L3Ds 22
1 | 2112
+ 2T (lllll",,trt) wrtl) 9" (x*))1 4T
(141)
Lemma 4, we know that (u)t( S (1 (1- (11271)))*' T7 Ds. so when T >
From
-2 (VTT)
DsgDs
2T110("", w( - (x3))
(142)
72
Substituting (142) back to (141) gives the desired result.
27

---

B.5 Descent of Potential Function
Lemma 9.
Assume that A1-A5 are satisfied and that the local regudarity condition holds. Sup- pose that the sequence fx² .y, , ,=",,"""""" "X""""V X.rr is generated by SLM, p > I, and N N V (w, 2²), V.v" fuu",2"; 2"; ()+1) are bounded. When the step-sizes are chosen such that
1
(p-1)²
7 min
1 min
Lg 2/g
LK 136T(E, + + L
(p-
10-14 L)
(p - L)
1/(126 48)
a S min
T min
LK
36T E2
3456pS (p L)
pc m Saong 02)
T" 2 max
-2logg 2711 (X++1 /īr)), - -2log1 11011-27p. rVT].
1/4
- max {
1 1
0
1, <W
1 S
(143)
2p
+
305 (p-L)T
[1'' [2
TG3
{ P-L
then, we have
2'+1
Q"
S 1
xx r++ x²11 112- 1 11y 8²113-
P 11 -2112
p
w0
24n
12a
123
123
gg(x" (v'; (0";>²+1)), (v"; (00=; - 9x' (=";A\+))) 812
189
- 4r
Ds 72
- + (ug و 2(
(144)
where 6 strong A o O O and G1, S2, C3 are defined in (171) and (174).
Proof. From (104), it is clear that if we can select the step-sizes properly so that the coefficients in front of || 12, Ily y 11 || 2 1/ || w²|l are strictly negative, then the potential function Q" will be decreasing, To be more specific, the step-sizes are chosen as follows.
Selection of 1). Given the condition of (41), we request
(6 g
+ 22)
17T + (7)
> 0,
(145)
41
172
Am
17 L)2
811
i.e.
(p 1.)2
1)
1367 (12 E L
(146)
2) Selection of
1
9T 2
1
9T
1
(147)
2x
a²
20
a a² (p L)
4a
i.e.,
(p - L)
a
<
361 P2 T22
(148)
11
3) Selection of 3,
2p
1
+
+
36Ç0
>
> 0,
(149)
23
p
L
48
i.e.,
1
3 <
(150)
4
+
2p
+
3
p-L
(p- L
4) Selection of T.
28

---

We need
1
1
48pÇo2 2
> 0,
(151)
56
63
i...
(p - L)
7 T
(152)
3456pC + L)
Then, consider the following two cases:
Case 1.
max
1
| x² x=11 11 -0112 P
43 4g - 2512 P
433 11l1 111
w=11
8n
4a
T
19(x" (w", = ; ),1" (w", ,²"; =²;)+t))) - "000"""(("0000000""""" (ww,2" 12')1?
(x0 (wo ,²; ; 812
63
max (36p( [1V" (w", 2²; x ;,,)²))) - (w"",
+ +1|="(w,, ,0"","" 2"; x (w", 2²")) x² (w", (w',z")] =²²) 0T}
(153)
where / is some parameter. In this case, have
② O' S
12 +1 - x²12
12a - -111 123
21 -2"112-
Iw" | w=11
24n
12,3
189 10(x0 (0"; ))) (r" - 9" (x" (u' ( 812
0r 1 | x1 + (ngL2 +22)) 72
Ds
(154)
meaning that Q" is decreasing up to some constant at each step.
Case 2.
|| x=11 110 - -21?,
43 4 -1
P
- 2712
| flw - w011 --"'-w""""
P
max
8n
4a
43
1g(x" (w", ,2 ; 11 (w", (2,,,";",,>""""""" x²;x++1)) - 9" (x- (wo" ,f; 2x"", 63
T
812
< m3xp(3 (1lv" (ww", "uu,"" z²; x (w" z²)) 8J' (w" 2²
||00 (w", ="; x (w", ,²²)) - 5t (w", (w',2')l'" =²')]²²) 0T).
(155)
First, if 36p (1l"" (w", , 2;; X (w",²") /" (w",, 2 I12 + (w",,";;;; I" (w"))"))1²) 2 0r, then we have the following results.
Recall the weak error bound
1 (w,, 2; A+(ww, (w, 2)) D" (w, (w. =)1 + || (w, 2; 2, (), 5² (w. 2)12
S &weak || - X (w. 2) =| [1]) 2) - X+ (w. =)ll
(156)
where A(v) E arg maxosAsA K(# (o))
We get
ly" : A (w", (,"))))) - ="("", "(wT,=") 21 + (w", (w", xTxx ,²")) x' (w",=")]l
S Sweeat 2AT (v"; (0"" - g( "0"=
- -511.
(157)
An.
which gives
(w(, (w='2";Att)) v, (='',(;x+'1) (w" , -8ll < 3-366 63 36p (158)
29

---

Then, we can have
P || - 2011
48
I 3- 333pp (Ilv" (w", 2"; 2²x (w",²") 22)) - (w", 20)," + ||00 (w", (w",2"; 10;=""(""==== ,²") - ='("", ; 2²))1²)
< 3- v w ||9((" (w", ,"", ;²;2 (w"" ; )²+1) g((2(( (0="("""'">""""""""'">'" ,=',,"=;''" )) -81 (159)
<² 63 13-36"pp p=ppppp"" p2
(160)
Similarly.
1 81)
1 4a
1 - 1/1
P 4/3
1100 - -
{ 12.33.... 63. -3-36''p"" 366
=
(161)
These results imply that the iterates generated by SLM will converge to some point within a ball with a radius of (o))
Further, note that
||w"" - x² (w", xz") =²)11² + ||=" y" (w", (==,
1|02 - -x1+1 + x²
x² x'(w", 2²") 2²? + || - -yt + grt - (w',2")
< 32 (Iw - _w' 112 + || - ==1p²) + 2 (1 - (w", ,²) + 11 - y 21)1))
32 (Iw - ww'] 11 + || - =31))
2
+ 211x==11 - x² ==',,, ,²: ( + x=(w" , ( - x=(",==") =²)112
+ 211y*+1 - v'(w,, 22'; xx1)) + 3² (w", 22 (2++)) - y² (w", =1?
(162)
$ 32 (1ww - w² 112 + || - 1²)
+ 41|1=*1 - x² (w", "W"","" z²; )1
2 + 4|1=" (w", :2 - xx' 2²0) + 411y - y (w", ,²;; X x )|² + 44|yy (wo, 21; - 10 (w", ;00,²)) =1)
(163)
By following the steps from (136) to (138), we have ll""ww", =";ar))))))) - 8 =1) + || (w", 2"; x - x'' x0)?
< 21ly" i (w", ;") 5 (w), , + 21|x"(w", x"; (w" (w", 2²)) xz ,'",,, 2²)
+ 22lvv(w x y" (w", 25 XF (wo, 1²
+ 2|1=* (w", 22 ( - x (w", 2f x (w", 2²"))]²
(164)
$ 21ly" (w", 20: x5 (w", 2²) 8 (w", 22 20)1 + 2||2² (w", 22 2²'))))) - i'(",, 2 ')²
+ 40377 ||a(0" (w", : x
). y (w", ,z'; x+;x) g(0" (w", 2²' ,1;x++1)) - 61|² (165)
Combining (163) and (165) yields
1100 - =x'(w" = )12 + ||= - n (w" , )1²
(166)
) n(p - L)
1+ n(p [1
1 2 |100t1 - x- 1|2 + (1 (1+ 2
<4
alp L) l 11 yr1
2
(1wrt1 - -w" 1|2 + 1
+
ge
+ 8 8llu0(() (wT,2 x
x "w", (w",)")) - & 2² )12 + 8110 (w", x ;²²)) - =²' "w", """, l2
+ 160z7² 2 ||0(2* (w", (w","";'' ;²;;a+1) ),8' (w", ,"; ( 1) - (x" x";"""=-"" 1) - 611
(167)
<8 4n 1 1+ m(p
L)
1 1 1 Lb)
8
+ 2a
+ pB
32.63 - 36 p² 2
1(pp - L.)
alp L)
+ (8ō + 1. -33 -88-63-25 . 36)(ow)) (3 63 36p(ow).
(168)
30

---

Therefore, once
+ 1pp - 1b)
(1+0(p- L:)
8
8 4nj
n(p L.)
+ 2nx
aapp
a(p L)
+
pg
3 63
p6
+ T + 16 (3 63 36p( (3 63 36p(ow) 2 O(1,
(169)
i.e. ( small, then, Lemma holds automatically. We can simply choose
$ 5
max '1' C2
(170)
where
(1+ (1 I.)
1 nlp mpp
)1)) 2
2 1 (1+a(=-14 ( a(p L.)
8
Ç1 =3336p5
+20
+63 160372, (171a)
1/pp
p3
C 8-33 1.3.000 63 36pro
(171b)
Second, 36p (Ily 2"; (w"
8" (w",, 2²)12 + 11"" ="; X4; (w", ,2))) -
(""",, 1)) I Ur, then we have the following results.
11e² - x² , 21)11 + ||2" - yy"ww, "0),2
$ 12 ( 1
(1+
npp - 1.) -
7pp - L) 1 8n +
(' 1 app - [.) 2
480r
20r
a(p (app-I) L)
4a 0r +
+
+ 63 480
3p
9Cp
(172)
It is obvious that when @ is small, then the RHS of (172) is less than constant 0(1), i.e., when
5 Taa
(173)
where
(2)
7(p L) 7pp L)
+ a(p 1 -L) a(p T.)
48
2 9Cp
Ga 12
817
4ax
+
+
+ 63 480 (174)
3p
then, Lemma 8 holds automatically.
Given the strong error bound, substituting (103) into (141) yields
1
|
1
11
1/ 11
=1112 3-
P
-1"' w1
81)
4a
43
12pC
(30
strong + +402)
(0'
8)2
63
Ds
1
+ 1ا + 20))
-
-
(175)
p2 47
Following (152), we also require
12p6 (30 strong + 400)))
(176)
63
126
i.c.,
(177)
126
(3o
4o²)
126 48p{ max (oaamog o
When the conditions shown in (146), (148), (150), (152), and (177) are satisfied, we can obtain
2r+1
1
x²112 - 1 11 1/112 |
433 2 -2"112-
I| w"
811
4a
4,3
T
g0(2" (0"; ((;i++1)) v"",;"(";;"" (0";)++)))= 9" (x"(0") (E"; ( 81
126
+ L + 282)
Ds
_ || 2r112.
1
(178)
p2 47
This completes the proof.
D
31

---

B.6 Equivalence of KKT Points between the Saddle Point Problem and Constrained Optimization
Lemma 10. Consider the following two problems:
(P1):
min =EX.y.o(z.)) ( (*) fz, v) + 2 11 =11²+ + 2 1| - w|l
P
(179a)
(P2) min max f(z, v) + Mg(x, - g (x) - 6) + P lly - 2112 + 2 w|. (179b) mEX OSASA
2
Let x² 1y, w ,,,"",,,,,""" ,2,, X denote the KKT solutions of P2. If + A, then the KKT solutions of P2 are also the KKT solutions of Pl.
Proof. is easy to check that the primal stationary conditions of Pl and P2 are the same. Regarding the stationarity of dual variable X, we can apply the saddle point theorem. Note that problem P2 is strongly convex w.r.. y and concave w.r.t. y and both feasible of z, y are compact. Then, there exists saddle point such that
(g(x", ,y" - g²(xx* 5) 2 N(g(2' ,3" - 9" (x*) - 8),
(180)
which gives X in following three cases
A
if g(*", v4) - (x*) 8 0,
X
if g(x v - 9r (x*) = 0,
(181)
if g(x", -/ 9" (x*) 8 0.
If X* f A, we can obtain
X 2 0, (g(a"" -""") 0,
(182)
which are the KKT conditions of PI.
Given this result, we can know that P(w, 2) defined in (10b) becomes
min P(w, 2) =EN.v.a(a.)) (2)5g f(x y) + P > w|1
P + 211 211
(183)
0 < A. Therefore, when the iterates converge, the dual variable is strictly less than A, the converged point is the primal-dual (KKT) solution of the original problem.
C Boundedness of Dual Variable, LL Variables, and Potential Function
C.1 Boundedness of Q"
From (13), we know that
Q" v", "y"""w" 2")"";")
=K(x",'' ,","", ",,"" x²) 2D(w",2' 2";x""") + 2P"",,27
(184)
-(Ww" 2²") + K(x", vf, , w "0",";;00 (²) - D(w", ;²;;²"=;))) )++ + (P(w",=') - =Dw"">";>'0 ;²))
(185)
P(w", 2²) 2
(186)
where (a) holds due to 1) K(x", y", "=,,"="""" D(w", x²) 2 based the definition of
D(w", ,²";," X*) and 2) note that P(w, z) min maxosAga f(x, y) + >(g(x, y) g" (z) 5)
2| - 2||2 F1yy 2|I2 and P(w", 22r) -D(w", ((w")"";")) 2 0, which is true because the minimax equality theorem [49, 50] holds when K y, w. A) is strongly convex in y and linear (concave) A.
C.2 Boundedness of Dual Variable
Lemma 11.
32

---

Under A1-A5, suppose that the sequence {x" yy, w", =", u", X", Vr) is generated by SL.M. sume that X" ~ 0(1/V8), ~ O(1) are bounded. When 0 < < 1, choose O(1/x+)), Ç. (8)-a) such that p L. I L/LK, B S 1, then, X will either be upper bounded by for at most (11/8255) steps or there exists a constant C such that
T= T
dj O V8
A> dj
X
(187)
V8
In addition, when 8 > 1. choose 3 (1), then, \ O(1)
Proof. From (7b), we have
x yf a aV x Vog("' (2)) + plu" -7))
=
(188)
Applying the triangle incquality gives
|| V "g(l", v/ - | - v0ll + , ('")l + plus" 2"11.
(189)
If 1 < X" then x is bounded immediately. Otherwise, note that
V || Vug(=", .v'Il
(n) 2
*+1 2 3²)) g(x,; y² (x*)))
(190)
X
V 210g( (0((xx""''))))" yy) - glx,, w²) + g(x", , - ,0x", (r(()))))
(191)
22g (x++1 x²) 5 g(* u²) g(o", 1² (x*))
(192)
where (a) holds due to the PL condition and nonnegativity of X, in (b) we use the rule of the dual variable update.
Then, we can obtain
Ily y" + VyJ("" ,,",'")' + plly" - 2"
X+1
(193)
244 (Ar+1 - Xr) + 8 + g(x", w²) - g(x", , , - (z²))
11y +1 1r + Vy,(x", 3²) + plly" - =-11
(194)
24 (Ar+1 - x²) +
where (a) follows from the definition 9" (xx"), i.e., g(x",,""" u²) 2 g(x", "/ (x")). As X Xr, can further have
1 111 8ell + <
(x* vnlll + pluy" 2"1l
(195)
v8
Note that the LHS of (153) decreases on the order of (Q) - frrr. with the lower bound of this quantity being Dr. Therefore, according to (153) and (155), we can know that the iterates will be either in Case for certain number of iterations (i.e., at most O((Q) (((("=f)/il f)(()r) steps) or in Case Case 1, the projection operation (i.e.. P+I.) can always ensure that X++1 is bounded by so L. In the following. it can be seen that the dual variable is automatically bounded, implying that the projection of the iterates onto the upper bound will be always inactive when the algorithm is in Case 2 (i.e., X" < A)
that we can choose
In Case 2, when 0 8 and the following conditions are met
1 1
77, a =
p= p== O(x",, 3 = 01813), == (L),
(196)
33

---

and assuming that X = O(1/V)), we can have ow (1) due to (157), 0 = O due to (153),
@l = (1/V88) and
11 - z²1² (198)
O1ly
501 + - /31) - O
(161)
(197a)
1161)
11 v²1 v O
(197b)
where we use
11y + 1²t z"1 S 11 ++ -2'l + - - ==
(198)
Then, (195) can be written
x 11 +1
v'1l
+ E
pod 11 -
X=1
+
(199)
00v8
V8
where we choose
p 1++1
000
(200)
X-+1
By utilizing the step-sizes as specified in (200) and substituting (197) back to (195), it can be easily checked that the first term of (199) is (641/22++1 /oo), and the last term is Oppo)++1) From (161),
it can be seen that when Ç is small (or cquivalently So is small, where B (150) 3002.5), there must exist a constant e such that
di 0
1
Xr+1 S
(201)
v8
Vo
When 1, it is easy to check that when 3, r = O(1), p 1(A++1), we have X =0().
Given this result and Lemma 10, we can set the tunable variable A as @(1/V8). After rumning the algorithm for T steps, if the last dual variable is A, i.e., the projection of the last iterate A is active, then, we need to increase A and regenerate the sequence.
C.3 Boundedness of y", 88 (w","") ,²"), and (w",, 20;T,
Lemma 12.
Under Al-A5 and the local regularity condition, suppose that the sequence (x" yy ,","",, ,", 2",u", X", Vr] is generated by SLM. Assume that y" (ww",,"" bound- ed. Then, we have ÿ (w++1, (wrt1,z+t) 2"++), (w", x y are also bounded.
"0' Proof. We prove these results by induction. First, we assume that y", """ (w", "o0,"") 2²") are bounded, which gives the (gradient) Lipschitz continuity of g(x, -) these points.
Let ART A p (T Ds/rrr 2 (xz,z) f(z, v), X, y (vlg(x,y) g" (x) - 6).
Recall the bounded set level assumption that let
(202)
Under the assumption that y", ("""" are bounded, we can have the descent of the potential function up to AR that decreasing sequence. By the fact that (w p1+ 8" (w z1+1)) < P( r11), for any (x .y w 21; there exists constant R such that
(w- (1"+1,2r-11)
,r+t)) @-+1 + AR' C B(R(a) SUR ,,,21,11)
(203)
which gives that (w"*1 (1+1) is bounded.
34

---

Applying (14) shown in Lemma 2 gives
11 (x", :=: X (w", 2²)) " -" (w", ,z")1
(4)
(w0", @weak /weak//Artt X (w", ""))"ll(("",,>"" - x (w", ,""||
(204)
(157)
$ 0 (VoNT (1g(0 ( 20: (";;,,) g0x=0=000 (w="
;2;; ,"; - 81]
(205)
(0) 1 x((88)
(206)
where in (a) choose т (1) when 8 > 1, we have X, X, O(1), and we choose
step-sizes according to (196) and also apply (158) when 0 < 8 s 1. So, we can have that y² (10", ="; x (w", =²)) ~ ((Vō) is bounded. Also, it can be checked that
1 (w", ; ) y (0",,, 2" (2'','))I]
(28a)
S p + I
| x+ (wo","")
(207)
p L
(4) p+ L
2 p L (u'; v''' - (0 (w;;a)))))) - 5)ll
(155) S O(r)) ~ 0(1
(208)
where (a) holds due to the nonexpansiveness of the nonnegative projection operator. Therefore, y" ("o",, ;"; x+11 is bounded.
) is strongly convex with modulus p I. and gradient Lipschitz continuuus with parameter p + L. From [51, Theorem 3.5.], we have
Note that K(x,, 2; x
p I.) p+ p+L) L) 110" -v"("" 20;,,"";"+11
1 ("""" 2"; x1;++1)11 < 1
(209)
which directly gives the boundedness of y*1
D Theoretical Convergence Results
D.1 Proof of Theorem
Proof. KKT Conditions.
For v, y, W.F, 2, A, we define F map such that F(x, y, w. u, (x+,,** wn+ where (a+ ,,,,,,,,,,. aut,,t,uu ut, _++) is the next iteration of Algorithm 1. It can be easily checked that the map F is continuous and if x. V, w, 2, u, X is fixed point of F, i.e., F(x,, y, w, z, u, A) (x. y, w, z, u. A), then (I, U, A) is pair of primal-dual stationary solution of problem (1). Suppose that
=-, ut ,0,==
*)).
(x".v", w., x" ",,,,'" + (z, J. w. E, a. X) along a subsequence E T.
(210)
Notice the lower boundedness of Q" shown in (186) and Lemma 9, we can get
||x: - 2"1l +00, I1 - v'll + 0, || - 2"|l +
(211)
and
[o(x"(w'' 2 ( y (wo, , ,,;,,;;,, x²;; (--t)))--+ 96 (w0, ;²; )) - + 0, lo(0", (0)-g"(00)) + 0, which gives ||,0+1 wIll 0, -1 ا|| 0, ||-1 xr 0. and further implies
(3 t1 +1 11 +1 x (a '², w. 2=," n. XD o.
(212)
35

---

Therefore, we obtain
F( W. u. - (Z, X]
(e)
lim |1 V. w², ,², ,,,," F (x" yy, , w", ,-", ,0)
(213)
10000
( lim D0,
(x"t1, y wrt1 2t uit x F (x" vf w 2" xy]
(214)
where (a) holds due the continuity of J. and (b) follows from (212). Hence, (3, y, X) satisfies
| (z Px(T - V x))) 0, $ TEX, 0, (215a)
stationarity:
v,f(z.g:
- feasibility g(..0) - 0.120, 0,
(215b)
complementary slackness: (9(3.)) 9) (z) -0) =
(215c)
i.e., every limit point (æ. X) is primal-dual stationary solution (KKT point) of problem (1).
Stationarity of Primal Variables. Recall
g( = 1 (x Px(x" - V y,; ;())))
(216)
vyf(I',y'';N
For the block-2, we have
1
(x -xx(x - V/V V. ((AII
17
(11x011 x01l + || Px(x" (V.i(<"', (V.g(""'
(0(a"//)) v/ - - )))]
77
1
(311a² r1 + V.. V.I(=", nル ,1" V Vzg(ø' y/ - II)
17
+ +
V Veg(z", u +1)+ V2g" + + X V 30) V (x") p|11=" - w0
3
+p || - x1 + P || -w'l
17
+ (Lg + Lag (1(r+1)1ly +1 1'll x Lyds(ar) (u t2) + 2e - X-1
(217)
3
+ p)
|| || x²| + P
3
f w/ (L, 1,g v'll
7
+ +2g7 g(x", .v") g(0", 2( -81 x L Lyds(ar
(218)
20T
110 - x01 + - will
+ p+ + 17pp- - L)
PGT
+ Li + Lgg011 + alp L)
11 - 8²ll
+ 2lgT gg(" (w", " ;2;; 1f (w" 20; ((:t)+))) - g" tw", (w", (2;;x+1)) - 6
+ (2ep + r+ Lg) (1(
(219)
where in (a) we apply the following optimality condition of the z-subproblem
r+1 px 1 -n Vol(=",1'" +1
(Vgg""" vag(x", (u w(+1))+ p(x- - -w") + 1 (
(00t)- (x)t1-x1))) 1r))
n
36

---

(b) results from the nonexpansiveness of the nonnegative projection operator, and (c) holds due to 1g(x' (w", ,="; ; yy (w"; == ="; - g(x","'' ,v")
)
lg - 1ly w/ + | - x-11 )
S ーール a
(220)
and
Ey 11 - x²|l
g (w", 2² ((tt))) 9" (x")) s 7pp L)
(221)
For the block-y y, we have
I y fx=" v/; X"Il
y (x" 32) + X V 1g(x", w/'ll
(222)
(4)
18g - y''ll + fg/A - x + - 2-1l
(223)
- +p 119/ |1/ - - lg 1 - x11+ 33
1
P -11=-t1-3 =
(224)
a
1
11 - 1/1l + l ,/¹ g(x", "d=x,,t+1)) - 81 + P g1 -2
+ p
(225)
a
3
1 + u(p - D)
PgT
2
119 11g - Tp L) | x' 11 + -1 2='1
+ +gg (w" ,0; 1 ) (w", (,",=";""''' xx)) - g" (x"("", 22,=,"
+ ( (1
(226)
where in (a) we apply the following optimality condition of the y-subproblem
Vyl(a', + V v²) + p(u" =²" _ (1 =
-
(227)
and (b) comes from the update rule of the dual variable, i.e., the second line of Algorithm Therefore, the primal optimality gap can be quantified as follows:
|| ,""'
2
3 (11 L. Lgg
28 7/pp
55
+p+
+
1100 1|x0 - x112
17
L)
1pp L)
a(p - 1.) )
2L9
PgT
) 2)
+5
+ +p+ alp 1.) )
110 11 2
+ 5p²
5p2
82 - w01l2+
8² 11 - 2212
+ 2563-1(((2" (g((( "g(x"("",, ,²,;,"+11 " - 9" (x" (1)+))))+++))--- - -82
+5 5 (2lgT + + L.)) + 2g²2) (S(e)(("+)))
(228)
From (144), we have the following three inequalities.
The first one
1 } (110+11 - x=112 + 1111+11 ( 00 - - + (Mg + 2et) (229)
Ds
min
2-112+1100"
224 12a
p²
The second one is
Ds
123 (1 w012 122 + -111++1-2-113 < Q - Q + (Mg 20%
- 2511²)
(230)
,
37

---

The third one is
189 1g(x ( ))) (u"; g'xx'("";; -x"x"("";x~t11 - -8
Ds r²
S Q - (11T22) + 2((
(231)
Then, let
1
P1 min
(232a)
24r
12x
3
2Lg
2L
P2
max
5
+
p
+
1ppp L.)
T/PP L))
269
Pg alp L.)
5
b + L. x +
+
-
(232b)
a(p T.)
Plugging (229), (230), and (231) into (228) along with (232a) and (232b), we can have
|| 0"(2"
P2
+
60p
25 189697)
(0r - erti (MoLi + 20%)
Ds
P1
B
,²
+ 5 (20 + ( x + +g70) + (s(ta)(((+)))
Note that according to (32) we have
12 - (1-211))) T" Ds S D2D
(233)
p2
when T" 2 2y04, 1
Applying the telescoping sum over r 1,... T yields
|1(2))11
T
T
<
P2
60p
+ 25 - 1896
Σ
-
T
P1
8
1=1
+
1
P2
60p
+ 25. 1896()
(ugL3 + +222
Σ
T Ds
+ (10 4567²
Ds Σ r=1
T
P1
B
72
,2
r=1
(a)
1
P2
60p
+ 25 1898
(0'-
$
+
T
P1
3
1
P2
60p
+ 25 189637
(HgLiz + 2(2) (10 150+2))77)) Ds
T
3
where (a) results from the fact Σ r 1 1- f1 = 2 -1
We can obtain the convergence rate based on the following two cases: 1) 5 > 1 and 2) 5 < 1.
If 8 > have Ar+1 O11). We choose
Xr+1 p= O(X+t), 7 0(1), 5.B = 0 5,)= T" = =R(log X²11). (234)
such that the step-sizes satisfy (143). Note that as Ç satisfies (169) and (173), it leads to e O(v))
and the strong error bound being true automatically.
38

---

0 < 8 < 1, we choose
71, = (XTTT p 5,3 0(3)) T= T-)),, T" = =[(log \rt1); (235)
such that the step-sizes satisfy (143), (169), (173) and (177), which leads to O(V8) and the strong error bound being true again.
Finally, it can be easily checked that when > 1, according to (234), we can have + Ez= 11"""1 v²)1 < O(1/T), when d s 1, obtain
( [x+11
02 = o(
p = 0
o = O(p)
(236)
P1
B
82.5
which gives + D |9(x", 5'' < (L))
Constraint Violation. Similarly, we can quantify
10(0", :/" - g (x") - 81
1g(x", 1²) g(0", u x111)= g000, -
- g=((x") -0
21g(2", ,y') - g(o", w wn+1) 812 + 2/g(2', "000="22"+1)
w(th) - 9" (x)) w(1l)= 9xx"))
| - 11 + 21g(("","++)
where (a) holds due g(x", xr+l)= portl--g' g²(x") 2
From (144), we have
2
-
2T12 V 7
8 Q' -Q--2 2 + ( 21g) Ds
72
,2
Applying the telescoping sum yields
T
g6 y²) - -x"(x") - -812
T 1=1
(4)
8 Q + (1 L3 + 20%) Ds +
422Ds T
(237)
T
where (a) results from the fact Σ -2 S +
ST x 2dr T- Therefore, when ò > 1,
select step-sizes by (234), which gives 1 Σ 10(=", .v)) (x") 513. = =O(1/T): when
0 < < 1, we choose step-sizes by (235), which gives 7 IT= 1g(2", - -x" - = (l)(VTT))
Slackness. If X O. then it is trivial that [g(=", 5²) - (x*) 8|25 is zero. So, we only need to consider the case where X" >> 0 as follows.
39

---

Step 1. Note that
la(x", v²) (x") - 612
S 31g(2", ,y" g(2" (w", 2²; ;²;;x+ (x"",,"""""""""
+ 33gg(" 2"; x ","" ,';2 9" (a (w" 21; - 6|2
+ +31g" (x' (2"; X -))
(238)
s 66 11 (w(",, x
( x ( 211
+ +3gg(0" (w0" ;² x ) 1. (x',
9 (x" (x'(w,, ;x;;tt)) - 612 (239)
6l2
11 r+ v 1|2 + 3(26g g )
$ a²(p 1
1 r+ - x²11
17 L)²
+ 331g(2" (w", ,² ;²; ), ",y" (x' 22 xxt))
9" (2" ,';,,"=;=++" 8|
(240)
3
26 26 +
82
g
g
(1 - 1'11 + |1y0-1 -3)
max
(p L)²
a² 272
Apa
+ +3)g(0" 2²; ;²
1r ) (w", (1=) - (x= ((x'(((0,,,;;;'; - -|
(241)
Step 2. Then, we can get
T
lla 10(x"+1,)"+1) - 9" (1( - 8112114+1112
T
1
T Σ
P3 (1 || - 112 + /11 - 112 |1
+ 3/g((1 (1)t) ; 1/ (v 1, ( 9" (0 (o= (1))
(242)
3. 189
max {22 2' f + (ugLi + 229) Ds
< P1 +
T
where (a) holds when d > 1 we have X+1 = 011, which gives 11g[ y )²
-x(x+++1--
5 ++1 ||2 = O1/TT); when 5 I 1, we have ps/P1 P1 = 0(1 111//>+1,, |X 112/7 S 0(1/5), so we
can obtain [l y ) g²(x"t1)- - 1| = ((1/(8%/T)).
40

---

E Additional Numerical Results
In this section, present additional numerical results obtained from the Fashion MNIST data set and compare the performance of SLM with other algorithms, such as BOME [15], V-PBGD [16]. BVFSM [52], and ITD[13].
85
SLM d 1.0
SIM 0.5
BOME PBGD
test accuracy
04
SLM A 1.0 SLM & 0.5
test loss
BOME V-PHGI
54.1
120
200
400
600
822
1932
number of iterations r (a) Test loss
number iterations P
(b) Test accuracy
Figure 4: Convergence performance of SLM, BOME [15], and V-PBGD [16] on the neural network with the fashion MNIST data set.
E.1 Fashion MNIST Data Set
We also evaluate the performance of these algorithms using the fashion MNIST dataset. The neural network architecture employed is the same as in the previous case. For all the compared algorithms, we set the step-sizes of the block-r and block-y updates to 0.1. The step-size 7 for the auxiliary block-u update is set to 0.01. Figure 4 illustrates that SLM with = consistently outperforms the other algorithms in this example. This suggests that allowing for certain tolerance level for the LL objective can enhance generalization performance. The convergence rates of all the algorithms are similar. However, it is important note that both BOME and V-PBGD fail to achieve the optimal solution at the LL level since there exists a discrepancy of Cerror = 0.78 for V-PBGD and Cemor 0.42 for BOME. Consequently, none of the methods can find the KKT points of problem (2) in this particular case. Nonetheless, SLM can attain the KKT solution of problem (1) with Cemor values below and 0.5 respectively. This further underscores the advantages of utilizing this class of structured constrained problems compared to the BO formulation.
E.2 Comparison with BVFSM and ITD w.r.t. Runtime
In addition, we conduct a numerical perfor- mance evaluation of our problem formulation and SLM algorithm on a different data hyper- cleaning task described in [15]. In this par-
test accurary
ticular setup, clipping function is applied at the lower level, and the training data consist- s of 50, 000 samples. We compare the per- formance of SLM with two other baseline al- gorithms: the bi-level value-function-based se- quential minimization (BVFSM) algorithm in- troduced in [52]. and the iterative differentia- tion (ITD) based bilevel optimizer described in [13]. The results of these experiments are presented in Figure
2.00
2.56
1.4
SLM
BOME
V.PBGD
FED
HVPSM
100
200
300
433
500
600
700
800
902
time
Figure 5: Convergence performance (test accura- cy) of BOME, SLM, V-PBGD, ITD, and BVFSM.
important to note that in this presentation, we plot test accuracy against runtime to ensure fair comparison. The outcomes of the evaluation demonstrate that SLM achieves higher test accuracy compared to these existing benchmarks. Furthermore, the convergence speed SLM closely aligns with that of V-PBGD and BVFSM.
F Ethical Considerations
This work primarily focuses on the design optimization algorithms and the theoretical analysis of convergence. It does not involve any negative societal or ethical issues.
41


Reviews:
[{"review_id": "jLTHydQhPu", "reviewer": "Reviewer_7siX", "summary": "This paper studies structured nonconvex functional constrained problems and proposed a smoothed first-order Lagrangian method to solve it. The proposed method decomposes the complexity of the problem by introducing a proximal term. Convergence of the proposed method is also studied. In general this is a well-written paper and the results are interesting.", "questions": "Assumption A2 only requires the feasible set X to be compact. However, in the top layer, a projection operator is used. If the the set X is compact but the shape is very irregular, there can be multiple distinct points in X that is closest to x. In this case, how to define the projection operator? Will different choices of projection operator affect the convergence of the proposed method?\n\nFor the numerical experiments, if the feasible set X is irregular, say a star shape in R^2, how to apply the proposed method and what is the performance?\n\nIf the PL condition is not satisfied, numerically does the proposed method work?\n\nWill the complexity of g or f affect the error and convergence rate theoretically and empirically? I do not see it from Theorem 1.", "limitations": "Limitations are discussed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "A new method to solve nonconvex functional constrained problem.\n\nConvergence of the proposed method is analyzed,", "weaknesses": "More numerical experiments will make this paper stronger.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer 7siX for your helpful comments and questions.\n\n*Weaknesses: More numerical experiments will make this paper stronger.*\n\nWe have incorporated new numerical results, including new loss functions and data set partitions, as well as two additional baselines. Please kindly refer to the general response and the attached file for further details.\n\n*Q1: Assumption A2 only requires the feasible set $\\mathcal{X}$ to be compact. However, in the top layer, a projection operator is used. If the the set $\\mathcal{X}$ is compact but the shape is very irregular, there can be multiple distinct points in $\\mathcal{X}$ that is closest to $x$. In this case, how to define the projection operator? Will different choices of projection operator affect the convergence of the proposed method?*\n\n**R1.**\nIn A2, we assume that the feasible set $\\mathcal{X}$ is a type of projection-friendly set, implying the existence of a closed-form projection operator. This operator ensures that a single projection step keeps the iterate within the feasible set. Your concern is indeed valid, and we will additionally incorporate the convexity of the set to make the assumption more reasonable and clear. Under this assumption, the projection operator will not affect the convergence of the proposed method.\n\n\n*Q2: For the numerical experiments, if the feasible set $\\mathcal{X}$ is irregular, say a star shape in $\\mathbb{R}^2$, how to apply the proposed method and what is the performance?*\n\n**R2.**\n As mentioned in response to the first question, our current method is unable to handle cases where the feasible set is irregular.\n\n\n*Q3: If the PL condition is not satisfied, numerically does the proposed method work?*\n\n**R3.**\n Based on our current experimental results, even when the PL condition does not hold, our method can still work without theoretical guarantees.\n\n\n*Q4: Will the complexity of $g$ or $f$ affect the error and convergence rate theoretically and empirically? I do not see it from Theorem 1.*\n\n**R4.**\nThe smoothness constants of $g$ and $f$ characterize the properties of these functions. They essentially quantify the differences in gradients at two different points. If these constants are large, it implies that the gradient of the corresponding objective might change rapidly, and vice versa. Both of these constants are located in the numerator of the theoretical convergence rate (please see equation (174) in the appendix, where $\\sigma_4\\sim\\mathcal{O}(L=L_f+L_g)$). This indicates that if the gradients change significantly at different points, the method requires a greater number of iterations to achieve convergence.\n\nIn our numerical results (refer to section E), we employ various datasets, resulting in different empirical loss functions. Figure 3 and Figure 4 illustrate distinct convergence behaviors among all the compared methods, indicating that the shapes of $g$ and $f$ also numerically impact the convergence."}, {"review_id": "aDO0ZlLSNt", "reviewer": "Reviewer_aS1n", "summary": "This work studies a class of structured nonconvex functional constrained optimization problems, where the functional constraint satisfies the PL condition w.r.t. one block of variables. The authors propose a smoothed first-order Lagrangian method (SLM) and establish the theoretical convergence rates of SLM to the KKT solutions. The authors demonstrate the application of the proposed SLM to bilevel optimization problems where the lower-level problem is nonconvex. Several experiments are provided.", "questions": "Major comment 2 above is my first question. The following are others:\n\nQ1: In Line 268, why does the strong error bound immediately come from (14) and (16)?\n\nQ2: In Section 5.2, why do we set $\\delta=1.2$ in Line 308 for the data hyper-cleaning problem? Why not choose a smaller one? Is the performance sensitive to such parameter? \n\nQ3: Could the authors add the figure of the test accuracy and F1 score in the comparison between SLM and V-PBGD on the data hyper-cleaning problem?\n\nMinor comments:\n(1) In Line 124, is the ball open or closed?\n(2) In Equation (4a), why is $g^*(x)$ smooth? It is generally not smooth when non-singleton at the lower level. When $g(x,y)$ is strongly convex w.r.t. $y$, $g^*(x)$ is smooth and its gradient does NOT require the computation of the Jacobian matrix and inverse of Hessian by Danskin’s theorem.  \n(3) In Equation (5), $u_{t}^{r+1}$ should be $u_{t+1}^{r}$.\n(4) In Line 165, does $y^r$ be $y^{r+1}$?\n(5) In Line 1 of Algorithm 1, for $r=0,1,\\cdots,T-1$ do.  \n(6) In Corollary 1, the $\\epsilon$-stationary solution of the bilevel problem (2) does not defined.  \n(7) In Line 233, “result in 1” should be “result in Theorem 1”.\n(8) Correct the expression of $y^*(x^r, \\lambda^{r+1}; z^r)$ between Lines 249 and 250, and in Line 252. Also verify the expression of $y^*$ in other parts of the paper.\n(9) In Line 258, correct the definition of $\\lambda_{+}(z)$.  \n(10) In Line 322, “optimal solution” should be “optimal value”. \n(11) Please update the references.\n\n\n", "limitations": "The authors discussed part of the limitations in the conclusion section of the paper. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "(1) The paper is easy to follow. The structured constrained optimization and then the bilevel optimization has not been well studied. Finding an effective first-order method is both interesting and important. \n\n(2) The proposed SLM algorithm achieves a near-optimal convergence rate for finding the $\\epsilon$-KKT points under certain conditions. The three-layer structure of the propsoed method is interesting. The experiments in Fig. 1 and Fig. 2 support much better performance of SLM than other same-type methods in this area. ", "weaknesses": "Major comment 1: BOME in Table 1 also covers the nonconvexity and non-singleton case, as described in Section 4.3 of their paper. So SLM is not the first work where a first-order method is capable of finding the KKT points of BO problems in the presence of nonconvexity and non-singleton at the lower level, as claimed in the main contributions of this work.\n\nMajor comment 2: For Regularity Condition in Line 201, why does the KKT solution is unique? Is the feasible set convex, and if so, why? Why is the constant $\\underline{\\delta}$ independent of $(x,z)$? Is the Regularity Condition too strong?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer aS1n for your helpful comments and questions.\n\n*W1: Major comment 1: BOME in Table 1 also covers the nonconvexity and non-singleton case. So SLM is not the first work.*\n\nWe have thoroughly reviewed reference [14] (i.e., BOME paper). We acknowledge that SLM is not the first work capable of finding the $\\epsilon$-KKT points of BO points in the presence of nonconvexity and non-singleton at the lower level. The primary contribution lies in the fact that our derived achievable rate of SLM is $\\mathcal{O}(\\epsilon^{-2})$, whereas BOME achieves $\\mathcal{O}(\\epsilon^{-4})$. We will rectify this mistake and the associated statements.\n\n*W2: For Regularity Condition in Line 201, why does the KKT solution is unique? Is the feasible set convex, and if so, why? Why is the constant $\\underline{\\delta}$ independent of $(x,z)$? Is the Regularity Condition too strong?*\n\nWe did not mention that the KKT solution is unique. This condition only intends to convey that given the point $(x,z)$, the constraint can be satisfied.\n\nWe did not make the assumption that the feasible set of $y$ is convex. We are considering the case where $g(x,y)$ satisfies the PL condition w.r.t. $y$.\n\nStrictly speaking, $\\underline{\\delta}$ depends on $(x,z)$. We partially agree that this assumption is strong, as it involves a global regularity condition. However, it is not excessively stringent, given that this constraint is nonconvex. To the best of our knowledge, all the existing approaches for solving functionally nonconvex constraints require a certain type of constraint qualifications, such as the CRCQ required in BOME. Therefore, it is necessary. \n\nThank you for bringing up this concern. In the revised version, we will address this issue by including a discussion along with a comparison to existing works.\n\n*Q1: In Line 268, why does the strong error bound immediately come from (14) and (16)?*\n\nWe apologize for the errors in the expressions of the error bounds.\n\nThe correct weak error bound or equation (14) is as follows:\n\\begin{equation}  \n||y^*(x^r,z^r;\\lambda^{r+1})-\\bar{y}^*(x^r, z^r)||^2\n\\le \\sigma_{\\textrm{weak}}\\|\\lambda^r -\\lambda_+(z^r)\\|\\|\\lambda(z)-\\lambda_+(z)\\|\n\\end{equation}\nwhich has been already shown in equation (87). And $\\sigma_{\\textrm{weak}}:=(1+\\tau L + \\tau L\\sigma_2)/(\\tau (p-L))$.\n\nThe correct strong error bound or equation (16) should be:\n\\begin{equation} \n|\\lambda^r(z^r) -\\lambda_+(z^r)| \\le \\sigma_{\\textrm{strong}}||y^*(x^r,z^r;\\lambda^{r+1})-\\bar{y}^*(x^r, z^r)||\n\\end{equation}\nThe reason is $\\lambda$ in equation (148a) should be $\\lambda(z)$ based on the defintion of $\\bar{y}^*(x,z)$ shown in equation (10d)\n\nBy combining these two results, we can immediately derive the strong error bound\n\\begin{equation}\\notag\n||y^*(x^r,z^r;\\lambda^{r+1})-\\bar{y}^*(x^r, z^r)||\\le  \\sigma_{\\textrm{weak}}\\sigma_{\\textrm{strong}}\\tau |g(x^r, y^*(x^r,z^r;\\lambda^{r+1})) - g^*(x^r)-\\delta|,\n\\end{equation}\nbased on the update rule of the dual variable (or please see equations (112) and (113) ).\n\n*Q2: In Section 5.2, why do we set $\\delta=1.2$ in Line 308 for the data hyper-cleaning problem? Why not choose a smaller one? Is the performance sensitive to such parameter?*\n\nThe hyperparameter is determined through cross-validation. The proposed method with $\\delta=1.2$ exhibits superior generalization performance compared to cases with smaller $\\delta$ values. We have delved into this topic more comprehensively in the appendix; please refer to section E for a detailed discussion. We have also generated explicit plots depicting the test loss across various $\\delta$ values. These plots clearly illustrate that the method with $\\delta=1$ yields higher test accuracy than when $\\delta=0.5$. This observation further underscores the advantages of our proposed model over existing bilevel formulations. In essence, our model offers greater flexibility for enhancing the generalization performance of the tested machine learning models.\n\n*Q3: Could the authors add the figure of the test accuracy and F1 score?*\n\nPlease see the general response.\n\n*MQ1: In Line 124, is the ball open or closed?*\n\nClosed.\n\n*MQ2: In Equation (4a), why is $g^{\\*}(x)$ smooth? It is generally not smooth when non-singleton at the lower level. When $g(x,y)$ is strongly convex w.r.t. $y$, $g^{\\*}(x)$ is smooth and its gradient does NOT require the computation of the Jacobian matrix and inverse of Hessian by Danskin’s theorem.*\n\nThat's a valid question. Even in scenarios where multiple optimal solutions exist at the lower level, the gradient of $g^*(x)$ remains unique as $g(x,y)$ satisfies the PL condition w.r.t. $y$. For more details, you can refer to Lemma A.5 in [Nouiehed et al., 2019 or 34] or Lemma 2 in [Shen et al., 2023 or 15].\n\nExactly. The computation of this gradient doesn't necessitate the calculation of the Jacobian matrix or the inverse of the Hessian. This characteristic is why our method qualifies as a first-order approach. In contrast, the conventional bilevel formulation mandates the computation of the gradient of $f(x,y^{\\*}(x))$, even in cases where $g(x,y)$ is strongly convex with respect to $y$. Additional information can be found in Lemma 2.1 in [Ghadimi et al., 2018 or 17].\n\n*MQs 3-5:* Yes. We will correct them. Many thanks.\n\n*MQ6: In Corollary 1, the $\\epsilon$-stationary solution of the bilevel problem (2) does not defined.*\n\nThe concept of an $\\epsilon$-stationary solution for our considered problem primarily pertains to a point $x^*$ that satisfies the following inequality:\n\\begin{equation}\n\\max  \\\\{ || \\mathcal{G}(x^*,y^*)||,|g(x^*, y^*) - g^*(x^*)-\\delta|_+ \\\\}\\le\\epsilon.\n\\end{equation}\n\n*MQs 7-11:*  We sincerely thank you for pointing out these typos. We will correct them in the updated version"}, {"review_id": "ME62A5TaXX", "reviewer": "Reviewer_Ggqj", "summary": "In this paper, a smooth first-order Lagrangian method (SLM) is proposed to solve a class of structured nonconvex functional constrained optimization problems, where the two optimization variable are nonlinearly coupled. The convergence rates are established by the dual error bounds. The proposed method is used to solve bilevel optimization problems with nonconvex lower-level problems. Numerical experiments are used to show that the proposed method outperforms the compared methods.", "questions": "(1) This paper is able to handle nonconvexity and non-singleton at the lower level. However, the assumption that the PL condition is quite strong. If there exist multiple isolated minimizers, then such a condition does not hold.\nThough [40] give a condition that guarantees the PL condition, overparameterization is not practical. Is there any example\nthat is practical and satisfies the PL condition?\n(2) In the toy example, SLM is notably faster than V-PBGD method. However, both V-PBGD and SLM have the same complexity O(\\eps^{-1}). Can the authors explain this?\n(3) How to choose the parameters in Algorithm 1? Any suggestions to improve its performance? For many optimization algorithms, their performance highly depends on the choice of parameters. It is important to choose appropriate parameters when compared to other algorithms.\n", "limitations": "This paper discussed the limitations of the proposed algorithm, which is to only consider a single constraint problem.\n", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) This method only uses the gradient information and obtains the optimal iteration complexity.\n(2) SLM can be used to solve bilevel optimization problems with the lower-level problem satisfying the PL condition.", "weaknesses": "These are given in the question section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer Ggqj for your helpful comments and questions.\n\n*Q1: This paper is able to handle nonconvexity and non-singleton at the lower level. However, the assumption that the PL condition is quite strong. If there exist multiple isolated minimizers, then such a condition does not hold. Though [40] give a condition that guarantees the PL condition, overparameterization is not practical. Is there any example that is practical and satisfies the PL condition?*\n\n**R1.**\nPlease kindly note that our assumption does not exclude the case where there are multiple isolated minimizers. For example, the function $\\sin^2x$ satisfies the PL condition, yet it possesses multiple isolated minimizers.\n\nOverparameterized networks are indeed a common scenario, particularly in applications involving large-scale fundation models. Reference [35] demonstrates that the PL condition is relatively weak compared to other existing conditions. In the realm of bilevel optimization applications, many studies assume the strong convexity of the lower-level problem. It's worth noting that strong convexity implies the PL condition, but the reverse is not necessarily true. \n\nAn example where the objective satisfies the PL condition can be found in the context of learning LQR models (please refer to Lemma 3 in [R]).\n\n[R] Fazel, Maryam, et al. \"Global convergence of policy gradient methods for the linear quadratic regulator.\" ICML, 2018.\n\n*Q2: In the toy example, SLM is notably faster than V-PBGD method. However, both V-PBGD and SLM have the same complexity $\\mathcal{O}(\\epsilon^{-1}$). Can the authors explain this?* \n\n**R2.**\nIt's generally understood that primal-dual methods tend to converge more quickly in numerical experiments compared to penalty-based approaches even they have the same order of the theoretical convergence rate. This is because the dual variable or Lagrange multiplier adaptively enforces constraint satisfaction throughout the optimization process.\n\n\n*Q3: How to choose the parameters in Algorithm 1? Any suggestions to improve its performance? For many optimization algorithms, their performance highly depends on the choice of parameters. It is important to choose appropriate parameters when compared to other algorithms.*\n\n**R3.**\nIn the numerical results, we opt for step sizes as large as possible to anticipate a faster convergence rate. Similar to other algorithms, these step sizes are generally determined through cross-validation."}, {"review_id": "5upjE7HjZJ", "reviewer": "Reviewer_VNHZ", "summary": "The paper proposes a smoothed first-order Lagrange method(SLM) with the help of a primal-dual optimization framework for solving a class of structured nonconvex functional constrained optimization (FCO) problems. It can be used to deal with lower-level (LL) nonconvex bilevel optimization(BO) problems.  Theoretically, the paper proves that the algorithm converges to an $\\epsilon$-KKT points of these nonconvex constrained problems. Under some assumptions, the convergence rate of SLM to an $\\epsilon$-KKT point is $\\mathcal{O}(\\epsilon^{-1})$ for FCO problems. SLM can achieve a convergence rate of $\\mathcal{O}(\\epsilon^{-2})$ to solve nonconvex BO problems when the LL problem satisfies the PŁ condition.\tThe paper compares the proposed method with existing ones on a toy example and a data hyper-cleaning problem. In the toy example, SLM performs better than BOME and V-PBGD. As for the data hyper-cleaning problem, it performs better than the V-PBGD.", "questions": "1. Equation (9): is there a missing \\{\\}?\n1.  In Line 617, why does inequality (111) hold?\n1.  In Line 721, E.1 Neural Network on MNIST Data Set. I am wondering why the performance is better when $\\delta$ is larger. You say \"The constraint tolerance parameter $\\delta$ and the dual variable implicitly play the tradeoff between the training and validation losses.\" Is that an explanation for this phenomenon? Could you explain it more clearly? \n\t\t\n1.  In the conditions of Theorem 1, step-sizes are chosen as $\\tau, \\eta, \\alpha = \\mathcal{O}(\\frac{1}{\\lambda^r})$. These step-sizes will be very small when $\\lambda$ is getting large. Will this setting of step-sizes affect the effectiveness of the algorithm?\n1.  In Figure 3,  why does the test accuracy of BOME get down after 400 iterations?", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper proposes a new algorithm to deal with a class of structured FCO problems, and also nonconvex BO problems. \nThe authors give convergence analysis when solving FCO and BO.", "weaknesses": "1. There are no formal definitions for $\\epsilon$-KKT points and $\\epsilon$-stationary points. This makes the paper difficult to follow. Moreover, when $\\delta=0$, I don't think the KKT condition for bilevel optimization is well defined.\n\n2. Assumption A4 needs more explanations.   Why can it hold for the case of $\\delta=0$? It will be beneficial if the authors can give such an application.\n\n1. There are numerous errors in the proof. Some are minor details that need to be carefully checked, but others lead to incorrect conclusions. \n   - In Line 532, inequality (59),  there should be a $p$ in the gradient Lipschitz constant of $K$ with respect to $y$. \n   - I cannot follow the proof of Lemma 6. Do we need a bound for $D(x^{r+1}, z^{r+1}; \\lambda^{r+1}) - D(x^{r}, z^{r}; \\lambda^{r+1})$?\n   - In Line 567, why is $\\lambda_+$  the maximizer in the expression of the objective function? \n\t\t\t\n\t\n4.\tThe author should clarify the theoretical novelty of their compared to reference [1].\n\t\t\n[1] Zhang, J., Xiao, P., Sun, R., & Luo, Z. (2020). A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems. Advances in neural information processing systems, 33, 7377-7389.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer VNHZ for your helpful comments and questions.\n\n**Response to Weaknesses 1 (RW1)**\n$\\epsilon$-KKT points and $\\epsilon$-stationary points essentially refer to a point $x^*$ that satisfies the condition:\n\n\\begin{equation}\n\\max \\\\{|| \\mathcal{G}(x^*,y^*)||,|g(x^*, y^*) - g^*(x^*)-\\delta|_+\\\\}\\le\\epsilon.\n\\end{equation}\n\nIt is true that when $\\delta=0$, the KKT condition of our formulation lacks a clear definition for bilevel optimization, given that the Slater condition is not satisfied. Consequently, we only discuss the method's convergence toward approximate KKT points.\n\n\n**RW2**. \nWhen $\\delta=0$, our considered problem is not well-defined. Therefore, our focus remains solely on cases where $\\delta>0$. While A4 is reasonable, since neither the feasible set nor the function value can be infinity in practice.\n\n\n**RW3.1** \nYes, the $p$ was missing in the gradient Lipschitz constant. However, this omission will not impact the convergence result as $\\lambda\\sim p$. \n\n\n**W3.2** \nThere were typos in the proof. The $y^{r+1}$ and $y^r$ in $D()$ should be $x^{r+1}$ and $x^r$.\n\nYes. We also need a bound of $D(x^{r+1},z^{r+1};\\lambda^{r+1})-D(x^{r},z^{r+1};\\lambda^{r+1})$.\n\nTo be more specific, as function $K(\\cdot)$ is $L_x=L+p$-smooth and $p-L$-strongly convex, we can apply Lemma 4.3 in [Lin et al., 20 or 37] and have\n\n\\begin{align} \n  D(x^{r+1},z^{r+1};\\lambda^{r+1}) - D(x^r,z^{r+1};\\lambda^{r+1})\n\\le  \\langle \\nabla K(x^r,y^*(x^r,z^{r+1};\\lambda^{r+1}), z^{r+1};\\lambda^{r+1}), x^{r+1}-x^r\\rangle + \\frac{L_{K_x}}{2}||x^{r+1}-x^r||^2\n\\end{align}\n\nwhere $L_{K_x} = L_x+L_x^2/(p-L)$. Then, following the similar steps shown from equations (47) to (54), we can first quantify\n\n\\begin{align} \n& ||\\nabla \\hat{K}(x^r,y^{r+1},z^{r+1};\\lambda^{r+1}) - \\nabla K(x^r,y^*(x^r,z^{r+1};\\lambda^{r+1}), z^{r+1};\\lambda^{r+1}) ||\n\\\\\\\\\n\\le & 3(L^2_f+\\lambda^{r+1}L^2_g)||y^*(x^r,z^{r+1};\\lambda^{r+1}) - y^{r+1}||^2 + 3(\\lambda^{r+1})^2L^2_gd^2_{\\mathcal{S}(x^r)}(u^{r+1})\n\\\\\\\\\n\\le &   3(L^2_f+\\lambda^{r+1}L^2_g)(1+\\sigma_1)^2/\\sigma^2_1||y^{r+1}-y^r||^2 + \\frac{3\\mu_g L^2_gD_{\\mathcal{S}}}{\\eta r^2}\n\\end{align}\nwhere the first inequality holds due to gradient Lipschitz continuity; in the second inequality we utilize the primal error bound from Lemma 3.10 in [Zhang et al., 20 or 32] and the facts from equations (50) to (53). Here, $\\sigma_1=\\alpha (p+L)$.\n\nCombing this result with gradient Lipschitz continuity of $D(\\cdot)$ mentioned above, we can have\n\\begin{align}\\notag\n&\\quad D(x^{r+1},z^{r+1};\\lambda^{r+1}) - D(x^r,z^{r+1};\\lambda^{r+1})\n\\\\\\\\\n\\le & -\\frac{1}{4\\eta}||x^{r+1} -x^r||^2+\\frac{3\\mu_g L^2_gD_{\\mathcal{S}}}{r^2} +3\\eta (L^2_f+\\lambda^{r+1}L^2_g)(1+\\sigma_1)^2/\\sigma^2_1||y^{r+1}-y^r||^2\n\\end{align}\nwhere $\\eta\\le 1/L_{K_x}$.\nIt can be easily seen that the second term can be combined with the bias. The third term can be dominated by the descent accomplished by updating $y$ (given that the coefficient in eq.(60) is proportional to $1/\\alpha$, whereas here, the coefficient is only proportional to $1$).\n\n\n**RW3.3** Here, we employ the optimality condition of the fixed point, which implies that $x^*=P_{\\mathcal{X}}(x^*+\\tau \\nabla f(x^*))$ represents the optimal solution for $\\max_{x\\in\\mathcal{X}} f(x)$. It is straightforward to verify that the function $\\lambda_+(z)$ defined in equation (76) corresponds to the optimal solution of the problem presented in equation (78).\n\nTo elaborate further, we can calculate the gradient of the objective shown in equation (78) at $\\lambda_+(x)$, yielding $-\\lambda_+(z)/\\tau+\\lambda/\\tau+\\nabla_{\\lambda}K(x,y^*(x,z;\\lambda),z;\\lambda)$ (please note that we are scaling the objective by a constant $1/\\tau$, which does not alter the optimal solution). Subsequently, we multiply this gradient by $\\tau$ and examine the optimality condition. It becomes evident that $\\lambda_+(z)$ defined in eq.(138) indeed stands as the optimal solution to this maximization problem.\n\n**RW4** \nPlease note that the two papers address distinct optimization problems. We do utilize the primal error bounds obtained in [1], as they are independent of the dual problem. The key technical differences are as follows:\n- Here, we consider a constrained problem where the dual variable is unbounded, while in [1], the authors assume the boundedness of the maximizer directly, making the analysis more tractable.\n- The proofs of the strong error bound are entirely distinct. Here, we consider a constraint that follows the PL condition, while in [1], this bound is established based on a specific min-max problem, i.e., the minimization of the point-wise maximum of finite functions.\n- The constraint considered here belongs to a class of equilibrium constraints that did not appear in [1]. Demonstrating the convergence of the primal-dual algorithm in this problem involves new analysis for showing the descent lemma.\n\n \n**Response to Q1 (RQ1)** Yes.\n\n**RQ2** Sorry for the errors in the expressions of the error bounds. Due to the space limit, please see our response to Q1 of Reviewer aS1n.\n\n**RQ3**  Indeed, an optimal choice of $\\delta$ exists. If $\\delta$ is small, the constraint may limit the search space. If $\\delta$ is too large, the problem essentially reduces to an unconstrained or single-level problem, lacking the capacity to perform the LL learning task. In the example, $\\delta$ essentially adjusts the model's reliance on training and validation losses.\n\n**RQ4**  It holds true that if $\\lambda$ is large and the step-sizes theoretically need to be small, which is reasonable. In this scenario, it implies that the constraint is not satisfied, leading to a greater value on the Lagrangian. Consequently, this results in a higher Lipschitz constant.\n\n **RQ5**  The model optimized by BOME enters the overfitting regime after 400 iterations. In this instance, the LL problem is optimized using training data, where a distribution shift between the training and testing datasets could exist (actually indeed exist)."}]

Author rebuttal:
We sincerely thank all the reviewers for their time spent reviewing our work and greatly appreciate the comments provided by each of you. In this general response, we would like to present the F1 score and test accuracy achieved by SLM and V-PBGD, as requested by reviewer aS1n, along with the newly added numerical experimental results that include two additional baseline algorithms in response to the concerns raised by reviewer 7siX.

First, we have further plotted the F1 score and test accuracy of SLM and V-PBGD in the attached file. It can be observed that the achievable test accuracy is consistent with what has been discussed in the main text. The results imply that SLM is more robust against overfitting than V-PBGD. However, the F1 score achieved by SLM is relatively lower than that of V-PBGD, with a difference of 0.2%.


Secondly, we extended our implementation by utilizing the codebase of BOME, which is publicly available on GitHub. We proceeded to conduct a performance comparison of SLM with two additional baseline algorithms: bi-level value-function-based sequential minimization (BVFSM) [R1] and iterative differentiation (ITD) based bilevel optimizer [R2]. This comparison was carried out on the data hyper-cleaning task. 

In this particular scenario, a different setup was taken compared to our prior work. We introduced a clipping function at the lower level, which differs from our previous utilization of a sigmoid function. Additionally, the dataset was divided into four subsets: the training set, validation sets 1 and 2, and the test set. This variation sets this use case apart from our previous one.

The results of these experiments are presented in Figure 2 in the attached file. It is important to note that for this presentation, we plotted the test accuracy against time, enabling a more fair comparison. The outcomes demonstrate that SLM achieves higher test accuracy in a comparsion with these existing benchmarks. Furthermore, the convergence speed of SLM closely aligns with that of V-PBGD and BVFSM. Once again, these results emphasize the superiority of our proposed formulation in enhancing the generalization performance of machine learning models.

@Reviewer aS1n and VNHZ: Our response to the concerns regarding the error bounds can be found in our response to Q1 from reviewer aS1n. Please kindly note that these errors can be easily addressed, as the results have been displayed in the appendix.

We hope that we have addressed all your major concerns. Please let us know if there are any questions.

Thank you again for your time.

Authors of #8513


[R1] Liu et al., Value-function-based sequential minimization for bi-level optimization, 2021.


[R2] Ji et al., Bilevel optimization: Convergence analysis and
enhanced design, ICML, 2021.

Meta-review: The paper proposes a new algorithm, the Smoothed First-Order Lagrange Method (SLM), to address structured nonconvex functional constrained optimization (FCO) problems and nonconvex bilevel optimization (BO) problems. While the method showcases promising results and theoretical proofs for convergence, it was criticized for lacking clarity in definitions and making unclarified assumptions

A number of issues related to the assumptions and numerical results have been adequately addressed in the rebuttal period, with reviewers increasing the score.

From my perspective, the structured constrained optimization and bilevel optimization problems tackled by this paper are not well studied, making the paper's focus both interesting and important. The paper is generally well-written and easy to follow, the authors provide theoretical proofs for the algorithm's convergence. Specifically, the proposed SLM algorithm offers near-optimal convergence rates under specific conditions. Finally, numerical experiments show that SLM outperforms existing methods in certain situations.
Decision: Accept (poster)