Overcoming Lower-Level Constraints in Bilevel Optimization: A Novel Approach with Regularized Gap Functions
Authors: Wei Yao
Haian Yin
Shangzhi Zeng
Jin Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: bilevel optimization
constrained optimization
gap function
single-loop
Hessian-free
convergence analysis
Primary area: optimization
TL;DR: We introduce a novel single-loop, Hessian-free constrained bilevel algorithm capable of handling broader lower-level constraints by using a doubly regularized gap function.

Abstract: Constrained bilevel optimization tackles nested structures present in constrained learning tasks like constrained meta-learning, adversarial learning, and distributed bilevel optimization. 
However, existing bilevel optimization methods mostly are typically restricted to specific constraint settings, such as linear lower-level constraints. 
In this work, we overcome this limitation and develop a new single-loop, Hessian-free constrained bilevel algorithm capable of handling more general lower-level constraints. 
We achieve this by employing a doubly regularized gap function tailored to the constrained lower-level problem, transforming constrained bilevel optimization into an equivalent single-level optimization problem with a single smooth constraint. 
We rigorously establish the non-asymptotic convergence analysis of the proposed algorithm under the convexity of lower-level problem, avoiding the need for strong convexity assumptions on the lower-level objective or coupling convexity assumptions on lower-level constraints found in existing literature. 
Additionally, the generality of our method allows for its extension to bilevel optimization with minimax lower-level problem. 
We evaluate the effectiveness and efficiency of our algorithm on various synthetic problems, typical hyperparameter learning tasks, and generative adversarial network.

Published as a conference paper at ICLR 2025
OVERCOMING LOWER-LEVEL CONSTRAINTS IN BILEVEL OPTIMIZATION: A NOVEL APPROACH WITH REGULARIZED GAP FUNCTIONS
Wei Yao!.2 Haian Yin- Shangzhi Zengl.2
Jin Zhang2.1.5
National Center for Applied Mathematics Shenzhen
Department of Mathematics, Southern University of Science and Technology
*CETC Key Laboratory of Smart City Modeling Simulation and Intelligent Technology, The
Smart City Research Institute of CETC
"Corresponding author(s). E-mail(s): zhang j9lannge@ssseeet sessusechh. edu.
Contributing authors: naow@sustech edu, en; yinha@sustech. edu. en; zengsz@susstech. edu. en;
ABSTRACT
Constrained bilevel optimization tackles nested structures present in constrained learning tasks like constrained meta-learning, adversarial learning, and distributed bilevel optimization. However, existing bilevel optimization methods mostly are typically restricted specific constraint settings, such as linear lower-level con- straints. In this work, we overcome this limitation and develop a new single- loop, Hessian-free constrained bilevel algorithm capable of handling more gen- eral lower-level constraints. We achieve this by employing a doubly regularized gap function tailored to the constrained lower-level problem, transforming con- strained bilevel optimization into an equivalent single-level optimization problem with single smooth constraint. We rigorously establish the non-asymptotic con- vergence analysis of the proposed algorithm under the convexity of lower-level problem, avoiding the need for strong convexity assumptions on the lower-level objective coupling convexity assumptions existing literature. Additionally, the generality of our method allows for its ex- tension bilevel optimization with minimax lower-level problem. We evaluate the effectiveness and efficiency of our algorithm on various synthetic problems, typical hyperparameter learning tasks, and generative adversarial network.
lower-level constraints found in
INTRODUCTION
Bilevel optimization (BiO), which subsumes minimax optimization special case, is hierarchi- cal optimization comprising two levels, with one problem nested within another. There grow- ing interest in BiO that is driven by abundance of applications. Examples in machine learning (ML) include hyperparameter optimization (Pedregosal [016]] Franceschi et al.) (2018) Mackay et al. 2019) meta-learning (Franceschi et al. 2018 Zügner Günnemann] 2018 Rajeswaran al. 2019 Ji et al. 2020), and reinforcement learning (Kunapuli et al.) [2008] Hong et al. (2023). Typically, the lower-leve (LL) problems of BiO in ML literature handle learning tasks as unconstrained optimiza- tion problems. However, constraints are crucial for learning tasks and are becoming increasingly important in designing robust, fair, and safe ML systems (Silva & Najatirad [020)] Mehrabi al.) 2021 Yang et al., 2023). The resulting constrained bilevel problem applies to a wider range of ap-
plications than the unconstrained one, such as adversarial learning (Madry et al. 2018 Wong al.)
2019
Zhang et al. 2022), federated learning (Fallah et al. 2020 Tarzanagh et al. 2022: Yang al,
2024 continual learning (Lopez-Paz & Ranzato 2017). and meta-learning for few-shot learning
Xu & Zhu 2023)
Existing BiO methods mainly focus on the LL unconstrained case (Franceschi et al. 2018 Ghadimi
& Wang 2018 Grazzi al. 2020 Ji al.
2021
Chen et al. 2021 Ji et al.
2022 Hong al.
2023 Arbel & Mairal 2022; Dagréou et al.
2022
Kwon et al. 2023 Huang 2023). Recently,
few approaches have emerged tackle BiO problems with constraints. However, most of these

---

Published as a conference paper at ICLR 2025
approaches are limited to linear constraints or constraints that rely solely on the LL variable. In this study, we address more general constrained BiO problems, where the LL problems involve constraints coupling both upper-level (UL) and LL variables. Explicitly, we consider the constrained bilevel optimization problem of the following form:
min xEXWEY
V( s.t. y S(x),
with ((x) being the set of optimal solutions of the constrainted lower-level problem,
min f(x,y) s.t. g(2, S O,
(2)
DEY
where: x E R", y E RM X and Y are closed convex sets in R and R", respectively. The UL objective F X Y RR the LL objective f X x Y + R, and the LL constraint mapping x + RP are continuously differentiable functions.
The constrained BiO problem [1 is challenging due to the implicit constraint y E S(x), which re- quires y to be a solution of an optimization problem. The I.I. constraints introduce extra complexity, especially when dealing with coupled LL constraints. This complexity hinders the straightforward extension of existing methods to constrained BiO problems (Kwon et al, 2024).
In the pursuit of solving constrained BiO problem, several algorithms have been developed to ad- dress specific cases of (I. For instance, the works (Tsaknakis et al., 2022 Khanduri et al. 2023 Kornowski al. 2024) handle constrained BiO problems with g(z, y) Ay and f [z. y being strong convexity with respect to (w.r.1.) y. As for coupling constrained LLL problem, Xiao et al. (2023) introduces an alternating projected SGD approach for family of BiO problems with cou- pling LL linear equality constraints Ay + hzx)) - = 0, where A represents a matrix, с denotes vector, and h(x) is vector-valued function. Beyond the confines of specific setting, Xu & Zhu (2023) develops a gradient-based approach for general BiO problems, where the LL problem convex with equality and inequality constraints. Since the methods presented in these works pre- dominantly utilize implicit gradient-basee based techniques, it is unexpected that they all presuppose the strong convexity of the LL objective w.r.l y, alongside other regularity conditions, to ensure the uniqueness and smoothness of the LL solution mapping. More importantly, the algorithms in these studies would tolerate the heavier memory and computational cost of using second-order calcula- tions in large-scale applications.
Therefore, it is imperative to develop first-order methods that do not necessitate explicit estimation of the implicit gradients, thereby facilitating the resolution of broader class of constrained BiO problems. In pursuit of this goal, the value function approach has garnered considerabl attention due to its efficacy in designing first-order, single-loop numerical algorithms Ye & Zhu 1995| Kwon let al. 2023; Shen & Chen 2023). However, challenges arise when the LL problem involves con- straints. Specifically, the value function, v(xx) = minyer (J(r,) g(,,,, v) I 0). is usually an implicit nonsmooth function, even when the underlying problem functions possess favorable prop- erties. This difficulty is further exacerbated in the presence of coupled LL constraints, where v(z) is typically nonsmooth, making it challenging to compute or approximate its generalized gradient. Recently, Jiag et al. (2024) proposed a primal-dual-asssteer penalty approach to address these chal- lenges associated with coupled LL constraints, based on the value function reformulation.
notable distinetive approach for addressing general constrained BiO problems has recently been presented in Yao et al. (2024), which introduces a novel proximal Lagrangian value function to tackle constrained LL problems. By utilizing this function, they convert the constrained BiO prob- lem into equivalent optimization problem with smooth constraints. Notably, their reformulation preserves the coupling LL constraints, akin to the value function approach. Consequently, the pro- posed algorithm (LV-HBA) in Yao et al. (2024) involves Euclidean projection onto the coupled LL constraint set. However, such an operation typically requires the assumption of coupling convexity and can be costly when the set is complex. Therefore, natural question arises: Can we develop first-order algorithm to overcome possibly coupled lower-level constraints in bilevel optimization?
Our response this question is affirmative. Next, we highlight the main contributions of this study. Additional related work is provided in Appendix A.]
Reducing constrained bilevel optimization into an equivalent optimization problem with only a single smooth inequality constraint. We propose a novel single-level smoothed reformulation for constrained BiO with possibly coupled LLI constraints. A key
2

---

Published as a conference paper at ICLR 2025
technique is the doubly regularized gap function defined in which serves op- timality metric for the LL problems and allows for straightforward Hessian-free free gradient evaluation, as shown in 4 Furthermore, this type of gap function can be readily extended to tackle more complex bilevel optimization scenarios involving minimax lower-level prob- lems.
Developing single-loop first-order algorithm without projection onto the coupled lower-level constraint set. Building upon the newly introduced single-leve reformula- tion, we propose Bilevel Constrained GAp Function-based First-order Algorithm (BiC- GAFFA), a first-order algorithm that can be implemented entirely within a single-loop framework. Furthermore, rigorously establish the non-asymptotic convergence analysis of BiC-GAFFA under the convexity LL problem, avoiding the necessity for either the strong convexity assumption on the L.I. objective the full convexity assumption on the LLL constraints.
We validate the effectiveness and efficiency of BiC-GAFFA on various synthetic problems, typicial hyper-paramette parameter learning tasks, and generative adversarial network. These experi- ments collectively substantiate the superior performance of BiC-GAFTA.
REGULARIZED GAP FUNCTION AND EQUIVALENT REFORMULATION
Transforming BiO problem to single-level optimization problem is useful strategy from both theoretical and computational perspectives. In this section, we introduce a novel smoothed refor- mulation tailored for constrained BiO problems with potentially coupled LL constraints. For this purpose, we define the following doubly regularized gap function for the LL problem (2):
(,,, = max YEY,AERS
{ {Ca,, A) 1| _
2||2 C(r,
10 u1²) }
(3)
2//2
271
where = R., the Lagrangian function C(x, y; =) = [(x, v) + 2² g(x y). and 7 = (71 72) > O is the regularization (or proximal) parameters. This regularized gap function concept has been previously applied in various contexts, such as variational incqualities (Fukushima) 1992), standard Nash games (Gürkan & Pang 2009). and the generalized Nash equilibrium problem (Von Heusinger & Kanzow] 2009). More recently, it has been successfully utilized in addressing optimal control problems with equilibrium constraints (Lin & Ohtsuka 20044). However, its application in studying BiO problems with constrained lower-level problem remains unexplored.
When the LL problem is convex, and the associated multipliers exist for any y S2x), that is,
y) (y), g0 y) = 0} * Ø, where (y) denotes the normal cone of Y at point y. i.e., (v) == E R (e,y' - y) < 0, Vy' e
M(x, y) := {X E. 0 Vz, 3) +
Y}. the single inequality constraint G. y, 2) S O can equivalently characterizes the solution set
LL problem.
Lemma 2.1. Assume that both fxx and g(x,-) :) are convex for any a E X. Let 7 72 > O, we have (2. y, 2) for any (z, y, 2) E XxY x xR.. Furthermore, for any (x, y, 2) E XXXxRR, (I, y.2) S 0 if and only if y E S(x) and = E M(z,y).
Another advantageous property of G. is its continuously differentiability when both functions f and g exhibit continuous differentiability.
Lemma 2.2. Assume that both f(x, y) and g(x, y) are convex in y on Y for any E X and be continuously differentiable on an open set containing X x Y. Then G, v, is contimuously differentiable on X x Y x TRP and for any (x, E X x Y R.y
(x](x,)) (x*)TV.((E,))
V Vzf (z, 0*) + + T 2z(x,000)
(I, =
V, + V
(y- (w- /n1
(4)
-(2 x²) /
g(x, 0r)
where Or and X denote 0* (x, z) and X >t(rr, U =), respectively, defined as
1
0 0' = argmin DEY
[(x, 0) + 2T TT +
110 - y
2n1
(5)
1
\T(o,V,2) argmax AERY
f(x,v) + XT
/|~ x11
-Projay (z + (2)(x.
272
3

---

Published as a conference paper at ICLR 2025
Now derive smooth single-level reformulation for the constrained BiO problem ①
min F(a, y) s.t. (x y,
0.
(6)
(x.
This reformulation problem 6 is equivalent to the original BiO problem
Theorem 2.3. Assume that both f(x,,) and g(æ, .) are convex for any x E X. Let n, 72 > O, the reformulation (6) is equivalent to the bilevel optimization problem 7 provided that for any feasible point (x, y) of 1 a corresponding multiplier of the lower-level problem (2) exists at (z. y). i.e M(x, v) A Ø. Specifically, (x* y²) is optimal solution to the bilevel optimization problem (
and x" E MMx"", ,y"" if and only if (x", >>s an optimal solution to the reformulation 10
Remark 2.4. The equivalent reformulation (6) possesses two noteworthy characteristics. First, the formulation includes only one inequality constraint. Second, the LL constraints g(,, y) I 0 are not explicitly stated in the reformulation (6), in contrast the value function- based reformulation as well as the formulation presented in (Yao et al.) 2024). Note also that the proofs of Lemmas and Theorem presented in this section are available in Appendix A..3
Remark 2.5. The assumption of the existence of the multiplier of the lower-level problem 2 in The- orem 2.3 can be guaranteed when the lower-level constraint g( y) S 0 satisfies a constraint quali- fication condition such as the Guignard's s CQ. linear independence constraint qualification (LICQ), or Mangasarian-Fromort constraint qualification (MFCQ).
3 GAP FUNCTION-BASED FIRST-ORDER ALGORITTM
Building upon the newly introduced reformulatio,, we proceed to the algorithm design phase.
First, to enhance the stability of the proposed numerical algorithms, introduce upper bound constraint on the variable z. Consequently, we consider the following truncated variant of the refor- mulation
min (xxx,)))XxYx2
F(2, v) s.t. Gz 5 0,
where z == [0, r|P with 2 0 is compact subset Rf It demonstrated that if r is appropriately
chosen such that solution (x" ,"","""""" 2²" to 6 satisfies 2| I1 S then any optimal solution 7
also an optimal solution to the original reformulation (6).
Proposition 3.1. Suppose 7,
and that an optimal solution (x", ,"",""" =²) (6) exists with
z" Z, then any optimal solution of 7 is also optimal for the reformulation (6)
Second, to develop gradient-based algorithm for solving 7 we explore its penalty formulation: min F(z,y) + cx,
(8)
(x.,,,)eXxxxx
where c > is a penalty parameter. This work focuses on first-order penalty methods for the constrained BiO problem (I). To this end, we propose algorithms to find approximate stationary
solutions of g alignment with several previous works (Liu et al. 2021 2023a Shen Chen
2023 Kwon al. 2024).
Third, we study the relationship between the penalty formulation g and a relaxed problem of (7
min F(x,y) xxX
y) s.t. G, S 6,
where E > 0 is the relaxation parameter. The relation between the penalized and relaxed problems of BiO problems has been previously studied in (Shen Chen 2023) across various single-level reformulations. Herein, we discuss the relationship between (8) and
Proposition 3.2. Assume that F(x, y) is bounded below by F on Y. For any E > O, there exists ē 0 such that any global solution (Ie, ye, Ne) to the penalty formulation (8) with penalty parameter e 2 ē also a global solution to the relaxed problem (9) with some relaxation parameter Ee satisfying E S Moreover, if (Ie, ye, 2e) is a local solution to the penalty formulation (8). then is also a local solution to the relaxed problem
with relaxation parameter E. := (Ze, Bey Ze).
If we consider the penalty formulation ( with increasing sequence of penalty parameter C₁ such that c₁ - oc, any accumulation point of the sequence of solutions associated penalty formulation problem (1.5) with varying values of et solution to the problem (7).
4

---

Published as a conference paper at ICLR 2025
Theorem 3.3. Assume that X and Y are closed, and functions F, f and g are continuous on X x xY. Suppose that cj - oc and let
(Øk, yk 2x) E argmin F(a, v) + cu (x,
Then, any accumulation point (z.g. y, E) of the sequence {(Ik) yk. 2x)} is solution problem 7
The proofs of the lemmas and theorem presented this section are provided in Appendix [A.4
Remark 3.4. The truncation technique applied to the multiplier of lower-level problem in reformu- lation problems 7 and (8) is commonly used in the literature on numerical augmented Lagrangian methods for nonlinear program (see, e.g., A.drrann et al. (2008)). Applying this truncation techmique can enhance the stability of the proposed numerical algorithms. As demonstrated in Proposition 3.1 theoretically, if the bound is selected such that solution
to (6) exists with ||=*|>> S r.
then the optimal solution of will also be optimal to (6). Propositions 5. 3.2 and Theorem 3.3
along with the numerical experiments in Section 6 illustrate that the penalized problem serves as an effective surrogate for the original bilevel problem.
3.1 THE PROPOSED ALGORITHM
Now introduce first-order gradient-based, single-loop algorithm to solve the truncated and penalized approximation problem (8) with a potentially varying penalty parameter ck. Note that solving (8) still requires care since involves optimal value function (r v, for another optimization problem.
Lemma ettabllisss that Gr is continuously differentiable, implying that the objective function of (8) is also continuously differentiable. Consequently, we can apply gradient descent-type method solve However, also noted in Lemma 2.2 computing the gradient VG, (a y a*) at
the current iterate (a* y², 2²) requires solving the minimization problem in (5) to obtain the exact solution 8* (x*,, y", 2*),, process which can be computationally intensive.
To mitigate this computational challenge, we introduce an auxiliary sequence (0*) as an approxi- mation to 0*. At each iteration, we employ a single projected gradient descent step to update g to approximate 0* (a: y ) as follows:
g++l= Projy (g* (8h-maah))
(10)
where > is the step size, and
t = Vyl(at, 0h) + (2 Veg(tt fackt,0 oh) + 1 (0--
(11)
7
Furthermore, we introduce iterate k+1 to represent X (a yht 2* as follows:
x = (x* y 24t) = Projæ; (z* 12g(2* .v"))
(12)
By substituting (Oh+1, 1+ for (0", X²) in (4). we can approximate the gradients of the objective function in ( to define the update directions:
V.F(at,3 Ch
( Vel(s" 1²t) + (AR+I)TV TV Veg(a .x²) - Vet(e"t -x*0) Veg(o 0
(13)
d = (a* y²) vzf(** 1hh (A*tI)"V x² ) (1* gh+l) 1/11
d: :=== X x+ 1/12 g( gb+1).
Finally, we implement update for the variables (I,
y, 2) using step size aj > 0:
(z A++ 1++ x = Projxxyxz ((*" ,² au (d., dr, d())
(14)
The complete algorithm is presented in Algorithm Notably, our proposed algorithm uses only the gradient information of the problem's functions and can be easily implemented when the projections onto the sets X and Y are computationally simple. Furthermore, the updates +++1 y² and ++1 can be executed in parallel, enhancing computational efficiency.
5

---

Published as a conference paper at ICLR 2025
Algorithm Bilevel Constrained GAp Function-based First-order Algorithm (BiC-GAFFA)
Input: (x =0) E XxXxXx, 8 Y, stepsizes ag 7 0, proximal parameter ? (71 12),
penalty parameter for
K do
calculate dž as in 11
update
gh+1 Projy (@+ nedg), x = -roojg (=* + rag(a", ,v)))
calculate d di de as in 13
update
(a hh1 xh1 Projxxxx2 (1*t, ,/, ax(d d:))
end for
4 NON-ASYMPTOTIC CONVERGENCE ANALYSIS
In this section, we rigorously establish the non-asymptotic analysis for BiC-GAFFA towards the truncated and penalized approximation problem
(x.g,))EXXYa (e 2) = F(x, + c ().
min
(15)
The proofs of Lemmas and Theorem presented in this section available in Appendix A.5
4.1 GENERAL ASSUMPTIONS
The following assumptions formalize the smoothness property of the UL objective F, and smooth- ness and convexity properties the LL objective f and the LL constraints g.
Assumption 4.1 (UL objective). The UL objective F is Lm-shooth on x Y. Additionally, F is bounded below X x Y, i.e., F := inf().)) F(x, y) -0.
Assumption 4.2 (LL objective). Assume that the following conditions hold:
(i) For each E X, f is convex w.t.f LL variable on Y. iii is continuously differentiable
open set containing X Y and is Ly-smooth X x Y. Assumption 4.3 (LL constraints). Assume that the following conditions hold:
(i) For each E X, is convex w.E.f. LL variable y on Y. iii g(x, v) is Ly -ipsshitt continuous X x Y.
(iii) (x. y) is continuously differentiable on an open set containing X V2g(z. and V V0g(r, y) are T.g. and -ipscchit continuous on X x Y, respectively.
Our assumptions solely require the first-order differentiability of the problem functions, avoiding (possibly) higher-order smoothness. The setting of this study substantially relaxes the existing re- quirement for second-order differentiability in constrained BiO literature. Moreover, we do not impose either the strong convexity on the LL objective fxx the fully convexity of the LL constraints g(z, v).
4.2 CONVERGENCE RESULTS
The proof of con-asymptotic convergence for BiC-GAFFA primarily hinges on establishing the sufficient descent property of the merit function defined as follows:
V₂ = der (2 2² Ce
||@*
0
(x "h 2* )}
where
Dc. (x,, v2,) (F(xx v) F) (x,
Ck

---

Published as a conference paper at ICLR 2025
and C. == ( rLgi + + Lg)? inequality holds
With appropriately chosen step sizes ag and 7e, the following
VK+1 - V/ S
h+1
w w²112-
CoCoo 110* (w
400g
271
where w. (a*, y² ). ). See Lemma A.5 for detailed description.
We define the residual function for problem 15 as follows
R(x, ys 2) == dist (0, Vh (2, y. =) Xxxxxxzxzz 1, v.))),
noting that R(z, y. 2) if and only if (z, y, 2) is stationary point to (5 i...
EE V y, 2) + Xxxx (2, v,
Theorem 4.4. Under Assumptions 4.7
4.2 and 4.3 assume that X, Y compact sets, 71 0.
12 > O, c > 0 and Te E (n, ( + .g + 1/7)) with y > O. Then there exists Ca > 0 such
that when Ork E Ca) with >> 0, the sequence of (x* ,y, 2 0h, N²) generated by Algorithm satisfies
1
min R(x OSkSK
++ k+1)
K2/2
In subsequent analysis, we consider Algorithm 1 and the penalty approximation problem 15 with an iteratively increasing penalty parameter Gk. leading to the following convergence result based on the residual function RI 2) == dist (0, Vilee (I, v, + NNxx x (x, U.2)).
Theorem 4.5. Under Assumptions 4.1 and 4.3 assume that X, Y are compact sets, "/ > O, [0, 1/2) and THs (n, 1/LLf + +rbg + 1//1)) with 7 > 0. Then there exists Co such that when ar E (a, Ca) with ar > O, the sequence of (x* v 2h,0k, x²) generated by Algorithml satisfies
72 0, Ck c(k + 1)e with e 0, E
(+* yt1 ++))= OSkSK
min
K((1-
Furthermore, if p > O and Wey (s* ,,,, is uniformly bounded above, then the sequence of (a* ( 2 satisfies
s (x x)
KP
Remark 4.6. The hypergradient norm is commonly employed as stationary measure for BiO prob- lems, when the LL problem is unconstrained and strongly convex. However, for constrained BiO problems, even if the I.I objective is (strongly) convex w.rlf the I.I. variable, the differentiability of variants of hypergradient, including optimistic and pessimistic ones, is not fully understood. To our best knowledge, no universally recognized stationary measure is known in this scenario. Different methods use various stationary measures. For instance, the KKT residual function utilized in (Liu al.) 2023b Lu 2023). The residual functions in the above theorems originate from the corre- sponding penalized problems, aligning with several previous prior on first-order penalty methods
(Liu et al. 2023a Shen & Chen 2023
Lu & Mei 2024 Kwon al. 2024).
EXTENSION TO BILEVEL OPTIMIZATION WITH MINIMAX PROBLEM
In this section, we explore the extension of our proposed gradient-basee based, single-loop, Hessian freee algorithm, originally designed for bilevel optimization problems with constrained lower-level prob- lems, to bilevel optimization problems with minimax lower-level problem (Beck et al. al. 2021
2023 Sato
min FE X Z
F(x, y,2)
s.t. (y,z) E SP(x),
(16)
where Sp(z) denotes the set of saddle points for the convex-coneaws minimax problem.
min max fæ, 2),
(17)
yeY zEZ
7

---

Published as a conference paper at ICLR 2025
where x E R", E R and 2 RP, the sets X, Y and Z are closed convex sets in R R and IR, respectively. The UL objective F X x Y + R, and the LL objective f x x + R continuously differentiable with f being convex in y and concave in 2. Building upon the idea applied in the development the regularized gap function (3) we introduce the doubly regularized gap function for lower-level minimax problems, defined as:
graddle (x, (2,9.2)
max BEY,E
{f 272
| ((x,-((,,,)))
100
v1p3 (18)
2/11
By employing proof techniques analogous to those used in Lemma 2.1 or Theorem 3.3 from Von Heusinger & Kanzow (2009), can derive similar results for the doubly regularized gap function Gy (x, 2)
Lemma 5.1. Assume that far 2) is convex in Y for any given E X, E Z and concave 2 on for any given E X, E Y. Let 7. 2 O, we have graddle (x. y, 2) 2 0 for any (I, y. 2) E
Z. and
ge gaaddle (2, (. S 0,
if and only if 2) E SP(r).
This characteristic of the newly introduced gap function enables the following equivalent single- level reformulation of the problem (66).
min (m. (x F, s.t. graddle (x, ys 2) S O.
(19)
establish the equivalence be- tween the reformulation (19) and the bilevel optimization problem (16).
Using Lemma 5.1 and the proof techniques in Theorem
Theorem 5.2. Assume that [xx, y, is convex in on Y for any given X. 2 E Z and concave in on Z for any given x E X. E Y. Let 71 > 0, the reformulation (19 is equivalent to the bilevel optimization problem (66.
Utilizing the reformulation 19) and the gradient formula of the gap function Ga (x., y, pro- vided Lemma A.7 in the Appendix, analogous to BiC-GAFFA, we can propose a gradient-based, single-loop. Hessian-free algorithm for problem (16), detailed in Algorithm
Algorithm single-loop flessian-free algorithm for bilevel optimization problems with minimax lower-level problem
Input: (z", ,,)=)))))))))))))))))) E Xxxxxx00 E Y, stepsizes ag, 7 > 0, proximal parameter 7 = (71, 72),
penalty parameter for to do
calculate d and d in 55
update
gh+l Projy (0 ma), x = -Projz (2* - mxa%))
calculate dh. dk. dh as in (56:
update
(a++1 ,y b+l ( b+l) Projxxxxz (ut,,",=")) ar (dt
end for
While the primary focus of this paper is the bilevel optimization with constrained lower-level prob- lems, we defer the convergence analysis of this algorithm to future work.
NUMERICAL EXPERIMENTS
To validate both the theoretical and practical performance of our proposed algorithm (BiC-GAFFA), we conduct experiments on both synthetic tests and real-world applications. We compare BiC- GAFFA with various related algorithms on the synthetic tests and some real-world applications. Detailed information about the experiments can be found in Appendix[A.2 Our code is available at https: // thub. SUSTecS Opt mi zat ioo B GAFFA
8

---

Published as a conference paper at ICLR 2025
6.1
SYNTHETIC EXPERIMENTS
Here we consider the following synthetic bilevel optimization problem:
min xEx,
(y1-2) - 2- 1x,) nn + llya + 11
(20)
(2) argmin ( Iy-1l -x'y 1.ya S.t. Σ h(x.) 11y1 +1.y 0},
s.t.
(n) 82)
where X' = R", y = R x IR" and h(t) R + R is defined as h(t) = 19. We consider the
cases q and g = 3. Note in both cases, the optimal solution x" 1n yi 2 1,
y2 -3 n, and S(x) = {(x + (2)22) E h(x,) + [ + I,) + 1, = 0}. where 1
denotes the v-diimnnsionl vector with all elements equal to
A.7000
BAM
13 MBB
EAC-GAFFA
Figure I: The first two pictures are results for the problem 20 with 0 1, n, 1000, and the third
and fourth pictures are results for the problem (20) with g 3, 1000.
We compare our algorithm (BiC-GAFFA) with AiPOD Xiao al. 2023 GAM (Xu Zhu 2023).
B BVFSM (Liu et al. 2023a), and LV-HBA (Ya et al. 2024) on the synthetic tests. Hyperparameters are collected in Appendix A.2.I The comparison results are collected Figure [ From this, we can see that BiC-GAFFA converges fast and correctly in both cases, while AiPOD fails to optimize either of the problems, algorithm GAM and BVFSM run slowly on both cases, the algorithm LV- HBA converges well in the case of q 1 but runs slowly in the case of 3 due to the high complexity of the projection step.
Table 1: Sensitivity analysis problem 20 with g 3, 100.
71
Time
9
Time (5)
Time/
10
1.0
0.001
0.01
0.3
2.24
0.001
0.01
0.3
2.88
1.0
0.001
0.01
0.3
3.04
0.001
2.47
1.0
0.0003
0.003
0.3
7.69
1.0
0.001
0.01
0.3
2.28
10
1.0
1.0
0,0007
0.0005
0.887
0.005
0.3
0.3
4.61
3.25
0.001
10
0.1
0.001
0.01
0.3
2,89
0.001
0.001
2,72
1.0
0.001
0.01
0.4
2.92
10
0.5
0.001
0.01
0.3
2.60
10
1.
0.001
0.01
0.49
1.95
Figure 2: Time cost V.S. 12.
Sensitivity analysis. We conduct sensitivity anal- ysis the problem (20) to show the performance of BiC-GAFFA under different hyperparameters and problem sizes. We use the computational time when [xx - X=|xx < 0.01 as metric to measure the performance. The comparison results for differ- ent hyperparameters are presented in Table I1 which demonstrates the robustness of BiC-GAFFA. Fig- ure 2 shows the results based on the problem's di- mension, which is plotted on logarithmic scales for both axes, indicating that BiC-GAFFA scales well for large-scale problems. Detailed reports and addi- tional information provided in Appendix A.2.T
Table 2: Results the sparse group Lasso hyperparameter selection problem with nTr 100, nVal 100, nTest = 300.
Method
Time(s)
Val
Test
Grid
17.3
35,9 4 7.2
37.7
Random
17.4 17.4-00 0.7
6.7
35.7 15.7:63
TPE
16.9 - 0.7
33.9
36.0
IGJO
21.2 21.2-222
19.7
25.6
VE-iDCA
12.4
14.642
29
BIC-GAFFA
21.4 0.7
7.
22.3 3.0
6.2 HYPERPARAMETER OPTIMIZATION
Hyperparameter optimization (HO) is an inherent bilevel optimization. According to Theorem 3.1 of Gao's work (Gao al. 2022). can turn the hyperparameter optimization problem of statistical

---

Published as a conference paper at ICLR 2025
learning model into equivalent constrained BiO problem. Three HO problems considered in this section. Detailed results and information are provided in Appendix A.2.2
Sparse group LASSO problem. For the HO problem for the sparse group LASSO model, compare GAF-A with some widely-used algorithms, including Grid Search, Random Search, TPE (Bergstra al. 2013), IGJO (Feng & Simon, 2018), and VF-iDCA (Gao et al. 2022). Detailed
settings are provided in Appendix [.2.2 From Tabla2 we can see that BiC-GAFFA outperforms the other algorithms in terms of both validation and test errors.
Support vector machine (SVM). In this part, we apply BíC-GAFFA to HO problem where the lower model (base learner) SVM and the upper model is signed distance based loss. We ) and LV-HBA and the results are shown in Figure We can see that BiC-GAFFA converges faster than GAM and achieves better performance.
compare BIC-GAFFA with GAM (Xu & Zhu 2023)
DA0GARRA
GAM
Teu Aecuser 700
Figure 3: Results of the SVM problem on the diabetes dataset.
Figure Results of the data hyper-cleaning problem on the breast-cancer dataset.
Data hyper-cleaning, Data hyper-cleaning (Franceschi et al. 2017) is train classifier based on data where part of their labels are corrupted with a probability Pe. to achieve this goal, we need to train classifier that recognize the wrong labeled data. Such a process can be modeled HO problem. Results are shown in Figure 4 from which we can see that BiC-GAFFA outperforms the other algorithms in terms of both validation and test accuracies.
6.3 GENERATIVE ADVERSARIAL NETWORKS
Generative adversarial networks (GAN) (Goodfellow et al. 2014) models are also investigated in our paper. involves hierarchical structure of optimization with two interacting components: the generator and the discriminator. We compared different training strategies for distribution recovery problem. Detailed information is provided in Appendix [A.2.3] The numerical results in Figure and Table 3 show BiC-GAFFA can train such generative model efficiently.
DAWGAN (KDGGTFE))
MitS (BCSIZAFRS)
Table 3: Time to meet the required accuracy, (n records the number of failures.
WINN--77
Seatiurr Eib-wrrrenn
Methol
Time reach sanget accuRacy
EMcc 0.5
EM: 0.1
GAN
:: 13,0
64.5 12.5
17:2 2.3
WIAN--IP
17.3+622
Con-CIA
12.3
(3.0034)
18.2
GAN (BIC-GAFFA)
BL-AN (BIC-GAFEA)
0.5
(RC-GAFFA)
Figure Earth mover's distance Time.
7 DISCUSSION AND CONCLUSION
This work introduces BIC-GAFTA, a single-loop first-order algorithm tailored for broader class of bilevel optimization problems, where the LL constraints may depend the UL variables. A key technique employed here to address constrained LL problem the newly introduced doubly regularized gap function, which serves straightforward gradient evaluation. We also study the non-asymptotic performance guarantees of BiC-GAFFA. The experimental results validate the effectiveness of BiC-GAFFA.
optimality metric for the LL problems and allows for
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Authors listed in alphabetical order. This work is supported by National Natural Science Founda- tion of China (12222106, 12326605, 62331014, 12371305), Guangdong Basic and Applied Basic Research Foundation (No. 2022B151502005
REFERENCES
Roberto Andreani, Ernesto G Birgin, José Mario Martínez, and María Laura Schuverdt. On aug- mented lagrangian methods with general lower-level constraints. SIAM Journal Oplimization, 18(4):1286-130, 2008
Michael Arbel and Julien Mairal. Amortized implicit differentiation for stochastic bilevel optimiza- tion. In ICLR, 2022.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. arXiv:1701.07875, 2017.
Wasserstein gan.
arXiv preprint
Amir Beck. First-order methods in optimization. SIAM, 2017.
Yasmine Beck, Ivana Ljubić, and Martin Schmidt. A survey bilevel optimization under uncer- tainty. European Journal of Operational Research, 31 311(2):401-22) 2023.
James Bergstra, Daniel Yamins, and David Cox. Making a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures. ICML. PMLR, 2013.
J Frédéric Bonnans and Alexander Shapiro. Springer Science & Business Media, 2013.
Perturbation analysis of optimization problems.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM trans- actions on intelligent systems and technology (TIST), 2 121,)211,,,011111 2011.
Xiaopeng Chao, Jiangzhong Cao, Yuqin Lu, Qingyun Dai, and Shangsong Liang. Constrained generative adversarial networks. leee Access, 10992088-9299 2021.
Lesi Chen, Yaohua Ma, and Jingzhao Zhang. Near-optimal nonconvex-strongly-coneee bilevel op- timization with fully first-order oracles. arXiv preprint arXiv:2306.14853, 2023.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems, NeurIPS, 2021.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In NeurlPS, 2013.
Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. In NeurlPS, 2022.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta- learning approach. arXiv preprint 2xXx:20022007440 2020.
Jean Feng and Noah Simon. Gradient-based regularization parameter selection for problems with nonsmooth penalty functions. Journal of Computational and Gruphical Statistics, 27(2):426-435, 2018.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In ICML. PMLR, 2017.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In ICML. PMLR, 2018.
Masao Fukushima. Equivalent differentiable optimization problems and descent methods for asym- metric variational inequality problems. Mathematical programming. 53:99-110, 1992.
Lucy L Gao, Jane Ye, Haian Yin, Shangzhi Zeng, and Jin Zhang. Value function based difference- of-convex algorithm for bilevel hyperparameter selection problems. In /CML. PMLR, 2022.

---

Published as a conference paper at ICLR 2025
Lucy L Gao, Jane J Ye, Haian Yin, Shangzhi Zeng, and Jin Zhang. Moreau envelope based ceakey reformulation and algorithm for bilevel programs. arXiv preprint arXiv:2306.16761, 2023.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246., 2018.
Tommaso Giovannelli, Griffin Dean Kent, and Luis Nunes Vicente. Inexact bilevel stochas- tic gradient methods for constrained and unconstrained lower-level problems. arXiv preprint arXiv:21 10.00004, 2021.
Ian Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Neur/PS, 2014.
Paul J Goulart and Yuwen Chen. Clarabel: An interior-point solver for conic programs with quadratic objectives. arXiv preprint arXiv:2405. 12762, 2024.
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo, On the iteration com-
plexity of hypergradient computation. In ICML. PMLR, 2020.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Im- proved training of wasserstein gans. In NeurlPS, 2017.
Güil Gürkan and Jong-Shi Pang. Approximations of nash equilibria. Mathematical Programming, 117:223-253, 2009.
Elias S Helou, Sandra A Santos, and Lucas EA Simões. A primal nonsmooth reformulation for bilevel optimization problems. Mathematical Programming, 198(2):1381-1409, 2023.
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:2303.03944 2023.
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: Nonasymptotic analysis and faster algorithms. In ICMI. PMLR, 2021.
Kaiyi Ji, Mingrui Liu, Yingbin Liang, and Lei Ying. Will bilevel optimizers benefit from loops. In NeurlPS, 2022.
Liuyuan Jiang, Quan Xiao, Victor M Tenorio, Fernando Real-Rojas, Antonio G Marques, and Tianyi Chen. A primal-dual-assise penalty approach to bilevel optimization with coupled constraints. In NeurlPS, 2024.
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. PMLR, 2023.
Guy Kornowski, Swati Padmanabhan, Kai Wang, Zhe Zhang, and Suvrit Sra. First-order methods for linearly constrained bilevel optimization. In NeurIPS, 2024.
Gautam Kunapuli, Kristin P Bennett, Jing Hu, and Jong-Shi Pang. Classification model selection via bilevel programming. Optimization Methods & Software, 23(4):475-489, 2008.
Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. A fully first-order method for stochastic bilevel optimization. In ICML. PMLR, 2023.
Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. In ICLR, 2024.
12

---

Published as a conference paper at ICLR 2025
Kangyu Lin and Toshiyuki Ohtsuka. A successive gap constraint linearization method for optimal control problems with equilibrium constraints. Pape-pppesOnn,,ee, 58(18):165-11) 172, 2024.
Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order al-
gorithmic framework for bi-level programming beyond lower-level singleton. In ICML. PMLR, 2020.
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. PMLR, 2021.
Risheng Liu, Xuan Liu, Shangzhi Zeng, Jin Zhang, and Yixuan Zhang. Salue-function-baser se- quential minimization for bi-level optimization. IEEE Transactions on Pattern Analysis and Ma- chine Intelligence, 45(12): 15930-15999- 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. PMLR, 2023b.
Risheng Liu, Zhu Liu, Wei Yao, Shangzhi Zeng, and Jin Zhang, Moreau envelope for nonconvex bi-level optimization: a single-loop and hessian-free solution strategy. In ICML. PMLR, 2024.
David Lopez-Paze Pazz and Mare' Aurelio Ranzato. Gradient episodic memory for continual learning. In NeurlPS, 2017.
Songtao Lu. SLM:
smoothed first-order Lagrangian method for structured constrained nonconvex optimization. In NeurIPS, 2023.
Zhaosong Lu and Sanyou Mei. First-order penalty methods for bilevel optimization, SIAM Journal on Optimization, 34(2):1937-1969 2024.
Matthew Mackay, Paul Vicol, Jonathan Lorraine, David Duvenaud, and Roger Grosse. Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. In ICLR, 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM computing surveys (CSUR), 54(6):1-35 2021.
Luke Metz, Ben Poole, David Pfau, and Jascha Sohl-Dickstein. Unrolled generative adversarial networks, arXiv preprint arXiv:1611.02163. 2016.
Jifí V Outrata. On the numerical solution of a class of stackelberg problems. Zeitschrift für Opera- tions Research, 34(4):255-21) 1990.
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In ICML. PMLR, 2016.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with im- plicit gradients. In NeurlPS, 2019.
Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
Ryo Sato, Mirai Tanaka, and Akiko Takeda. A gradient method for multilevel optimization. In NeurlPS, 2021.
Han Shen and Tianyi Chen. On penalty-based bilevel gradient descent method. In ICML. PMLR, 2023.
Samuel Henrique Silva and Peyman Najafirad. Opportunities and challenges in deep learning ad- versarial robustness: A survey. arXiv preprint arXiv:2007.00753 2020.
Noah Simon, Jerome Friedman. Trevor Hastie, and Robert Tibshirami. A sparse-group group lasso. Journal of computational and graphical statistics, 22(2):231-24) 2013.
13

---

Published as a conference paper at ICLR 2025
Daouda Sow, Kaiyi Ji, Ziwei Guan, and Yingbin Liang. A primal-dual approach to bilevel optimiza- tion with multiple inner minima. arXiv preprint arXiv:2203.01123, 2022.
Davoud Atace Tarzanagh, Mingchen Li, Christos Thrampoulidis, and Samet Oymak. Fednest: Fed- erated bilevel, minimax, and compositional optimization. In ICML. PMLR, 2022.
loannis Tsaknakis, Prashant Khanduri, and Mingyi Hong. An implicit gradient-type method for linearly constrained bilevel problems. In ICASSP. IEEE, 2022.
Anna Von Heusinger and Christian Kanzow. Optimization reformulations of the generalized nash cquilibrium problem using -ssdato--soda--ype functions. Computational Optimization and Appli- cations, 43:353-377, 2009.
Eric Wong, Leslie Rice, and Zico Kolter. Fast is better than free: Revisiting adversarial training. In ICLR, 2019.
Quan Xiao, Han Shen, Wotao Yin, and Tianyi Chen. Alternating projected sgd for equality- constrained bilevel optimization. AISTATS, PMLR, 2023.
Siyuan Xu and Minghui Zhu. Efficient gradient approximation method for constrained bilevel opti- mization. In AAAI, 2023.
Qisong Yang, Thiago D Simão, Simon H Tindemans, and Matthijs TJ Spaan. Safety-constrained reinforcement learning with a distributional safety critic. Machine Learning, 11(33)859-887, 2023.
Yifan Yang, Peiyao Xiao, and Kaiyi Ji. Simfbo: Towards simple, flexible and communication- efficient federated bilevel learning. In NeurlPS, 2024.
Wei Yao, Chengming Yu, Shangzhi Zeng, and Jin Zhang. Constrained bi-level optimization: Proxi-
mal lagrangian value function approach and hessian-free algorithm. In ICLR, 2024.
Jane Ye and Dao li Zhu. Optimality conditions for bilevel programming problems. Oplimization, 33(1):9-27, 1995.
Mao Ye, Bo Liu, Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: A simple first-order approach. In NeurlPS, 2022.
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. PMLR, 2022.
Daniel Zügner and Stephan Günnemann. Adversarial attacks graph neural networks via meta learning. In ICLR, 2018.
14

---

Published as a conference paper at ICLR 2025
A APPENDIX
The appendix is organized as follows:
We give a brief review of additional related work in Section A.1
Experimental details are provided in Section A.2
Proofs in Section 2 can be found in Section A.3
Proofs in Section are presented in Section A.4
Proofs in Section are given in Section A.5
Details regarding the extension to bilevel optimization with minimax lower-level problem are discussed in Section A.6
A.1 ADDITIONAL RELATED WORK
In the section, we give brief review of additional related works that are directly related to ours.
Gap functions. Transforming a BiO problem into a single-level optimization problem is useful both theoretically and computationally. Gap functions are erucial in this process. Among them, the most commonly used one is the value function, originally proposed in (Outrata 1990; Ye & Zhu 1995). When the LL problem unconstrained and its smooth objective is strongly convex w.r.f the LL variable, the value function of the LL problem is smooth and has a closed-form gradient with the LL solution. Benefiting from this property. fully first-order gradient- based algorithms have been developed. see, e.g., Liu et al. (2023a); ; Ye et al. (2022); Shen & Chen (2023): Kwon et al. 2023 : Mei (2024). However, the value function is often nonsmooth when the L.I. problem constrained or its objective is merely convex. As result, the value function reformulation usually leads to a nonsmooth single-level optimization problem. Recently, the Moreau envelope-based gap functions have emerged, see, e.g., Gao al. (2023); Yao et al. (2024); Liu et al. (2024). Among these works, by utilizing the Moreau envelope-basse reformulation for unconstrained LL problem, the very recent study (Liu et al., 2024 proposes novel single-loop
baseed algorithm for general BiO problems with nonconvex and potentially nonsmooth LL objective functions. In con- trast, both Gao et al. (2023) and Yao al. (2024) address constrained BiO problems. The key difference is that the Moreau envelope-based reformulation in [ao et al. (2023) is nonsmooth, while the reformulation in Yao et al. (2024) smooth. The smoothness achieved by leveraging a novel proximal Lagrangian value function to handle constrained LL problem. When the LL problem has (coupling) inequality constraints,
important note that all the reformulations in these works explicitly preserve these (coupling) inequality constraints. In contrast, this work introduces a novel reformulation that integrates the LL (coupling) inequality constraints into a doubly regularized gap function. Consequently, it achieves the minimal smooth constraint, with only one smooth constraint the single-level reformulation. This provides a significant advantage algorithm design because it removes the need for Euclidean projection onto the (coupled) LL constraint set. This expands the range of applications and significantly reduces computational costs.
First-order algorithms. Many applications involve optimization problems with thousands mil- lions of variables. First-order algorithms are popular because their storage and computational costs can be kept tolerable level. In bilevel optimization, the value function approach avoids recur- rent second-order calculations like those involving the Hessian matrix in implicit gradient-base methods. This makes it particularly useful for developing efficient first-order, single-loop numer- ical algorithms, see, e.g., Kwon et al. (2023); Chen et al. (2023), in cases where the LL problem unconstrained and its smooth objective strongly convex w.E. the LL variable. When the LL problem involves constraints, challenges arise. For instance, the value function is often nonsmooth and lacks an exact straightforward gradient evaluation. To address the nonsmooth issue, [iu et al. 2023a) introduces sequential minimization algorithm framework using penalty and barrier func- tions. The recent study (Shen & Chen 2023) provides sufficient condition under which the value function is (Lipschitz) smooth and proposes first-order algorithms through the lens of the penalty method for bilevel problems with constraints that rely solely on the LL variable, Also, through the lens of the penalty method, first-order method with complexity guarantees is developed in Lu & Mei (2024) using a novel minimax approach, and the recent study (Kwon et al.) (024) proposes a first-order stochastic bilevel optimization algorithm when the L.I constraints depend only the L.I.
15

---

Published as a conference paper at ICLR 2025
variable. Other advances in first-order algorithms for bilevel optimization include: primal-dual al- gorithms (Sow et al. 2022); ; primal nonsmooth reformulation based algorithm (Helou et al. 2023);
and low-rank implicit gradient-basee methods (Giovannelli et al. 2021).
A.2 DETAILS EXPERIMENTS
All the experiments in this paper are performed on a computer with Intel(R) Core(TM) i9-9900K CPU @ 3.60GHz and 16.00 GB memory. Except for the synthetic experiments. the reported data for all the other experiments (including the sparse group LASSO problems, SVM, data hyperclean and GAN) are the statistical results after repeating each experiment 20 times. For further discussions on computational considerations and scalability, please refer to the notes provided in Appendix A.2.4
A.2.1 SYNTHETIC PROBLEMS
For all the experiments on this problem, we use the initial point (Xo. yo = (0,, , O,, 0,,) where O, represents the n--dimensional zero vector. For the synthetic experiments recorded in Figure use the following settings:
For AIPOD, we set 5, 2, 3 0.0001, a 0.0005;
For GAM, we solve the lower level problem with convex solver Clarabel (Goulart & Chen 2024) and set stepsize a = 0.01:
For BVFSM, we solve the subproblem (10) and (11) in (Liu et al. 2023a with Clarabel, use the quadratic penalty function with 02 = Pa = Pk: 1/ and stepsize = 0.01;
For LV-HBA, we set 711 10, 12 = 1, = 0.005, 3 0, 0.03;
For BiC-GAFFA, we set 71 1, 0.1, 0.001, ry 0.01, r- L, 0.2.
They are applied for both problems, i.e., for both n. 1000, problem. Note that AIPOD requires the calculation of matrix inversion, which computationally expensive, however, due to the special structure of the problem, the matrix inversion in each iteration returns the same result, so we only calculate once and use the result all iterations. For LV- HBA, the projection step is the most structure of the problem where = since the projection is efficient in that case, which is the reason why it performs well in the first case. However, for the problem where q 3. the projection step much more complex, which requires solving a nonlinear optimization problem, therefore, performs poorly in the second case.
problem and = 1000,
part generally, it gets benefits from the special
Table 4: Sensitivity analysis the hyperparemeters for the problems with 3, where q 1 in the left table and = in the right table.
72
72
TJk
Time (s)
?1
0Xk
7Jk
Time (s)
1.0
0.001
0.01
2.96
1.0
0.001
0.01
2.66
1.0
0.001
0.01
0.3
2.84
0.001
2.28
1.0
0.001
0.01
2.95
0.001
2.47
1.0
0.001
0.01
1.0
0.001
0.01
3.04
0.1
0.001
0.01
10
0.1
0.001
0.01
2.89
0.3
0.001
0.01
0.3
3.14
10
0.3
0.001
0.01
2.72
0.5
0.001
0.01
0.3
2.98
10
0.5
0.001
0.01
0.3
2.60
0.7
0.001
0.01
0.3
3.09
10
0.7
0.001
0.01
0.3
2.88
1.0
0.0005
0.005
0.3
4,50
10
1.0
0.0001
0.001
0.3
21.98
10
1.0
0.0007
0.007
0.3
3.68
10
1.0
0.0003
0.003
0.3
7.28
1.0
0.003
0.03
0.3
0.83
10
1.0
0.0005
0.005
4.79
1.0
0.005
0.05
0.3
0.42
10
1.0
0.0007
0.007
0.3
3.30
1.0
0.001
0.01
0.1
0.59
10
1.0
0.001
0.01
0.1
0.45
1.0
0.001
0.01
0.2
1.76
10
1.0
0.001
0.01
0.2
1.34
1.0
0.001
0.01
0.4
2.66
10
1.0
0.001
0.01
0.4
2.92
1.0
0.001
0.01
0.49
2.00
10
1.0
0.001
0.01
0.49
2.04
1.0
0.001
0.01
0.3
2.20
10
1.0
0.001
0.01
0.3
2.51
To see how parameters impact the performance the algorithms, we conduct a series of sensitivity analyses, the results collected in T Besides, also conduct experiments to investigate the
16

---

Published as a conference paper at ICLR 2025
relationship between the problem's dimension and the time cost, the results shown in Figure
For these expriments, we set ?1 = 10. 722 = 1, 1.r=u 1, p = 0.3, and choose (ag, 7kk = (20 n, 2/n for problems with 1, (at: M7.) = (10/n. 1/n) for problems with q = 3. Such a choice is quite rough, but is sufficient to demonstrate the scalability of BiC-GAFFA.
Table 5: Sensitivity analysis on the hyperparameters for the synthetic experiments.
Settings
n 100, g =
n2 100, g = 3
72
=0.001
7 =0.01
-0.3
1y-12
10
0K =0.001
-0.1
AALL SOL
P 0.3
11 =10 =1
T 0001
O 0.001
71 =10
7/2 =1
P 0.3
A.2.2 HYPERPARAMETER OPTIMIZATION
Hyperparameter optimization is inherent bilevel optimization. According to Theorem 3.1 of Gao's work (Gao et al. 2022), we can turn the hyperparameter optimization problem of a statistical learning model which consists of data fitting Lasa and convex regularization terms Px(x) the following constrained bilevel optimization problem.
(x) S.t. X E argmin (Lx(x) s.t. P.(x) Sr. i 1,... J.. xER
min xER" .ERR
Sparse Group LASSO Problem. The sparse group LASSO problem (Simon et al. 2013) is an advanced statistical learning model, which aims find the grouped structure of the predictors and select the relevant ones. It is critical to select the weights of the regularization terms. The direct form of the problem is follows:
1
Σ bb
min BERP, AERM41
2
(21)
s.t.
B arg min
Σ
bb.
3T
+
Σ
Am
( AM+1 11811
BERR
ie
17

---

Published as a conference paper at ICLR 2025
By decoupling the data fitting term and regularization terms, we can reformulate the problem to the following bilevel optimization problem:
min BERM,EE
1
Σ i
lb, B²a.1
2
S.t.
BE
arg min
Σ 1b: 3'a=1
(22)
2
BERN
iEL
s.t.
11,((T)
ll2 S Tm. m I,...,,,, ||3 S TM+1-
From our practice, we find that the proposed BiC-GAFFA algorithm works better on the squared two norms rather than two norms directly, so by introducing u gM++1 such that Um r for m = 1,..., M, and Mar+1 TM+1, we can reformulate the problem to the following bilevel optimization problem:
min
Σ Fm
lb,
B D'a,l
BERF BEBP,UER"*!
2
s.t.
B E
arg min
Σ
b. - -Taaa" a,l
(23)
2
BER
iET (l
S Um m I....,M, M, || S uM++-
s.t.
Grid Search, Random Search, Bayesian Optimization and VF-iDCA are applied the model 22 IGJO is applied to the model (2T). and BiC-GAFFA is applied to the model (23) The experimental results are collected in Table
Data used in these experiments are generated by the following procedures: we random smapled a, E Rº from the standard normal distribution, and set the true weights / to be a grouped sparse vector, specifically, it was defined as /3 ( ..... (5)], where the first 5 entries of ( are 2, 3, 4, 5, and the rest entries are all zeros. The responses are defined as b, = 3 a, + de; where the 6, are generated from the standard normal distribution, and o is chosen such that the signal-to- noise ratio is 3. The training set, validation set, and test set are split randomly, and the size of the training set is denoted as nTr, the size of the validation set Val, and the size of the test nTees.. For all the experiments in this part, p 150, M 30.
g(2)
The detailed settings of each algorithm are provided as follows:
For Grid Search, and the range of TM+1 is 100];
the grid size to be 20, the range of rm is [1, 10) for 1.... M,
For Random Search, we set the number of iterations to be 400, the range of rm is [o, 10) for
I,...,, M, and the range of r'++1 is [0, 100), uniformly sampled method is adopted; For TPE, set the number of iterations to be 400, and use uniform distribution for each hyperparameter, the range rm is [0, 10] for m = 1, 1,..., M, and the range of ras-1 1 is [0, 100);
For IGJO, set the number of iterations to be 100 for each hyperparameter, and the initial guess is 0.1 x 1 M+1:
For VF-iDCA, we set the number of iterations to 50 for each hyperparameter. As to the initial guess, we firstly solve the lower level problem of (2I) with hyperparameters 0.1 x || ||, then take the as
1 1+11, denote that r. [|@((m)) || for =1 M, TM+1 the initial guess for the bilevel problem of (22
For BiC-GAFFA, we set the number of iterations to be 30000 for each hyperparameter, As to the initial guess, firstly solve the lower level problem of (1) with hyperparameters
0.1 1M41, denote that um = (m)))) || for m 1...., M, UM++ = || then take the u as the initial guess for the bilevel problem of (23) For this problem, we always take
71 10, ?22 1, Mp 0.1, ay 0.01, r 0.5, and p 0.3.
that BiC- outperforms other algorithms in terms of the validation error and test error, and when the number data is increased, the time cost of BiC-GAFFA does not increase significantly, which indicates that BiC-GAFFA is scalable large-scale problems.
From Table 6
18

---

Published as a conference paper at ICLR 2025
Table 6: Results on the sparse group Lasso hyperparameler selection problem.
nTr = 100, n aVal= 100, nTest 300
n'rr 300, n 300, nTesst = 300
Method
Time (s)
Val Err
Test Err
Time (s)
Val Err
Test Err
Grid
17.3 + 0.9
35,9 + 7.2
37.7 + 6.7
78.7
+ 1.9
18.9 + 2.3
19.8 : 1.8
Random
17.4 0.7
33.6 + 6.7
35.7
6.2
78.6
+ 2.5
18.7 + 2.4
19.5 - 1.9
TPE
16.9 0.7
3
36.0
5.6
74.7 - 2.2
18.9
19.8 1.9
IGJO
:.2
1.8
25.6 16644444
49.9 - 2.6
16.5 2.5
18.1
1..1
VF-iDCA
12.4 0.5
14.6
25.4
40.7
+ 1.7
14.9 + 2.1
17.2
1.3
BiC-GAFFA
0.7
7.3 = 1.3
22.3 3.0
22.0
1 1.0
12.8
+ 1.4
17.1
1.3
Support Vector Machine. The mathematical model can be written as follows:
CER WERF, WEERR..ERREERM (w.((,))
min
NOr Σ
s.t.
argmin
//l2
2 c c
WERF, SERF,,ER,EERA
s.t.
y: y:(w x; + 2 1 - Ei. i= 1...,
Here we use (Drr, D to denote the split of the training set and validation set of data, and N₂ to denote the number of data in the training set. The upper-level objective function is defined in the following way:
(- Ji((" x; + b)
(w,,(w,)) b) = Dvall
Σ (E
Sigmoid
[w]] |
The function inner the sigmoid function gives an opposite of a signed distance between point (x,, V:) and the decision hyperplane fx 12' w"x b 0}. Specifically, the inner part positive when the sign of the prediction w x; + is different with its label yi. and negative otherwise. And the sigmoid function converts the distance values to some probability value. Such a composition makes the objective function to be a smooth approximation of the validation accuracy.
The dataset we used in this experiment is the scaled diabetes dataset provided in the repository (Chang & Lin 2011), which contains 768 data points and 8 features. In each experiment, the training set, validation set, and test set are split randomly, and the size of the training set 400, and the size of the validation set is 150, the rest part is the test set.
The initial values of с in this problem are sampled from a uniform distribution on [-6, -5., the initial values for other parameters are solutions of the lower level problem with hyperparameters c. The hyperparameters for all the three algorithms are:
For GAM, we keep the same setting the original paper (Xu Zhu 2023 did, the maxi- mal iteration number is set to be 80.
For LV-HBA, we use a = 0.001, 7 = 0.001, 71 = 0.1, 7/ = 0.1, the maiximal iteration number is set to be 400.
For BiC-GAFFA, we 71 10, 72 0.01, 1/ 0.01, 10. og 0.001, P 0.3,
the maximal iteration number is set to be 5000.
Data Hyperclean. For this problem. we use the same model as the one in the SVM experiments, but we change the dataset to the scaled breast-cancer dataset provided in the repository (Chang & Lin 201T). which contains 683 data points and features. In each experiment, the training set, validation set, and test set are split randomly, and the size of the training set is 400, and the size of the validation set is 180, the rest part is the test set. For the training dataset, we change the label with probability P. 40%, and the validation set and test set are kept unchanged. This means the data used in lower training is not reliable, the researcher need to find out which data are more reliable and give them higher weights while giving the unreliable data lower weights. Such weighting process can be viewed as a data clean procedure. Here we such procedure by regarding the weights as hyperparameters and evaluating their effects the validation such process is regarded as data
19

---

Published as a conference paper at ICLR 2025
hyper cleaning. Therefore, such problem is quite similar to the aforementioned SVM, the main difference occurs in the training data.
The hyperparameters for all the three algorithms are:
For GAM, we keep the same setting as the original paper (Xu & Zhu 2023) did, the max-
imal iteration number is set to 30. The initial values of с are chosen from uniformed distribution 2.).
For LV-HBA, number is set to 400. The initial values of с are chosen from uniformed distribution (-5, -4);
0.001, 7 0.001, 71 0.1, 72 0.1, the maiximal iteration
For BiC-GAFFA, the maximal iteration number is set to 2000. The initial values of c are choosen from a unifromed distribution (-5--4)
" 10, 72 0.01, 7/s 0.1, 0g = 0.001, 10, p 0.3,
A.2.3 GENERATIVE ADVERSARIAL NETWORK
We also apply our algorithm the GAN, which is popular model in the field of deep learning. can be written as the following bilevel optimization problem:
min Egen DG s.t. E argmin DED (G, G.D
The main idea of GAN is to find a network that learns the distribution of the given training data. This paper investigates the fitting of two-dimensional distributions (i.e., 8-Gaussians model and 25-Gaussians model, refer to Gulrajani et al. (2017)) using GANs. For such simple distributions, approximate the earth mover's distance (EMD) between the generated distribution and the true distribution by calculating the Sinkhorn distance (Cuturi) 2013). This allows us to observe the optimization progress of the network during the iteration process, and make comparisons between different strategies.
COAT
LEAC SAAPAL Ohr DAN
MELES
Figure 6: How EMD changes w.r.t time for different GAN models. The true distribution in the left picture the 8 Gaussians mixture model, and the true distribution the right picture is the 25 Gaussians mixture model.
For all the 8 GANs make comparison here, though the loss functions exhibit slight variations. The generator and discriminator are both three- layer neural networks with 128 hidden units, and the activation function except the last layer is ReLU. The output size of the generator is 256. For the WGAN and WGAN-GP, the last layer of the discriminator is the linear layer while other models have a sigmoid activation function after the linear layer in their discriminator. The batch size is 512, and the number of iterations is 2701. According train the discriminator steps and then the
similar structures and similar parameters,
the practical advice in Gulrajani et al. (017). generator 1 step in 1 loop. We use Adam with 51 = 0.5, 62 = 0.999 for all the learnable parameters all the models. The specific objectives and additional parameter details are listed below:
GAN (Goodfellow et al.
2014
Egen (G, D) = =E,- [CEELsss (BBCLLoss((((())) 1,.)],
Laa(G. D) = Ex-P, [BCELoss ((x), 1,)] +
2 Ez-n (BL=:BBCELoss((((i())) 0,.)]
We set learning rate of generator 10-3 learning rate of discriminator 10-4
20

---

Published as conference paper at ICLR 2025
WGAN AArjossyy et al. 2017):
geau (G, GG,DD D) = Ex (D((())
Ex Ba.
with a box constraint that | Σ Celip- We set learning rate of generator as 10
learning rate discriminator as 10-1, the clip value as 0.001;
WGAN-GP (Gulrajani et al.
2017):
Leg (G, D) -x ((G
Caer Cae(G, D) Ex~,, 2x=,, E + P 1)?
where Ayp is the parameter of gradient penalty, and Px is defined by sampling uniformly along straight lines between pairs of points sampled from the data distribution IP, and the generator distribution P. {G(z)]z E N}. We set learning rate of generator 10th learning rate of discriminator 10-4, lambda of gradient penalty as 0.1:
Con-GAN (Chao et al.
2021):
Egen (G, (G,D) D) =E EEg.N
BCELoss (z)))), 1.)).
(G, =Ex-F, BCELOss (x)), 1,)] E (CCLL AM D),
where
L(G, D) == Px (log(((()))))))))) log D(G(2)))
We set learning rate of generator as 10-3, learning rate of discriminator as 10-4, lambda constant penalty as 0.3;
UGAN (Metz et al.
2016
Lgeal (G, D)
=B Eg [BCEL)s(D(((()). 1,)],
Lael (ae D) Exn=, [BCELoss((xx) II.)] -EZ.N (C
We set the learning rate of the generator 10-3 the learning rate of the discriminator as 10-4 the unrolled step as 5 and let it update the discriminator just step in loop;
Bi-GAN (BiC-GAFFA):
Leen (G, D) -E [BCELos(D(((())) I1,)],
LGa E Ex [BCELos(((x)) 1..)] + Ez-N BBx.N/BCELossD(GGGaa
We set the learning rate of the generator 10-3 the learning rate of the discriminator as 10-4, p 0.1, the learning rate of the auxiliary generator as 10 10-3 the upper bound for the auxiliary dual variable (r) 0.1;
Bi-WGAN (BIC-GAFFA):
Eyen (G, D) Ez~N (D(G(z)),
Lae(G, D) -- Ex [D(x)) + Be->
with constriant
max
VD(x)]12 < R
where P& is defined by sampling uniformly along straight lines between pairs of points sampled from the data distribution P, and the generator distribution P, = [G(z)]z N). We set the learning rate of the generator 10-3, the learning rate of the discriminator as 10-4, r 0.1, = 0.1, the learning rate the auxiliary generator as 10-3, the learning rate of the auxiliary dual variable 10-4, the upper bound for the auxiliary dual variable (r) as O.1. Note here we turn the gradient penalty introduced in Guirajani et al. (2017) constraint by taking maximum over the sample points, and by practice, the original GAN structure seems more stable with this optimization method, further study is still required;
21

---

Published as a conference paper at ICLR 2025
Bi-CCnnAN (BIC-GAFFA):
Egen (G, -EE [CELoss 1n)],
Lda (G, D) = -xx- [BCELoss ((x), 1.)] + Ez-N (DCiLsss
with constraint
G(G, =
(x()) log D(G(z)))
We set the learning rate of the generator as 10-3 the learning rate of the discrininator as 10-1, 0.1, the learning rate of the auxiliary generator as 10-3 the learning rate of the auxiliary dual variable (r) as 10-1, the upper bound for the auxiliary dual variable as 0.1. We realize the constraint proposed in Chao et al. (2021) with 0.1.
Different analyses and assumptions lead to various regularization requirements for these models. When constrained optimizers are unavailable, such a regularization method can only be achieved by penalizing them to the objective (Gulrajani et al. [0017] Chao et al.) (02II) potentially compromising the interpretability of the model and complicating analysis. Our algorithms mitigate these issues without significant computational overhead. The effectiveness of our algorithms is demonstrated in the numerical results presented in Figures
A.2.4 ADDITIONAL NOTES ON NUMERICAL EXPERIMENTS
Computational and Memory Considerations
We acknowledge that the introduction of additional sequences, such as 0₂ and Åε. does contribute to increased memory usage, which can present challenges for large-scale applications. Addressing this limitation and exploring ways to reduce the storage requirements is an area we plan to investigate in future work.
In terms of computational complexity, while algorithm introduces additional computation, empirical results suggest that these additional calculations contribute to more effective model op- timization. This added complexity, in many cases, proves competitive and can lead to improved convergence and solution quality. Moreover, from the perspective of numerical implementation, our method offers notable advantages ventional approaches, our algorithm does not rely on nested loops or matrix inversion estimations, which significantly enhances computational efficiency. Additionally, when handling lower-level constraints, our method avoids the need for complex projection steps.
traditional bilevel optimization algorithms. Unlike
However, recognize that large-scale applications of bilevel optimization, particularly those with lower-level constraints, remain in their early stages due to the lack of efficient solution tools. We believe that our work provides step toward developing more scalable and efficient approaches for these complex problems.
Scope of Current Experiments
Our experimental evaluation is primarily focused on toy numerical problems and small-scale real- world scenarios. This limitation was partly due hardware constraints and the challenge of identi- fying suitable large-scale models that align with our problem framework.
However, we recognize the importance of demonstrating the broader applicability and scalability of BiC-GAFFA. We are actively working expanding research to include more comprehensive evaluations on larger and more diverse datasets. This will allow us to better showcase the practical potential and robustness of our algorithm in real-world, large-scale applications.
A.3
PROOFS IN SECTION 2
A.3.1 PROOF OF LEMMA
be proved using proof techniques similar to those in Theorem 3.3 from Von Heusinger & Kanzow 2209)). For completeness, we present an alternative proof of Lemma 2.1 here.
Lemma 2.1
22

---

Published as a conference paper at ICLR 2025
Assume that both f(x,-) ) and g( -) are convex for any given Z E X. Let 2, 0, we have G, v. y, 2) 2 for any (z, y. 2) E x Y x R. Furthermore,
Lemma 2.1
(r, =) S 0,
if and only y E S(z) and E M(z,v), where M(x, y) denotes the set of multipliers of the lower-level problem at (z. V), i.e.
M(x.v) = {XE R I VVEVyf(a v, V Ve + Nv) N (( 0}.
Proof. For any (0, Y R.p have
min PEY
f (x. 0) + 2 (0 0) + 271
110 y/1²
$ f(r, y) + 2 (())
(24)
s max AER
f(z, v) + X ()g(E.)) - || - =112
272
which implies that
(x, = max AER
f(z, v) + -xgg(z,))
- M| 2/3
272
1
min
[xx; () =² g0, 0) +
100 y/1
BEY
2
20.
Therefore, (1, y, = 0 if and only if
1
1
max AEPP
f(,,8) + x 92z,)) 272
11 21|
min min BEY
f(z, +30
110
y11
2
Then,
24
yields that (z 2)
0 if and only if
y E argmin BEY
f(z,0) 0) + 2 (x +
1|0 y1
2
(25)
1
2 E argmax XER
f(x, y) + x 9
a - z|1?
272
Given that the function f(x, 8)
+ xT (rg 0) is convex with respect to variable 8 and that A gx 8)
is concave with respect to A, 25 is equivalent to
E argmin (f(2,0) + [g(2,
dEY
(26)
E argmax (f(r.v) X (x)()))))
XER
which is equivalent to that (y, 2) is a saddle point to
min max f(x, 0) + X (z. WEY XER"
Consequently, applying the classical minimax theorem to this convex-concave min-max problem. we obtain that G- (2., y, 2) = 0f and only if y S(z) and z E M(x.g).
A.3.2 PROOF OF LEMMA 2.2
Lemma 2.2 Assume that both [(x, y) and g(a,y) convex in on Y for any given X and are continuously differentiable on an open set containing X x Y. Then (x y. is continuously differentiable on X x WRP and for any (x,y,2) 2) E X x Y R.
V.I(I,y)
Va. (2, 0*) + =VVag(e 0+)
(Z, = V (yl(I,y) (At) V
(x,
(y - 0³) /m
(2 X²//22 /T2
g(z, 0-)
23

---

Published as a conference paper at ICLR 2025
where 9r and X* denote #* (z, y, and (1, y: 2). respectively. defined as
1
M* (2, argmin YEY
f(z, fz + g(r, +
10 vl1
2/1
1
(2 argmax AER
+ g(
|| z112
Projæy (2+ + (29(2.1) y))
2712
Proof. We first define two auxiliary functions,
1
(1, = min DEY
f(x, (6.00)+22 + +zzggzz000 ((xx0))))))))000))))) 0)+
- 110 - y/
271
G2 (2, = max XER
[xx + x Ngr,,y) 2722
|| =1?
Then, it follows that (v y, 2) G2, (2,, v. (I, z). Since by assumptions that f and are both continuous differentiable on an open set containing X x Y, it can be easily shown that f(x 0) + 2=x 0) + 27
-.1111 110 y/1² satisfies the inf-compactness condition in Theorem 4.13 of Bonnans & Shapiro (013) with respect to E Y on any point (7. M) E X x Y x RL, i.e., for any (ž, 2) E X x Y x IR4, there exist c E R. compact set D and neighborhood W of (z, T. 2)
such that the level set {0 E Y [xx, +)+ 0) + शम 110 yll² I c) is nonempty and contained in D for any (z. 2) E W. And because of the convexity of f (z, y) and g(x, y) with respect to E Y for any E X, argmin (fx,,) 0) + 2 g(z, 0) + 2% ||0 y||3) is a singleton for any BEY
(r.y,2) E x x R. Then, by the differentiablility of f and we can derive from Theorem 4.13, Remark 4.14 of Bonnans Shapiro (013) that G1,, (z,, y. 2) differentiable at any point on R.
X x Y x TR and for any (I, 2. x
VG,,
(V (v= 0*) + VV (a, 0²). (y 0*) /n, /m,g(1,0 0').
(27)
By using similar arguments, we can also demonstrate that G2, (x, y. 2) is differentiable at any point on X Y R. and for any (s, v, E X x x R.p
VG2,, (z, y, 2) (V. + (X*) x y), V Vyl(z, + (A*) y (z- k²)/72)
(28)
And then the conclusion follows from Gz y, 2) = G2 (z. v, G (x, 8.
A.3.3 PROOF OF THEOREM 2.3
Theorem 2.3 Assume that both fxx, -) and g(x.-) -) are
are convex for any given X. Let 0,
the reformulation (6) is equivalent to the bilevel optimization problem 7 provided that for any
feasible point (x, 1) of (7), a corresponding multiplier of the lower-level problem (2) exists at (2,
ie.. M(x, 3) + #0
Proof. Let (xr, y, 2) be any feasible point of problem (6). then we have (x, y) E X G,,,,,,) < O. And it follows from Lemma 2.1 that (x, feasible to bilevel program
R. (x, y, 2) = 0. S(x) and thus (x, v) is
Now, suppose (Ir is an feasible point of bilevel program (T. then we have (x, E X x Y and y E S(x). According to the assumption that a multiplier 2 E R² of the lower-level problem 2 exists at (z, i.c., E _M(z, y). Then it follows from Lemma 2.1 that (z, V, 2) 0 and thus (x, y. 2) is feasible to reformulation problem (
A.4 PROOFS IN SECTION 3
A.4.1 PROOF OF PROPOSITION
Proposition 3.1
Suppose m. 72 > 0 and an optimal solution (x* y" 222") to 6 with x" E Z,
exists, then any optimal solution of 7 is optimal reformulation
24

---

and Published as a conference paper at ICLR 2025
Proof. For any feasible point (z, y, 2) of problem 77 (xx, y, 2) is also feasible to problem and thus the optimal value of problem 7 is larger or equal to that of problem (6). Let (a V be optimal solution of reformulation problem (6) with x* belonging to the set Z, then (a" y is
also feasible to problem (7) Therefore, the optimal value of problem (7 equal to that of problem
(6). Then, because any feasible point (a, y; 2) of problem (7 is feasible to problem (6), we get the conclusion.
A.4.2 PROOF OF PROPOSITION 3.2
Proposition 3.2. Assume that F(x, y) is bounded below by on X X. For any E > O, there exists O such that any global solution (Fey Yes 2e) the penalty formulation @8) with penalty parameter 2 ē is also a global solution to the relaxed problem (9) with some relaxation parameter ee satisfying & Moreover, (Fer ye: ze) is a local solution the penalty formulation (8) then it is also a local solution to the relaxed problem ( with relaxation parameter Ee == ( Vey Ze).
Proof. Let (z. 8) E X X xXxxx x Z be a feasible point to problem (7p and (Ies Nos z0) E X
be a global solution of problem (8) with penalty parameter > 0. We then have
F (ates + e ( yes ze) S F(..8) 1) + e (T, U.
F(2, W).
implying
(Fe Nes ze) S (F 0) E)/c.
Thus, for any & > 0, there exists ē > O such that for any c 2 C,
Ec (T Ve: ze) S..
Next, we demonstrate that (Ies No: =e) is a global solution to problem (9) with relaxation parameter eo. Assume, for the sake of contradiction, that there exists (I, X Y Z with (2, s Ec and F(x, y) < Fzze: Vc). This leads to
F(x, v) c 2) F(re, Me) + CE. F(re; Me) + (Jies Mer ze);
which contradicts the global optimality of (Zex yo: ze)to problem (8) with penalty parameter e >> 0.
By analogous reasoning, the assertion concerning the local optimality of (Ie, Mos =e) for problem 8 holds similarly.
A.4.3 PROOF OF THEOREM 3.3
Theorem Assume that X and are closed functions F, and are continuous on X
Suppose Cje
and let
(rk, Uk. 2x) E argmin
F(x, y) c (x(,,y,)).
(x
Then, any accumulation point (ā. D. E) of the sequence ((Ts, Uk. =x) is solution to problem
Proof. Applying the proof techniques used in Lemma of Liu al. (020), we can establish that (xr yj z) is lower semi-continuous on X Y 2. The theorem's conclusion follows by employing the same proof techniques from Theorem of ofLiu et al. 2020).
A.5 PROOFS IN SECTION
The proof of non-asymptotic convergence for BiC-GAFFA primarily hinges establishing the sufficient descent property of the merit function defined as follows
Vi= der (x nx 2 Co ||0
0 (2 4r 2 112
where
6ec (z, 22, = (F(x, (x y)
F) + (I, y)
Ck
1
Co : (Lg + r
+
+ I
711
25

---

Published as a conference paper at ICLR 2025
To establish the sufficiently decreasing property of the merit function, we initially derive several cru- cial auxiliary lemmas. These lemmas establish the Lipschitz continuity of 0* (z, y, 2) and X (æz y, 2) (as detailed in Lemma A.II, the Lipschitz continuity of VG, (z. y. (as detailed in Lemma A.2 and descent property with bounded errors for the function den, (z, y; 2) at each iteration (as detailed in Lemma A.4)
A.5.1 AUXILIARY LEMMAS
The Lipschitz properties of 6* (z. y, 2), X (x, 2) and VG, y, 2) are crucial for the convergence analysis. We establish these properties in the subsequent lemmas.
Lemma A.I. Under Assumptions 4.2 and 4.3 and let 7/2 > 0, 7/2 > for any (a, y, z), (x', v/ 2²)
X x Y x Z, the following inequalities hold
|10 (z, 2) - 60 (x', ,'''v',20 ,''1' S (71 T.g + + (1 || - x'll + 1y w'll + 1-gl=== z'11
- Lo (z,, V. 2) - (a', 2')ll,
(29)
(2,)) - (1 8'' x') S ا [1, y) - (x' + 1112- =211
- LA (2z, y, (ee, "'',8'=2)11
where Lg == v3 max (n + nr 1, m lng) and L, = /2 max (maxx(122..) (12 1}.
Proof. To simplify notation, we denote (I. y. v.. (x' .y, z') XxX by w and w', respectively.
Considering that 6" (w) and X (w) are optimal solutions to optimization problems in (5) it follows from the stationary conditions that
0 E vzf(x, 6 (w)) + 2" V V00 (w)) + (0" -
(30)
0 E g(z + (X* (X"(w) 2)/12 + Nop (x)).
Same results apply to 0* (w") and X (w')
0 E vyf((', (w")) + (z') ,0(2,, (w)")
(31)
0 g0' (2~ 21)/12 + Na; (X^
Defining
Tx,,3,2, y. 2) = Vo (f(z, () + g0 (xx +)
1
100 y/(
2?1
and exploiting the monotonicity of Ny, we have from 330 and (3T that
(ww, 0* (w:) + T(w, 0* (w') (w')), 00 (w) - 0* (w'))
(32)
+ ( (-w, 0- (w") )} + T(w,, (w") )), (w) - 0 (w ()))) 2 0
Under Assumptions 4.2 and 4.3 and given that 7/1 > 0, it holds that for any (z, v, E X XX x R.
[(x, 0) + TT g(, 0) + 271 0 y/l
is -/ -tronnyyyy convex with respect to 0. According to Rockafellar & Wets 20099, T(x, v. 2) is s/ronlly monotone. Consequently, we have that
(T(w, 0" (w)) T(w, 0* (w""), 8* (wr)) - (w())) 2 (00(ww) - (w/))l//
(33)
Under Assumptions and we establish that
- T(w, ( T(w', .0 (w'))(
< [2, - V,f(a', 0* (w
+| - "V (w/))l + +l 1/1//m
< - V ~V ('''))
+ VIl="V (w') (=') 30(و6 ( + 11 - ~11//
-/1 2'11 2 + lll wlm//,
26

---

Published as a conference paper at ICLR 2025
where the last inequality follows from the Loz Lipschitz continuity of vg on X x Y, m y.Y Vvg(z.))) I Lg. (z', ( E X x Y and 2 E Z. Combining this inequality
with 32 and (33). we have
- 0ww)) S (T + m || x' 11 + 1lv s'1 v 11= 2'11.
Further, exploiting the monotonicity of Neg. we obtain from (30 and
31 that
(g(x, + (= - (2w))/722 - g(x' y/) - (z' - x² x (w) (')))) 2. Then, invoking Assumption 4.3 we have that
(34)
- - X-w''Il 12 v) - (x', vy' Il + ||= - z'11-
Lemma A.2. Under Assumptions 4.2 and 4.3 assume that X, are compact sets, and 71 > 0,
12 O. Then, there exists Lg 0 such that for any points (2, (x,, V 2') E Xxxxx x Z,
Vg, (1,,(,
'Ill T,]l(x,,,2))
and
L U. 2)) +
(2' v/'. (V -x,,
((x, y, 2) - (a', ,
2
Proof. For conciseness, we denote (æ, y, z), (,', Recalling from Lemma A.I we have
y' 2 E x x Y x Z by w and w', respectively.
[10"(w) 0" (ww')l s Lo ||ue - w'll [|, (w)(w)) X x² ||| S Ia-lw- w'll.
(35)
As specified in (5) the norm of X (w) is bounded above by
[=>[w)]| = ||Proize (a + T29(1, w)) || S || + 729(z, y) +r+ V X
where Mg == max (19 y)ll. Drawing upon Lemma 2.2 Assumptions 35 for any we w/ E X x Z, we have
4.2 and 4.3 and
(w) - (w')(
< (VV v) - V.f(2' . +
I''l (w)) - VV'"Vng(('" 0 (w'')))
+IX((w)VVe9(xx))) |1 8/) X2 (w)) "iuo)"TVollee Vag(z' //))l
- [z]]
Lo ||
( (w')))
< <</'
+ (k
Lg -| w'll
+ + -'11 + -o w'1l + L ||2 =/11,
where the last inequality follows from 0² (w") Y, 2 E Z and max V v)ll Ly- Similarly, for gradients with respect to and z, for any w, w/ E X x Y x Z, we have
|1 (w) - (w')l'))
< <IVV)(IZ,)) V,f(z', II)
X" (w)) V Veg(x', R')ll
1 lly w'll + m
+
- (x 10 s/)l +11
100 (w) - (w')ll
$L v) (x'.0)) + (r+ 722
9b
|1 xx. v) .''l
1 |1 w1l
1
+ Txwl - w'll +
+
Lø w|w w'll.
71 71
27

---

Published as a conference paper at ICLR 2025
where the last inequality follows from the fact that max Vug(z, v)1l s Lg. and
V=
v-Sy(w')Il
- 2| 1111 + [1((w) - (-0(")) 11, (w)) g(x', (0 (w''))l
72
72
-1 ||2 111
| w| w'll + Lo || 2'11 Lo w w' ||.
7/
72
The above inequalities together yields the existence of constant L.g > 0 such that
(I, - VG, ,/'l')1== S Le] (x', y = =
Then the conclusion follows from Lemma 5.7 Beck (0117).
The update of 0² constitutes a single gradient descent step to the minimization problem defined in (). The progress of this update is quantified in the subsequent lemma.
Lemma A.3. Under Assumplions
4.2 and
4.3
let 71 > O, 722 0 and T/s E (0, + rbgs + generated by Algorithm satisfies
1/m)), then the sequence of (x
0" (~ 1
3. >
(1 /////) 0" (x )1
(36)
and
x++1 = x0(xh,1/ 2²
Proof. Consider (a", (a","" ,²,=²))))))))) E Xxxxxx For brevity, we denote 0* (x*t, y a and X X= 3 )*)
by l and X², respectively. Under Assumptions 4.2 and 4.3 and given 7/2 O, the function
f(a + (2 )T g(a* 0) + 2-1 10 1/,
is 1 strongly convex and (L, + r rgg + 1/7))///////))n)) smooth with respect to B. invoking Theorem 10.29
of Beck (2017), we obtain
100+ - 0-1 < (1 Th/71) |10 - 1-
Additionally, according to it follows that x++1 = X
The update of variables (x, y, 2) in 14 can be viewed as an inexact alternating proximal gradi-
ent step from (a y 2²) on solving min( x x dcg (z, y, 2). In the lemma below, demonstrate that the function d.a (I, v,2) 2) exhibits a decreasing property with bounded errors at each iteration.
Lemma A.4. Under Assumptions and
assume X, Y are compact sets, and let m > O, generated by Algorithm 7 satisfies
22 > 0. Then the sequence of (x*
6t.
Ler
des (1+ 1ttt 2t1) S Dee (ot " x/
[[(att1, (ittt,ytt1 , - (x v²t 2112
20x
+
ak
Ls + Uz uzbng + 79
1
+ Lgg)
02t1p1
2
(37)
where Lon == Lp/ck + Lgg.
Proof. For clarity, we denote (a y* 2²)), (a+-11 , x+11 as w and ++1 respectively. Under
the Assumptions 4.2 and 4.3 where V and Vf are LF- and Ly-Lisschizz continuous on X x Y. and applying Lemma 5.7 of Beck (0117) and Lemma A.2 we obtain
dor 11 . x+1) & dey (I* y 2) + (Voce (x* y 2*), (a*+1 se , - (a+, . )²,)
Loz ||att],, y 2et1) - (a* ", 201,
+
2
(38)
28

---

Published as a conference paper at ICLR 2025
with Loz == Lp/ck + Lg. Based on the update rule of variables (z, y. 2) in
14). the convexity of
X x x Z and the property of the projection operator Proj x x x we have
(at,,,,= - (x dr db.) (x++1 yett, , =h11,, (x ,² (x (x y gh , =))) S 0,
yielding
((dt, dy d (attt1, yhti, ( s - (at, B (²)))
1 [|(altt -yht x - (x* 3 211
Onl
Integrating this inequality with (38), we infer that
Dca (xhtt1 , s Dea (s* ,², - (1 Lox
2 l((ahtt . ghttl , - (0 , ,²,,²²) )11
+ @e (x v0 2t) - (d di. de), (xttl , ,ttt - (z* v.t =²1)
(39)
Furthermore, considering w X Y Z and with 0" (w*)), 0h E Y for all k. and utilizing the formula of VG, (2, ys 2) derived in Lemma 2.2 along with the definitions of g. d and di in (3)
and x *+ = (w= from Lemma A.3
can obtain from Assumptions 4.2 and 4.3 that
V (xt yr =t) (di, d'el
( 5t 2 Vzf(e*, yh) ( //t Vef(a" gctz) + "
V (1 s x*) - Vys(e* ,2²) - (A Vugle"" .1t) + (v* - -0tt2//711
+ ( 33/ x²) + (=* ( 1/12 + olat,atti gh+
- V w/) (1 ++ ) 'V =f w²)|| || + Vaf(e (af(=",0(w")) V Vzf(E* ,0+
[|(==*)\V ( (=*) Vvg((" |b+1)||
||> Vgg(t x² (A Vv
v9(a* w²)l| + 71
_ |10 -0--111
|A((w*) x+ 1| + 11g(0*, ('()))) = .h+1|||
72
1 100 (w*)) 10 + L, 100((())) - gc+1
< <b, (w0)) - 0++ + rLos (w*) gl+l|| - 71
- + - + Lig) (10( gl+||l
(40)
This yields that
(Vor, (xt,y²
". 24) - (ite de), (
, , (t1) (x* * ,/ ,211))
< Ok 2 L ( + 1 _+1,)
- 01+111 + 2ork
|1x0/et1 1/ 1 xb11) - (xh, )*),
71
Combining this with (39 leads the following inequality
Lope
des (a n 2lt1) S Dee (xx y ;² 20x
[1(aatt
Bockt,,yatt yutt 2b11) - (a* 20,1
2
2
ak + Los+ rhy
110 -0tt212
2
71
(41)
A.5.2 SUFFICIENT DESCENT PROPERTY OF Vi
Utilizing the auxiliary lemmas established previously, we now proceed to demonstrate the sufficient decreasing property of Vz.
29

---

Published as a conference paper at ICLR 2025
Lemma A.5. Under Assumptions 4.1 4.2 and 4.3
suppose X. Y compact sets, "1 > 0, Y/2
and Th E (7. [n + Lg + 1/71)) with y > 0. Then there exists Ca > 0 such that when
0 < Or I Cas the sequence of (x" nrt 2², gh, X²) generated by Algorithm satisfies
V&+1 V/ S
1 k+ wh w²12
CC 110t 00 (11")11
(42)
4a
271
Proof. For clarity and conciseness, we represent (x* ,", 2*),, (2++1 y , 1) as w and w++, respectively. Recall (37) from Lemma A.4 that
Des k+ /3 pt1 , ) S (x","" ,²*)=* ( 200
Loe
[[(abtt,, " , - (x* vx" ,
2
2
+ ak
L u Tbys - + (1
110",0", 01-
71
(43)
Given that ck+11 2 Ck. it follows that (((aa-1,,//tt F)/ck-1 S (F(x+t1 ((tttt,,*tt) F)/ck. Combining this with (43) leads to
V&+1 Vi= = Dents (w Dea (w=* + Co ||0kt1 -0 100001-00000000 [m]+ -o fl0 - (w+))
S Dea (w
Den (w*) + Co p|lkttt 0² (w - fl0 - -0" 00(())]l'
1
Ldve
| - -2 Co ||ghtl - 0 (w - Co 11 - 0 (1=
200k
2
1 + 110) 2 [10()²+) - 01t211
+ Olk
T.f + rlon +
2
Todn
) | - w 12 Co |lght1 - or (w -Co 11 - (
200k
2
ak Co (10 - gh+211
+
2
(44)
+ Lg) Further, we can where the last equation follows from defining Co = (L, + rLg, + 1 n demonstrate that
1 8" (w 2 - 1100
0r (1+))| + an 10 ( -
11+
2
<(1 + cx + ax/22) ||ghtl - -0" (w^))) )|2
-110t 2
0 (1*))| + (1 + 1 >110 (w*+t)) 0" (2)
EK
< + c + as a2/2)(11 (1//2)/m/11)))))) ////1)1l0* 8 (w*))" - -100 0r (w (w0)|| + (1+ L3 |
wn 112
EK
for any E > O, where the second inequality is consequence of Lemmas A. and
A.3
By setting
c / in the above inequality, we obtain that when O% I m 7/1 the following inequalities hold
(1 + ek + ax/2)(1 nk/1a) S (1 + nh/ n///1)(11111 ma/1)) $ 1-
1
7
2
Consequently, establish the inequality
||0ht1 0r (w (w+
-1100 0¹ (w("\\/²== + |10(w(*) g1+t211
<
nh l10t
0t (w>
(1 1 471 LB / - w/1
(45)
2x1
17x
Combining (44 and (45) implies
Ve+1 - 1/2 S
Lou
1
471
| -w w
no
11th
8"
(w
2ax
2
2
(46)
30

---

Published as a conference paper at ICLR 2025
When Ck+1 ck. 7/ 2 ?
0, 02
////1. it holds that for any k, as S n///
LoR 2
+ 1+
471
LiCo -
Leu
+
(1+
4n
LgCa = Ca.
2
Ca > satisfies
c, min
2 5m/m 4C
then, for 0 < 0r: S Ca. it is guaranteed that
Lox
(1+
4h
1
LăCo 2
2aq
2
40x
Therefore, the conclusion follows directly from (46).
A.5.3 PROOPS OF THEOREM AND THEOREM 4.5
Indeed, Theorem 4.4 is special case of Theorem 4.5 with p 0. Consequently, we present proof of Theorem 4.5
Under Assumptions 4.1 4.2 and 4.3 assume that X, Y are compact sets, 0, c(k- + 1) with e U. 00. 1/2) and T7 (n) 1/(L/ + rLgg 11/1)) with q > 0. Then there exists Ca such that when ag E (a, Ca) with a > O, the sequence of
Theorem 4.5
72 0, Ck
(x s 2 ,0 (²) generated by Algorithml Natissies
min ||0t - (x* ... ,/,,=/)1== 00 OSASK
K1/2
and
min OSkSK
Ra(x+t1 gttl + (<1--2)/22
Furthermore, if > 0 and te (x*, s 2 is uniformly bounded above, then the sequence of (x* s 2 satisfies
1 KP
S C1(K kk 2 xx) 0
Proof.
Lemma A.5 establishes the existence of Ca
such that 42 holds when og Ca. Sum-
ming
42
over
0, l...... K - 1, we obtain
K-1
no 11t 00 Se,,e,, "/f"=*)1
||x y x+1 , (2 "y 2 1| +
4a
2n1
(47)
km
Vo/
VK < Vo.
where the last inequality follows from the nonnegativity of Vk. Consequently. it holds that
Σ |10h 0z ., )112 < co. k=
and
|0t 0 (x* ( ,,, O
min k
K1/2
According to the update rule for variables (I, y1, x) in 14 derive
e (d d d + -Xxxxxz F+1 y+t x+
Ck ((*h+t) h+l xkt) 1 x²))))).
ax
(48)
Following the definitions of dh. di and dh in 13 we obtain
V Viee (+1 y b Nxxxxx ( (4t1),
31

---

Published as a conference paper at ICLR 2025
where
cx = Vilce (x , ck cx db) Ck ((xh+1, yft 2ltt1 - (x 241 (49)
Next, we estimate ||e We have
||_|| & VV h1 yhtz 2ht1) Velca (2* y 2*, + VVV (2 ,g (/,22) - cs cx( dr d!)1
Ck [[a htl =tt) - (x* sf. ,
For the first term the right hand side of the above inequality, by using Assumptions 4.1 4.2 and along with Lemma A.I establish the existence of Ly == LF + Lg > 0 such that
V Vecc Vog (+1 3 t x+1)
Vita (a , 2* S cowvl(I , (tt) - (s* y² 2*)
Using 40 and Lemma A.3 we have
Viloe (x", y x²) cx (d de. d cc |i (2t) , =² - (d dh. dt)1l
Sc 110 vt v ;²t)) gk+z||
(50)
Sc 110 , 24) 0² 11.
with Cs = (Leg + rlon + 1 + Lg)3. Consequently, we have (x v 2*)]]
31
|et|| S ScLooll>>t ,
ak ||(o*t1, | , - (0".v* ,*,"
+ Co 1100 ,"", , x²) --2--00 - 0011.
Using this bound on ||e/||, we have that
(x xx +11 scu (Ly + 1 1/az) |1xtt1 yetl xht2) (x 5 2*)
+ 110 (at , 3 20) gh||
Utilizing this inequality, and given that ag E (a) for some positive constant o, we can establish the existence of a constant On > 0 such that
1 Ru (at nt1 24222
(51)
sCn -laahtt , xtl) - (1* ,0
no 1 0r (x " ,,,,,,=,113 ++1)) 2y1
4ax
This inequality, combined with 47
implies that
(zk+1 ykt2, ghtipe < 00.
(52)
k=
k
Because 2p
< 1, it follows that
K
= K
20
1
R+2
1
(KK (K+2)
-1
Σ
dx
2
x
c2
1-2p
2
k=
k=
leading us to conclude from that
2
min oskgk
2+1,2t11) [t1)== =
K(1-2p)22
Given that tieg (a* , x² < M and F(a*, .x²) > F for all k. it follows that
Ca (a+ y² x²*) s M F. Vk.
From 4 = c(k: + 1)8 and p > O, we can obtain that
1
G " ,²²k) 0
KP
32

---

Published as a conference paper at ICLR 2025
A.6 EXTENSION BILEVEL OPTIMIZATION WITH MINIMAX LOWER LEVEL PROBLEM
In this part, we explore the extension of our proposed gradient-based, single-loop. Hessian-free algo- rithm, originally designed for bilevel optimization problems with constrained lower-level problems, to bilevel optimization problems with minimax lower-level problem,
min IE TEX.EEY,
F(x y,
s.t. (v,2) SP(x),
where SP(x) denotes the set of saddle points for the convex-concave minimax problem,
min max far v) DEY =E
where E R", R and 2 RP, the sets X, Y and Z are closed convex sets in R R" and IR, respectively. The UL objective F X x Y continuously differentiable with f being convex in y and concave in x. Building upon the idea applied in the development the regularized gap function (3. we introduce the doubly regularized gap function for lower-level minimax problems, defined as:
+ R, and the LL objective f : x x + R
graddle (x, V,, = max {(1, - || - =112 f(x, 0,) 2/2
_110 -110 w1l? 2711
DEY,AEZ
By employing proof techniques analogous to those used in Lemma 2.1 or Theorem 3.3 from Von Heusinger Kanzow (2009), we can derive similar results for the doubly regularized gap function Gxpdddleex V.
Lemma A.6. Assume that f(x, y, is convex in y on Y for any given x E X, Z and concave in z on Z for any given x E X,y E Y. Let 71, 72 > O, we have Graddle (x, y, z) 2 0 for any (r, 2) E X x x Z, and
guaddle (x, 02 00
if and only if (v. E SP(x).
Similarly, utilizing the proof methods in Lemma
2.2 we establish the differentiability of
gaaddlo (z, 2) and derive the formula for its gradient.
Lemma A.7. Assume that f(x, y, z) is convex in y on Y for any given x E X, Z and concave in on Z for any given E X. y Y and is continuously differentiable on an open set containing
X Y x Z. Then graddie (z, 0, 2) continuously differentiable on X Y Z. and for any
(I, v, 2) X
Val(a,y,
V V.s(2,0' 2)
Vggaadlee v,2) =
(y 0+) 00) vzf 0"
(53)
(z /22
V
where 8" and X* denote 8" (xx v. and X2 (x, y, 2), respectively. defined as
1
0* (xx,3122 = argmin BEY
f 0x,0,22 +
- 10 8l
271
(54)
1
argmax X
||
=1|2
272
This newly introduced gap function enables the following equivalent single-level reformulation of the problem (66).
min (mxx))XXxXxZ F(x,y,2) s.t. Graddle (x, y, O.
Using Lemma A.6 and the proof techniques in Theorem 2.3 we can establish the equivalence be-
tween the reformulation (19) and the bilevel optimization problem (16).
Theorem A.8. Assume that fx, y.2) is convex in y on Y for any given X, E Z and concave in z on Z for any given x E X. E Y. Let "h 7/2 > O, the reformulation (79) is equivalent to the
bilevel optimization problem
33

---

Published as a conference paper at ICLR 2025
propose gradient-based, single- loop, Hessian-free algorithm for problem (6.. At each iteration, we employ a single projected gradient descent step to update g X to approximate 6" (** , . 2*) and X X" ,3" "0²,)*), as follows:
Utilizing this reformulation, analogous to BiC-GAFFA,
g++1 Projy (0* m)d)))
x Projz (1* m²d))
where 7/ 0 is the step size, and
1
d = V vyl(a 0h x + - 10 1/1,,
71
(55)
d vzf(x* sh A²) + (2* 24t). By substituting (0++1, 1) y for (0", x*) in 53
72
approximate the gradients of the function
1 F(z (I + goaddle 22
to define the update directions:
d 1
F ) + Vaf(a , Vaf(x*, gh+z 2t, Ck
dy = vyF( ) + Vyf (a x - -0²" 1/tt)//2
(56)
Ck
1 d - v v (2 k+| 1/12 - V=l(x" ,0h+1 ,
Finally, we implement an update for the variables (I., y, 2) using a step size o₁ > 0:
kx++1 y k+1 = = Proixxyxz ((** y =², an (d dz. d=)))
The complete algorithm is presented Algorithm
While the primary focus of this paper is the bilevel optimization with constrained lower-level prob- lems, we defer the convergence analysis of this algorithm to future work.
34


Reviews:
[{"review_id": "3W84t2jEeW", "reviewer": "Reviewer_qRB2", "summary": "This paper studies a bilevel problem where lower-level problem is convex with coupled constraints. To avoid joint projection onto the coupled constraint set which requires coupling convexity and is costly, this paper introduces a doubly regularized gap function to convert lower-level problem into a smooth constraint. This constrained problem is then solved by penalty method. Convergence analysis is provided and numerical results validate the effectiveness of the proposed method.", "questions": "In Proposition 3.1, it is assumed that the optimal solution $(x^*,y^*,z^*)$ to (6) exists with finite $z^*$. How can this be guaranteed? Additionally, how should $r$ be chosen in practice? Setting $r$ too large may hinder algorithm convergence, while choosing $r$ too small could exclude the optimal point $z^*$, which is unknown. \n\nAdditionally, several concurrent related works are missing: [1]--[2]. \n\n[1] A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints. L Jiang, et. al. arXiv:2406.10148. \n\n[2] First-Order Methods for Linearly Constrained Bilevel Optimization. G Kornowski, et.al. \tarXiv:2406.12771.\n\nIn Table 3, the term \"Required accuracy\" could be replaced with a word like \"Time\" to clarify the values reported. As it stands, it is unclear whether the numbers in this table represent accuracy or computation time.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This work tackles an important bilevel problem which involves coupled constraints at the lower level.\n2. The design of the doubly regularized gap function is novel and effective. \n3. The numerical studies are comprehensive and thorough.", "weaknesses": "This paper addresses a relaxation of the original bilevel problem through a penalty reformulation and truncation approach. For the penalty reformulation, it is shown that by selecting a sufficiently large penalty constant $c$, the penalty problem becomes an $\\epsilon$-approximate solution to the original problem. At the same time, the truncation parameter $r$ also appears to need a large value to ensure equivalence with the original problem. But in the final convergence theorem, $r$ is chosen as a constant, independent of the target error $\\epsilon$.", "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": "o7rbsnYWtN", "reviewer": "Reviewer_ejeH", "summary": "The paper introduces a method for transforming constrained bilevel optimization problems with coupled lower-level constraints into a single-level problem with a smooth constraint, employing a doubly regularized gap function. Based on this reformulation, the authors propose a first-order single-loop penalty-based algorithm called BiC-GAFFA. Theoretically, they establish non-asymptotic convergence results under general assumptions. Additionally, they investigate the extension of the proposed algorithm to bilevel optimization problems featuring minimax lower-level problems, a topic that has received limited attention in the existing literature. Extensive experiments are conducted to validate the practicality, robustness and efficiency of BiC-GAFFA, encompassing multiple complex problem models within the learning problems.", "questions": "1. The convergence results for extending the proposed algorithm to bilevel optimization problems with minimax lower-level problems are lacking, which leads to that Section 5 feels somewhat abrupt overall.\n\n2. In the experimental settings, we observe that the step sizes $\\alpha_k$ and $\\eta_k$ are fixed or vary in a specific form. Are the step sizes related to the specific formulations of different problems?\n\nSome more detailed questions:\n\n1. Can the conclusion of Lemma 2.1 be stated as \"$\\mathcal{G}_\\gamma(x,y,z)=0$ if and only if $y\\in S(x)$ and $z\\in \\mathcal{M}(x, y)$\"?\n\n2. In line 845, the loss function in lower-level problem should be $\\mathcal{L}_{tr}$.\n\n3. In line 1007, can you provide the specific mathematical format of the functions $\\mathcal{L}_{gen/det}$", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The paper introduces a smooth constrained reformulation for bilevel optimization with a constrained lower-level problem. This reformulation avoids the use of any implicit functions associated with the lower-level problem, which are typically known to necessitate additional iterations or inexact solutions.\n\n2. The authors present the first-order single-loop algorithm BiC-GAFFA, which exhibits overall complexity that is lower than that of many existing first-order algorithms requiring double-loop iterations. Notably, it does not rely on the assumption of full convexity of the lower-level constraints.\n\n3. When updating the proximal variable $\\lambda$ associated with the multipliers $z$, there is no need to compute the gradient of the gap function. Instead, the update can be effectively executed solely by applying the first-order optimality conditions of the maximization problem.\n\n4. BiC-GAFFA possesses a broader range of potential applications, making it suitable for solving bilevel optimization problems where the lower-level problem is a minimax problem. Existing bilevel optimization algorithms are unable to achieve this simultaneously.", "weaknesses": "1. From Section 6.2 and A.2.2., we observe that when dealing with nonsmooth problems, such as sparse group lasso and SVM, it is necessary to reformulate them into a smooth form for effective resolution. It may impact the applicability of the algorithms.\n\n2. By introducing the gap function, the authors have designed a single-loop algorithm. However, the dimensionality of the introduced variables remains the same as that of the original problem, resulting in an increased iteration scale. Compared to LV-HBA proposed in [1], there is no significant improvement in mathematical representation or convergence results.\n\n3. The necessity to control multiple iteration step sizes within the algorithm significantly affects the convergence theory and empirical performance, making them highly dependent on the adjustment of these step size parameters.\n\n[1] Wei Yao, Chengming Yu, Shangzhi Zeng, and Jin Zhang. Constrained bi-level optimization: Proximal Lagrangian value function approach and Hessian-free algorithm. In ICLR, 2024.", "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": "I3DzUPBrI9", "reviewer": "Reviewer_pgpK", "summary": "The paper introduces a novel algorithm for constrained bilevel optimization (BiO) using a regularized gap function to transform bilevel problems with lower-level (LL) constraints into a single-level optimization problem with a smooth inequality constraint. The authors propose a first-order, single-loop algorithm, BiC-GAFFA, that operates without requiring Hessian evaluations or projections onto the LL constraint set, offering both theoretical convergence results and empirical validation on synthetic and real-world tasks, such as hyperparameter optimization and generative adversarial networks (GANs). The paper also presents an extension of the method to minimax lower level problems, which broadens its applicability.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The introduction of the doubly regularized gap function is a novel (as far as I am aware in the context of bilevel optimization) solution to deal with constraints at the lower level in bilevel optimization. This regularization allows the transformation of the bilevel problem into a smooth optimization problem, which simplifies the numerical implementation and analysis. \n\n2. The proposed BiC-GAFFA algorithm avoids costly second-order computations, which is usually the case for methods based on constrained optimization reformulation. The single-loop nature of the algorithm is also computationally efficient, as supported by the non-asymptotic convergence analysis. \n\n3. The extension to minimax inner level problems provides flexibility in dealing with a broader class of problems beyond the traditional settings.", "weaknesses": "1. Some theoretical assumptions are insufficiently justified (i.e. very weak statement), particularly in Remark 2.5, where it’s stated that the existence of a multiplier in Theorem 2.3 “can be guaranteed” under certain constraints qualification conditions like MFCQ. Is the assumption in fact guaranteed when the constraints qualification conditions are satisfied? Or does those conditions directly imply that the assumption is satisfied? Please clarify. \n\n2. The update steps in BiC-GAFFA are quite similar to existing constrained optimization reformulation methods, such as primal-dual [1] and dynamic barrier [2] methods. While these approaches have been applied successfully in other constrained settings, the paper does not explain why they are inadequate for the additional lower-level constraint here, suggesting a need for BiC-GAFFA. A discussion on this distinction would help clarify the necessity of more complex methods such as the proposed BiC-GAFFA. \n\n3. The algorithm requires additional sequences (e.g.,  $\\theta_k$  and  $\\lambda_k$), adding to the computational and memory load, which may challenge its feasibility for large-scale applications. \n\n4. The experimental results focus on toy numerical problems and small-scale real-world problems. While these results are encouraging, a broader evaluation on large-scale or diverse domains would better demonstrate BiC-GAFFA’s practical applicability and scalability. \n\nReference: \n\n[1] Sow et al. A Primal-Dual Approach to Bilevel Optimization with Multiple Inner Minima. \n\n[2] Ye et al. BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach.", "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": "fnxXI2yo4x", "reviewer": "Reviewer_CGDJ", "summary": "This work studies bilevel problems where the LL problem is constrained. \n\nThe key contributions are:\n\n1. The equivalence between main problem and the smoothed problem (6) under convexity.\n\n2. The relation between (6) and the sequence of problems in Thm 3.3\n\n3. A gradient based algorithm with nonasymptotic grad-norm rate for an instance of problem 3.3\n\nStrength:\n\n1.The paper is technically sound. \n\n2.The comparison against known results are clear, and hence the main contributions are clear.\n\n3. I like the discussions on reformulations and the experiments.\n\nWeakness:\nI hope the authors could address my concerns below.\n\n1. When and why would constraints in the LL be necessary? \n\na. GAN would not require constraints.\n\nb. SVM has uncontrained versions.\n\nc. Hyperparameter tuning / data selection can be solved with more naive approach without bilevel problems.\n\n2. There are more than one way to smoothen/regularize the lower level so that the limit is the original problem.\n\nFor example: one can add positive coefficients c1, c2, so that the bilevel is now F +  c1 f + c2 max(g, 0) . Then by sending c1, c2/c1 to infinity, one could also get an approximate solution. Why would one formulation better than another?\n\n\nMinors: \n1. The notation N_Y(y) and other similar ones are not defined.", "questions": "See summary", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "See summary", "weaknesses": "See summary", "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 (Poster)