Constrained Bi-Level Optimization: Proximal Lagrangian Value Function Approach and Hessian-free Algorithm
Authors: Wei Yao
Chengming Yu
Shangzhi Zeng
Jin Zhang
Venue: ICLR 2024 spotlight (2024)
Keywords: Bi-level Optimization
Constrained Optimization
Hessian-free
Single-loop
Value Function
Convergence Analysis
Primary area: optimization
TL;DR: This paper presents a new approach and algorithm for solving a class of constrained Bi-Level Optimization problems in which the lower-level problem involves constraints coupling both upper-level and lower-level variables.

Abstract: This paper presents a new approach and algorithm for solving a class of constrained Bi-Level Optimization (BLO) problems in which the lower-level problem involves constraints coupling both upper-level and lower-level variables. Such problems have recently gained significant attention due to their broad applicability in machine learning. However, conventional gradient-based methods unavoidably rely on computationally intensive calculations related to the Hessian matrix. To address this challenge, we devise a smooth proximal Lagrangian value function to handle the constrained lower-level problem. Utilizing this construct, we introduce a single-level reformulation for constrained BLOs that transforms the original BLO problem into an equivalent optimization problem with smooth constraints. Enabled by this reformulation, we develop a Hessian-free gradient-based algorithm—termed proximal Lagrangian Value function-based Hessian-free Bi-level Algorithm (LV-HBA)—that is straightforward to implement in a single loop manner. Consequently, LV-HBA is especially well-suited for machine learning applications. Furthermore, we offer non-asymptotic convergence analysis for LV-HBA, eliminating the need for traditional strong convexity assumptions for the lower-level problem while also being capable of accommodating non-singleton scenarios. Empirical results substantiate the algorithm's superior practical performance.

Published as a conference paper at ICLR 2024
CONSTRAINED BI-LEVEL OPTIMIZATION: PROXI- MAL LAGRANGIAN VALUE FUNCTION APPROACH AND
HESSIAN-FREE ALGORITHM
Wei Yao 24 Chengming Shangzhi Zeng"l, Jin Zhangal.
National Center for Applied Mathematics Shenzhen, SUSTech, DDepartment of Mathematics, SUSTech, DDepartment of Mathematics and Statisties, UVic, *CETC Key Laboratory of Smart City Modeling Simulation and Intelligent Technology, The Smart City Research Institute of CETC {yaow, 9 edu. en, yucmêmail sustech. edu. sengshangzhi@uvicc...
ABSTRACT
This paper presents approach and algorithm for solving class of con- strained Bi-Level Optimization (BI.) problems in which the lower-level problem involves constraints coupling both upper-level and lower-level variables. Such problems have recently gained significant attention due to their broad applicabil- ity machine learning. However, conventional gradient- crasient-based methods unavoid- ably rely on computationally intensive calculations related to the Hessian matrix. To address this challenge, we devise smooth proximal Lagrangian value fune- tion to handle the constrained lower-level problem. Utilizing this construct, we introduce a single-level reformulation for constrained BL.Os that transforms the original BLO problem into equivalent optimization problem with smooth con- straints. Enabled by this reformulation, we develop a Hessian-free gradient-bart based mhoritthm-termd proximal Lagrangian Value caccion-bbaed Hessian-free Bi- level Algorithm (LV-HBA) that is straightforward to implement in a single loop manner. Consequently, LV-HBA is especially well-suited for machine learning applications. Furthermore, we offer non-asymptotic convergence analysis for LV- HBA. eliminating the need for traditional strong convexity assumptions for the lower-level problem while also being capable of accommodating non-singleton scenarios. Empirical results substantiate the algorithm's 's superior practical perfor- mance.
INTRODUCTION
In this work, we consider the constrained Bi-Level Optimization (BLO) problems with possibly coupled lower-level (LL) constraints, which is in form of,
min xEX
F(x, v) s.t. y S(x),
(1)
where S(x) denotes the set of optimal solutions for the constrained LL problem,
min VEY
f(x v) s.t. g(x. v) < 0.
Here both X C R and Y S R. are closed convex sets. The upper-level (UL) objective F X Y R. the LL objective f X x Y R. and the LL constraint mapping g X R are continuously differentiable functions. It is noteworthy that both LL objective f and constraint mapping g are functions of UL variable æ LL variable y.
BLO has recently emerged as powerful tool for tackling various modern machine learning prob- lems characterized by inherent hierarchical structures, such as hyperparameter optimization Pe- dregosa (2016); |Franceschi et al. (2018); |Makay et al. (2019). meta learning |Franceschi et al. (2018): Zügner Günnemann (2019); Rajeswaran al. (2099: et al. (2020). neural architec- ture search Liu et al. (2018); Liang et al. (2019); Elsken et al. (2020), to name a few. Among them, the constrained BLOs capture several important applications, including adversarial learning
"Correspondence Jin Zhang (zhangj9 @suuttcch.cuu.cm)

---

Published as a conference paper at ICLR 2024
Table 1: Comparison of our method LV-HBA with closely related works for constrained BLO
IG-AL saknakis et al. (2022). SIGD Khanduri et al. (023). AiPOD/E-AiPOD Xiao et al. (022b),
GAM & Zhu ( BVFSM Liu al. (2023a) All method, except BVFSM, require the LL.
strongly convexity assumption, which implies the singleton of the LL minimizer. GAM and BVFSM
provide only asymptotic convergence analysis. Using ((x, y) = 0 + h(z, y) S 0, -(x, y) 0,
our method allows for the inclusion of linear constraints.
Single Loop
Method
LL Objective
LL Constraints
Hessian-Free
Non-Singleton
IG-AL
Strongly Convex
Ay <.b
X
X
SIGD
Strongly Convex
Ay S
X
X
X
AiPOD
Strongly Convex
Ay A)x) =
X
X
E-AiPOD
GAM
Strongly Convex
g(5, y)
X
X
X
h(,, y)
BVESM
Convex
g(x, v) < 0
X
LV-HBA
Convex
g(x, v) 0
Madry et al. (2018); Wong et al. (2019); Zhang et al. (2022). federated learning Fallah et (020); Tarzanagh et al. (2022); Yang et al. (2023b), see the recent survey papers Liu et al. (2021a) Zhang et al. (223) for more applications machine learning and signal processing.
Owing to their effectiveness and scalability. muddient-based algorithms have become mainstream techniques for BLO in learning and vision fields[Liu et al. (202Ta). While gradient- algorithms for unconstrained BLO problems have been extensively explored in the literature Ghadimi & Wang
(2018): 201aaa et al. (2019); Liu et al. (2020; 2021b); Huang et al. (2022); Ji et al. (2021 2022);
Hong et (2023); Dagréou et al. (2022) Ye et al. (2022); Liu et al. (2023b); K Kwon et al. (2023a) research focusing on efficient methods for constrained BLO problems is quite limited. This gap is especially evident in scenarios where LL constraints couple both UL and LL variables.
Indeed, the majority of existing works in this direction focus on particular types of constrained LL problems. For instance, recent works Tsaknakis al. (2022); Khanduri et al. (2023) address constrained BLOs where LL problem pertains to minimizing a strongly convex objective subject to linear inequality constraints. The study Xiao et al. (2023)) considers the stochastic BLO prob- lems with equality constraints at both upper and lower levels, while Xu & Zhu (2023) studies BLOs wherein LL problem convex with equality and inequality constraints and presumes that LL ob- jective is strongly convex and the constraints satisfy Linear Independence Constraint Qualification (LICQ). Notably, the methods presented in these works all employ implicit gradient- based tech- niques, relying on implicit gradient computation of LI. solution mapping. This dependency requires both the uniqueness and smoothness of L.L. solution mapping, thereby limiting its applicability. Crit- ically, implicit gradient techniques necessitate computationally intensive calculations related to LL Hessian matrix. In this context, a natural yet important question is: algorithms for constrained BLOs?
Can we devise Hessian--ree
A recent affirmation to this question is provided in Liu et al. (2023a), leveraging the value func- tion approach Ye & Zhu (1995). For constrained BLOs, value function-baas methods encounter issues tied to non-differentiable constraints emerging from the value function based reformulation. To circumvent this non-smoothness issue, [iu et al. (2023a) introduces sequential approximation minimization strategy. Herein, quadratic regularization alongside penalty/barrier functions of LL inequality constraints are applied to smooth LL value function. Nonetheless, this approach necessi- tates solving a series of subproblems and lacks a non-asymptotic analysis. This leads to a practical question: Can we devise Hessian-free algorithm in a single-loop manner for constrained BLOs? 1.1 MAIN CONTRIBUTIONS
In this study, we provide affirmative answer to the previously raised question. We first pro- pose a single-level reformulation for constrained BLO problems by defining a proximal Lagrangian value function associated with the constrained L.I. problem. This function is defined as the value
2

---

Published as a conference paper at ICLR 2024
function of a differentiability. As result, our approach recasts constrained BLO problems into single-level opti- mization problems with smooth constraints. Drawing from this reformulation, free gradient-based algorithm for constrained BLOs, and provide the non-asymptotic convergence analysis. Conducting such analysis, especially given L.L constraints, is non-trivial. By utilizing the setel---oooee-stoogl-y-o-o
proximal min-max problem and exhibits continuous
devise Hessian-
structure within the min-max problem of the proximal La- grangian value function, we can approximate its gradient using only the first-order data from LL problem. The error in this gradient approximation remains controllable, without the need for LL objective's strong convexity. This facilitates our establishment of the non-asymptotic convergence analysis of the proposed algorithm for constrained LL problem with merely convex LL objective.
Our primary contributions are outlined below.
We introduce a novel proximal Lagrangian value function to handle constrained LL prob- lem. By leveraging this function, we present new single-level reformulation for con- strained BLOs, converting them into equivalent single-level optimization problems with smooth constraints.
Drawing from our reformulation, propose the proximal Lagrangian Value function- based Hessian-free Bi-level Algorithm (LV-HBA) tailored for constrained BLO problems with LL constraints coupling both UL and LL variables. To our knowledge. this work is the first to develop a provably Hessian free gradient- algorithm for constrained BLOs in single-loop manner. A brief summary of the comparison of LV-HBA with closely related works is provided in Table
We rigorously establish the non-asymptotic convergence analysis of LV-HBA. Employ- ing the proximal Lagrangian value function, we eliminate the necessity for LL objective's strong convexity, thereby accommodating merely convex LL scenarios.
We evaluate the efficiency of LV-HBA through numerical experiments synthetic prob- lems, hyperparameter optimization for SVM and federated bilevel learning. Empirical re- sults validate the superior practical performance of LV-HBA
1.2 RELATED WORK
In the section we give a brief review of some recent works that are directly related to ours. An expanded review of recent studies BLOs is provided in Section A.2
Reformulations BLOss One the most commonly approaches for BLOs is to reformulate them single-level problems. This can often be done in two ways Dempe & Zemkoho (2013). One is known as KKT reformulation/ Kim et al. (2020). which replaces LL problem with its Karush-Kuhn Tucker (KKT) conditions. Consequently, it unavoidably relies first-order gradient information. As a result, gradient- algorithms based on it also necessitate second-order gradient informa- tion. In contrast, value function reformulation does not rely on any gradient information. Benefiting from this, the majority of existing Hessian-free gradient-based -based algorithms for both unconstrained and constrained BLOs, are developed based on value function reformulation, see, e.g.. Liu et al. 2021b 2 Ye et al. (2022); Sow et al. (2022); Shen & Chen (2023): Kwon et al. (202a)); Lu & Mei (2023): Lu (2044). Recently, Gao et al. (2023) proposes new reformulation of BLOs, using Moreau envelope of LLI problem, to weaken the underlying assumption from I.I. full convex- ity in Gao et al. (2022) to weak convexity. However, Moreau envelope-based reformulation still encounters challenges related to non-differentiable constraints, arising from the reformulation itself.
Algorithms for Constrained BLOs. Other than the previously mentioned works that focus on LL constraints, there is a line of research dedicated to addressing the constrained UL setting, including: implicit approximation methods in Ghadimi & Wang (2018); two evo-timescale framework in Hong
et al. (2023); single-timescale method in Chen al. (2022a); initialization auxiliary method in
Liu et al. (2021c); Bregman distance- based method in Huang et al. (2022); proximal gradient-type algorithm in Chen et al. (2022b); inexact conditional gradient method in Abolfazli et al. (2023)
3

---

Published as a conference paper at ICLR 2024
2 PROXIMAL LAGRANGIAN VALUE FUNCTION APPROACH
In this section, we introduce a novel single-level reformulation for constrained BLO problems, foun- dational to our proposed methodology. Furthermore, we describe the proposed algorithm LV-HBA. To simplify our notation, throughout this paper, for LL constraint mapping 9 X x Y + R' and any vectors À 14,, R', we represent Σ X and Σi= 2:9; Ag and 2g. respectively. Similarly, E AeVugh and Ei=1 2i V.Va Vygi are denoted by XV ug and =Vy9. respectively.
2.1 REFORMULATION VIA PROXIMAL LAGRANGIAN VALUE FUNCTION
We start by introducing the proximal Lagrangian value function my (2r, y, 2) for LL problem, drawing inspiration from Moreau envelope value function discussed in Gao et al. (2023). It is defined as:
(2 2) == min max
BEY XER, [(2, -gg,x) 0) +
{
1
100 ylI
1
211 21²}
(3)
2
272
where = E E == (A 00.). 7 = (21,72) 2 is the proximal parameter. Note that far v) + (x, y) is the Lagrangian function of LL problem. Employing this function, present a smooth reformulation for constrained BLO problem (I:
min F(x,, v) s.t. f(x. (x y, 2) s 0,
(4)
(x.0)EC,220
where := ((x,)) E X g(x,y) - 0}. Under the convexity of L.I. problem and the exis- tence of multipliers for LL problem, the equivalence between reformulation (4) and constrained BLO problem (I) is established. Notably, f(x,
By (z, y, 2) > 0 for any (I, E C x R..
Comprehensive proofs proofs can be found in Theorem A. in Appendix A.3
To guarantee the theoretical convergence of the proposed method, instead of directly solving refor- mulation we consider its variant using a truncated proximal Lagrangian value function,
110 y11² { [xx 0) + Ag(a, 0) + 2n1
1 2/2
By (x, (z, = min max BEY XEZ
||
=1|?
(5)
where : 00,)' C RR, and r > O. Compared with v, (x,, y, z), the truncated version uy (2r, yr 2)
defined by maximizing over bounded set Z instead of over RK,,, And the truncated proximal
Lagrangian value function gives us the following variant to reformulation (
min F(x, v) s.t. f(x, Uy (z, 2) < O. (x.
(6)
Note that [3x y) -r (Ir, y, z) for any (x, y, 2) C Z. If sufficiently large, the solution of reformulation (4) can be obtained by solving variant (6). comprehensive proof is presented in Theorem A.2 within Appendix A.3
2.2 GRADIENT OF PROXIMAL LAGRANGIAN VALUE FUNCTION
An important property of v. (z, y, 2) and its truncated counterpart Uy,r (1 2) is their continuous differentiability under the setting of this study, as elucidated in Assumptions 3.2 and 3.3 Specif- ically, (x, and g(z, -) are convex on Y, the proximal min-max problems stoonlyy-coneee---nnnn soouvve-stroonly-ooo strongly-concave. By invoking saddle point theorem, these problems possess unique saddle points. Moreover, with continuous differentiability for both f and g. the gradient Vey (2, y, can be derived with the explicit expression as
3 and (5) are
(y-0") 0*) (x* 2²-)) 2)
+ X"Vzg(x,00" (I. (
72
where "0, := (x. u. 2), (x, y, 2)) denotes the unique saddle point for the min-max max prob-
lem in (5. Similarly, for ey (2, y, 2). the gradient Vv, (z. y, 2) shares the same form as in (7 but
with (0 x*) corresponding to the unique saddle point of the min-max problem in (3) A detailed proof can be found in Lemma A. within the Appendix.
4

---

Published as a conference paper at ICLR 2024
2.3 THE PROPOSED ALGORITHM
We introduce LV-HBA, a Hessian-free gradient-based algorithm designed for constrained BLOs. ,,,=,,,,,, At each iteration, given the current values of (x* , =* 0%, >²), we initiate by executing a single gradient descent ascent (GDA) step for the proximal min-max problem described in 5 updating the variables (0, X) as follows
(0K+1, / A Projyx2 xz ((0+, x*) The (dt. d(x)= where Projz represents the Fuclidean projection onto the bounded box 7, and
(8)
(dg (2) = (V ,0) + X V vg((" 00) +
1 - v²), - gg(0, 0²) + - (1*
zb1)
-
(9)
711
72
Subsequently, we update the variables (I, y, 2) as follows
(x y ) = Projc ((**, ,h) - on (1 d
(10)
++1 = Projz (2* -Bad))
where the directions are defined as:
1
d= V. F( y² + V v. 2² - an ,0,t10022--000 1 Vzg(e ghtl),
d = 1
Fx 15 + V (x x/ - (u* -
(11)
d: (1++1 - 2²)).
7/2
comprehensive description of LV-HBA provided in Algorithm
Algorithm proximal Lagrangian Value function-baas Hessian-fres Bi-level Algorithm (LV-HBA)
Initialize: (x.", yy) E X E Z, (09, 29) E x B4,, stepsizes ou, Sk. Mee proximal parameter
7, penalty parameter CR:
1: for k= =,0,1.... K do
2: calculate (dy d as in equation
3: update (Ok+1, 1 = Projy x
00k 2²) mn (dl d;));
4: calculate d d dh as in equation 11
5: update
(a y x+1
Projc ((* y²r) - axdd d(y)
k+1 = Projz (2* - Brd=))
6: end for
We provide insight into the construction of LV-HBA. The update of variables (x, y. in (1)) can be interpreted as inexact alternating proximal gradient step from (x wh z*) concerning the following minimization problem:
1 F(x,V) + (xx
min (x,5)EC,sE2 C
Drawing from the gradient formula of (2, v, 2) given in (Vaf(z*, (k+1) + X++1 (ag @k+1), (y* ( 2/1 (X++1 2²//22) in 1II can be considered as approxima- tions to Vuy, (x, y, 2), using (ok (o++1 (,bt1) as a proxy to (0*
Particularly, when the feasible sets Y and C exhibit "projection-friendly"" characteristics, meaning that the Euclidean projection onto them is computationally efficient, LV-HBA can be characterized single-loop Hessian-free pradient-bsed algorithm for constrained BLO problems.
3 NON-ASYMPTOTIE CONVERGENCE ANALYSIS
In this section, we conduct non-ast msymotitit analysis for LV-HBA. We begin by outlining the basic assumptions adopted throughout this work.
5

---

Published as a conference paper at ICLR 2024
3.1 GENERAL ASSUMPTIONS
The following assumptions formalize the smoothness property of UL UL objective P. and smoothness and convexity properties of LL objective and LL constraints g-
Assumption 3.1 (Upper-Level Objective). The UL objective F is Lp-smoolff X Y. Addi- rionally, F is bounded below on X x Y, i.e., E = inf( F(x, -OC.
Assumption 3.2 (Lower-Level Objective). Assume that the following conditions hold:
(i) is convex w.r.t LL variable Y for any X. (ii) is continuously differentiable
open set containing X Y and is Ly-smooth X x Y.
Given that f is L ysmooth on X x Y, by leveraging the descent lemma (Beck 2017 Lemma 5.7). it can be deduced that f is also wy-wakkly convex, i.e, (x, y) + Ly Ex]](x, / is convex on X x Y. Consequently, under Assumption 3.2
py-weakly convex on X Y. with Pf potentially being smaller than Ly. To precisely determine the range for the step sizes of LV-HBA, we will employ the weak convexity constant of f. py. in subsequent results.
Assumption 3.3 (Lower-Level Constraints). Assume that the following conditions hold:
(i) g( v) is convex and be Lg Lipschitz continuous on X x Y.
(ii) g(x, y) is continuously differentiable V Vg y) are Lg and Lg -Lisschizz continuous on x respectively.
open set containing X X Y, Vag(z,v) and
Our assumptions are based solely on the first-order differentiability of the problem data. The setting of this study substantially relaxes the existing requirement for second-orde -oder differentiability in con- strained BLO literature. Notably, we do not impose strong convexity on the LL objective As result, our analysis encompasses LL problem non-singleton scenarios, as detailed in Table [
3.2 CONVERGENCE RESULTS
To derive the non-asymptotic convergence results of LV-HBA, we first demonstrate the decreasing property of merit function introduced below,
Vi == Poe (z* "y" 2x + Cox || 1²) - (1 ,² (, 3 )|
(12)
where Cos == max C2L.11 + 1/(27?) + L. 1 C2 max ||=||| and
1 (F(z,)) F) + f(x, v) (,,r(1,
Dep (xt y, 2)
(13)
Ck
Lemma 3.1. Under Assumptions
3.1
3.2 and
3.3 let 71 E 1/p)) 72 > O, ck+1 2 c and
Th E (T/ (23)) with n > 0, Pr min //1 Ps. 1/72) and LB == max [, by + Cz +
1/71, by + 1/ra,, then there exist constants Cae, Cg > such that when ar (0, cal and Ba cp], y the sequence of (x* y*, 2*) generated by LV-HBA satisfies
Va41 VV
1
[1 ,b+t) (z >/111 1
11 11att1- 2112
4ax
4.8
(14)
Cex ||00k x ) (x* v 2)) (a s 1)
The step sizes are carefully chosen to guarantee the sufficient descent property of V₁. This es- sential for the non-asymptotic convergence analysis. Comprehensive proofs for Lemma 3.1 and accompanying auxiliary lemmas can be found in Sections A.44 A.5 in Appendix.
Given the decreasing property of V4. we proceed establish the non-asymptotic convergence analy- sis. Owing to the constraint f(x y) Uy y, 2) < 0 in 6 by employing an argument analogous be deduced that conventional constraint qualifications are not satisfied
Ye & Zhu (995),
'Recall that function h is said be T-smooth on Ω if is continuously differentiahle and its gradient Vh Tpsshisc continuous Q

---

Published as a conference paper at ICLR 2024
at any feasible point of constrained problem ( appropriate as necessary optimality conditions for problem (6). Motivated by the approximate KKT condition presented in Andreeni et al. (2010), which is characterized nonlinear program, regardless of constraint qualifications fulfillment, we consider the following residual function Rg R2 (2, y, 2) as stationarity measure,
As result. the standard KKT conditions are in-
optimality condition for
R& dist (0, (VF(z, y). 0) cæ ((V v).0) (e, 2)) (2, (15)
where (s) denotes the normal cone to s. This residual function Rx y: 2) also serves as stationarity measure for the penalized problem of (6). with cæ serving as the penalty parameter,
min Vee (I, y, (#.y)EC,aEZ
F(z, v) + (f(z, v) uy (x, y. 2))
(16)
Evidently, R4 [x, = 0 if and only if (at, y, =) is stationary point for problem (16). meaning O E Vile (I, 2) NCx (x, v, v)=.. =). The following theorem offers the non-asymptotic convergence for LV-HBA, and the proof is detailed in Section A.6 of the Appendix.
Theorem 3.1. Under Assumptions of Lemma 3.1 let " E (0, (0,1/P)). '22 c = c(k + 1) with E (0, 1/2), >> O and E (n, pr [. then there exist Ca. C3 0 such that when og E (a, Ca)
and B& (B, ca) with a, B > the sequence of (w* sxt * 0h, X²) generated by LV-HBA satisfies
1 K1/2
min (1 (0) (0 ,²,²" X2("" .0t D| =0 o
and
min R& (x xt1 uSkSK
= ,
((1-2p)/2
Furthermore, if there exists M > such that ten (1* at .1² 2 S M for any k, the sequence of (a y²t x² satisfies
S f(* ("*) vy (x yk 2*) f(x ,,*),,,))))))) 2y vy , "8 )
KP
4 EXPERIMENTS
In this section, we evaluate the empirical performance of LV-HBA using numerical experiments on synthetic problems, hyperparameter optimization for SVM, and federated bilevel learning problem. We compare LV-HBA against AiPOD, E-AiPOD (Xiao et al. 2023b), and GAM (Xu & Zhu 2023)) The results underscore the effectiveness of LV-HBA in practical scenarios. Detailed experimen- tal settings and parameter configurations can be found in Appendix The code is available at https://githur con/ SUS Tech- Opt imi inn
4.1 SYNTHETIC EXPERIMENTS.
We test LV-HBA in comparison to AiPOD and E-AiPOD, on two synthetic coupling equality- constrained BLOs from two distinct scenarios: merely convex and strongly convex LL objectives.
E-4POD
-EAPOD
-EAPPO
APOU
AIPOL LVMIBB
Airco
AIPOO
1
LV-IBB
LX-IBA
LV-IBA
1.3
03
40
60 Time
60
150
20
48
50
50
100
120
140
160
120
18)
50
20
100
120
140
(1)
Time
(3)
Time (6)
Time
Figure 1: Comparison between AiPOD, E-AiPOD and LV-HBA LL merely convex synthetic
problem. Left two figures: initial point 10- 1 E 300 Right two figures: initial point 100 E 300
LL merely convex. We consider BLO with coupling equality constraints given by
1
1 11 s.t. y arg min (x))(z)
min
||I
12ll +
2 llvi
| IT 1/1 + 1 1
*ER" (:8

---

Published as a conference paper at ICLR 2024
where 1 IR" represents vector with all elements equal and ((x)) {y E R
1 x +
1 511 + 1" 1/2 = 0}. Its optimal solution can be analytically expressed as x= 10 1, yi
3
10 1,
V/ = - 1. For the problem where n = 100, we test algorithms from two distinct initial points: 10 E R-300 and 100 1 E R:000 The convergence curves relative to time are presented in
Figure ! Notably, LV-HBA provides more precise approximation the optimal solution and demonstrates faster convergence compared to AiPOD and E-AiPOD, The inadequate performance of AiPOD and E-AiPOD may stem from the fact that while our synthetic problem has a merely convex L.I objective, both AiPOD and E-AiPOD require strongly convex L.L objective for convergence. Moreover, we examine the sensitivity of parameter Cş LV-HBA, and present its convergence curve in Figure 2 We further test the synthetic problem in a high-dimensional setting to demonstrate the computational efficiency of LV-HBA by increasing the dimension n. We record the time when ||æ I| ||//||==||| 10 is met by the iterates generated by LV-HBA. Results in Figure highlight the computational efficiency of LV-HBA
10
10
10
Time(s)*1
10a
10
10
35
40
10 20
30
40
50
60
70
80
Time (s)
Time
(8)
Dimension 10"
Figure 2: Left two figures: Impact of p in parameter c₁ for LV-HBA. Rightmost figure: Time taken achieve a specified accuracy v.s. dimension for IV-HBA.
LL strongly convex. We consider the strongly convex instance as presented in Xiao et al. (023b):
min sin (c + d x (x)) + (1 y" (x)]1 (1))++1) ZEX
y" (x) arg min | yll? yEV(#)
1 2
where X x= = fz Bx = 03 c R 100 (xx) = {y Ay+ Hz = 0} 100 and A, B, H, c, are non-zero matrices vectors imported from the code of Xiao al. 2023b) available https: //github. www.coo.cacceaoeo wwwm/hannsenn//AIPP..
Contrary to the experiment in Xiao et al. (202b)). we do not add Gaussian noise in this simulation. We test algorithms from two different initial points: 5 51,,1) and 10 11 in 200 We use the norm of l - yxx]] as one stationarity measure, another one is the value of hyper-objective F(a*, y² (x*)). We depict the respective convergence curves over time in Figure B Empirical results highlight the superior speed of convergence of our IV-HBA compared both AiPOD and E-AiPOD.
APPOO
APOU
LV-BIA
LV-IIIA
LV.HBA
E-APPDD APPOO L LV-HBA
30
29
150
210
100
26
166
Ticre (5)
Time (3)
Time (5)
Tane (3)
Figure 3: Comparison between AiPOD. E-AiPOD and LV-HBA on BLO with LL strongly convex objective. Left: initial point 5(1, 1) in IR Right: initial point 10(1, 1) in 22000
Table Numerical results on the hyperparameter optimization problem of SVM and the data hyper- cleaning task. The notation a + b signifies a mean value with a standard deviation of b over 40 trials.
Linear SVM
Data Hyper- gisette
Dataset
diabetes
fourclass
Method
GAM
LV-HBA
GAM
LV-HBA
GAM
LV-HBA
Accuracy
74 + 1.4
75.07 + 1.6
75.2 + 1.6
75.4 + 1.2
94.2 + 0.5
94.6 + 0.4
Time(s)
33.06 2.2
6.65+ 1.3
30 2.2
6 1.8
200
100=11.5
8

---

Published as a conference paper at ICLR 2024
4.2 HYPERPARAMETER OPTIMIZATION
We test the performance of our algorithm LV-HBA in comparison to GAM (Xu & Zhu 2023). Both algorithms applied the hyperparameter optimization problem of SVM and the data hyper- cleaning task, as described in Xu & Zhu (022)). comprehensive discussion of the problem for- mulation and the specific implementation settings can be found in Appendix A.1
Hyperparameter Optimization of SVM We center our attention on the linear SVM model and conduct experiments on the dataset diabetes from Dua al. (2017) and the dataset fourclass from Ho & Kleinberg (1996). The results are presented in Table 2 Moreover, Figure 4 illustrates the curve between test accuracy and time for the result on the dataset diabetes. Notably, our LV-HBA outperforms GAM by achieving superior accuracy within significantly reduced time.
Data Hyper-Cleaning We compare our LV-HBA against GAM on the data hyper-cleaning task (Franceschi et al. (217);; (Shaban al. (2019)) utilizing dataset gisette (Guyon et al. (2004). Results performance curve for test accuracy against time is depicted in Figure Remarkably, LV-HBA surpasses GAM, delivering enhanced test accuracy in a shorter time.
are tabulated in Table 2
0.71
succomt 12
V-IIIAA Cowd Sellaar (Tid)
3.50
0.6
3:55
2000
3030
Running time
Running time
Communication mond
Figure 4: Left: accuracy v.s. running time in hyperparameter optimization of SVM on diabetes; Middle: accuracy v.s. running time in data spper-cleaning Right: accuracy v.s. communication round in federated loss function tuning problem.
4.3 FEDERATED LOss FUNCTION TUNING
In this part, test our LV-HBA compared to E-AiPOD (Xiao et al. 2023b) and FedNest Tarzanagh (ct al. 2022) using the federated loss function tuning problem, as explored in Xiao et al. (202b)).
Detailed descriptions of the problem formulation and the specific implementation settings able in Appendix A This federated learning with imbalanced data task aims to develop a model ensuring fairness and generalization across datasets dominated by under-represented classes Li al.
avail-
(2021) Results, detailed in Table and Figure 4 indicate that LV-HBA surpasses E-AiPOD and FedNest in both communication complexity and computational efficiency.
Table 3:
Communication round and time taken to achieve specified accuracy in the experiment for the federated loss function tuning problem. E-A represents E-AiPOD; FN denotes FedNest; LV denotes LV-HBA.
Test accuracy:
90
Test accuracy:
92
Test accuracy: 94
Test accuracy
E-A
FN
LV
E-A
FN
LV
E-A
FN
LV
Round
527
625
65
1080
1575
149
2256
3010
588
Time(s)
x25.7
x27.4
1638
x23
x25.3
3754
x12
x x1..9
14994
CONCLUSIONS
This work proposes new approach and algorithm for solving class of constrained BLO problems which LL problem involves constraints coupling both UL and LL variables. The key enabling technique is introduce a smooth proximal Lagrangian value function to handle the constrained LL problem. This allows us to smoothly reformulate the original BLO, and develop Hessian-fire gradient-basee based algorithm. In the future would be interested in studying stochastic algorithms for constrained BLOs, leveraging the simplicity of our approach and incorporating techniques such as extrapolation, variance reduction, momentum, and others.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
Authors listed in alphabetical order. This work is supported by National Key & D Program of China (2033YFA1014400), National Natural Science Foundation of China
(12222106, 12326605, 62331014, 12371305). Guangdong Basic and Applied Basic Research Foundation (No. 2022B1515020082 and Shenzhen Science and Technology Program (No.
(CXX20220011411170007))
REFERENCES
Nazanin Abolfazli, Ruichen Jiang, Aryan Mokhtari, and Erfan Yazdandoost Hamedani. inexact conditional gradient method for constrained bilevel optimization. arXiv preprint arXiv:2306.02-22 02449, 2023.
Roberto Andreani, José Mario Martínez, and Benar Fux Svaiter. new sequential optimality condi- tion for constrained optimization and algorithmic consequences. SIAM Journal Optimization, 20(6):3533-3554, 2010.
Michael Arbel and Julien Mairal. Amortized implicit differentiation for stochastic bilevel optimiza- tion. In ICLR, 2022a.
Michael Arbel and Julien Mairal. Non-convex bilevel games with critical point selection maps. In NeurlPS, 2022b.
Hédy Attouch and Roger J-B Wets. A convergence theory for saddle functions. Transactions of the American Mathematical Society, 280(1):1-444 1983.
Heinz H. Bauschke and Patrick L.. Combettes. Convex analysis and monotone operator theory in Hilbert spaces. CMS Books in Mathematics, 10, 2011.
Amir Beck. First-order methods in optimization. SIAM, 2017.
J Frédéric Bonnans and Alexander Shapiro. Springer Science & Business Media, 2013.
Perturbation analysis of optimization problems.
Lesi Chen, Yaohua Ma, and Jingzhao Zhang. Near-optimal fully first-order algorithms for finding stationary points in bilevel optimization. arXiv preprint vrXiv:2306.14853 2023a.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. In NeurlPS, 2021.
Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A single-timescale method for stochastic bilevel optimization. In AISTATS, 2022a.
Xuxing Chen, Krishnakumar Balasubramanian, and Saeed Ghadimi. Stochastic nested composi- tional bi-level optimization for robust feature learning. arXiv preprint arXiv:2307.053884 2023b.
Ziyi Chen, Bhavya Kailkhura, and Yi Zhou. A fast and convergent proximal algorithm for regular- ized nonconvex and nonsmooth bi-level optimization. arXiv preprint arXiv:2203.16615 2022b.
Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. In NewrlPS, 2022.
Stephan Dempe and Alain B Zemkoho. The bilevel programming problem: reformulations, con- straint qualifications and optimality conditions. Mathematical Programming, 133:447-473, 2013.
Dheeru Dua, Casey Graff, et al. UCI machine learning repository. URL https:/aachiiv..es....i. 2017.
Thomas Elsken, Benedikt Staffler, Jan Hendrik Metzen, and Frank Hutter. Meta-learning of neural architectures for few-shot learning. In CVPR, 2020.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta- learning approach. arxiv preprint arXiv:2002.07945 2020.
10

---

Published as a conference paper at ICLR 2024
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient- hyperparameter optimization. In JCML,L 2017.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In ICML, 2018.
Lucy L Gao, Jane J. Ye, Haian Yin, Shangzhi Zeng, and Jin Zhang. Value function based difference- of-convex algorithm bilevel hyperparameter selection problems. In ICML, 2022.
Lucy L Gao, Jane J. Ye, Haian Yin, Shangzhi Zeng, and Jin Zhang. Moreau envelope based difference-of- wwwwoof-lww-oomommmmae convex reformulation and algorithm for bilevel programs. arXiv preprint 11711 2023.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246. 2018.
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration com- plexity of hypergradient computation. In ICML, 2020.
Isabelle Guyon, Steve Gunn, Asa Ben-Hur, and Gideon Dror. Result analysis of the NIPS 2003
feature selection challenge. In NeurlPS, 2004.
Elias S Helou, Sandra A Santos, and Lucas EA Simões. A primal nonsmooth reformulation for bilevel optimization problems. Mathematical Programming, 198(2):131-11099 2023.
Tin Kam Ho and Eugene M. Kleinberg. Building projectable classifiers of arbitrary complexity. ICPR, 1996.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application actor-critic. SIAM Journal on Opti- mization, 33(1):147-180, 2023.
Feihu Huang. On momentum-based gradient methods for bilevel optimization with nonconvex lower-level. arXiv preprint arXiv:2.03303944 2023.
Feihu Huang, Junyi Li, Shangqian Gao, and Heng Huang. Enhanced bilevel optimization via breg- man distance. In NeurIPS, 2022.
Kaiyi Ji, Jason D. Lee, Yingbin Liang, and H. Vincent Poor. Convergence of meta-learning with task-specific adaptation over partial parameters. In NeurIPS, 2020.
Kaiyi Ji. Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In ICML, 2021.
Kaiyi Ji, Mingrui Liu, Yingbin Liang, and Lei Ying. Will bilevel optimizers benefit from loops. In NeurIPS, 2022.
Prashant Khanduri, Ioannis Tsaknakis, Yihua Zhang. Jia Liu, Sijia Liu, Jiawei Zhang, and Mingyi Hong. Linearly constrained bilevel optimization: A smoothed implicit gradient approach. In ICML., 2023.
Youngdae Kim, Sven Leyffer, and Todd Munson. MPEC methods for bilevel optimization problems. In Bilevel Optimization, pp. 335-360. Springer, 2020.
Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, and Christos Thrampoulidis. Label- imbalanced and group-sensitive classification under overparamcterizatton. In NewrIPS, 2021.
Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. A fully first-order method for stochastic bilevel optimization. In ICMI. 2023a.
Jeongyeol Kwon, Dohyun Kwon, Steve Wright, and Robert Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. arXiv preprint 23900:330 2023b.
11

---

Published as a conference paper at ICLR 2024
Junyi Li, Bin Gu, and Heng Huang. Improved bilevel model: Fast and optimal algorithm with theoretical guarantee. arXiv preprint arXiv:2009.00690, 2020.
Mingchen Li, Xuechen Zhang, Christos Thrampoulidis, Jiasi Chen, and Samet Oymak. Autobal- ance: Optimized loss functions for imbalanced data. In NeurlPS, 2021.
Yu-Wei Li, Gui-Hua Lin, and Xide Zhu. Solving bilevel programs based on lower-level Mond-Weir
duality, INFORMS Journal on Computing, 2024.
Yuwei Li, Gui-Hua Lin, Jin Zhang, and Xide Zhu. novel approach for bilevel programs based on Wolfe duality. arXiv preprint urXiv:2332.06833 2023,
Hanwen Liang, Shifeng Zhang, Jiacheng Sun, Xingqiu He, Weiran Huang, Kechen Zhuang, and Zhenguo Li. DARTS+: Improved differentiable architecture search with early stopping. arXiv 2019.
preprint arXiv:I909.000
Gui-Hua Lin, Mengwei Xu, and Jane Ye. On solving simple bilevel programs with nonconvex lower level program. Mathematical Programming. 144(1-2):277-305, 2014.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In ICLR, 2018
Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order algo- rithmic framework for bi-level programming beyond lower-level singleton. In ICML, 2020.
Risheng Liu, Jiaxin Gao, Jin Zhang. Deyu Meng, and Zhouchen Lin. Investigating bi-level optimiza- tion for learning and vision from unified perspective: A survey and beyond. IEEE Transactions on Puttern Analysis and Machine Intelligence, 44(12):0045-10067, 2021a.
Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A value-function-basel interior-point method for non-convex bi-level optimization. In ICML, 2021b.
Risheng Liu, Yaohua Liu, Shangzhi Zeng, and Jin Zhang. Towards gradient- bilevel optimiza- tion with non-convex followers and beyond. In NeurIPS, 2021c
Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A general descent aggrega- tion framework for gradient-based bi-level optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):38-57, 2022.
Risheng Liu, Xuan Liu, Shangzhi Zeng, Jin Zhang, and Yixuan Zhang. Value-function-bar se- quential minimization for bi-level optimization. IEEE Transactions on Pattern Analysis and Ma- chine Intelligence, 2023a.
Risheng Liu, Yaohua Liu, Wei Yao, Shangzhi Zeng, and Jin Zhang. Averaged method of multipliers for bi-level optimization without lower-level strong convexity. In ICML,, 2023b.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In AISTATS, 2020.
Songtao Lu. SLM: A smoothed first-order lagrangian method for structured constrained nonconvex optimization. In NeurlPS, 2024.
Zhaosong Lu and Sanyou Mei. First-order penalty methods for bilevel optimization. arXiv preprint arXiv:2301.01716. 2023.
Zhi-Quan Luo, Jong-Shi Pang, and Daniel Ralph. Mathematical programs with equilibrium con- straints. Cambridge University Press, 1996.
Matthew Mackay, Paul Vicol, Jonathan Lorraine, David Duvenaud, and Roger Grosse. Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. In ICIR, 2019.
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-based hyperparameter optimiza- tion through reversible learning. In ICMI. 2015.
12

---

Published as a conference paper at ICLR 2024
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
Aurélien Ouattara and Anil Aswani. Duality approach to bilevel programs with convex lower level. In 2018 Annual American Control Conference (ACC), pp. 1388 1395. IEEE, 2018.
Jifí Outrata. On the numerical solution of a class of Stackelberg problems. Zeitschrift für Opera- tions Research, 34(4))255-277, 1990.
Fabian Pedregosa.
Hyperparameter optimization with approximate gradient. In ICML, 2016.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-lcarning with im- plicit gradients. In NeurIPS, 2019.
Tyrrell Rockafellar. Conjugate duality and optimization. SIAM, 1974.
R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back kack-propagation for bilevel optimization. In AISTATS, 2019.
Han Shen and Tianyi Chen. On penalty-based bilevel gradient descent method. JCML, 2023.
Daouda Sow, Kaiyi Ji, Ziwei Guan, and Yingbin Liang. A primal-dual approach to bilevel optimiza- tion with multiple inner minima. arXiv preprint 22Xx::2203301123 2022.
Davoud Atace Tarzanagh, Mingchen Li, Christos Thrampoulidis, and Samet Oymak. Fednest: Fed- erated bilevel, minimax, and compositional optimization. In ICML., 2022.
loannis Tsaknakis, Prashant Khanduri, and Mingyi Hong. An implicit gradient-type method for linearly constrained bilevel problems. In ICASSP, 2022.
Ioannis Tsaknakis, Prashant Khanduri, and Mingyi Hong. An implicit gradient method for strained bilevel problems using barrier approximation. In ICASSP, 2023.
Eric Wong, Leslie Rice, and Zico Kolter. Fast is better than free: Revisiting adversarial training. In ICLR, 2019.
Quan Xiao, Songtao Lu, and Tianyi Chen. An alternating optimization method for bilevel problems under the Lojasi-wojsiiwiizz condition. NeurIPS, 36, 2023a.
Quan Xiao, Han Shen, Wotao Yin, and Tianyi Chen. Altemating projected sgd for equality- constrained bilevel optimization. In ICAIS, 2023b.
Siyuan Xu and Minghui Zhu, Efficient gradient approximation method for constrained bilevel opti- mization. In AAAI, 2023.
Haikuo Yang. Luo Luo, Chris Junchi Li. Michael Jordan, and Maryam Fazel. Accelerating inexact hypergradient descent for bilevel optimization. In OPT 2023: Optimization for Machine Learn- ing, 2023a.
Yifan Yang, Peiyao Xiao, and Kaiyi Ji. SimFBO: Towards simple, flexible and communication- efficient federated bilevel learning. NeurlPS, 36, 2023b.
Jane J. Ye and Daoli Zhu. Optimality conditions for bilevel programming problems. Optimization, 33(1):9-27, 1995.
Jane J. Ye, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. Differrncc of convex algorithms for bilevel programs with applications in hyperparameter selection. Mathematical Programming, 198-2)11533-1666 2023.
Mao Ye, Bo Liu, Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: A simple first-order approach. In NewrIPS, 2022.
13

---

Published as a conference paper at ICLR 2024
Yihua Zhang, Guanhua Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, and Sijia Liu. Re- visiting and advancing fast adversarial training through the lens of bi-level optimization. In ICML, 2022.
Yihua Zhang. Prashant Khanduri, Ioannis Tsaknakis, Yuguang Yao, Mingyi Hong, and Sijia Liu. An introduction to bi-level optimization: Foundations and applications in signal processing and machine learning. arXiv preprint arXiv:2308.0077 307880088, 2023.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In ICLR, 2019.
A APPENDIX
The appendix is organized follows:
The experimental details is provided in Section A.1
Expanded related work is provided in Section A.2
The equivalent results of the reformulated problem 4 are provided in Section A.3
Some useful auxiliary lemmas are provided in Section A.4
The proof of Lemma 3.1 is given Section A.5
The proof of Proposition 3.1 provided in Section A.6
A.1 EXPERIMENTAL DETAILS
In this section, we outline the specific experimental settings. All experiments were conducted using Python 3.8 a computer with Intel(R) Xeon(R) Gold 5218R CPU @ 2.10GHz CPU and an NVIDIA A100 GPU with 40GB memory GPU.
A.1.1 SYNTIETIC EXPERIMENTS
LL merely convex:
Hyper-parameter settings for algorithms.
IV-HBA: In Figure D the step sizes are chosen as a
0.005, B 0.002, 7 = 0.03, 7 = 7/2 the step sizes are chosen as a 0.002, with various p.
10, r0 with parameter = (A: 1 In Figure
0.002, = 0.03, 71 = 72 0.1, = 1, c = (k +
E-AiPOD: Projection probability is p 0.3, total iterations are K 300/p. UL iterations are = 2, and LL iterations are S 5. Figure [ the step sizes are set as a 0.0001, = 0.001. In both AiPOD and E-AiPOD, the parameter 7 is set to 2, this choice has been demonstrated to yield best performance, as shown in (Xiao et al. 2023b Figure 1).
LL strongly convex Case:
The strongly convex instance is adapted from Xiao et al. (2023b) by omitting the Gaussian noise.
Hyper settings for algorithms. For LV-HBA, the step sizes are chosen
0.02. 0.001, 7 = 0.1, 71 = 72 = 1, 1000 with parameter C = (k + 1)0.3 For both AiPOD and E-AiPOD, the hyper-parameter
set consistent with the code in Xiao et al. (2023b). Specifically, the projection probability p = 0.3, the number UL iterations in is 7 2, the number of LL iterations is S 5, and the step sizes are
0.001, B 0.02.
Sensitivity of parameters:
Additionally, to assess the sensitivity of the remaining parameters, further numerical experiments were conducted on LL merely convex synthetic model. We record the time when ||a -00 [1|[x=]] 10-2 is met by the iterates generated by LV-HBA. The results follows:
14

---

Published as a conference paper at ICLR 2024
Parameters
Sensitivity
Ct
8
= 71
722
(ime(s)
0.001
0.02
0.01
10
0.025
0.3
1000
0.23
a
0.005
0.02
0.01
10
0.025
0.3
1000
0.064
0.01
0.02
0.01
10
0.025
0.3
1000
0.052
0.005
0.005
0.01
10
0.025
0.3
1000
0.068
B
0.005
0.02
0.01
10
0.025
0.3
1000
0.064
0.005
0.1
0.01
10
0.025
0.3
1000
0.063
0.005
0.02
0.005
10
0.025
1000
0.098
7
0.005
0.02
0.01
10
0.025
0.3
1000
0.064
0.005
0.02
0.05
10
0.025
0.3
1000
0.025
0.005
0.02
0.01
5
0.025
0.3
1000
0.069
71
=
0.005
0.02
0.01
10
0.025
0.3
1000
0.064
0.005
0.02
0.01
500
0.005
0.3
T000
0.064
0.005
0.02
0.01
10
0.005
0.3
1000
0.026
C
0.005
0.02
0.01
10
0.05
1000
0.064
0.005
0.02
0.01
10
0.025
0.3
1000
0.086
0.005
0.02
0.01
10
0.025
0.3
200
0.066
0.005
0.02
0.01
10
0.025
0.3
1000
0.064
0.005
0.02
0.01
10
0.025
0.3
2000
0.065
A.1.2 HYPERPAMETER OPTIMIZATION
The hyperparameter optimization SVM and the data hyper-cleaning experiments were performed using qpth version 0.0.11 1 and evxpy version 1.2.0.
Hyperparameter Optimization SVM We test the performance of our algorithm LV-HBA in comparison GAM proposed in Xu & Zhu (2023) on the same hyperparameter optimization prob- lem of SVM as considered in Xu & Zhu (2023). Experiments are conducted using datasets dia- betes from Dua al. (2017). and fourclass from Ho & Kleinberg (1996). For dataset diabetes, randomly partition into training, validation, and testing subsets containing 500, 150, and 118 ex- amples, respectively. Similarly, dataset fourclass is partitioned into training, validation, and testing subsets with 500, 150, and 212 examples, respectively. We conduct experiments on each dataset with 40 repetitions.
The hyperparameter optimization of SVM can be expressed as:
min (c) LD... (w" (w".b").
where the hyperparameter to be optimized is [c],... "al....,Cll CNl and w", 6t are solution to the SVM optimization problem given by
1 N | +
(w",b", 00)"")) = arg min w.b.E
Σ c
2 i=1
s.t. 4 (w (z:) + +) 2 E,, i= 1,2,
Here, Dvai represents the validation data, and Djr the training data. For all 1 < i S N, 2; denotes the data point, is the label, and (2,,4) E Drr The upper-level objective function is:
CD. (w*,b')~ [Dval
1
Σ (s.))
(w",,b" 22;
where (ww", Deal) is given by
-l u0* + +b)
C (ww" ",,",,),,11) =a
15

---

Published as a conference paper at ICLR 2024
with (xx) --e T+e The term 1(= +b) signifies the signed distance between point and the |
decision plane z w² + = O. is positive when predictions are accurate, and negative otherwise. Thus, CD., (w*, b*) serves
differentiable surrogate for validation accuracy.
Hyper-parameter settings for algorithms. For LV-HBA, the step sizes are chosen as a = 0.01, 8 0.1, 17 = 0.01, 71 = 72 = 10, 100 with parameter C₁ = (k + 1)0.3. For GAM, hyperparameters are set in alignment with the code in Xu & Zhu (2023) = 0.3, Eg = 0.3, 5 = 0.5. In GAM's
implementation, to uphold the LL strong convexity assumption, the LL problem' objective function is set as 2 |0ll 2 2 e + 2db² where y is a small positive number.
Data Hyper-Cleaning We adopt the data hyper- cleaning formulation as the hyperparameter opti- mization of SVM, as presented in Xu & Zhu (2023). In this model, post-optimization of hyperpa- rameter c, the penalty term corresponding to the corrupted data (2 Mt) approaches O. Consequently, the corrupted data (z,. yi) is identified and has a negligible impact on the training and prediction of the classifier model. Experiments
conducted using the datasets gisette from [uuynn et al.) (2004). For dataset gisette, we segment it into training, validation, and testing subsets, comprising 400, 180, and 5420 examples, respectively. We conduct experiments on each dataset with 40 repetitions.
Blype--paramete settings for algorithms. For LV-HBA, we select step sizes with values a 0.01, = 0.1, and 1) = 0.01, accompanied by parameter C₁ (k + 1)0.3 For GAM, hyperparameters are consistent with specifications in Xu & Zhu (202)). with = 0.3, 6o 0.3, and / = 0.5.
A.1.3 FEDERATED Loss FUNCTION TUNING
In this part, we test our LV-HBA compared E-AiPOD Xiao al. (2023b) and FedNest Tarzanagh et al. (2022) on the same federated loss function tuning problem, as explored in Xiao et al. (0023)). The experiments were executed with opencv-python version 4.6.0.66. In the federated loss function tuning problem, the UL optimizes loss-tuning parameters to enhance both generalization and fair- ness. Meanwhile, the LL focuses on training model parameters on potentially imbalanced datasets. The formal problem statement is:
min 2 ZEX
dup (y (I); Dia)) Dm)
M
s.t. y (²)x)= arg min Σ m=1
flow (z, ym: D(t).
yEy M
where M 50 representing the number of clients,
the loss-tuning parameter and y indicates the neural network parameters. DDr and Dm are the training and validation sets of client m. The consensus sets and y are given by = (x x = xM } and y == {y 9/1 =.... y/r } respectively. Training datasets {Dir J m=1 have class imbalances. As introduced by Kini et al. 2202)) the vector-scaling loss flow is
1 D
exp exp ly, (1r dr)) + Tr.) Ee exp (6 (yr dn) + Te)
flo (x, y. D) =
Wi, log
dn ED
where N signifies dataset size, C denotes the class count, and dn is the n-th data item with label In in dataset D. The logit output of the neural network for parameters y and input d, is h (y; dz)) = [h (y; .dn).... ...., hC (y; d E RC, æ is defined as (w. 8, r) with w == [wi...., we] E C and r defined and w is static class weight for the validation dataset.
similar manner. The upper-level loss pup is a variant of flou where 8 = 1, 0.
Hyper-paramedt settings for algorithms. For LV-HBA, we select step sizes with values a 0.01, = 0.01, and 17 0.01, 71 72 = 10, r 100, parameter Cı = (k: + 11).33 and bath size as 256. For E-AiPOD and FedNest, hyperparameters align with specifications in Xiao et al. (2023b): E-AiPOD has communication probability p 0.3, S 20, 0.01, 3 0.04, N' = 3, and batch size of 256. FedNest utilizes LL iteration number r = 3, episode = 3, resulting in a communication frequency of 0.3 per LLI iteration.
16

---

Published as a conference paper at ICLR 2024
A.2 EXPANDED RELATED WORK
In this section, we provide an extensive review of recent studies closely related to our work.
Approaches for BLO. One of the most commonly employed approaches for tackling BLO prob- lems is to reformulate them as single-level problems. This can often be accomplished in two ways Dempe & Zemkoho 2013). One of these approaches, known as the KKT (or MPEC) reformula- tion, replaces the LL. problem with its Karush-Kuhn-A the original variables as well as multipliers if the LL constraints exist. The resulting problem is constraints (MPCC/MPEC) Luo et al. (199),, which itself poses a significant challenge when treated nonlinear program- ming problem Kim et al. (2020). Remarkably, the KKT reformulation employs the KKT conditions, thereby unavoidably relying on first-order gradient information. Consequently, gradient-baad baaseddt-baddddddee algo- rithms based on KKT reformulation also depend on second-order gradient information.
(KKT) conditions and minimizes over
the so-called mathematical program with complementaaityyequliibbn
Another often used approach is the value function approach, originally proposed in Outrata (1990) and Ye & Zhu (1995). It is obtained by replacing the LL problem by its description via the (optimal) value function. Unlike the KKT reformulation, the value function reformation does not use any gradient information of the objective and constraint functions in the LLL problem. To the best of our knowledge, the majority of existing Hessian-free (also referred to as fully first-order) gradient-based algorithms for both unconstrained and constrained BLOs, are developed based on the value function reformulation, see, e.g.. Liu et al. (2021b 2023a): Ye et al. (022);; Sow et al. (2022); ;; Shen & Chen 2023); Kwon (2023a) Lu & Mei (2023). It should be noted, however, that the value function is typically nonsmooth, even when the functions involved are linear and affine. Hence, the value function reformulation often leads to nonsmooth problem. To alleviate the nonsmooth issue, the recent works Ye et al. (2023); Gao et al. (2022) develop difference of convex algorithms for solving BLO problems in which the UL objective is a difference of convex function and the LL problem is fully convex.
Recently, to weaken the underlying assumption from lower level full convexity weak convexity, Gao et al. (2023) proposes new reformulation of BLOs, using Moreau envelope of the LL problem. They also demonstrate the equivalence between the reformulated and the original BLO problems in the convex setting. Other approaches for BLOs include implicit methods Franceschi et al. (2017); Ghadimi & Wang] (2018); (Shaaan et al.] (2019). penalty methods [Lnn et al. (2014), duality- based
solution approach Ouattara & Aswani 2018): Li et al. (2033 2024
Unconstrained BL. The LLI strong convexity in unconstrained BLO significantly contributes to the development of efficient BLO algorithms, see, e.g.. Maclaurin et al.
(2015): Franceschi et al. 2017): Shaban et al.] )2019); Mackay et al. (2019) Grazzi et al. (2020); Ji et al. (2021) 2022) for the iterative differentiation (ITD) based approach; Pedregosal (2016 6); Ghadimi & Wang (2018); Ra-
jeswaran et al. (2019); Lorraine et al. : Hong et al. (2023); Chen et al. (2021). Arbel & Mairal (202aa); Dagréou et al. (2022): Ye et al. (2022); Yang et al. (2023a) for the approximate implicit differentiation (AID) based approach. Recently, based on the value function-based reformulation, Kwon al. (2023a) developed stochastic and deterministic fully first-order BLO algorithms and established their non-asympiotic convergence guarantees, while an improved convergence analysis provided in the recent work Chen al. (2023a).
Convex LL problems introduce additional challenges, such as the presence of multiple LL solu- tions (Non-Singleton), which can impede the utilization of implicit-based approaches developed for nonconvex--ttronlyy-comm
BLO. To tackle Non-Singleton, recent advances include: aggregation methods (or called sequential averaging methods) in Liu et al. (2020); Li et al. (2020): Liu et al.
(022) with asymptotic convergence guarantees; in [iu et al. (2023b) with convergence rate anal- ysis; value function-basee
difference-of-conneex algorithm in Ye et al. (2023); Gao et al. (2022);
primal-dual algorithms in Sow et al. (2022); min-max optimization reformulation-based first-order penalty methods Lu & Mei (202)).
Efficient methods for nonconvex-noncomee BLO remain under-explored, recent advances in- clude: initialization auxiliary and pessimistic trajectory truncation method in Liu et al. (2021c); value function-based interior-point method in Liu al. (2021b); possibly degenerate implicit differentiation based unrolled optimization algorithms in Arbel & Mairal (2022b); momentum- based algorithm in Huang (2023); generalized alternating method in Xiao al. (2023a): fully first-
17

---

Published as a conference paper at ICLR 2024
order value function- based algorithm in Ye et al. (2022); penalty- based fully first-order algorithm in Shen & Chen (2023): ; a smoothed first-order Lagrangian method in Lu (2024).
Constrained BLO. While baased algorithms for unconstrained BLO problems have been extensively explored, the investigation of efficient methods for constrained BLO problems is rela- tively limited, especially when addressing LL constraints coupling both UL and LL variables.
Recently, driven by applications in machine learning, the recent works such as Tsaknakis et al. (002); Khanduri et al. (2023) study the constrained BLOs, where the LL problem involves the minimization of a strongly convex objective over set of linear inequality constraints; Xiao et al.) (023a) investigates the stochastic BI.O problems with possibly coupled equality constraints in both upper and lower levels; Xu & Zhu (2023) considers BLOs in which the LL problem is convex with general equality and inequality constraints, while assuming that the LL objective is strongly convex and the constraints satisfy strict Linear Independence Constraint Qualification (LICQ): Tsaknakiss al. (2023) develop a novel parrier-based gradient approximation algorithm that transforms the general constrained BLO problem to problem with only linear equality constraints. Observe that all of these works employ implicit gradient- based methods, relying on the computation the implicit gradient of the unique LL solution mapping. Among them, Khanduri et al. (2023) develops linear perturbation- -assed smoothing framework for the linearly constrained LL problem that ensures the existence of the implicit gradient in an almost sure sense. Notably, these implicit gradient- based methods for constrained BLOSs unavoidably rely on computationally intensive calculations related to the Hessian matrix.
The value function-based methods can avoid recurrent calculations related to the Hessian matrix, see, e.g.. Liu et al. (2023)); Lu & Mei (2023). Both papers have considered BLOs with general constraints in the LL problem. For constrained BLOs, value function-based methods face challenges related to non-differentiable constraints, stemming from the value function- lunetion-based reformulation. To address the nonsmooth issue. Liu et al. (2023a) proposes a sequential minimization algorithmic framework, by adding a quadratic regularization and penalty/barrier functions of the LL inequality constraints to the LL objective; Lu & Mei (2023) develops first-order penalty methods by solving sequence of minimax problems or a single minimax problem. Recent advances include primal-dual algorithms in (Sow et al. (2022); ; primal nonsmooth reformulation-basse algorithm in Helou et al. 2003); penalty-based first-order algorithms in Kwon et al. (2023b).
There is also a line of works devoted to tackle the constrained UL setting including: implicit approximation methods in Ghadimi & Wang (2018); a two-timescale framework in Hong et al. (2023;; single-timescale method in Chen et al. (2022a); initialization auxiliary method in Liu et al. 2021c); Bregman distance-based method in Huang et al. 2022); value function-basee Difference- of-Convex algorithm in Gao et al. (2022); proximal gradient-type algorithm in Chen et al. (2022b) saaalty-based method in [Shen & Chen (2023); Moreau Envelope-based Difference-of weakly ly-
Convex method in Gao et al. (2023); inexact conditional gradient method in Abolfazli et al. 2023
nested compositional BLO in Chen et al. (023b)).
A.3 EQUIVALENT RESULTS OF REFORMULATED PROBLEM
In the following result, we demonstrate that the reformulation problem (4) is equivalent to the BLO problem (I).
Recall that for the sake of notational simplicity, throughout this paper, for LL constraint mapping g: x Y + Rt and any vectors X, 2 E IR, we represent El= Xgg; and El= 2i9i as Ag and zg. respectively. Similarly, El= A V ugg and E 2, V v,g, are denoted by AV yg and 2V yg. respec- tively.
For the reader's convenience, we restate the reformulation problem 4 follows:
min EC,2)
F(x,y) v) s.t. f(x, v) - Uy (x, y, x) 50. O,
where := ((x, y) X x Y ()) 0}, and ( v. is the proximal Lagrangian value function, restated below,
Uyy (x,,,), == min max #EY XER { ((x,0)) - -0601, 0) +
1 10 - vl
1 11 x1|2
2%1
272
18

---

Published as a conference paper at ICLR 2024
The proximal Lagrangian value function (2, defined in equation (3) can be regarded as the (upper) Yosida approximate of the Lagrangian function [(z, y, X) == f(z y) + >g(z, y) the LL problem (Attouch & Wets 1983 Section 5).
Theorem A.1. Assume that fzz--) and g( -) are both convex on Y. Suppose 7/, '22 > 0, the refor- mulated problem (4) is equivalent to the BLO problem (2), if multiplier of the lower-level problem
2 exists for any feasible point (z, y) of the BLO problem L
Proof. First, let (I, y, 2) be any feasible point of problem (4. then have (I, X X 0. and g(., y) S 0. Furthermore, the following inequalities hold,
[(,,0) S (,( = min max DEY A20 [(x, 0) + >g(g, 0) +
100 y1
- 1| =|1?
1
2
27/
1 - 100 y11
S min max f(x,0) 0) + >g(z, 0) + A20
2
(17)
< min { [(x, 0) + 1 DEY
u11 g( 0) s o}
[(x,0)
271
I f(x y).
Since the first and the last terms in the above inequalities are the same, we must have equalities throughout. Specially, we have
1 100 vl1 g( 0) =0) 2/11
y E argmin dEY
[(x, 0) +
Because fIx,-) and g(z.-) -) are both convex functions on Y, considering g(z, -) < 0 as an abstract convex set constraint and using the first-order optimality conditions, we obtain that
y E argmingey (f(rr, 0) g 0) 5)
and thus y S(z). Then the point (z, is feasible to the BLO problem
Conversely, suppose that (z, y) is an feasible point the BLO problem (T. then we have (I. y) e X Y and S(z). On one hand, according to the assumption that multiplier 2 0 of the LL problem (2) exists at (x, y), since the I.I problem is convex, by the first-order optimality conditions, get
y argmingey 0) + æg(æ, 0)}. Once more, due to the convexity of the LL problem, this implies that
1 110 y/1
y argmingey f(z,0) 6) + zg(x, 0)
2%11
On the other hand, since g(x, y) < 0, by the complementarity conditions, i.e., 2g(x, v) 0,
2/22 _ =112
argmaxx20 f(x,8) + Ag(2, v)
Hence, the point (y. 2) is a saddle point of the following strong convex strong concave function L: Y x R. R:
1
L(O, == f(x, 0) + Ag(x, +
110
112
||
2 2112.
2711
272
Thus it follows from saddle point theorem that
min max f(z, 0) + \g(2, 0) + BEY A20
1|0
vll
| - 2112 27/2
2n1
= f(x v) + =9(0, y) f(x,
where the last inequality uses the complementarity conditions 2g(x; v/) ny (2, y, 2) f(r y) and then (x, y. z) is feasible to the reformulation problem 44
0.
Therefore,
19

---

Published as a conference paper at ICLR 2024
Remark A.1. Indeed, per the estimate provided in ( the proximal Lagrangian value function By (x. y. 2) establishes a lower bound for f(x, y). that is, v y, 2) S f(x, y) for any (x, y. 2) E
C' x R4, Specifically, we have
(z, 2) & min DEY f(x,0) 0) + - 1 []xz (00200)=00=00 uy, (2,1),
1
(18)
2
where Us, (z. y) coincides with the so-called Moreau envelope function, initially introduced by Gao et al. (2023) for BLO problems. Additionally, the latter also acts as lower bound for the function (x, V).
Subsequently, we demonstrate that for a sufficiently large r. the solution to the reformulation can be obtained by solving variant ( Note that Projz in Algorithm
[ is simple Euclidean projection
on a box Z == [0. r| with lower bounds and upper bounds r 2 0. This projection is pivotal in guaranteeing the boundedness of the auxiliary variable =k+1, For clarity, we restate the variant (6)
of the reformulation 4 as follows:
min (a.))eXXY
F(x, y) s.t. f(x. (1, y. S O, g y) S 00,
(6
where By (z. y, 2) is truncated proximal Lagrangian value function, defined in equation (5)
[xx 0) + Ag(a, 0) + 2n1 110 y/1² _110
1 ||
(2, == min max BEY XEZ
=||2
272
Theorem A.2. Suppose "/1, 72 > O, let an optimal solution (x",y", x²) ) of reformulation 4 exist
such that zt is within the set Z. Then (x" ,y" x²)) is also optimal solution for the reformulation oo. Consequently, the optimal values for both reformulations, and (6), are identical. Moreover, any optimal solution of (6 is optimal reformulation
Proof. Firstly, according to the definitions of U. and Uyy. we have that (z, V, 2 Uy (Z, 2)
for any (ar, y. 2) E X Y Z. Therefore, any feasible point (ar, y, 2) of problem (6) also feasible
to problem and thus the optimal value of problem (6) is larger or equal to that of problem (4)
Conversely, let (x" .y"",""" ","" "²") >²*) be an optimal solution of the reformulation problem (4) with 2 belong- ing to the set Z, since (xx", ,."", =") is feasible to problem (4). As shown in the proof of Theorem A.1
)")
we obtain y" E S(x=).. Next we show that =" is multiplier of the LL problem ( (x", y/" To this end, it suffices to prove that
(y" +²* argmin argmax [(x" ,0)+ + Ag(="",, 2n1
(0(=*00)+
110 y²122
1
1| 2=123 2*12] (19)
DEY
X20
272
By estimates in 17
we get
1
8¹ Eargmin max
f(x",00 >g(x=",))
|0 y²1l
yEY A20
2y1
1
y" aargmin max X20
f(x",0) >g(x",00 0)
+
00 y 112
1| 2=1l²
112
OEY
2r1
2%22
Furthermore, the optimal values of the above optimization problems are equal. This implies that 2" "(""", ,y") = O, and then
E argmaxx2o ((o""'") + >g(=", - _11 - 2- =-1p
272
Now since =² E Z, we have
1
1
(w","") = argmin argmax [(x",0) + >g(x0, 0) + DEY
10 - 101
1 - z 201
XEZ
2?1
27/2
leading to v. (x"", y", 2") (x" (,","="=""00"" 2² and thus (x" y² 2*) } is also feasible to problem (6) Therefore, the optimal value of problem (6) is equal to that of problem (4) Then, because any
feasible point (a, y, 2) of problem (6) is feasible problem (4. get the conclusion.
20

---

Published as a conference paper at ICLR 2024
A.4 AUXILIARY LEMMAS
The following lemma provides a characterization of the gradient of the Lagrangian based proximal value function Uy v)
Given that f is --moooot on x Y, by leveraging the descent lemma (Beck 2017 Lemma 5.7), can be deduced that f is also L wy-wllkly convex, i., f(x, y) + L 51(((,, // is convex on X x Y. Consequently, under Assumption 3.2 is Py-weakly convex on X Y. with P1 0 potentially being smaller than Ly. To precisely determine the range for the step sizes of LV-HBA, we will employ the weak convexity constant of f. Py. in subsequent results.
Lemma A.I. Under Assumptions 3.2 and 3.3 le E (0, 1/ps) and 72 > O. Then Uy (Z, V, is continuously differentiable on X x Y x IR, and for any (x, y, z) E X x Y x R'
VU 2) V f 0*) + x' 0²), yy 8* (X* 2)
(20)
71
72
where H" 8 (z. 2, and X² == X² (x, y. 2) the unique saddle point of the min-max problem:
1 -11 ul2
- 21?
1
f(z 0) + >g( 0) min max ØEY XE
(21)
271
272
Furthermore, for any P. Ps/ p3/ Uyr v, 2) is pu-weakly convex with respect variables y) on X x Y for any fixed R
Proof. Firstly, we define an auxiliary function,
(x,002) == max AEZ
[(x,0) + Ag(x,
1 --111 112
=112/
272
Noticed that s (x. 02 2) can be rewritten as
9 (x, = inf { X
>g(x, 0) -)
1 21|
2n2
By Assumptions 3.2 and 3.3 f and are both continuous differentiable
open set containing X x Y, it can be easily shown that - fxx 0) Ag 0) 2T2 a - =1|² satisfies the compeattsss
condition in (Bonnans & Shapiro 2013 Theorem 4.13) on any point (#. 0) E X X RR, that
is, for any (i, 0, 2) E X x Y x R. there exist e E R. compact set D and neighborhood W of
(r,0,3 2) such that the level set {A Z f(x 0) >g(z, 0) + 1 - 21I < c} is nonempty and
1 2||3 contained in D for any (z, 0, 2) E W. Because arg max {f(z, 0) + Ag(2, 0) マック
unique for any (z, 0, 2) E X Y R', we denote by '1 2). Then, by Assumptions 3.2 and
3.3 we can derive from (Bonnans & Shapiro 2013 Theorem 4.13, Remark 4. 4.14) that (xr, 0, z) is
differentiable at any point on X x Y x R², and for any (a,, 0, E X x Y x R
[z, 2) fz 0) (z, (z) (a X 0 2)22))
(22)
By simple calculation, we can obtain that
X 0) == arg max [(x, 0) + >g(x,, 0) X
1 1| =1p = Projz (= + (2. 0))
2
Since by Assumptions 3.2 and 3.3 that f and g are both continuous differentiable on an open set
containing X x Y, and Projz is continuous, hence Vip, (x, 0, 2)) is continuous on x Y R!.
Secondly, with the introduced auxiliary function (py, we can rewrite Ugrr as
Uy (x. y, min SEY
ey (z, 0, +
100 vl
(23)
2
Next we will show that s (z. y, z) is weakly convex with respect to variables (æ, v) on X x Y for any fixed E Re. By Assumptions 3.2 and
3.3 we have that for any X E R4,
f(x,v) + \g(
1
|| 2
212 + PI [x, 1)1
272
2
21

---

Published as a conference paper at ICLR 2024
is convex with respect to variables (z, on X x Y. Then by (Rockafellar 1974 Theorem 1), obtain that
(2, 2)
P [1x w))l= 2
max AEZ
f(1 + )g(z,
1 _ 11 z112 + P 11, 2)
272
is convex with respect to variables (Ir, y) X Y and thus sy (x, y, 2) is py-weakly convex with respect to variables (z, y) on X Y for any fixed
R'. Then, by Assumptions 3.2 and 3.3 it can be easily shown that when Y1 E (0, 1/pr), Py (x,002) 0, + 2% 10 - yl? satisfies the inf- compactness condition on any point (z, 2) X Y x R.. Next, because when 71 (0,
0,, 2 110 y is strongly convex with respect to 0, arg minser (5p, (1r, 0,=) + 2y: 10 ) is unique and it is equal to (z, y, A). By using (Bonnans & Shapiro, 2013 Theorem 4.13, Remark 4.14), the continuous differentiablility of bo established above and equation (22), we can
obtain that Uy v. =) is differentiable at any point on X x Y IR, and for any (2r U; X R
-0) (2,, = (x (x)) (x, 2)/
where 0* denotes 0* (' y/ z).
Finally, noticed that under Assumptions 3.2 and 3.3 when 71 E (0, 1/pr) and 1/2 > 0, the function
f(x 8) + Ag 0)
+ 271
110
all²
2//2 || - -113,
strongly convex and strongly concave with respect to I and X, respectively. Therefore, it follows from saddle point theorem,
min max ØEY XEZ
f(x,0) + >g(I, 0)+ +
_ 100 - vl1
1
1
1|^
=13
2?i
27/2
1
1
max min A DEY
[(xx,)) >g(2, 0) + 2>1
10 yl1
||
x1?
272
leading to
xx
and thus the conclusion follows.
Remark A.2. Using the similar argument as above, the following result holds for the Lugrangian bused proximal value function (3., U, 2) when 7/1 1/9)/ and "/2 >> 0. That is,
(1) The function (z y,2) continuously differentiable on X Y x RR:;
(2) The gradient of Vn (x. y, 2) has closed-form given by
(1, = Vz,(x, 0*) + X X' V 0*), (y 0²) (A* (A*-2)
2)
(24)
m
72
where 8r == 6" (x. (e,,v2) 2) and X" = (xx y. 2) is the unique saddle point of the following min- max problem:
[[x, + +xg(x, 0)+ + 271
1 _110 110 - w112
_ || =112
1
min max DEY X20
(25)
272
(3) Furthermore, for any Pu 2 variables (z, y) on X x Y for any fixed 2 E R
7ps)) By (2x y. 2) is pu-weakly convex with respect to
Lemma A.2. Under the assumption of Lemma A.7 let m E (0. 72 > O, and (z. y, 2) E X x Y x R.. Then for any Pe 2 ps 7P)) and (z, y) in X XxY, Y, the following inequality holds:
(V Wy (3. 8), (x. v) - (a. 7)) + Po [1(x, v) - (z. 2 2
- -y (I, y, 2) S - -y (.. (2.
22

---

Published as a conference paper at ICLR 2024
Proof. The conclusion follows directly from Lemma A.1 that (2, 2) is p. pe-weakly convex with respect to variables (z, y) on X x Y for any fixed R.
Lemma A.3. Under Assumptions 3.2 and 3.3 let n E (0,1/p5), 72 > 0. Then, for any (x, ys z),
('' =)) E X x Rm x R2, the following Lipschitz property holds:
I1(0 y, 2), X (I, 2)) (0 (x', v/ 22), (= 22
Ly + Cz + Lg |1 x'll +1+ rIP l s'll
||
2'11
(26)
PT
72PT
S <Toal (x, - (s', ,// =1))l1=
where Pr == min[1/71 - Ps. 1/22 Cz == max || and Lox = /3 + CzL + bg 1/.1//11//m 1//aa1/////pr
Proof. For succinctness, we denote (x,y. 2) and wo'.y'=' z') by w and w', respectively. Given that (0"(w,, X² (w)) is the saddle point for min-max problem
1 2n1
112 _11- - 110--111-000
min max BEY XE [(2,00 0) + Ag 0)
110 yl1
2n2
it follows from the stationary condition that
0 E V,f ff + X (W) 0r (w)) + (0 (0) -
1000-1)/mm y)/n + NY (w)), + (X*(w) 2)/12 + N (w)).
(27)
0 E
Under Assumptions 3.2 and 3.3 and that 71 E (0, pr) and 72 >> 0, we know that the function
1
f(z, 0) + Az 0) + 2yy ||0 y
|| 2||
2/2
is (1/m sttrongyy convex and 1/12-strongly concave with respect I and A, respectively.
Then, it follows from [Rockafellar & Wets 2009 Theorem 12.17 and Exercise 12.59) that the operator
Tw A) +VV (0- (0-y)/n + -0),))))) (A- 2)/12 + (A))
is PT == min(1177 pf. 1/12 stroongyy monotone. Using Tw (0, A), the inclusion 27 can be rewritten as
0 ( (x)) (wc).
Similarly, since (0 (w'),, X (w") is saddle point for min-max problem
min max DEY XEZ
f(x', 0) + >g 2m
110
112 _1111
21122
272
we have
0 w (0 (Ow'),\(('')))
Next, by the definition of Tw (0, A), we have
(e1, E Tw (0 (w0')) (w))))
with
C1 = V
- (w))
+ X (ww))) (V 00 v او 0² (w(()))) + (y' - -///n,
62 = - g(z, 0 (w'))) + g( 0² (w ))) + (z' - =2//22
Given that (0, is strongyy monotone, we have
(-()1, (0 - (0 (w'), {² (1), - (0')
(28)
For X* (w). we can obtain that
{ |(o,, (w)) (u))) 0g(x, +
X X²(w) = argmax
1 (w) - 21
| 2112
XeZ
271
272
-Projz (z + 729(2, 0* 720((x00(w))) (w()))
23

---

Published as a conference paper at ICLR 2024
Since Z is bounded set, it follows that X" ("ww) Cz, for any X, Y, E Z. According to Assumptions 3.2 and 3.3 and the fact that 8* (w) E Y, we can derive that
1 11v
||alll S T.gl1x x' + Cz T. || x'll + 71
5/11.
and
||ea|| S L.gl - 2'1l + 11= 2'11-
7/2
Thus, it follows from inequality 28 that
((0)(w), X (w)) (0 (w'), (w)')l
1
[2)1 - (lee)l + ||22ll)
pT
Is + Cz + Lig || z'll + nPT PT
11 111l + 72PT
|| 2'11.
which implies the desired result.
Lemma A... Suppose Assumptions of Lemma A.3 holds, and let n (0,1/p5), 12 and
(I. E X Im B.. Then for any R., we have
-Uy (i, 0,2) = - vy (Z, 2) - Un 2) + Tu || - 2|1
2
with Lv, == (72pT + 1)/(12pT)
Proof. By using Lemma A.3 with fixed (Z. 7, E X R. x R., for any 2 E TR! we have
1(00 (I, ;), X (z, T, [), (0" (2. X 5 72PT
|| - E1,
and thus it follows from Lemma A.I that
1 -
| 22 (T, - V (T,
(T, 0. =)]
|^* - (2, - +
72
12PT +
||| E||.
72PT
Then the conclusion follows from
Beck 2017
Lemma 5.7).
Lemma A.5. Under Assumption of Lemma A.3 let 9 (0, (0.)) 72 > 0 and me E (0, PT L3)
with pr == min 1/7 -ps,
1/,1//0 1//23 and LaB == max (T.g + L, Cz 1211 + 1/m, 1,g + 1/72]. then,
the sequence of (x y² 2t 0b )²) generated by Algorithml / satisfies
(0ght xk+1)= (0* , 2², 1.A' (x* v.
(29)
< (1-TTPP) 11:00 )x*) (0 .. ) N (a* ))
Proof. With given (x*, 3 2 E X x Y Z. we denote 0- (x y 2²) and A (a y 2 by 0
and X*, respectively, for conciseness. By Assumptions 3.2 and 3.3 and that 71 E (0, l/pr), 72 0, we know that
fa* 0) Ag(x=
0) +
110
*
||
2012
2m1
27/2
is (1/m -stronyy convex and 1/12--trong concave with respect to 0 and X, respectively. Then, the proximal min-max problem in equation equivalent to finding (0, A) satisfying
0 (A (),
with
A(O, = (0) x N2),
and
B(0, A) = (V, 0) + AV u0(0* 0) (0 ,²) / / - g(00t ,00 (A -21//2)--
24

---

Published as a conference paper at ICLR 2024
And, therefore, 0 E (A+ () ; Because f(x², ,0) >>)(= + 2 10-
27p || 2* ||
(1/71 - P J-strongly convex and 1/72-strongly concave with respect to 0 and X, respectively, follows from (Rockatellar & Wets, 2009. Theorem 12.17 and Exercise 12.59) that the operator B is
Pr == min(1/ 11:11-10 -pr. 1//2/ 1/111///-stonng -strongly monotone on Y Z. And by Assumptions 3.2 and 3.3 we
have that for any (0, (0", X) E Y X
[(O, 2) - B(0", X E V of(" 0) Vuf(a', 8'11 + M vg(x", 8) - X'V VVvg(r (0)1l
- 110 00'1 |1g( -0)-g(²* 01)l +
1 -11- X'Il
71
72
LJ + Ly + 1 110 8'll +
- || XII
1
711
722
|AV ",0=,,,000, 0) X'V VVvg(0* .0]1 + -I''V 100 ,0) X'V N'Vag(e" I'
LB + by + Cz + 1 10-0011+ - 0'l+ Log 11) 112 11- X'I1,
72
where the last inequality follows from the fact that Cz == max,e || and max,ex.0cs YEY V Vug(zz f)ll S Lgg Therefore, we obtain that the operator B is LB := max + Lg + C2L g. + 1/1 Lg + 1/122- L-ipschtt continuous. Then, we can have from (Bauschke & Combettes 2011 Proposition 26.1 (iv)) that (0", (2) (Id++ ( X²)
Id denoting the identity operator. Since (0 ( = (Id + A) ((O) X²) m) 1(00, with
m: (( )²)), Proposition 26.9) that when
as shown in the proof of (Bauschke & Combettes
2011
E (p. (L)B))
m
I|(0+t1, ( (0", X S (1 m0ppm-2-rrr L2)) I(@0 x²) (0", (*)1--
())))/ we can obtain from the above inequality that When 7 E (0, PtpPr/L3 Li),,
(1gh+t,,,+1) (0", x+)I s (1 mxPr) l1(@t, x²) - (1)]-
As previously stated that the update of variables (x,, y, 2) in equation (10) can be interpreted as inexact alternating proximal gradient from (I**, y 2) on aa des (I, y, 2), in which 6a. is defined in equation (13) as
Prg 2))
1 (F(z.v) F) + f(x.v) (x, Ck
Since (I, 2) I uy V (xx v) for all v) E C. by Assumption 3.1 we have &es (3r, 2) 0 for all (x. y, 2) E C x Rd. In the following lemma, demonstrate that the function doa 2) exhibits decreasing property with errors at each iteration.
Lemma A.6. Under Assumptions
3.1 3.2 and 3.3 let 711 E (0. and > 0. Then the sequence of (at,u" )0*)) generated by Algorithm satisfies
Por (41, btt 2211 S dee (a*,, 3 2)
1
Lon
B2LØx
[[xttt1 ((aktt,ytt) - (xx 112
20h
2
7
Lyg
|| - x112
233g
2
(30)
Bk
L
L2
+
|| - x Xarath ,x )1²
g
7/2
+
ag
2(L + Cz 1og
7p ) ||05t1 0 (att y , =11
(x
2
where Top. : Tpp/rk Tog + Pv.
25

---

Published as a conference paper at ICLR 2024
Proof. Given Assumptions 3.1 and 3.2 that VF and Vf are Lg- and L -ipsschhi continuous on X x Y, respectively, and applying (Beck 2017 Lemma 5.7) and Lemma A.2 we obtain
Den (x , ,²,) Den (a", nh 25)
V Ma (x* y² =*), (x+t1 ,(tt) (0t w²))
+ Lo
(31)
([ ) (at v ||?
2
with Lov == Lp/ck + Lg + Pv. Based on the update rule of variable (æ;, y) in equation 10). the convexity of C == (1x,1) v) E x v) I 0f and the property of the projection operator
Proje, we have
(1x4) au d.t) (1 g (x* y²) (aht1, b)) 20. 0.
leading to
((d), dg), (1th-1 (acb-,,/tt ,1(t1) - (at, y²1) 1 - -Illaatt , , - (x )|?
Combining this with inequality 31). we infer that
Dea (2*t1 ,tt, 2x S de (a* 2² - -22 Lon
2 ||(abt1,
(laltt,gatt ggtt) - (2* y11
akk
(32)
+ (V (Vaygen (at " ,²,)===)) (dt=, dty) (stht1 3y n (at 10),)/1)-
It should be noticed that since (ath soh.yy, 24) E XXXXx x Z and (8 ya 26), 22
(0", x²) E Y x Z for all k, it holds that \ E Z and Vagla 00 y
maxaex,0eY (ag 0)l I by for all k. Considering the formula of V VayUy, y, y, 2) derived in Lemma A.2 and the definitions of dh and dt provided in equation (11), we can obtain that
V Ra (at . + (d dt)l
= l/V 8" (x* ,. (0,2"1) 1) + (at 1/ Vog(t ((a 8 (a",, (2,,) 211)
Vzf(a", g X V V g M1+ + I
(x",""" - - 11
"i
$ 2 V ff(aa 0 tt 3² ,,, X V Vegl" (0*x" ".8 2*))
Vaf(o" 1 1 V.g(** ||
(33)
+ 21|A .,* V Vaga** 8 ( v. x² - x V ng 0* (a ,
+ 7 1100 (at 2²) 112
22 + Oz +
1 7
| 0" (at v. ** 20) + 221
| x (x* ,²2 211
where the last inequality follows from Assumptions VVag(a" (** (2,2 s Lg- This yields
3.2 and 3.3 | S Cz and
(V (VavPen (a* 2² ( dt), (x*t1 ,gtt)) - (at (0))
$ ak (2(L, + OzL )2 + 1/7?) ||ght1 - (a* ,,t, ,x) )²) 112 a Li | - >=*x,, .// 21
2
1 [1(athtt,, - (x* 3 )1
2ax
which combing with inequality 32 leads to
Dea (2+t1, soott,y"* . 22
A Deg ( u,,, x/, - ( 20sk
Lone
[1aatt, - (x* "
2
(34)
+ Oik (2(Lg + Cz Cztzgg)2
1
|1aht1 - 00 ,² 211??
2
77
+ Fanl311 (z* y/ , 11
26

---

Published as a conference paper at ICLR 2024
According to the update rule of variable in equation (10) and the property of the projection operator Projz. we have
1
(d), k+t =41 S
| - 2/11
(35)
3r
Using Lemma A.4, we obtain
Des (xttt g 1
S &d (xtt1 t 2 + @Vzdon (1 yxtt , z x+l - + Luz
(36)
2/1
2
Combining this with inequality (35) we can derive
de (x*+1 y 2ht1
S den (x++1 yht - ( Twue
1
2x118
(37)
3R
2
(Vzeee (2 g+1 2² dx 2 k-1
24)
Using the definition of des and the formula of V Vy, derived in Lemma A.1 and the definition of d provided in equation 111 we have
V=da (x
"0 k+1
dh 2 = || VzUg, k+l p+1 , 2²)
d d=11
= =1( X (x h+1 A+1 ,,=,,,=)) 1)/1 - - x 1/72/1
|| x (x (xt y ++1 >²²
7/2
and thus
3r
@V (x nnt ;²a) dh b+l - =²²) -
|| | x- "e_hti,""11 a
2
1| 2/112
253
Then, we have from inequality 37 that
(x , tt1)
Lus
des (1
k+ , 1,, -
112 212 - 221112
23
3k | - (²* , 11?
+
27
(38)
I des (x k+1 , ,,, ) - 2 2
Lus
112 11
2 21
+ 72
| - ---1-xaaa* y 2 2
3g 13 A
(1 1. )()) - (a* ,
72
where the last inequality follows from Lemma A.3 34 and (38)
The conclusion follows by combining estimates
A.5
PROOF OF LEMMA 3.1
By utilizing the auxiliary lemmas established in the previous section, we will demonstrate the de- creasing property of
V& des (z ","""" 2² + Cox ||(o*, (0" (x*, y² (,,2*),,. x " D1
(39)
where Cos = mLx CzL )2 + 1/(27)) 1/ 1//7), and
1
Dea (x)
(F v) F) + fax v) Uy v.
13
Ck
27

---

Published as a conference paper at ICLR 2024
Lemma A.7. Under Assumptions 3.1
3.2 and 3.3 let n E (0.1/pr). 72 0, Cx+1 2 c and
Th E (T,PT/ PT/ [.1]) with 7 > 0, PT min 1/m Ps. 1 /22) and L.B == max [T + l.g Cz Tuga +
1/n, Iy 1//22, then there exist constants ca, CB > 0 such that when O < az S ca and 0 < Bk -
Cg. the sequence of "e"."" =²) generated by Algorithm 1 satisfies
Va+1 Vi S
1 _
=1( ,gtt)) (x )0
1 || - 2112
4ax
4
(40)
-oprCox 11000, - (x* ,,,,2* 2), X (a x1)2
Proof. For succinetness, we denote (x* ",,,,, 2 by wtt Let first recall estimate (30 from Lemma A.6 which states that
Den (1+ Den (10*)
1
Lon
Bel
(ictt,yatt (at, " )²
20rk
2
72
1
Tuvo)
)
||eAt1
- -2112= + (astiz + 3k | (2()))1 (41)
2
2
73/
0
22 + Cz 32 ++
1)
1
1 (w())(
0
77/
Since Ck+1 2 Ck. we can infer that (F(xtht)
- E)/eutt S (F(xtt), ( - F)/cu.
Combining with inequality (41) leads to
Vk+1 V/= = 0cc+s =cet1(x
des (w=*
+ Cox (lattt 1htl)- - (0 (, ( Cox11(0", ,x))
x (,x((())))
I des (ottl, yeti, ,,aht)) - &a (x"; ",",""""
+ Gax ||(obtt 1ageett,,t , - (wx ),²' (w (1=++))))])+++++)1))) 1)] -Co - (0 (w+)), x- (~
1
Lone
BaL22
[[00tt] y x ) - (I*,, )²
$
200k
2
22
Line
|| ||2 - =111 + Cax [|(0 ,1ttt)- - (w+*t)) ),,")) (
2
2
Cos ||(o ,x²)
- -(8 (1xx + [a +
3x
| 22x")11
7
+ ak
2(L + +.
+ 71
1
1100-11 - 0¹ (w>))1
2
1
Lod
[[xtt11,, / - (x* )1² (
Lne
) || 1= - 2012
S
20x
2
72
2/x 2
+ Cox ||(oait1, ,,,t-1- - (8" (w*+))) ), 1,,'((0' +1 1) - Cox 11(0#, ,x1) - (0'(w*)) ( 11
+ 2 max(au, Cox [|(okt], (1/o+t,,,,+,)) - (0 (w ) (,((w~))))
(42)
where the last inequality follows from the fact that
Cex := max {(L + Cz + +1( + Lz. 1/72)
We can demonstrate that
((0h) . - (# (w* +11), 1), X x((xx*1))) )>[p - -11(0"
- (x))) - (0" X X'(w"\))1'
+ 2ax (1 ,, 1h+1)= - (0" X (,x'))))))
< <(1 + ex + 20xx) [1(0t) (xtt) - (0 (w )
X x> - 1100 - (0'(w)), x² ((((w)))xx(x)) 2
-] (1((00(w (wx+1), X² (1) (0 (w²* ), x² (1x))1111
+ (1 + ck
5(1 + c+ + 21x )=pr)) (²) - (w*) X2 (w -1100 2²) - -00 (0((wt),x((w'))
1 1 || |10 - 111
(1 + ck
28

---

Published as a conference paper at ICLR 2024
for any 6g > O, where the second inequality is consequence of Lemmas A.3 and A.5 By setting 6k = / in the above inequality, we obtain that when ag S 7xPT 4, holds that (1 + e +
20x) PxPT) I 1 and thus
[|@htt ( - (0"(w ) (" - -l(cot 11(ot,2*) - (0 (, (=("())]]
+ 2a [(00t)] _ - (0 (w") X (w 111
(43)
S - -mprl((0 100 2²) - (0 (w*)), X (w ||12 + 1 TAPP
Lixx | - r01 -00
Similarly, we can show that when BR S n&PT / 4, it holds that
[| 100+,1,,_+00 , - (1)) ) x (w++))) || ? - l1(e*, |1(e",2*) - ,,,
+ 2/3 1(0ht1, , - (0 (w x (w 1>1?
(44)
$ - -m ,x)) (0 (w*), X (w ||12 + (1+ MapT
2 Ligx | -
-00tt--011(-- w0/
Combining estimates
43
and 44
we have
Ve+1 - Vv2 5
Lor
BrLa2
L8xCos ((oatti,y/ - -xx )²
20
2
7/2
TTPT
Lv=
2
1
Lix Cox
|| - -2/11
2Bk
2
TRPP
TOxPTCoxl1(0 ,²² - (0 (w="), (wo"),>" ),>*(w*))) 1)1
(45)
When Ck+1 2 Ck. mh 2 1 > 0, az S npr/ and Bx S npr/ / it holds that for any k. ax S nxPp /4, Bx S 1KPP /
Tope 2
L2x
2 M&PT
L
(1+
2
+
+ 1
L2 L2gCon Cox -
++
+
L Cox =: Ca.
7/2
2
472
nPT
(46)
and
Luz 1
2
Luz (1 1+ 2
Løx Cax
Cox Cg.
(47)
WEPT
1PT
Consequently, if ca. cg > satisties
{
{
1 4 npr, 4Ca S:
1
Ca < min
cB S min
{4
nPT, 4C' s
(48)
then, when 0 < ax S ca and
Bb S cg, it holds that
1
Lon
BeLi
2
1
[
Li Cox 2
20k
2
7/2
N&PT
4ak
and
1
Lus
2 (TPTT
1
1
Lix Cas 2
2,3
4.3x
Then, the conclusion follows from estimate (45)
A.6 PROOF OF THROREM
We establish the asy-tsytit convergence of LV-HBA in the following theorem, as measured by the residual function defined in equation 115).
R4 dist (0, FVF 0) c (V Vey. 2)) (x,
155
29

---

Published as a conference paper at ICLR 2024
Theorem A.3. Under Assumptions of Lemma A.7 let n (0.1/p5), 72 0, c c(k + 1)) with
P E (0,1/2),0 > O, and чд E PT/ [. with q > O, then there exists ca. CB > O such that when
OK Ca. and 3g E cg) with a, > 0, the sequence of (x* .yy, zh ,0, >²) generated by
LV-HBA in Algorithm satisfies
min OSkSk
(0 x²) (07 ,², (x 1/
0 0 K1/2
(49)
and
min R& Rx(htt1 ,y = = (<(I-20//2 0SkSk K
(50)
Furthermore, if there exists M > such that Des (xt ,21 I M for any k, the sequence of (x* n 2 also satisfies
S f(x" w1") (x x²) S f(x w² o ( =²) O
(51)
K2
Proof. Firstly, given Cas > O in equation (48) Lemma 3.1 guarantees that the inequality
(4]
holds when O'k S Ca. 3k S cg. By telescoping the inequality 14 for O, 0,I, I,.,,.. K
get
Σ k=0
1 4a
[1ahtt ( (x*t, y 2+
1
11 - 2
43x
(52)
v² + npT Cpp 1|(0", ,x) (x* y/t ;0 X, u², =)))))
V. VK Vo.
where the last inequality is valid since Vk nonnegative. The latter is implies by the fact that (x, U, 2) I (z 2) S f(r, for all (z.v) E C. Thus, we have
Σ 1| x (1 y 2* 2, ,² =))]
(53)
This implies that the estimate 49 holds, that is,
min OSkCK (0 x²) (0 3. 2 1; y² 2 O K1/2
(54)
Secondly, According to the update rule of variables (x,, y, 2) in equation (10). we have that
0 e cu d d + *No ,.ttttt,tt x+ + as
((rttl (ohtt,bttt x+ - (2 (
(55)
0 c + NZ( + Ck
3h - -M)
By the definitions of dh, dt and d given in equation
11 we obtain
(eny,e + (VF(a*+1 ,,)), 0) + cN ((V) (V
,, 0) Ve, (att3 (attt,ybtl, ,kx1))
+ + kt1 , 2011,+11 x
with
ey = V VayVin (1 nht / x-1 - cx (at d Ch ((a - xc))))));
(56)
ot Vather t+1 ntt , xtl) ca Ck
(2 1--1-2h z
Be
Next, we estimate l|ebyyll- We have
l|e2 5 Vay (a 1 stt 1, 2bt1) Vaythey (x* t 1/t -1) VI ayy then (a* 11t ca (dh db)
+ Ck [(ott] ( - /
ax
30

---

Published as a conference paper at ICLR 2024
For the first term in the right hand side of the above inequality, by using Assumptions 3.2 3.2 and
3.3
Lemmas
A.1
and
A.3 we can obtain the existence of Lv, > such that
V ay Poe (a++1 y h+1 R+1) VayVer (x* y² I*)l| S cx [1( .ytti , - (2 3. )|.
Using the inequality (33) and Lemma A.5 we have
VV VegWee (at,, ",, 2*) c& (d% d')l
c* Vegles (1t .rt 22/) - (d) diلl
S Cp, ||( 1 _ (0, .y" 21 27(a" ,,,²1))
$ Sca Cp. ||(0k, - (0) .r at)) Xa(a s/ )1))
(57)
with Can := -/maxx2( (2(,s + Cz Cz )2 + 1/77; 2. Hence, we have
|e Seppor ||(a*t), ,, x +1) - (x", 2// * || + Ck ||(a ,y - (a","""))
ar
C || (0 w² *)),, 1, 3t =11]
For ||e]]], we have
| S Ve (a , ,x x xht - ca c || + Ct
||: - 2*1
3x
Using Lemmas A.I and A.5 we have
V Ve (-1 1,,t_,,,,1111_ x x
cadill
= c/ || - V Uy ( (I++1 ghtth ( - 12all ||
Ck (1) / - X7 1+4 f | 2. (111 ||ا + || | _ 1)
7/2
Ck (1I 22 (tt 1+1 الرtب + | - *1)
Therefore, we have
|| S Ck
|
k+ - 2*1 +|+ +
Ck x1 (2 ( 2 || + || 1=)
3x
72
With the estimations of || and ||e-||, we obtain the existence of Li > 0 such that Re(x++1, "a(a"+,,**t,,, , S c (okkt1, "ook+,,,**t y2tt1 , xx11)- - (x*,2f (,,,2,))) x*,1 Ck [[(a (.ttt) - (I* |+]
Ck || - 2111
okk
Br
2 11(0* x²) - (0 .." ; Xr (0 ,y,, *** D)
+ ck
Cer +
72
Utilizing this inequality, let 0 2 a and Bx 2 33 for some positive constants Cr, B. we can show that there exists CR > 0 such that
Rv (artt k+1 , ,
c
1
||( (ottt)))t)))... - (x ,012 + 1 || - 2012
I CR
4ax
4.3
(58)
||(o=,at)- - (0, ,/, ) ,,, =(]]]1²)
+ Cox
Combining this with the inequality 52 implies that
RR (x*11 k1 ykt1 get2/² < 20.
(59)
k=
Because 2p 1, it holds that
K Σ
K
2p
K+2
(K + 22)1-22
>
dt 2
2
k (+1
2
t2
7 (1 - -2pp))
k=
k
k=0
1
31

---

Published as a conference paper at ICLR 2024
and we conclude from the inequality (59) that
min ogkgk
R&
(x ++1 y k+1 = =0 (
1
Thus we complete the proof of the estimate (50)
Finally, since dea (x*, n =²) S M and F(a*, y*) 2 for any have
ak f(xtt 3² vyr (x / ,/,) s M F. Ak,
and we can obtain from c = c(k + 1)2 that
f(a", 1²1) - (x ,,,
KP
Since Ug (2, S (x y, 2) S f(x, v) for all (s, E C, we get
0 5 f(x*, 1²²) v., (x 3.t = S f(z", ,.)) un (e ( =/) =
Kp
This establishes the desired estimate 51 completing the proof.
32


Reviews:
[{"review_id": "4WI5PMrPzv", "reviewer": "Reviewer_7k2H", "summary": "This paper presents a single loop proximal Lagrangian Value function-based Hessian-free Bi-level Algorithm (LV-HBA) for solving constrained bilevel optimization where the lower-level problem involves constraints coupling both upper-level and lower-level variables.\nThe authors relax the strongly convex assumption on lower-level problem to the general convex case, and provide non-asymptotic convergence analysis for LV-HBA. They also provide numerical experiments on the synthetic problem, hyperparameter selection problem and data hypercleaning task.", "questions": "1. Can the authors elaborate why there is no need to assume the Lipschitz continuity of the upper level function $F(x,y)$, which is typically necessary in bilevel optimization even the lower function is strongly convex, e.g. Xiao et al. (2023b).\n2. On page 6, the sentences after Assumption 3.2 say $f$ is $\\rho_f$-weakly convex on $X\\times Y$ with $\\rho_f\\ge 0$, which is potentially being smaller than $L_f$. Can you provide the exact form of $\\rho_f$ or show the case of $\\rho_f$ being smaller for some specific application? Does that mean we can only suppose $\\rho_f = L_f$ in general?\n3. Theorem A.1 says reformulation (4) is equivalent to constrained BLO problem (1). In the proof of Theorem A.1, it only illustrates that the feasible points of (4) and (1) are equivalent. It is unclear why this means the formulations (4) and (1) and are also equivalent. Can we conclude the optimal solution of (4) and (1) are equivalent?\n4. In reformulation (5), how to choose the parameter $r$?\n5. The proposed methods includes many hyperparameters, making difficult to implement in practice.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written. The authors propose a single loop Hessian free method that we refer to as Lagrangian Value function-based Hessian-free Bi-level Algorithm (LV-HBA). The authors provide non-asymptotic convergence analysis for LV-HBA, relaxing the underlying assumptions for lower level problem from strongly convexity to only convexity.", "weaknesses": "Please see questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zvhcqmflCs", "reviewer": "Reviewer_ttDx", "summary": "This paper introduces a new single-loop Hessian-free algorithm for the solving Bi-Level Optimization (BLO) problems. \n\nIt first creates a smooth proximal Lagrangian value function, effectively addressing the constrained lower-level problem. Subsequently, the authors present a single-level reformulation for constrained BLOs, converting the original BLO problem into an equivalent optimization problem with smooth constraints.\n\nThe paper includes a non-asymptotic convergence analysis for the proposed algorithm. Some experiments have been conducted to show the superior practical performance of the algorithm", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. This paper proposes the first single-loop Hessian-free algorithm for solving the BLO problem.\nS2. The authors introduce a new potential function, which is associated with the monotonically decreasing step size. Furthermore, they demonstrate how to select these step sizes to ensure the potential function exhibits the sufficient descent property.\nS3. The authors have conducted experiments on five machine learning tasks to validate the performance of their proposed methods.", "weaknesses": "W1. There are an excessive number of stepsize parameters in use, and it remains uncertain whether the algorithm's performance is significantly affected by the choice of these parameters.\n\nW2. While other bilevel optimization algorithms employ techniques such as Nesterov's momentum or utilize high-order information of the objective function, the plain and simple gradient descent/ascent algorithm may be slow in practical applications.\n\nW3. Assumption 3.3 (ii) can be quite stringent since the global Lipschitz constant for both $L_{g_1}$ and $L_{g_2}$ have not been determined in advance for many applications.\n\nW4. The choice for the parameter $r$ for the truncated proximal Lagrangian value function is not mentioned.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EQLckrPBw4", "reviewer": "Reviewer_hK2o", "summary": "This paper introduces a novel gradient-based algorithm designed for a class of constrained Bi-Level Optimization (BLO) problems that have coupled lower-level (LL) constraints. In this problem, the lower-level problem takes the form:\n$$\n\\min_y f(x,y), s.t. g(x,y) \\leq 0.\n$$\nIn contrast to existing methods relying on implicit differentiation techniques, this paper introduces a smooth proximal Lagrangian value function for the lower-level problem. This new value function enables the formulation of a single-level reformulation for the constrained BLO. Building upon this reformulation, a single-loop alternating gradient descent method is derived to efficiently tackle the constrained BLO. The paper establishes a non-asymptotic convergence result for the proposed algorithm. Additionally, the paper includes numerical experiments conducted on both illustrative toy examples and practical applications, demonstrating the algorithm's superior practical performance.", "questions": "I think this work provides some good contributions to constrained bilevel optimization, and hence I tend to accept it. See my questions in the weakness part.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThis paper is well-organized and in general easy to follow. The assumptions concerning the functions and problem settings are clearly elucidated, facilitating a clear grasp of both the primary concept and the technical intricacies of the proposed approach.\n\n2.\tA noteworthy contribution to the bi-level optimization community is the introduction of the proximal Lagrangian value function and the resulting single-level reformulation for constrained BLOs. This addition holds significant promise for advancing the development of other efficient methods to the constraints BLOs.\n\n3.\tNotably, the proposed method distinguishes itself by its Hessian-free nature, obviating the need for any computations involving the Hessian matrix of the lower-level problem data. Furthermore, its single-loop structure renders it highly implementable and computationally efficient. An appealing aspect of this method is its ability to work without imposing the stringent requirement of strong convexity on the lower-level problem. Moreover, it exhibits versatility by accommodating scenarios in which the lower-level problem possesses multiple solutions, expanding its applicability to a broad spectrum of practical applications.\n\n5.\tThe paper extensively explores the properties of the newly introduced proximal Lagrangian value function and the associated reformulation. Additionally, a non-asymptotic convergence analysis is included, further substantiating the contribution and the validity of the proposed approach.", "weaknesses": "1.\tIn Table 1, to the best of my knowledge, BVFSM does not require LL objective to be convex.\n\n2.\tThe authors have not included some recent works that investigate algorithms for addressing constrained Bi-Level Optimization (BLO) problems through the value function approach, such as:\n\nFliege, J., Tin, A., & Zemkoho, A. (2021). Gauss–Newton-type methods for bilevel optimization. Computational Optimization and Applications, 78(3), 793-824.\n\nFischer, A., Zemkoho, A. B., & Zhou, S. (2022). Semismooth Newton-type method for bilevel optimization: global convergence and extensive numerical experiments. Optimization Methods and Software, 37(5), 1770-1804.\n\n3.\tOn page 8,  $\\|y^k-y^*(x)\\|$ should be revised to `` $\\left\\|y^k-y^*(x^k)\\right\\| $ \"?\n\n4.\tWhen the constraints of the LL problem are absent, i.e., when $g = 0$, does the introduced proximal Lagrangian value function revert to the classical Moreau envelope function of the LL objective? Furthermore, is there any relationship between the proximal Lagrangian value function and the augmented Lagrangian function of the LL problem?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XIVlPNw1Tr", "reviewer": "Reviewer_W8M5", "summary": "This paper studied a class of new constrained bilevel optimization, where the lower-level problem involves constraints coupling both upper-level and lower-level variables. Based on the Moreau envelope value function, this paper proposed an efficient single-loop Hessian-free gradient-based algorithm. Moreover, it studied the non-asymptotic convergence analysis for the proposed algorithm. Extensive experimental results verify the efficiency of the proposed algorithm. In summary, the contributions of this paper are significant on the design algorithm and solid theoretical analysis.", "questions": "Some questions:\n\n1)\tIn the proposed LV-HBA algorithm, there exist many hyper parameters such as $\\alpha_k,\\beta_k,\\eta_k,\\gamma,c_k$. Although the authors provided the range of these parameters in the convergence analysis, I still think that the choice of these hyper parameters is not easy in practice. \n\n2)\tIn the experiments, how to choose these hyper parameters including the parameter $r$ in set $Z$ ?\n\n3)\tFrom the Theorem 3.1, the best convergence rata is $O(1/K^{1/4})$ when $p=1/4$ ?\n\n4)\tIt is better to list some bilevel optimization examples in machine learning that have nonsmooth and weakly convex lower level functions, which will strength the motivation of this work.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "This paper studied a class of new constrained bilevel optimization, where the lower-level problem involves constraints coupling both upper-level and lower-level variables. Based on the Moreau envelope value function, this paper proposed an efficient single-loop Hessian-free gradient-based algorithm. Moreover, it studied the non-asymptotic convergence analysis for the proposed algorithm. Extensive experimental results verify the efficiency of the proposed algorithm. In summary, the contributions of this paper are significant on the design algorithm and solid theoretical analysis.", "weaknesses": "It is better to list some bilevel optimization examples in machine learning that have non-smooth and weakly convex lower level functions, which will strength the motivation of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xWzHZGnqTy", "reviewer": "Reviewer_4Vih", "summary": "This paper concerns bi-level optimization (BLO) problems with coupled inner constraints. By introducing the Moreau envelope of the Lagrange function, the lower-level problem can be reformulated into a smooth function value constraint. Then, a single loop algorithm is proposed based on the formulation. Non-asymptotic rate is established for the proposed method using a newly defined stationarity measure.", "questions": "What is the central benefit of using the Moreau envelope instead of the optimal value function, especially in the technical parts?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The smoothing technique based on the Moreau envelope is good. This provides a new reformation for the BLO.\n\n2. The theoretical rate and numerical experiments are sufficient.", "weaknesses": "1.Assumption 3.1(i) seems too strong for me. Usually, the involved functions in BLO are assumed convex only w.r.t. $y$. \n\n2. The stationarity measure needs further clarification. The proposed measure is based on (16). However, it is not clear how the stationary points of (16) are related to the original BLO.\n\n3. The techniques in the theoretical proofs lack novelty, which directly takes advantage of analysis for penalty methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)