A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization
Authors: Wei Shen
Jiawei Zhang
Minhui Huang
Cong Shen
Venue: NeurIPS 2025 poster ()
Keywords: Bilevel optimization
Constrained optimization
Hessian-free
Single-loop
Convergence analysis
Primary area: optimization
TL;DR: This paper proposes a new single-loop first-order algorithm for solving linearly constrained bilevel optimizationm problem.

Abstract: We study bilevel optimization problems where the lower-level problems are strongly convex and have coupled linear constraints. To overcome the potential non-smoothness of the hyper-objective and the computational challenges associated with the Hessian matrix, we utilize penalty and augmented Lagrangian methods to reformulate the original problem as a single-level one. Especially, we establish a strong theoretical connection between the reformulated function and the original hyper-objective by characterizing the closeness of their values and derivatives. Based on this reformulation, we propose a single-loop, first-order algorithm for linearly constrained bilevel optimization (SFLCB). We provide rigorous analyses of its non-asymptotic convergence rates, showing an improvement over prior double-loop algorithms -- form $O(\epsilon^{-3}\log(\epsilon^{-1}))$ to $O(\epsilon^{-3})$. The experiments corroborate our theoretical findings and demonstrate the practical efficiency of the proposed SFLCB algorithm. Simulation code is provided at https://github.com/ShenGroup/SFLCB.

A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization
Wei Shen University of Virginia
Jiawei Zhang University of Wisconsin-Madison jahang29240risc.com edu
zyy5hb@virginia edu
Minhui Huang
Cong Shen University of Virginia congEvirginia. edu
Meta
mhhuangSmeta.cco
Abstract
We study bilevel optimization problems where the lower-level problems are strongly convex and have coupled linear constraints. To overcome the potential non- smoothness of the hyper-objective and the computational challenges associated with the Hessian matrix, we utilize penalty and augmented Lagrangian meth- ods to reformulate the original problem as single-level one. Especially, we establish a strong theoretical connection between the reformulated function and the original hyper-objective by characterizing the closeness of their values and derivatives. Based on this reformulation, we propose single-loop. first-order algorithm for linearly constrained bilevel optimization (SFLCB). We provide rigorous analyses of its non-asymptotic convergence rates, showing an improve- ment over prior double-loop algorithms form O(e (og(= to O(e-3). The experiments corroborate our thcoretical findings and demonstrate the practical efficiency of the proposed SFLCB algorithm. Simulation code is provided at https::/ //github. com wwt.lcco..ossieeee /Stm/hhhooorp/SLC3
Introduction
In recent years, bilevel optimization (BLO) has gained significant popularity for addressing a wide range of modern machine learning problems, such hyperparameter optimization [36 33) data reinforcement learning
hypercleaning 38) meta learning 337
13
41 [1 and neural architecture
search [26] 23
40 for additional discussions. While numerous works for unconstrained BLO problems have been proposed 9 30 15|
survey papers 52
27
22 studies focusing on
constrained BLO problems are relatively limited.
In this paper, we consider the following BLO problem where the lower-level (LL) problem has coupled constraints:
min FEX
((x) 2 f(x, y" (x))
s.t. (x) E arg min g(z, y). (E)((r)
The upper-level (UL) objective function f R R4 + R and the lower-level objective function g Rd x Rd IR continuously differentiable. Moreover, assume that g y) is strongly convex with respect to y. The feasible sets defined as X Rd (x))) { y 1y 1((x, y) S 0) where h. R Rdy - Rdh.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

For this setting, we develop single loop algorithm for the special case h(x,y) y) Bx + Ay - b. where B E xd, and E IRdaxd, This special class of constrained BIO problems covers a wide class of applications, including distributed optimization [48). hyperparameter optimization
of constrained learning problems [46] and adversarial training (53 and draw significant attentions
1 20
popular approach for solving unconstrained BLO is implicit gradient descent 9
15
14
19I. For
constrained BLO, several studies have extended this approach to accommodate different constraint muddient-based methods in constrained BLO
settings 18 46
45]. However, these implicit
necessitate computing the Hessian matrix of the lower-level problem 42
18
46 45).
The potential
computational challenges associated with the Hessian matrix limit their practical applicability for large-scale problems.
Recently, some first-order methods [21 50 16 20 have been proposed for addressing constrained BLO problems. Most of those works considered transforming the original problem ( into single- level one and trying to find the stationary points of the reformulated problem. For example, [50] 49] reformulated the original problem into some approximated functions and proposed single-loop algorithms for finding the stationary point of the approximated problem. However, neither (50) nor
49 establishes clear relationships between the stationary points of their approximated problems and the original one.
Works most closely related to ours are those by 21 and 16 both of which reformulated the problem as
min (Y)
(xr v) s.t. g(x v)
min g(.,2) 2) S 0, =<)())
and considered optimizing the following function with penalty parameter d:
m minlDo(x) A min max 25 2,2]
(3)
wVV( sE)(w)
where L, y, = f(z, y) + + [g( y) g(, z)]. Based on this reformulation, 21 proposed algorithms for solving BL.O with LL. constraints y y and [16] proposed algorithms for solving coupled LL constraints ((x) = {u E (R(,))( I 0}. However, [21 only considered the LL constraints Y that independent of and their methods require projection oracle to ) at each iteration. Algorithms in [16] require complex double or triple loops, resulting in sub-optimal convergence rates and diffieult implementation. Moreover, the connection between the stationary point of the reformulated function & and the original hyper-objective & is not discussed in 26 for coupled constraints (z))
To address these limitations, in this paper, we establish a rigorous thcoretical justification for this reformulation (3) and propose single-loop Hessian-free algorithm for the linearly constrained cases. Our main contributions can be summarized as follows.
We establish a rigorous theoretical connection between the reformulated function 4, and the original hyper-objective & by proving the closeness of their values and derivatives under coupled constraints (xx) = fy E 124//h(2 y) I 0} with certain assumptions, which provides strong justifications for the reformulation (3).
Based on this reformulation and equipped with augmented Lagrangian methods, we proposed SFLCB, single-loop. first-order algorithm for linearly constrained bilevel optimization problem, and provide rigorous analyses of its non-asymptotic convergence rates, achieving an improvement in the convergence rate from ( loog(- )) to O(c-3) compared to prior works (See Table for a more comprehensive comparison of our work with previous studies). The simple single-Toop
structure also makes our algorithm easier to implement in practice compared to [16.
Our experiments on hyperparameter optimization the support vector machine (SVM) and transportation network design problems validate the practical effectiveness and efficiency of the proposed SFLCB algorithm.
2
Related works
BLO without constraints. One popular approach for solving unconstrained BLO is to use implicit gradient descent methods (36). It is well established that when the LL problem is strongly convex

---

Table 1: Comparison of our paper with [21 16] More detailed introductions and discussions of other
related works can be found in Section 2 Here, the "Complexity" means the iteration complexity needed to achieve the e-stationary point of 4s 3.
Methods
LI Constraint
Complexity
Loops
2T
y y. V.y.iis is a convex and compact set
O(e log(e !)
single/double
16
h(r, S 0, LICQ holds
O slog(E 1)
triple
[6
B(x) AAr)y S 0, A(x)) is full row rank
O log(e=
double
SFLCB (ours)
Br + Ay & 0, A is full row rank
O
single
SFLCB (ours)
Ay S 0, LICQ holds at the initial points
O
single
SFLCB (ours)
Ay S
O(c-a)
single
and unconstrained, y²(x) = argmin, g(z 3) exists and is differentiable, and the gradient of the hyper-objective can be calculated by ($ V (zr + (Vy" (Vy(
(z. V., y (a:) 99. Later
works improved the convergence rates and studied the gradient descent methods under various settings
[15 14
19 47]. Another popular approach is based on iterative differentiation, which iteratively
solves the LL problems and computes Vy"(z) to approximate the hypergradient [4 10 29 2].
Recently, venalty-based methods have gained traction as a promising approach for solving BLO. Those works usually reformulate the original BLO as the single-level one and use the first-order
methods to find the stationary point of the reformulated problems [28 35 25
39
31 32)
BLO with constraints. There are two primary types of methods for solving constrained bilevel optimization problems. One is based on the implicit gradient method. Generally, when the LL problem
has constraints, the differentiabilities of y (zz) and (xx) are not guaranteed [8]. 42 proved the
existence of (z) under additional assumptions for linearly constraint Ay S b and proposed an implicit gradient-type double-loop algorithm. [88] proposed a perturbation- based smoothing technique to compute the approximate implicit gradient for linearly constraint Ay S b. [46] used Clarke subdifferential to approximate the non-differentiable implicit function Φ. However, they only provided asymptotic convergence analysis of their algorithm. 45 proved the existence of Vej
where the LLL has equality constraints Ay + H (x) = e, and introduced an alternating projected SGD approach to solve this problem. However, these implicit gradient-tye type algorithms [42 18 46 45
require the computations for the Hessian matrix of the LL problems, which potentially limit their practical applicability for large-scale problems.
Another commonly used approach for solving constrained BLO problems is based on penalty reformulation. For example, (32) reformulated unconstrained and constrained BLO problems as structured minimax problems and introduced first-order methods with guarantees for finding e- KKT solutions. (50] reformulated the original problem into a proximal Lagrangian value function and proposed a single-loop. first-order method to find the stationary points of the reformulated value function. However, their algorithm requires the implementation of the projection operator on = {x. y//( y) I 0} at each iteration, which can be potentially costly. [49] reformulated the original problem into doubly regularized gap function and proposed single-loop. first-order algorithm. Compared to [50]. [49 did not need the projection operator to the coupled constraint
set. However, both [50] and [49 did not establish very clear relationships between the stationary points of their approximated problems and the original one. For example, [49] only provided an asymptotic relationship between the original problem and their reformulated one, i.e., their penalty parameter approaches infinite, their reformulated problem is equivalent to the original one. Recently, proposed algorithms based on barrier approximation approach for constrained BLO problems. However, their algorithms also require the computations for the Hessian matrix.
43 17
21 and [16] considered the same reformulation ours. [21] studied the case where the LL variables y E y are independent of x and characterized the conditions under which the values and derivatives of Φ and 4 can be ((8)-close for E y constraints. Compared with [21]. we prove similar results under coupled constraints )'(x) {v E 2d [/( y) I 0}. Moreover, the algorithms in (1 require
the implementation of the projection operator to y at each iteration, which can be costly. [16] studied
the coupled constraints }²(x)) = {v E 4 [h(x, y) < 0). While [16] considered more general constraints than ours, however, it did not characterize the gap between the stationary point of the
reformulated function 4 and the original hyper-objective 4. Our Theorem 4.9 provides further
3

---

justifications for their reformulation in coupled constraints. Moreover, compared with the double- and triple-loop algorithms in [2T], we propose a single-loop algorithm SFLCB and prove an improvement in the convergence rate from Of+ logg(=))) to O ))
Recently, (0 also proposed first-order methods for linearly constrained BLO. Especially, they proved nearly optimal convergence rate Ō for linear equality constraints and proposed algorithms that can attain (6, ( -GGoldstein stationarity for linear inequality constraints. However, their convergence rates for linear inequality constraints either have additional dependence on dimension d (such as O(d8-1c-3) need additional assumptions to access the exact optimal dual variable (such as ()),, while we do not require the exact optimal dual variable assumption. Compared with the double-lood algorithms in [20]. our proposed single-loop one is easier to implement in practice. Moreover, our techniques are also different from theirs under linear inequality constraints, thereby highlighting the distinct contributions and independent interests of our work.
3 Preliminaries
Notation. For vectors b R we denote S b if for all i [d]. S b,. We use || to denote the l2 norm of a vector and the spectral norm of a matrix. We define the projection operator that project set P as (x)) argmin 2 - x'1??. We denote the projection operator that projects a E the set Id as (z).
We state the following assumptions for problem which are commonly used in the theoretical studies of BLO.
Assumption 3.1. For any x E X, (xx) is nonempty, closed, and convex and (xx) is lower bounded by a finite, d- = en ((z)= 2 -00.
Assumption 3.2. f, f.. Vg are Lipschitz continuous with 4,,0, 44144.11 respectively, jointly over X' x (z)).
Assumption 3.3. For any fixed E X, g(z, v) is Ma Strongly convex with respect y E (xx).
We introduce the standard definition of the e-stationary point for differentiable function.
Definition 3.4. We say è is an c-stationary point a differentiable function f if [ S c.
4 Reformulation
In this section, we provide theoretical justification for our reformulation (3) and establish the conditions under which the function values and gradients of the reformulated function & and the original hyper-objective & become sufficiently close. Note that in this section, we considered general coupled constraints ((x) = (y Rdv [h y) S 0} which include, but are not limited to, the linear constraint case. The complete proofs for the lemmas and theorems in this section can be found in Appendix
First, we assume
<
My. and introduce the following notations: 24,1
(x)) = argmin 5 ff () + g(x yE)(x)
y²(x) = =²(x)= = argmin g(r,
,E)(x)
ds y. 2) = (z, (s(x) = (z. (x),
Similar to Theorem 3.8 in 21 we have the following theorem bound the difference between + and 6G as well as y" (x) and y (x) in the coupled constraints.
Theorem 4.1. When Assumption 3./ 3.2 and 3.3 hold, we have
28
0 S ((x) (x) <
(1))(x) - (x))l
2/1
14

---

Theorem 4.1
characterizes how the difference in function values and the optimal LL variables between the reformulated problem and the original one are controlled by the penalty parameter 6. Therefore, by choosing a sufficiently small 6, i.e., 6 = O(e), we can treat the reformulated problem mingex & (z) as an approximation of the original problem and solve this approximated problem instead. In the following lemmas, we will provide the conditions under which the reformulated function (ar) is differentiable. Before that, we first introduce the well-known and commonly used Linear Independence Constraint Qualification (LICQ) condition.
Definition 4.2 (Active set). We denote Iy
C [dx] as the active set of y, i.e. In = E [da] |
h2 v) = 0)-
Definition 4.3 (LICQ). We say point y satisfy the LICQ condition if, for all i E Iy, Voli(z, v) are linearly independent.
Then, similar to Lemmas 2 and 3 in [6]. we have the following lemma.
Lemma 4.4. When Assumption 3./ 3.2
hold and ó S (2)()) if. for all x E X, the LICQ
condition (Definition 4.3) holds for y (z) and y (z). then there exist the corresponding unique
Lagrangian multipliers X (x) Rd and (x) E 1R such that
X (x) argmax min ( + h(x,)) xEă vE)(()
(4)
(z) = argmax min 8f(z, v) + +((z,)) + A h(2,)) XER+ vEV(2)
(5)
Furthermore, we have
V& = V V (x)) + 1
V VLhC,
Vag(z, y (z)) V V24(2, ( (z)).
While the gradients of (x)x) exists under LICQ conditions, for general problem ①.. (xx is not
guaranteed to be differentiable. For example, (18) provides an example where the LICQ condition
holds, ((x) is non-differentiable at some points. However, if a given x satisfies the following conditions, then (x)x)) exists at x.
Assumption 4.5 (Strict Complementarity). Let (xr) be the Lagrange multipliers for y" (x) For any E (x) [X* (x)]; > 0.
Assumption 4.6. V. V2g are Lipschitz continuous with 1,2, 9,22 respectively, jointly over X' x (xx)) For E [. (z, y) is convex with respect to y, h., Vh, 22 are respectively Lipschitz continuous with 4,,0, 41,1 41,2 jointly over X' x (z)).
Note that Assumption 4.5 4.6 are commonly used in constrained BLO literature 42 ensure the existence of (x)).
are
8
46
Lemma 4.7 (Theorem 2 in [6)). When Assumption 3.7 3.2
4.6 hold, if. for given condition hold for y (z), then V (xx)) exists at x.
Assumption 4.5 and LICQ (Definition
Moreover, with additional assumptions, we can establish non-asymptotic bound for [ (2)(1)]
Assumption 4.8. For any t [0,
(1) y (ar) satisfies the L.CQ condition (Definition 4.3 with the same active set as y (ar). Denote this active set as T. Let (z) be the Lagrange multiplier for vi (x)) in (5). For any E I, [>][) > (Strict Complementarity). We assume [x)(())] < A, where is an O(1)
constant.
(2) Denote V, h(,,, yt (x)) = Vy[h(z, oi (z)))z. The singular values of V 2 (x)) satisfy
mmax ([V,[VVVteee ,, vi (x))) < Smaxs miin ( V h(x vi (x))) 2 8min > O, where 8max; 8min are ((1) constants.
Assumption is made for E [0, 6). When sufficiently small, i.e., O(e), y (x) and yi (x) are very close according to Theorem 4.1 Thus, we expect that for L E 8), yI (z) will have similar properties as y" (x). Similar assumptions have also been used 21 to establish the non-asymptotic
bound for (+))) (
5

---

Theorem 4.9. When Assumption for given I, we have
3.7
3.2
3.3
4.6
hold and á S (g/(21 if Assumption 4.8 holds
(v)))
vd,(2)) S O(6).
Similar non-asymptotic bound for ( (<) has been established in 21 however, their
bound is established only for the LL constraints ) that do not depend on z. Our Theorem 4.9 provides more general theoretical justification for the validity of the reformulation 33 for coupled constraints
(x) = {y E [/(/, y) S 0}.
The SFLCB Algorithm
In the last section, we have justified the validity of our reformulation for coupled constrained BLO. this section, we focus on special and important case where the LL constraints are (xx, v) = Ba + Ay - b. This particular category of constrained BLO problems encompasses broad range of applications, including distributed optimization [48] [8], adversarial training [53 18 and hyperparameter optimization for constrained learning tasks such as hyperparameter optimization in SVM (see Section 6). For this special case h(x,)) y) = Bx + Ay - b, we introduce novel single-loop, first-order algorithm SFLCB, which achieves an improvement in the convergence rate compared to prior works 21 [6]
First, we introduce the following slackness parameters a, 18dh and define y' (yT,aT) TT)
z' = ,T)T With these slackness parameters, we can convert the original inequality constraints to equality constraints, i.e. we can reformulate min (ax Ø8(x,, y, as:
min =EX. ='E,(())))
max 03 (5 v,.2
(6)
where Py - ty E R4 E J. S,()) a Pyl((,,) - = =0]. The Lagrangian of with multiplier u, E Rd
Ls(x, 3 u.,u, =0s(=, (z, y, 2) + u (h(x,)) - a) - -(((xz 2) - -B).
According to Proposition 5.3.4 in [ we know that
(3(2)= min max
La(x,8/ V.u.u),).
V'EP,.ER4 d'EPh
Note that when d I (2) 6s pg/2-strongly convex with respect y. However, Ls(x, v/, 2', u, v) is only convex with respect y' and concave with respect 2'. To make the ob- jective function strongly convex with respect to y and strongly concave with respect to 2', we can construct augmented Lagrangian K:
u, K v', Lo . 36 x', u, + |1(2,, y) -all 11(x 2) -112
With S Pı - and S P2 S Ti (Aj. according to Lemma D.I K strongly convex with respect to s/ and strongly concave with respect to z'. Moreover, we have
())
min y VER H'R'h
max
1=(,, v) min y'EP, PER E'RR"
max
K(x, v u),
Note that Ls and K have the same optimal points and same optimal function value. Thus, we can reformulate the problem (6) to the minimax optimization problem over K:
min x EP..Y'EP,,.EEER PERd, HER
max
K(x, // ,,,,,v)
Motivated by these theoretical analyses, and applying gradient descent ascent (GDA) over problem propose SFLCB. A compact description can be found in Algorithm [

---

Algorithm SFLCB
Input: 8, Pl. P2. 12 22 f1 Mlus T
Initialize: Tp E X, Vo: = E Py uo, 10 E Rdd
for 1 0, 1, ,..,,... T
do
Uz++1 = + Tu (f((z, 31 -as)
1t+ Ut + T7 (1 zc) -+)
T++1 = It f] K (Zr.V1,, Z/ Me+1, vt+1)
Vi+1 II,, f Bl V (Ze, Vo oi ue+1, [(+1)}
2/41 1p, {2t + T7= V K (zt, b 24, ue+1, 0(41)]
end for
5.1 Convergence results
In this section, we provide the non-asymptotic convergence results of SFLCB (Algorithm D for two constraint settings: 1) h(x,,) y) = Bx + Ay b, where A is full row rank, and 2) h()) Ay b.
where not required to full row rank.
Note that when the LICQ condition (Definition 4.3 holds for y (a:) and y (z), the optimal Lagrangian multipliers of y (ar) and y (x) are unique. Thus, we first introduce the following lemma and notations for these optimal Lagrangian multipliers.
Lemma 5.1. When the LICQ condition (Definition 4.3)
holds for y² (x) and yā (z:), the optimal Lagrangian multipliers of y" (1)) and v/g (x) are unique, and we have
45(x)) = argmax min 98(r, y) + u h((,y)) = argmax min K K(r, v ,2,,,,,,,,, ", u),), wER4 yEV(Z)
HERt y'EP,
o" (x) argmax min g(x, =) + argmin max K( ,',,,, v). wERth e'EP,
vER, =c)((r)
The proof of Lemma 5.1 can be found in Appendix E Next, we introduce the following notations:
3/5 (x, u) = argmin K K(x, (z,
(x argmaax K K( z'EP,
A'= (A,
y'EP,
Then, we present the convergence results of SFLCB (Algorithml for coupled constraints l((x, y)
Bx + Ay b, where A is full row rank. Note that BLOCC in [66 that achieves the complexity of O 3 log(E 1)) also needs the matrix A to be full row rank (See Table 1.. For A that is not full row rank and B 0. provide the convergence results in Theorem 5.4 and Corollary
5.5
Theorem 5.2. When (x.,y) Br + Ay- b, A is full row rank, Assumption 3.1 3.2 3.3
hold and
O S (2/(2l if we apply Algorithm with appropriate parameters (see Appendix Fl, then we can find an e-stationary point of 2 with complexity of O(E
Moreover, if we have initial points 2o: you 20, Up Uo such that
llyo y (no) || S O()), l|ue- uz (xo))) S 0(5), = = (xo)) < O()), |/vo o (xo)) < 0(0), then we can find an e-stationary point of d with a complexity of O(E
(8)
The formal statement and the complete proof of Theorem 5.2 can be found in Appendix
Proof sketch for Theorem 5.2 The key new idea in proof is the construction of novel potential function Vú and prove the descent lemma V, (Lemma E.4 V, is defined as:
1
V, K (Ix, vls z/1 ue vt) 2q( ve) d(xte zhe de, Uz)
where da,=', "' u.v) = K(x, 1/2 (x, u), u, v) and q(x, v) T (A'="(zr w) - b) 1''1'' ( bll2. To prove Lemma E.4
6s(a, 1/ (x), x" (z), v)) we need first prove sev- E.2 Those error bounds may be of
eral novel eπror bounds in Lemma D.2 Lemma E.3 and Lemma

---

independent interest for solving other similar problems. The full row rank property of A is used in Lemma E.2 to bound || uz(=))l and ||er+1 (xxx))ll-
Since A has full row rank, then according to Theorem 6 in [16], we can easily find initial points satisfying (8) (-1 with complexity of O(log(e and we have the following corollary.
Corollary 5.3. When h(x,v) v) = Br + Ay - b, A has full row rank, Assumption 3.1 3.2
3.3 hold, and = ( S (2 if we apply projected gradient descent (PGD) for b) with a fixed No. we can find 0, 2 such that max VER min g(zo, 2) + (Bro + Az -b)
||0 - v² (2o))l S and _| - =x (xo)l I 5 with a complexity of O(log(=))), Set yo = =0 = 2, 0g- h((r, yo). 30 h1 20). With va, Vos =6 uo, Un as initial points and applying 7 we can find an e-stationary point of Dg with a complexity of O(e Thus, the total complexity is O log((=1))
Wg - un
Algorithm
((6-3)
The proof of Corollary 5.3 can be found in Appendix E. Thus, compared to [66. we achieve an improvement in the convergence rate from O(e 3 logle 1)) O for the coupled linear constraint (See Table I.
Additionally, we have the following convergence results for constraints h(y) = Ay b. where A is not required to have a full row rank.
Theorem 5.4. When h(x, y) = Ay-b, b, Assumption 3.1 3.2 3.3 hold, and 8 O - / (2( if we apply Algorithm [ with appropriate parameters (see Appendix D.. then we can find an e-stationary point of & with a complexity of ().
Moreover, if we have initial points zo: y6= 2/6, uo Uo such that
11yo y (zo)ll - O6)), || v/" (zu, mo) bll z O()), 14'26 - b|] s (())
(10)
||=0- (x=0]l < O || (æo, vo) b1l < ( || - bl s O())
(11)
then we can find an c-stationary point of tb with a complexity of ((c
The formal statement and the complete proof of Theorem 5.4 can be found in Appendix D
Proof sketch for Theorem 5.4 The general proof flow of Theorem 5.4 is similar to that of Theorem 5.2] However, since here we do not have coupled constraints, K has no relationship to u or v, and according to the Danskin's 's theorem, Vá = oV. vž (x)) + V2g(2, V7 x
Vagga, 2 (z:) also has no relationship u (zz) or 8* (z)) Thus, we do not require Lemma E.2 or the full row-rank assumption on A in this setting.
Next, we show that, long the LICQ condition (Definition 4.3) holds for the initial y (27) and yg (xo). we can find initial points satisfying (0) with a complexity of O(E 2) and we have the following corollary.
hold, and 8 8= O(E) S (21,,)) for a given initial point zo. if the LICQ condition (Defiiition 4.3 holds at y (zo) and y (zO), we can apply Algorithm / with fixed xo- Then for sufficiently small (see Appendix D.. we can find i', 2,,,,,,,,, ú. such that
Corollary 5.5. When h(,, v) = Ay b, Assumption 3.1 3.2 3.3
1 vo (xu)) S 0(6), ( i) - bll < 0()), ||'' - b1l - 0()), || - un (2o)) < 06)) | =" (2o)] 0()), I|A'z (zo, 6) bll < (6), A - -bl S 0()), || u (zo))l - O())
with a complexity of (c-2). Set y6 = J. =a = 2', wo = â, no = é. With xo. Vo: z uo, to as initial points, we can find an stationnyyy point of 4 with a complexity of O Thus, the total complexity is O(E + 2 = 3).
The proof of Corollary 5.5
can be found in Appendix D The key to proving Corollary 5.5 lies in
Lemma D.4 In Lemma D.4 we prove that, without the full row-rank assumption on A, we can bound
| 2 (20)] I|
and U++1 - u* (zo)]] with fixed zo. Thus, we can use our algorithm SFLCB to find suitable initial points with a fixed zp.
Note that in Corollary 5.5 we only need the LICQ condition holds for the initial y" (au) and y (mo), and we can achieve total complexity of -3). Compared to the decoupled constrained setting in (2T), we achieve an improvement in the convergence rate from O(E -3 log(e-1) to 0(e-3) (See Table I
8

---

Experiments
In this section, we evaluate the performance of our SFLCB algorithm on three tasks: toy example, hyperparameter optimization for SVM, and a transportation network design problem. These experi- ments demonstrate the practical effectiveness and efficiency of SFLCB. Additional hype-parameter sensitivity analysis experiments and detailed experimental settings can be found in Appendix F
6.1 Toy example
We consider the same constrained BLO problem that was studied in [16), which is:
4.3
6 (x)++2
1
Day, 3r13
min f(x, (x)) 2 cos(62) zE|O.3]
+ In 2)² 2
+
(12)
3.0
s.t. (²(x) E arg min g(x,3) v) = -v 2x))
(13)
(E)(x)
where y(x) f R fies Assumption 3.1 3.2 Moreover, we have y" (xx x and Equation 122 is equivalent to mo,3 f(x, v)ly=x= In Figure 1 we plot the hyper-objective function fz, y (z)). The red points indicate the converged solutions obtained by our al- gorithm with 200 different initialization values. We notice that SFLCB consistently finds the local minima the hyper-objective function, which validates the effectiveness of SFLCB.
Note that this problem satis-
0.0
1.0
1.5
2.0
Figure 1: Toy example.
6.2 Hyperparameter optimization in SVM
0.000
Hyperparameter optimization in SVM is well- known real-world application for constrained BLO problems that has been used in many prior works [6]. Here we consider the same prob- lem formulation
Test Accuracy
0.50
46 50
0725
in [16), which formulates this problem as a coupled linearly constrained BL.O problem. We conduct experiments comparing our
0.00
0.073
SFLCB algorithm with GAM [46). LV-HBA [50],
QAFPA
BLOCC [6], and BiC-GAFFA 49 the dia- betes dataset [6]. Results are plotted in Figure We notice that our SFLCB algorithm converges significantly faster than other algorithms. which demonstrates the practical efficiency of the pro- posed SFLCB algorithm.
BIOCE
0.625
HBA
CAM
Time (s)
Figure 2: Hyperparameter optimization in SVM.
6.3 Transportation network design
We further conduct experiments on transportation network design problem, following the same setting in [16]. In this setting, act the operator, whose profit serves as the upper-level objective and is influenced by passenger behavior, which modeled in the lower-level problem. Detailed formulations and settings can be found in Appendix FF We consider the two synthetic networks of 3 and nodes, same as those considered in [16]. We compare SFLCB with BLOCC [16]. Results plotted in Figure 3 which indicate that SFLCB significantly outperforms BLOCC this network design task.
6.3.1 Sensitivity analysis of
We also conduct the sensitivity analysis of the in SFLCB for the 3-node network. We set Pi /22 1000. 7/2 Fy 7)= The The 3e 4, and T 20000. Then, we test different values from (0.01, 0.05, 0.5, 1). For each 8, we test with three different random seeds. The final average results and one standard deviation reported in Figure 4 As can be seen, larger values of

---

2.07
U1 Utilityy
100
-00
-00
SFLC8
SFUCE
-100
352
Time
(s)
Time (6)
nodes
(b) 9 nodes
Figure 3: Results of the transportation experiments on 3 nodes and 9 nodes settings. Larger UL utility indicates better performance.
lead to a faster initial decrease in the loss (increase UL utility). In contrast, very small (e.g.. 5 0.01) results in significantly slower convergence overall. However, overly large (c.g.. 6 = 1) can lead to large approximation emrors in later stages, causing deviation from the true optimization objective and ultimately poor performance. We observe that moderate values of 8 (such 0.05, 0.1, and 0.5) achieve relatively good final performance. These observations are consistent with our theoretical predictions. For example, inversely proportional to smaller 8 leads to slower convergence but smaller approximation error, whereas larger å improves convergence speed towards the approximate problem but incurs greater approximation error. Figure indicates a properly chosen thus can balance convergence speed and approximation error.
theory indicates that the convergence rate of SLFCB is
2.5
0.0
Utility
-7.5
6 0.01
-10.0
6 0.05
-125
6 0.10
6 0.50
11.00
6 1.00
2500
5000
7500
10000 Iteration
12500
15000
17500 20000
Figure 4: Comparison of different in SFLCB for the 3 nodes network.
7 Conclusions and future directions
In this paper, for coupled constrained BLO problem in Equation (T). theoretically analyzed the relationship between the original hyper-objective and the reformulated function 6 in Equa- tion 3 providing a solid justification for the validity of the reformulation. Especially, for the linearly constrained case, we proposed SFLCB, single-loop, Hessian free algorithm, improving the convergence rate from O(E Log(e on hyperparameter optimization for SVM and the transportation network design problem validated the practical efficiency of the proposed SFLCB algorithm. One limitation of our work that the analysis is restricted to deterministic and linearly constrained settings. A promising direction for future research to extend the current results to stochastic environments or more general constraint structures. Moreover, since the best-known complexity for first-order methods in unconstrained BLO 12 is ( (c).), is also an interesting problem whether we can achieve this optimal rate in the constrained cases.
log(e-1)) 1) O 3) over previous works [2 16]. Our experiments
10

---

Acknowledgements
The work of Wei Shen and Cong Shen was supported in part by the US National Science Foundation (NSF) under awards 2143559 and 2332060. The work of Jiawei Zhang was supported by the Office of the Vice Chancellor for Research and Graduate Education at the University Wisconsin-Madison with funding from the Wisconsin Alumni Research Foundation.
References
[1] Dimitri Bertsekas. Convex Optimization Theory, volume Athena Scientific, 2009.
[2] Jérôme Bolte, Edouard Pauwels, and Samuel Vaiter. Automatic differentiation of nonsmooth iterative algorithms. Advances in Neural Information Processing Systems, 35:26404-2644 2022.
[3] Congliang Chen, Jiawei Zhang, Shen, Peilin Zhao, and Zhiquan Luo. Communication effi- cient primal-dual algorithm for nonconvex nonsmooth distributed optimization. In International conference on artificial intelligence and statistics, pages 1594-1602. PMLR, 2021.
[4] Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A single-timeseee method for stochastic bilevel optimization. In International Conference on Artificial Intelligence and Statistics, pages 1466-2488. PMLR, 2022.
[5] Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. framework for bilevel optimization that enables stochastic and global variance reduction algorithms. Advances in Neural Information Processing Systems, 35:26698 --7180, 2022.
[6] Dheeru Dua, Casey Graff, et al. UCI machine learning repository. 2017.
[7] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. International Conference on Machine Learning, pages 1568-1577. PMLR, 2018.
[8] Lucy Gao, Jane Ye, Haian Yin, Shangzhi Zeng, and Jin Zhang. Value function based difference-of-come algorithm for bilevel hyperparameter selection problems. In International PMLR, 2022.
Conference on Machine Learning, pages
[9] Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint 1rXiv:1802.022444 2018
[10] Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complexity of hypergradient computation. International Conference on Machine Learning, pages 3748 3758. PMLR, 2020.
[11] Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor- critic. SIAM Journal on Optimization, 33(1):147-18) 2023.
[12] Feihu Huang. Optimal Hessian//acooban--reee nonconvex-Pi bilevel optimization. arXiv preprint arXiv:2407.1788 17823, 2024.
[13] Kaiyi Ji, Jason D Lee, Yingbin Liang, and H Vincent Poor. Convergence of meta-learning with task-specific adaptation over partial parameters. Advances in Neural Information Processing Systems, 33:1 1144091-5000 2020.
[14] Kaiyi Ji, Mingrui Liu, Yingbin Liang, and Lei Ying. Will bilevel optimizers benefit from loops. Advances Neural Information Processing Systems, 00:3011-3023, 2022.
[15] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882-4892. PMLR, 2021.
11

---

[16] Liuyuan Jiang, Quan Xiao, Victor M Tenorio, Fernando Real Real-Rojas, Antonio G Marques, and Tianyi Chen. A primallduul assisted penalty approach to bilevel optimization with coupled constraints. arXiv preprint arXiv:2406. 10148, 2024.
-aass-ddul-assistedd
[17] Xiaotian Jiang. Jiaxiang Li, Mingyi Hong, and Shuzhong Zhang. Barrier function for bilevel optimization with coupled lower-level constraints: Formulation, approximation and algorithms. arXiv preprint arXiv:24 10670, 2024.
[18] Prashant Khanduri, Joannis Tsaknakis, Yihua Zhang, Jia Liu, Sijia Liu, Jiawei Zhang, and Mingyi Hong. Linearly constrained bilevel optimization: smoothed implicit gradient approach. In International Conference on Machine Learning, pages 16291-16325. PMLR, 2023.
[19] Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in neural information processing systems, 34:30271-302833 2021.
[20] Guy Kornowski, Swati Padmanabhan, Kai Wang, Zhe Zhang, and Suvrit Sra. First-order methods for linearly constrained bilevel optimization. arXiv preprint arXiv:2406. 12771, 2024.
[21] Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. arXiv preprint arXiv:2309.01753, 2023.
[22] Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning, pages 18083-18111 PMLR, 2023.
[23] Hanwen Liang, Shifeng Zhang, Jiacheng Sun, Xingqiu He, Weiran Huang, Kechen Zhuang, and Zhenguo Li. Darts+: Improved differentiable architecture search with early stopping. arXiv preprint arXiv; 06035, 2019.
[24] Tianyi Lin, Chi Jin, and Michael Jordan. Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pages 2738-2779, PMLR, 2020.
[25] Bo Liu, Mao Ye, Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: A simple first-order approach. Advances in neural information processing systems, 15:17248-1728 2022.
[26] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprini 1806000000 2018
[27] Risheng Liu, Jiaxin Gao, Jin Zhang, Deyu Meng, and Zhouchen Lin. Investigating bi-level optimization for learning and vision from unified perspective: A survey and beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(12):00055-1006,, 2021.
[28] Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A value-fure www.-funnttttaaaaeeeeeee interior-point method for non-convex bi-level optimization. In International conference on PMLR, 2021.
machine learning pages
[29] Risheng Liu, Yaohua Liu, Shangzhi Zeng, and Jin Zhang. Towards cradient-basee bilevel opti- mization with non-convex followers and beyond. Advances in Neural Information Processing Systems, 34:8662-8675, 8675, 2021.
[30] Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. In International Conference on Machine Learning, pages 6515 PMLR, 2020.
[31] Songtao Lu. Slm: A smoothed first-order lagrangian method for structured constrained noncon- vex optimization. Advances in Neural Information Processing Systems, 36, 2024.
[32] Zhaosong Lu and Sanyou Mei. First-order penalty methods for bilevel optimization. SIAM Journal on Optimization, 1977)199771196, 2024.
12

---

[33] Matthew MacKay, Paul Vicol, Jon Lorraine, David Duvenaud, and Roger Grosse. Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. arXiv preprini arXiv: 1903.03088, 2019.
[34] Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-based hyperparameter opti- mization through reversible learning. In International Conference on Machine Learning, pages 2113-2122. PMLR, 2015.
[35] Akshay Mehra and Jihun Hamm. Penalty method for inversion- free deep bilevel optimization. In Asian conference machine learning. pages 347-362. PMLR, 2021.
[36] Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference Muchine Learning, pages 737-746. PMLR, 2016.
[37] Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. Advances in Neural Information Processing Systems, 32, 2019.
[38] Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back- propagation for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics,, pages 1723-1732. PMLR, 2019.
[39] Han Shen and Tianyi Chen, On penalty-based bilevel gradient descent method. International Conference Machine Learning, pages 30992-31015. PMLR, 2023.
[40] Ankur Sinha, Pekka Malo, and Kalyanmoy Deb. A review on bilevel optimization: From classical to evolutionary approaches and applications. IEEE Transactions on Evolutionary Computation, 22(2):276-29) 2017.
[41] Richard S Sutton. Reinforcement learning: An introduction. A Bradford Book, 2018.
[42] Ioannis Tsaknakis, Prashant Khanduri, and Mingyi Hong. An implicit gradient-type method for linearly constrained bilevel problems. In 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages
IEEE, 2022.
[43] loannis Tsaknakis, Prashant Khanduri, and Mingyi Hong. An implicit gradient method for con- strained bilevel problems using barrier approximation. In 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1-5. IEEE, 2023.
[44] Gerd Wachsmuth. On LICQ and the uniqueness of lagrange multipliers. Operations Research Letters, 41(1):78-80, 2013.
[45] Quan Xiao, Han Shen, Wotao Yin, and Tianyi Chen. Altemating projected sgd for equality- constrained bilevel optimization. In International Conference on Artificial Intelligence and Statistics, pages 987-1023. PMLR, 2023.
[46] Siyuan Xu and Minghui Zhu. Efficient gradient approximation method for constrained bilevel optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 22509-12517 2023.
[47] Haikuo Yang. Luo Luo, Chris Junchi Li, and Michael Jordan. Accelerating inexact hypergra- dient descent for bilevel optimization. arXiv preprint arXiv:2307.00/26 2023.
[48] Shuoguang Yang, Xuezhou Zhang, and Mengdi Wang. Decentralized gossip-based stochastic bilevel optimization over communication networks. Advances in Neural Information Processing Systems, 35:238-255 2-22, 2022.
[49] Wei Yao, Haian Yin, Shangzhi Zeng, and Jin Zhang. Overcoming lower-level constraints in bilevel optimization: A novel approach with regularized gap functions. arXiv preprint arXiv:2406.01992, 2024.
[50] Wei Yao, Chengming Yu, Shangzhi Zeng, and Jin Zhang. Constrained bi-level optimization: Proximal lagrangian value function approach and Hessian-free algorithm. arXiv preprint arXiv:2401.16164, 2024.
13

---

[51] Jiawei Zhang and Zhi tuanQ Luo. A global dual enror bound and its application to the analysis of linearly constrained nonconvex optimization. SIAM Journal on Optimization, 32(3):2319-233) 2022.
[52] Yihua Zhang, Prashant Khanduri, Ioannis Tsaknakis, Yuguang Yao, Mingyi Hong, and Sijia Liu. An introduction to bilevel optimization: Foundations and applications in signal processing and machine learning. IEEE Signal Processing Magazine, ++(()):8-59) 2024.
[53] Yihua Zhang, Guanhua Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, and Sijia Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. In International Conference Machine Learning, pages 26693-267 12. PMLR, 2022.
14

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer:
[Yes]
Justification:
We clearly state this paper's contributions and scope in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discussed the limitations of this work in Section 7
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

We clearly state all the assumptions for each theorem. The proofs can be found in Appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We provide detailed experimental settings in Appendix F
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [Yes]
Justification: We provide the open access to our code and provide detailed experimental settings in Appendix
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https
wtt.ggiddde/eeSSSuunnrnn ssiicyolicy) for more details. hetpolliiigguddde/ooooooo
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide detailed experimental settings in Appendix F
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report the error bar in Figure 2 The definition of the error bar can be found in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
17

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the information on the computer resources in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: To the best of our knowledge, the research conducted in this paper fully conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is theoretical in nature and does not have immediate direct societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
To the best of our knowledge, we do not think our paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We used diabetes dataset and cited the original paper.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
21

---

Appendix
The Appendix is organized as follows. In Appendix A we introduce some useful lemmas that will be utilized in the subsequent proofs. Appendix B we introduce some notations that will be used throughout the Appendix. In Appendix [ we provide the proofs for the lemmas and theorems in Section 4 In Appendix D we provide proofs for Theorem 5.4 and Corollary 5.5) In Appendix F provide proofs for Theorem [.2 and Corollary [5.3] In Appendix F we present the detailed
experimental settings along with additional hyperparameter sensitivity analysis experiments.
A Useful Lemmas
Lemma A.1 (Lemma 12 in B.. Suppose f(-) is I-smooth and u-strongly convex, X is comvex closed set, and 1) I 1/l. Define x² argmin f(x) and x 11x (x)) Then, we have
2 pnj
|| x'1 S
|| x+1
Lemma A.2 (Lemma 23 in (24) Suppose for any fixed y E y. f(x, y) u-strongly convex w.r.f. and suppose for any V1 32 V X, [V, y1 V V=f(x, v2)) S 1ly11 v2ll. Define x (y) = argmingexx [(x,1) v). Then, we have
(x0)))) x² (222)l - - 1191 3/2l
Lemma A.3 (Theorem 4.1 in (5I). Suppose f(x) Rd + R I-smooth and u-strongly convex, {x P|Ar b = r), where C, A Rd2xd, e, e, E Rd Define
Cz|Cz s S(r)
[xx, u) = [(x) TuTT(As (Ax - b)
x² (u) = argmin L(x, u)
xEP
x argmin f(x)
wES(r)
where u E I2d2 is the Lagrange multiplier. We have
|| (u) اللl S or Ax bll
|| zill S |
where
V2 + +1) 02
11
M = AT CT
0=
max o 2 (M) miu (M) MEB(M)
M is the of all submatrices of M with full row rank.
Lemma A.4. Suppose f(x)) : Rdz + T is p-strongly convex W.r.t. x. Define L(I, a, a)
f(x) +x (Ax b- a) - Ax al12, where a, a,u,b be Rdd, A E Rdd, (0, 10/ (A)) Denoting x' (x a T)T M(x', u) M(x, a, u), we have L(x', u) pe-strongly convex w.r.l. x'.
where Ms min{u pamx (A), })
22

---

Proof. For any 22,22 E R ,
02,00 02 E R denoting 2 (xT 22 = a2) =
(A, -1), we have
L( L1z22 u) (V u). 2/22
=f(x1) - f(22) + +u A'(''' x²2) - 2 211A''' b112
P 21Aa' bl2
2
(VaI(v2), 11 - 02) - wn// A'(n' x22) - -(A'T A'uz2 - A b) T (x) 2t2)
2 I|m - x21l + 2 A''1 - =/2)1?
"
11 || - 12ll² + | - -22l2²
P
22 2
A| - x2)11
2
po max (A)
|| r22
P ll01 - azll
2
4
|0 x221?
where Uu min - po maxx (A), 2)
B
Notations
Denote is = M2/22. We introduce the following notations.
$,(2,9 2) (5f(x, + + g(x, z))
08(x, = (.f(. + g(,,)) + - g(x,2)
9s(2, v) (z( (( 9
0x)) min 96(x.v)
yE)(Z)
min g(z,g) g²(x) vE)(2)
Lg la 1111
L = 4/ + 21
((x) fz. (x))
(5(x) = 03 y (z),
65(x) os(II, y (z),
When 8 S Mg//21.1, we have ,1,,1 S pg/2 = is and thus, go (2, y) is -y-stooth and øs (z(2, y, 2) is Ly-smooth.
C Reformulation
In this section, we provide the proofs for the lemmas and theorems in Section
Theorem 4.1
When Assumption 3.1 3.2 and 3.3 hold, we have
812
s ((x) (8(x)) S
2/1
f.
(x) (x)]
1gg
Proof. Similar results and proofs of Theorem 4. can also be found in 21 16] For completeness, we also provide proofs for Theorem here.
23

---

Note that (x) satisfy
(5V, + V va (5(() = vz(
Since g(x, :) is My strongyy concave and 1.11--1m000 smooth and Lg 2 1..1. according to Lemma have
A.1
wc
2 (x) - (1x)l
11ub (2)
(v)()) (3
2
[[Ty(s) - uf uo(2 (x)
My
[Iy (V3 (x) - V (8))
25
V2f (x))
Mg
300
Pg
For (z(x). we have
25(x) -f vz (6 g0 (z)))
<f(,,0' (x)) ((t,,((())) ,la,v' (x)))
and
Φ5(x) 93 19(2, yē (x)) - g(.,y"(x)))
2f(x, + M9
Ilub (z) - -y-(xx)() (x)
28
2/(2 y² (x)) +
Hg
lluā (x) - (x)) 1,.0 (15()))(()))))))))))))))))))(( (x))
28
80700
2
where the first equality due to the quadratic growth of strongly convex function, the last equality is due to az? + ba 2 bb²/ b2/))
Lemma 4.4
When Assumption 3.1
3.2
3.3 hold and 8 S Ut/ f,),) for all x E X, LICQ condition (Defini-
tion 4.3) hold for y xx) and y (r), then there exist the corresponding unique Lagrangian multipliers
X (z) E Rd and (x) dd such that
(x(x) = arginax min g(x, v) (1((,1))) XER, sE)
(14)
A1(x) argmax min 8f(x, g(x,)) A (( AER, *E)(())
(15)
Furthermore, we have
13 (x)) V V.g(z,nū (.Mr.))))))) Vag(z, y (x)) - V.h(z, (z)) (z)).
(16)
Proof. The uniqueness of Lagrangian multipliers a direct result from the LICQ condition
45
According to Lemmas 2 and 3 in [16). We know that when Assumption 3.1 3.2
3.3 hold, 8 <

---

(g/(2( if, for all æ e X, LICQ condition (Definition 4.3 holds for (x) and yī (z). defining ((x) = = (z)) and vz(x) (=l, we have
V (=) ( Vatis (
V +
Since 25(x) fz, (z(()) + (95 (000(, - we have
{Φソ(2) ( V (z)) + V
- - (
Lemma 4.7
When Assumption 3./ 3.2 3.3 4.6 hold, for a given æ, Assumption 4.5 and the LICQ condition
(Definition 4.3) holds for y (z), then (Φ(x) exists at x and can be expressed as
( vz,( + (Vy*(z)) Vv)())) vuf(z, (z))
where Vy (z) can be calculated according to 20
Proof. According to Theorem in [46]. we know that when Assumption 3.1 3.2 3.3 4.6 hold, if, for given æ, Assumption 4.5 and exists at x.
and the LICQ (Definition 4.3)) condition holds for y (z), then (
Moreover, we can give the explicit expression of (D(r).
With E Rdd,, we have the following Lagrangian function
f(x, y, A) = g(z v) + X h(x. v)
Denote (x) the optimal Lagrangian multiplier, I, [dp] the active set of y" (xx, i.e. I. = {i E [da][h(x, y)l; = 0} Denote h(2, yx())" ) = [h(I, y (z))lz, and (x)x) [x"(z)lz, We
have the following KKT conditions:
V Vos(a,y(<)) Vyh(e,, (x(x)= (
Ma, y" (x)) = 0.
Differentiating the KKT conditions with respect x, we have
(z) (at
Xx(x))
V Veh(z,v v + VV,:))))VVVV/iiii/L( Vy (A
Thus, Vy"(x) and X (x) satisfy the following equation.
V2 Vy y (z) +
v,b(a,y(<)))
[z((x)
(17)
V vyl(z,y((x)
0
[)*(z)
22 22 yy (z) - (c) X+(a]
(18)
V (h(2
Denote
V 1f (x)) (z)
(yh(,,y()))
(19)
Vyh(o,y(xx)
Since is strongly convex, is convex, Vi (x)) > 0. ( (x))) 2 0. More-
since (*) 0, we have V2 2 + b(e [x) > 0. Additionally,
25

---

Vyh(x, (x)) has full row rank. Thus, according to Lemma A.2 in (20], H is invertible. We can calculate (x) and X (xx with the following equation.
(x) v
V 1 y (x)) - (a)))
H
(20)
-Vh(Z,y((())
According to 99. have
VΦ(2)=
V=(z)=V=J(E.))) (VV
Theorem 4.9
When Assumption 3.1 we have
3.2 3.3 4.6 hold, and 8 $ /2/() Assumption 4.8 holds for given
(+ ( (x) S 0(8).
Proof. With À E Rd,, we have the following Lagrangian function
La y A) gs (2, v) + X h(x,y)
Denote (z) as the optimal Lagrangian multiplier. We have the following KKT conditions. Vy95(z, vā (z)) + v vz))) (z(x) h(x y (z)) = 0.
Differentiating the KKT conditions with respect to we have
V 2 (y vz (bx) Ve, X2(x) d do (x)
v ,,, (z) d xz(x) =
vyh(z, db (Z) =0
We have the following equation:
2 Vy (z, y3 (x)) + 22 )(.
vyh(a,((()))
(x)
by
V (nb(z,,((z))
(x)
V y (x)))
(21)
Denote
V2 Viygs V2, vx)) + (x Vyh(2,8(())) V Vy (x))
Hs
(22)
We can notice that Hā=o H, where H is defined in 19
Then, have
Vag(z,
Vallz
- V.glz, Val(,, (
lim
8
2 (x)) (e) Xx()]]
ap yg (x)
V vah(z,n"(>))
(x)
15
V2g0(,, (x)) + (x))
V yf fx, v
H
v=h(z,v((z)
0
26

---

where we denote
V 2 ( y +
T
Vah(z,yy(z))
Note that according to 20 we have
Vy((2) [1 0 1T
V v
Thus,
lim
5
= (v)"
(23)
Note that, according to Lemma 4.4 we have
V (z))))))()
- V292,, + (x)
V2b(2x)
(a](I,
Then, we consider to bound ( V
V - VQ(x)
(())( - Vo
Vag(E, + - W.
[V
V.
V M(x (=)) (x)) d8 1 v=h(z,v((x))) \5(x))s=
d8
(24)
where the last equality is due to 23
For the first term in 24 we have
2 f.1
[V.s(,,)((z)) Vaf(z,v"
< v² v²(x)]l s
27

---

For the remaindering terms in 24 we have
T=g(x.03(=)) Vog(z,v((<) (z "عا
Vah(a, vs (=)))((())) (aM))))))))) - ( (f
V2h(a,y'(x)
(1)) م
(
(n T.(() - V (1))) (x)) d
2o ( di
1=
1
+
Vay at 01++) V.M(z. (z))dtt
dt
((ig((, d
V.h(r,y de x3(x) lo=odt
8 0=
1
-
V (+)) d
ni (1)
1=
+ 8
(xng(e,
vi() - ) dt
1=
1
b ue vo) (z)dt
+
1
(a,((,,"" -.((()) _ (
d
+
1
+ 8
V2hhl, - vah(a, "² (x)) (z)dt
dl
+ / Vah(z,y (z))
1
dt -x(a))X((0)le dt
(25)
For the first term in 25 we have
1
22
V2 y (x)))
dt v (x)dt
8
1=
1
d
421l27)))) (z)l dt
12202 d.
1=0
where the last equality is due to Lemma C.I Similarly, for the third, fifth terms in 25 we have
V2
(i)
(o)
1=
+
- dt
xt))att
1=
<6(1n.2 1 1,,
28

---

For the second term in 25 we have
1
v
(
(i))(())
ds u/ (x)) dtll
d
8
d2
(x)]
do2 Ue (d)slt
8
(x)]l
max E[00,5]
T 2. 22 (x)) 8²
,
where the last equality is due to Lemma C.1 Similarly, for the fourth, sixth terms in we have
1
d
d
((r (x))
dt (i)
ds Vz (+))
dt
8 1=0
1
Sr
d
Vah(z,y (x))
di M)) 13(=))==0
dt
1=0
<8(1n,1 + Ln
Therefore,
(0))))))()))))))))) 50()).
Lemma C.1. When Assumption 3.1 for a given n, we have
3.2
3.3
4.6 hold, and 6 S /// (2) if Assumption 4.8 holds
25 y3 (x)
d
- C.
48 {1(x)
Je U (x)
$ Lug
og 1z(2))
where Cy, Ly are O(1) constants.
Proof.
According to
21 have
20 (x)
H ps,
28 (x)
where
2 V5 (2, (x() + 2 (z)
Voh(1,1((1))
H;
V he, y/ (z))
(1, (x))
p8
According to Lemma
C.2
we have
d (x))
< || 'ss S Cul Cy-
A (z)
Denote
B DT D
Ho, H5, =
29

---

where
B (1, (x)) V 14 (x)) X/g (x) - v 1 (x)) - V he (x)) X3, (a)
82 V Ma (x)) 6. (x)) + 1g
vg y3 (x))
V (x)) (2) 1
+
=6 (o (1) (2.
(x)) V / No (z)) - 51) (3 (x))
Vng( V5 (x) + - (x)) (x)) (x)
+ 2 v8, (+)) 11, 13, (x)].
Thus
(2 Cy + 1,,1 + C2 + 2l + +,,100y 102 -6il
|B|| <
11,1
|D] = VV, Max, uāg (x))
,,((,,, vā, (x)) S 1n,1 (vā, (1) vo, (x)) S C,, 521
Therefore, we have
1H - Ho, 11 S MH 521
Moreover, we have
25 (x) 26 (t)
y (a)
do Xxx (x)
d
H Ps. - H P52ll
(HH²) H P6, 1//1 H (p6, pb2)]l (p6,
< (Hg, (H8, Ho, HH5,
|1lp,,) + ||H5,1111Pp - -P |l
< (H CnH 181 52 -Ly181 82
where by = (CH + Cnl,.).
Lemma C.2. For Ha defined in 122p. we have
|1 Cn,
where Ch is an ((1) constant depending on Po 1g.1 4.11 dns 4R,1 Smins Smaxi A.
Proof. Denote
2 My vx()))
V2 M (x)) (z(a)) V Vyh(,,
(x:)) We have
[A C
-A-ICT(CA-CCTT) (CA- T1
H
-(CA-
According to Assumption 4.8
we know that [A](x)]] S A. Thus, 0 S [4]())]; S A. We have
2
A 11 fgg
|||| < Ly + di A A
|C| S 5max
|C-1 1
Smin
Denote
B DT D E
H
we have |B|| < CB.IDD < CD. | S CE and so that || ||,7'|| S Ch, where CB, CD, CE. Ch are O11) constants depending on Ag 1,,, I, y day An.1, 8min, 8max, A.
30

---

D Proofs of Theorem 5.4 and Corollary 5.5
In this section, provide proofs for Theorem 5.4 and Corollary 5.5 notations and lemmas that will be used this section.
We first introduce the additional
Notations
( ,2' u, ,2',,,,,,) 6s(2, yo +u (A'y' 'A'z'' b)
P1 11''y'
b11²
P2 11 b11
2
LK = ls + -1 + max(pl, P2 p max (A')
My min [ 1s - PI o (A):
P1
2
= min (1g max P2 }
V 2z(2)
min (5(
sc)(2)
=0) argmin (Ir, z)
=EY(x)
19 (z, u) = argmin K (x, V/ ,/, v) y'EP,
=< v) = arginax K(x,1) 2', u, ='EP,
(1 u) azfx, u) TT- 50 (="( ,3 uz, T =='(xx,))
(12,2',,0 (z, u), u.
q(x, v) 6s(2, (z),
v (A'z' -6) -) P1 (x,,)
b11
1 V, K( 3/. 24, ue, v)) 2g( v2)) - dl (z 2/1 uu, v1)
Lemma D.I. When (gg(21),)), 0 0 ss
Hوーقlي and 0 p2 S (a K(x, y/, u,, is (A) Myy-Strongly convex w.r.f. y', Me-strongly concave w.rl. z', and Læ-smooth w.rl. x, ,
Proof. According to Lemma A.4 we know that K (x, y/,2 u. v) is -tyonnyy convex w.r.t. y. Mu-strongly concave w.r.t. z' Moreover
V ( V.0s(z,
V (z,y,' V,0s(2, v.2) A u + T b)
VzK(z,B/,2'uu VeOs(E, A - A (A'z' b)
Thus, K(x, 3/ 2, u, v) is Lx- w.r.t. 2''
31

---

Lemma D.2. When ò S (2) 0 P1 I
" and 0 S P2 S Po
(A) 7g S LK, we
oinx (A)
have
llu8" (at, w1)
16 (I., u2)
1 yyu yullur
U2
(26)
ll//" (21, u) 1/5 (22, W|
|| x2
(27)
(='((, v1) 2x, 02)ll < 2z |1 U2
(28)
[='( u) - 2""22, w)ll $ Canl|>r - x2ll
(29)
(15( (x2)) S Tys | z2ll
(30)
(x1) - 2 -d=2))l $ dza | - x2ll
(31)
lu8" (a, u) - v5" (z)]] s ",yl''y33 (z, u) - bl
(32)
(x' v) z ==())]] 5 (,, - 110 (2x, u) - s'1 || s dge Ie VV, v) + aaaalaa-- IT_ (a - 7 u, v))l
(33)
(34)
(x,, 2' - azel V (z, gz, u,) + 1111111111 7/ VI 5/ 2. u, v))l
(35)
110/" 1441) - vill v
|1 -''ll
(36)
Myy
2
11 (12,, 1++1) - 2411 v
||
- 2111
(37)
|
where a
(A')
Byz yx
Lx
My
(A))
Mz Ozx
LR
Bye
My
2
Oze
2, 0a 'y
2LK
Lx
03 Mo
Oys
Uge
bg
V2(0L' + 1)
0y
My
V2(0L + 1)
0,
A GT
M
0
Od xd Xdn
0
G =
Idn
0
max o max (M /M)om min (M) MEB((M
M is the set of all submatrices of M with full row rank.
Proof. 26
17
28
31 is due to Lemma A.2
34
35
36
37
is due to
Lemma
32
33
is due to Lemma A.3
D.1 Potential function
In this subsection, we will prove the following descent lemma for V,,
Lemma D.3. When ā < / (21,) 11), 0 S P1 S - 2/(Txx + 4Taa), 1 = min
Tiu (A) 0 E P2 S o (A). By = 1/(4Txx). 12 =
Hg
n (96T2)) nu/ (B/(6A0TT2)) no/ (40 123); 2/(T.x
4ha + 8L)) The = =ny1, /320/ max (A)). 1/v 1=
/ (320 (a) (A)), we have
1
Vn - Ve+1 2
|| - 2x + 16ny
11
1/2 12
+
|| - 1112
4m
811=
+
nu
|AA''/5" (Ite, u(++)) 1) - -b1l2 + 7lu
I|A'= (xze, 1e+1) b112
4
2
+
7a
| 2/2// - b112 + no ||''' - b112 + na
[os(22)11
4
4
4
32

---

Thus,
4 Tm
Vos(
(Vo
mmnn Vi)
(38)
T
c
Proof. First, for function d, we have
d(wi zy U141, ut+1) d( 2/1 u1, Uz)
= K( v88 (Te, (44444: 1), 2/. 1441, 1,411 K( 9/8 (Zr, u,), 2/, U2, v1)
(1 1/8 (at, ue+1), 2/, 1441, 11+1) - K( 9/8 (2t, u(41), 2/, Ue, v1)
(wl-1 u.) (A'v/8 (Ize Me+1) b) - (o141 - 21) (A' 24 b)
nollA' 2/2 bll + nu 4/5 (zi, ue+1) - (A'y/. - b)
Note that
V Vnd(,, ,',,,',,,, u, V.ds( 13 (x, u)
V V 2', 2,,,) Vag(z, 2) - 0 P2 T (A'zz - -b] 4 (A' -b) b)
Thus, according to Lemma D.2 we know that v,d(x, z', u, v) is (Ie + continouuss w.r.f.
st 2' and V2d(x,22,,,, u, is Lx continuuus w.r.t. x, z'. Define Itd = max (Ls + Lo yx, Lg). ). We have
d(x Z u44 Ut+1) - d( z/2 u vt+1)
K (Izz s/ (Ix, 1e+1), Eo u v+41) Je+1 - xz)
2 K 3/8 (Ie, ue+1), 2/. "4+1 11+1) 2441 21)
La (1 2111 + || - 2
2
ds (Ie, y (Ir, 11+1), 2t), Zt+1 - x²) + - || 24,1
2 2(V V
17=
La (1 22,1 + | - 2/11²)
Then, for function q, we have
g(Fe; v2) - q( v(+1)
> K (Ki, y/ (xt), 2"d (x+, ve), ur vz) - K K(r,, wo (2t), (x2, ve+1). ue, vc+1)
2 2 (1 1/5 (mt), 2 (xee 0141), ), u4 v2) - K(r,, 1/5 (xx), 2 (2s, ve+1), ue v(41)
(A'2 (zz, U241) - b) T (A'2)) b)
Note that
V V24(I, v) = Va (z), x" (I, Thus, according to Lemma D.2 q(: v) is T.g = (Isp + La002z + -gggys) We have q Ut+1)
g( vt41)
L (1104111 -xol3))
2(V (xre, x- (It, U(41)), I(+1)
2
Finally, for function K, we have
K (at, sho z/n ue, ve) - K K(r,, whs 2/0 wett, vo+1) = -mall =-1//
A'sb - b112 + n. 11 - 611²
and
K (xt, V/. 2/, u1-1. V141)
K
(( V
2/+11 U,+1, 2/+1)
1
|1ret1 22 1 -
1
-11647 2/1122 - _
1 2111?
1/2
1/1
1/2
LK
(11æ0+1
=x212 + -111441 - 26l1 + 1| - =611?)
2
33

---

Thus, for Vt, we have
Vi - Ve+1
1
2 Voos(zr, y (Tt, (e+1)))) 2), 2++1 - xz) + - || - 2/12
Ld (1 =xel + 11 - =111?)
+ na (A'v/" (Te, ue+1) b) (A'v/- - b) 11ll'' - -112
+ ViV 11 (ar)); (Ize m(+1)), xz re+1)
+ 27 (1re - b) (A's4 b) T (1(4411411 - xzel3)
1 -111--111 |1b(41 - 3/l12 - 47/- 1 - 2/113 Bu 1A' - b112 Du ||A' - b11
+ 4mp
| - 2
4nly
L (1 - 22.1? + |1 - v.111 + | - =11
8
2 - |/ #0 (xe, yo (Iee u(+1), V V 3o (2z), )²=
2² (Ii, (111))++1)lllll - xz
Mu
7/
|| - b11² + 17a 1| A| (zt, u1+1) b112 7/1 |lA'v/ -A'y's (xe, u1+1)ll
+
2
4
2
2
+
+ T
No
|| - b112 + A n2' (xr, u(+1) - b112 nu Al'' - A'z' ((1))11))
4
The
V
Vaths (1 yg (1x), x" ",x,,, e+1) V va yt, (t 21)1
2
Te V 2 3/ (2)), 2" (x,, 21+1 12 +
+
|20, - I1+1
27,
2
1
LK
La
|.++11 - xz 22112
41
1
Lg
La
+
|| 2411
17
4m²=
8
2
1
LK
+
|1 1/.112
Afly
8
|
12
2n L 11//5 (I', (441) v/- -x)011) 1 2n 20/2L (2 (21, Ul+1) - 24,1
41/-
Mu
||A y/ b112 + Thu
|| 1/55%"" (Ie, uc+1) - -612 m maxe (A)
113//" (Ire, ue+1) -2/11
4
2
2
+ Th
||A' b112 no.1144 17'2" 1111''((''00 (21, b112 no max (A)ll2" (Ize U(t1) - 2/112
4
13 (xx) 1/2 (rr, (11 -2n 1.z 1//5" (Fe, m+11) - will n7 1.811=" 222222(( (are, 0o41) - 2411
+ Ne || V Veds(an (2,, y (Iz), x (1x)))1²- MooL || (xx) 2" (x1, (21112++1)1 +
1 || 0141ll²
4
2n
1
LK
La
+
Tng
||0141
xzel 1l?
411w
2
3
T
Laa
+
||
2/,12
4m7=
8
2
1
LK
+
I1
1/.12.
411y
34

---

and
1/2
V4+1
LK
La
Lug |0++1 - Dzll
21/r.
A1p
Ank
8
2
LK
|lubt1 - 1/11? - [4 1ig + 1/ Muxaaa((A)
11u/8 (az, me+1) - v/ll2
4fyy
8
2
3
LK
La
|| =1112 (31 + max (A)) || (ate
(Iee Ve+1) - =111
8
2
The 114'vl - b1b2 +
Thu
|| (Iea, me+1) b12² - An
L -Ana Lallus (e41) - 1/6 (xx))1
4
2
Th 1 1| 11a""((x (2i, Uc+1) - (xx))1 1|44 - b1(2 + no Il'''''' (22,, ue+1) bb12
Th
4
2
+
11
[os( 1²
4
1
LK
Ld Ln) || - xell?
211
8
2
LK
16n, 1.g max
1106+2 - will?
Ar/y
8
12
LK
Ld
12 L3 + o
Pmax (4)
|1 - =/11?
41/²
8
2
12:12
7u
4o of (
|| u/5 (Iee ue+1) - bl12
2
+
I|A''² (x Ut+1) - b11
2
+ 7/u
I|A'v' - 6112
+ Th |A' - b112 + ne
[+)((=))1
4
4
where the last equality is due to Lemma D.2
Thus, when 8 S M
(2l,.)2 0 S P1 S "g " 12 0 P2 S --nl 7hy = 1/(4Lx),
(A)
(A):
= n2 = 2/([KK +
4 4Ta)) The / (2,
/o/ /a/(640 (11)))(((1))))))2
Th = max
(A)), The
we have
V1 Vi+1
1 || - =/ll²
|| - xeel + 167/y
11 1/1122 +
41/o
811=
+ Tu || (#re, u1+1)
-112 + 7
11 (xre U(41) b112
4
+ Th
||A'v// - b112 21 | - b112 + 7
(xs(x))))
(39)
4
Thus.
4 (Vo min Vi)
Vos( Tne
(40)
35

---

Proof of Theorem 5.4
When S (2 P1 He م 0 p2 I oa Bl 1/((///()))))) 17 = 2/ +4Ld).
oine (A)
7 min / (1. (9 1// (6A0) Be/ (10 2/ + nm
(320 by (320 (A)), n7 = n (320 maxe (A)), according to (40), we have
T-1 Vos(T=))
4
(Vo min V4)
(41)
Tn
Note that
1 V1 K (ax, ve 2/, ue, v6) + +2((22, 01) - d(Ies 24 ue, Us)
4
5
5
50
55217.0
22q v1) 4dd d( 2/, ue, v1)
_ 70(z vz)
4 x 2
4
8/1
Therefore, when 8 = (ct), with T =((-)), we have 1 E [T]. such that [ ! (xi()ll S6.
Moreover, if we have zo. yo, 2o, uo. such that
Ilvo y (2o) S O(6)
|| v/ (oo, un) bl < O())
11 bl < O(6)
|| 20 2" (ax) S 0(6)
|| z" (ro, vo) bb s 0(6)
2 bl S <0())
Then, we have
Vo
8f (20: yu) (g(x0o vo) g( 20)) un (A'v' b) vo- (A'2') - b)
PL 11''66 - -b12-
P2 1l''6' bll2
2
2 (f Vī (z0)) (g(20, vī (2o)) ((0o,,"(z00) vn))) -n0 (A'z" vo) -b) b)
P2 11''' (2o, 0o) - bl13
un)) -no (A'26 b)
[f(oo: uo)) (g( yā u0)) g( 20)) uo (A' '/8 (ro, b)
P1 |1''v (Iu, uo) b112 P2
1| -B112
2
550()0) +O11) 3" (zo))l + (xo) 3" (zo))l + (2o, uo) (zo)]l
O(1)C,((1 ~ -10 ( 2" (zo, vo) + Vl (zo. uo) zoll)
- bll - +||
b1| + 114'166 - bll + 114'v6 b112
I|A''= (1o''""zoo (z)) - IIA'' un) 612 ||A' (No, up) - bll + 11'' (Io, uo) - bll2)
(20( 0())
where - max(g(wo, (o)_W,o,,)))))))))) g(0o, =u), g(zo, 2z (zo), g(20 =" (*o, vo)), g( ( uo)). C {v 1 v) < G), C. supyec Vog(zo, v). Since g( y) is strongly convex w.n. y, its sub-level
36

---

set C is compact and convex. Moreover, since is Lipschitz smoothness, its gradient in this compact set C' is upper bounded by an (11) constant Cg.
We can notice that
(0) - T + -0)6)=((
Vo - min V2 5
1
4
and
1 T [
4
[oos(,;))
Tn (V min Vi) 0
T8
T
Therefore, we can find an e-stationary point of (2(x) with a complexity of O(e
Proof of Corollary
For fixed To. define Wi 1 (To, V/: z/s u4 vz) - 2q(20: vz) - d(zo, 2/1 ue, vz). According to (3) with appropriate parameters, we have
W. W++1
1
|1 - v/ll + - 11 =1112
2
1677y
817;
+
Thu
|A''//" (100: M++1) ( bbl2 +
||A'='* (t+1) b11
4
2
+
77
Al''v v - b112 + 170
|| bl1
4
4
Thus, when T T= 0(?)), we can find E T such that
11/41 s/1l I 6
A (zo, u4+1) - b/1 S 8
1|'' - bll I
| - = 5
[A'=="(xoo U1+1) - bll 5
|| 2// bll 28
Denote the active set at v (2)) as Io Ja [d,]/I. Define A min | (zu)) De-
note the active set of 2 (zo) I8, J [dn]/I. Define A m ra 3 [o)] Set
< mino)"/(6o.). A (60 v, A (6op)) A (//(6r))) According to Lemma D.4 we have
| (z0) S O())
|lu411 00 (zo) S O())
Then, if we set 16 = 1/. 2/ 2/1 uo u4+1, th Ut+1, with Fu, yn 26 uo vu as initial points, according to Theorem 5.4 we can find an e-stationary point of 4 with a complexity of O(e
Thus, the total complexity is O + + O(E-3)
Lemma D.4. For fixed Tu. denote the active set at yī (2o) as Ia Ja -ddn/I. We have
(2o))z> = 0 and [a](20)] < O. Suppose shin Omiul (Aza) > 0. Define A
minje [[az(zu)]el- When 11 3/ll s A" /(6Ga), A' (Zo, u(t1) -bl s A" (60())))) we
have
[14+1 - (zo)ll So Souyyollb44 sill + aaaxoll (Io: u1+1) - bll + AouzzolAA Aly', bll
where Juyzz = 1 + L+omax mymm
+
Ly Tu2z0 = Ly za
Oulæ0
Pia (A).
Similarty, for a fixed Fo. denote the active set of x" (x0) as Is, J [dn]/I. Suppose
3
min amin (Azo) > 0. Define A = min5e (2o)lok When || - =1ll S
A (6/ A|A'2/ (xo, U1+1) - S A /(6rz), we have
||ue4] v² (2o)1l Souznol 1 12 2''ll + @22nall A'' (zo: Ut41) - bll + Twien A''z bll
where Tuzan
1 + L2g00 0w2.0
L2 Tulsn p20max (A)
miin
miin
Amin
37

---

Proof. Denote the active set of (zu) as I, J = =dd.//I. We have (az(2a)]z and (aj(mo)lo < Note that
||o-- - -3((20)) S11ví - v/3 (zo)] - 11ye 13 (zo, ur- 131l + 11v6 (2n) - 23 (zro u++1)ll Saa - sill + oy Al's's (2o, u(+1) - bbl
vill - A/(60a), ||A' (ro, u4+1) = A/(6oy)) Define A minjer [ When 11 -vll we have
1
1la. a0 - A
3 1
lau+1 - - - 6
Thus, for J, we have
Jasly <
[0141l < 0
Therefore, there are no projection in the update of ax+1 and we have
[[[u+1l3 [x)(2)))>1 = 1| = (lastils - [aelz)ll $ nl
||a+11 0z
Moreover, for I, we have
Vngo (8(()) A (ug(o))) =
Thus,
1
(A'vl Vygs(To vr) + AJ [14+ilz + A 4f(u41ll + ATA'lA'ul - b)-
(yi+1 - y1)
Suppose min (Az) Smin have
|||u+1lz - (x0)21]
1
|lye+1 vell + Tngllse v3(o))) pio (A)]l (A)llA'ub bll Fmax (A))(u))(
8min
'/y
1
+ Tmax
+ (.g0a)
11 - -v6ll + T. A'y/5 (zo, m(+1) bll
8min
fly
Pax (A)llA'v( -bll
Thus.
[wr+1 - 2ug((2 (2oO)) Sa S0uynoll/44 sell + AuazollA'yfs (vo: u4+1) bll + outzoll A'y6/ b|l
where Juyz0
1+omax
Lyga
Tu2z0
Lagyy
Oula0
Aramax (A)
My frim
Smin
Emin
8min
Similar conditions and conclusions also hold for |l1441 2¹ (xo)).-
E Proofs of Theorem 5.2 and Corollary 5.3
In this section, we provide proofs for Theorem and Corollary 5.3 We first introduce the additional notations and lemmas that will be used in this section.
38

---

Notations
K(r,v/ ./'//.//,0 u, (5 2) + u (Ba + A'y' b) v² (Bx. + A'z' - b)
+
P1 |Br + +'yy -bl? 12 2
2 -11 Br + A'z' - bbl
L la + 2 + pp p2) max (o max (A'); o (B), Fmax B maxx (a)))A)))
My min Ugg - 11 p1o max (A), P1
12 M. min P20 max (A),
2
2 (x) min 96(2z (5(z))) V)
yE)(#)
x* x'(x) argmin ((x, z) =<)(w)
2z(x) argmax min g5(2, + u (Br + Ay - b) wER4 vE)(z)
v² v'(x) = argmax min g(z,y) + u TT (Bx + Az - b) "ERt xE)(x)
1/2 (z,, u) argmin Kxx, u,,) y'EP,
21, = argmax K K(x, ,2,,,,) ='P, [V3 T),, ,0 u) T = (x, (x, ,8 (x, v) (x,
d(r,,', u, v) = K K(t, 1/5 (x, x),
((0, u) = 05(2, (z)) (I, v. (Bx + (x, - P2 Br + (z, - -b12
V, K (z 1/. 24. ue vt) 29(x2, v1) d(z,. 2/, u1, vz)
Lemma 5.1
When the IJCQ condition (Definition 4.3) holds for y" (x) and vž (1)), the optimal Lagrangian multipliers of yn (x) and y (z) are unique and we have
uz(x) argmax min g6(x, y) + TT h(,,)) argmax min K(r, 3/ 2/, u, v). ueR4 VEV(Z)
wERth s'EP,
0" (x) argmax min g(x,2) + w =x max K( u, veR, =eM(a)
vER%, e'EP,
Proof. Suppose
U1 = argmax min g(x, ()) vER, =EY(2)
argmax min K(x, y/ 2 u, v. a yeP,
The KKT conditions for are
V =) + A v==0 =0
Br +z 6
1 20
8. T(x (x) - =0
39

---

The KKT conditions for 12 are
V (=)(,==(()) + A 1 + P2 + (x)" -b) =
Bæ + (x) - -=0
8 < 0
U1 E (3)
Note that these two KKT conditions are equivalent. Moreover, since the LICQ condition (Defi- nition 4.3) holds for 2z),,, we have 01 u2- Similar conditions and conclusions also hold for (z).
Lemma F.I. K (( =', v) is sy-styyngly w.r. y', Pt--Stoongly concave w.r.t. 2', and Lmoohhoth x. 12
Proof. According to Lemma A.4 we know that K (4g-Strongly concave w.r.t. z'. Moreover
(z g/ 2/, 2, is My -trongly convex w.r.t. y/
K v 2 v) =V
(u- o) P. (Br + A'y -b) b)
P2B "BBB(Bx+o A'2' b)
(Bx
V V (x, (2. ,/', u, =V v0s(s,, + (A''' -b)
V=K(x,y'' u) (,, - - (A''' -
Thus, K K(x, 1/ F u, 0) is Lm-shhoth w.r.t. ,,
Lemma E.2.
||ue+1 - uz (dxe)) S Juy Juyllb641 - v/6ll + oul Br, + A'yl - bll + ow2 BBg + A'ul5 (Ite Us+1) bl
||ee+1 - v'(x))]l S uzz |:441 - z/yl + oul [Br, + A'z - bll + o,22 Be, A'z" (Kz; Us+1) bll
where Ouy [mj tl a_tu,1 aanin (A)
1 + oalg.)). oul Pt. 0a2 5xlz1 (Aj
Ouz mmiald) 1 0z6g,1).
Tol = P2, 0+2
Proof.
By the optimality condition y (xt), we have
V (r (xx)) + A (up(st) = 0.
The update rule of yr:
Mt+1
V ugo (998(11111)) A u441 + AT (Bxr Aye - ozt)
ny
Putting together, have
A T (xx)) uz+1)
M/+1 - Yt
+ V Vvo6(xr.v))
V Vuos(2n, (E())) + PIA + Ay: - b an)
F
Since has full row rank, we have
ug(xz)) u1+1 =(AAT)-1A
Me+1 V1 + Vyge(Fe.31)) - V (1
+ +p + AAy: at).
and
||ue+1 (xx)ll
1
1l - well +
1l vē (x+))) + Pi Pill + Aye - b ael
Omin (A)m
Jmin (A)
40

---

Moreover,
11 - vo (z))l S11 - y ( u4+1)l + 11v3 - 2 ( u(+1)l
-0a11344 - sill + σ. Brg + A'yl3 (zee; Us+1) - bl
where the last equality is due to Lemma D.2
Thus,
||ue+ uz (zre)l S Guyllb6+1 V/ll + Jui BBr + A'y. bl1 + 0 Brg A'y' (4+1) - b1
where Guy = amin(A) 22 mo
1
+ Dalg,)), Jul = 02, 022
0x/s,1 mmn (A)
Similarly, we have
||t+1 - 00 (x+)1l S 0 - 2/1l + rol Br, + A'2 - bll + 0 Bx, + A'z"" (x4,) -bl
where duz (A) (/e 0glg,1). 0vl P2. 002 mii)
Lemma E.3.
(x1) - 2'(x2)) S oz 11 - T2l
(21) - (x2) و [x] 22
[1'((1) (x1) -22(2)) s 0 |2 T2
[14z(z1) -3((22) S owlll - x22
where db max (A)o + Jez yyb Tmax + yzz Jvb (d) Jub "min(A)
Lig
Proof. Here, we introduce an additional notation: (2; w) = argmin g(x, 2) + 2 | A'z' - bll?, where ((w) fz's E pyl Bu A'z' - b= 0}. We can notice that 2¹" (I; = (z). According to Lemma A.3 we have 1z (x1;)))) (2);; S Azl Ar2l. Moreover, we have (11;))))) azz)l 51 - x2||. Moreover,
(222422) || S Tzn | x2ll. Thus, | (x1) ="*(x2)l S [maxx Fmax(A)p (A)o=
v0 =x=)) + ( = 0 v0g(x,= (x²2) + A 'n (xz) = O
Thus,
(x1) 0² (x2)) <
||:01 x2 mmiu (A)
Similarly, we have (2)" - 3/5² (22)) S [o (A)o,, + +z - x2ll and [|uz(z)) 23(x22) 5
owin (A) 1|21 22ll
E.1 Potential function
In this subsection, we will prove the following descent lemma for V..
Lemma E.4. When 8 < (2/(2)
0
I
P1
<
Pg 16يق
ooa (A)
0
<
P2 I o (A)'
Mg
1/(4Lk),
n=
=
2/(LK +
4La),
n
( /6400 ( / na/ (240((
+
da
2 [. /// (240
0²2
)2)) 2/ + 4La + 8Lg), 1/1900m,,
o uy
1
L3
}.
Th
max // 2g12//22566 (2560 max (A)). To = 7 (2560 ( (A)), we have
1
1
V4- V4+1
2
||-,-|
- x0e12 2 +
116441 - 2/112 +
|| - z/,1?
41p
167y
81]=
+
Thu
|Bx + AA1//" (Ie, ue+1) -b122 + n7
BB + A'z' (Iz, Uz+1) - b112
4
2
+
17u
Br + A'v/ - b112 + ne | + A'2/ b112 + ns
[
(42)
4
4
41

---

Thus,
T-1 1
4 T/
Vos(Ia)) 2
(Vo
min Vi)
(43)
Proof. First, for function d, we have
d(z,, z/, Ux41, Ut+1) d( 2/1 uz, vt)
= (m 5/ (Ie, ue+1), 2/, u1+1, u141)) K (2t, 98 (Te, ue), 2/. ue u2)
2 KK(x y8 (Ie, ue+1), 2/, u++1, 1141) K (2t, y8 (Iz, uet1), 2/4 Ue, Ut)
2 Moll Bar + 2 b112 + 7/ Brx + A A'yl (2t, uo+1) - b) (Ber + A 1/ b)
Note that
V=d(2,2', u) = =V V006( 13 u), B" (u v) + Pı (Br + A' (a, u) b)
p2B (Br + A'z' bb)
Vedda,z',u, Vag(z, 2) - A V A2 (Bz + A'z' -6] + (Bx + A'z' bb)
Thus, according to Lemma D.2 know that V v,d(z, z' u, v) is (LK Lg yn continuuus w.r.t.
x, x' and v'd(a,,',,, v) is Lx-continuous w.r.t. x, z'. Define La = max + Lxx Lx) We have
d(zx+1, 2/4 1411 u++1) d(xt, 2/. M441, 1)+1)
2 (V, K ( u/5" (Iz, ue+1)) 1), 2/6, u441 Ut41), Te+1 xz) + <V 35 (2t, ue+1), 2/1 uet1, 0e41); 2/41 - =1)
La (1 - x1l1? + 11 - 2
2
2 (V (Iee v/6 (Ie, 1o+1), th ue+1 1141), Fc41 xz) + -1 =2/11
1
7
La
2 (1 -x,l + || - 2
Then, for function q. we have
(xx, v2) ((12,
2 K (x1, u/ (xt), 2"d (xz, u4,
ue 02) - K K(x, 1/ (xt), (x1, Ut+1). ue, Uet1)
> K (or, u8 (zt), 2" (oe, Ve+1), Uz, vz) - K (Iz, 1/5 (xz), 2n (x,, Ut+1) 1), ths v2+1)
2nd (Ber + A'z' (It, U141) - (Bxr A' - b)
Note that
Vag(a, v) = 1ols yg (x), 2" (s, u)) + B (u}(2) v) + p1 BT BBx + (x) b)
B2 (Bx + Alz" (Ir, v) b)
Thus, according Lemma smooth. We have
D.2 and E.3 g(:, v) is Lg (Lx LKosz + LK + maxx ( ())
q(Ee, v141) (x ve+1)
Ly (11:2++1 - -xel(3)
2 Z(V,K(It 18 (x+); (In, ve+1), (x.)) - x141)
2
Finally, for function K, we have
K K wos z/, ue, ve) K (Ix, V/s 2/1 u41,, Ue+1) -mpu "/llBBr A'y. b112 + 1
Bar + A'z! - -b1l.
and
K (x1, v/. 2/, u1-1. v141)
K
(I
V44
2/+1 Ue+1, 2/+1)
1
1
1
|1te+1 22 -
-11644 2/112
_
1 21(1?
1/2
1/1
1/=
LK
(11æ0+1
x2l12 + -111441 - 26l1 + || - =611?)
2
42

---

Thus, for Ve, we have
Vi Ve+
(Ir, v/ (It, ue+1) 1,, 4/ Pe41,, - zz) + 1
1 -2/112
17=
+ (Brr + A'ul6 (1te u++1) b) [ (Bar + A'yi - b) 1/o Bare + A' bll
La (1Ie+)1 - =xl1² + |1 - 2(11 2 ,. (x,, 3/5 (2+), 2" (202, Uo+1) ). ui" 0441,,0 - x(+1)
2
+ 2n (Bx, + AA'z' Uc+1) b) (Bx; + A'z - b) [1[(1=2+11 1 1xel3)
+ 47
| - -2el1²= 1 + 4fly
11/4+1 - 1/ll2 - 47/
| - 2/11² ")
|B + Alyl b11²
4
+ Th
|Br, + A'z - -b1
LK (1|-0+1 - 22e12 + 11 - s/1l2 + |1 - 2/11²)
4
8
2 - V K (Iz; 1/8 (Te, U1+1 1), =/1 uc+1: Ut+1) - V K (xz, y/5 (z+), /²' (21, ve+1), u² (Ire); Ut+ ||||=|||1111 - xell
+
Na
7u
|xx + A'yl 6112 + 7u
Bxx + A'yl (ot, U(+1) - 6112 7/1
1| 1/2 A'y/6 (Iz, u(+1)ll
2 4
2
2
+
+ T7
9/ |Bx + A' b112 + no Brx + A'z (xz,, 22-1) - b112 - 7u A' - A'z v++1)1?
4
Th
V.K
VKK(I,, 10 (x1), ( U4 1)-1), u² (Iz)) (441) V K (Iz, Ver 2/1 1141, U1+1)l2
2
+
110, - rt+1l 1| +
Te
V (xi,, 33 (xt), 22 (Fer vr41), u" (2xe), 1(+1)11
27/
2
1
Lk
Lad
Lg
| - 2211?
417
2
1
1
LK
La
+
|| 2413
17
41T
8
2
1
T.K
+
|1
1/l.?
417y
and
Ve Ve+1
1
2 47, | - 22e12-300 11u6 (11, 1/5 (xxa)1 3 T.xl1"" (xz, Ue41) =2112
L2 1/u441 -u"(x:)11
+ Nu
[|| + +A'vi - -b12 + The 2
Brr + A' A'y// (Ie, uo+1) 1) bb112 2 o max (A)
11 (Ie, ue+1) 1/11
4
2
+ n1
[|Irr: + A'z' -b12 no BI,, A'z'" (3 (x1, ve+1) b112 noo max A))lz"((12 (I2, -//112
4
2
11// (xx) (re, 11+1)11 111 21 Lx 1//// (2e, M441) s/ll2 2 21 Lx [1411 u 2xx2))1
1 ||,r xz41 112
L. 112 (2x, 1)+1) =1122 + 2n
Te || K.K( (I,, 1/5 (z,), x² (wx), , 2 (2x), v² (x.)))1 Th 11== - 2'((xe, 1111)11
+
4
T/
1 11+t11 2² (2x)11
1
Lx.
La
+
Tzg ||01+1 - =xel?
41/w
2
3
T.
Laa
+
|| - 2/112
4m²=
8
2
1
LK
+
11
-/112..
4f1y
43

---

and
Ve
1(+1
1
1
1
LK
Ld
Lg)
|01+1 xzl1
27/
41Te
41/2
8
2
1
LK
5onelii + nu nuo o max)
|1//+1
1/112²
1166 (Ie, u441) 16112
41y
2
3
LK
Ld
|| 2/112 - (5m Ii no nox (A)) || (2te, (30, Uc+1) 2/112
41T=
2
+
Th
Bx + A'yl - b||2 + The
|Be + A' 1 (Ie, uc+1) - b11² - 1:, xx 11 (Ie, u+11) 1/8 (xx))l
4
2
+
1h
|Brt + A' - b12 + no BB,, A'z' (#t,, u(+1) b112 -/2 1 2/" (322; 11-1) - (sx)2
+
V , (Ix, 3/5 (z+), 2² (2z)) 20 (2+), 0" (2+) -5 ||uc+1 u² (xx)11 nhe Li |1++1 v² (xx))1
4
Lx
La
Tng) ||:241 1iel?
27
8
2
1
LK
20 I. + max 15n ox |16/+1 - 1611?
Afly
8
12
3
L.K
L.d
201 T.2x + 4m max
max (A) 37 Li 0
+
1| - =111
411s
2
+ 2
Uu
n1
15 I2 022))
||ere + A'yl (0r,, u++1) B112
+
(1h
a 11s 1.2x
31 1:3x
|B + A'= (r+, ut+1) b/12
+ Nu
15 12x0000 saa) ||Brrt + A'1/1 b11 + (%h
Me
31/ 31 1xx | + A'zi A'z -b12+ + Th
4 | [))s))))
where the last equality is due to Lemma D.2 (z)(2))
E.2 and V KK,, (xx),, u (z)) (x))) =
Proof of Theorem 5.2
When 8 S /g/((2 0 S S K=- 0 05 P2 S Pe (1), fly = 1/(4Lk), n3 = 2/LLK
amn 4Ld), The = min(Take /640/)66)))))))))))))))))))))))) / Th. (240(0 + t + L ); nu/ (240(22
2²2 + L3) 2/L + 4La + 8L,), 1/9900/ 02 uy 1/(19/00m L3x "z))
/ (2560 max (A)), no 7 22560 max
max (A)), according to 43)
we have
T-1 Vos(I:)1
4 Tn
Σ
(Vo min Vi)
(44)
Note that
1 K(xi. vh. 2/ ue, vi) + +2((xe, v1) d(Ir, 2/, ue, vx)
V1 4
22q(Ie, vi) d(z 2 un v²) 2 7 { vx) 2 {0)()z)
5
5
2
5
58
f.0
4
4
8pg
Therefore, when 8 = O()), with T = we have 1. E [T]. such that [ = |l Vos( Se e.
44

---

Moreover, if we have 20: Mo. 20, No. such that
y/o vI (20) _ 0())
Uno ug (zo)) - O())
= =(xo)] < (()))
10 v (xx))] - O(6)
Then, set 0g = h( vo), 30 = f(200 zo). we can easily prove that
| + A'y' (zo: uo) bll 1 |B + A v/5 (zo, (xo)) bll + max (aax(A))yyullu - uz(x))] - 0
[2z + A'y bl| S max (A') 1166 (xo) _ (())
and similarly,
|| BB A'z'* (zo, 0b) - bll - 0(6)
|B A' bll - 0(6).
Then, we have
Vo-
[6 yo) + (9( 90) - g(zo, 20)) + u/ (Bry + A' b) - 11) (Bro + A'2/ b)
4
+
P1 |Bxx0 + A'y6 bll2
02
|Bx + A' b||
2
2
+ 2(6 ub (Io)) (g(ano: v1 (In)) g( x (x00, mn)) vo (Bro A'= vo) b)
P2 || A'2'" uo) b1| - (2 1/3 (Io, un)) + (g( v (zo, uo)) g( 20))
2
+ up (Bxo + +A'y/ (zo, uo) - b) v/ (Bxo + A' - b)
+ P1 ||Baro A'yl" (zo, uo) - b112 P2 BBr + A'z - b|]l]
2
+ (((1)),,,((1)) - y" (xo) || + 1111 (2o) - y (200) || + 11 ( uo) - y/ (xxoll)
+ ((1)C,((1 - woll + 18 (2)) =" (xx, uo)1l + [1v 20) zoll)
+ O(1 Bro + 2/ - bl + B + A'26 - b11 + |B0 + A'yó bll + BBo + A'y6 - B12
+ |10 + +A'='"zo, vo) - bll + Bro + A'z'"(zo vo) -112
+ || | + =A'u// (Fo, un) bll + Bæo + A' A (zo, ua) b11
(Fo)
S 4
((5)
where G = max(g(2o. yo), g 20), g(00, (zo), g( 2x0, vo)), g(r. y ( uo)), C = {v e Rdy (g( y) < G). C. = suppee Vag( v). Since g( y) is strongly convex w.r.t its sub-level set compact and convex. Moreover, since g Lipschitz smooth, its gradient this compact set C is upper bounded by an O(1) constant Cg.
We notice that
56 (2r) Th + + O(c)
Vo min V <
4
and
4
E
Σ
[os(( S
Tnn (Vo min V/) =0
T8
T
Therefore, we can find an e-stationary point of (x(x) with a complexity of ((E
Proof of Corollary 5.3
When h(x w) = Bx + Ay - b, A full row rank and under Assumption 3.1 3.2 3.3 and ò O(e) < (21 if we apply PGD for maX min min, g y) + (Br, + A b) with
fixed 2g. then according to Theorem 6 in [66). we can find 0, 2 such that
||nn " (zx) || < 6
| 2 (xx) < 5
45

---

with complexity of O(log(E-1) )).
Set yo 2g ł, No vp ú, o0 h( vo), fo h(s0, =0) We have
1130 y (zo) < O(6)
Bzo A A'y (Zo, uo) - bl - O(6)
| + A A'1 bll s (()))
1 u (2)))] < 0(6)
|Brg + A (Fo. Uo) bll _ 0(6)
B20 + A' bl - 0(6)
with zo. 26- z/g: uo, uo as initial points and apply Algorithm | according to Theorem 5.2
we can find
an e-stationary point of 4, with a complexity of O(e
Thus, the total complexity is O(E -3-3, log(E-)) O)e
F Detailed Experimental Settings and Additional Experiments
We adapt and modify the code from 16]. The experiments on the toy example and hyperparameter
optimization for SVM are conducted
AMD EPYC 9554 64-Core Processor. The experiments on transportation network design are conducted on an Intel(R) Xeon(R) Platinum 8375C CPU. For
the toy example, we set the hyperparameters for our algorithm as ó 0.1, Tl2 Tly 7)2 Thu
We = 0.01, P1 P2
F1 Hyperparameter optimization in SVM
Support Vector Machines (SVMs) construct a machine learning model by identifying the best possible hyperplane that maximizes the separation margin between data points from different classes. In hard-margin SVM, misclassification is allowed, ensuring that all samples are correctly classified. Conversely, soft-margin SVMs allow certain samples to be misclassified to accommodate cases where perfect separation is not feasible. To achieve this, slack variables & are introduced to quantify classification violations for each sample.
We consider the same problem formulation as in 16 which is
min
CD ;,) =
Σ
exp (1 Lval " + b*)) + ||cl2
w", b², =
arg min
2 |!1i1/
w.b.g
s.t. l (2,, (
+ b)
2 - Ei, Vi (1, ... |ull
& S C, Vi (1..... (Dul).
where Dr A {Z la, [Pul is the training dataset, D A { beat ) Dual is the validation dataset, with Er,á (2vat.) being the features of sample and lir (Ivat.) being its corresponding labels. The hyperparameter o is introduced to bound the soft margin violation & Note that the LL problem equivalent
w", b' = arg min 1
|1
b.b 2
(r, w +
Ci Vi (1,..., [rr
Then upper level variables c, and the lower level variables are w. b. Thus, have coupled linear constraint for the lower level problem.
We compared our algorithm SFLCB with GAM 46 LV-HBA 50 BLOCC 16, and BiC-GAFFA 44 on the diabetes dataset. For GAM, we follow the same implementation approach and hyper- parameters [16), setting 0.05, 0.005 and using different formulation as introduced
46

---

in 46]. For BLOCC and SFLCB, we set the LL objective as 2| 2 + bb, where = 0.01 serves as a regularization term to make the LL problem strongly convex w.r.t w, For LV-HBA we set
0.01, = 0.1, 72 = 0.1, 0.001. For BLOOCC, we set = 12, 9) 0.01, 20, y, = 20, 1/1 = 0.001. 1/ 0.00001, = 0.0001, 72F = 0.0001.
BiC-GAFFA, we set 0.001, Co 10. R 10. For our algorithm SFLCB, we set 6 0.010 Te = FBy = 7/s 7h = 17 0.001, P1 = P2 = 0.01. The hyperparameters of LV-HBA, BLOCC are the same as those used in []6] and the hyperparameters of BiC-GAFFA are the same as those used their original paper [49]. The experiments are conducted across 10 different random train-validation-ees splits, and the average results along with standard deviation are reported in Figure
0.3, 71 10 = 0.01, 0.01, 00001,
F.2 Transportation network design
We consider the same setting in [6]. In this setting, that connects a set of stations 5. Passengers then decide whether to use this network based on their rational decisions (lower level). The objective is maximize the operator's benefit (upper level).
the operator design network
The operator can select a set of potential links A C S x S, and for each link (i,j) E A, determine its capacity Tıj. A link constructed if zij > 0: a larger Tij attracts more travelers, generating more revenue but incurring higher construction costs Cij. Passenger demand is defined over a set of origin-destination pairs K. C S S. For each (o, d) E K,, there is known traffic demand Wod and existing travel times tod. We assume single existing network. The fraction of passengers choosing the new network for each (o, d) pair is denoted by Yod. and Yod represents the proportion using link (i,j).
We summarize the notation as follows. We keep the notation the same in [16
Tzj E R4, the capacity of the new network for the link (i.j) E A.
yod E [0, 1], the proportion of passengers from (o, d) E K. choosing the new network for their travel.
Viy [0, 1]. the proportion of passengers from (o, d) E K. choosing the new network and use the link (i, A
x =
are the upper-level variables to optimized.
[ represents the domain æf
= fvdd {uej'
od
(vci)ne are the lower-level variables to optimized
y [e, 1
K3 [e, e]| where is small positive number, represents the
domain of y.
oo the total estimated demand for (o, E K.
od the revenue obtained by the operator from passenger in (o, d) K.
Cij. the construction cost per passenger for link (i..) E A.
Lg,, the travel time for link (i,j) A.
ood travel time the existing network for passengers in (o, d) E K.
0, the coefficient associated with the travel time for passengers.
With these notions, we can introduce the bilevel formulations of this problem. At the upper level, the network operator seeks maximize the overall profit by attracting more passengers while minimizing construction costs; thus, its objective is
min fzz (x)) = xex
Σ
m od od (x)
Σ
(45)
Y(o.dEER
v(d)EA
profit
cost
47

---

where gode(a (x) are optimal lower-level passenger flows. For the lower-level, the objective is defined finding the flow variables that maximize passenger utility and minimize flow entropy cost.
min g(x, vEy
Σ
w witggii
wo (1 spud)
(46)
(o.d)EK (KJ)EA
(o,
passengers utility
way (l0((1
1)
Σ (o,d)EK
w y yod) 1)
(o,d)E
flow eutropy cost yod
i o you
S.t.
Σ
od Vij
od Vjs
ifi d otherwise
xxx
VilliJ)EA
VilGADEA
(47)
w
od pd Vij
S Fzg
v(i.)) EA
(48)
v(o,))KK
where (47) are the flow-conservation constraints and 48 are the capacity constraints.
We consider the same nodes and nodes settings as in and use the same lower level feasibility criteria. The hyperparameter settings used Figure are listed below. For the 3 nodes setting, set the hyperparameters of our method SFLCB as: å = 0.1, P1 P2 = 1000, The Fly = 77 1/ = Th 3e and T 30000. For the 9 nodes setting, we the hyperparameters of method SFLCB as: 5 = 0.25, Pr P2 = 50, = 1/= = 7u, = T/ = 3e 5, and T = 300000. For
BLOCC, we used the same hyperparameters as those used 16
48


Reviews:
[{"review_id": "KiFNREudMR", "reviewer": "Reviewer_gHwN", "summary": "This paper studies bilevel optimization problems where the lower-level objective is strongly convex and subject to general linear constraints, including both inequalities and equalities that may couple with upper-level variables. The authors first apply a penalty relaxation and derive sufficient conditions under which the relaxed problem remains approximately equivalent to the original formulation. They then introduce a surrogate strongly convex loss function for the relaxed (but still constrained) problem. Finally, they propose an algorithm, SFLCB, to optimize the surrogate loss, analyze its convergence, and relate the resulting solution back to an approximate stationary point of the penalized problem.", "questions": "See Weaknesses", "limitations": "Overall, this paper feels borderline, but it addresses a relevant problem for the bilevel optimization community. Sharpening the emphasis on novelty and highlighting more surprising or non-trivial insights would help improve readability.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n-\tThe writing is generally clear and the contribution is positioned well in the context of existing work.\n\n-\tThe paper builds on prior landscape analysis results and offers a nontrivial extension.\n\n-\tConvergence guarantees are provided for the proposed algorithm.\n\n\n**Weaknesses**\n\n-\tThe landscape analysis appears more general than previous results, but it primarily builds on [21], and the novelty seems limited.\n\n-\tThe transition from Section 4 to Section 5 feels abrupt. The restriction to linear constraints in the algorithmic part needs more justification. \n\n-\tThe sample complexity discussion is somewhat unclear. In particular:\n\n1)\tIf $\\delta = O(\\epsilon)$, then we are already close to a stationary point — calling this a “good initialization” seems misleading.\n\n2)\tIn many settings, initialization quality does not affect the final convergence rate. Where does the difference come from?\n\n-\tThe claimed $\\log(1/\\epsilon)$ improvement over [16] needs clarification. Is this a fundamental improvement, or could a sharper analysis of [16] yield the same rate?", "was_revised": true, "final_justification": "Still somewhat borderline, but a technically correct paper.", "rebuttal": "We thank the reviewer for the valuable comments. However, we believe that the reviewer has some misunderstandings about the initialization and the sample complexity discussed in our paper. Actually, the $O(\\epsilon^{-3})$ convergence rate in our paper does _not_ depend on the choice of initial point $x_0$. One can randomly choose $x_0\\in X$ and set $\\delta=\\Theta(\\epsilon)$ (Note that setting some constants to be $O(\\epsilon)$ (or $O(\\epsilon^{-1})$) is commonly used in related works [16, 20]). Then, according to Corollary 5.3 and Corollary 5.5, one can easily find $y'_0, z'_0, u_0, v_0$ that satisfy line 259-260 (or line 273-274) with a complexity of $O(\\log(1/\\epsilon))$ (or $O(\\epsilon^{-2})$). Then with these $\\delta, x\\_0, y'_0, z'_0, u_0, v_0$, our SFLCB algorithm can converge with a complexity of $O(\\epsilon^{-3})$. Therefore, with random initial point $x_0$, the overall complexity is $O(\\epsilon^{-3}+\\log(1/\\epsilon))=O(\\epsilon^{-3})$ (or $O(\\epsilon^{-3}+\\epsilon^{-2})=O(\\epsilon^{-3})$). We hope these explanations clarify these misunderstandings. Below, we provide more detailed responses.\n\n>The landscape analysis appears more general than previous results, but it primarily builds on [21], and the novelty seems limited.\n\nThe analysis in [21] only considers lower-level constraints  $y\\in Y$ that are independent of $x$, whereas our work analyzes _coupled constraints_ of the form $y\\in Y(x)=$ { $y\\in R^{d_y} | h(x,y)\\leq 0 $ }. Handling such coupled constraints requires estimating the Lagrangian multipliers in the implicit gradient formula, which makes our analysis more involved compared to [21]. Notably, the Future Directions section of [21] also emphasizes that analyzing lower-level $x$-dependent constraints is a valuable direction for future research, highlighting the value of our work. Therefore, we believe our work offers both novelty and significance.\n\n>The transition from Section 4 to Section 5 feels abrupt. The restriction to linear constraints in the algorithmic part needs more justification.\n\nThe focus of our paper is on linearly constrained bilevel optimization, and therefore Section 5 primarily analyzes the linear constraints. It is worth noting that linear constraints encompass a broad range of applications, including distributed optimization [47, 18], adversarial training [52, 18], and hyperparameter optimization for constrained learning tasks such as hyperparameter tuning in SVMs. Moreover, several related works also concentrate on analyzing the linear constraints [41, 18, 20]. We appreciate your advice, and will add more justifications in the revised paper to make the transition smoother.\n\n>If $\\delta=O(\\epsilon)$, then we are already close to a stationary point — calling this a “good initialization” seems misleading.\n\nSetting $\\delta=\\Theta(\\epsilon)$ does not suggest that we are close to a stationary point. Setting some constants to be $O(\\epsilon)$ (or $O(\\epsilon^{-1})$) is commonly used in related works [16, 20]. In our paper, our goal is to find an $\\epsilon$ stationary point $\\hat x$ satisfies $||\\Phi_\\delta(\\hat x)||\\leq \\epsilon$. However, initial $x_0\\in X$ can be randomly selected, and there is no guarantee that it will be close to a stationary point. In this paper, we say $y'_0, z'_0, u_0, v_0$ are \"good initializations\" if they satisfy line 259-260 (or line 273-274). Actually, we prove that for any fixed $\\delta=\\Theta(\\epsilon)$ and $x_0\\in X$, these \"good initializations\" are not difficult to achieve. In Corollary 5.3, we prove that for any initial point $x_0$, for $Bx + Ay-b$ constraints and $A$ is full row rank, we can find \"good initializations\" with a complexity of $O(\\log(1/\\epsilon))$ and in Corollary 5.5, we prove that for any initial point $x_0$, for $Ay-b$ constraints, we can find \"good initializations\" with a complexity of $O(\\epsilon^{-2})$. Thus, the overall complexity is $O(\\epsilon^{-3}+\\log(1/\\epsilon))=O(\\epsilon^{-3})$ (or $O(\\epsilon^{-3}+\\epsilon^{-2})=O(\\epsilon^{-3})$).\n\n>In many settings, initialization quality does not affect the final convergence rate. Where does the difference come from?\n\nActually, the initial point $x_0$ does not affect the final convergence rate in our algorithm. Please refer to our general response before. We further add that the main reason why $y'\\_0$, $z'\\_0$, $u\\_0$, $v\\_0$ affect the convergence rate is that our theoretical analysis establishes the following result:  \n$$\n\\frac{1}{T} \\sum_{t=0}^{T-1} || \\nabla \\phi_\\delta(x_t) ||^2 \\leq \\frac{4}{T \\eta_x} \\left( V_0 - \\min_t V_t \\right)\n$$  \n(line 959, 1069). Moreover, we prove that  \n$$\nV_t \\geq V_{\\min} \\geq \\frac{5\\delta \\Phi^*}{4} - \\frac{5\\delta^2 l^2_{f,0}}{8\\mu_g}\n$$  \n(line 960, 1070).  \n\nSince $\\delta = \\Theta(\\epsilon)$ and $\\phi_\\delta = \\delta \\Phi_\\delta$, an $\\epsilon^2$-stationary point of $\\phi_\\delta$ is correspondingly an $\\epsilon$-stationary point of $\\Phi_\\delta$. Therefore, we can find an $\\epsilon$-stationary point of $\\Phi_\\delta$ with a complexity of $O(\\epsilon^{-4})$. Note that $-V_t \\leq O(\\delta) = O(\\epsilon)$.  \n\nWe additionally prove that with good $y'\\_0$, $z'\\_0$, $u_0$, $v_0$ (satisfying line 259–260 or line 273–274), we have  \n$$\nV_0 \\leq \\frac{5\\delta \\Phi(x_0)}{4} + O(\\delta) = O(\\epsilon)\n$$  \n(line 963, 1074).  \n\nTherefore, with good $y'\\_0$, $z'\\_0$, $u_0$, $v_0$ (satisfying line 259–260 or line 273–274), SFLCB can find an $\\epsilon$-stationary point of $\\Phi_\\delta$ with a complexity of $O(\\epsilon^{-3})$.\n\n>The claimed $\\log(1/\\epsilon)$ improvement over [16] needs clarification. Is this a fundamental improvement, or could a sharper analysis of [16] yield the same rate?\n\nCompared with [16], the $\\log(1/\\epsilon)$ improvement achieved by our algorithm is a fundamental advancement. The additional $\\log(1/\\epsilon)$ complexity in [16] arises from their double-loop structure. Specifically, their inner loop involves solving a constrained strongly convex minimization problem, which inevitably incurs an extra $\\log(1/\\epsilon)$ complexity. In contrast, our algorithm adopts a single-loop structure, which theoretically avoids this additional overhead, leading to better convergence complexity. Moreover, single-loop algorithms are generally easier to implement in practice, and our experiments further demonstrate that our method empirically outperforms [16]. We believe that one of the main contributions of our paper compared to [16] is the improvement from a double-loop to a single-loop algorithm. In the field of minimax optimization -- a related area closely connected to bilevel optimization -- such improvements from double-loop to single-loop (Zhang 2020; Xu, 2023) are also commonly regarded as significant contributions.\n\n__Additional References__:\n\nZhang, Jiawei, et al. \"A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems.\" Advances in neural information processing systems (2020).\n\nXu, Zi, et al. \"A unified single-loop alternating gradient projection algorithm for nonconvex–concave and convex–nonconcave minimax problems.\" Mathematical Programming (2023)."}, {"review_id": "Oi1gY7brgU", "reviewer": "Reviewer_ME2c", "summary": "- This paper proposes a first-order method for bilevel optimization problems where the lower-level problem has a strongly convex objective function and linear constraints.\n- The authors first reformulate the bilevel optimization problem as a single-level problem. They provide non-asymptotic bounds on the differences in function values and gradients between the original hyper-objective function and the reformulated one.\n- They then construct a convex augmented Lagrangian function under linear constraints and design a Hessian-free first-order method based on this augmented Lagrangian.\n- The paper analyzes the convergence of the proposed algorithm, demonstrating an improved convergence rate compared to existing Hessian-free single-loop methods.", "questions": "- Regarding the second weakness I raised: Is the observed speedup directly attributable to the improved convergence rate? I am also interested in whether the convergence of the objective function value improves with the number of iterations.\n- Related to the first question, I am interested in the arithmetic computational cost per iteration of the proposed method. Is the arithmetic computational cost of the proposed method the same as that of existing single-loop methods?\n- The authors mention that prior work [49] requires projection onto $\\mathcal C$, which incurs high computational cost. However, in cases like this paper, where $h$ is a linear function of $x$ and $y$, projection is easily computable. Does the proposed method still offer a computational cost advantage over [49] even when $h$ is a linear function?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- Strengths\n\t- Bilevel optimization problems have diverse applications in the machine learning community, making the design of efficient solution methods for these problems highly significant.\n\t- In particular, existing single-loop methods could only discuss the asymptotic relationship between the reformulated problem and the original bilevel optimization problem. This work offers originality by providing a non-asymptotic analysis.\n\t- Furthermore, despite the limitation to linear constraints, the paper achieves an improved convergence rate, which makes it a valuable contribution to research on solution methods for bilevel optimization problems.\n- Weaknesses\n\t- The clarity of Section 4 could be improved. Section 4 discusses the reformulation in a general case where the constraint function $h$ is not necessarily limited to being linear. This section should state more explicitly that $h$ is not limited to a linear function.\n\t- Regarding the computational experiments: While it's true that the proposed method obtains higher quality solutions in less time compared to existing single-loop methods, it's unclear if this should be directly attributed to the improved convergence rate.", "was_revised": true, "final_justification": "The authors have sincerely addressed all of my concerns and questions. While I recommend they revise the manuscript to incorporate these points, I believe the paper is suitable for publication.", "rebuttal": "We thank the reviewer for the valuable comments. Please see our responses below.\n\n>The clarity of Section 4 could be improved. Section 4 discusses the reformulation in a general case where the constraint function  is not necessarily limited to being linear. This section should state more explicitly that  is not limited to a linear function.\n\nThanks for your advice. We will state these more explicitly in the revised paper.\n\n>Regarding the computational experiments: While it's true that the proposed method obtains higher quality solutions in less time compared to existing single-loop methods, it's unclear if this should be directly attributed to the improved convergence rate. Regarding the second weakness I raised: Is the observed speedup directly attributable to the improved convergence rate? I am also interested in whether the convergence of the objective function value improves with the number of iterations.\n\nIn transportation network design experiment, the observed speedup is attributable to the improved convergence rate and objective function value improves with the number of iterations. Actually, in the transportation network design problem, the UL utility is defined as the negative of the objective function value. Thus, a larger UL utility means a smaller objective function value. We provide the following results showing how the objective function value changes over time with BLOCC and SFLCB.\n\n3 Node:\n| Time (s) | 1    | 2    | 3    | 4    | 5    |\n|----------|------|------|------|------|------|\n| BLOCC    | 1.36 | 1.66 | 1.70 | 1.70 | 1.71 |\n| SFLCB    | 1.04 | 1.69 | 1.84 | 1.84 | 1.84 |\n\n9 Node:\n| Time (s) | 20     | 40     | 60     | 80     | 100    | 120   | 140   | 160   | 180   | 200   | 250   | 300   | 350   | 400   |\n|----------|--------|--------|--------|--------|--------|-------|-------|-------|-------|-------|-------|-------|-------|-------|\n| BLOCC    | -420.87| -89.73 | -23.66 | -4.62  | 1.72   | 6.25  | 6.59  | 8.55  | 8.93  | 9.14  | 9.53  | 9.15  | 9.52  | 9.54  |\n| SFLCB    | 2.57   | 12.09  | 15.30   | 18.03  | 19.95  | 20.52 | 20.92 | 21.18 | 21.19 | 21.20 | 21.06 | 20.79 | 20.67 | 20.40  |\n\nIn the 9-node setting, we set $\\delta=0.25$ in SFLCB for better comparison with BLOCC (since in our reformulation, $\\delta$ has a similar role as $1/\\gamma$ in BLOCC and $\\gamma=4$) and keep all other hyperparameters the same as those in our current paper. Note that the $\\delta$ here is different from the one used in our paper. Thus, the results of the 9-node setting are different from the current paper.\n\nWe can see that in both the 3-node and 9-node settings, SFLCB converges faster than BLOCC and achieves better UL utility (i.e., smaller objective function value). We will add performance figures in the revised paper to show how the objective function value changes over time and the number of iterations to better illustrate the practical efficiency of our method.\n\n>Related to the first question, I am interested in the arithmetic computational cost per iteration of the proposed method. Is the arithmetic computational cost of the proposed method the same as that of existing single-loop methods?\n\nYes, the arithmetic computational cost per iteration of our proposed method is at least the same as, if not better than, the existing single-loop methods. For example, let us adopt the same assumptions that were used in [16] which assumes the complexity of calculating a function is proportional to the dimension of the inputs. In this case, assume the complexity for $\\nabla_x f$, $\\nabla_x g$ are $O(d_x)$, and the complexity for $\\nabla_y f$, $\\nabla_x g$ are $O(d_y)$. Then, the arithmetic computational cost per iteration of our method is $O(d_xd_h+d_yd_h)$. The arithmetic computational cost per iteration of BiC-GAFFA [48] is also $O(d_xd_h+d_yd_h)$, which is the same as ours. As a second example, LV-HBA [49] requires projection onto $\\{h(x,y)=Bx+Ay-b\\leq 0\\}$ in each iteration. This projection problem is a Quadratic Programming (QP) problem with linear inequality constraints, which generally does not have a closed-form solution and common methods used to solve this problem, such as interior-point methods (Nesterov, 1994), require a complexity of $O(p(d_h, d_x, d_y)\\log(1/\\epsilon))$ to obtain an $\\epsilon$ accurate solution, where $p(\\cdot)$ is some polynomial. Thus, the computational cost per iteration of LV-HBA is $O(d_xd_h+d_yd_h +p(d_h, d_x, d_y)\\log(1/\\epsilon))$, which is larger than ours. As a third example, BLOCC [16] for linear constraints has a double-loop structure and its arithmetic computational cost per outer-loop iteration is $O((d_xd_h+d_yd_h)\\log(1/\\epsilon))$, which is also larger than ours.\n\n>The authors mention that prior work [49] requires projection onto $C$, which incurs high computational cost. However, in cases like this paper, where $h$ is a linear function of $x$ and $y$, projection is easily computable. Does the proposed method still offer a computational cost advantage over [49] even when $h$ is a linear function?\n\nYes, even when $h$ is a linear function, the projection to $\\{h(x,y)=Bx+Ay-b\\leq 0\\}$ is a Quadratic Programming (QP) problem with linear inequality constraints, which generally does not have a closed-form solution and commonly needs iterative methods to solve. Common methods used to solve this problem, such as interior-point methods (Nesterov, 1994), require a complexity of $O(p(d_h, d_x, d_y)\\log(1/\\epsilon))$ to obtain an $\\epsilon$ accurate solution, where $p(\\cdot)$ is some polynomial. Thus, our method still offer a computational cost advantage over [49]. \n\n__Additional References__:\n\nNesterov, Yurii, and Arkadii Nemirovskii. Interior-point polynomial algorithms in convex programming. Society for industrial and applied mathematics, 1994."}, {"review_id": "qZGwM6tGVQ", "reviewer": "Reviewer_Fppg", "summary": "This paper considers bilevel optimization problems where the inner problem is linearly constrained. The inner function is assumed to be strongly convex, and the outer function is smooth, possibly non-convex. Additionally, the inner constraint set depends on both the inner and outer variables. First, the authors provide some differentiability results about the hyperobjective. Then, they propose SFLCB, a single-loop fully first-order algorithm to solve the considered problem. This algorithm is based on the Lagrangian reformulation of the bilevel problem. The authors demonstrate non-asymptotic convergence of SFLCB towards a stationary point of the hyperobjective. Numerical experiments on a toy problem, hyperparameter selection for SVM, and transportation network design are provided.", "questions": "- **Q1**: How is SFLCB sensitive to the hyperparameters?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n- **S1**: To my knowledge, the proposed method is the first fully first-order algorithm that handles inner constraint set that depends on the outer variable $x$.\n\n- **S2**: The proposed algorithm is a single-loop algorithm, making it more practical than a two-loop method. This is an improvement upon prior work.\n\n- **S3**: SFLCB is theoretically grounded with non-asymptotic theoretical results.\n\n- **S4**: Numerical experiments show the practical interest of SFLCB.\n\n\n\n### Weaknesses\n\n- **W1**: There is a substantial number of typos, imprecisions and notational issues that have to be fixed. See the section Minor/Typos for details.\n\n- **W2**: I personally find the paper, and in particular Section 5 hard to read. In particular there are many notations, and readers can easily get lost. The introduction of $\\alpha$ and $\\beta$ in Section 5 should be motivated. Also, stating the SFLCB is an adaptation of gradient descent ascent on $K$ would be beneficial for a better understanding of the algorithm.\n\n- **W3**: Maybe I missed something but in the proof of Theorem 5.2, it is unclear to me how from the different inequalities the authors conclude that the complexity is in $\\mathcal{O}(\\epsilon^{-3})$. Could the author clarify this point?\n\n- **W4**: SFLCB comes with many hyperparameters (the five different step sizes and $\\delta$) which makes it less practical.\n\n\n\n### Minor/Typo\n- **Line 23**: \"upper level\" -> \"upper-level\"\n\n- **Line 24-25**: \"$\\mathcal{X} = \\mathbb{R}^{d_x}, \\mathcal{Y}(x) = \\{y \\in\\mathbb{R}^{d_y}\\,\\vert\\, h(x,y)\\leq 0\\}, h(x,y):\\mathbb{R}^{d_x}\\times\\mathbb{R}^{d_y}\\to\\mathbb{R}^{d_h}$\" -> Avoid sentences full of mathematical symbols without any accompanying text.\n\n- **Line 33-34**: \"However, these implicit gradient-based methods necessitate computing the Hessian matrix of the lower-level problem.\" -> This is inaccurate. Even though the implicit gradient involves a linear system with the Hessian matrix, this system can be solved by only using Hessian-vector products (for instance, with the CG algorithm [1, 2]), which do not require computing the full Hessian matrix [3, 4].\n\n- **Assumption 3.2 and 4.6, and Lines 966 and 1077**: \"Lipschitz smoothness\" -> \"Lipschitz continuous\"\n\n- **Assumption on $\\delta$**: The assumption $\\delta\\leq \\frac{\\mu_g}{2l_{f,1}}$ should be stated from the beginning of section 4. Otherwise, $y_\\delta$ and $\\Phi_\\delta$ are not necessarily well-defined. It is also missing in Theorem 4.1.\n\n- **Convex/concave about**: Avoid writing that a function is \"convex/concave/strongly convex *about* $y$\" as done lines 208, 209, 210, 212. Instead, write that a function is \"convex/concave/strongly convex *with respect to* $y$\".\n\n- **Lines 841-843**: There are several notational issues and typos:\n    - \"$\\nabla_x g(x, y^* (x)) = \\nabla_x g(x, y^* (x)) + \\nabla_x h(x,y^* (x))\\lambda^* (x)$\" -> This is unclear, but if I refer to Lemma 2 in [5], I assume that $\\nabla_x g(x, y^* (x))$ on the left-hand side refers to $\\nabla_x(x\\mapsto \\min_{y\\in\\mathcal{Y}(x)}g(x,y))$ and $\\nabla_x g(x, y^* (x))$  on the right-hand side refers to the gradient of $g$ with respect to its first argument at the point $(x, y^* (x))$. This has to be clarified in the notation. \n    - \"$\\nabla_x g_\\delta(x, y_\\delta^* (x)) = \\delta \\nabla_x f(x, y_\\delta(x)) + \\nabla_x g(x, y_\\delta^* (x)) + \\nabla_x h(x,y^* (x))\\lambda^* (x)$\" -> Merely the same remark. $\\nabla_x g_\\delta(x, y_\\delta^* (x))$ in reality denotes the gradient of $x\\mapsto \\delta f(x, y_\\delta^* (x)) + g(x, y_\\delta^* (x))$ which is unclear from the notation.\n    - \"$\\Phi(x) = ...$\" -> \"$\\Phi_\\delta(x) = ...$\"\n\n\n[1] [Pedregosa, F. *Hyperparameter optimization with approximate gradient.* ICML 2016.](https://arxiv.org/pdf/1602.02355)\n\n[2] [Grazzi, R., Franceschi, L., Pontil, M., and Salzo, S. *On the iteration complexity of hypergradient computation*. ICML 2020.](https://arxiv.org/pdf/2006.16218)\n\n[3] [Pearlmutter, B. A. *Fast exact multiplication by the hessian*. Neural computation, 1994](https://www.bcl.hamilton.ie/~barak/papers/nc-hessian.pdf)\n\n[4] [Dagréou, M., Ablin, P., Vaiter, S., and Moreau, T. *How to compute hessian-vector products?* ICLR Blogposts 2024.](https://iclr-blogposts.github.io/2024/blog/bench-hvp/)\n\n[5] [Jiang, L., Xiao, Q., Tenorio, V. M, Real-Rojas, F. Marques, A. and Chen, T. *A primal-dual-assisted penalty approach to bilevel optimization with coupled constraints*. arXiv:2406.10148 2024](https://arxiv.org/pdf/2406.10148)", "was_revised": true, "final_justification": "The paper makes a solid contribution to the resolution of linearly constrained bilevel optimization problems. However, as noticed by the other reviewers, the clarity of the writing can be improved. For this reason, I keep my score at 4.", "rebuttal": "We thank the reviewer for the valuable comments. Please see our responses below.\n\n>I personally find the paper, and in particular Section 5 hard to read. In particular there are many notations, and readers can easily get lost. The introduction of $\\alpha$ and $\\beta$ in Section 5 should be motivated. Also, stating the SFLCB is an adaptation of gradient descent ascent on $K$ would be beneficial for a better understanding of the algorithm.\n\nThanks for your advice. The introduction of $\\alpha$ and $\\beta$ is primarily for technical reasons. We reformulate the original constraints $h(x, y) \\leq 0$ and $h(x, z) \\leq 0$ as  $h(x, y) - \\alpha = 0, \\alpha \\leq 0; h(x, z) - \\beta = 0, \\beta \\leq 0$ respectively.  This reformulation allows us to handle the equality constraints $h(x, y) - \\alpha = 0$ and $h(x, z) - \\beta = 0$ using the augmented Lagrangian $K$, while the inequality constraints $\\alpha \\leq 0$ and $\\beta \\leq 0$ can be enforced via simple projection. We will add these explanations and state that the SFLCB is an adaptation of gradient descent ascent on $K$ in the revised paper to make the derivation and the motivations of SFLCB clearer.\n\n>Maybe I missed something but in the proof of Theorem 5.2, it is unclear to me how from the different inequalities the authors conclude that the complexity is in $O(\\epsilon^{-3})$. Could the author clarify this point?\n\nThanks for your question. Our theoretical analysis establishes the following result: $$\n\\frac{1}{T} \\sum_{t=0}^{T-1} || \\nabla \\phi_\\delta(x_t) ||^2 \\leq \\frac{4}{T \\eta_x} \\left( V_0 - \\min_t V_t \\right)\n$$  \n(line 959, 1069). Moreover, we prove that  \n$$\nV_t \\geq V_{\\min} \\geq \\frac{5\\delta \\Phi^*}{4} - \\frac{5\\delta^2 l^2_{f,0}}{8\\mu_g}\n$$  \n(line 960, 1070).  \n\nSince $\\delta = \\Theta(\\epsilon)$ and $\\phi_\\delta = \\delta \\Phi_\\delta$, an $\\epsilon^2$-stationary point of $\\phi_\\delta$ is correspondingly an $\\epsilon$-stationary point of $\\Phi_\\delta$. Therefore, we can find an $\\epsilon$-stationary point of $\\Phi_\\delta$ with a complexity of $O(\\epsilon^{-4})$. Note that $-V_t \\leq O(\\delta) = O(\\epsilon)$.  \n\nWe additionally prove that with good $y'\\_0$, $z'\\_0$, $u_0$, $v_0$ (satisfying line 259–260 or line 273–274), we have  \n$$\nV_0 \\leq \\frac{5\\delta \\Phi(x_0)}{4} + O(\\delta) = O(\\epsilon)\n$$  \n(line 963, 1074).  \n\nTherefore, with good $y'\\_0$, $z'\\_0$, $u_0$, $v_0$ (satisfying line 259–260 or line 273–274), SFLCB can find an $\\epsilon$-stationary point of $\\Phi_\\delta$ with a complexity of $O(\\epsilon^{-3})$. We will make the proof of Theorem 5.2 clearer in the revised paper. \n\n>SFLCB comes with many hyperparameters (the five different step sizes and $\\delta$) which makes it less practical. How is SFLCB sensitive to the hyperparameters?\n\nWe note that related works also typically require a similar number of hyperparameters. For example, BLOCC [16] similarly requires 5 step sizes for their $x$, $y_g$, $y_F$, $\\mu_g$, $\\mu_F$ and one hyperparameter $\\lambda$, which plays a similar role as $\\delta$ in our work. BiC-GAFFA [48] needs step sizes $\\alpha$, $\\eta$, proximal parameters $\\gamma_1, \\gamma_2$, and a penalty parameter $c_k$. LV-HBA [49] needs step sizes $\\alpha$, $\\beta$, $\\eta$, a proximal parameter $\\gamma$, and a penalty parameter $c_k$. In Appendix F.2.1, we conducted sensitivity experiments of $\\delta$ for transportation network design and found that our algorithm performs well over a wide range of $\\delta$ values (from 0.05 to 0.5). In our hyperparameter optimization experiments for SVM and transportation network design, we simply set all five step sizes ($\\eta_x$, $\\eta_y$, $\\eta_z$, $\\eta_u$, $\\eta_v$) to the same value and still observed reasonably good performance. These experimental results indicate that SFLCB is not particularly sensitive to the choice of hyperparameters, and that good performance can be achieved with simple tuning of $\\delta$ and the learning rate. We would like to add more sensitivity analysis experiments in the revised paper to better illustrate this point.\n\n>Minor/Typo: Line 23; Line 24-25; Assumption 3.2 and 4.6, and Lines 966 and 1077; Assumption on $\\delta$; Convex/concave about\n\nThanks for your advice. We will modify these typos in the revised paper.\n\n>Minor/Typo: Line 33-34: \"However, these implicit gradient-based methods necessitate computing the Hessian matrix of the lower-level problem.\" -> This is inaccurate. Even though the implicit gradient involves a linear system with the Hessian matrix, this system can be solved by only using Hessian-vector products (for instance, with the CG algorithm [1, 2]), which do not require computing the full Hessian matrix [3, 4].\n\nThanks for your advice. The phrase “these implicit gradient-based methods” in line 33 is intended to refer to the works mentioned in the previous sentence, namely [41, 18, 45, 44], which all use implicit gradient-based methods to handle constrained bilevel problems and involve computing the Hessian matrix. We will revise the paper to clarify this and avoid potential misunderstandings.\n\n>Minor/Typo: Lines 841-843: There are several notational issues and typos\n\nThanks for pointing out these issues and typos. Actually, we will define $\\psi(x) = g(x, y^{\\ast}(x))$ and $\\psi\\_\\delta(x) = g\\_\\delta(x, y^{\\ast}\\_\\delta(x))$.  \n\nLine 841 should be:  \n$$\n\\nabla_x \\psi(x) = \\nabla_x g(x, y^{\\ast}(x)) + \\nabla_x h(x, y^{\\ast}(x)) \\lambda^{\\ast}(x)\n$$  \n\nand  \n$$\n\\nabla_x \\psi\\_\\delta(x) = \\delta \\nabla_x f(x, y^{\\ast}\\_\\delta(x)) + \\nabla_x g(x, y^{\\ast}\\_\\delta(x)) + \\nabla_x h(x, y^{\\ast}\\_\\delta(x)) \\lambda^{\\ast}\\_\\delta(x)\n$$  \n\nLine 842 should be:  \n$$\n\\Phi\\_\\delta(x) = f(x, y^{\\ast}\\_\\delta(x)) + \\frac{1}{\\delta} \\left[ g(x, y^{\\ast}\\_\\delta(x)) - g(x, y^{\\ast}(x)) \\right]\n$$  \n\nWe will modify these in the revised paper."}, {"review_id": "rQAmHWyvCQ", "reviewer": "Reviewer_K5dx", "summary": "This paper studies a bilevel optimization (BLO) problem with a linear inequality constraint in the lower-level (LL) problem under the assumption of strong convexity in the LL variable. The goal is to improve the known convergence rate from $ O(\\epsilon^{-3} \\ln(\\epsilon^{-1}))$ to $O(\\epsilon^{-3})$. The authors propose a novel penalty-based reformulation by transforming the original BLO problem (0) to a value-function-based formulation (1), then introducing a slackness parameter to convert inequality constraints to equality constraints (2), applying a Lagrangian formulation (3), and finally converting the problem to an augmented Lagrangian form (4), which is jointly strongly convex in the LL variable and slack variable.\n\nThe paper theoretically establishes function value and gradient equivalence between (0) and (1), then claims equivalence through steps (1)–(4). Based on this, the authors propose SFLCB, a fully single-loop algorithm with an O(\\epsilon^{-3}) convergence guarantee. Experimental results on a toy problem, SVM parameter learning, and a transportation network demonstrate the method’s effectiveness.", "questions": "1.\tRelated Work Comparison:\nIn the table on page 3:\n\t•\t[16] handles general domain constraints Y, not just LL inequality constraints. Please acknowledge this distinction.\n\t•\tThe comparison in line 112 is arguably unfair since [16] requires projection due to its more general setting.\n\t•\tPlease also include [20] in the table and discuss its relevance. This will strengthen the positioning of the paper.\n\n2.\tEquivalence Gaps:\nThe paper uses gradient equivalence between the original BLO and the value-function-based penalty formulation (original BLO problem (0) to penalty reformulation (1) $\\phi_{\\delta}(x)$), but the later equivalences (e.g., step 2 to 4) a at optimal points. Can the authors clarify this distinction and avoid using “equivalence” loosely? This impacts the logical flow of the methodology.\n\t\n3.\tConnections to Prior Work:\nSeveral results appear to overlap with prior literature:\n\t•\tTheorem 4.1 vs. Theorem 1.1 in [21] and Theorem 1/2 in [38]\n\t•\tLemma 4.4 vs. Lemma 2 in [16]\n\t•\tLemma 4.7 vs. results in [21]\n\t•\tTheorem 4.9 vs. Theorem 1.1 in [21]\nPlease clarify the distinctions or cite appropriately instead of re-deriving them.\n\t\n4.\tTerminology and Notation:\n\t•\tReplace “convex about y” with “convex in y” or “with respect to y”.\n\t•\tClarify the set notation: defining \\mathcal{X} = \\mathbb{R}^{d_x} after stating x \\in \\mathcal{X} can be misleading.\n\t•\tFix the confusion between “Lipschitz continuous” and “Lipschitz smooth” (e.g., Lines 134, 168).\n\t•\tPlease add numbering to key formulations (e.g., line 140) for clarity.\n\t\n5.\tUse of Saddle Envelopes:\nIn line 211, the paper introduces a Moreau-like or saddle-envelope formulation (see [53]). How is this justified as being equivalent to the original problem? More explanation is needed.\n\n6.\tExperimental Evaluation:\n\t•\tFor the transportation network problem, how long does the algorithm take to run?\n\t•\tCan the authors provide convergence plots under a 24-hour time budget to demonstrate practical efficiency?\n\t•\tIn the SVM and transportation tasks, how well is the lower-level problem solved (e.g., optimality gap)?", "limitations": "Yes. The paper focuses on a specific BLO setting (LL strong convexity and linear inequality constraints) and clearly outlines the assumptions needed. The scope is narrower than in some related work, which should be acknowledged more clearly, but this limitation is not ignored. e.g. future potential improvement can be on a more generalized constraint setting or relaxing LL SC assumption to PL.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\t•\tIntroduces a novel reformulation strategy using slack parameters and augmented Lagrangians for handling LL inequality constraints.\n\t•\tPresents a theoretically grounded, fully single-loop algorithm (SFLCB) with a provable convergence rate of O(\\epsilon^{-3}).\n\t•\tExperimental evaluation on diverse tasks demonstrates practical performance.\n\nWeaknesses:\n\t•\tThe language and writing clarity hinder readability and understanding of key concepts. Several expressions are nonstandard or unclear.\n\t•\tThe claimed equivalences between various reformulations are not always rigorously justified. Some gaps remain, especially between function-level and pointwise equivalence.\n\t•\tThe paper occasionally re-derives known results without citing or contrasting them with existing literature.\n\t•\tComparison to related work is somewhat unfair in cases where the settings differ (e.g., projection in [16] only because of its more complicated setting of considering domain constraint Y).", "was_revised": true, "final_justification": "I believe this paper presents a solid method with both theoretical and empirical strengths. The proposed approach is well-motivated, and the results are promising. However, I have two significant concerns that affect my overall assessment.\n\nFirst, the writing quality is a major barrier. The language is often unclear and difficult to follow, which hinders readability and makes it challenging to fully evaluate the technical contributions. While the authors acknowledged this issue in the rebuttal and committed to improving the presentation, the current state of the writing makes it hard to assess whether the revisions will be sufficient to resolve the underlying clarity issues.\n\nSecond, the analysis techniques and experimental setup, while sound, appear fairly derivative. In addition, several known results are stated without appropriate citation in the main text, which weakens the positioning of the paper within the existing literature.\n\nGiven the strength of the method itself, I have decided to slightly raise my score. However, due to the concerns above — especially the difficulty in fully interpreting the contributions — I have lowered my confidence to reflect this uncertainty. I believe the paper could become a strong contribution with substantial revision.", "rebuttal": "We thank the reviewer for the valuable comments. Please see our responses below.\n\n>In the table on page 3: [16] handles general domain constraints Y, not just LL inequality constraints. Please acknowledge this distinction.\n\nThanks for your advice. We will acknowledge this distinction in the revised paper. Actually, [16] assumed that $Y$ is a domain that is easy to project, and for any $y\\in Y$ in a neighborhood of $y^*(x)$, its constraints satisfy the LICQ condition. Thus, [16] only used a simple projection to $Y$ to handle this domain constraint $Y$. If we adopt the same assumption on $Y$ as in [16], then in our algorithm we can simply add a projection onto $Y$ to handle this domain constraint, which would not cause any issues in theory or practice. The main theoretical focus of our work is on handling _coupled constraints_ of the form  $Bx+Ay-b\\leq 0$, which are not easy to project onto. For such constraints, compared to [16], our work improves the double-loop algorithm to a single-loop one and provides a theoretical guarantee of better complexity. We believe these are significant results. Furthermore, in practice, single-loop algorithms are easier to implement. Our experiments also demonstrate that our method empirically outperforms [16].\n\n>The comparison in line 112 is arguably unfair since [16] requires projection due to its more general setting.\n\nWe do acknowledge that [16] considers a more general setting, and we will highlight this in the revised paper to avoid misunderstandings, However, in line 112, what we stated was: \"However, they [16] did not provide a discussion between the stationary point of the reformulated function $\\Phi_\\delta$ and the original hyper-objective $\\Phi$.\" This is a factual description of their work [16]. While [16] considers a more general setting, it does not discuss the relationship between the stationary point of the reformulated problem and that of the original problem. Our work focuses on a more specific setting and provides a discussion on this relationship.\n\n>Please also include [20] in the table and discuss its relevance. This will strengthen the positioning of the paper.\n\nThanks for your advice. The main reason we did not include [20] in Table is that [20] used a different stationary measure so that the complexity results of [20] are not directly comparable to our paper and [16, 21]. Our paper used the same reformulation as [16, 21], and as a result the complexity results of our paper and theirs are comparable. Thus, we mainly compared [16], [21] and our paper in Table and discussed [20] in the Related Works section. We will add [20] to Table and add some explanations in the revised paper.\n\n>The paper uses gradient equivalence between the original BLO and the value-function-based penalty formulation (original BLO problem (0) to penalty reformulation (1) ), but the later equivalences (e.g., step 2 to 4) a at optimal points. Can the authors clarify this distinction and avoid using “equivalence” loosely? This impacts the logical flow of the methodology.\n\nThanks for your advice. We will clarify this distinction in the revised paper and avoid using “equivalence” loosely. Yes, the “equivalence” in Section 5 refers to the optimal points. Our derivation in Section 5 is intended to illustrate the idea behind the design of SFLCB. In fact, in Theorems 5.2 and 5.4, as well as Corollaries 5.3 and 5.5, we established the convergence results for stationary points of $\\Phi_\\delta$.\n\n>Several results appear to overlap with prior literature: Theorem 4.1 vs. Theorem 1.1 in [21] and Theorem 1/2 in [38]\n\nIn Appendix line 824, we stated that \"Similar results and proofs of Theorem 4.1 can also be found in [21, 16].\" Thanks for your advice, we will add these citations in the main text.\n\n>Lemma 4.4 vs. Lemma 2 in [16]\n\nIn Appendix line 840, we stated that our proof used the Lemma 2 and 3 in [16]. Thanks for your advice, we will add these citations in the main text.\n\n>Lemma 4.7 vs. results in [21]\n\nOur Lemma 4.7 is different from the results in [21]. [21] considers lower-level constraints  $y\\in Y$ that are independent of $x$, whereas our work analyzes coupled constraints of the form $y\\in Y(x)=$ { $y\\in R^{d_y} | h(x,y)\\leq 0$ }. Actually, in Appendix line 848, we stated that our Lemma 4.7 used Theorem 2 in [45]. We will add the citation in the main text.\n\n>Theorem 4.9 vs. Theorem 1.1 in [21]\n\nOur Theorem 4.9 is also very different from Theorem 1.1 in [21]. The analysis in [21] only considers lower-level constraints \n$y\\in Y$ that are independent of $x$, whereas our work analyzes coupled constraints of the form $y\\in Y(x)=$ { $y\\in R^{d_y} | h(x,y)\\leq 0$ }. Handling such coupled constraints requires estimating the Lagrangian multipliers in the implicit gradient formula, which makes our analysis more involved compared to [21]. Notably, the Future Directions section of [21] also emphasizes that analyzing lower-level $x$-dependent constraints is a valuable direction for future research, highlighting the value of our work.  In the main text line 191-194, we also stated the connections and differences between our results and those in [21].\n\n>Terminology and Notation\n\nThanks for your advice. We will modify these in the revised paper.\n\n>In line 211, the paper introduces a Moreau-like or saddle-envelope formulation (see [53]). How is this justified as being equivalent to the original problem?\n\nThanks for pointing out our imprecise use of terminology. In line 211, we mean $K$ and $L_\\delta$ have the same optimal points and same optimal function value. Our derivation in Section 5 is intended to illustrate the idea behind the design of SFLCB. In fact, in Theorems 5.2 and 5.4, as well as Corollaries 5.3 and 5.5, we directly established the convergence results for stationary points of $\\Phi_\\delta$ (not for $K$). We hope this response can address your concern.\n\n>For the transportation network problem, how long does the algorithm take to run? Can the authors provide convergence plots under a 24-hour time budget to demonstrate practical efficiency?\n\nThanks for your advice. We will add plots in the revised paper to better illustrate how the UL utility converges over time. Since the rebuttal does not support images, we present the following primary results in tables.\n\n3 Node:\n|Time(s)|1|2|3|4|5|\n|---|---|---|---|---|---|\n|BLOCC|1.36|1.66|1.70|1.70|1.71|\n|SFLCB|1.04|1.69|1.84|1.84|1.84|\n\n9 Node:\n|Time(s)|20|40|60|80|100|120|140|160|180|200|250|300|350|400|\n|---|----|----|----|----|----|----|----|----|----|----|----|----|----|----|\n|BLOCC|-420.87|-89.73|-23.66|-4.62|1.72|6.25|6.59|8.55|8.93|9.14|9.53|9.15|9.52|9.54|\n|SFLCB|2.57|12.09|15.30|18.03|19.95|20.52|20.92|21.18|21.19|21.20|21.06|20.79|20.67|20.40|\n\nIn the 9-node setting, we set $\\delta=0.25$ in SFLCB for better comparison with BLOCC (since in our reformulation, $\\delta$ has a similar role as $1/\\gamma$ in BLOCC and $\\gamma=4$) and keep all other hyperparameters the same as those in our current paper. Note that the $\\delta$ here is different from the one used in our paper. Thus, the results of the 9-node setting are different from the current paper.\n\nWe can see that in both the 3-node and 9-node settings, SFLCB converges faster than BLOCC and achieves better UL utility.\n\n>In the SVM and transportation tasks, how well is the lower-level problem solved (e.g., optimality gap)?\n\nThanks for this question. For SFLCB, suppose its final outputs are $x, y', u, z', v$. We keep its $x, y', u$ fixed, and only optimize $z'$ and its multiplier $v$ for additional 1000 interactions to get $z^{\\ast}$ as its LL optimal point. Then, we calculate $||z-z^{\\ast}||$ as its optimality gap. For BLOCC, suppose its final outputs are $x, y_g, \\mu_g, y_F, \\mu_F$. we also fix its final output $x$ and run the inner loop to optimize $y_g, \\mu_g$ for additional 1000 interactions to get $y_g^{\\ast}$ as its LL optimal point. We then calculate $||y_g-y_g^{\\ast}||$ as its optimality gap. For SVM, we find that SFLCB's optimality gap is 3.6e-2, and BLOCC's is 1.9e-2. For the transportation 3-node task, the SFLCB's optimality gap is 6.6e-6, and BLOCC's is 2.3e-3. For the transportation 9-node task, the SFLCB's optimality gap is 9.7e-3, and BLOCC's is 5.5e-2. Overall, it can be observed that BLOCC and SFLCB have optimality gaps of similar magnitude and these optimality gaps are relatively small, indicating that the lower-level problem is well-solved.\n\n>The paper focuses on a specific BLO setting (LL strong convexity and linear inequality constraints) and clearly outlines the assumptions needed. The scope is narrower than in some related work, which should be acknowledged more clearly, but this limitation is not ignored. e.g. future potential improvement can be on a more generalized constraint setting or relaxing LL SC assumption to PL.\n\nThank you for this constructive comment. We acknowledge that some related works [16, 48, 49] have considered more general settings, and future research can be done on more general settings. However, it is also worth noting that linear constraints already encompass a broad range of applications, including but not limited to distributed optimization [47, 18], adversarial training [52, 18], and hyperparameter optimization for some constrained learning tasks. Several related works have also concentrated on analyzing linear constraints with LL strong convexity, such as [41, 18, 20]. Actually, [18, 41] considered an even narrower setting ($Ay\\leq b$) than ours. Compared to the double-loop structure in [16, 20] and the requirement of Hessian computations in [18, 41], our work provides a single-loop first-order algorithm for linearly constrained BLO with rigorous theoretical analyses. Our experiments also demonstrate the practical efficiency of our method. Therefore, we believe that our work has its own contributions and value. We will add some discussion and highlight that future potential improvement is worth exploring in the revised paper."}]

Author rebuttal:

Meta-review: Based on my reading the reviews, author responses and discussion, I see the following strengths of this manuscript:

- **S1.** The manuscript presents a reformulation of a bilevel optimization problem with coupled lower level linear constraints, converting it to a single level problem using the value-function based formulation. Based on this, the paper proposes a first-order Hessian-free optimization algorithm, and studies the convergence of the reformulated problem. Furthermore, the difference between the solution of the reformulated problem and the original bilevel problem is also bounded.

- **S2.** The convergence rate provides improvement over existing double loop solvers, highlighting the benefit of the single loop solution.


I also see the following limitations of this manuscript:

- **L1.** The presentation of the manuscript is quite confusing in parts and requires significant revision to better highlight the novel contributions of this work. On a related note, as highlighted by reviewers, the authors need to better position the contributions with respect to existing literature. Overall, it seems that the manuscript would need a significant revision.

- **L2.** (minor) The actual algorithm requires multiple hyperparameters to tune though that seems to be standard in bilevel optimization literature. Furthermore, the authors shared some additional results in the rebuttal claiming that the proposed scheme is not sensitive to the choices of the hyperparameters.

Based on the author-reviewer discussion, it seems like all reviewers agree that their concerns have been addressed. However, this manuscript needs some revision with better presentation of contributions and better positioning against existing literature.

I am recommending an accept but I hope that the authors incorporate all the feedback provided by the reviewers.
Decision: Accept (poster)