A Single-Loop Gradient Algorithm for Pessimistic Bilevel Optimization via Smooth Approximation
Authors: Qichao Cao
Shangzhi Zeng
Jin Zhang
Venue: NeurIPS 2025 poster ()
Keywords: Bi-level Optimization
Pessimistic Bilevel Optimization
Gradient Method
Single-loop
Value Function
Smooth Approximation
Primary area: optimization
TL;DR: A Single-Loop Gradient Algorithm for Pessimistic Bilevel Optimization via Smooth Approximation

Abstract: Bilevel optimization has garnered significant attention in the machine learning community recently, particularly regarding the development of efficient numerical methods. 
While substantial progress has been made in developing efficient algorithms for optimistic bilevel optimization, the study of methods for solving Pessimistic Bilevel Optimization (PBO) remains relatively less explored, 
especially the design of fully first-order, single-loop gradient-based algorithms. This paper aims to bridge this research gap. We first propose a novel smooth approximation to the PBO problem, using penalization and regularization techniques. Building upon this approximation, we then propose SiPBA (Single-loop Pessimistic Bilevel Algorithm), a new gradient-based method specifically designed for PBO which avoids second-order derivative information or inner-loop iterations for subproblem solving. We provide theoretical validation for the proposed smooth approximation scheme and establish theoretical convergence for the algorithm SiPBA. Numerical experiments on synthetic examples and practical applications demonstrate the effectiveness and efficiency of SiPBA.

A Single-Loop Gradient Algorithm for Pessimistic Bilevel Optimization via Smooth Approximation
Qichao Cao caoqc2024@mall hwwp://ww.ma.sssss.s.....mommaa. edu. cn
Shangzhi Zengal
zengszōsustech. edu.
Jin Zhang 1,2,,'
zhangj9@sustech. edu. cn
Abstract
Bilevel optimization has garnered significant attention in the machine learning community recently, particularly regarding the development of efficient numer- ical methods. While substantial progress has been made in developing efficient algorithms for optimistic bilevel optimization, the study of methods for solving Pessimistic Bilevel Optimization (PBO) remains relatively less explored, especially the design of fully first-order, single-loop gradient- based algorithms. This paper aims to bridge this research gap. We first propose novel smooth approximation to the PBO problem, using penalization and regularization techniques. Building upon this approximation, A Algorithm), a new gradient-based method specifically designed for PBO which avoids second-order derivative information inner-loop iterations for subproblem solving. We provide theoretical validation for the proposed smooth approximation scheme and establish theoretical convergence for the algorithm SiPBA. Numeri- cal experiments on synthetic examples and practical applications demonstrate the effectiveness and efficiency of SiPBA.
then propose SiPBA (Single-loop Pessimistic Bilevel
Introduction
Bilevel optimization constitutes hierarchical optimization problem formulated as follows:
min F(I,8) y) s.t. E S(z) = arg fin xEX
y'EY
where x E R and y R represent the upper-level and lower-level decision variables, respectively. and X C R" and C RT are closed convex sets. The functions F I2" Rm - R and f R" x R + R are the upper-level and lower-level objective functions. respectively. Bilevel optimization naturally models non-cooperative game between two players, often referred to Stackelberg game [66]. When the lower-level problem in bilevel optimization admits multiple optimal solutions for given I, the corresponding decision variable y in the upper-level objective becomes ambiguous. To resolve this, bilevel optimization is commonly formulated in two distinct settings: Optimistic Bilevel Optimization (OBO) and Pessimistic Bilevel Optimization (PBO).
Department of Mathematics, Southern University of Science and Technology, Shenzhen, China. 2 National Center for Applied Mathematics Shenzhen, Southern University of Science and Technology, Shenzhen, China.
Detection Institute for Advanced Technology Longhua-Shenzhen (DIATLSSS), Shenzhen, China. Corresponding Author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In the OBO setting, it is assumed that the lower-level selects solution y S(x) that is most favorable the upper-level's objective F. The OBO formulation is thus:
min min F(z, y) xEX yERm
s.t. y E S(x),
Conversely, the PBO setting considers cautious or adversarial scenario where the lower-level is assumed choose solution y E S(x) that is least favorable to the upper-level. The PBO formulation is:
min max F(x, v) s.t. y E S(r),
zeX yER"
Therefore, OBO models scenarios predicated on cooperative or aligned lower-level responses, whereas PBO is essential when robustness against worst-case outcomes, often encountered under uncertainty or in adversarial contexts, required.
In recent years, bilevel optimization has garnered substantial interest within the machine learning
community, finding applications in areas such hyperparameter optimization [23]. adversarial learning [72). reinforcement learning [75), and meta-learning (28). among others, where first-order
gradient-based methods are preferred for their efficiency and scalability [15] 63
Much of the existing bilevel research focuses on the OBO case, for which numerous fully first- order gradient- massen algorithms suitable for large-scale machine learning tasks have been developed [3| 42 45 61]. often by reformulating the problem using Karush Kuhn- Kuhn-Tucker (KKT) conditions or through ddle-ffuctioon-bsee constraints. While OBO benefits from well-established algorithmic toolkit, PBO remains comparatively underexplored from an algorithmic standpoint. PBO offers a robust framework for leaders concerned with worst-case follower responses and growing body of work has explored the potential of PBO in various machine learning applications such as adversarial learning [6. [3,, contextual optimization 17 36 and hyperparameter optimization (64). Outside the machine learning domain, PBO has found applications in many other practical scenarios, including but not limited to demand response management 377, rank pricing and second-best toll pricing [8] 9), production-distributioo planning [74]. and gene knockout [7de Yet, the inherent max-structure the upper level of PBO creates a more complex, three-level-like structure (min-max-ming making the direct application of gradient-based techniques developed for OBO challenging. Although several PBO single-level reformulations have been proposed [67 [1] [ their intricate structures continue to pose difficulties for the development of fully first-order gradient-based solution methods. Recently, [3 proposed AdaProx, gradient- based method for PBO. This AdaProx method employs double- loop procedure and requires second-orde derivative information. This motivates our central research question:
Can we design a fully first-order single-loop gradient-based algorithm for PBO?
This paper demonstrates that the answer is affirmative. We approach PBO by reformulating it as the minimization of value function:
min (xx), where dxx)= == max {F(x,y) s.t. y E S(x)) #EX
(1)
yER
As indicated by the formulation in [ the PBO can be solved by minimizing the function ((x). However, ((x) is the value function of maximization problem whose feasible region depends on the solution set of another optimization problem. Consequently, d(x) is generally non-smooth [32]. and evaluating its value and gradient (or subgradient) poses significant computational challenges. The non-smoothness of (xx) constitutes a primary challenge in solving PBO, rendering the direct minimization of ((z) difficult.
To surmount the challenge posed by the non-smoothness of ((x). we introduce a smooth approxi- mation of o(x) by employing penalization and regularization techniques. This transforms the PBO into a tractable, smooth optimization problem, enabling the application of efficient gradient-based methods. However, calculating the gradient of this smooth approximation function requires solving an associated minimax subproblem to find its saddle point, which can be computationally demanding and complicate the implementation of gradient-based methods. To address this complexity, we propose a one-step gradient ascent-descent update strategy to obtain an inexact saddle point solution. This inexact solution is then used to construct an inexact gradient for the minimization of the smoothed objective. Through this approach, we propose SiPBA (Single-loop Pessimistic Bilevel Algorithm), novel fully first-order single-loop gradient- based algorithm designed to solve PBO problem (I).

---

1.1 Contribution
This paper presents the following key contributions the study of PBO problem:
New Smooth Approximation for PBO: We introduce a novel smooth approximation for PBO. This is achieved by constructing continuously differentiable surrogate for the potentially non-smooth value function ((x), using penalization and regularization techniques. Based on this, we formulate smooth approximation problem corresponding the original PBO. The validity of this smooth approximation is rigorously established by demonstrating the asymptotic convergence of the solutions of the smoothed problem to those of the original PBO. These results are detailed in Section 2
Single-Loop Algorithm (SiPBA) and Theoretical Guarantees: Building upon the proposed smooth approximation, develop SiPBA Single-loop Pessimistic Bilevel Algorithm). SiPBA is a gradient- based algorithm designed for solving PBO problems, which avoids the computation of second-ordes derivatives and eliminates the need for iterative inner-loop procedures to solve subproblems (Section 3). We provide a rigorous convergence analysis of SiPBA in Section This analysis includes the metrics and establishes guarantees
derivation of non-asymptotic convergence rates for relevant for achieving a relaxed stationarity condition for the iterates generated by the algorithm.
The practical effectiveness and computational efficiency of the proposed SiPBA algorithm are validated through numerical experiments, presented in Section 5 We evaluate SiPBA across synthetic problems, email spam classification, and hyper-repreeenntaton learning. The results provide empirical evidence supporting the competitive performance of SiPBA.
Empirical Validation:
1.2 Related work
Optimistic Bilevel Optimization: OBO has been extensively studied, with surveys detailing its theory, algorithms, and applications [9 it to a single-level problem, using Karush- Kahn-KKuhuhhhe
22 23 A common approach for solving OBO is to reduce (KKT) conditions, leading to Mathematical Programs with Complementarity Constraints (MPCC) 4 51, or through value-function--ue based inequality constraints [70, (57. Approximating the lower-level solution with finite trajectory is
another strategy [53 26 These approaches have yielded scalable and efficient algorithms suitable
for large-scale machine learning tasks (58
27
48
46
33
49
35
61
38
42
50 39).
However, the max-structure at the upper level of PBO creates more complex, three-level-like
structure smin-max-min), hindering the direct application of OBO algorithms to PBO.
Theoretical studies include [1. which investigates sufficient conditions for the existence of optimal solutions, and [7]. which studies properties of approximate solutions. Optimality conditions for PBO have been explored,
Pessimistic Bilevel Optimization: PBO has been surveyed in 43 23
including KKT-typp conditions for smooth and non- smooth cases 21 8 studies the relationship between PBO and its MPCC reformulation. For PBO algorithms, 2 7 propose penalty methods
for solving weak linear PBO problems. [67 introduces semi-infinite programming reformulation of PBO. [40] reformulates PBO as an OBO problem with a two-follower Nash game, solving as an MPCC. (71) transforms PBO into minimax problem with coupled constraints, proposing methods for the linear case. More recently, [2] explores relaxation methods for solving PBO's KKT conditions. (31] combines the lower-level value function with the KKT conditions of the upper-level max problem, resulting in constrained minimization problem solved by a gradient- based method. Several heuristic algorithms have also been proposed, though without convergence guarantees [5] 3 Recently, gradient- based algorithms for minimax bilevel optimization have been developed (30 34 68). However, these problems differ from PBO in that their max structure is the upper-level variable, not the lower-level variable, making these algorithms inapplicable to PBO. To our knowledge, fully first-order, single-loop gradient-based algorithms for solving PBO remain limited.
2 Smooth approximation of PBO
Throughout this paper, make the following standing assumptions:
Assumption The upper-level objective function F(x, y) is continuously differentiable, and its gradient F( y) is Lipschitz continuous on X x Y. For any fixed x X, (2. y) is j-sttrongy concave with respect y Y for some p 0.
3

---

Assumption 2 The lower-level objective function f(z, y) is continuously differentiabee, and and its gradient V fax y) is Lipschitz continuous on x Y. For any fixed X. f(z,y) is convex with respect to y Y. Furthermore, S is nonempty for any E X. For any bounded set B S X, there exists bounded set D such that S(x) O D * Φ for every x E B.
In this section, introduce smooth approximation for o(x), leading a smooth approximation of the PBO problem. All proofs for the results presented in this section are provided in Appendix [
2.1 Smooth approximation of (bx;)
To construct smooth approximation of ((x)), we first consider an equivalent reformulation of d(x) as the value function of a constrained minimax problem:
Φ (x) = min max {F(r,)) s.t. f(z,8) S f(z,2))
(2)
zEY DEY
This reformulation was explored in 771 an application of the value function approach for designing numerical methods for PBO problem. The equality in (2) is justified by [7] Lemmas 1, 2]; for completeness, a proof is provided in Appendix B.
Next, we use this constrained minimax formulation develop a smooth approximation of ó(z). To address the nonsmoothness introduced by the constraint in (2), we consider penalized approxiatiio:::
min max F(x, y) pl (x., v) fa, =)),
sEY yEY
where p > a penalty parameter. Under the stated assumptions, this minimax problem convex in and concave in y, making it computationally tractable. However, the potential non-umt non-uniqueness of the optimal 2, can result in the value function of this penalized problem being nonsmooth with respect x. To ensure smoothness and well-posedin well-posedness, we introduce regularization term for and a coupling term (y, z), leading to the following regularized objective function:
a po (z, v. 2) F(z, v) pl v) (zx + |=12 (y. 2)
(3)
where a > 0 is regularization parameter. This function 1 (I, y, =) is designed to be strongly convex and strongly concave y. Based on this, we propose the approximation for (xx) as:
(x) = min max zEY yEY (2, 2)
The strong convexity-concavio of v/ao ensures that (x) is well defined for any E X. Furthermore, it guarantees the existence and uniqueness of a saddle point, denoted by (1), 2p. (z)), and allows the interchange of minimization and maximization operators, i...,
(p.o(() mingey maXzeY (1, y, 2) max mingey (x, v,
is important to highlight the role of the coupling term (y,2) in 3 introduced alongside the regularization term |||| 12 This coupling term is crucial for establishing Lemma 2.2 which is the foundation of the asymptotic convergence of the proposed approximation &p.o (x) to ((z), and of the saddle point (1 (x), a (x)) established in Theorems 2.5 and 2.6 respectively.
We now establish a key smoothness property of (p.( its differentiability, and provide an explicit formula for its gradient.
Theorem 2.1 Let p, a > be given constants. Then, for any x E X, 2p.o (x) is differentiable. Its gradient is given by:
V = (5)) ( o (x)) + aN 20 (x));
(5)
where (1 (x), (x)) is the unique saddle point for the minimax problem defining & (xx) in (4).
2.2 Asymptotic convergence of the approximation
Using the smooth approximation function & (I), we formulate the corresponding smoothed opti- mization problem intended to approximate the original PBO !I:
min &p.a (z)) x
(6)

---

This subsection validates the use of (6) by establishing the asymptotic convergence properties of Pp.a (x) ) ((x)), and, consequently, the convergence of the solutions of (6) those (T) as p + 00
and + 0. We begin by establishing a relationship between pp. (2) and ((x) in the limit.
Lemma 2.2 Let {pE} and { be sequences such that Pk. + 00 and + O. Then, for any E X, holds that:
lim sup 6 on (x) ((x).
(7)
R-+00
Furthermore, considering the optimal values, have:
limsup Ao-b00
inf (pr.o (EEX
S inf Φ(x).
(8)
wEX
Lemma 2.2
provides an upper bound on the limit the approximate values. Building upon this, we can demonstrate the convergence of the optimal values under mild conditions.
Proposition 2.3 Let {px} and {ak} be sequences such that Pk + co and ax - 0 as - co. If
either X or Y is bounded, then the optimal values converge:
lim k-+00
(pr.aa (t)) xEE
inf
inf d(x)
=EX
Establishing the convergence of optimal solutions (minimizers) requires additional structure related to the continuity properties of (xx). To this end, we introduce the assumption of lower comi-continuity.
Assumption <0x) is lower semi-continuous (l.s.c.) on X. That is, for any sequence {œu} C. X such that + I E X as k + oc, it holds that, ((T) S lim inf ((rx).
Lower semi-continuity is equivalent to the closedness of the function's epigraph and its level sets, and guarantees the existence of minimizer for Φ(z) over compact set X (see, e.g., [60 Theorem 1.9)). Sufficient conditions for Assumption 3 such as the inner semi-continuity of the lower-level solution map S(z), are discussed in Appendix B.5 Under this assumption, we can establish the following result for epi-convergence.
Lemma 2.4 Assume (xx) lower semi-contnuous on X. Let {pk} and {ox} be sequences such that Pk= - oc and d₁ + as + Then, for any sequence { C X converging to F, we have:
lim (x*k) 2 Φ(z). R-000
(9)
Conditions 7 (applied with a constant sequence of the sequence of functions {0m...r) } to & on as oo (see, e.g., (60) Proposition 7.2]). This signifies that the epigraph of @pu. (x) converges, in the set-theoretic sense, to the epigraph of ((z).
I)) and 9 together imply the spi-convergence
Leveraging this epi-convergence property, and employing results such as [14 Proposition 4.6] (60
Theorem 7.3 we can establish the subsequential convergence of minimizers of problem (
Theorem 2.5 Assume ((x) is lower
on X. Let {pr} and {ax} be sequences such that Pk + oo and a% + 0 as + op. Let Ia E argmin ze x &p a (I). Then, any accumulation point of the sequence { is optimal solution to the original PBO i.e., T argmin ((x).
In the following, we characterize the asymptotic behavior of the saddle point (w) (4), =0,0 (x)) as p - do and a - 0, and show that both components converge the solution of the maximization problem that defines the value function ((x) in (T).
on X. Let {px} and {ok} ) be sequences such that P - oc and dj -+ as l - co and let { be sequence such that Tkk E X and I& as + xo. Then, we have:
Theorem 2.6 Assume ((x) is lower
lim Vor.or (xx) = lim =p (xx) [ = (z),,, k+20
(10)
k
where (²())= := arg maxyes(s) F(2,y)
5

---

3 Single-loop gradient-based algorithm
In this section, we introduce the Single-loop Pessimistic Bilevel Algorithm (SiPBA), novel single- loop gradient-based method designed to solve the PBO problem (T). The foundation of our approach the smooth approximation problem (6. min 9p.ar (2), developed in the previous section.
Owing to the continuous differentiability of the function @p.a (2), gradient-based methods can be employed for solving it. However, established in Theorem 2. the computation of the gradient V necessitates the saddle point solution, denoted (8 (z) (x),, of the minimax subproblem min maXgEY dipo (æ, y, 2). Although this minimax problem strongly convex in and strongly concave in y, finding its exact saddle point solution can be computationally expensive.
To mitigate this challenge, we propose constructing an inexact gradient at each iteration for updating z². Specifically, iterates (v" =*) are introduced to approximate the the exact saddle point solution to the minimax subproblem. At iteration k. given parameters Pk+ 0 > 0 and the current iterate 2², single projected gradient ascent-descent step is applied to the minimax subproblem millzey maXyEY Vn,.o, (x* y. =) to update (y* )*). The update rules are:
+ Projy (u" + Badd)) 2 = Projy -
where B& > 0 is the step size, Proiy represents the Euclidean projection onto to set Y, and the update directions di and d are defined as:
dy F(* n²*) pa (x w/") oNz dh = Vyl + ox v*). (11)
Subsequently, the newly updated iterates (y*+1, 2)1 are used in place of the exact saddle point solution (V (I*), pp (x*)) within the formula for Von.. (x*) (given in (5). This yields an inexact gradient, which serves the update direction dt for the iterate r²:
d F(* t Pk (V (x= , - v 2t1))
(12)
The iterate x² is then updated as:
* = = Projx (a*-axdd)
where or 0 is the step size.
Furthermore, the parameters Pk and 0% are updated throughout the iterative process, specifically by ensuring Pk: - and σk 0 as k + c0. The precise update strategies for selecting these parameters, along with the step sizes og and Bx. are detailed in Theorem|4.2) presented in Section 4
preeseee
Based on the preceding components, we now formally present the Single-loop Pessimistic Bilevel Algorithm (SiPBA) for solving the PBO problem (I) in Algorithm [ In many practical applications where projections onto X and Y are computationally efficient, SiPBA offers the significant advantage of a single-loop structure, making it straightforward to implement.
Algorithm 1: Single-loop Pessimistic Bilevel Algorithm (SiPBA)
Input: Initial points (z. .y 20) X x Y, stepsizes ogk By > 0, parameters Pk 0 > for i 0, 1,..,, K 1 do calculate di and d in 11 and update
Projy (y* + )ed"), 1+1 =+ Projy
(2* = -Bedh);
caleulate d in 12 and update
x 1+1 Projx (x* - -a,d")
4
Convergence analysis
This section establishes the convergence properties of the proposed SiPBA. All proofs for the results presented herein are provided in Appendix C
Throughout this section, introduce additional assumption regarding the boundedness of X.

---

Assumption 4 The set X is compact.
To streamline the notation in this section, given the sequences pk and ok, we adopt the following shorthand: Φn (x). th (a, y, z), yi (x) and z (a) will denote op (I), Vpu.on (2, y, 2), Vpg.o (x) and pp..or (1)), respectively. Furthermore, let == (v, 2). wf == (v" x²) and ug (x) = (0)(2), (x)). Let Lp and Ly denote the Lipschitz constants of V ( y) and V (2 4) on X x Y, respectively.
To facilitate the convergence analysis of SiPBA, introduce merit function Va incorporating dynamic positive coefficients ag > 0 and by > 0:
Vx ag (0x(x") - +) + bxllu* - u,((²")1?
(13)
where & represents a uniform lower bound for Φh (a*), such that de (x<xx)== 2 for all k. The existence of such lower bound is formally established in Lemma C.8 in the Appendix, under the condition
that ((x) is bounded below on X. Consequently, as a& 0, by > 0, (x(x)) 2 Φ. and the squared norm term is inherently nonnegative, V₁ is always nonnegative.
Through careful selection of the parameters Pk: ak, step sizes ork, 8R, and merit function coefficients ag, b2. we establish the following descent property for the merit function Vx-
Proposition 4.1 Let {(x", ) be the sequence generated by SiPBA(Algoritimm] with parame- ters selected as:
ak = aakk
= 2ok-2
Ok = 1o0kk = Pok"
(14)
with ap. 90, Go. Po.S.P.P. > O. Assume that s > t + 4p + 2q. t 4p 4q and P.q q < 1. If 3 is sufficiently small, then all sufficiently large k, the following inequality holds:
Vk+1
Vx S
ak
||I x²112
1
bg. u/ (2 + Sks
(15)
4
where V& is defined in (33) with a = k= by = k k ox minfos, ub. and {Cx} } is a summable sequence, i.e., Ek- Sk
Using this descent property of Vk. we establish the following convergence result and derive non- asymptotic convergence rates for the error terms ||=k=| - x* l|/o and I|u* - (x**))
Theorem 4.2 Let {(* y } be the sequence generated by SiPBA(Algorithm 7 with parameters ((=".""
selected as in (14). Suppose that the function ((x) is bounded below on the set X. Assume further
that 0 < 8 < 1 22, < p.g < and 8p + 89 S s. If 80/00 is sufficiently small, then the following
hold:
min OCkcK ok.
|aa
-01 and
min l|u* ockcK
Moreover,
lim inf ||00 - Projx (x* - az V (xbe(*))) |1/0 = =0, and lim inf 1|u* (x(x)) = 0.
Based on Theorem 4.2 a practical parameter selection strategy for SiPBA is provided in Appendix A.4 Furthermore, we can establish a modified stationarity result for the iterates x² generated by SiPBA in terms of the e-subdifferential (cf. [55] Theorem 1.26)).
Corollary 4.3 Assume d(x) is lower somi-continuous on X. Let {(* =*)} be the sequence
generated by SiPBA(Algorithm 77 with parameters chosen specified in Theorem 4.2 Suppose that the function Φ(z) is bounded below on the set X. If 30/ ou is sufficiently small, then there exists a subsequence (art), } such that for any >> and ē >> 0, there exists an integer K > such that for all kj > K, there exists corresponding 8j > 0 f.ror which the following inequality holds:
δ(z) + ellx k 2 dlz*)) - -E,
Vx E Bs, (a*5) n.
Numerical experiments
To evaluate the performance of SiPBA, we conducted comprehensive validation through both synthetic examples and real-world applications. All computational experiments were performed on a server provisioned with dual Intel Xeon Gold 5218R CPUs (a total of 40 cores/80 threads, with 1-10 GHz)) and an NVIDIA H100 GPU. Detailed information regarding the specific implementation of algorithms, along with the configurations for each experimental setup, is available in Appendix
7

---

5.1 Synthetic example
To empirically demonstrate the performance of SiPBA, we consider the following synthetic PBO:
1 - x ell² -1yy e s.t. E arg min y'el 20) [| v/) - |==+||| (16)
min 11 yER"
max
where denotes the all-ones vector of appropriate dimension. For 2 2. it can be shown that the unique optimal solution is given by (x".y") (e/2, e/ The performance is assessed by the relative error, Ere! = (1|z* - xx 1I + lly y /|]]=)
y I1'). For all experiments in this subsection, the results are averaged over 10 independent runs, each initialized from a distinct, randomly generated starting point. The initial point (a", .y") is generated by sampling each component of x: from uniform distribution (0)0.11 10) and each component of y from U1 (2 10).
-x"12 =x"
SIPBA
AdaaPro-PPP PD
AdaProx
10.0
Iterations (x101)
0.50
10
7.5
Time (5)
0.45
Realtre enee
30
5.0
0.30
20-1
0.15
3014
0.0
250
500
750
1000
0.00
Iteration (x10?)
Dimension (n)
(a) Convergence curve
(b) Time and Iter. v.s. Dimensions
Figure I: (a): Convergence curves of SiPBA, AdaProx-PP PD and AdaProx-SSe SG on (6) with n = 100; (b): Iterations and runtime required for SiPBA (66) for varying problem dimensions
Table I: Performance comparison of the SiPBA, AdaProx- PD,, AdaProx-SO SG, Scholtes-C, and Scholtes- D with n 100.
SIPBA
AdaProx PD
AdaProx -SG
Scholtes-C
Scholtes-D
Min. (Frel)
1.22 x 10
1.79 10
3.80 x 10
L.2 10-3
9.60 10
Max. (f,a)
1.45 x 10-6
1.53 x 10-5
1.02 x 10-1
0.10
1.06
Valid Runs
10/10
10/10
9/10
1/10
1/10
Ave Time (s)
1.03
87.44
4.07
23.12
23.81
AdaProx-PD and AdaProx-SG - well as two MPCC-based approaches- Compact Scholtes (Scholtes-C) and Detailed Scholtes (Scholtes-D) relaxation method [2 SiPBA, AdaProx-PD, and AdaProx-SG are run for 20,000 iterations, while Scholtes-C and Scholtes-D D are run for 10 outer iterations (as they converge within this range). We report the minimum and maximum relative errors, the number of successful runs achieving the tolerance Eyel < 10 (Valid Runs), and the average runtime to reach this tolerance for those valid runs (Ave. Time). Figure a shows the convergence curve of the madient-based algorithms and Table Saadeessumnn summariizes the final performance metrics of all the methods. We further evaluate SiPBA's robustness to hyperparameters (stepsizes oo. fo and update factors p, 8) and its scalability by measuring runtime and iterations required to achieve the tolerance, Ere! < 10-4 across varying hyperparameters and problem dimensions, with results shown Table 2 and Figure (b).
We compare SiPBA against two other gradient-based
All the results indicate the consistent performance and computational efficiency of SiPBA.
Table 2: Ablation analysis for SiPBA on 16) with n
100.
A
Time (6)
Bg
Time (s)
0.1
0.001
0.001
0.001
0.1
1.0=0.1
0.1
0.001
0.0001
0.001
0.1
1.0=0.1
0.001
0.001
0.001
0.1
0.1-0.0
0.1
0.001
0.001
0.01
0.1
1.2=0.1
0.01
0.001
0.001
0.001
0.1
14,5+1.5
0.1
0.001
0.001
0.0001
0.1
1.1:0.2
0.001
0.5-0.1
0.1
0.001
0.001
0.001
0.3
5.0+0.2
0.1
0.0001
0.001
0.001
0.1
16.443.1
0.1 0.001
0.001
0.001
0.016
0.8=0.1
0.1
0.001
0.01
0.001
0.1
1.=003
1.9=0.3
5.2 Spam classification
Spam classification is challenging due to adversarial dynamics and poor cross-domain generalization.
We consider the PBO model for spam classification tasks, as proposed by [16]:
min max kw,, &. y) + >a Reg(w) s.t. J E arg min I' ('(w, x²) + >allv(a') (1x))1? (17) WER" 2
xeE
8

---

where w denotes the classifier parameters, (z, represents vectorized training data, / (resp. l') corresponds the classifier (resp. adversarial generator) loss, Reg(-) denotes the regularization term, and (p()) characterizes the feature of data.
We conduct two-part empirical comparison. First, we compare the PBO model (17) trained using SiPBA (with (p(x) as the top k principal components) to the same model trained using the SQP method with (o()) 2, as proposed in [16]. Second, we compare the SiPBA-trained PBO model against a standard single-level model, min ((w, I, y) + A (Reg(w), trained using the scikit-learn library [59] We use either hinge loss or cross-entropy for both and I', and refer to the resulting
methods as HuPBA-Hingele
and
Experiments are conducted using four standard spam datasets: TREC2006 [56], TREC2007 [52] EnronSpam 54 and LingSpam [6]. The average results over ten independent runs are summarized in Table 3 which indicate that the PBO model (either trained with SQP SiPBA) exhibits superior cross-domain performance compared to the single-level models. Moreover, the SiPBA-trained models achieve the best overall accuracy and Fl score.
Table 3: Accuracy (Acc) and Fl score (F1) on four spam corpora, training on TREC06, TREC07, EnronSpam or LingSpam.
Train Set
Model
Test Set(Ace/FF))
Ave(Aco/F1)
TREC06
TREC07
EnrunSpamm
LingSpam
SiPBA-Hinge
96,4/94.7
87.3/81.0
70.6/70.2
87.6/92.7
85,5/84.7
SiPBA-CE
94.5/92.5
79.5/73.0
70.9/71.8
87.6/92.8
83.1/82.5
OQn-Hinge
93.1/90.0
89.2/83.2
69.0/66.7
89.0/93.4
85.1/83.3
TREC06
SQP-CE
93.6/91.3
78.9/72.4
70.7/71.4
87.2/92.6
82,6/8199
Singl
95,4/93.1
89.3/82.8
63. 63.9/46.5
75.5/82.5
81,0/76.2
Single-CE
93.8/90.4
88.5/79.6
56.9/24.1
16.1/
73.6/64.2
HiBBe-Hinge
68.9/16.8
93.7/89.7
57.0/33.7
50,5/57.6
67.5/49.5
SiPBA-CE
71.7/56.9
1/97/
18.3/68.8
64.6/75.5
75.7/74.6
Hinge
68.9/17.2
95.3/92.5
55.0/210
29,9/28.1
62.3/39.7
TRECO7
SQP-CE 71.3/56.9
97.7/96.6
68.4/69.7
70.1/80.5
76.9/75.9
Single-Hinge
65.4/1.9
97.7/96.4
$0,9/0.2
16.6/0.3
$7.7/24.7
Single-CE 66.4/3.4
95.7/93.0
51.0/0.8
17.3/18
57.6/24.8
SiPBA SipgA-Hinge
75.8/61.8
72.1/28.0
95. 95.9/95.8
59.6/67.4
75,9/63.3
SiPRA-CR
76.3/62.8
74.0/34.4
95.2/95.0
64.0/72.0
77.4/66.1
SQP-Hinge
77.5/61.7
70.5/22.8
96910
$2.3/59.3
7/61/60.0
EnronSpam
SQP-CE 76.0/62.6
73.4/32.9
94.9/94.8
63.0/7100
76.8/65.3
Single-Hinge
76.8/56.00
69.3/15.0
95.8/95.6
47,2/52.3
72.3/54.7
Single-CB
76.4/55.4
70.0/19.2
95.6/95.3
43.1/46.9
71.3/54.2
SiPRA-Hinge Hinge
63.4/59.1
66.2/51.2
71.1/65.4
99.4/99.6
75.0/68.8
SiPBA-CE
71.8/48.5
69.0/27.6
59.1/34.3
91.8/94.8
72.9/51.3
SQP-Hinge
42.5/53.8
45.3/52.0
72.5/65.8
98.2/99.0
64.6/67.7
LingSpam
SQP-CE
72.0/49.5
68.9/26.2
58 9/39/33.9
91.9/94.8
72.9/51.1
Single-Hinge
37.2/51.9
38.6/50.6
56.7/69.0
95.7/97.5
57.1/67.3
Single-CE
34.5/51.0
34.0/50.1
51.3/66.8
91.4/95.1
52.8/65.8
5.3 Hyper-representttion
Hyper-representationn 29 27 aim to learn an effective representation of the input data for lower-level classifiers, where PBO model was used to handle the potential multiplicity of optimal solutions in the lower-level problem and robust learn the representation (31] In this experiment, we further explore the potential of the PBO model and compare it with optimistic models.
5.3.1 Linear hyper-repreesnntatinn on synthetic data
We begin with synthetic linear hyper-representtaion task, which formulated as:
1
1
min HER
X 1. 171
Yeaill s.t. w E arg min _ [ Hw' - Virain 113,
(18)
W'ERP 7122
where Xeat E Raxmi and Xtrain paxm² are the validation and training feature matrices, and Rha are the corresponding response vectors. The synthetic data is generated as 229, with feature matrices X Xtrain; X and ground-truth matrices Hreat and vectors Wreat
Yeat E IR"" Ytrain E Itrrin
sampled randomly. The response vectors are formed using the linear model y() X Hreat Wreals
with Gaussian noise (O0 a²) added to both X() and y(-) for train and valid data to simulate noise.

---

To evaluate solver efficiency and formulation effectiveness, we conduct two-part comparison. First, we compare the SiPBA algorithm with PBO algorithms AdaProx-PD and AdaProx-SG. Second,
we assess the impact of the bilevel formulation by comparing the pessimistic model
(88) (solved
by SiPBA) with optimistic variant (solved by AID-FP, AID-CG [29] and PZOBO 62 which
replaces max with min in the upper level. To assess the robustness of each method under varying
levels of noise, we conduct experiments with moderate (a = 0.1) and severe (a = 1) perturbations.
The performance is measured by test loss, averaged over 10 random seeds. Results in Figure demonstrate the stability and efficiency of SiPBA.
SIPBA
PZOBO
AID-CG
AID-FP
AdaProx-PD
AdaProx-SG
== 5 64
n
=128
m= 128
5
= 1000, n 128 256,
128. 0.1
256. 0..1
10a
10a
10
10
10a
10a
10a
10a
Test
10-2
10
10a
10a
10-3
10"3
10
10
Time (5)
Time (5)
Time (S)
Time (5)
Figure 2: Test loss time in Hepee-representation with varying dimensions and noise levels.
5.3.2
Deep hyper-repressentaion on MNIST and FaShionMNIST
To further assess the practical effectiveness of the pessimistic model, we conduct a more complicated deep hyper-representttion experiment real-world classification tasks. The problem is formulated as:
min max 1 [I f)w yeaill?, s.t. arg min m
1 - -II 0lw' Vtroin 11?
(19)
w/ W'EW m2
where f(,,0) represents a neural network parameterized by 0, and w corresponds to a linear layer.
We adopt the LeNet-5 architecture (22 as the feature extractor f(; 9) and evaluate performance on the MNIST and FashionMNIST datasets. Each dataset is randomly split into 50,000 training samples, 10,000 validation samples, and 10,000 test samples, with performance evaluated by test accuracy. We compare the pessimistic formulation (1)), trained with SiPBA, to its optimistic variant (replacing
max with min in the upper level) trained with AID-FP, AID-CG 29 and PZOBO 622 Mean results
over ten runs are shown in Figure 3 which shows that SiPBA achieves the highest test accuracy.
MNIST
FashionMNlST
1.0
3.0
acrunryy
8.6
0.0
0.90
0.96
0.4
0.4
0.92
160
180
200
160
1.00
0.0g
0.0
200
Figure 3: Hyper-representaaion on MNIST and FaShionMNIST.
6 Conclusions and future work
This paper introduces a novel smooth approximation for PBO, which underpins the development of SiPBA, efficient new gradient-based PBO algorithm. SiPBA avoids computationally expensive second-order derivatives and the need for iterative inner-loop procedures to solve subproblems.
The current study is confined to deterministic PBO problems. However, significant number of practical applications feature PBO problems within stochastic settings. Extending the SiPBA methodology to effectively address these stochastic PBO problems presents a crucial and promising direction for future research. We hope this research stimulates further algorithmic development for stochastic PBO.
10

---

Acknowledgements
Authors listed in alphabetical order. This work was supported by National Key R&D Program of China (2023YFA 101 1400), National Natural Science Foundation of China (12222106, 12326605), Guangdong Basic and Applied Basic Research Foundation (No. 202281515020882) the Longhua District Science and Innovation Commission Project Grants of Shenzhen (No. 20250113G4346822) and Natural Science Foundation of Shenzhen (No. 00250030150024003)
References
[1] A. Aboussoror and P. Loridan. Existence of solutions two-level optimization problems with nonunique lower-level solutions. Journal of Mathematical Analysis and Applications, 254(2):348 357, 2001.
[2] A. Aboussoror and A. Mansouri. Weak linear bilevel programming problems: existence of solutions via a penalty method. Journal of Mathematical Analysis and Applications, 304(1):399- 408, 2005.
[3] E. Alekseeva, Y. Kochetov, and E.-G. Talbi, A matheuristic for the discrete bilevel problem with multiple objectives at the lower level. International Transactions in Operational Research, 24(5)995--91,, 2017.
[4] G. B. Allende and G. Still. Solving bilevel programs with the KKT-approach. Mathematical Programming, 138:309-333 2013.
[5] M. J. Alves and C. H. Antunes. semivectorial bilevel programming approach to optimize electricity dynamic time-of-use retail pricing. Computers & Operations Research, 92:130-144 2018.
[6] I. Androutsopoulos, J. Koutsias, K. V. Chandrinos, G. Paliouras, and C. D. Spyropoulos. An evaluation of naive Bayesian anti-spam filtering. In Workshop on Machine Learning in the New Information Age, 2000.
[7] M. Arbel and J. Mairal. Amortized implicit differentiation for stochastic bilevel optimization. International Conference on Learning Representations, 2022.
[8] D. Aussel and A. Svensson. Is pessimistic bilevel programming a special case of a mathematical program with complementarity constraints? Journal of Optimization Theory and Applications, 181:5045520, 2019.
[9] X. Ban, S. Lu, M. Ferris, and H. X. Liu. Risk averse second best toll pricing. In Transportation and Traffic Theory 2009: Golden Jubilee: Papers selected for presentation ISTTT18, a peer reviewed series since 1959, pages 197-218. Springer, 2009.
[10] A. Beck. First-order methods in optimization. SIAM, 2017.
[11] I. Benchouk, I. O. Jolaoso, K. Nachi, and A. B. Zemkoho. Relaxation methods for pessimistic bilevel optimization. arXiv preprint arXiv:2412. /416, 2024.
[12] I. Benchouk, L. O. Jolaoso, K. Nachi. and A. B. Zemkoho. Scholtes relaxation method for pessimistic bilevel optimization. Set- Valued and Variational Analysis, 33(2):10, 2025.
[13] D. Benfield, S. Coniglio, M. Kune, Vuong, and Zemkoho. Classification under strategic adversary manipulation using pessimistic bilevel optimisation. arXiv preprint arXiv:2410.20284 2024.
[14] F. Bonnans and A. Shapiro. Perturbation analysis of optimization problems. Springer, 2013.
[15] L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-31, 2018.
[16] M. Brückner and T. Scheffer. Stackelberg games for adversarial prediction problems. In International Conference Knowledge Discovery and Data Mining, 201
11

---

[17] V. Bucarey, S. Calderón, G. Muñoz, and F. Semet. Decision-focusee predictions via pessimistic bilevel optimization: A computational study. In Integration of Constraint Programming. Artificial Intelligence, and Operations Research, 2024.
[18] H. L. Calvete, C. Galé, A. Hemández, and J. A. Iranzo. A novel approach to pessimistic bilevel problems. an application to the rank pricing problem with ties. Optimization, pages 1-34, 2024.
[19] B. Colson, P. Marcotte, and G. Savard. An overview of bilevel optimization. Annals of Operations Research, 153:235-256, 2007.
[20] S. Dempe, B. S. Mordukhovich, and A. B. Zemkoho. Necessary optimality conditions in pessimistic bilevel programming. Optimization, 63(4))505- 2014.
[21] S. Dempe, B. S. Mordukhovich, and A. B. Zemkoho. Two-level value function approach to non-smooth optimistic and pessimistic bilevel programs. Optimization, 68(2-3):433 455, 2019,
[22] S. Dempe and A. B. Zemkoho. The bilevel programming problem: reformulations, constraint qualifications and optimality conditions. Mathematical Programming. 138:447-473, 2013.
[23] S. Dempe and A. B. Zemkoho. Bilevel optimization. In Springer Optimization and its Applica- tions, volume 161. Springer, 2020.
[24] Facchinei and J.-S. Pang. Finite-dimensional variational inequalities and complementarity problems. Springer. 2003.
[25] L. Franceschi, M. Donini, P. Frasconi, and M. Pontil. A bridge between hyperparameter optimization and learning-to-leann. In Advances in Neural Information Processing Systems, 2017.
[26] L. Franceschi, M. Donini, P. Frasconi, and M. Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning, 2017.
[27] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Machine Learning, 2018
[28] K. Gao and O. Sener. Modeling and optimization trade-off in meta-learning. In Advances in Neural Information Processing Systems, volume 33, pages 11154-11165 2020.
[29] R. Grazzi, Franceschi. M. Pontil, and Salzo. On the iteration complexity of hypergradient computation. In International Conference on Machine Learning, 2020.
[30] A. Gu, S. Lu, P. Ram, and L.. Weng. Nonconvex min-max bilevel optimization for task robust meta learning. In International Conference on Machine Learning. 2021.
[31] Z. Guan, D. Sow, S. Lin, and Y. Liang. Adaprox: A novel method for bilevel optimization under pessimistic framework. In Conference on Parsimony and Learning, 2025.
[32] L. Guo, J. J. Ye, and J. Zhang. Sensitivity analysis the maximal value function with applications in nonconvex minimax programs. Mathematics of Operations Research, 49))::33 556, 2024.
[33] M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application actor-critic. SIAM Journal on Optimization, 13(1):147-188) 2023.
[34] Q Hu, B. Wang, and T. Yang. A stochastic momentum method for min-max bilevel optimization. In Workshop on Optimization for Machine Learning, 2021.
[35] K. Ji, J. Yang, and Y. Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, 2021.
[36] D. Jiménez, B. K. Pagnoncelli, and H. Yaman. Pessimistic bilevel optimization approach for decision-focusee learning. arXiv preprint arXiv.2501.16826, 2025.
12

---

[37] T. Kis, A. Kovács, and C. Mészáros. On optimistic and pessimistic bilevel optimization models for demand response management. Energies, 14(8):2095, 2021.
[38] J. Kwon, D. Kwon, S. J. Wright, and R. D. Nowak. A fully first-order method for stochastic bilevel optimization. In International Conference Machine Learning, 2023.
[39] Kwon, D. Kwon, S. Wright, and R. Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. In International Conference Learning Representations, 2024.
[40] L. Lampariello, S. Sagratella, and O. Stein. The standard pessimistic bilevel problem. SIAM Journal Optimization, 29(2):1634-1655 2019.
[41] Z. Lin, H. Li, and C. Fang. Accelerated Optimization for Machine Learning. Springer, 2020.
[42] B. Liu, M. Ye, S. J. Wright, P. Stone, and Q. Liu. Bome! bilevel optimization made easy: A simple first-order approach. Advances in Neural Information Processing Systems, 2022.
[43] Liu, Y. Fan, Z. Chen, and Zheng. Pessimistic bilevel optimization: A survey. International Journal of Computational Intelligence Systems, 11(1):25-7736 2018.
[44] R. Liu, Y. Liu, S. Zeng, and Zhang. Towards gradient-basee based bilevel optimization with non-convex followers and beyond. In Advances in Neural Information Processing Systems, 2021.
[45] R. Liu, Z. Liu, W. Yao, S. Zeng, and J. Zhang. Moreau envelope for nonconvex bi-level optimization: A single-loop and hessian-free frree solution strategy. In International Conference Machine Learning, 2024.
[46] R. Liu, P. Mu, X. Yuan, S. Zeng, and J. Zhang. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. International Conference on Machine Learning, 2020.
[47] Loridan and J. Morgan. Approximate solutions for two-level optimization problems. In French-German Conference on Optimization. Springer, 1988.
[48] J. Lorraine, P. Vicol, and D. Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International Conference on Artificial Intelligence and Statistics, 2020.
[49] S. Lu. Slm: A smoothed first-order lagrangian method for structured constrained nonconvex optimization. In Advances Neural Information Processing Systems, 2023.
[50] Z. Lu and S. Mei. First-order penalty methods for bilevel optimization. SIAM Journal on Optimization, 3472)119771199, 2024.
[51] Z.-Q. Luo, J.-S. Pang, and D. Ralph. Mathematical programs with equilibrium constraints. Cambridge University Press, 1996.
[52] C. Macdonald, I. Ounis, and I. Soboroff. Overview of the TREC 2007 blog track. In Text REtrieval Conference, 2007.
[53] D. Maclaurin, D. Duvenaud, and R. P. Adams. Gradient-based hyperparameter optimization through reversible learning. International conference on Machine Learning, 2015.
[54] V. Metsis, I. Androutsopoulos, and G. Paliouras. Spam filtering with naive Bayes-which naive Bayes? In CEAS, volume 17, pages 28-69. Mountain View, CA, 2006.
[55] B. Mordukhovich. Variational Analysis and Applications. Springer, 2018.
[56] I. Ounis, C. Macdonald, and Soboroff. Overview of the TREC 2006 blog track. In Text RÉtrieval Conference, 2006.
[57] V. Outrata. On the numerical solution of class of stackelberg problems. Zeitschrifi für Operations Research, 34(4):255-277, 1990.
13

---

[58] F. Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference on Machine Learning. 2016.
[59] Pedregosa, G. Varoquaux, A. Gramfort, Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, and V. Dubourg. Scikit-learn: Machine learning in python. the Journal of Machine Learning Research, 12:2825 2830, 2011.
[60] R. T. Rockafellar and R. J.-B. Wets. Variational Analysis, volume 317. Springer, 2009.
[61] H. Shen and T. Chen. On penalty-based bilevel gradient descent method. In International Conference on Machine Learning, 2023.
[62] D. Sow, K. Ji, and Y. Liang. On the convergence theory for hessian-free bilevel algorithms. In Advances in Neural Information Processing Systems, 2022.
[63] S. Sra, S. Nowozin, and S. J. Wright. Optimization for Machine Learning. MIT Press, 2011.
[64] M. A. Ustun, L. Xu, B. Zeng, and X. Qian. Hyperparameter tuning through pessimistic bilevel optimization. arXiv preprint arXiv:24/2.03666, 2024.
[65] Virtanen, R. Gommers, T. F. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, et al. Seipy 1.0: fundamental algorithms for scientific computing in python. Nature methods, 17(3):611-72,, 2020.
[66] H. von. Stackelberg. The Theory of the Market Economy. Oxford University Press, 1952.
[67] W. Wiesemann, A. Tsoukalas, P.-M. Kleniati, and B. Rustem. Pessimistic bilevel optimization. SIAM Journal on Optimization, 335333333-38,, 2013.
[68] Y. Yang, Z. Si, S. Lyu, and K. Ji. First-order minimax bilevel optimization. In Advances in Neural Information Processing Systems, 2024.
[69] W. Yao, C. Yu, S. Zeng, and J. Zhang. Constrained bi-level optimization: Proximal lagrangian value function approach and hessian-free algorithm. In International Conference on Learning Representations, 2024.
[70] J. Ye and D. L. Zhu. Optimality conditions for bilevel programming problems. Optimization, 33(1):9-27, 1995.
[71] B. Zeng. A practical scheme to compute the pessimistic bilevel optimization problem. INFORMS Journal on Computing. 32((): 121-111-111111 1142, 2020.
[72] Y. Zhang, G. Zhang, P. Khanduri, M. Hong. S. Chang, and S. Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. In International Conference on Machine Learning. 2022.
[73] Y. Zheng, Z. Wan, K. Sun, and T. Zhang, An exact penalty method for weak linear bilevel programming problem. Journal of Applied Mathematics and Computing, 42(1):41-49, 2013.
[74] Y. Zheng, G. Zhang, J. Han, and J. Lu. Pessimistic bilevel optimizatioon model for risk-averse production-distrribttio planning. Information Sciences, 372:677-689, 2016..
[75] Z. Zheng and S. Gu. Safe multi-agent reinforcement learning with bilevel optimization in autonomous driving. IEEE Transactions on Artificial Intelligence, 6(4): 2025.
14

---

A Numerical experiment
In this section, we provide the specific description of experiments in Section 5 were conducted on CPUs except for the spam classification task, which utilized an NVIDIA H100 GPU. The primary compute node features dual Intel Xeon Gold 5218R processors operating at 2. 2.1 base frequency (4.0GHz turbo boost), featuring 40 physical cores (80 logical threads) with a three-tier cache architecture: 1.3MB LI, 40MB L2, and 55MB L3 shared cache. The NUMA-based memory architecture partitions resources across two distinct domains, with hardware support for AVX-512 vector instructions and VT-x virtualization. Security mitigations against Spectre/Meitdown vulnerabilities were implemented through combined microcode patches and kernel-level protections.
All experiments
A.1 Synthetic example
For the problem 5.1 we can get the value function by simple calculation:
1
|ar
x
(x(2) || e112-11v" eel?, where y (xxx)=
(20)
2
which implies that (a", .y") in Table we fix the sesper-prrameters as
2: 2/3)
Except for the stability tests of the initial step sizes reported
= 0.001, = 0.001, 8 = 0.1, og = 0.1, 80 = 0.001 Po = 10, do 0.01. (21)
For the implementation of AdaProx-PD, we first fix & = 0.001, o = 0.001, = t. 0g = 7 / 2/ 2a) 1/T, and set 7. (To Th 7//t, /t, K 100, and N min / [), 200
Then we perform a grid search for T = min (1/ Ve, 200).
1/m. 1/TO. E (0.1, 0.01, 0.001, 0.00011, a (0.1, 0.010.11..0000 0.001}.
However, none of these yielded satisfactory convergence. We thus fixed parameters across iterations, set K = 100, T' = 200, N = 10, 1, (L,, + 2a) = 1/T and conducted grid search to find a best parameter get lowest loss, where the grid is set as follows:
1/n, 1/ E (0.1, 0.01, 0.001, 0.0001,, o, E (0.1, 0.01, 0.001).
As result, we have 1/7 0.001, 1/1 0.001, o 0.001, 0.1 and / 0.001 for AdaProx-PD.
For the implementation of AdaProx-SG, we fix 7 = t, 0, = 7t41 2/(L, + 2a) = 1/7 and K 100, and N (in 200). T min/1/c,200) Then perform grid search for 1/70. 5 E
0.0001). a, 3 E {0.1, 000,, 0.001}.
As result, we have 1/700 0.1, 0.001, ę = 0.1 and B 0.1 for AdaProx-SG.
For the implementation the Compact Scholtes and Detailed Scholtes relaxation method in [12. utilize the fsolve solver from the SeiPy library (65). In each outer iteration, the value of f is updated as + 1 = 0.1f; with ty = 1 and fix c c= ty.
A.2 Spam classification
Spam classification remains a critical challenge in machine learning due to adversarial dynamics: spammers adapt their strategies in response to deployed classifiers, while models trained on specific datasets often exhibit poor cross-domain generalization. In this paper, we extend the pessimistic bilevel model for Spam classification in [16]:
min max I(w, 2) + Reg(w) wERe
s.t. à E min ('(w,=') + )ello(x') 11= (22)
ZEX
where denotes the classifier parameters, (x, v) represents vectorized training data, I (resp. 1') corresponds to the classifier (resp. adversarial generator) loss, Reg(-) denotes the regularization term, and ())- characterizes the feature of data. This framework explicitly models spammer adaptations through adversarial samples é, enhancing classifier robustness against evolving threats.
We evaluate our model on four benchmark datasets:
15

---

TREC06 (37,822 emails: 24.912 spam / 12,910 ham):
https://plg..uaterlo.. ca/
TREC07 (75,419 emails; 50.199 spam / 25,220 ham):
https://plg.uwaterlooo ca/
EaronSpam (33,715 emails; 16,545 spam / 17,170 ham):
https:// edu/
enron/
LingSpam (2,893 emails; 481 spam 2,412 ham): http://wwww.ubb....... http://wwww.uubbggg/////////////
Batta/iingspmmpuulli.c. tar.z
The text was vectorized using l'fidrvectorize that removed English stop words, retained only terms appearing in at least five documents, and limited the feature space to the top 9000 most informative terms. We represent the resulting vectors as the variable and train the model in the vectorized space. To simulate the real world situation, we assume that email authors always aim to have their messages classified ham; accordingly, define l' as the loss incurred when email is classified as spam, using the same formulation (cross-entropy or hinge) as The specific definition of and used in experiment is given by
[[w, x, (((w,x) 1 E max {0, w T I;),
1 E max (0, w x,yec.
PBO-Hinge
([ ('(w,x) x)
CrossEntroppyu'' (w vt1),
PBO-CE:
CrossEntropy(w' 1).
where 2; denotes the input data, yi E {-1,1} denotes the label (-1 for spam and for non-spam) and CrossEntropy - (y log(o(w") x)) + (1 y) log(1 (w x))) and a(2) 1/(1 + + is the Sigmoid function. The function & is defined as
defined by CrossEntropy(w" z,
x(x) = :=)=pppp xPp,
where the matrix P& consists of the top principal components obtained from the principal component decomposition of the sample matrix. This choice is motivated by the assumption that meaningful information emails is primarily captured by the principal components, and modifications made by spammers generally do not alter this core content. Therefore, we penalize changes along the principal components to enforce robustness against adversarial modifications. In this experiment, we always set h = 100, A 0.01, X2 0.1 for SiPBA.
For the implementation of SiPBA, fix po 10, σo 10-6 0.01, g 0.01 and 0.16, and we set the hyperparameter as follows:
ong 0.03,
30- 10-6
for PBO-Hinge, for PBO-CE,
TREC06:
Og 0.1,
3n 10-4
Ok 0.1,
S0 = 10 -
for PBO-Hinge,
TREC07:
0.05,
3 = 10
for PBO-CE,
ag = 0.02, 30 10-7
for PBO-Hinge,
EpronSpam:
(ro = 0.01, 30 = 10-7
for PBO-CE,
Grg 0.02, 30- 5 10-5
for PBO-Hinge, for PBO-CE.
LingSpam:
ak 0.05, 30- = 10-7
For the implementation SQP-Hinge and SQP-CE, we set (p(x) == x (to ensure the lower level can be uniquely solved) and X 0.01, X2 = 0.001 and solve the problem using the trust-constr method from the scipy.optimize solver [65].
For the implementation of Single-Hinge and Single-CE, we use SVC and Logistic Regression from scikit-learn 59 with default setting and mar iter 10000.
A.3
Hyper-repreesentatinn
In the linear hyper-representation on synthetic data, we follow the data generation procedure of 62 Specifically, generate the ground-truth matrix Hreat Rpxd the vector Wreat E Rd and
16

---

the inputs Xtrain- Yeal, Xtest by sampling each entry independently from the standard normal distribution (0, 1). We then generate the train, valid and test data by Y()) =x)==/x H Finally, we
add (0,, a²) with 0.1 and 1 to X Xtrain and Yeal; Mtrain to simulate the noise condition. The parameters of the algorithms are initialized as
For SiPBA, we set 0.01, 0.01, 0.16, = 10, 10-4. And the stepsize is set as ag 5 x 10 4 S.g = 10 for m 500, a 0.1 and ag 10 1004, 5. 10 for the remaining senarios.
For AdaProx-PD, we set K = 100, T 20, 10, = 2/ + 2a) 1/T and a 0.1, { = 0.001 and 3 0.001. And the stepsize is setted as 17 10 2 10 2 10 5 10 for the four senarios in Figure 2
For AdaProx-SG, we set K = 100, T min [20, - logg//))))(())
2x) = 1/7, = 0.001, 0.001, 3 = 0.001 and 7 = 10a.
For AID-FP, AID-CG and PZOBO, keep the setting presented in wttttttt///// pettps://githnn com/ sowmaster /es acobians aitiiiann/teeennaeee /ttreemmaster except that the inner learning rate is set found it's more stable for these algorithms.
0.0001
For the classification tasks on MNIST and FashionMNISTT, we split the dataset into 50,000 training samples, 10,000 validation samples, and 10,000 test samples. Both the upper and lower levels are trained using the LeNet architecture, following the setting in [62]. During each training iteration, we randomly select 256 samples to compute the loss and gradients. The parameters of the algorithms initialized as follows:
For SiPBA, we set p 0.01, 7 = 0.01, = 0.16, Pa 10, = 0.01, 0.01 and
30 = 0.1.
For PZOBO, adopt the implementations from https://gittu/: httpiithuu..o..aaeeeeeeemeeeeeee com/sowmaster/ esjacobians/tres waeeiiannn/teeeeeeeeeeeeeeeeeeee wtteeeeeeeeerrreee and set number of inner iterations T = 30 for training on FashionMNIST to ensure proper convergence.
For AID-CG, we set the learning rate to Ir = 0.001 (0.0005) and the number of inner iterations to T (50) for training on MNIST (FashionMNIST).
For AID-FP, set Ir 0.001 and T 20(30) for training MNIST (FashionMNISST)
A.4 Parameter Selection
The implementation of SiPBA includes seven parameters, namely Ou, Su, dp. Pu. q, S. The parame- ters s, p. and collectively govern the fundamental trade-off between value function approximation accuracy and iterative step size selection. The parameter p controls the growth rate of the penalty coefficient Pa = poke, while g determines the decay rate of the regularization coefficient σ ook-9. Larger values of p and yield faster convergence of the approximate value function &pn. (x) the true objective. The parameter regulates the step size decay rate a aok for the primal iterates =²
The theoretical requirement s 2 8p + 8q reveals an essential trade-off:: choosing larger values for and q accelerates the value function approximation but necessitates a larger s, resulting in smaller step sizes ag that slows down the convergence rate of z Conversely, smaller p and 9 permit more aggressive step sizes through reduced s, but at the cost of slower convergence of the approximate objective m (x) to the true value function, potentially degrading overall algorithmic performance.
We provide practical guidelines for parameter selection here. Specifically, the update rules given by:
0g = ook 88--8p- 8q with default settings p q 0.01 and po 10. Therefore, tuning is only required for the three scalar parameters: ag. ,9. and og.
18p---8p-8
Bg = -ok--2p- P P
a = ook
B Proofs for Section 2
This section provides the proofs for the theoretical results established in Section 2.
17

---

B.1 Equivalent minimax reformulation of ((x)
Lemma B.1 Consider the function
<(x) == max (F(r,v) s.t. E {(x)),
where
S(x) == argmin f (x,zy).
Then, for any x E X, we have the following equivalent minimax reformulation:
<(x) min max
(F( s.t. f(x, f(x,2))
zEY yEY
Proof. Let x X be an arbitrary point. The assumptions that S(x) is nonempty, and F(z, y) is j--trongly concave with respect to y, and using the fact that S(x) is closed, we conclude that there exists some y" E ((x) such that ((z) = F(r,y")
For any 2 E Y, since y" E S(z), it follows that
[(x ()) S (x,,2).
Therefore, we have
d(x) = F(z, v²) < max (F(2,8) s.t. f(z,0) & f(x,2))
yeY
Taking the minimum over all E Y. we obtain
((x) = (2, v*) I min max (F(z,)) v) s.t. f(x, v) S f(x, 2)}
.EY yEY
Next, we establish the reverse inequality. Consider the specific choice = = y², since y" S(z), we have
max (F(x,y) s.t. f(x,)) S f(x, max NEY
v) s.t. y S(x) 6(z).
yEY
Thus, we conclude that
min max zEY yEY
{F(r,)) s.t. f(x,)) s f(x, 2)} s ((())
This completes the proof.
B.2 Proof for Theorem 2.1
The proof strategy is analogous that employed in 69 Lemma A. We proceed by first analyzing an auxiliary function and then leveraging its properties to establish the differentiability of Φp.a (x).
Let us define an auxiliary function hzzz 2) as:
l(x,, 2) == max th (I, = min - -ppp0 (xr, y, v)=). yEY
yEY
By assumption, ( y, 2) is continuous differentiable X Y Y,, and -tbp V, 2) is j--ttoongly convex with respect to y for any (z,2) E X x Y.
The j-strongly convexity of - (x, z) with respect ensures the uniqueness of the minimizer of minyer - (Ir, y, 2) (equivalently, the maximizer of maxyey t (I, y, =)). us denote this unique maximizer 7 (x, z). Furthermore, it can be shown that - -ip (xc.
satisfies the
Specifically, for any (ž,z) E X x Y, there exists constant I. compact set B C R" and a neighborhood W of (z, 3) such that the level set {y E Y - vp.o (x, y, 2) S c} is nonempty and contained B for all (x, 2) W.
inf-compactness condition as stated in [14 Theorem 4.13) on any point (z, () X
Given that p condition holds, we can apply [14] Theorem 4.13 Remark 4.14]. This theorem implies that h(æ,, 2) is differentiable on X Y. and gradient is given by:
(x, y. 2) is continuously differentiable, '* 2) is unique, and the cofpacmpsss
Vh(a, (Vatpo (x, 2), V Verno (z, (2,
(23)
18

---

The strong concavity of Vp. (a. y, in y and the continuous differentiability of t imply that (2, 2) is continuous on X Y. Since V, v Poy and V are continuous by assumption, and y' (2, is continuous, it follows from 23 that Vh(x, z) is continuous on X x Y. Thus, h(x, 2) is continuously differentiable on Y.
The function &p.a (2) can be expressed using f(x,, z) as:
(p.a = min (xx, =EY
(24)
We are given that (2, y: 2) is o-strongly convex with respect for any fixed (x, E X Y. Since h(z, =) == mYX p. (2, y, z). and the maximum of set of functions preserves strong convexity (see, e.g.. [TO] Theorem 2.16]), can be shown that h(x, 2) o-strongly convex with respect to 2 for any fixed x E X. The o-strong convexity of h(x, 2) with respect to 2 ensures the uniqueness of the minimizer (x) = arg min h(x, 2). This strong convexity, combined with the established continuous differentiability (and thus continuity) of h(x,2), 2), ensures that h(z,, z) satisfies the inf-compast condition for for any z E X. Furthermore, 2p.o (x) is continuous on X.
We can again apply [4] Theorem 4.13, Remark 4.14] to (p.)(x) = minger h(x z). The conditions met: h(2, 2) is continuously differentiable (as shown above), and 2/.0 (I) unique. Therefore, (x)) is differentiable on X, and its gradient is given by:
Vo.o (z) =V= Vnh(a, Vatao (z, 2,"),
where 2" denotes 2/,o (z). Since V (Ir 2) is continuous on X Y x Y, T (z, 2) is continuous on X x Y and 2/20 (z) is continuous on X, the composite function V Vóp.o (x) is continuous on X. Thus, @p.a (x) is continuously differentiable.
Additionally, because "p, U, 2) is strongly concave in y and strongly convex in for any E X, and because mingey maxyeY up (x. y, 2) = maXyey mingey pr.e (x, y, 2) for any x E X, follows that y (x, 2²) Vp.a (I) for any E X. Thus, the desired conclusion is obtained.
B.3 Proof for Lemma 2.2
Before presenting the proof for Lemma 2.2 first establish some auxiliary results. Throughout this subsection, given sequences } and {ok), we will use the shorthand notations (z), (2, y, z). v (z) and 2 (xx) denote @pn.ore (x), Vonior (a, 2), Vpe.on (x)) and xp..ox (I)) respectively, for notational brevity.
First, establish uniform boundedness property for the saddle point components vx( and 2z(x).
Lemma B.2 Let {pp} and {ax} be sequences such that + oo and σ₁ + 0 as k + oc. Let B C X be a compact set. Then, there exists constant M such that for all k and all B.
I1 < M, and |,)[())|| S M,
where (v]()),)(())) is the unique saddle point of the minimax problem
mingey maxyey op (I, y. 2)
Proof. The proof proceeds in two parts, establishing the boundedness of (x)) and (2)( separately, both by contradiction.
Suppose, for the sake of contradiction, that {u% (x)) is not uniformly bounded. Then there exists sequence } C B such that |[vv + Do as + oc.
By Assumption 2 for each Fy B. there exits Sr. Eg such that 2h = 2 E S(zx) n D, where
D C Y is a compact set. Thus, the sequences {ūx} and {&+} are uniformly bounded. Since F(z, y) is continuous differentiable on X x Y and is p-strongly concave in y for any X, and 0 + 0.
we have
lim F(Zx, (xx)) || -88--onnn (x)) ax) -c. k0000
(25)
19

---

Next, since 2n E ((x)), we know that (((x)) 2 f(z,, &x). Given Pk > 0, it follows that:
d (2k, yy (2x), 24)
FI Ui (r()) Pa (f v1 - f( 2x)) 11 112 0x (Ix);
S F(R, vk((w) + 0k || | (vr)) 2x)-
From
25
we deduce:
lim ( ux ( 2xx) -00
(26)
k-+20
By the saddle point property of (vi (zx)) =f(x)))))))))))))))))
(2R, V (mr),, , 2x) 2 dha (Zks Ui (za) 27 (xx)) 2 (Tk Dhs =((x)))
Combining this with 226 yields:
lim the (2E, Un. (xx)) -00
(27)
Since UR S(x)), we have f(r* 2 (m+)) 2 f( 0n). Thus:
th (2x, DR. 21 (xx)) F(zx, 2k) Pa (f (0k. 0&) f fIk 2 (xx)) -h (=x)() (f(x))
Th |=; )12 σx (ūk = (xx))
2 F(rk, 91)
0k (x(((x)) - 0xx12
σk 1 1
F(Zk, 0k) +
2
2 F( 9k) 2 11
0k
Since {a*}} and { are bounded, and F(x,, y) is continuous on X x Y, F(xk, 9k) 7 ll bounded. As 0% - O, the term F(rK; Ut) % | 1? bounded below. This contradicts (27). Therefore, our initial assumption was false, and there must exist M >> O such that [x)]( s M for all and x E B.
Next, we show that there exists M > 0 such that [+)]] < M for any k and E B. Suppose, for the sake of contradiction, that (x)) is not uniformly bounded. Then there exists sequence { C B such that (Ixx)] + 00 as k + co. By Assumption 2 for each Ik, there exists 2g ((xx)
for a compact set D, so {$x} } is bounded.
From the saddle point property, = (mx) minimizes vu (T(),,, =) over = E Y. Thus:
tu Vi (xx), = (*x)) I ( ve (x)).
Expanding this inequality, simplifying and rearranging terms:
par( (xxx)) + Ok
2 ( - ((())) (ark: 2x) + Tk
2 || V (xx)
Combining the above inequality with the fact that f (Irx: 2/ (Ix))
f 2x) yields that:
[ 2pk (f(*e, 2x) f(zn, 2 (z - v (z+) 1| < (xx))=) (28)
σ%
The right-hand side of (28) is bounded because { and { (#+)) are bounded. However, since
|| (ax))l and (rx())) is bounded, the left-hand side (2xx) y (**)) co. This presents contradiction. Thus, our assumption was false, and there exists M > 0 such that for any k and x B, [z)]l < M.
Next, we demonstrate that accumulation points of WVpc.on (x)} belong to the solution set S( when I& + Z.
Lemma B.3 Let } and {au} be sequences such that Pk any sequence } C X such that æn + 7 E as k + 20, we have
and σ 0 as k + cc. Then, for
lim [( vi (xx)) S min [ v) k
(29)
yEY
Consequently, for any accumulation point ō of sequence (xx)) we have S(ū).
20

---

Proof. Let y be an arbitrary point in S(z). From the saddle point property, (2x)) maximizes 4h (Tx. y: (xx)) over y Y. Thus:
( (xx), =z 2 ( 0s (xx))
Expanding this incquality:
F(rk, v - Paf (m o2 (mx)) - (vE(())) (xxx)) 2 Firk. 0) P D) - -ok (Ū. =xx))))
Rearranging this inequality to isolate terms involving f. and since > 0, we can divide by px:
f (x f(x.. - (F(x)))((H)) F(xx 0)) + ok [v(((x)) - (
1
Pk:
Pk
By Lemma B.2 (vi and (=] (xx( are uniformly bounded. Since F(x,y) is continuous X x Y and } converges, F( (xx)) and (I 4) are bounded. Given Pk + co and + 0, the entire right-hand side of the inequality converges to k - oc. Therefore, by taking kt in the above inequality, and since f( y) is continuous on X x Y, we have
lim sup (I (xx))
lim f(R V) min f( Io-
8-+50
yEY
This concludes the proof.
proof of Lemma 2.2 We prove the first statement (i.e., lim dx(() S ((z) by contradiction.
k-+00
Suppose there exist ā E X and ô > 0 such that
lim sup (7) > ((z)+ + 8
k+
Then, by properties of lim sup, there exists a subsequence (which we re-index by le for simplicity) such that
lim (x) ((z) 5
A
Recall that (z), =1 (z)) the saddle point for the minimax problem mingey maxyEY t/a (Z, 2).
Thus, (z( ( y (z), 2 (z)). Expanding 4/k, we have:
F(E, (T)) pM (Z, vit (=)
f(E (x)) Th2
(4), = (+)) 2 ((x) + (30)
By Lemma B.2 [vg (+)} bounded. Thus, we can extract further subsequence (again re-indexed by k) such that vi (z) ý for some Y. By Lemmal B.3 this implies S(z).
From the saddle point property, +x) minimizes tha (7. (F)) 2) over E Y. Therefore, d/ (z. VT ()))) < tx (T)
Expanding this:
Tk 2f(()
Tk
(z)
2
Rearranging:
Ph (f(z, =))) - (( 2h [=)(,) )(( so.
Combing this with 30 yields that
F(2, (t()) - Th (+) 2 (z) +
2
Taking & oo in the above inequality, since F(x, y) is continuous on X Y. (x)( is bounded and + 0, we have
F(x. v) 2 ( +
However, since ÿ E S(x), by the definition ((x)) max F(2, v), we must have F() S o()). This leads to ((x) > F(I, Ø) 2 d(z) + 8. Since 5 > 0, this is a contradiction. Therefore, the initial assumption was false, and we must have
lim (x) < ((x), X. k
The second conclusion then follows from this result and the Proposition 7.30 in [60
21

---

B.4 Proof for Proposition 2.3
For any given x E X, Assumption 2 ensures that the set S(x) is nonempty and closed. Combined with the p-strong concavity of F(x, y) with respect to y, this guarantees the existence of a unique maximizer y (z) Sxx) such that ((x) F(z, y²), i... y (z) arg max)) F F(r.)) y).
We first establish uniform boundedness property for y" (x) when is restricted to compact set.
Lemma B.4 Let B be compact set in X. Then, there exists constant M such that for any I E B,
(x))l S M,
where y (x) arg maXyeS(x) F(x,)) v).
Proof. Suppose, for the sake of contradiction, that such a uniform bound M does not exist. Then there must exist sequence {**) } C B such that (2x))l Assumption 2 for each Zv. there exists an element y&e S(zx) n D, where D is a specified compact set. Consequently, the sequence }y²} uniformly bounded.
h - According to
Because F F(x, is continuous differentiable on X x Y and is p-strongly concave in y for any x E X, Ily" (Ix)]l - oc leading to:
lim F( y (xx)) = -00
(31)
R
By the definition of y (rxx) as the maximizer of maxyes(wx) FirKs y), and since ye S(xx)) D, we
have:
F( y (xx)) 2 F( (x).
Given that (#ks y2 (xx)) + oo from 31 must also hold that:
lim F(rks yk)) -00.
R-+000
However, since both {ax} and {yk } are bounded, and F(x, y) is continuous on X Y, the sequence [F(*k, }t)} must be bounded below. This contradicts the finding that F(IK, Mke) - -o0. Thus, our initial assumption must be false, and we get the conclusion.
Next, we establish an inequality relating (z) and ((x).
Lemma B.5 Let p. > 0 be given constants. Then, for any X.
(po(x) 2 (xx) 1l (x)
where y (x) = arg maxyes(s) F(x,y). v).
Proof. For notational brevity within this proof, let y denote yy (x). Because (x, y, is strongly
concave in y and strongly convex in 2, have:
tp. (x) = min max
(p v) = max min pp 2)
#EY yEY
yEY sEY
From the max-min formulation, it follows that for any specific choice of y, such y =y"
(p)(()) 2 min (p
(32)
zEY
Since
p Ve..v'22 ,2) = F(z, v²) (z v²) + pf 2) + 2 -1l=l--o(v* o olv", ,2),
find min pp (x, y² 2). we can minimize the terms dependent on z:
argmin {pf(o, 2) + Ill== - y" 12]
argmin ( y², 2) sEY
sEY
Since y S(x), follows that
argmin & An (1, "/ 2) {y²}. sEY
Substituting = into (r, 2)): min (p, y", = (x. vv" F(zx)")))" 11v "1l="1" 112 6(x)) 2 '1v"'1²
zEY
Combining this with 32). the conclusion follows.
22

---

Now, we are ready to provide the proof for Proposition 2.3
Proof of Proposition For any T& E X such that
> 0 and for each by the definition of infimum, there exists an
ppr (xx) S inf Ppc (x) tc. zEX
(33)
Applying Lemma B.5 to Oprio (xx)):
Ope.o (Ix) 2 (xxx)
Tk 2
#eX lly" (Ix))1 2 inf ((x) 2 lly" (xx))) (sx)
(34)
Y is bounded, we have that sequence {y" (r+) } is bounded. Alternatively, if X bounded, Lemma B.4 establishes that {v((xx) (rxx)} is bounded. Under either condition, since d - 0 as k +
Ok ll (xx)) = 0.
lim 8000
2
Combining this with 33 and (34
inf (xx) s lim inf
inf Ope (x)) +
zex
aEx
Since e > was arbitrary, we can let ε + 0, yielding:
inf (zz) s lim
inf op
#EX
xExx
Then the conclusion follows by combining the above inequality with Lemma 2.2
B.5 Lower semi-continuity ((x)
In this part, we demonstrate that the inner semi- semi-continuity of the lower-level solution set mapping S(x) serves as sufficient condition for the lower semi-continuity of the value function d(x).
We begin by recalling the relevant definitions.
Definition B.6 function ((x) R + R U (oo] is lower semi-continuous (Ls.c.) for any sequence {2x} } such that + T as k - oc, it holds that
d(x) lim inf d(xx).
k
Definition B.7 A set-valued function S(x) R" = Rm inner semi-contimenn at if S(ø) S lim inf (zx), where lim inf S(x) = {y Vzg Byk E S(Ix), s.t. Vs > y).
R-BB
2-42
Lemma B.8 S(x) is inner comiicontiiuous at X. then Φ(z) lower comi-continuous at ã.
Proof. Let } be an arbitrary sequence such that I - I as k + xc. If d(ž) = co, the inequality hods trivially. Assume ((z) > 00. For any > by the definition of supremum, there exists an element E (()) such that
F ye)
((T)) ( c.
Since S(x) inner semi-continuous at T. there exists a sequence {yk} such that y E S(xx) for each k. and
lim yk = ye. k0000
Then, by the continuity of F(x,y) y) and the fact that F F yk) S ((xx), we have:
((x) < w.) lim F(X,, wa) < lim inf d(xx). k-000
(35)
Since this inequality holds for any arbitrary e >> 0, we can let + 0 to conclude:
((T) lim inf d(xx)) k0000
23

---

B.6
Proof for Lemma 2.4
Proof of Lemma 2.4 From Lemma B.5 for each we have the inequality:
Pp m (ax) 2 ((wx)
Tk lly (srx))
(36)
where y (x) = arg ma F(x, 3). Since the sequence { converges to I, it bounded. By
Lemma B.4, the sequence {y" (xx)) } is uniformly bounded. Given that oR - 0 as + oo and {y" (Ixx) ) bounded, it follows that
Tk lly (xx)]l²= 0.
lim 700
Combing with (3).. we obtain
lim inf ((Tx) S lim inf Opeio (FR)) k=000
k+000
Thus, by the lower semi-continuity of ((x) at ž, we conclude that:
④ S lim inf ((x)) lim inf Pp (2%).
(37)
k-yoc
k0000
This completes the proof.
B.7 Proof for Theorem 2.6
Proof for Theorem 2.6 Since { is bounded, Lemmas B.2 and B.4 imply that the sequences {u" (mx)} and [w ( (xx))) are also bounded.
First, show that S(z) is outer semi-continuoud on X.
Let {11g,15) an arbitrary sequence such that Vi E X. yı S(x,) and (1), + (I. D) as j co. Since Vj E S(zz), we have
f(r, Uj) S f(zj, (2)).
Taking the limit as j + oo and using the continuity of / on X x Y, we obtain
f 0 S f(ž v (+))
min f(t
sey
Hence, ÿ E S()), which shows that S(x) is outer semi-continuous on X.
Next, we establish that
lim y² (Ix) y (x²)
Let {3' (x;)} be any subsequence of {y" (xx)) such that v - y as + oc. By assumption, æy - T. From the outer semi-continuity of ((x) established above, it follows that ÿ S(z). Moreover, by definition (ιx,) F' y² (xz)) and (()) F(2, y (z)). Using the continuity of on X Y and the lower semi-continuity of Φ. we obtain
F(a, Ø)
lim F( (x,)) = lim o(z,) 2 (()) = F(I, (T)).
Since zj E (T)) the above inequality implies that y E arg maxyeS(a) F(ū, v). Because S(z) is convex, and F(ē, y) is strongly concave in this maximizer unique, so J = y (T). Hence any accumulation point of sequence (v" (rx)) equals (*)). Since {y" (xt)) is bounded, conclude that lim y (Ix) = y (ø).
Third, we show that
lim v((())) = y" (z). 8-000
Let (r,)) be any subsequence of (v]())) such that (2t - y as - co. By Lemma B.3 we have E S()). Since (x,) maximizes vy (z, v. (z over E Y. follows that

---

Expanding both sides gives
P(2z, - ( ((
2
+o ( (()))
Since v((x)) S(zz), we have [ax, (zz)) [(x),0) (z))) 2 0 and thus
(1 F(z,, (z,)) 2, ((r)(z))) - (w"())) 25
Taking the limit as j + oo and using the continuity of F, together with lime 1/ (Ix) = y² (z), yields
F( D) - F(T, y (T) 2 0.
Since y E S(t), this implies that y E arg maS)) F(2, y). Since S(t) is convex, and F(z, y) strongly concave y, we must have yj = (.). Therefore, all accumulation points of (vā
equal y" (z). Then, the boundedness of [v] (mx)) implies that limg- (zx) y (T))
Finally, we show that
lim =xxx) = y (z). k
Since (x() minimizes vu (T (xx),, 2) over E Y, we have (x v (1x)), 2 (xx)) S (.
Expanding this inequality gives
PKI( =1 (xx))
|| (xxx)1 (u = (xx))
2
Spaf(Ek, 32 (xx))
|| (xx)]
on (ox)).
Rearranging terms yields
Pk (f(#R 27 (xx)) - f(ans 42 (xx))) + 2 0 [1][(T]]]))) - v1(22 - 0k 11 (xx) 1xx21
2
Since y- (xx) E ((x)), it follows that f 2 (Ix)) - f(xx. 32 (Ix) 2 0 and hence
[1 (xx) [1 - (x*) (xx))
Because lim y² (xx) = y" (x) = lim ve (mx)), we have
lim 111 (Ix) (xxx) O. R+000
Taking k oo in the above inequality yields
lim [ v (xxx)) 0, k0
and consequently,
lim xxxx = lim vū(xx) = y" (z). k
k-t00
This completes the proof.
C Proof for Section 4
Throughout this part, we assume Assumption 4 which states that is a bounded set.
Given sequences Pk and ok. for notational conciseness, we employ the shorthand notations @u (z). th (ar, y. =), yī and =f(x) to denote &pr.cr (x), Wpn.or (x., y,,),, =), Vf (x) and = (r), re- spectively. We use u to denote the pair u := (y. 2). and correspondingly, u² := (1+,2*) and u (x)) (x), = (xr).. The symbols (x))), Ny and Ay ( y) denote the normal cones
the sets X, and x Y at x, and (x, y), respectively.
Let LF and Ly denote the Lipschitz constants of V FF(x,)) and (x on X x Y, respectively.
25

---

Consider the sequences {px} and {ox} such that - dc and + 0 as k + 30. As established in Lemma B.2 the quantity M, := supk, max flgg (z) (=) is finite. This implies that the collections of points {vk [z)) and (x) are bounded. Given that X is bounded, and f and its
gradient ff are assumed to be continuous on X x Y, the continuity over this effectively bounded domain of evaluation ensures that the suprema M == sup,,aex max y (z))., [f =f and M = = max v (=)) I f =f(r))] are also finite.
With given sequences {ok} and ). for each we define the operator Tp : 1R=+2m 22m as
(2, == v-V y. 2). V (2,
By assumption, for any fixed x X, the function (1, y, 2) is dx-Strongly convex in and p- strongly concave in y. Consequently, invoking [[0] Theorem 12.17 and Exercise 12.59], it follows that for fixed x E X, the operator Ta (zc, :) exhibits strong monotonicity with respect to (y. z):
(T& (z, u) T& (z. n²), v²) 2 plyy - 1/12 + +xll= I/I Vu, EEEE
(38)
Furthermore, under the assumption that the gradients of F and f are Lipschitz continuous, the operator (2,,;),) also Lipschitz continuous with respect (v, 2) for any fixed x X:
[[Ta(r, (T, u u')ll S max ((Tr + pTl. + akk, (pxtis 20x)) ||u u'll, Vu, u' E Y X
(39)
C.1
Auxiliary Lemmas
To establish the convergence properties of SiPBA(Algoritmm)) T.. we first introduce several auxiliary lemmas pertaining to the behavior of the iterative sequence. The following lemma demonstrates contraction property for the sequence ug := (gk,
Lemma C.1 Let {pk} and {ax} be sequences such that Pl. > O. Define o = minfokk H.. Sup- pose the step-size sequence { satisfies 0 < 3Bx < "LetpeL,+2or for each k. Let {(x y x²)}
be the sequence generated by SiPBA(Algorihmm 7. Then, the iterate w and t satisfy:
||u u (a )12 < (1 0x u1
(40)
Proof. The update rule for ++1 can be expressed in the compact form:
2 xrojyxy (u* BrT(x*, u²)).
Recall that u](x*) (Vt (a+*), ) (x+²)) is is the unique saddle point of the minimax problem mingey maXyEy (1 2). From the first-order optimality conditions, u²(x*) satisfies:
Ta(x* u=((")) + x
which implics
(x** Projyxy (ua(**) BaT up (z())))
Utilizing the non-expansiveness of the projection operator, the strongly monotonicity of T. in (38) and its Lipschitz continuity with respect to u in (39). we can apply standard results from the analysis of projected fixed-point iterations 24 Theorem 12.1.2]. If the step size 3k
(0, 2 min(ax: /1/ (I.p Px 20x)3), then:
|| (1 || < (1 + (Ir + P&LL + 20x) 28 minfax, mo)) )1*
min
Thus, when 0 < Br < (L. M. )2 it holds that
||u k- ( M|2 <
84 min pHlllu (1
The subsequent lemma is dedicated to establishing the Lipschitz continuity of (x).
26

---

Lemma C.2 Let {ps} and { be sequences such that Pk. > O. Define on minfok, Then, for any I, X, the corresponding saddle points (z) and ug (x') satisfy:
[x (x)) L + 2px Ls || - x|1.
(41)
5x
Proof. Because (z) minimax problem min maXyeY V'a (z, y, 2), and min maXyEY the (z', y, 2), respectively. Ac- cording to the first-order optimality conditions, these saddle points must satisfy:
and ug(2²) = (vt(z'), 2 (2')) are saddle points to the
0 (1 v1(x)) NVxx(uu(x)),
(42)
and
e Ta(x', un (z')) + (xxxx()((z))
Next, we analyze the Lipschitz continuity of Tk TT u) with respect to The first component difference is
- -Vydu(a', ui(x')) + + (,
- F, (²))) + v Uf + ph (V (V,J(',,2(()) vol(r,
And the second component difference is
V Vethal'', (=th('',_u(z'")) (z') - V V2Vx(z, P (V - (x,
Thus, we obtain
[T (z(x))) - T2 (x)))) & Lpl|2' - x11 2y - ze|l
(43)
Next, we use the fact that
Ta " Te(x', n (x')) Te(x, (x')))
and apply the strongly monotonicity of T' from (38) along with the monotonicity of the normal cone NY and (45). This leads to the following inequality:
(*)vt(a') (x))1 + oxll=(((')) (x))
s (Ta un (a')) Ta(x'
(2(a', "
14((')) (z))))
< [Z uf(('') (z', (x(xx)) -
By substituting the bound from min /
43 into the above inequality, we obtain
=x(x)) s Lella' Ill + 2p 1| - xl|.
This completes the proof.
Lemma C.3 Let {px} and } be sequences such that Pk+1 0 = Hi) Then, for any fixed x E X, we have
Pk 0, 2 ok+1 > 0. Define
2(px+1 pk)
3(0x ok+1)
(z) xx(2))l <
Mes
My.
(44)
σk
Proof. Because (x) = (x)(z), (x))) and ( ( (x), (x)) are saddle points to the minimax problem minzey max,ey ( y, ²), and minzey max,er th+ (I, y, 2), respectively.
According to the first-order optimality conditions, these saddle points satisfy:
0 E T2 ux( + NY
(45)
and
0 E Tet (2. - (x)) + Ny (1 (x)). Next, we expand the differences between the gradients of 1/a and th+ at (x):
Vy u + Vo (x))
= (pk+1 - Px) (z, vi (x)) + (ax+1 - (2)=
27

---

and
A444i (5, (z)) - vatu(z (2,2,,u4110 (x))(())
(pk+1 - Pa) vf ++, + (o++1 ox) (x) -
Thus, we have the following bound for the difference between the operators Ta and Tk+1:
1 (ar, u Th (z, u (x)))1 < 2(pk+1 PK)MWs + 3(0x ok+ M2
(46)
Now, using the fact that
(x, ( Th+1 (z, 2h 1z)) [2 + + Ny (4)+1()));
and combining this with the strongly monotonicity of Th from (38 the monotonicity of the normal cone Ny and (4). get
1 (1lb++1(x)
+zll (2) - (z))
$ (T, u (I)) - (1, u (2)) 2z) u (x))
- [T u (x)) Th (x, u (x)) | (z))l
By substituting the bound from 46) into this inequality, we obtain minfox, /1) | (z) u (x)] s 2(px+1 pa)MMs 3(0x ok+
This completes the proof.
Lemma C.4 Let {pk} and {ax} be sequences such that pke 0k O. Define ox minfok, p.. Then, for any x,x' x' X, we have
(ée(E')-Vénnll) Vob((')) - (x)(2)) S 1oo - -x|1,
(47)
(Io++pp (1, 1m)4)
where Tope
8k
Proof. From the expression for Vor(z) given in Theorem 2.1
we have the following:
[z) Vou(z')] V2 V u
< (= V F(
+ Ps (z, - VaS(e', vi
+ Pk (ef(2, -
$ (Lr + px
z'11 (17(()) -
(48)
+ =
-
- =x(')ll
$ (LF + +2p L )] - 2'1 2 ||
u (x')l)
(LF
+ 2pxL, σk)
|| - x'
where the final inequality follows from Lemma C.2
By synthesizing the results from Lemmas C.4 the following lemma characterizes the evolution of the squared norm of the tracking error, 1u u )x*)
Lemma C.5 Let {pE} and {aw} be sequences such that pk+1 2 Pk > 0, o 2 ob+1 > 0. Define Tx minfork u.. Suppose the step-size sequence {3x] satisfies 0 < 8x (LotpuL,-2or for
each k. Let {x* st 2 be the sequence generated by SiPBA (Algorithm)
7. Then, the following
inequality holds:
||12 1 (1 - -1lu* u/ (2+)))1
, 320xxlet aoxllu/ (x + + 3,0
1
2
(LF + 2)
11 - x212
o
(49)
2
8(pk-1 p2)2
18(0x
xktt) )2 oz
+ +(11 +
M2, +
M2
BLōk
oz
28

---

Proof. Using the Cauchy-Schwarz inequality for any > O, we obtain the following:
|| u u (x
<(1 + 6) (z( )12 + (1 + - / 1 ( 2 (12
(50)
<(1 + 6)]l2* h+1 (z((=*)1 2(1 + z 1 )1luū((
- (12
+ 2(1 + 1 111 - (((t~1))1
Next, take bound:
BRo in the above inequality. By applying Lemma C.I we obtain the following
(1 + uf I (1
_ BLox)llu* us (1
1
Using Lemma we can further bound the second term as follows:
2
(LF + 2px 1,) 1 - x0113
2(1 + I| (x++t) - u (>^>))² S 2(1 +
BLOK
o2
Next, applying Lemma C.3 with = x++ we obtain
2(1 3) 1 (1=t))= (2
2 8(ph-1 pk)2
18(0x ok+1)2
<2(1 +
M3, +
M2²
of
oz
Finally, combining the above three inequalities with 50 we arrive at the desired inequality.
Lemma C.6 Let {pk] and {ax} be sequences such that Pk+1 2 Pk > 0, oz 2 out1 > 0. Then, for any X, we have
M²
6x+1(x)- - dx(x)= S (oxx - ok+1)
+ 2 (p Pk) Ms.
(51)
2
Proof. We begin with the expression for Φx+1 1 (x) as follows:
(x+1(x))
min max (2,,10,,,3)) seY wEY
This leads to the inequality
(x)
min thet1 (I, 1 (I), zEY
S Sik+i (z, (x): 2x (x))
Vi+1 (x))
pk+ (f (x)) f(x, =x(x))
Oktl
2 1144 (x) 2z) okt1 (1
< Fl Vie (x)) px(f(x vi (z)) f(x, 2x
Ok 1 (x) - 21(2))12 -/ [ + ok 0k-Okt1 1 (x)
+ (pk - 1k+1) (f wh+1 - 122 =x()))
< max
(((z.)) v) - (x( 9) f(x, (x))) + Tk -2 |1 - =](x)]1-_ - Tk
2 [Tul]3
DEY
σh 0k+1
| (2=) + (pr - Pk+1) 1) (f - (xx))
2
< max vn (x, y, 2 (x)) ok Tk+1 M3 (px+1 pk) M,. yEY
2
This completes the proof, as the final inequality is derived from the fact that du(x))
max,ey v2 3,(2,,,2((r) (x)).
29

---

The subsequent lemma characterizes the descent property of the value function (x( across iterations.
Lemma C.7 Let {pk) and { be sequences such that pk+1 2 Pk O, ok oht1 > O. Define Th = min min(oks Suppose the step-size sequence {3k] satisfies 0 < 8N < [L, portp,,,-00 for
each Let ((a,,5 , 2 be the sequence generated by SiPBA (Algorithm)
1
Then, we have
(041(1 Φu (x*)++ +
( 1 Lide
| 1 x01
200k 2
My
$ 0k (Lp 2p L, ()) -1xb -u (1 + (ox -k++1)
+ 2 ( -PA) M,
2
2
(52)
where Lov = 11
Proof. We decompose the total difference as follows:
@x+1(x (x(²²) = Φx+1 1 (x*+1) ox 0x () + @x(xtt)) - =xx(x*)
(53)
For the first term, applying Lemma C.6 with x = xkt1;
M2
@ cx(x I (ox - 0k+1)
" + 2 (px+1 pka) Pk)Mr M,.
(54)
2
For the second term, on (x on (x*), use the Lav Lipschitz continuity of V (x) established
in Lemma C.4 A standard descent incquality (cf. [10] Lemma 5.7] for smooth functions) states:
Φu (x - (x*x S (Vol(="), x - x²) + Iodn || - 111
(55)
2
Next, applying the update rule for ktt we get
-
k+l
- x21 S (-Vaba , xktl xt)).
Olk
By combining this incquality with the previous one, and using the formula for VoL( given in obtain
Theorem
2.1
Φx(2 (x(xtt)) - (x(())++ + (1) Ludu
2 |1 101
ax
(V (x" V (zt)), ) (x()")) - V VeVa( y2tt1 2 , kt1 - x/)
((LF + pk , ( 111 || (1((*))l pxls | 11a - 2x (x((*))]] ||a - x*1l
(56)
0k (LF + 2pp Ly) ) )211u 1+1 1 (x + - 1| - 121
1
2
20rk
(I.r + 2px (1 TxBa)llu** u }|
||
2
20c
where the last incquality follows from Lemma C.I inequality with (55) and (54).
The conclusion follows by combining the above
Lemma C.8 Let { and {aw} be sequences such that Pk > 0, 0k > 0 and a - 0 as k + co. Furthermore, assume that sbxx) is bounded below on X, ie., inf ((x) -00. Then, there exists a constant such that.for any {a*} X, we have
Φy (x 26
Proof. According Lemma B.5 for any the following inequality holds:
(x(x*))
((**)
o IIv" (+*)
inf d(z)
0% 1/ (a 112
(57)
2
30

---

where y (a) = arg maX)))(a)) g).
Next, by Lemma B.4 we have that there exists My such that for all k,
"x*()")l| S My
Thus, we can bound the second term in the inequality:
Φx (a*** 2 inf (xx)
Tk M
=ex
2
Taking the limit as k + oo and using the fact that 0g - 0, we obtain
lim inf $x(x²) 2 inf Φ(x),
xex
and then the conclusion follows.
C.2 Proof for Proposition 4.1
Proof of Proposition 4.1 Given 8g = Bok - and d ookk the constant ratio Bu/oro can be
chosen sufficiently small
ensure that for all k 2 1, the following inequality holds:
Ōx (LF + PkLy + 20
Bx
Recall the merit function,
Vx ax (#x((=") - x) + bxllu* ux(="))1
Applying Lemmas C.7 and
specifically equations (52) and (49)
and using the facts that a&+1 S
ag and bx+1 & by. we obtain:
Va+1 - V&
- (z+t1) ②) -ax((bex=") ②) b bet1llu= ++ - w 1 1112 - by bll -1 21(
S as aa<(0++1(00) (xx41) - (x*))) + bull u (a |12 1|ue )1
Lize
||att|
1112 -1-1-x111
+ as an (LF + 22p ox (1
a 20k
M2
a (ok -k++1)
+ 2ax (pet1 Pkb) M,
2
1
baBkosllll
"1(a*))l
2bx
2
(Top + 2p 1.g
|1, - 11
B5ōK
ox
2 2 Brok
18(kK+1
pN)²
18(0x
0x41)2
2b2
MB,
MM
o
(58)
The parameters are set according to the schedules: ag = agk - 9, .xx Bok 2p-20- by k-t o = ook-* and Pk Puk". We have that
buBror B -2p-2-22--2--- 24-24-1
Since > 1+ 4p 2g, it follows for sufficiently large k that
ax(LF + 2pxLs)² < by BRōx
Therefore,
0k (LF + 2px 11P1111))1]11 u 2
1 b - )12
buBkōn u "x(
Furthermore, since as = k- 3 by = 1 σh ook- and = pok?, we find that there exists C such that
by (1 +
2 (Lr + 2p)
S Cha-ttapt44
ak
320k
oz
31

---

and
(Lp + 2px + + +
Lbu
< Ck2rt
σk
Given that ag = agk " large k:
4p+ + 4q and > t t+ 4- 29 > 2p+0 9, we conclude that for sufficiently
Lon
2b
(L + 2p²
2ork
ag
BROR
o%
4ack
Substituting this and the earlier bound into
58
we deduce that for large k;
V
V& S
as
|1
1
40ck
4
M²
ax (ok ok+1)
20k (pk+1 P&) M,
(59)
2
8(pk+1 pk)2 M2, + 18(0x: ox+1)2
26x (1 +
M13
BLōR
o
Next, we show that the sum of the positive terms on the right-hand side of (59 is bounded. Since ag k- < and 0g. = ouk we have
20
Σ ax (ox xk+l) S
Σ (ox xk+1) S on-
With Ok =k Pak and 2p + 9, there exits such that
ap (pk+1 Pk) S Ck 2p [(k + 1)p - kP) S Ck p-
SPCk
S pCC
P p-
k
which implies
Σ 2ak (pu+1 - PPk) My < 00. 1=1
Regarding the remaining terms, since Bu Bok - by = k- oz =ook Ph poke and 1 4p + 4g, there exists such that
2
(pk+1 - px)2
6b +
Ck- -4- (( 1)p 2292
BLσ
02
Ck ++g-++p+400 12
12
$ CK -44------
Thus, the sum
2
8(pk+1 ppa)3 M2, 00.
2b (1 +
BROK
R=1
Similarly, there exists C > 0 such that
2 18(0x - 0x+1)3
2b (1 +
< ++2
BLOK
ok
Since t -2p + 2g. the sum
18(0x -x+11)
2b (1
M co.
BROK
o2
This completes the proof.
32

---

C.3 Proof for Theorem 4.2
Proof of Theorem 4.2 The conditions 8 2 8p + 8q and 4p + 5q are chosen to satisfy the
requirements of Proposition 4.1 From Proposition 4.1 and noting that V& 2 0 for all k, we have the following summations:
2 b+1
121 +
by Bkōullu u/(("))13 < co.
Okk
Rewriting the first sum, have:
be -ug(t))11 < xo. OR | -x
(60)
Since the terms in these convergent series non-negative, it follows that for any K 0:
min Ogoc OckcK
I x012 - O(1KK), and ockcK bR.Bkōn (x* O(1/K).
min
The parameter schedules are Ork agk- 5, 3x = Bok 2p-9, ak kk --p 4p-54 on ook and = Pake. We have
ag a 2s and bx Bookk - Gp-
Under the conditions 8 < 1/2 and 6p + 7q < 1, we we deduce the convergence rates:
min =
| =0
D<kcK og
and
min 11ue - "x 011K/2 OckcK K
Furthermore, since by BaBLOn/CC (LF + 2pp 0(1/K and 7p - 7q < 1, the summability in
(60) implies
(LF + 2p (1(())))1 11a* (1))) 0. lim inf - 1/ak:
10000
From Theorem
we have
[Projx(=: - aA V Projx( aa,d a
< [V)n(**) - d:''
VV (x(" =1((("))) Varta S *
(Lr + 2px [., u (x()))
S (Ir + 2ps [. "
where the first inequality follows from the nonexpansiveness of the projection operator Projæ, and the last inequality follows from Lemma C.I Combining this with the previous equality yields:
Timinf
-
1
Projx og Voh((**)
k-000
O%
1
-lim inf
1|
Projx
as (r*) + Projx (2x -xd - -x++1|
- |Projx - ax (xx( Projx - aaddh)l + 1100 s(-11))
1
< inf
k-000
aq
< lim inf
(LF + L )ll - (z Ill - 1| - xbtll|
k-+00
lim inf max
x. 1/aok (Ir + 2px I., ,)|k u u1(03)113
k0000
0.
This completes the proof of stationarity.
33

---

C.4 Proof for Corollary 4.3
We first establish the following auxiliary result.
Lemma C.9 Assume <(x) is lower semi-continuous on X. Let {pu} and { be sequences such that Pi= + oc and σ% O. Then, for any O, there exists K > 0 such that for all k Z K,
(x( - ((x)) + e,
Vx E
(61)
Proof. Assume, for the sake of contradiction, that the statement is false. Then there exists eg and sequence { C X such that
lim ou (2x)) > ((xx) c0- k
Since X is compact, by passing to a further subsequence if necessary. can assume Ik + E X. Recall that (v((()) =f())) is the saddle point of the minimax problem mingey maXyey (1 Thus, (x())) (n ((xx)) and by the definition of L/k, we have
(T), [a (xx)) + Th [1 ox(U)(())) = (mx))
2
20(Tx) +E.
(62)
By Lemma B.2 the sequence {yE(2x) } is bounded. Thus, by passing to another subsequence if necessary, we can assume y (zx) - for some y E Y. It follows from Lemma B.3 that y E S(z).
Since (11) is a minimizer of sb (ER, 8 (#x), 2) over E Y, we have thx 97 (Ix)), 2 (zx)) S (n( (xx)) (*x))
Substituting the definition of the this yields:
f z [=+a)=))1 (v (((x)) S pa (I oh
2 |lvt(<>))
This simplifies to:
Øk [z (xx)) 5o.
Pk (f(2, flz vixx)))
Combining this with 62 we have
F( Vil (xx)) 2 ((xx) +c. Taking the limit as & + co, continuity of F(x, y) and lower semicontinuity of d(x) yield
F(2. 7) 2 (T)) +
However, since ÿ E S(r), we must have
( > F(F, 8),
leading to a contradiction. Thus, the claim follows.
Proof of Corollary 4.3 From Theorem 4.2 we have the stationarity condition:
1
lim inf
||a.*
Projx a Vor = 0.
10000
Ork
Thus, we can find a subsequence {æ*s) such that lim ||a - Projx akk Vol, This condition, together with the Lipschitz continuity of VΦ established Lemma C.4 implies that x an approximate stationary point for on,, Standard arguments then show that for any > there exists Ko > 0 such that for all k3 2 Ku. there is d, > 0 such that
(a+s)) V =
0ky (I) Øu (x**)=
E||æ * 1l.
Vx 1s,, (x** n.
According to Lemma
B.5 for each ki:
duy (x*)) 2 ((xt)))-
Tke 11 (a+)))
(63)
34

---

where y (x) = arg yES())(()) v). By Lemma B.4 there exists My such that for any ky,
lyy (2 )| S My
Since 0k, +0 as kj + oc, we can obtain from 633 that for any ē >> O, there exists Ko such that for each K3 2 K,
Øk (a ) 2 o(xx))))))
Furthermore, by Lemma C.9 for any > there exists Ko > such that for any k z Ko-
Φ2, (2) S x(x)) 2'
Vor X.
Combining these inequalities yields that for any 6 and > find Kn such that for each k, 2 Ko, there exists ò3 > such that
<(x) 2 p
e||x x²1 11-
Ya Bs,, (x') nx.
Since for > Ko, we can find some ky > K, the proof is completed.
35

---

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

---

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

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We will uploade the code to the supplemental material and provide detailed instructions on how run the code ensure the reproducibility of the experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//ipss.ccppblli... wwcppbblccgguuieeeeo http:/gddess/eee/ htt////ooSSumiiseeeeeeeeee stibbbmmmssoooooooocc. for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: All experimental settings, including dataset descriptions, data splitting methods, hyperparameter choices, and the implementation of algorithms, clearly explained in Section 5 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper reports error bars using standard statistical metries. All experimental results are based on multiple repetitions of the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
38

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We wrote this in the beginning of Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
We have read the code of ethics carefully and done our best to conform.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses on theoretical and algorithmic problem machine learning and is not like to a significant impact society.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
39

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our experiments only used small classification models, without the risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have cited the relevant papers providing the algorithms, code and dataset used in this paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
40

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
There are no new assets for this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not contain any studies involving human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper does not contain any studies involving human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
41

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The core research of this paper is not related to LLM.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
42


Reviews:
[{"review_id": "UwfxNUUsDS", "reviewer": "Reviewer_ckLr", "summary": "This work focuses on addressing the relatively underexplored area of Pessimistic Bilevel Optimization (PBO) by proposing a single-loop, fully first-order algorithm. Specifically, it introduces a smooth approximation to the PBO problem through penalization and regularization, and builds on this to develop SiPBA, a gradient-based method that avoids second-order derivatives and inner-loop optimization. Theoretical analysis is provided to justify the approximation and prove the convergence of SiPBA.", "questions": "My questions are based on the weakness:\n\nIn the recent literature on Optimistic Bilevel Optimization, it has been shown that the lower-level optimization problem can be viewed as a soft constraint to the upper-level. In this work, since some approximation and smoothing techniques are adopted, does the lower-level optimization problem in Pessimistic Bilevel Optimization also act as a soft constraint to the upper-level problem?\n\nAlthough the proposed framework is claimed to be single-loop, each iteration involves multiple gradient projection steps. Given that the projection in this work is applied to the main variables (which are often non-convex and complex), does this still qualify the framework as fully single-loop in practice? Could the authors provide more discussion or clarification on this point?\n\nAssumption 3 appears to be uncommon in the context of bilevel optimization. Could the authors elaborate on the motivation and practicality of this assumption? In particular, are there empirical results or real-world scenarios that support its validity?\n\nHow does the proposed method compare with existing bilevel optimization methods in terms of non-asymptotic convergence rates? Can the authors provide a theoretical or empirical comparison?\n\nThe experimental validation appears limited, and the practical applications of Pessimistic Bilevel Optimization in machine learning are not well demonstrated. Could the authors include more experiments on additional tasks or provide further discussion on the potential applications of PBO in the introduction?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. The studied problem is interesting.\n\n2. The presentation in this work is good.\n\nWeaknesses:\n\n1. The recent work on Optimistic Bilevel Optimization has shown that the lower-level optimization problem is a soft constraint to the upper-level ones. Whether the lower-level optimization problem is also a soft constraint in Pessimistic Bilevel Optimization? Since some approximation and smoothing tricks are used in this manuscript, and the soft constraint means that this constraint can be violated to some extent without resulting in a meaningless solution.\n\n2. Although the framework proposed in this work is single-loop. Each step in this framework is computationally complex since multiple gradient projection steps are used. I understand that the gradient projection step is efficient if the feasible region set is simple, for instance, the feasible region for some dual variables. However, the projection set in this algorithm is for the main variables, which are usually complex and non-convex. Operating the projection in each iteration needs to solve a non-convex optimization problem. Thus, more discussions on whether the proposed method is fully single-loop need to be added.\n\n3. The Assumption 3 is not a widely-used assumption in bilevel optimization, can you provide more discussions on this assumption? Additionally, whether the assumption is practical? Can you provide more results, e.g., experimental results, to support this assumption?\n\n4. Can you compare the non-asymptotic convergence rates of the proposed method with the existing bilevel optimization methods? \n\n5. The experimental results are limited. It seems that PBO has limited applications in machine learning. Can you provide more experimental results on additional application? More discussions on the applications of PBO in the introduction can also improve this manuscript. The reviewer will appreciate this work not only for its theoretical analysis of the optimization problem, but also for the practical relevance of the studied problem, which has broad applications in machine learning (since NeurIPS is a ML conference).", "was_revised": true, "final_justification": "My concerns have been addressed. I’ve increased the confidence from 3 to 4.", "rebuttal": "We thank the reviewer for their insightful comments and constructive suggestions. We are grateful for their acknowledgment of our work's primary contributions: proposing a gradient-based method for Pessimistic Bilevel Optimization (PBO) that avoids second-order derivatives and the need for an inner-loop optimization solver. We believe this is a valuable contribution to a relatively underexplored area.\n\nBelow, we address the specific concerns raised.\n\n---\n\n### 1. On the Lower-Level Problem as a Soft Constraint\n\nRegarding the question of whether the lower-level optimization acts as a soft constraint, the reviewer's intuition is correct. This result is established in Theorem 3.6 of [1]. The theorem shows that if the lower-level problem constraint is relaxed to $f(x,y) \\le \\inf_y f(x,y) + \\epsilon$, the solution to this relaxed problem converges to the solution of the original PBO as the violation $\\epsilon \\rightarrow 0$. We will add this interpretation in the revised manuscript.\n\n---\n\n### 2. On the \"Single-Loop\" Nature of the Algorithm\n\nWe appreciate the opportunity to clarify our \"single-loop\" claim. Our use of this term emphasizes that our algorithm does not require an inner loop to iteratively solve the minimax problem in Eq. (4) to approximate the gradient of $\\phi_{\\rho,\\sigma}$ at each iteration. We agree that this advantage relies on the assumption that the projections onto the feasible sets $X$ and $Y$ are computationally simple (i.e., have a closed-form solution or can be computed efficiently). We will add a statement to the manuscript to explicitly clarify this condition for the single-loop claim.\n\n---\n\n### 3. On the Justification for Assumption 3\n\nWe agree that Assumption 3 is not a commonly used assumption in bilevel optimization. In fact, Assumption 3 is equivalent to the closedness of the function’s epigraph, and it is a common assumption for ensuring the existence of a function's minimum (see, e.g., Theorem 1.9 of [2]).\n\nWe recognize that verifying Assumption 3 directly can be challenging. For this reason, we provide a more practical sufficient condition immediately following the assumption: the inner semi-continuity of the lower-level solution map $\\mathcal{S}(x)$. This condition holds for all problem instances considered in our numerical experiments under mild assumptions, thereby satisfying Assumption 3. We will expand this discussion in the revised manuscript to make the motivation and verification of this assumption clearer.\n\n---\n\n### 4. On the Comparison of Non-Asymptotic Convergence Rates\n\nWe thank the reviewer for raising this important point. To the best of our knowledge, AdaProx [3] is the only other algorithm for PBO with a non-asymptotic convergence rate analysis. However, a direct theoretical comparison of our rate with that of AdaProx is not straightforward for several fundamental reasons:\n\n* Different Assumptions: AdaProx requires additional assumptions, including Lipschitz continuity of the Hessians for both objective functions and the strict positive definiteness of the lower-level Hessian, none of which are required by our method.\n* Different Methodology and Metric: AdaProx reformulates the PBO problem using a relaxed KKT system, which leads to a different stationary metric for measuring convergence.\n\nGiven these differences, a direct comparison of the theoretical convergence rates would not be meaningful.\n\nTo provide a comprehensive  numerical comparison, we have expanded our numerical evaluation on the synthetic example from Section 5.1 to include AdaProx-SG and the Compact/Detailed Scholtes (Scholtes-C/D) relaxation methods [4]. We ran SiPBA, AdaProx-PD, We report the minimum and maximum relative errors of the outputs, the number of valid runs (achieving $\\epsilon_{\\text{rel}} < 10^{-4}$), and the average runtime (to reach $\\epsilon_{\\text{rel}} < 10^{-4}$)  of those valid runs. The results over10 times from random initial points, summarized in the table below, demonstrate that SiPBA is not only significantly faster but also more robust, consistently converging to a valid solution.\n\n**Table**: Performance comparison of SiPBA, AdaProx variants, and Scholtes relaxations on synthetic experiment ($n=100$). \n|                               | SiPBA               | AdaProx-PD          | AdaProx-SG          | Scholtes-C          | Scholtes-D          |\n| :---------------------------- | :------------------ | :------------------ | :------------------ | :------------------ | :------------------ |\n| Min. $(\\epsilon_{\\text{rel}})$ | $1.22 \\times 10^{-6}$ | $1.79 \\times 10^{-7}$ | $3.80 \\times 10^{-6}$ | $1.12 \\times 10^{-5}$ | $9.60 \\times 10^{-5}$ |\n| Max. $(\\epsilon_{\\text{rel}})$ | $1.45 \\times 10^{-6}$ | $1.53 \\times 10^{-5}$ | $1.02 \\times 10^{-4}$ | $0.10$              | $1.06$              |\n| Valid Runs                    | 10/10               | 10/10               | 9/10                | 1/10                | 1/10                |\n| Ave. Time (s)                 | 1.03                | 87.44               | 4.07                | 23.12               | 23.81               |\n\n\n\n---\n\n### 5. On Experimental Scope and Practical Applications\n\nWe appreciate the feedback regarding the experimental results and the practical applications of PBO. A key motivation for our work is to provide an efficient and accessible algorithm for PBO, thereby encouraging its adoption in a wider range of machine learning applications.\n\nTo further demonstrate the practical utility of SiPBA, we have added a new experiment on deep hyper-representation using real-world datasets. The problem is formulated as:\n\n$$\n\\min_{\\theta\\in\\Theta}\\max_{w}\\frac{1}{m_1}\\|\\|f(X_{val},\\theta)w-\\mathbf{y}_{val}\\|\\|^2,\n$$\n\n$$\n\\text{s.t.} w\\in\\underset{w^\\prime\\in\\mathcal{W}}{\\arg\\min} \\frac{1}{m_2}\\|\\|f(X_{train},\\theta)w^\\prime-\\mathbf{y}_{train}\\|\\|^2,\n$$\n\nwhere $f(\\cdot, \\theta)$ represents a neural network parameterized by $\\theta$, and $w$ corresponds to a linear layer. We adopt the LeNet-5 architecture [5] as the feature extractor $f(\\cdot, \\theta)$ and evaluate performance on the MNIST and FashionMNIST datasets. Each dataset is randomly split into 50,000 training samples, 10,000 validation samples, and 10,000 test samples, with performance evaluated based on test accuracy. The accuracy on test data are reported below:\n\n**Table**:Test accuracy (%) on MNIST and Fashion MNIST. \n| Dataset       | SiPBA          | PZOBO | AID-FP | AID-CG |\n| :------------ | :------------- | :---- | :----- | :----- |\n| MNIST         | **99.1** | 95.8  | 97.6   | 92.5   |\n| Fashion-MNIST | **89.6** | 78.8  | 82.1   | 78.8   |\n\n\nThese results indicate that the PBO model optimized by SiPBA exhibits superior generalization performance, further demonstrating the promise of PBO in machine learning applications.\n\nActually, a growing body of work has explored the potential of PBO in various machine learning applications recently. We will add a discussion to the revised manuscript. \nSpecifically, adversarial learning has been formulated as a PBO problem [6,7], and decision-focused learning in contextual optimization has been addressed within the PBO framework [8,9]. The use of PBO for hyperparameter optimization has also been investigated [10]. Outside the machine learning domain, PBO has found applications in many practical scenarios, including but not limited to demand response management [11], rank pricing and second-best toll pricing [12,13], production-distribution planning [14], and gene knockout model in biological systems [15].\n\n---\n\n### References\n\n[1] L. Lampariello, S. Sagratella and O. Stein. The standard pessimistic bilevel problem. *SIAM Journal on Optimization*, 2019.\n\n[2] R. T. Rockafellar, and R. J. Wets. Variational analysis. *Springer Berlin Heidelberg*,1998.\n\n[3] Z. Guan, D. Sow, S. Lin, and Y. Liang. AdaProx: A novel method for bilevel optimization under pessimistic framework. *Conference on Parsimony and Learning*, 2025.\n\n[4] I. Benchouk, L. O. Jolaoso, K. Nachi, and A. B. Zemkoho. Scholtes relaxation method for pessimistic bilevel optimization. *Set-Valued and Variational Analysis*, 2025.\n\n[5] D. Sow, K. Ji, and Y. Liang. On the convergence theory for hessian-free bilevel algorithms. *Advances in Neural Information Processing Systems*, 2022.\n\n[6] M. Brückner and T. Scheffer. Stackelberg games for adversarial prediction problems. *International Conference on Knowledge Discovery and Data Mining*, 2011.\n\n[7] D. Benfield, S. Coniglio, M. Kunc, P. T. Vuong and A. B. Zemkoho. Classification under strategic adversary manipulation using pessimistic bilevel optimisation. In *arXiv:2410.20284*, 2024.\n\n[8] V. Bucarey, S. Calderón, G. Muñoz, and F. Semet. Decision-focused predictions via pessimistic bilevel optimization: A computational study. *Integration of Constraint Programming, Artificial Intelligence, and Operations Research*, 2024.\n\n[9] D. Jiménez, B. K. Pagnoncelli and H. Yaman. Pessimistic bilevel optimization approach for decision-focused learning. In *arXiv:2501.16826*, 2025.\n\n[10] M. A. Ustun, L. Xu, B. Zeng, and X. Qian. Hyperparameter Tuning Through Pessimistic Bilevel Optimization. In *arXiv:2412.03666*, 2024.\n\n[11] T. Kis, A. Kovács, and C. Mészáros. On optimistic and pessimistic bilevel optimization models for demand response management. *Energies*, 2021.\n\n[12] H.I. Calvete, C Galé, A Hernández and J. A. Iranzo. A novel approach to pessimistic bilevel problems. An application to the rank pricing problem with ties. In *Optimization*, 2024.\n\n[13] X. Ban, S. Lu, M.Ferris and H. X. Liu. Risk averse second best toll pricing. In *Transportation and Traffic Theory 2009: Golden Jubilee*, 2009.\n\n[14] Y. Zheng, G. Zhang, J. Han and J. Lu. Pessimistic bilevel optimization model for risk-averse production-distribution planning. In *Information Sciences*, 2016.\n\n[15] B. Zeng. A practical scheme to compute the pessimistic bilevel optimization problem. *INFORMS Journal on Computing*, 2020."}, {"review_id": "yjTmECMd77", "reviewer": "Reviewer_iXKX", "summary": "The paper addresses pessimistic bilevel optimization and introduces a single-loop algorithm based on a smooth approximation of a reformulated value function. The authors establish asymptotic convergence with respect to the smoothing parameter in the approximation and also provide a non-asymptotic convergence rate.", "questions": "1. What is the intuition behind this smoothing approach, which incorporates both a quadratic term and a bilinear term? Does this technique have precedent in the literature? What would happen if we only add $\\sigma ||z||^2$ in the smoothing? Can the non-asymptotic results in Section 4 still hold? It seems in [28], they only used something similar to $\\sigma ||z||^2$ for smoothing.\n\n2. How do the results compare to those in reference [28]? Can authors add a remark under Theorem 4.2 on the choice of $s, p, q$ so that $||x^{k+1} - x^k||^2 / \\alpha_k^2$ and $||u^k - u_k^* (x^k)||^2$ converge in the same order of rate?\n\n3. The convergence notion in Theorem 4.2 is tied to the reformulation in (2) and smoothing approximation. Does this convergence imply $F(x^k , y^k)$ is close to $\\min_{y \\in S(x^k)} F(x^k , y)$? Are there other commonly used notions of convergence, and what is the relationship between these notions?", "limitations": "N.A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The algorithm is single-loop and gradient-based, which is easy to implement. \n\n2. The idea of smoothing seems effective here. \n\nWeaknesses: \n\n1. The upper-level function $F(x, y)$ is also assume to be strongly convex in $y$. This assumption is usually not needed in (optimistic) bilevel optimization. I think the main reason for this assumption is that the unique $y_{\\rho, \\sigma}^* (x), z_{\\rho, \\sigma}^* (x)$ is needed in gradient of value function $ \\phi_{\\rho, \\sigma}^* (x)$. Is there any way to remove this assumption?\n\n2. The penalty method and the associated first-order updates are not particularly novel. However, the smoothing technique introduced here appears to be new.", "was_revised": true, "final_justification": "I would like to maintain the current rating. Authors should include additional remarks on Theorem 4.2 in the revised version.", "rebuttal": "We thank the reviewer for their insightful feedback. We are grateful for their acknowledgment of our work's primary contribution: proposing a single-loop gradient-based method for Pessimistic Bilevel Optimization (PBO). We believe this is a valuable contribution to a relatively underexplored area.\n\n---\n\n### 1. On the Strong Concavity Assumption\n\nThe reviewer is correct that the strong concavity assumption on the upper-level objective $F(x,y)$ is primarily used to ensure the uniqueness of the saddle point and the differentiability of the smoothed value function $\\phi_{\\rho,\\sigma}(x)$. Without this, $\\phi_{\\rho,\\sigma}(x)$ may become non-differentiable.\n\nOne way to weaken this assumption to mere concavity in $y$ would be to add a regularization term, such as $-\\delta_k \\|\\|y\\|\\|^2$ with vanishing $\\delta_k$. We opted for the strong concavity assumption to maintain clarity and focus. Our goal was to present the core ideas of our new smoothing approximation and single-loop algorithm as clearly as possible. Introducing an additional hyperparameter would complicate the theoretical analysis and could obscure the central contributions of this work. We therefore made a deliberate choice to prioritize clarity in this paper, leaving the exploration of this relaxation for future work.\n\n---\n\n### 2. On the Novelty of the Proposed Method\n\nWe appreciate  the reviewer for the recognition of the novelty of our smoothing strategy. While we agree that penalty methods and first-order updates are established techniques in optimization, we wish to clarify that their synthesis and application to create a single-loop, gradient-based method for PBO are novel.\n\nSpecifically, these techniques are not merely combined, but are strategically integrated. The penalty strategy is a key component within our smoothing approximation framework, and the first-order updates are subsequently enabled by this new smoothing. It is this complete, integrated methodology that constitutes the main contribution and allows for an efficient single-loop PBO algorithm.\n\n---\n\n### 3. On the Intuition Behind the Smoothing Approach\n\nWe thank the reviewer for this valuable question. The reviewer correctly notes that adding a quadratic term to ensure strong convexity/concavity is a common technique. Our key innovation, however, lies in the introduction of an additional bilinear term. To our knowledge, no prior work has incorporated both a quadratic and a bilinear term for smoothing a bilevel optimization problem.\n\nThis bilinear term is not arbitrary; it is theoretically essential for the convergence of our smoothing approximation. As noted in the manuscript, without this coupling term, we cannot establish the key inequality in the proof of Lemma 2.2:\n\n$$\n\\rho_{k}(f(\\bar{x}, z_{k}^{\\star}(\\bar{x})) - f(\\bar{x}, y_{k}^{\\star}(\\bar{x}))) + \\frac{\\sigma_k}{2} \\|\\| z_{k}^{\\star}(\\bar{x}) - y_{k}^{\\star}(\\bar{x})\\|\\|^2 \\le 0.\n$$\n\nThis result forms the foundation of our subsequent convergence analysis, underpinning both Proposition 2.3 and Theorem 2.5.\n\nThe work in [28] considers a different setting and relies on an additional assumption on the lower-level Hessian (there exists a constant $\\kappa > 0$ such that $\\lambda_{\\min}(\\nabla^2_{yy} f(x,y)) > \\kappa$ for all $\\nabla_y g(x,y) \\neq 0$), which our method does not require. This additional condition is what permits their use of a simpler smoothing term. Our approach, by design, is more general; the inclusion of the bilinear term is the critical element.\n\n---\n\n### 4. On the Comparison with [28] and Discussion on Convergence Rates\n\nWe appreciate  the reviewer for this question. Our work differs from [28] in several aspects:\n\n* Assumptions: [28] requires stricter assumptions, including Lipschitz continuous Hessians and a strictly positive definite lower-level Hessian, none of which are needed for our method.\n\n* Methodology and Metric: AdaProx [28] follows a different path by reformulating the PBO problem via KKT conditions of the maximum subproblem, leading to a constrained single-level problem that is structurally distinct from our smoothing-based formulation. Consequently, their stationarity metric is different from ours, and their method relies on second-order information.\n\nGiven these significant differences in assumptions and formulation, a direct theoretical comparison of the convergence rates would not be meaningful.\n\nFor the question regarding the convergence rates of terms $\\|\\|x^{k+1} - x^k\\|\\|^2/\\alpha_k^k$ and $\\|\\|u^k - u_{k}^{\\star}(x^k)\\|\\|^2$ stated in Theorem 4.2, as it requires that $8p + 8q \\le s $. \nTherefore, the convergence rate of the term $\\|\\|x^{k+1} - x^k\\|\\|^2/\\alpha_k^2$ is at most $\\mathcal{O}(1/K^{1-16p-16q})$. This is strictly slower than the $\\mathcal{O}(1/K^{1-6p-7q})$ rate of the term $\\|\\| u^k -u^{\\star}_k(x^k)\\|\\|^2$. We will add this clarification to the revised manuscript.\n\n---\n\n### 5. On the Convergence Notion in Theorem 4.2\n\nThe reviewer's understanding is correct. We can indeed show from Theorem 4.2 that $y_k$ will eventually be close to the solution of $\\max_{y \\in \\mathcal{S}(x_k)} F(x_k,y)$, and therefore $F(x^k,y^k) - \\max_{y \\in \\mathcal{S}(x_k)} F(x_k,y)) \\rightarrow 0$. More rigorously, under the assumptions of Theorem 4.2, we can establish that\n\n$$\n\\lim_{k \\to \\infty} y_k^{\\star}(x_k) = y^*(\\bar{x}),\n$$\n\nwhere $y^*(\\bar{x})=\\underset{y\\in \\mathcal{S}(\\bar{x})}{\\arg\\max} F(\\bar{x},y)$. We will add this result to the revised manuscript.\n\nRegarding other convergence notions, the choice of a stationarity metric is tied to the specific reformulation an algorithm is based on. As the reviewer correctly notes, our metric is based on the reformulation in (2) and its smooth approximation in (6), whereas the metric for AdaProx [28] is based on a constrained single-level reformulation with KKT conditions of the max subproblem. Establishing a formal relationship between these distinct metrics is a non-trivial direction for future research, as it would likely require additional assumptions to bridge stationarity conditions of different problem formulations."}, {"review_id": "jOpMPLrUZn", "reviewer": "Reviewer_5FpQ", "summary": "This paper presents a numerical method for solving pessimistic bilevel optimization (PBO) problems, a class of bilevel optimization that has received less attention in the literature compared to its optimistic counterpart. The authors introduce a novel smoothing technique for the PBO value function, leveraging penalization and regularization. This approach transforms the value function into a smooth function corresponding to a strongly convex-strongly concave minimax problem.\n\nBuilding upon this smoothed formulation, the authors propose a fully first-order, single-loop algorithm for solving PBO.  The paper provides a rigorous theoretical convergence analysis of the proposed algorithm. Furthermore, the effectiveness and efficiency of the method are validated through a series of numerical experiments on both synthetic and real-world problems.", "questions": "1. On page 3, in lines 119 and 122, the word \"and\" appears to be duplicated. Please correct this for clarity.\n\n2. Regarding the regularized function defined in Equation (3), could the authors elaborate on the motivation for including the coupling term $\\langle y, z\\rangle $? What is the specific role of this term? The reviewer understands the need to ensure the function is strongly convex with respect to $z$. Would the quadratic regularization term alone be insufficient to achieve this, or does the coupling term serve an additional, distinct purpose in the analysis or performance of the method?\n\n3. Could the authors precisely define the \"SVM\" and \"Logistic\" models listed in Table 2 and explain how they relate to the PBO model formulated in Equation (16)? The basis for comparison in this experiment is unclear. Please specify which algorithms are being compared. Was the proposed method benchmarked against other PBO algorithms, or does the comparison involve other methodologies?", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths :\n1. This paper addresses PBO, a challenging and less-explored area of bilevel optimization. The inherent difficulty of PBO, which includes a maximization problem at the upper level, has limited the development of efficient algorithms. This work makes a valuable contribution by focusing on single-loop, first-order methods for this problem class.\n\n2. The proposed methodology is both clear and sound. The authors introduce a novel technique to construct a smooth approximation of the PBO problem using penalization and regularization. The paper provides a detailed analysis to justify the convergence of this approximation to the true PBO problem, a contribution that may inspire further research in this domain.\n\n3. Based on the smoothed approximation, the paper presents a single-loop algorithm that relies solely on first-order information. This design choice makes the proposed algorithm simple to implement and computationally efficient, rendering it suitable for large-scale applications.\n\n4. The authors provide a non-asymptotic convergence analysis for the proposed algorithm. This rigorous theoretical support substantiates the algorithm's validity and strengthens the paper's overall contribution.\n\n5. The numerical experiments demonstrate the practical effectiveness and efficiency of the proposed algorithm.\n\nWeaknesses:\nThe primary area for improvement lies in the numerical experiments. Several descriptions of the experimental setup and results lack clarity. Furthermore, the empirical evaluation is somewhat limited due to the small number of baseline algorithms used for comparison. Although the literature on PBO algorithms is not extensive, several existing methods could have been included, at least in the experiments on synthetic data. A more comprehensive comparison would provide a stronger case for the advantages of the proposed approach.", "was_revised": true, "final_justification": "I have read all rebuttals, and keep my score.", "rebuttal": "We sincerely thank the reviewer for their insightful comments and constructive suggestions. We are grateful for their acknowledgment of our work's primary contributions: proposing a gradient-based method for Pessimistic Bilevel Optimization (PBO) that avoids second-order derivatives and the need for an inner-loop optimization solver.  \nBelow, we address the specific concerns raised.\n\n---\n\n###  1. On the Weaknesses of Numerical Experiment\n\nWe thank the reviewer for this feedback. We have revised the experimental section to improve clarity, particularly the spam classification setup, which we detail in our response to Question 3.\n\nWe agree that including more baseline comparisons is valuable. Accordingly, we have expanded our synthetic experiments to include additional methods. As detailed in our response to Reviewer ckLr, these new results further highlight the effectiveness of our proposed method, SiPBA. We will incorporate these results into the revised manuscript.\n\n---\n\n###  2. On the Typo on Page 3\n\nWe appreciate the reviewer for the attention to detail. This typo has been corrected in the revised manuscript.\n\n---\n\n###  3. On the Additional Bilinear Term in the Smoothing Approach\n\nWe appreciate this insightful question. The bilinear term is indeed crucial for the theoretical guarantees of our proposed method.\n\nWhile adding a quadratic term to ensure strong convexity is a common technique in optimization, its specific form in our work is not arbitrary. Its inclusion is theoretically motivated and essential for the convergence of our smoothing approximation. As noted in the manuscript, this coupling term is critical for establishing the key inequality in the proof of Lemma 2.2:\n\n$$\n\\rho_{k}(f(\\bar{x}, z_{k}^{\\star}(\\bar{x})) - f(\\bar{x}, y_{k}^{\\star}(\\bar{x}))) + \\frac{\\sigma_k}{2} \\|\\| z_{k}^{\\star}(\\bar{x}) - y_{k}^{\\star}(\\bar{x})\\|\\|^2 \\le 0.\n$$\n\nThis result forms the foundation of our subsequent convergence analysis, underpinning both Proposition 2.3 and Theorem 2.5.\n\n---\n\n### 4. On the \"SVM\" and \"Logistic\" Models in Table 2\n\nWe apologize for the lack of clarity and thank the reviewer for the opportunity to elaborate on our experimental design for the spam classification task. The original experiments were designed to compare the performance of the PBO model trained using SiPBA with standard single-level models implemented in `scikit-learn`. For clarity, we restate the PBO formulation considered in the spam classification task:\n\n$$\n\\min_{w\\in\\mathbb{R}^n} \\max_{\\hat{x}}l(w,\\hat{x},y) + \\lambda_1 \\mathrm{Reg}(w)\n\\quad \\text{s.t.}\n\\hat{x} \\in \\arg\\min_{x'\\in\\mathcal{X}} l'(w,x') + \\lambda_2 \\|\\|\\varphi(x') - \\varphi(x)\\|\\|^2,\n$$\n\nwhere $ w $ denotes the classifier parameters, $ (x,y) $ represents the vectorized training data, $ l $ (resp. $ l' $) corresponds to the classifier (resp. adversarial generator) loss, $ \\mathrm{Reg}(\\cdot) $ denotes the regularization term, and $ \\varphi(\\cdot) $ characterizes the feature mapping.\n\nWe perform a two-part empirical comparison:\n\n- PBO solvers: We compare the PBO model above trained using SiPBA (with $\\varphi(\\mathbf{x}) $ as the top $ k $ principal components) to the same model trained using the SQP-based method with $ \\varphi(\\mathbf{x}) = \\mathbf{x} $, as the setting in [2].\n- Single-level baselines: We also compare the SiPBA-trained PBO model against a standard single-level model:\n\n$$\n\\min_{w} l(w,x,y) + \\lambda_1 \\mathrm{Reg}(w),\n$$\nimplemented using the `scikit-learn` library.\n\nFor both $ l $ and $ l' $, we consider hinge loss and cross-entropy loss, leading to the following method names:\n\n- SiPBA-Hinge / SiPBA-CE: Our proposed PBO solver using SiPBA.  \n- SQP-Hinge / SQP-CE: SQP-based method from [3].  \n- Single-Hinge / Single-CE: Standard single-level classifiers corresponding to SVM and Logistic Regression.\n\nThe results over ten runs are summarized in the table below, which indicate that the PBO model (either trained with SQP or SiPBA) exhibits superior cross-domain performance compared to the single-level models. Moreover, the SiPBA-trained models achieve the best overall accuracy and F1 score.\n\n> **Table**: Accuracy (Acc) and F1 score (F1) on four spam corpora, training on TREC06, TREC07, EnronSpam or LingSpam.\n\n| Train Set | Model         | TREC06       | TREC07       | EnronSpam   | LingSpam    | Ave          |\n|-----------|---------------|--------------|--------------|-------------|-------------|--------------|\n| TREC06    | SiPBA-Hinge   | 96.4/94.7    | 87.3/81.0    | 70.6/70.2   | 87.6/92.7   | **85.5/84.7** |\n|           | SiPBA-CE      | 94.5/92.5    | 79.5/73.0    | 70.9/71.8   | 87.6/92.8   | **83.1/82.5** |\n|           | SQP-Hinge     | 93.1/90.0    | 89.2/83.2    | 69.0/66.7   | 89.0/93.4   | 85.1/83.3     |\n|           | SQP-CE        | 93.6/91.3    | 78.9/72.4    | 70.7/71.4   | 87.2/92.6   | 82.6/81.9     |\n|           | Single-Hinge  | 95.4/93.1    | 89.3/82.8    | 63.9/46.5   | 75.5/82.5   | 81.0/76.2     |\n|           | Single-CE     | 93.8/90.4    | 88.5/79.6    | 56.9/24.1   | 55.1/62.6   | 73.6/64.2     |\n| TREC07    | SiPBA-Hinge   | 68.9/16.8    | 93.7/89.7    | 57.0/33.7   | 50.5/57.6   | **67.5/49.5** |\n|           | SiPBA-CE      | 71.7/56.9    | 98.1/97.2    | 68.3/68.8   | 64.6/75.5   | **75.7/74.6** |\n|           | SQP-Hinge     | 68.9/17.2    | 95.3/92.5    | 55.0/21.0   | 29.9/28.1   | 62.3/39.7     |\n|           | SQP-CE        | 71.3/56.9    | 97.7/96.6    | 68.4/69.7   | 70.1/80.5   | 76.9/75.9     |\n|           | Single-Hinge  | 65.4/1.9     | 97.7/96.4    | 50.9/0.2    | 16.6/0.3    | 57.7/24.7     |\n|           | Single-CE     | 66.4/3.4     | 95.7/93.0    | 51.0/0.8    | 17.3/1.8    | 57.6/24.8     |\n| EnronSpam | SiPBA-Hinge   | 75.8/61.8    | 72.1/28.0    | 95.9/95.8   | 59.6/67.4   | **75.9/63.3** |\n|           | SiPBA-CE      | 76.3/62.8    | 74.0/34.4    | 95.2/95.0   | 64.0/72.0   | **77.4/66.1** |\n|           | SQP-Hinge     | 77.5/61.7    | 70.5/22.8    | 96.1/96.0   | 52.3/59.3   | 74.1/60.0     |\n|           | SQP-CE        | 76.0/62.6    | 73.4/32.9    | 94.9/94.8   | 63.0/71.0   | 76.8/65.3     |\n|           | Single-Hinge  | 76.8/56.0    | 69.3/15.0    | 95.8/95.6   | 47.2/52.3   | 72.3/54.7     |\n|           | Single-CE     | 76.4/55.4    | 70.0/19.2    | 95.6/95.3   | 43.1/46.9   | 71.3/54.2     |\n| LingSpam  | SiPBA-Hinge   | 63.4/59.1    | 66.2/51.2    | 71.1/65.4   | 99.4/99.6   | **75.0/68.8** |\n|           | SiPBA-CE      | 71.8/48.5    | 69.0/27.6    | 59.1/34.3   | 91.8/94.8   | **72.9/51.3** |\n|           | SQP-Hinge     | 42.5/53.8    | 45.3/52.0    | 72.5/65.8   | 98.2/99.0   | 64.6/67.7     |\n|           | SQP-CE        | 72.0/49.5    | 68.9/26.2    | 58.9/33.9   | 91.9/94.8   | 72.9/51.1     |\n|           | Single-Hinge  | 37.2/51.9    | 38.6/50.6    | 56.7/69.0   | 95.7/97.5   | 57.1/67.3     |\n|           | Single-CE     | 34.5/51.0    | 34.0/50.1    | 51.3/66.8   | 91.4/95.1   | 52.8/65.8     |\n\n---\n\nThis clarification and the full results will be incorporated into Section 5.2 of the revised manuscript.\n\n---\n\n### References\n\n[1] Z. Guan, D. Sow, S. Lin, and Y. Liang. *AdaProx: A novel method for bilevel optimization under pessimistic framework*. Conference on Parsimony and Learning, 2025.  \n[2] I. Benchouk, L. O. Jolaoso, K. Nachi, and A. B. Zemkoho. *Scholtes relaxation method for pessimistic bilevel optimization*. Set-Valued and Variational Analysis, 2025.  \n[3] M. Brückner and T. Scheffer. *Stackelberg games for adversarial prediction problems*. In International Conference on Knowledge Discovery and Data Mining, 2011."}, {"review_id": "E32GjlvWS3", "reviewer": "Reviewer_roeL", "summary": "The paper presents a novel approach to solving Pessimistic Bilevel Optimization (PBO) problems by proposing a single-loop gradient-based algorithm named SiPBA. The core technique involves constructing a smooth approximation of the PBO problem using penalization and regularization methods. This approximation transforms the original non-smooth PBO into a smooth optimization problem, enabling the application of efficient gradient-based methods. The authors provide theoretical validation for the proposed smooth approximation scheme and establish convergence guarantees.", "questions": "See the above weakness.", "limitations": "yes", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. Algorithmic Innovation. The paper successfully relaxes the original PBO problem to a strongly convex-strongly concave formulation, enabling the development of a single-loop first-order gradient algorithm. \n   \n2. Theoretical and Empirical Validation. The authors provide rigorous theoretical analysis, including convergence rates and stationarity conditions. Additionally, the empirical results demonstrate the effectiveness and efficiency.\n\n3. The paper is well-structured and clearly presented. The technical details are well-explained, and the mathematical derivations are thorough.\n \nWeaknesses\n\n1. Related Work. This paper lacks a detailed discussion of existing work on first-order optimization algorithms and single-loop methods for both Optimistic and Pessimistic Bilevel Optimization [1-7]. This omission makes it difficult to assess the novelty and improvements over existing methods. Additionally, the lack of experimental comparisons with other PBO algorithms limits the evaluation of the proposed method's performance.\n\n[1] A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse\n\n[2] BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach\n\n[3] Hyperparameter Tuning Through Pessimistic Bilevel Optimization\n\n[4] A fully first-order method for stochastic bilevel optimization\n\n[5] One way to solve pessimistic bilevel optimization problems\n\n[6] On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation\n\n[7] Scholtes Relaxation Method for Pessimistic Bilevel Optimization\n\n2. Theoretical Gaps. The paper constructs an approximation function that ensures strong convexity in \\(z\\) and strong concavity in \\(y\\). While this is a simple strategy for problem relaxation, I am not quite sure about the strong concavity property. Moreover, the min-max problem is transformed into a max-min problem using Sion's theorem. Such relaxation is similar to conjugate gradient method, which require statements on the prima-dual gap. The authors are kindly suggested to provide a theoretical bound on the gap between the optimal solutions of the original and approximated problems.\n\n3. Convergence Results. The convergence results presented in Proposition 4.1 and Theorem 4.2 are somewhat weak. The derivation of the merit function \\(V_k\\) includes additional constant terms that are not thoroughly discussed. I’ve checked partial proof. It is unclear how these terms are introduced or whether they depend on specific assumptions or parameter choices. \n\nAdditionally, the paper only provides bounds on the minimum of the error terms \\min_k \\|x^{k+1}-x^k\\|, which does not strongly support the algorithm's convergence guarantees. A more detailed analysis of the asymptotic or expected convergence rates of V_{k+1} - V_k, x^k-x^* or x^{k+1} - x^k would be beneficial.\n\n4. The authors are encouraged to analyze the algorithmic (computational and storage) complexity [8], which is crucial for comparison among existing algorithms, and understanding the algorithm's practical applicability and performance in large-scale problems.\n\n[8] On the complexity of first-order methods in stochastic bilevel optimization\n\n5. The experimental section lacks comparisons with other existing PBO optimization algorithms . Some commonly investigated problems in PBO [9,10] are also suggested in the experiments, instead of merely on simple synthetic data.\n\n[9] The Standard Pessimistic Bilevel Problem\n\n[10] Revisiting and Advancing Fast Adversarial Training Through The Lens of Bi-Level Optimization", "was_revised": true, "final_justification": "Partial issues are well addressed. And I decided to raise the scores to 3.\n\nThe current experiments are limited to low-dimensional cases and some classical statistical problems. Indeed, the bilevel optimization has been widely extended to many fields in machine learning scenarios, which this work ignores. \n\nTheoretically, the **min-max and max-min type problems are not equally consistent** except for the convex-concave scenario [Sion's Theorem]. This is the key concern in my review, **which still has not been addressed in the authors' response**. **Some assumptions are indeed rarely shown in some previous relevant works**, which could be some kind of **strong without applicable examples in practice**.\n\nMoreover, this is a good algorithm for some specific tasks, e.g., maximum AUC bilevel problem.", "rebuttal": "We sincerely thank the reviewer for their time and comments. We are grateful for their acknowledgment of our work's primary contributions and appreciate the opportunity to clarify our work and address the concerns raised.\n\nBelow, we address each point in detail.\n\n---\n\n## 1. On Related Work and Experimental Comparisons\n\nWe appreciate the reviewer's suggestions for related work and would like to clarify how our paper is positioned with respect to these references. We also take this opportunity to present new experimental results that further benchmark our method against relevant algorithms.\n\n### Discussion of Prior Literature:\n\nThe reviewer mentioned several references, a number of which were already cited and discussed in our manuscript.\n\n* References [2, 4, 6, 7] in the reviewer's comments correspond to references [38, 34, 35, 11] in our paper, and their relationship to our work is discussed in the Related Work part.\n\n* Regarding the other references suggested:\n\n    * Reference [1]: This work studies first-order algorithms for optimistic bilevel optimization. Our paper, in contrast, focuses on the pessimistic formulation (PBO), which addresses a different class of problems.\n\n    * Reference [3]: This paper applies PBO models to hyperparameter tuning. The algorithm it employs is the one proposed in our reference [11], which we have already discussed.\n\n    * Reference [5]: This is a very recent work (published April 2025) that tackles a specific subclass of PBO where the upper-level objective is quadratic and the lower-level is linear. It proposes a single-level DC (Difference of Convex) program reformulation. The resulting algorithm is neither single-loop nor gradient-based in the same vein as our method, making it less directly comparable.\n\nFurthermore, the reviewer suggested experiments on problems from [9, 10]. We have carefully examined these works and concluded they are not suitable for benchmarking our method.\n\n* Reference [9]: The PBO applications in this work are from economics and involve integer variables, which falls outside the continuous optimization setting considered in our paper and the broader machine learning context.\n\n* Reference[10]: This work focuses on the optimistic bilevel optimization model, which is fundamentally different from the PBO problem we study.\n\nGiven this, we respectfully maintain that our original manuscript provided a detailed discussion of the relevant existing literature.\n\n### Experimental Comparisons:\n\nWe wish to clarify that our original manuscript did contain experimental comparisons, specifically benchmarking our proposed SiPBA against the AdaProx-PD algorithm [2] on a synthetic example. To further strengthen our evaluation and address the reviewer's concern, we have now expanded these experiments to include additional important baselines: AdaProx-SG [2] and the Compact/Detailed Scholtes relaxation methods [3]. The comprehensive results for each method are summarized in our response to Reviewer ckLr, which demonstrate that SiPBA is not only significantly faster but also more robust, consistently converging to a valid solution across all runs.\n\n---\n\n## 2. On the Theoretical Analysis\n\n* **Strong Concavity**: The reviewer questioned the strong concavity of $\\psi_k(x,y,z)$ (defined in Eq. (3)) with respect to $y$. This property follows directly from the strong concavity of the upper-level objective $F(x,y)$ with respect to $y$, which is an assumption stated in Assumption 1.\n\n* **Min-Max Interchange**: The reviewer also raised a question about the interchange of minimization and maximization operators in Line 146: $\\min_{z \\in Y} \\max_{y \\in Y} \\psi_k(x, y, z) = \\max_{y \\in Y} \\min_{z \\in Y} \\psi_k(x, y, z)$. As we discussed in Lines 143-146, this equality holds due to the existence of a saddle point for $\\psi_k(x, y, z) $ with respect to variables $(y,z)$. This is a direct consequence of classical min-max theorems (e.g., [VII, Theorem 4.3.1, 12] or [Theorem 3.1.29, 13]). There is no primal-dual gap in this step.\n\n* **Convergence of the Approximation**: Finally, we would like to highlight Theorem 2.5, which establishes the convergence of our smoothing approximation to the original PBO problem. This theorem formally proves that the solution to the smoothed problem converges to a true solution of the original PBO problem as the smoothing parameter approaches zero, justifying the correctness of our smoothing framework.\n\n---\n\n## 3. On Convergence Results\n\n* **Definition of Constants**: The reviewer commented on the constants used in the merit function $V_k$. All terms, including $\\underline{\\phi}$, $a_k$ and $b_k$, are explicitly defined in the paper. Specifically, $\\underline{\\phi}$ is discussed in Lines 223-224, and the precise formulas for $a_k$ and $b_k$ are provided in the statement of Proposition 4.1 in Line 233.\n\n* **Convergence Guarantees**: The reviewer's claim that our paper \"only provides bounds on the minimum of the error terms\" is a misinterpretation of our results. In Theorem 4.2, we establish the asymptotic convergence of the sequence generated by our algorithm, explicitly showing that key error terms approach zero:\n\n   $$\n  \\lim_{k \\rightarrow \\infty} \\frac{1}{\\alpha_k} \\|\\|x^k - \\mathrm{Proj}_X(x^k - \\alpha_k \\nabla \\phi_k(x^k))\\|\\| = 0, \n   $$\n\n   $$\n   \\lim_{k \\rightarrow \\infty} \\|\\| u^k - u_{k}^{\\star}(x^k) \\|\\| = 0.\n   $$\n\n    Furthermore, establishing a convergence rate based on the metric $\\min_{0 \\le k < K} \\frac{1}{\\alpha_k^2} \\|\\|x^{k+1} - x^k\\|\\|^2$\n    is a standard and widely accepted practice for gradient-based methods applied to general non-convex optimization problems (see, e.g., [Theorem 10.15, 14]).\n\n---\n\n## 4. On Algorithmic Complexity\n\nWe thank the reviewer for suggesting that we include a discussion of complexity. We will add the following analysis to the revised manuscript.\n\n* **Computational Complexity**: At each iteration, SiPBA performs gradient evaluations ($\\nabla_xF, \\nabla_x f, \\nabla_y F, \\nabla_y f$) and several vector operations. Since the cost of gradient evaluation is typically linear in the variable dimension, the per-iteration computational complexity of SiPBA is $\\mathcal{O}(n + m)$.\n\n* **Storage Complexity**: The algorithm exhibits low memory requirements. To compute the next iterate, it only needs to store the variables from the preceding step $(x^k, y^k, z^k)$ and a few intermediate vectors. Consequently, the storage complexity is $\\mathcal{O}(n + 2m)$.\n\nThis lean computational and memory footprint confirms that SiPBA is scalable and well-suited for practical, high-dimensional applications, representing a key advantage of our approach.\n\n### References\n\n[1] J. Li, B. Gu, and H. Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. In *the AAAI Conference on Artificial Intelligence*, 2022.\n\n[2] B. Liu, M. Ye, S. J. Wright, P. Stone, and Q. Liu. BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach. In *Advances in Neural Information Processing Systems*, 2022.\n\n[3] M. A. Ustun, L. Xu, B. Zeng, and X. Qian. Hyperparameter Tuning Through Pessimistic Bilevel Optimization. In *arXiv:2412.03666*, 2024.\n\n[4] J. Kwon and D. Kwon and S. J. Wright and R. D. Nowak A fully first-order method for stochastic bilevel optimization. In *International Conference on Machine Learning*, 2023.\n\n[5] A. S. Strekalovsky. One way to solve pessimistic bilevel optimization problems. In *Optimization*, 2025.\n\n[6] J. Kwon and D. Kwon and S. J. Wright and R. D. Nowak On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation. In *International Conference on Learning Representations*, 2024.\n\n[7] I. Benchouk, L. O. Jolaoso, K. Nachi, and A. B. Zemkoho. Scholtes relaxation method for pessimistic bilevel optimization. *Set-Valued and Variational Analysis*, 2025.\n\n[8] J. Kwon, D. Kwon, and H. Lyu. On the complexity of first-order methods in stochastic bilevel optimization. *International Conference on Machine Learning*, 2024.\n\n[9] L. Lampariello, S. Sagratella and O. Stein. The standard pessimistic bilevel problem. *SIAM Journal on Optimization*, 2019.\n\n[10] Y. Zhang, G. Zhang, P. Khanduri, M. Hong, S. Chang and S. Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. *International Conference on Machine Learning*, 2022.\n\n[11] B. Zeng. A practical scheme to compute the pessimistic bilevel optimization problem. *INFORMS Journal on Computing*, 2020.\n\n[12] JB. Hiriart-Urruty and C. Lemaréchal. Convex analysis and minimization algorithms I: Fundamentals. In *Springer science and business media*, 2013.\n\n[13] Y. Nesterov. Lectures on convex optimization. In *Springer International Publishing*, 2018.\n\n[14] A. Beck. First-order methods in optimization. In *SIAM*, 2017."}]

Author rebuttal:

Meta-review: The work studies the underexplored setting of pessimistic bilevel optimization. The authors propose a single-loop first-order gradient algorithm based on a smooth approximation of the PBO value function. The theoretical contributions include the design of a penalization–regularization-based smooth approximation and a convergence analysis of SiPBA with non-asymptotic guarantees. The algorithm avoids computing exact second-order derivatives, which makes it appealing from a computational standpoint. Experiments on synthetic problems, spam classification, and hyper-representation learning illustrate its feasibility and efficiency, with comparisons to existing methods such as AdaProx.

The main strength of the work lies in tackling a relatively less studied PBO problem through a first-order and single-loop approach. The theoretical analysis is carefully developed, the algorithm is easy to implement, and the smooth approximation technique represents the core technical contribution. The empirical results, though limited, provide some evidence of the method’s effectiveness and scalability.

Nevertheless, there are still some weaknesses. The theoretical framework relies on restrictive assumptions (e.g., strong convexity/concavity requirements). The smooth approximation depends heavily on heuristic penalization and regularization terms, which, while functional, limit the sense of conceptual novelty. The theoretical results are also confined to stationarity. The experimental validation, though expanded in the rebuttal, remains modest in scope and does not convincingly demonstrate broad applicability or real-world advantages. 

In the rebuttal, the authors clarified the role of assumptions, expanded their discussion of the single-loop claim, and added experiments on hyper-representation learning. These efforts improved clarity and provided additional empirical evidence, but the fundamental limitations remain: restrictive conditions, the heuristic nature of the approximation, and limited experimental scope.

In summary, the paper makes a technically solid and timely contribution to the niche area of pessimistic bilevel optimization, offering a new algorithmic perspective. Its novelty lies primarily in the problem framing and smooth approximation. The work is sound and has value, though its scientific depth is limited.
Decision: Accept (poster)