Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds
Authors: Pengyu Chen
Xu Shi
Rujun Jiang
Jiulin Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: Simple Bilevel Optimization
Hölderian Error Bound
Penalization
Complexity
Primary area: optimization
TL;DR: This paper proposes a novel penalty-based formulation to solve simple bilevel problems with lower complexity results.

Abstract: This paper investigates simple bilevel optimization problems where we minimize a convex upper-level objective over the optimal solution set of a convex lower-level objective. Existing methods for such problems either only guarantee asymptotic convergence, have slow sublinear rates, or require strong assumptions. To address these challenges, we propose a penalization framework that delineates the relationship between approximate solutions of the original problem and its reformulated counterparts. This framework accommodates varying assumptions regarding smoothness and convexity, enabling the application of specific methods with different complexity results. 
Specifically, when both upper- and lower-level objectives are composite convex functions, under an $\alpha$-Hölderian error bound condition and certain mild assumptions, our algorithm attains an $(\epsilon,\epsilon^{\beta})$-optimal solution of the original problem for any $\beta> 0$ within $\mathcal{O}\left(\sqrt{{1}/{\epsilon^{\max\\{\alpha,\beta\\}}}}\right)$ iterations. The result can be improved further if the smooth part of the upper-level objective is strongly convex. We also establish complexity results when the upper- and lower-level objectives are general nonsmooth functions. Numerical experiments demonstrate the effectiveness of our algorithms.

Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds
Pengyu Chen'
Xu Shi' School of Data Science Fudan University xshi220m, fudan. edu cn
Rujun Jiang'
School of Data Science
School of Data Science Fudan University rjj iajigfuuddnnn...mm edu
Fudan University
pychen22@m. fudan edu.
Jiulin Wang
School Data Science
Fudan University wangjiulin@fudan edu. cn
Abstract
This paper investigates simple bilevel optimization problems where we minimize an upper-level objective over the optimal solution set of convex lower-level ob- jective. Existing methods for such problems either only guarantee asymptotic convergence, have slow sublinear rates, or require strong assumptions. To address these challenges, we propose penalization framework that delineates the rela- tionship between approximate solutions of the original problem and its reformu- lated counterparts. This framework accommodates varying assumptions regard- ing smoothness and convexity, enabling the application of specific methods with different complexity results. Specifically, when both upper- and lower-level objec- tives are composite convex functions, under an o--ölderria error bound condition and certain mild assumptions, algorithm attains (. solution of
the original problem for any 3 > O within O (1/emax(a..B) iterations. The result can be improved further if the smooth part of the upper-level objective strongly convex. We also establish complexity results when the upper- and lower- level objectives are general nonsmooth functions. Numerical experiments demon- strate the effectiveness of algorithms.
Introduction
Bilevel optimization involves embedding one optimization problem within another, creating hi- erarchical structure where the upper-level problem's feasible set is influenced by the lower-level problem. This framework frequently occurs various real-world scenarios, such as meta-learning
[Bertinetto all 2018.
Rajeswaran all, 2019), hyper-parameter optimization [KCen all, 20224]
Franceschi et all
2018
Shaban et al [ reinforcement learning [Mingy] et all 202( and ad-
versarial learning [Bishop all 202)) Wang all, RIXI (022)) In this paper, concentrate on a subset of bilevel optimization known as simple bilevel optimization (SBO), which has garnered significant interest in the machine learning community due its relevance in dictionary learning
Beck and Sabach. 2012), Jiang et al,, (2023), lexicographic optimization [Kissel all 20211 Gong
2021], lifelong learning [Malitsky, 211 Jang all, [023;;; ; see more details in Appendix Al
Equual contribution Corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

SBO aims to find an optimal solution that minimizes the upper-level objective over the solution set of the lower-level problem. In other words, we are interested solving the following problem:
min F(x) s.t. x E arg min G(z). XER
(P)
ZER
R - ) are proper, convex, and lower semi-continuous functions. We also assume that the optimal solution set of the lower-level problem, denoted as Xopt. is nonempty. More- over, since G is convex and lower continunn,, it holds that Xop is closed and convex [Bertsekas etall 2003, Proposition 1.2.2 and Page 49].
Here F, F.G:
In this paper, we first reformulate problem (E) into the constrained form:
min F(x) s.t. G(x) G S 0,
(Pval)
where G represents the optimal value of the unconstrained lower-level problem. Based on this reformulation, we consider the following penalization of (Pval),
min XER"
4 y (x) F(x) + >P(x),
(Py))
where p(x)= == G(x) G is the so-called residual function and 7 is the penalized parameter. Obviously, we have p(x) 2 O, and p(x) = 0 if and only if x E Xopt.
Denote F and G* the optimal values of problem (L) and the lower-level problem minxeR" G(x), respectively. We aim to find an (cF, (.0eg)))0oo ooptima solution x of problem (E), which satisfies
F(x*) - F <F G( - G S EG.
Moreover, a point x is said to be an 6-optimal solution of problem (P-) if
Φ (x.)
Φ e,
where t is the optimal value of problem
1.1 Related work
Various approaches have been developed to solve problem (L) (Cabol, 200S, Solodow, 2007 Sabach
and Shtern, 2017, Dutta and Pandii, 2022 [ong et all 2021]. Among those, one category that is
the most related to penalization formulation (P-) is the regularization method, which integrates the upper- and lower-level objectives through Tikhonov regularization [[Tkhonov and Arsenin, [977]]
min n)(x) := F + G(x),
(PReg)
xER*
where a is the so-called regularization parameter. When F' is strongly convex and its domain is com- pact, Amini and Yousefian [20T]]] extended the IR-PG method from Solodoy [2[07]] which achieved asymptotic convergence rate for the upper-level problem and convergence rate of O (1/K"0.5-)) for the lower-level problem, where b E (0, 0.5). Malitsky [2017]] studied a version of Tseng's ' ac- celerated gradient method and showed a convergence rate O (1/K) for the lower-level problem. while the convergence rate for the upper-level objective is not explicitly provided. Kaushik and Youschan [202T] proposed an iteratively regularized gradient (a-IRG) method which obtains a com- plexity of O (1/K0.5-b) and O (1/K*) for the upper- and lower-level objective, respectively, where b E (0, 0.5). Inspired by this research, and under a quasi-Lipschitz assumption for F. Merchav.an Sabach [202K] introduced a bi-subgradient (Bi-SG) method. This method demonstrates convergence rates of ((1/A K*) and 0(1/K1- for the lower- and upper-level objectives, respectively, where b E (0.5, 1). In their framework, the convergence rate of the upper-level objective can be improved to be lincar when F' is strongly convex. Recently, under the weak-sharp minima assumption of the lower-level problem, Samadi aLa [212]] proposed a regularized accelerated proximal method (R- APM), showing convergence rate of (l)K3²) for both upper- and lower-level objectives. When the domain is compact and F, G are both smooth, Giang- Tran et all [2025] proposed an iteratively regularized conditional gradient (IR-CG) method, which ensures convergence rates of (1/KPP) and O(1/K) for upper- and lower-level objectives, respectively, where E (0, 1).
Despite the abundance of existing methodologies yielding non-asymptotic convergence outcomes, their efficacy is frequently contingent upon additional assumptions. Denote I.,, and T.g, as the Lips- chitz constants for the gradients of the smooth components in the upper- and lower-level objectives,

---

respectively, Specifically, when F is strongly convex and G is smooth, Beck Sabach [0011]] pre- sented the Minimal Norm Gradient (MNG) method and provided the asymptotic convergence the optimal solution set and a convergence rate of O / /e²) for the lower-level problem. When F is assumed to be smooth, Jiang et al. [2023]] introduced conditional gradient-based bilevel optimiza- tion (CG-BiO) method, which invokes at most O (max (L,, /cp, T. /())) )) of linear optimization oracles to achieve an (Ep, EG) (EF,,G))optinnn -optimal solution. Shen et al [2022]] combined an online framework with the mirror descent algorithm and established a convergence rate of ((L/e") for both upper- and lower-level objectives, assuming a compact domain and boundedness of the functions and gradients at both levels. Furthermore, they showed that the convergence rate can be improved to O(1/c²) under additional structural assumptions. For a concise overview of overall methodologies, including their assumptions and convergence outcomes, refer to Table (I in Appendix H
For general bilevel optimization problems, there have been recent results on convergent guarantees [Shen Chen. 2026, Sow et 2022. Chen et all 20223, Huang. 2023]. Among those, the one that the most related to ours [Shen and Chen, 2023]_ It investigates the case when the upper-level objective is nonconvex and gives convergence results under additional assumptions (Shenand 2022, Theorem 3 and 4]. However, as the general bilevel optimization problem nonconvex, the algorithms in the literature often converge to weak stationary points, while our method for SBO converges to global optimal solution.
1.2 Our approach
Our approach is straightforward. Firstly, we introduce a penalization framework delineating the connection between approximate solutions of problems (E) and This framework enables the attainment of an (crs, ( --pptmal solution by solving problem
approximately. Subsequently, our focus shifts solely to resolving the unconstrained problem (P. Depending on varying assump-
tions regarding smoothness and convexity, we can employ different methods such as the accelerated proximal gradient (APG) methods [Beck and Teboullé, 2009 Nesterov, 2013, Lin and Xiad, 20144] to solve problem PP
We summarize our main contributions as follows.
We propose a framework that explicitly examines the relationship between an e-optimal solution of penalty formulation (P.) and an (ep, -opttiiaa solution of problem (P)). We also provide lower bound for the metric F(x) - FF*
When F and are both composite convex functions, we provide a penalty- APG algorithm that attains an ( solution of problem (E) within O(V1/ ) iterations. If the upper-level objective is strongly convex, the complexity can be improved O ((v/1/emax(o-1.0 1,3-1 log !). We also apply method for the scenario where both the upper- and lower-level objectives are generalized nonsmooth convex functions.
We present adaptive versions of PB-APG and PB-APG-sc with warm-start, which dynami- cally adjust the penalty parameters, and solve the associated penalized problem with adap- tive accuracy. The adaptive ones have similar complexity results their primal counter- parts but can achieve superior performance in some experiments.
Utilizing the penalization method to address the original SBO problem is a novel approach. While Tikhonov regularization may seem similar our framework, its principles differ. Implementing Tikhonov regularization necessitates the "slow condition" (lims- σ = 0, Ek=u = +oo), which requires iterative solutions for each iteration. contrast, our method simply involves solving a single optimization problem (2)) for given Furthermore, we establish a relationship between the approximate solutions of the original bilevel problem and those of the reformulated single- problem (P)) for a specific 7. This is the first theoretical result connecting the original bilevel problem to the penalization problem, accompanied by an optimal non-asymptotic complexity result.
2 The penalization framework
We begin by outlining specific assumptions for F and G, as detailed below. Assumption 2.1. The set S = UxEX.. 0F(x) is bounded with diameter LP maxęss [|
Note that the type of subdifferential OF used here is the most general form for convex function, as detailed in [Berisckas et all 2003 Section 4.2]. When the upper-level objective F is non-convex.
3

---

we replace the assumption with the condition that the upper-level objective is Lipschitz continuous (cf. Theorems 2 and 2.)).
Assumption 2.2 (Hölderian error bound). The function p(x) := G(x) G satisfies the Hölderian error bound with exponent 2 and
0. Namely,
dist(x;, Xoxe pp(x), Vx E dom(C),
where dxst(xx, Xmp) = infyexa Xap ||x
y|1-
We remark that Hölderian error bounds are satisfied by many practical problems and widely used in optimization literature [Pang. 1997, Bolie et 2017 Zhou and So. 2017, Roulet and d' Aspremont
2020, Brang and Li. 0022]. There are Iwo notable special cases: (i) when = 1, we often refer to Xopt as set of weak sharp minima of G [[uurke and Ferris, I193,, Studniarski and Ward, (199, Burke and Deng, 20005, Samadi et all [023]] (ii) when a = 2, Assumption 2 is known as the quadratic growth condition [Drusvyatskiy and Lewis, 2018a]] Additional examples of functions exhibiting Hölderian error bound, along with their corresponding parameters, are presented in Appendix C
We now ready establish the connection between approximate solutions of problems (L) and (?.). The subsequent two lemmas build upon the work of Shen and Chen [202X] for (general) bilevel optimization. Compared with their work, generalize the exponent from 2 to 1, providing a more general result. Furthermore, we also derive lower bound for the penalized parameter for all and present theoretical framework for these scenarios.
Lemma 2.3. Suppose that Assumptions D 2.2 hold with or >> 1. Then, for any 0, an optimal solution of problem (H) is an e-optimal solution of problem
when 7 2 pl (ax 1)a- - 2-1-a
Lemma MK establishes the relationship between optimal solution of problem (E) and an e-optimal solution of problem (P-]) when a > It also provides a lower bound for y. which plays a pivotal role in the complexity results. The proofs of this paper deferred to Appendix E.
The lemma presented below yields more favorable outcome when a 1, which is referred as exact penalization. Notably, this specific result is not discussed in Shen and Chen [2023]]
Lemma 2.4. Suppose that Assumptions 2 and 2.2 hold with a = 1. Then an optimal solution of problem (E) is also an optimal solution of problem (P3) if 2 pl and vice versa if > plr. In this case, we say that there is an exact penalization between problems (D) and
For simplicity, we define
pl - 11) a > if =
(2)
pl
Based on Lemmas 2 and 2.4. we give an overall relationship of approximate solutions between problems and Theorem 2.5. Suppose that Assumptions 2 and 2
hold. For any given > 0 and B > 0, let
21 21 2-0 1eet-B
ff ff=11
with 7 defined in (2). X is an e-optimal solution of problem optimal solution of problem (E).
then Xt is an (e, (E
Particularly, we are also able establish lower bound for F(žt)= under the same conditions outlined in Theorem L
Theorem 2.6. Suppose that the conditions in Theorem 2.3 hold. Then, Xy satisfies the following suboptimality lower bound,
F(C:) F" (pl _
By setting / a, we obtain F(X)) F 2 -pac. which along with Theorem 2.3 gives
FF(x)) F < max{c,p=cc
We emphasize that the lower bound established in Theorem R.G is an intrinsic property problem
( under Assumptions I and 2i This property is independent of the algorithms present.

---

2.1 The upper-level function is non-convex
Note that the upper-level objective F required be convex in the above context (cf. Theorem This raises a question: while Theorem 2 establishes the relationship between approximate
2.5).
solutions problems (H) and (PD). the distinction between the global or local optimal solutions of problem (E) and (PA) remains unclear when F is non-convex.
We first establish the relationship between global optimal solutions of problems and when F is non-convex, which is similar to Theorem 2.
Theorem 2.7. Suppose that Assumption 2.2 holds, G convex, and F is I-Lipschitz continuous on dom(F). For any given > O and > 0, let
Y x
2 1
if Ra>1,
(3)
ifa=1.
where 7 is given by (.)) X; an e-globul optimal solution of problem (e. optimal solution of problem (B).
then X is an
Theorem provides the relationship between the global optimal solutions of problems (P) and
(E). However, the relationship between local optimal solutions of these problems is more intricate than those of the global ones [Shen and Chen 2023). Given r > and z E R", define B(z,7) r) =
{x E R² ||x 2|1 < r.. We present the following theorem, which demonstrates that local optimal solutions of problem
can serve as approximate local optimal solutions of problem (E).
Theorem 2.8. Suppose that Assumption Pi holds and G convex. Let x., be a local optimal solution of problem (F-) on B(xx, r). Assume L-Lisschitz continuous on B)) Then x", an approximate local optimal solution of problem (L) that satisfies F(xx)) F S and G(xtt) G* S
when 1 and Furthermore, x is local optimal solution of problem (E) when a and pl.
) where FB is the optimal value of problem (E) on B(x*, r) Xopt-
Indeed, the relationship between approximate local optimal solutions of problems more intricate than the connection among global solutions presented in Theorem These inter- actions will be the focus of our future work. The proofs of Theorems 2 and 2 are presented in Appendixes E.5 and E.G.
and (E) is
3 Main algorithms
In this section, we concentrate on addressing problem (E), making various assumptions, and offering distinct convergence outcomes.
3.1 Both objectives are convex composite functions
In this scenario, we address problem LL) where F and G are both composite functions, i.e., F fi fe and G 91 + 92-
Assumption 3.1. F and G satisfy the following assumptions.
(I) The gradient fx(x), denoted as f1, is Ly, Lipschitz continuous on dom
(2) The gradient of g1 (x).. denoted as V is 4. -Lipschitz continuous on dom (G);
(3) and 82 are proper, convex, lower semicontinuous, and possibly non-smooth.
We remark that Assumption 1 1)(3) is more general than many existing papers in the literature. Specifically, while previous works such Beck and Sabach [201], Amin and Yousefan [20%]. Jiang et al. [2023]] Giang-Tran et all [20)]]]] require the upper-level objective to be smooth or strongly convex, we simply assume that
composite function composed of smooth convex function and a possibly non-smooth convex function. For the lower-level objective, previous works such as Beck and Sabachi [2014], Amini and Yousehan [201%, Drang et all [2023],, Giang-Trra et al.
[|02]]] impose smoothness assumptions and, in some cases, convexity and compactness constraints on the domain; while our approach does not require these additional constraints, allowing for more flexibility and generality presented in Assumption (3)3).
5

---

We are now prepared to introduce two algorithms: the penalty-basee based accelerated proximal gradient (PB-APG) algorithm and its adaptive counterpart, the aPB-APG to solve problem and, subse- quently, to obtain an (er, -o)ttimaall solution of problem (E))
To simplify notations, omit the constant term -7G", and rewrite problem follows,
min Φ, (x) == 0, + (x), xER"
(P&)
where (x) = fi fx) (x) and (x) = f2(x) + (92 represent the smooth and nonsmooth parts, respectively. Then, follows that the gradient of dy (x) is L,,Lisschitzz continuous with L, L, 7L
To implement the APG methods, need another assumption concerning (x).
Assumption 3.2. For any > 0, the function diy (x) is prox -rieefrendly, i.c., the proximal mapping
1 tro (y) arg min (x) + b ||x y113),
21
xER
is easy to compute for any t > 0.
The function d5y (x) represents the of non-smooth functions, and proximal mapping for such function sums is widely studied and used in the literature [Yu, 2013, Postelmik and Condail 2011, Adly all 2019, Booh all MIZ Lataatt general requirement compared to many existing algorithms [Sabach and Shtern 2017. Grang Iran important to note that our assumption is more general than existing literature. In the simple bilevel literature, when employing proximal mappings, researchers often consider the scenario where only one level contains nonsmooth term (see, e-g., [Diang all 2023, Doron and Sheml 2023., Samadi et all 2023, Merchay and Sabach. 2023)) In this case, the proximal mapping of the sum f2 + 792 then reduced to the proximal mapping of either f2 or g2, which a more easily satisfied condition.
2023). This assumption is also a more
all 202K)]
3.1.1 Accelerated proximal gradient-based algorithm
We apply the APG algorithm [eek and leboulle, 2009, Lin and Xtad, 2014, Nesterov. 2013 to solve problem Po)) as outlined in Algorithm MI Moreover, if the Lipschitz constant L,, is unknown or computationally infeasible, line search [Beck and Tehoullg 2009 can be adopted
and will yield almost the same complexity bound. For brevity, we denote Algorithm MI as x PB-APG Sy bh Ls, Ly Xo, e). where represents an e-optimal solution
Algorithm Penalty-based APG (PB-APG)
1: Input: 7, Loy = Li + 7 x-1 = X0 E R" R 0,1-1 to 1, 0,e > and {1x}.
2: for 2 do
3: Yk X + tx (tx-1 - 1) (xt x4-1)
4: X1+1 prox,,, 2 (yx Vor
5: end for
In Algorithm II, we stop the loop of Line. 3 if the number of iterations satisfies that:
2(L, + RZ
Se
(k: 1)²
where R is constant that satisfies [|xo
x=1
Combining Theorem and [esng 2008, Corollary 2), we establish the following complexity result for problem (E))
Theorem 3.3. Suppose that Assumptions 2.
and B74 hold and the sequence (tx) ) in Algoritiun D
satisfies 1-12+1
13.1 < it' Let be given as in Theorem ME
Algorithm D generates an (c, 1p ))
solution of problem (E) after at most K iterations, where
( Ln
maxx Lggs
K K=O
p.

---

Note that Theorem + encompasses all possible relationships between the magnitudes of and eG in (I)) a 1 and B are arbitrary. Specially, if a and 3 I a, the number of iterations is K
(V 1 1/e This result matches the lower bound complexity for unconstrained smooth or convex
composite optimization [Nemirossk and Yudin, 1983 Woodworth and Srebro, 20TG). Additionally, if 9i = the number of iterations for obtaining an (e, e",e") -ooptimll solution of problems (E) is independent of % which
can be improved to K- = =O(VLn/e)
Remark 3.4. It noteworthy that Theorem in previous paper Samadi at [2025] provides the first method (//))// )/c) iterations to achieve an (e,c) solution if = 1 and F is smooth. Neverthe- less, our methodology diverges in various respects. First, approach is rooted in the penalization formulation of problem (Pva)) while the approach proposed by Samadi el aall [[02K] is based the Tikhonov regularization [[ikhonoy and Arseniri [Α9лл]] Second, we provide theoretical framework that clearly delineates relation- ship between approximate solutions of problems (E) and (P for all cases of a 2 and is non-convex, as indicated in Lemmas DKC 2X4 and Theorems 2.S. 2M LS Therefore, we can first shift our focus from (EE (E3) based the penalization framework and then use various methods to solve (F3) not limited to using the APG methods. Besides, the association between approximate solutions significantly based on whether a or a = 1. For the case a > 1, the lower bound comprehensively integrates the accuracy parameter which results in a more sophisticated analysis of the convergence result, while Samadi et all [2024]] did not consider the situation when
that needs O( D(v(Ig + +1
problem (E) and (F)) differs
1. Third, method applies to the case that F' composite, while Samadi all [[0z]]] requires F' be smooth. Finally, also propose adaptive version of our algorithm (see Algorithm that does not require an estimate of
3.1.2 Adaptive version with warm-start mechanism
practice, the penalty parameter y might difficult determine. This motivates us to propose Algorithm which adaptively updates y and invokes PB-APG with dynamic ς and solution accuracics.
Algorithm 2 Adaptive PB-APG method (aPB-APG)
1: Input: Xg E IR" 7 = 71 > O, Lis Lg 1, > 1, En > 0.
2: for k 2 0 do
3: (xxx)) = [x( 74-9 (x)
4:
(x) = f2(x) + 7299 (x)
5: Invoke X3: = PB-APG Oks uhk Lif Loi xk-1,
6: Ek+11 = Ek/11
7: Yk+1 = V7
8:
end for
In Algorithm D. we adaptively update the penalty parameter "Yk and invoke the PB-APG to generate an ap- proximate solution for (4) with accuracy ex. Meanwhile, warm-star start mechanism is employed, meaning that the initial point each subproblem the output of preceding subproblem. The convergence result of Algorithm D as follows.
Theorem 3.5. Suppose that Assumptions 2. 2.2 B. and B.2 hold. Also assume that for every outcome of inner loop Algorithm
||X: x R. Eo be given.
When > 1. set 11ah and define N == [o 1)a= -g 0000-//001++ and 7e pT 1)--1 E " ((
When a = 1, set v > 1, and define N = [log, (ple /To) and 78 == pLF.
Then, for any k 2 N, Algorithm D generates an (5t (rouh most K iterations, where K satisfies
2zg
optimal solution of problem (E) after at
(V +
K k=O
co
Thcorem shows that for any given initial accuracy 0, Algorithm can produce an approximate solution problem (E)) with the desired accuracy.
Remark 3.6. From Theorem S one can obtain an (c, - optimal solution of problem (E) within
OL Von/ee) iterations when e/n- S ca/n* I e. which is similar to the complexity results in Theorem M
7

---

3.1.3 The upper-level objective is strongly convex
We investigate the convergence outcomes when the smooth part of the upper-level objective exhibits strong convexity.
Assumption 3.7. [x) j--strongly convex dom(F) with
Assumption SW is another widely adopted setting in the existing SBO literature [Beck and Sabaci 2014
Sabach and Shemm 2017, Amin and Yousehant 20T9, Merchav and Sabach. R023). Here, we propose a variant of PB-APG that provide better complexity results than existing methods. Our main integration APG-based algorithm, which has been studied in the existing literature [[Nesterox. MOTK, and Xiao, 20E. Kiz, 2022). In this paper, we adopt the algorithm proposed in Lin and Xtad [20E] and modify with a constant step-size for simplicity as in Algorithm & Similar to Algorithm MI we denote Algorithm B by
PB-APG-sc(P,, Boy, 14, T.fa Tog e),
Algorithm 3 PB-APG method for Strong Convexity Case (PB-APG-sc)
1: Input: 14, L, = Li + + X 1. E R".
2: y = -Yo L Vo,
3: X ,rox, v4, ( L (F))
4: Initialization: Let x- X0 =
5: for k 2 0 do
X + - (xt xk-1)
6:
7: X1+1 = prox L (yk - L V (yx))
8: end for
convergence analysis of Algorithm B the existing literature Nestery
2013 Lnn and Xıad, 201E
Combining II and Xiadi 20TE, Theorem 1] and Theorem R we have the following complexity result.
Theorem 3.8. Suppose that Assumptions 2 (e, 8 é )-optimal solution of problem (E)) after at most K iterations, where K satisfies
and E. hold. Algoritium can produce an
Li 1 + log
1f maax(a.9) Log log
K ==
emax 1,8-1
Theorem 5. improves the complexity results of Theorem B.3 significantly, Specifically, when 0 < B S a 1. the convergence rate can be improved to be linear, i.c., O(v Ly, / log 2).
Additionally, we present an adaptive variant PB-APG-sc, termed aPB-APG-sc, which adaptively executes X = PB-APG-sc sc(o,, the μ, Ln Log Xx- (x) and enjoys the similar complexity results Algorithm B. as delineated in Algorithm @ within Appendix Dil
3.2 Both objectives are non-smooth
this section, we focus on the scenario where both upper- and lower-level objectives are non-smooth, namely, fi = = 0. Additionally, we assume that there is a point x E C in the lower level prob- lem, where C is either RR" (the unconstrained case) or nonempty closed and convex set satisfying C' C int (dom(+)) n dGom)
It is worth noting that in the case where both F' and G are non-smooth, the convergence result may not be as favorable as those in previous scenarios. This is primarily due to the limited availability of information and unfavorable properties concerning F' and G. In this case, we employ a subgradient method to solve problem
P3), which has been extensively studied in the existing literature [Shor, 2012, Buheeck all 201 Becck 2017 Nesterov, 20IN]. Specifically, we update
X Proio T)pEk)
(4)
where & E (xx) an subgradient of (xxx).. and (roje(x) is projection onto
Xet be optimal solution of problem ( and suppose that there exists a constant such that ||xo
xx|I
R. Motivated by Theorem 8.28 in Beeg [211 we establish the subsequent complexity result for problem (e))
Theorem 3.9. Suppose that Assumption
T holds. and ga Lz2- and loz Lipschitz continuous,
spectively, Set step-size 1yKK+I
R
in
Then, the subgradient method produces an (c, ( )-pptimmll
8

---

solution of problem H after at most K. iterations, where K satisfies
K K=O G
maax
12
Ja emax
non-smooth SBO problems, our method has lower complexity compared to existing approaches. Specifi- cally, under a bounded domain assumption, Heloou and Simóes [А] simply proposed an e-subgradient method with an asymptotic rate towards the optimal solution set. The a-IRG method in Kaushik and Yousehan [2021]
achieved convergence rates of 0(1/e ) and (11/e)) ) for the upper- and lower-level objectives, respec- tively, where (0, 0.5). Setting b 0.25 yields the convergence rates of O(1/c") for both upper- and lower-level objectives, which indicates that our complexity is more efficient than theirs when or < 2 and S a.
Furthermore, the online framework proposed in Shen all [2022] performed a complexity of O ((1/²) )) for both upper- and lower-level objectives. Similarly, our approach prevails over theirs when < 1.5 and /
Strongly convex upper-level objective. Based on Theorem 8.31 in Beck [201 we next explore the improved complexity result for problem (ED when fa is additionally strongly convex.
Theorem 3.10. Suppose that Assumption (3) holds, C S int (dom (F) n (omm)))) f2 L -p-psccch continuous and ps -stongly conver and g2 is 1u2 -ippschshitzz continuous. Choose step-size Ul
P12 (k43)
in (.) Then, the subgradient method produces an ( )optimal solution of problem after most K iterations, where K satisfies
(
L/ U.22 M c 20 1,28-1)
maxx (2.,28)
O
+
f2
To our knowledge, within the context of Theorem BTl current findings fail to exploit strong convexity to enhance results. However, approach capitalizes distinct structural characteristics that yield superior complexity outcomes relative Theorem 5 in cases where 2 S a.
4 Numerical experiments
We apply Algorithms M1 and A two simple bilevel optimization problems from the motivating ex- amples Appendix [ The performances
methods compared with several existing methods: MNG [Beck and Sabach 2014), BiG-SAM [Sabach and Shtemn 2017,, DEGD [Gong ct all (020I,, a-IRG [Kaushik
and Yousehan 2), I) CG-BiO [Lang et all 21231, Bi-SG [Merehay and Sabach, 2026 and R-APM [Samadi e alll 2023] For practical efficiency, we the Greedy FISTA algorithm proposed in Liang el all [2U2e] as the
APG method in approach. Detailed settings and additional experimental results presented in Appendix
10
K0
Figure 1: Performances of methods in LRP.
Figure Performances of methods in LSRP.
4.1 Logistic regression problem (LRP)
The LRP reads
m
x||² s.t. x E arg min XE3
min
log(1 + exp(-a/zz.) + (z),
(5)
ZER
177
where (x) is the indicator function of the set C fx R ||||| < 0} with 0 = 10. Our goal is to find solution the lower-level problem with the smallest Euclidean norm. The upper-level objective only
In this case, must have C' bounded, fa is both strongly convex and Lipschitz continuous.

---

consists of the smooth part, which is 1-strongly convex and 1-smooth; meanwhile. the lower-level objective is composite function, where the smooth part is im Amax (A* A--smotth, and the nonsmooth part prox- mrox-friendly [Duch all 2008].
this experiment, we compare our methods with MNG, BiG-SAM, DBGD, a-IRG, CG-BiO, and Bi-SG. We plot the values of residuals the lower-level objective G(xx) - G and the upper-level objective over time in Figure M.
As shown in Figure MI the PB-APG, aPB-APP APG, PB-APG-sc, and aPB-APG-sc algorithms exhibit significantly faster convergence performance than the other methods for both lower- and upper-level objectives, although R-APM attains similar outcomes, our PB-APG and PB-APG-sc ensure more rapid decline than shown the first subfigure Figure MI This is because our methods achieve lower optimal gaps desired func- tion values of the lower- and upper-level objectives with less execution time. This observation confirms the improved complexity results stated in the theorems above. Although the high exactness of our methods for the lower-level problem leads to larger upper-level objectives. Table E in Appendix ET] shows that methods much closer the optimal value. This is reasonable because the other methods exhibit lower accuracy at the lower-level problem, resulting in larger feasible sets compared to the lower-level optimal solution set Xopt- In addition, Figure II demonstrates that aPB-APG and aPB-APG-sc outperform PB-APG and PB-APG-sc in terms of convergence rate. This improvement can be attributed to the adaptiveness incorporated in Algorithms D and
g!
4.2 Least squares regression problem (LSRP)
The LSRP has the following form:
min T 2 ||x]|| + ||I||] S.L. E arg min 263"
2m ||Az
b1]?
(6)
XER
where 7 0.02 regulates the trade-off between & and la norms. We aim find sparse solution for the lower- level problem. The upper-level objective formulated as a composite function, which consists a r-strongly convex and 7-smooth component, along with a proximal meximmll-rrindly non-smooth component [Beck, 2017]] The lower-level objective is smooth function with a smoothness parameter of :. Amaxx (A (A" A).
In this experiment, we compare the performances of our methods with a-IRG, BiG-SAM, and Bi-SG. We plot the values of residuals of lower-level objective G(xx) G and the upper-level objective over time in Figure A
Figure shows that the proposed PB-APG, aPB-APG, PB-APG-sc, and aPB-APG-sC converge faster than the compared methods for both lower- and upper-level objectives, as well. For the upper-level objective, our methods achieve larger function values than other methods, except BiG-SAM (6 = 0.01). This is because our methods attain higher accuracy for the lower-level objective than other methods. We have similar observations in Section I. Furthermore. Figure Malso demonstrates that the adaptive mechanism produces tedrrcae-shapee curves for aPB-APG and aPB-APG-se, which might prevent undesirable fluctuations in PB-APG and PB-APG- sc.
5 Conclusion
This paper proposes penalization framework that effectively addresses the challenges inherent in simple bilevel optimization prohlems. By delineating the relationship between approximate solutions of the orig- inal prohlem and its penalized reformulation, we enable the application of specific methods under varying assumptions for the original problem. Under the Hölderian error bound condition, our methods achieve su- perior complexity results compared the existing methods. The performance is further improved when the upper-level objective is strongly convex. Additionally, we extend our framework to scenarios involving general nonsmooth objectives. Numerical experiments also validate the effectiveness of our algorithms.
smooth component
Acknowledgements
This work partly supported by National Key R&D Program of China under grant 2023YFA1009300 National Natural Science Foundation of China under grants 12171100 and the Major Program of NFSC (72394360,72394364).
References
Samir Adly, Loic Bourdin, and Fabien Caubet. On decomposition formula for the proximal operator of the sum of two convex functions. Journal of Convex Analysis, 26(2):699-718, 2019.
10

---

Mostafa Amini and Farzad Yousefian. An iterative regularized incremental projected subgradient method for class of bilevel optimization problems. In 2019 American Control Conference (ACC), pages 4069-4074. IEEE, 2019.
Amir Beck. First-order methods in optimizaaiion SIAM, 2017.
Amir Beck and Shoham Sabach. A first order method for finding minimal norm-like solutions of convex optimization problems. Mathematical Progrumming, 147(1-2):25-44) -6, 2014.
Amir Beck and Mare Teboulle. A fast iterative thrnkkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183-202, 2009.
Luca Bertinetto, Joao F Henriques, Philip HS Torr, and Andrea Vedaldi. Meta-learning with differentiable closed-form solvers. arXiv preprint arXiv:1805.081 08136, 2018.
Dimitri Bertsekas, Angelia Nedic, and Asuman Ozdaglar. Convex analyxis and optimization, volume 1. Athena Scientific, 2003.
Nicholas Bishop. Long Tran-Thanh, and Enrico Gerding. Optimal learning from verified training data. Ad- vances Neural Information Processing Systems, 33:9520 9529, 2020.
Jérôme Bolte, Trong Phong Nguyen, Juan Peypouquet, and Bruce Suter. From error bounds to the complexity of first-order descent methods for convex functions. Mathematical Progrumming, 165:471-507, 2017.
Digvijay Boob, Qi Deng, and Guanghui Lan. Stochastic first-order methods for convex and nonconvex func- tional constrained optimization. Mathematicul Programming. 197(1):215-779, 2023.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trendy@ in Machine Learning, 8(3-4):21-3555 2015.
James Burke and Sien Deng. Weak sharp minima revisited, part ii: application to lincar regularity and error bounds. Mathematical Progrumming, 104(2-3):335-61, 2005.
James V Burke and Michael C Ferris. Weak sharp minima in mathematical programming, SIAM Journal on Control and Optimization, 31(5):1340 1359, 1993.
Alexandre Cabot. Proximal point algorithm controlled slowly vanishing term: applications to hierarchical minimization. SIAM Journal on Optimization, 15(2)555--57, 2005.
H. Chen, H. Xu, R. Jiang, et al. Lower-level duality based reformulation and majorization minimization algo- rithm for hyperparameter optimization. In Proceedings of the International Conference on Artificial Intelli- gence and Statistics, pages 784-792. PMLR, 2024.
L. Chen, J. Xu, and J. Zhang. Bilevel optimization without lower-level strong convexity from the hyper- objective perspective. arXiv preprint arXiv:2301.0071: 2023.
Damek Davis Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization,, 29( (1):2077-2,9 2019.
Stephan Dempe, Nguyen Dinh, Joydeep Dutta, and Tanushree Pandit. Simple bilevel programming and exten- sions. Mathematical Programming, 188:227 008:227-253,,, 2021.
Lior Doron and Shimrit Shtemn. Methodology and first-order algorithms for solving nonsmooth and strongly convex bilevel optimization problems. Mathematical Programming. 201:521-554 2023.
Dmitriy Drusvyatskiy and Adrian Lewis. Error bounds, quadratic growth, and lincar convergence of proximal methods. Mathematics of operations research, 43(3):919-948, 2018a.
Dmitriy Drusvyatskiy and Adrian S Lewis. Error bounds, quadratic growth, and linear convergence of proximal methods. Mathematics of Operations Rexearch, 43(3):919 (1-3)99999999 9488 2018b.
John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra. Efficient projections onto the 1-ball learning in high dimensions. Proceedings of the 25th international conference on Machine learning. pages 272-279, 2008
Joydeep Dutta and Tanushree Pandit. Algorithms for simple bilevel programming. Bilevel Optimization: Ad- vances and Next Challenges, pages 253-291, 2020. 2020.

---

Luca Franceschi, Paolo Frasconi. Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel program- ming for hyperparameter optimization and meta-learning. In International conference machine learning. pages 1568-1577. PMLR, 2018.
Michael Friedlander and Paul Tseng. Exact regularization convex programs. SIAM Journal on Optimiza- tion, (1(4):332--1355) 2008.
Khanh-Hung Giang-Trame Nam Ho-Nguyen, and Dabeen Lec. Projection- free methods for solving convex bilevel optimization problems. arXiv preprint arXiv:2311.09738, 2023.
Chengyue Gong, Xingchao Liu, and Qiang Liu. Bi-ohjective trade-off with dynamic barrier gradient descent. In International Conference on Neural Information Processing Systems, pages 29630-29642, 2021.
Elias S Helou and Lucas EA Simões. e-subgradient algorithms for bilevel convex optimization. Inverse Prob- lems, 3305)005000,,, 2017.
F. Huang. On momentum--asse gradient methods for bilevel optimization with nonconvex lower-level. arXiv preprint arXiv:2303. 03944, 2023.
Ruichen Jiang, Nazanin Abolfazli, Aryan Mokhtari, and Erfan Yazdandoost Hamedani. A conditional gradient- based method for simple bilevel optimization with convex lower-level problem. In International Conference on Artificial Intelligence and Statistics, pages (0305-103233 PMLR, 2023.
Rujun Jiang and Xudong Li. Hölderian error bounds and kurdyka-tojasiewicz inequality for the trust region subproblem. Mathematics of Operations Research, 4744):3055-3050, 2022.
Harshal D. Kaushik and Farzad Yousefian. A method with convergence rates for optimization problems with variational inequality constraints. SIAM Journal Optimization, 3163)2171-22198 2021.
Matthias Kissel, Martin Gottwald, and Klaus Diepold. Neural network training with safe regularization in null space of batch activations. In Artificial Neural Networks and Machine Couring-ICANN 2020: 29th International Conference on Artificial Neural Networks, Bratislava, Slovakia, September 15-18, 2020, Proceedings, Part II 29, pages 217-228. Springer. 2020.
Puya Latafat, Andreas Themelis, Silvia Villa, and Panagiotis Patrinos. Adabim: An adaptive proximal gradient method for structured convex bilevel optimization. arXiv preprint arXiv:2305.0355 2023.
Jingwei Liang, Tao Luo, and Carola-Bibian Schonlich. Improving fast iterative shrinkage-thressolldng algo- rithm: Faster, smarter, and greedier. SIAM Journal Scientific Computing, 44(3)A1069-AA 1091, 2022.
Qihang Lin and Lin Xiao. An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization. International Conference on Machine Learning, pages 73-81. PMLR, 2014.
Zhi- qui-Quan Luo. Jong-Shi Shi Pang, Daniel Ralph, and Shi-Quar Quan Wu. Exact penalization and stationarity conditions of mathematical programs with equilibrium constraints. Mathematical Programming, 75(1):19-76, 1996.
Yura Malitsky. Chambolle-Pock and Tsengs methods: relationship and extension to the bilevel optimization.
arXiv preprint arXiv: 2017.
Roey Merchav and Shoham Sabach. Convex bi-level optimization problems with nonsmooth outer objective function. SIAM Journal Optimization, 33(4):3114-314 2023.
Hong Mingyi, Wai Hoi-To, Wang Zhaoran, and Zhuoran Yang. A two-timescale framework for bilevel opti-
mization: Complexity analysis and application actor-critie. arXiv preprint arXiv:2007.05170, 2020.
Arkadij Semenović Nemirovsky and David Borisovich Yudin. Problem complexity and method efficiency optimization. Wiley, 1983.
Yurii Nesterov. Gradient methods for minimizing composite functions. Mathematical programming, 140(1): 125-161, 2013.
Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
Jong Shi Pang. Error bounds in mathematical programming. Mathematical Programming, 79(1-3):999332. 1997.
Nelly Pustelnik and Laurent Condat. Proximity operator of sum of functions; application to depth map estimation. IEFE Signal Processing Letters, 18712118 2017.
12

---

Aravind Rajeswaran. Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. Advances neural information processing systems, 32, 2019.
Vincent Roulet and Alexandre d' d'Asprmmont. Sharpness, restart and acceleration. SIAM Journal on Optimiza- tion, 30(1):262 2899 2020.
Shoham Sabach and Shimrit Shtern. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):440-660, 2017.
Sepideh Samadi, Daniel Burhano, and Farzad Yousefian. Achieving optimal complexity guarantees for class of bilevel convex optimization problems. arXiv preprint arXiv:2310.12247, 2023.
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back-propagation for bilevel optimization. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1723- 1732. PMLR, 2019.
Han Shen and Tianyi Chen. On penalty-based bilevel gradient descent method. In Proceedings of the 40th International Conference on Machine Learning, volume 202 Proceedings of Machine Learning Research, pages 30992-31015. PMLR, 23-29 Jul 2023.
Lingqing Shen, Nam Ho-Nguyen, Fatma Kulane-Karzan Karzan. online convex optimization based framework for convex bilevel optimization. Mathematical Programming, 198(2):151-11582, 2023.
Naum Zuselevich Shor. Minimization methods for non-differentiable functions, volume Springer Science Business Media, 2012.
Mikhail Solodov. explicit descent method for bilevel convex optimization. Journal of Convex Analysis, 14 (2):227-237, 2007.
D. Sow, K. Ji, 7. Guan, and et al. primal-dual approach to bilevel optimization with multiple inner minima. arXiv preprint arXiv:2203.01 123, 2022.
Marcin Studniarski and Doug Ward. Weak sharp minima: characterizations sufficient conditions. SIAM Journal on Control and Optimization, 38(1):219-236, 1999.
Andre Nikolaevich Tikhonov and V. I. A. Arsenin. Solutions of ill-posed problems. Wiley, 1977.
Paul Tseng. On accelerated proximal gradient methods for convex-concave optimization. unpublished manuscript, 2008
Jiali Wang, He Chen, Rujun Jiang, Xudong Li, and Zihao Li. Fast algorithms for stackelberg prediction game with least squares loss. International Conference on Machine Learning, pages 10708-10716. PMLR, 2021.
Jiali Wang, Wen Huang, Rujun Jiang, Xudong Li, Alex Wang. Solving stackelberg prediction game with least squares loss via spherically constrained least squares reformulation. In International Conference on Machine Learning, pages 22665-22679. PMIR, 2022.
Blake E Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. Advances in neural information processing systems, 29, 2016.
Yangyang Xu. First-order methods for problems with o (1) functional constraints can have almost the same convergence rate as for unconstrained problems. SIAM Journal on Optimization, 32(3):1759-1799 2022.
Yao-Liang Yu. On decomposing the proximal map. Advances in neural information processing systems, 26, 2013.
Jinshan Zeng, Tim Tiz-Kit Lau, Shaobo Lin, and Yuan Yao. Global convergence of block coordinate descent in deep learning. In International conference machine learning, pages 7313-7323, PMLR, 2019.
Zirui Zhou and Anthony Man-Cho So. A unified approach to error bounds for structured convex optimization problems. Mathematical Progranmingg 165:689-728, 2017.
13

---

A Motivating examples
Many machine learning applications involve primary objective G, which usually represents the training loss, and a secondary objective F. which can be regularization such problems is optimize G fully and then use select the optimal solutions from the ones obtained for G. This is called lexicographic optimization [Kissl 2020, Gong el all M02T] Two classes of lexicographic optimization problems are the regularized problem, also known as the ill- ill-posed optimization problem [Ammn and Yousehan RDT Diang et al, RO and the over- parameterized regression [Miang ar, (023), where the upper-level objectives are the regularization terms loss functions, and the lower-level objectives are the loss functions and the constraint terms. We present some examples of these classes of problems as follows.
auxiliary loss. A common approach for
Example A.1 (Linear Inverse Problems). Linear inverse problems aim to reconstruct vector x E .R"" from measurements E 1 that satisfy b Ax + pe, where : It" + I a linear mapping. E E 1 unknown noise, and > 0 magmitude. Various optimization techniques can address these problems. We focus on the bilevel formulation, widely adopted in the literature [Beck and Sabach, 2014), Sahach and Shtern, 20E, Dempe et all 202I, Latatat et all, 2023, Merchav and Sabach, 2023).
The lower-level objective in the bilevel formulation is given by
1 | - b|2 + Ix(x),
G(x)
2m
where [x(x) is the indicator function of set that satifics Ic (x) if x E C, and (x)x) +00 x Φ C. The set
closed, convex set that can be chosen as C = R". C = (x E R" x 2 0). or C == (x E R" ||x|| - 0} for some 0 >> O.
This problem may have multiple minimizer solutions. Hence, a reasonable option is to consider the minimal norm solution problem, i.e. find the optimal solution with the smallest Euclidean norm [[eck and Sabach 201 Sabach and Shitert (2017, Latatat all [203]]
F(x)=
|x12.
We need to solve the simple bilevel optimization problem:
|x| s.t. x E arg min XER" 2
min
zek 2mn ||
b1]2 + (z)
Example A.2 (Sparse Solution of Linear Inverse Problems). Consider the same setting as in Example A. but with the additional goal of finding sparse solution among all the minimizers of the linear inverse problem (W). This can simplify the model and improve computational efficiency. To achieve sparsity, we can use any function that encourages it. One such function is the well-known elastic net regularization [Eriedlander and Tseng 2008, Amin and Yousefian, 201%, Merchav and Sabach, R023),, which is defined as
F(x) ||>|] 7 |xx|2
where T > regulates the trade-off between & and & norms.
This example corresponds to our second experiment in Scction
Example A.3 (Logistic Regression Problem). The logistic regression problem aims to map the feature vectors a: to the target labels b; A standard machine learning technique for this problem is to minimize the logistic loss function over the given dataset [Amini and Yousetian, 201% Gong et all, 20211 [hang et all, 21223 Latatal all 2023, Merchav and Sabachi, 2023). We assume that the dataset consists of feature matrix A E R and a label vector b E R. with by { (-1,1) for each The logistic loss function is defined
1 m
91 (x)
Σ log(1 + exx(-aa xb.).)
Over-fitting is common issue when the number of features is large compared the number of instances regularize the logistic objective function with a specific function or constraint [lang et all Mize Mcrchay and and Sabach, 2022). For instance, we can use gx()) = lx(x), where (x(x) is the
m. A possible approach
indicator of the set C {x E B |x| S 0). as in Example A
This problem may also have multiple optimal solutions. Hence, a natural extension is to consider the minimal norm solution problem [Gong et all 2021, [hang et al) 2023, Latalat et all 2023), as in Example A. This requires solving the following problem:
m log(1 + exp(-a? 2b:)) + (z)
min x 2
|x|²
s.t. x E arg min ZER"
14

---

When choosing C' = [x E R²: ||x||] & 0} for some 0 > 0, it corresponds to our first experiment in Section
Example A.4 (Over-paramelerizeed Regression Problem). The linear regression problem aims find param- eter vector x R that minimizes the training loss &u (x) over the training dataset Du. Without explicit regularization, the over pwrrpparametrrize regression problem has multiple minima. However, these minima may have different generalization performance. Therefore, we introduce a secondary objective, such as the valida- tion loss over validation set Dval, to select one of the global minima of the training loss. This results in the following bilevel problem:
min F(x) := (xal(x) s.t. E arg min G(z) := (zz(z). XER"
*ER
For instance, we can consider the sparse linear regression problem, where the lower-level objective consists of the training error and regularization term, namely, G(x) = A1l bull? lx(x). Here, (x( denotes the indicator of convex set, as in Example AZ The upper-level objective is the validation error, i.e. F(x) = 1 ||lAvai beall?. The linear regression problem over-parameterized when the number of features n is larger than the number of data instances in the training set.
B Comparison between simple bilevel optimization methods
Table 1: Summary of simple bilevel optimization algorithms. The abbreviations "SC," "C,". "diff", "comp". "WS" and "C3" represent "strongly convex," "convex,", "differentiable", "composite", "weak sharpness" and "Convex objective with Convex Compact constraints," respectively. The ab- breviation a-HEB refers to Hölderian error bound with exponent parameter a. We only include the gradients Lipschitz constant in the complexity result when its relation to the complexity is clear; otherwise, we omit it. Notation Ir is the upper bound of subdifferentials of F, I., and Tyg. are the Lipschitz constants of fi and V 91, respectively.
Methods
Objective 1
Upper-level
Lower-level
Objective
[ep, rop-mil
Solution
Upper
Converpence
lavel
MNG Deck and Satoon [ips]
Smooohh
Asymptotic
Kg)
BIG-SAM (5ahaca and Shirm MIT
SC, smowth
C. comp
Mite:
Asymplotic
IR-1G Ammm Semmam UI
SC
C3, Finite
Asymptotic
J.e (0,0.5)
[R: CG (ming Tin el
UizA
C, soomth
C3 smooch
max L/x 1//
(0.1).
Tseng' i method [Manay bam
Comp
C, comp
[isg]
Asymptotic
Oflice
ITALEX Emoon
comp
comp
[6.1"]
+IRG (kmmml and Yorncha D124
1ip
C, Lip
(rrsta)
o max| 1/
1//g & (0.0.5)
CG-BIO Jaan et mr UIMG
C. smooth
C3, smooth
(cr.4g)
O (mmax (L /sp. /kah)
comp
1/
(0.5.))
J-SC. comp
C, comp
(erita)
0 max) buciie
(0.5.)
R.APM [stmanee am IAT
stoooh
C, WS
(4.4)
VI7c
Online Framework Sisiee 1 boxg
CiIip
Lip
2 juns (173,, 1745)
comp
C. comp, o-HBB
(5.1g%))
Our method
p-SC, comp
C. coEp
ky
11000
nonsmooth, Lip
nonsmooth. Lip. HEB
1021350
C
Examples of functions satisfying the Hölderian error bound
We present several examples of functions that satisly the Hölderian error bound Assumption 2 and their corresponding exponent parameter a in Table D. We also provide some clarifications for Table 2 below. The abbreviations "Q E gm and "Q > 0" stand for "Q is symmetric matrix of order n and a positive definite matrix, respectively. We refer the reader to [Pang [1197]], Bolte et all [2017]] Zhou and SG [2017] Diang and Li [P022]] Doron and Shieri [[OAK] and the references therein for more examples of functions that satisfy Hölderian error bound Assumption 2 Furthermore, it is noteworthy that numerous applications in neural networks, such as deep neural networks (DNNs), also comply with this assumption, as discussed in Bolle aLll
20 [] Zeng et all [0]]]
AAcorriing to Table 2 of Doron and Shiem [023)) the parameter a can take values of either or 2. Partic- ularly, when = 1, we have p = 1; when = 2, we have p 2/T.
15

---

Table 2: Summary of some functions satisfying Hölderian error bound with corresponding expo- nents.
G(x)
Remarks
Name
max lE [m] (a,, x] b,t
a, E R (m].
piece-wise maximum
xx
(x x1) TQ(x xo)
Q 9" 0, R" Xg R" 2
Q-norm
x xallp
2y-norm
|| 1 + =|
7> 0 E Rmxn 6 1
Elastic net
or 2
Ax bll?
Least squares
mm
log(1 exp( cxp(-a/xx)))
a R mm]. R A R
Logistic loss
n(x) / |
convex,
Strongly-convex
D Supplementary results
D.1 Adaptive version of PB-APG method with strong convexity assumption
Algorithm 4 Adaptive PB-APG-s- method (aPB-APG-S0
Input: X-1 1
X R", 7a 71 > Lf. Log V > 1, ED 0.
2: for k 2 0 do
3: ox(x)
(x) (x)
4: (x) = fx(x) + (x)
5: Invoke X₁ PB-APG-sc( Ok, Vk μ. Ls Lyg Xx 11:-11c0 (k)
6: Ek++1 Lek
7: 7k+1 1/7k
8:
end for
Similar to Algorithm D, we have the following convergence results of Algorithm g
Theorem D.I. Suppose that Assumptions
and hold. Let 6g 0 be given.
When > sete p0-1,N N (pL - //))///++++++ and 1i pL
1)--1a- h/ "-
When a = setv N [log, (ple//o01+ and Vi = pLp.
Then, for any k 2 N, Algorithm Q generates an ( (rack -ompuu-gg -optimal solution of problem (E) after most K iterations, where K satisfies
2ng
K k=O
(V
Ln log
T eD
u Lgg log
+ ma 1,3-1) co
The proof is similar to the proof of Theorem B in Appendix
EK So we omit it here.
E Proofs of main results
this section, we propose the proofs of main convergence results in this paper.
E.1 Proof of Lemma
Proof. Since Xop closed and convex BBeck and Sabaer [.E the projection of any 18" onto Xap. denoted x. exists and is unique. Furthermore. holds that dist(x, Xxpp) Then, by Assumption we have
||x - x||.
F(x) F(X) N -x- x)
+Ill||| X|| 2
1x
x11, AA OF()).
(10)
16

---

Choosing ppli(ec 1)"-1)"""" 2 it follows that
F(x) F(x) +>p((x
[p |x x1| + 7" p(x)
-1=| || - x|| + 3 ||x - x||"
P
(11)
1r + y z
min #20
where (a) follows from the Hölderian error bound assumption of p(x), and (b) is from the fact that y
-lpz + z" attains its minimum at z" pf
Since E Xop is feasible for problem (E), we have F(X) 2 F". This along with (II) indicates
F(x) + pp(x) F F(x) + Y p(x) F(x) -E, Vx Rd and y 2 7"
(12)
Let x" an optimal solution (EE) so that F(x") F In addition, since Xoot. we have p(x')
Combine these results with (I22), we have
F(x") +p(x'))>>>+>>>>)))
F(x) + (p(x))+++)))+)))))>>))) + vx Rd and 2
(13)
This demonstrates that an optimal solution of (B) am e-optimal solution for
E.2 Proof of Lemma 2
Proof. The proof is motivated by Theorem 1 in Luo ct (1966] Denote x', xx as optimal solutions of problem (D) and
respectively.
For any R", let & be the projection of onto Xap. Then is feasible solution of (E) and F(x) 2 F(x")
holds, Then we have
F(x) + xp(x)=
= F(x) + F(x) F(x) + xx(x
2 F(x") + F(x) - F(x) + >p(x)
(4)
2 F(x") 1111x - + 211 x
(14)
F(x") ) + 12 - 11)]lx ||| x||
p
F(x") F(x") ) >p(xx))))
where (a) follows from (IT) and Hölderian error bound assumption p(x), and (b) follows from y 2 plp.
Therefore, we conclude that x" is an optimal solution of (P-).
For the converse part, let x be the projection of x., onto Xam- Then x,, is a feasible solution of (E). Therefore, it holds that F(x.)= 2 F(x"), Similarly, we have
F(x") F(x') + ?p(x")
2 F(x,) + xx(x))
F(x²) F(x') F(x") + (x(x))
2 F(x") )+ + F(X)) - F(X)) + xx((x)
(15)
$ F(x") - -,1|x - - + ||x; xX,1
F(x') + (2 -r)ll>; x;1|
F(x"),
where the inequality (c) follows from (II) and the Hölderian error bound assumption of p(x).
Therefore, all inequalities in (15)) become equalities. We deduce that ||x;; X; = 0f > pl implying that x., in Xoq,, ie., p(x;) 0. Furthermore, the first inequality of (IS) becomes equality, we obtain
F(x") F(X,) Tx(x)) = F(X.).
Therefore, x is also optimal solution of (E)
17

---

E.3
Proof of Theorem L5
Proef. Denote x", x as optimal solutions of problem (H) and P respectively.
Case of 1. Since x is an e-optimal solution of
have
F(X.) + >xp(x)))) S F(x) (P(x) + e, Vx E R".
(16)
Note that the arguments in the proof of Lemma MX still hold. Substituting x" into ((EG) and utilizing p(x") we have
F(R.) + -x((x) & F(x") + F(x') ) + p(x' + S F(X)) 7 7'x(x;) + 2e,
where the last inequality follows from setting x = x; in
Then, it holds that
2x
2
p(3;) - 7 - 7"
(17)
By setting x" in (TG). we have
F(X2)) F(x") S <l(xx)) - -(&{.) +
Using the fact that p(x") = 0 ((E)), have
f(*;) F Fxx") S.
(18)
Combing (LE) with (T). we conclude that XC; is (e, -optimall solution of (e)
Case of a 1. Since x; is an e-optimal solution of (T.). we have
F(x.) + Tx([) - F(x,) + (p(x.) +..
(19)
On the one hand, as 7y =-" + 11 - 1-8 > 7- by Lemma L.l. x is an optimal solution of (E). On the other hand, since 7 2 7 accordinn to Lemma 2. x is also an optimal solution of (P:) Therefore,
p(x") = 0 and p(x;) = 0, it holds that
F(x") F(X7) + 7x(2))
S F(xt)) + >x(xx; +
F(x.)) + +x'((x))) +
(20)
F(x") + +-'p(x") +
(X,) + +7 +>"p("'' p(x)) +c,
where the first inequality follows from the fact that x" is an optimal solution of (P-) ). and the last inequality follows from the optimality of x" to (F-) when 7 2 7"
The second inequality of (2I)) and p({ç)) 2 0 imply that
F( S F(x),) + vp(x,) + e F(x") + (x(x')++++++)))))))) + tes F(x")x)))))) +e.
That is, it holds that
F(XC) F(x") +
(21)
In addition, from (2U), we have F(X,) + xx(x,) S F(X2,) + x(x;) + e, which implics that p(x)) 7-7" 12-25 = 8
(22)
This result along with (21) demonstrate that x;; is an (c, 1 ( --optimllll solution of (B).
E,4
Proof of Theorem PAF
Proof. Let &,, be the projection of x;; on Xop, we have ||,;; x;,1 = dist(X;,. Xoxe).
By Assumption Ma the following inequality holds.
|| - "11 S pp(xC) S P ||ز X S (p)=
(23)
where (a) follows from By Assumption D we have
(1 when a > or from when & = 1.
-| - x;,1 2 -1p (NI=²0) 1t
- F(X)) F(x))
where the first inequality follows from F(X)) F and E E Xop.
18

---

E,5 Proof of Theorem L
Proef. For any dom((F, let x be the projection of x onto Xet, where the existence and uniqueness of follows from that Xopt is closed and convex. Since F is I-Lipschitz continuous, similar (IL), have
F(x) F(x) 2 - x||, Ag @=(x).
(24)
Therefore, all the requirements of (ITI) equations (II), (EB) and (LLS) can replaced by (2E)). This implies
that Lemmas 2RS and [ also hold for the global solutions of problems (E) and (P-) when F is non-convex. Then, the final result follows a similar pattern to Theorem 2.5. Here we omit it.
E.6 Proof of Theorem
Proof. Let x be the projection of x,, onto Xap. and X cx; + c)xx with c min lix; xg] }.
which implies that s;, E B(x,,, r). Then, we have
F(x,) + (x(x v F(R)) + >D(x;) F(R)) + ((pp(xx)) + (1- c)p({x)) = F(2;) + vcp(x.), (25)
where inequality (1) follows from the convexity of p(x).
Inequality (25) demonstrates that
7(1 ())( & F(x.) - F(x,) - 1| x = 1(1 - |x x;1 S 1(1 ()p(xx)))
where the second incquality follows from the I-Lipschitz continuity of F on B(x;, r). Therefore, it holds that
xp(x²) s U(p((x;))
(26)
Case of > 1. By (LG), have p(x)) ( o which demonstrates that p(x.) I c if 7 22 pt )a
Then, for any x, B(x,,.) that also satisfies p(x,) S p(xx,) S e, have F(x1)) + >p(x;) - F(x,) ) + >p((x))
(27)
which implies that F(xx)) - Fxx,)) (p(xx., p(xx)) The desired result follows.
Case of a = 1. By (26)) we have p(x;) if > pl. Therefore, for any x, E B(x;, r) n Xops. by the definition of x., holds that
F(x,) + xp(xx,) < F(x,) + 7p((x>)
which demonstrates that F(x²)) & F(x,). The desired result follows.
E.7
Proof of Theorem
Proof.
From
Beck
Theorem 10.34). the objective value after K iterations can be bounded by 2L [xo x
Φ (xx) $;
(K 1)2
where L., = + Lyg.
Combining this with our stopping criterion, we find that after iterations,
Φ (xx) & Sc
This indicates that we obtain an e-optimal solution to problem P.). The value of K satisfies:
K 2(L,, + *bon) R-
Specifically, we analyze the value of K in various scenarios in the form of O(-).
Case of > 1. In this case, 7 7" + 21-e--= 1 comprises two components: 7" and 2 Therefore, it is natural to discuss which these two components plays the dominant role the complexity results. First, we write K in the form:
K = 2(I + (plp(a ij--la- -all--aa------ agl-a + 21-
R 1.
19

---

If B < a. the dominating term in 7 yis""" =pl - 1)0-1a 2-
Then, the number of iterations
is
K == 0 Li - lpel lppl--oog Lug
(v
L
If 3 have y (pla - -1)a-2a-a 2) 186t-a. Then, the number of iterations is
k=
-
Ls + -ppe-ana Loi -0
=0(
Ln
Lg
c
If 3 a, the dominating term in 7 is c Then, the number of iterations is
K- (V
Li + 21 2 Lug = =0 =0(v
L
Case of a = 1. In this case, = =y" -gee where y phr. Similarly, we explore which of these two elements plays more significant role.
If B 1, the dominating term in is y" Then, the number of iterations is
K 0 (v
T. plat
-
I.f
1p
=0
If we have 7 (0+ 1)lpct-a, Then the number iterations
(VZ L.
(p+ 1)1 = =o =0 Lo( 1F
==o
+
If 3 1, the dominating term in is 1 16.0-0 Then, the number of iterations is
K K-o x-O Ln + 1ffel- =0
(1
(v
Combining the above results, conclude that
in mmixto.8) Los (
Lii
K 0
E.8 Proof of Theorem +5
Proof. In this proof, we denote 4 as the optimal value of problem P when "R. and x as the output of PB-APG (Algorithm M1) the k-th iteration.
Case of 1. Suppose that N is the smallest nonnegative integer such that Yv rh plz 1)a-1a a a 1-a In this case, we have
7N you 2 pl 1)"
= 1-1 = plz - 1)0-1 α (1/1)
(28)
which is equivalent to
to a 2 plf (a 1)a-2 2-a
(29)
after at most N = [log,, (8-1a-100-10-04
From
(S))
1 iterations, (2X holds.
70
Since b = PB-APG(ON, VN, Tefis Tog KN-1,EN), we have
@x(xx) D5y SEN, ON 2 7N.
20

---

which shows that xx is an ex-optimal solution of P with 7 = From the proof in Theorem
(see inequalities (l (1S) Appendix 3, XN is also an (,
vp" (ToM -3g)
2:g
o-optimal
solution of problem
Furthermore, note that for any iteration 2 N, inequality (2 always holds, which means that the following statement holds for any l Z N:
4 (xx) 4 cR.
76
7k-
(30)
Let I& be the number of iterations of PB-APG required to satisfy (EU) at the k-th iteration of aPB- APG, Then, for any l: 2 N, the total number of iterations is
K To +... Ik-
From Beek 2014 Theorem 10.34), number of iterations in i-th inner loop satisfies:
T 2(L #L
|x:-1
x!1
where x is the optimal solution in i-th inner loop. Then we have that
2 Jchinn
K =
X - x;
61
2(L + 7hcLog)
R K 2(I + youttbgr k.
1=0
1
1
For simplicity, we can also use O(-) to show the value of K.
1/
7o
+ 7o
K
+0
cv
ch
Li 7a To
+ 7x Top
0
E0
EN
L/ Po
1 VI/++ V1/1 +...- v1/1*))
Ck
L1 JaLoo
Ck
Log Lon (o
6D
6D
Case of a 1. Suppose that after N updates, we have 2 plr.ie..
you 2 plp.
(31)
This demonstrates that after for 2 log,
(xx)) (5I) always holds.
Similar the case > the total iteration number
Lf + roLo
Li + raLor
K 0
Tif, + 7k Iug
0
Tig (o(p))
0
21

---

E.9 Proof of Theorem S
Before proving Theorem L.S. we need the following lemma that is modified from Theorem in Lin and Xtad B0ET, state in the subsequent lemma for completeness.
Lemma F.1. Suppose that Assumptions 2.A. B. 1.2 and B.A. hold. Let x be an optimal solution of problem
and suppose that there exists a constant R such that m Il I xx,I S R. Then, the sequence Xx generated by Algorithm B satisfy
T + I R²2 (222)((1 -.)
(xxx)) 2 (x,, -
(32)
Pruof. Denote L, = Ln + yog By Theorem 3.1 in Brck and Teboulle [2005]] we have
Ly
Φ (x) (x,) S 2
Ilyo xx,1?
(33)
Utilize Theorem 1 in and and Xıad 201)) we have
(xx) 4 (x,)
(x) (x,)) )
1 1| x111²) (1
1
2
V
La
Ilvo xłl1 + 1 x
1
11 V Izy
6
(34)
* byy + 1 n²² (1-V トリ
By Lemma DAL we now prepared prove Theorem
S.
Proof. By Lemma
the number iterations required to achieve an e-optimal solution problem is
k-o (V In log
Toy + 1² - o -0
(V
Ti log
26
Case of 1. In this case, y 7 + +2 where pl aaa-ta-aet-
If a, the dominating term in y is n", Then, the number of iterations is
K K=o (v Ln 1get-a log 1 1)= =0 Ln log _
La
12
+
log
1
If we have 7 = (pler 1ja-2a" 2) 17 t- Then, the number of iterations is
k=o (v Ln + ppet-aliun log 1 =0
(v
Li 1
1 Lo
1
log
+
log ea
P
If a, dominating term in 7 2 1-8 Then, the number iterations
K K=o
(1
Li 21 - Loo log )
= =0
(
L
log
1 +
1s Lo cl
log
1
1
Case of 1. When 1, can be written as 7 = 7" 2-0 where 7" phr.
If the dominating term in is y., Then, the number of iterations is
K 0 (1 T.r, plr Tug log ! 1)=o = (v L log
Lig log l
1
+
"
If 3 1, we have
(p+ 1) Then, the number of iterations is
K 0 (1
Ln Lo log 1 c
(v
L
1 +
l1 ca-l
1 log =
0
log
22

---

If 3 1. the dominating term in is 1 12ce-
Then, we have
(v L/ + 12 12cl- - Lu log c) 1)= o
!
(TT Tits log
log )
K ==
+ e
Combining the above results, conclude that
(11
Lis 1
1 - +
Ip
mmax(o,0) Logs log
k=
log
emaxia- a- 1-nxxa-113-11 1.3-13
t
E.10 Proof of Theorem 63
Proof. Denote by l/2 + 7d23- Define R
min (x,(x) and & K.j min
2x(xi) for all
g.best i=..... K
j K. claim the sequence generated by the subgradient method satisfies i=
KK N.best
t S 4 R² 2og
(35)
4 VK +
Specifically, from Lemma 8.24 in Beck [2011]], for all 0 S K, we have
1 R22 + ΣE =
$ K. n.best
$ 2
(36)
kmn! Tlk
Define [.] and [-] as rounding and rounding down, respoctively. Let = LX in (36), by the definition of &
step-size 77 VEFT we have
Φ S ly R +
+
K.j best
k+1
l R² + 2ogg2
(37)
2 Lk=14 $1
4 VK+2
VE+I
where the second inequality follows from that Σx KFI
1 11 -
1yds
S
2 log and
ΣK Ex-14)
K+1 14
ViT ds V
From the fact that "ee
9,best The desired result of (SS) follows.
K.j.
Then, inequality (BS) demonstrates that the number of iterations to obtain an e-optimal solution for problem
is
K K= 0 600('0 7992
Case of 1. have
- = 21 c and x- = plj,
- -
If B a, dominating term in 7 7" Then, the number iterations
1/2 19, 1-0 =
13
22
K k=0
f2
92
2a
If ß a, we have y = (p(a - 1y--1a-- 176"
Then, the number of iterations
1/2 + 17,55 11022
12
12 P
K ==0
c
2
If a, the dominating term in 7 21 1-8
Then, the number of iterations is
1/2 21
1- 3-31
2
22
K = 0
0
1/
+
f2 92
62
220
23

---

Case of 1, we have =-y" +1/22' c/- and 7" pl
If the dominating term in y is yy" Then, number of iterations
= 1/2 + +l )
P7
12
o
2
2
If 1. we have = (p 1)(Fc'-9. Then, the number of iterations
K = o (is + p
17
fo
92
If the dominating term in y is 19/2 c
Then, the number of iterations
K = 1/2 12 1/2 c
12
fa 92
e
20
Combining the above results, we conclude that
Pz 2
max m2a 288 12
K 0
emax 220
E.11 Proof of Theorem 3.10
Proof. Denote lyz P9 define *
min (x,)). From Theorem 8.31 in Beek [200]]] the ", i=0.....K
sequence generated by the subgradient method satisfics
21
P1s (K 1)"
This demonstrates that the number iterations to obtain an e-optimal solution for problem P
K= (112 + 7892 )2
14f2
Case of 1. have 7 7" 21,, 1- and pl% (a
aaa-1a-aet-
If ß < a, the dominating term in 7 "" Then, the number of iterations
K K=0
(11z + 17.2" ".."""927" "02)
)
-0 -0
12
+
12 12012
usge
If a, we have = (pla 1aa--a-a + 2) 13c--a Then, the number of iterations is
K K=
(112 (112+1/22 1722" 1222"~0922" 12
-0
17 Usge
132 23.
usee
If 8 > a, the dominating term in y is 21..e" 1-8
Then, the number of iterations is
K=O (142 + 21, 11-11p2)
=0 )
12 M15EE 29
12.18
+
P1.5
Case of a 1. we have y = 7- 10, 1-8 and 6" = pl
If 3 < 1, the dominating term in is y Then, the number of iterations is
K 0 (11z pl =0
13
12 12
1352

---

If 1, we have (p+ 1)1fe'-0 Then, the number of iterations is
K = o (11 ( (1a+t(aaam))))) )
1
L. 1
Ms2
M5ze
If the dominating term in 7 1/22t- Then, the number of iterations
K = (1/2 + 10 c0200 )
17
12
- =0
+
Combining the above results, we conclude that
m 1g
K = 0
f2
elnme (20 11:0-11000 1,25-11
Implementation details
In this section, we provide supplementary experiment settings and results. Specifically, in Appendix Ell we present the detailed experimental settings, and in Appendix EZ we provide the detailed experimental results. Additionally, in Appendix B+ and Fel conduct experiments with different values of penalty parameter solution accuracy e, respectively.
F.1
Experiment setting
All simulations implemented using MATLAB R2023a PC running Windows 11 with AMD (R) Ryzen (TM) R7-7840H CPU (3.80GHz) and 16GB RAM.
F1.1 Experiment setting Section
We conduct the first experiment using the ala.t data from LIBSVM datasets This data consists of 30, 956 instances, each with n 123 features. For this experiment, sample of 1, 000 instances is taken from the data, denoted as A. The corresponding labels for these instances are denoted as b, where each label b; is either 1, corresponding to the i-th instance
The Greedy FISTA algorithm [Liang et all 2020 is used as a benchmark to compute G To compute the proximal mapping of fx(x) (x) in problem i.e, projection onto 1-norm ball, utilize the method proposed in (Dich [0008] which performs exact projection (nn) expected time, where the dimen- sion of
the PB-APG and PR-APG-sc algorithms, we set the value of y = 105, we terminate the algorithms 10 For the aPB-APG and aPB-APG-sc algorithms, we set To = 25. v 20, 1 10, and 6a 10-6 The iterations of these two algorithms continue until é reaches 10 10-10 (meanwhile, 10a).
when x X
< 10 10-10
We compare our methods with MNG, BiG-SAM SAM, DBGD, a-IRG, CG-BiO, Bi-SG, and R-APM in this experi- ment. Specifically, for R-APM [Samadi a 2023), the regularization parameter is set 1) 1/7, reflecting the equivalence of the penalty formulation
Red with 1/7, as previously discussed.
We that the termination criterion X proposed in our algorithms since the parameters required for the latter are not easily measurahle. Nevertheless, this termination criterion is also widely used in the literature, as it corresponds to a gradient mapping [Bec 201 Nesterow, 20TK Davis and Drusvyatskry, 2013) Furthermore, Theorem 3.5 of Drusvyatskiy and Lewis also measures the distance to the optimal solution set.
x < 10-10 used in our experiments different from the
[ implies that | xx
F.1.2 Experiment setting of Section
In the second experiment, we address the problem of least squares regression using the YearPredictionne data from the UCI Machine Learning Repository This data consists of 515, 345 songs with release years ranging from 1992 to 2011. Each song has features, the corresponding release year used as the label.
htttp::/www..ct www.cceeeeeeeeeeeeooooo.c.. http://wwwww.aaat....ca..t////// http://wwww.........../oooo//a/a
https://archie..tt ics uci htt..////l//aaaatte//////eeelolt http:://cccioooooaaaaaaaasssssss
25

---

For this experiment, sample of m = 1.0 songs is taken from the data, and the feature matrix and release years vector are denoted and b, respectively.
Following Section 5.2 Merchay and Sabaci [2023]] apply the min-max scaling technique to normalize the feature matrix A. Additionally, we add an intercept term and 90 collinear features to A such that the resulting matrix A A becomes positive cemi-defintte, which implics that the feasible set Xage is not a singlcton.
We compare our methods with a-IRG, BiG-SAM, and Bi-SG this experiment. Specifically, for BiG-SAM [Sabach and Shtem (01T) we consider the accuracy parameter ó for the Morcau envelope with two values, namely 8 = 1 and 8 0.01.
To benchmark the performance, utilize the MATLAB function lsqminnorm compute G", Moreover, follow the parameter settings outlined in Section I.
F.2 Detailed results of experiments
To approximate the optimal value F", we use the MATLAB function fmincon to solve relaxed version of the
reformulations in equation (v ). In this relaxed version, replace the constraint in obtain approximation of the optimal value while allowing for a small deviation from the true optimal value G
(a with G(x) G where 10 10 This allows
We gather total number iterations for our methods, as well as lower- and upper-level objective values and the optimal gaps for all the methods, in Table Subsequently, we compare the optimal gaps of all methods, which are defined as G(x) - G and F(x) F for the lower- and upper-level optimal gaps, respectively.
Table 3: Methods comparison: lower- and upper-level objectives and optimal gaps
Logistic Regression Problem
Method
Total iterations
Lower-level value
Lower-level gap
Upper-level value
Upper-level gap
PB-APG
1470
3.2794c-01
1.7630c-08
4.9382c+00
-3.3998e-03
aPB-APG
1010
3.2794c-01
1.7630k--0
4.9382c+00
-3,3998--03
PB-APG-sc
2278
3.2794c-01
1.7630c-08
4.9382e+00
-3.3998c-03
aP--APG-sc
1046
3,2794c-01
1.7630c-08
4.9382c+00
-3,3998e-03
MNG
3.4540c-01
1.7459c-02
1.7469c+00
-3.1947c+00
BiG-SAM
3.3878c-01
1.0840e-02
2,2873e+00
-2.6543e+00
DBGD
5,2681c-01
1.9887e-01
8.8408c-02
-48532e+00
a-IRG
3.3765c-01
9.7121c-03
2.5401c+00
-2,4016c+00
CG-BiO
4.3040c-01
1.0246c-01
3.7684c-01
-455448c+00
Bi-SG
3 3.2806c-01
1.1530e-04
4.6873e+00
-2.5432e-01
R-APM
3.2794c-01
1.76445c-0
4.9382c+00
-3,4013e-03
Least Squares Regression Problem (
Method
Total iterations
Lower-level value
Lower-level gap
U Upper-level value
Upper-level gap
PB-APG
39314
7,3922c-03
6.0034e-07
4.7236c+00
-1,1888c-01
aPB-APG
40784
7.3922e-03
6.0030e-07
4.7236e+00
-1.1887e-01
PB-APG-sc
46446
7.3922c-03
6.0034c-07
4.7236c+00
-1.1888c-01
aPB-APG-SC
61777
7.3922c-03
6.0035c-07
4.7236c+00
-1.1888c-01
BiG-SAM (8 =8= 1)
7.5189c-03
1.2733e-04
3,5081c+00
-1.3344e+00
BiG-SAM (6 = 0.01)
7.3958e-03
4.2281e-06
5.8510e+01
5.3668e+01
a-IRG
1.622cc022
8.8328c-03
4.7745c-01
-436551c+00
Bi-SG
8.5782c-03
1.1866c-03
1,3832c+00
-3.4593c+00
Table reveals that for the logistic regression problem @ our PB-APG. aPB-APG, PB-APG-sC, and aPB-APG- exhibit almost identical function values for both objectives, surpassing other methods in terms of optimal upper-level objectives (measured by the numerical value the upper-lovel objective).
gaps for the lower- In the case of the least squares regression problem (8)) aPB-APG achieves the smallest optimal gaps for both objectives, followed by PB-APG and PB-APG-sc. These results demonstrate that our methods, despite yielding larger upper-level function values, generate solutions that are significantly closer to the optimal solution, as depicted in Figure Additionally. for the problem in (.), both aPB-APG and aPB-APG-sC require fewer iterations than PB-APG and PB-APG-sc, respectively. This can be attributed to the warm-stat start mechanism employed in aPB-APG and APB-APG-sC. Moreover, for the problem in (.) both aPB-APG and aPB-APG-sc require more iterations than PB-APG and PB-APG-sC. respectively. However, they exhibit staircase- shaped curves, which avoid the unwanted oscillations in PB-APG and PB-APG-sC, we have similar observation in Figure
F.3 Supplementary experiments for different penalty parameters
In this section, we investigate the impact of different values of penalty parameter on the experimental results of problems ( and ( We set 7 to be either 2 10s 5 10 for PB-APG and PB-APG-sc, and choose the
26

---

corresponding values 25 25 for aPB-APG and aPB-aP respectively. The remaining settings the same in Section B
We plot the values of the residuals of the lower-level objective ((xx) G* and the upper-level objective over time Figures and Additionally, also collect the total number of iterations, the lower- and upper-level objective values, and the optimal gaps of our methods Table for problems (5) and (Q) with different values of y.
600
600
Figure 3: LRP ( with 7 = 2 x 10 (left two subfigures) and 7 = x 10y (right two subfigures).
17
X
Figure 4: LSRP R with 2 x 10a (left two subfigures) and 7 5 x 10 (right two subfigures).
As Figures and show, our methods consistently outperform the other methods for both the lower- and upper- level objectives, irrespective of the penalty parameter r, since methods achieve lower optimal gaps and desired function values for the lower- and upper-level objectives. respectively. The only exception is problem (E) with
10 as the third subfigure of Figure shows, since we do not set the solution accuracy of BiG-SAM (8 = 0.01). it attains lower optimal gap than our PB-APG-sc and aPB-APG-SC for the lower-level objective. However, BiG-SAM (5 = 0.01) produces significantly worse upper-level objective values, which much larger than the objective values of methods.
Table Lower- and upper-level objectives and optimal gaps with different penalty parameters for problem (5))
x 10*
Method
Total iterations
Lower-level value
Lower-level gap
Upper-level value
Upper-level gap
PB-APG
883
3.2794c-01
4.3569c-017
4.9243c+00
-1.7362e-02
aPB-APG
967
3.2794e-01
4.3569e-07
4.9243e+00
-1.7362e-02
PB-APG-sc
1123
3.2794e-01
4.3569c-07
4.9243e400 4.9243e400
-1.7362c-02
PP--AGG-sc
879
3.2794c-01
4.3569c-07
-1.7362e-02
7
10"
Method
Total iterations
Lower-level value
Lower-level gap
Upper-level value
Upper-level gap
PB-APG
1623
3.2794c-01
7.0685e-10
4,9410c+00
-5.7820e-M4
aPB-APG
976
3.2794e-01
7.0685e-10
4.9410c+00
-5.7820e-04
PB-APG-sc 4848
3.2794e-01
7.0684e-10
4.9410e+00
-5.7820e-04
aPB-APG-sc
1018
3.2794c-01
7.0687c-10
4.9410c+00
-5.7821c-04
Tables EL L and N reveal that the number of iterations for methods increases penalty parameter ty in- creases. However, worth noting the accuracy of the obtained solutions also increases, as indicated by the decreasing optimal gaps of the lower- and upper-level objectives. This observation confirms that the com- plexity results and solution accuracies of our methods are indeed dependent on the choice of penalty parameters, specifically, L.y, as demonstrated in corresponding Theorem + and other related theorems.
27

---

Table 5: Lower- and upper-level objectives and optimal gaps with different penalty parameters for problem (8)
7 2 10*
Method
Total iterations
Lower-level value
Lower-level gap
Upper-level value
Upper-level gap
PB-APG
I7I53
7.4052e-03
1.3619.-05
4,2843e+00
-5.5818e-01
aPB-APG
20877
7.4052e-03
1.3619c-05
4.2843e+00
-5-5818e-01
PB-APG-sc
27501
7.4052e-03
1.3619c-05
4.2843e+00 4.2843e+00
8c-01
aPB-APG-sc
40077
7.4052e-03
1.3619e-05
-5.5818e-01
x 10
Method
Total iterations
Lower-level value Lower-level gap
Upper-level value
Upper-level gap
PB-APG
85511
7.39I6e-03
2,4094c-008
4.8198c400
-2.2752e-02
aPB-APG
85502
7.3916e-03
2,4093e-088
4.8198c+00
-2.2752e-02
PB-APG-se
173731
7.3916e-03
2,407 lc-08
4.8198c+00
-2.2740e-02
aPB-APG-se
166324
7.3916e-03
2.4091c-08
4.8198c+00
-2.2751e-02
F.4
Supplementary experiments for different solution accuracies
this section, we investigate impact different solution accuracies on experimental results of problems ( and (E)). We set e to be either 10 or 10-? and terminate the algorithms for PB-APG and PB-APG-sc when [|x+11 - xx S For aPB-APG and aPB-APG-sc. choose the corresponding values as or 10 The remaining settings
soluttion
the same in Section HL
We also plot the values of the residuals of the lower-level objective G(xx) G and the upper-level objective over time Figures and Additionally, also collect the total number of iterations, the lower- and upper- level objective values, and the optimal gaps of our methods in Table for problems (5) and (6) with diffcrent solution accuracies.
075
Figure 5: LRP (5) with 10-4 (left two subfigures) and 10-7 (right two subfigures).
614
01
C0
105
Figure 6: LSRP R with c 10 10-4 (left two subfigures) and e 10 (right two subfigures).
From Figures B and & it is evident that in most cases, our methods outperform the other methods in terms of both the lower- and upper-level objectives. However, there is an exception in the case of the upper-level objective for problem (5) when = 10 As illustrated in the second subfigure in Figure R our methods exhibit larger function values for the upper-level objective compared to the other methods (except BiG-SAM 0.01)), despite still achieving smaller optimal gaps for the lower-level objective. This discrepancy actually indicates our methods have not yet achieved the desired accuracy when 10m and it is important note that ||x+11 X I S e not the termination criterion in our proposed algorithms, as explained in Appendix El Therefore, the larger optimality gaps for the upper-level objective in this case may be attributed to the termination criterion.
28

---

Table 6: Lower- and upper-level objectives and optimal gaps with different solution accuracies for
problem (S).
10
Method
Total iterations
Lower-level value
Lower-level gap
Upper-level value
Upper-level gap
PB-APG
124
3.2794e-01
2.8671e-07
4,9483e400
6.7024c-03
aPB-APG
148
3.2794c-01
2.3660e-07
4.9419c+00
2.9831c-04
PB-APG-sc
100
3.2794c-01
5.4674c-07
4.9287c+00
-1.2956c-02
aB--APG-sc
149
3.2794e-01
7.9015e-07
4.9302c+00
-1.1404e-02
10-7
Method
Total iterations
Lower-level value
Lower-level gap
Upper-level value
Upper-level gap
PB-APG
841
3.2794c-01
I.763Ic408
4,9382c400
-3.3999e-03
aPB-APG
551
3.2794c-01
1.7707c-418
4.9382c+00
-3.4075e-03
PB-APG-sc
225
3.2794e-01
1.7493c-08
4.9383e+00 4.9382c+00
-3.3691e-03 -3.3874e-03
aPB-APG-se
614
3.2794e-01
1.7507e-08
Table 7: Lower- and upper-level objectives and optimal gaps with different solution accuracies for problem (8)
Method
Total iterations
Lower-level value
Lower-level gap
Upper-level value
Upper-level gap
PB-APG
426
7.6950e-03
3.0342e-(M
6.0249c+011
5.5407e+01
aPB-APG
432
7.8018e-03
6e
4.8967e+01
4.4125c+01
PB-APG-sc
437
7.6456e-03
2.5400e-00 04
6.0196c+01
5.5354e+01
aB-AAG--sc
517
7.6143e-03
2.2274e-04
4.9292c+01
4.4449c+01
10-7
Method
Total iterations
Lower-level value
Lower-level gap
Upper-level value
Upper-level gap
PB-APG
13707
7.3922c-03
5.9756e-407
4.7279c400
-1.1460e=00
aPB-APG
7803
7.3923c-03
6.5025e407
4.7300c+00
-1.1248c-01
PB-APG-sc 12724
7.3922e-03
5.7840e-07
4.7354e+00
-1.0714e-01
PP--APG-sc
7429
7.3922e-03
6.3816c-07
4.7326e400
-1.0992e-01
Tables R and Ø demonstrate that the number of iterations for our methods also increases with the solution accuracy, while the optimal gaps of the lower- and upper-level objectives decrease correspondingly. This finding confirms that the number of iterations and the optimal gaps influenced by the solution accuracy, as illustrated the expressions for the number of iterations provided by Theorem B.3 and other related theorems.
29

---

NeurIPS Paper Checklist
1. Claims
Question: the main claims made abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Please refer to Abstract and Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions 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.
It is fine to include aspirational goals motivation long it is clear that these goals attained by the paper.
2.
Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Please refer to the assumptions adopted in this paper (e.g. Assumptions and (22), our study is based on these assumptions.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well well-specification. asymptotic approximations only holding locally). The authors should reflect how these as- sumptions might be violated in practice and what the implications would he.
The authors should reflect on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
scope the claims made, e.g., the approach was only tested
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images taken in low lighting. Or speech-te to text system might not be used reliably 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.
applicable, the authors should discuss possible limitations of their approach address prob-
lems of privacy and fairness.
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 It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and com- plete (and correct) proof?
Answer: [Yes]
Justification: Please refer to the theorems and the proofs of them in this paper, please refer to Ap- pendix (EL For example, Theorem B and its proof in Appendix F
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and refereeefeee
30

---

All assumptions should be clearly stated or referenced in 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 are encouraged to 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 supplemental material.
Theorems and Lemmas that the proof relies upon should be properly refereneed.
Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimen- tal results of the paper the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Please refer to Section g and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless whether code and data are provided or not.
the contribution is dataset and/or model, authors should describe steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducihility can accomplished in various ways. For ex- ample, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others replicate the model with the same dataset, provide access to the model. general. releasing code and data often one good way to accomplish this, but repro- ducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of a large language model), releasing of a model checkpoint, other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily reproduce that algorithm.
algorithm. the paper should make clear how
(b) If 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.. large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (c.g., with an open-source dataset or instructions for how to construct the datasct).
(d) We recognize that reproducibility may tricky some cases, which case authors are welcome to descrihe the particular way they provide for reproducibility. In the case of closed-source models, may be that access the model is limited in some way (c.g.. 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
paper provide open access to the data code, with sufficient instructions to faithfully reproduce the main experimental results, as described supplemental material?
Question:
Answer: [Yes]
Justification:
Please refer to Section B and Appendix and the supplemental material.
Guidelines:
The answer means that paper does not include experiments requiring code.
Please see the NeurTPS code and data submission guidelines
http://iippsccccpplbbppp
Siaddes/CodeSubmiesiioll
for more details.
While we encourage release of code and data, we understand that this might not possible, so No is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source henchmark).
The instructions should contain the exact command and environment needed to run to repro- duce the results. See the NeurIPS code and data submission guidelines (attps://nipe) for more details.
31

---

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 proposed method and baselines. If only a subset of experiments are reprodueible, they should state which ones are omitted from script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommeneed, but including URLs to data and code is permitted.
6. Experimental Setting/Detann Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please refer to Section AI and Appendix E. 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 necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate infor- mation about the statistical significance of the experiments?
Answer: [No]
Justification: The error bars are not applicable in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by eroor bars, confidence inter- vals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for caleulating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should 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 report I-sigma bars, but should state it. The authors should preferably state that they have 96% if hypothesis Normality of
report 2-simma error errors is not verified.
asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported 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
Question: For each experiment, does the paper provide sufficient information on the computer re- sources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification:
Please refer to Section H and Appendix E
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 of compute required for each of the individual experimen- tal runs as well as estimate the total compute.
32

---

The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into paper).
9. Code Of Ethics
Does research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer:
[Yes]
Justification: Please refer to Section ! and Appendix
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics,
the authors answer No, they should explain special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there a special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Docs the paper discuss both potential positive socictal impacts and negative socictal im- pacts of the work performed?
Answer: [NA]
Justification: There is no socictal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. dis- information, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy consid- crations, and security considerations.
The conference expects that many papers will be foundational research and not tied partic- ular applications, alone deployments. However, if there is direct path to any negative applications. the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology being used as 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 strate- gies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, im- proving the efficiency accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible relcase of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
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 restrictions to access the model or implementing safety filters.
Datasets that have heen scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors take this into account and make best faith effort.
33

---

12. Licenses for existing assets
Question: Are creators or original owners assels (e.g., code, data, models), used the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification; All the creators or original owners of assets are properly credited, and the license and terms of use explicitly mentioned and properly respected, please refer to Section E and Appendix
Guidelines:
existing assets. The authors should cite the original paper that produced the code package dataset.
The answer NA means that the paper does
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information. and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasete has curated licenses for some datasets. Their licensing guide can help determine the license a dataset.
For existing datasets that re-packaged. both the original license and the license of the derived asset (if it changed) should provided.
this information not available online, the authors encouraged reach out the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Please refer to the supplemental materials and the 'README.n' file.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codd/model as part of their submis-
sions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URI 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 to participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor rescarch with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved data collection, curation, other labor should be paid at least minimum wage in country data collector.
15. Institutional Review Board (TRB) Approvals or Equivalent for Research with Human Subjects
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 equiv- alent approval/review based the requirements of your country institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsoureing research with human subjects.
34

---

Guidelines:
answer means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country 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 loca- tions, and 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 applica- ble), such the institution conducting the review.
35


Reviews:
[{"review_id": "4t0poAketP", "reviewer": "Reviewer_WQ6y", "summary": "The authors propose algorithms to solve simple bilevel optimization problems of the form $\\min_x F(x)$ s.t. $x$ minimizes $G$, in the case where $F$ and $G$ are composite convex functions (i.e. some of 2 convex functions, one of which is also smooth), and assuming Lipschitz continuity of $F$ on the set of minimizers of $G$ and $G$ verifying a Holder error bound.\n\nThe proposed algorithms actually tackle a simple minimization problem, solving a relaxed version of the original problem that authors previously proved to be equivalent.", "questions": "- l.32: Why exclude the particular case where $X_{opt}$ is a singleton? This assumption is not used, therefore if we do not know in advance whether $X_{opt}$ is a singleton or not, one can still run this paper's algorithms, and guarantees will follow.\n- l.39: Even if what $G^*$ is seems clear, I think it is worth mentioning it before using it in line 35.\n- l.50: What about the upper problem?\n- l.50: « where b in (0, 0.5) ». The authors should be more specific here. Is it true for one specific b in the interval, depending on some parameters of the problem? Is it true for any (one proposed algorithm for each value of b)?\n- l.55: same remark\n- l.61: It would be more convenient if the authors keep a consistent way of displaying complexity.\n- l.68: What is g_2? Not defined yet at this stage. Moreover, note that the authors could not look at what happens in their case when $g_2=0$, as discussed in the \"weakness\" section.\n- l.101: What is f_2? Again not defined. And I think here that the authors meant $F$.\n- l.193: typo: « an » is repeated.\n- l.205: « while samadi … » If they consider the smooth case only, studying $\\alpha<2$ would be pointless because it is empty.\n- It would be great if authors could add explicit stopping criteria in their algorithms. Indeed, if $F^*$ and $G^*$ are not known, I guess we stop PB-APG after K iterations where K is set according to Th3.3. But then, PB-APG is not only a function of $\\phi$, $\\psi$, $L_{f_1}$, $L_{g_1}, x_0, \\epsilon$, but also $\\ell_F$, $\\alpha$ and $\\beta$. Which is important to actually understand the iterates of aPB-APG.", "limitations": "No limitation", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The link between the solutions of the original problem and the ones of the relaxed one is interesting and allows considering a simpler problem to tackle.", "weaknesses": "I am not very familiar with this specific piece of literature, so I cannot pretend to be sure of the novelty of the results.\nIn particular, in line 47, the authors say « Tikhonov regularization most related to $P_\\gamma$ », I do not see any difference between the two formulations. Can the authors develop on this? What is exactly done in Tikhonov's paper? And what is new here?\n\n\nMinors:\n- Usually, a proximal-based algorithm can be applied to the particular case where the non-smooth part of the problem is null, then the prox map is simply the identity map, and all the guarantees hold. But in this paper's setting, the non-smooth part is essential and cannot be considered null as a particular case. Indeed, otherwise, $G$ would be smooth, therefore upper bounded by a quadratic function, and $G$ is also assumed to grow faster than $||x-\\bar{x}||^{alpha}$ which cannot happen (if alpha<2).\n- A natural oracle assumption in the case where $F$ and $G$ contain each a non-smooth part would be to assume access to the proximal map associated with each. However, authors assume access to the proximal of all the linear combinations of the 2 non-smooth parts, and this choice seems to be only motivated by the reformulation of the problem. Doing this makes the derivation of PB-APG trivial once Thm 2.5. has been proven. But how could we tackle the same problem with the sole knowledge of the 2 prox maps independently?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for providing these valuable suggestions.\n# Weakness:\nSolodov [1] applied Tikhonov regularization (TR) [2] to solve simple bilevel optimization problems. Although the formulation of TR (l.47-48 in our paper) is similar to our method (l.36-37 in our paper), their origins and theories differ. Implementing TR requires the \"slow condition\" ($\\lim_{k\\to\\infty} \\sigma_k=0,\\sum_{k=0}^{\\infty}\\sigma_k=+\\infty$) [2], while we do not have this constraint; Our method provides non-asymptotic convergence rates, whereas TR only provides asymptotic results on either the upper-level or the lower-level problem (l.537 in Appendix B); We give an explanation on $\\gamma$ while they do not.\n- Minor weakness 1: Thank you for pointing this out. The $\\alpha$ in the error bound assumption is not arbitrary. Indeed, it is determined by the lower-level problem. When there exists some $\\alpha$ such that $\\text{dist}(x,X_{\\text{opt}})^\\alpha\\le\\rho p(x)$, the subsequent analysis is correct. For your example, suppose the function $G$ is $L$-smooth and $x^*$ is unique, we have $G(x)-G^*\\le \\frac{L}{2}\\\\|x-x^*\\\\|^2$. In this case, there is no contradiction if $G$ enjoys quadratic growth ($\\alpha=2$), i.e., there exists $\\mu>0$ such that $G(x)-G^*\\ge\\frac{\\mu}{2}\\\\|x-x^*\\\\|^2$. But in the L-smooth case, we cannot find some $\\alpha<2$ satisfying our assumption as you observed.\n- Minor weakness 2: You are right that Assumption 2.2 is strong in some scenarios. However, we should emphasize that it is more general than existing literature. In the simple bilevel problem, when using proximal mappings, people often only consider specific cases. E.g., [3] explores 'norm-like' upper functions, [4,5] require both $F$ and $G$ to be smooth, and [6] assumes that the upper-level objective is smooth and strongly convex. Additionally, although [7] assumes the nonsmooth terms of $F$ and $G$ are prox-friendly, respectively, their complexity, $O(\\max\\\\{1/\\epsilon_F^{\\frac{1}{1-a}},1/\\epsilon_G^{\\frac{1}{a}}\\\\})$ with $a\\in(0.5,1)$, is significantly worse than ours.\n\n   Furthermore, in practice, the sum of proximal mapping can be reduced to the proximal mapping of either $f_2$ or $g_2$. One example is when $f_2=\\beta g_2$, for some $\\beta>0$. E.g., when we want to minimize the validation loss and training loss of the LASSO problem simultaneously, the non-smooth terms of the upper- and lower-level objectives are identical, both of which are $\\ell_1$-norms. Then the proximal mapping of $f_2+\\gamma g_2$ is the same as the proximal mapping of $\\lambda\\ell_1$-norm, for some $\\lambda>0$, which is easy to obtain. \n\n   In addition, there also exist studies that investigate the sum of two proximal mappings ([8]: decompose it into the sum of individual proximal maps; [9]: compute the sum of proximal mappings efficiently). For example, when we are dealing with the regression problem, we often come into a situation where the nonsmooth part of the upper- and lower-level objectives are the indicator functions of an $\\ell_1$-norm ball and an $\\ell_2$-norm ball, respectively. The joint proximal mapping is the projection onto the intersection of these two balls. [10] shows how to compute it. Another case is that one level has a squared $\\ell_2$ norm regularizer and the other has a $\\ell_1$-norm regularizer. The sum of $\\lambda_1\\\\|x\\\\|_2^2+\\lambda_2\\\\|x\\\\|_1$ ($\\lambda_1,\\lambda_2>0$) is known as the elastic net, where the proximal mapping admits a closed form [8, Example 5].\n# Questions:\n- l.32: Yes, you are correct.  The algorithm presented in our paper can still be executed without knowing whether $ X_{\\text{opt}}$ is a singleton. We will fix this in our revision.\n- l.39: Sorry for the confusion. We will introduce $G^*$ before using it in our revised version.\n- l.50: [11] guarantees asymptotic convergence for the upper-level problem as shown in Appendix B in our paper. We will clarify this in our revision. For the parameter $b\\in(0,0.5)$, it does not depend on any parameter of the problem and is arbitrary in $(0,0.5)$, as stated in [11, Theorem 2]. Thank you for pointing out the ambiguity.\n- l.55: According to [12, Theorem 3.3 and Corollary 3.4], parameter $b$ is also arbitrary in $(0,0.5)$. It is not related to any parameter of functions but is instead related to the adaptive choice of step size $\\eta_k$ in Algorithm 2.1 and 3.1, where $\\eta_k=\\frac{\\eta_0}{(k+1)^b}$.\n- l.61 Thanks for your suggestion. In l.61, the convergence rate of '$O(\\epsilon^{-0.5})$' is equivalent to '$O(1/K^{2})$' if we use the total number of iterations $K$. We will modify it in our revised paper.\n- l.68: Sorry. We should define $g_2$ before its first use. Or the sentence \"when $F$ is strongly convex and $g_2 = 0$\" should be modified to \"when $F$ is strongly convex and $G$ is smooth\". Moreover, for $g_2=0$, please refer to Minor weakness 1.\n- l.101 and 193: Yes, we mean $F$ instead of $f_2$. Thanks for pointing out these typos.\n- l.205: If they consider the smooth case only, it is still possible for $g_1$ to satisfy the error bound with $\\alpha \\ge 2$; please refer to Minor weakness 1.\n- Thanks for your constructive suggestions to our algorithms. For the stopping criterion and $K$:\n    - In Algorithm 1, we can use the following stopping criterion: we stop the loop of l.3-4 if $\\frac{2(L_f+\\gamma L_g)R^2}{(k+1)^2} \\le\\epsilon$, where $R$ is such that $\\\\|x_0-x^*\\\\|\\le R$.\n    - In Thm3.3, the complete expression of $K$ is\n     $K=\\sqrt{\\frac{2(L_{f_1}+\\gamma L_{g_1})}{\\epsilon}}\\\\|x_0-x^*\\\\|-1$.\n    - In both the above criterion and $K$, parameter $\\gamma$ is chosen as:\n        - If $\\alpha>1$, $ \\gamma=\\rho l_F^{\\alpha}(\\alpha-1)^{\\alpha-1}\\alpha^{-\\alpha}\\epsilon^{1-\\alpha}+2l_F^{\\beta}\\epsilon^{1-\\beta}$;\n        - If $\\alpha=1$, $ \\gamma=\\rho l_F+l_F^{\\beta}\\epsilon ^{1-\\beta}$.\n    - In Algorithms 2,3,4, and the corresponding theorems, we can also provide criteria and the value of $K$. We will include these in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WhIlgZj8qs", "reviewer": "Reviewer_EYqV", "summary": "This work proposes a penalty based algorithm for simple bilevel optimization problems. The paper studies the relationship between the solutions of the penalized problem and the original bilevel problem. It extends the existing results on general bilevel optimization problem, which are established under PL condition, to the more generic Hölderian error bounds. The results are also extended to non-smooth upper and lower-level functions.", "questions": "1. The proposed method is for convex simple bilevel optimization problems, which might be restrictive. Can the author explain how the algorithm can be extended to the non-convex case?\n\n2. How does this algorithm compare to the penalty-based algorithms for general bilevel optimization problems? Are there any advantages demonstrated by this algorithm as compared to the generic ones?", "limitations": "no potential social impact", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) The paper is well written and easy to follow. \n2) The generalization of the existing results on PL condition to Hölderian error bound is interesting.\n3) The extended results on non-smooth objectives are good contributions.", "weaknesses": "1. Missing literature comparison/review:  The method proposed in this paper is a penalty-based method. There is a large body of work for penalty-based bilevel optimization methods. While in the related work section in the main text, there is no detailed review/comparison of the previous penalty-based bilevel optimization algorithms. It might be beneficial if the authors could discuss about the advantage of the proposed method compared with the existing ones.\n\n2. In the current state of the paper, the experiments seem to be purely synthetic and might be a little too toy.  Though the paper is majorly a theoretical one, it would benefit to have more practical experiments. It is also of great importance to find meaningful applications for the simple bilevel optimization problem.\n\n3. The method proposed in this work falls into the penalty-based methods. It might be interesting if the authors include a comparison with existing penalty-based bilevel optimization methods in, e.g.,", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Your expert insights are crucial to our research, and we greatly appreciate your guidance and suggestions.\n\n# Weaknesses 1:\nWe should point out that for simple bilevel optimization (SBO), there is no existing penalty method, although there exists a closed related method that is based on Tikhonov regularization (please refer to l.44-65 in our paper). Your point is correct for general bilevel optimization methods, as referenced in [1, 2, 3]. However, the general bilevel optimization model, with the form $\\min\\ F(x,y)$ $\\text{s.t.}$ $x \\in \\text{argmin}_x G(x,y)$ is different from SBO as the previous one is general nonconvex, while the latter is convex. Indeed, our penalty method is partially motivated by the penalty method for general bilevel optimization in [1], but our method uses many properties from the structure of SBO. Nonetheless, following your suggestion, we will include a comparison of our method and other existing methods on general bilevel penalty-based methods in our revised paper. \n\n# Weaknesses 2: \nThanks for the comment. In fact, these experiments are widely adopted in the SBO literature [10, 11, 12, 13]. It would be more persuasive to add more practical experiments. Following your suggestion, we conduct three more practical and complex simulations. The problem settings and experimental results are presented in the global 'Author Rebuttal'. Our experimental results show that our methods exhibit faster convergence rates, and achieve the smallest optimal gaps compared to the baseline methods for both upper- and lower-level objectives. This finding confirms our theoretical predictions in the context of this practical simulation. Moreover, the third experimental results (fair classification problem) also suggest that our methods may perform well even in non-convex cases.\n\n# Weaknesses 3: \nPlease refer to the answer to Weakness 1.\n\n# Question 1: \nWe actually considered the nonconvex case in l.140-142 of our main paper. However, due to the page limit, we put our discussions in Appendix D.1 of our paper (please refer to \"full\\_paper.pdf\" in the supplementary zip), we extend the penalization framework to the setting where $F$ is non-convex with the assumption of the Lipschitz (or local Lipschitz) continuous of $F$. \n\n# Question 2: \n- For a comparison with penalty-based methods for general bilevel optimization problems, please refer to 'Weaknesses 1'. Our method explores the structure of SBO and specifies the penalty parameter \\\\(\\gamma\\\\) to establish a relationship between the original SBO and the penalty formulation. \n\n- For general bilevel optimization problems, there have been recent results on convergent guarantees [1,14,15, 16,17]. Among those, the one that is the most related to ours is [1]. [1] investigates the case when the upper-level objective is nonconvex and gives convergence results under additional assumptions [1, Theorem 3 and 4].  However, as the general bilevel optimization problem is nonconvex, the algorithms in the literature often converge to weak stationary points, while our method for SBO converges to global optimal solution.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tsAUzYbU8J", "reviewer": "Reviewer_fmaf", "summary": "This paper deals with a simple bilevel (the lower-level problem has no dependence on the upper-level variable) optimization problem, where both the upper- and the lower-level objectives are convex and potentially non-smooth. To simplify the original bilevel problem the authors consider a penalty-based single-level reformulation and establish the relationship between the solutions of the two problems. An accelerated proximal gradient method (PB-APG)  is proposed to solve the penalty problem. Under a Holderian error bound condition and certain additional assumptions about the convexity and smoothness of the objectives, convergence of the PB-APG is shown to approximate global optimal solutions of the original bilevel problem.", "questions": "* Are Holderian error bounds satisfied in problems involving training of complex learning models, like neural networks.\n* In table 1 some of the algorithms depend on parameters $\\alpha$ and b, but the property to which these parameters correspond to is not specified. Please clarify this.", "limitations": "No negative societal impact", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* Differently from most of the works in literature, this paper deals with a problem in which the global solutions of the original bilevel problem are attainable. As a result, from a theoretical perspective, this is an interesting problem class. In addition, the proposed method is shown to (approximately) converge to these global solutions (of the original bilevel problem) and not to the solutions of some reformulation, as it is usually the case in other bilevel works.  \n* The authors provide a comprehensive and detailed summary of algorithms developed for solving simple bilevel optimization problems (in table 1).", "weaknesses": "* From an applications perspective, the problem class considered here does not seem very interesting. The bilevel problem is simple, the objectives are (strongly) convex, a Holderian error bound holds and the non-smooth term is required to be proximal-friendly. This significantly restricts the number and complexity of potential applications. Indeed, the applications presented in the appendix seem to revolve around (regularized) linear least-squares problems and simple learning models like logistic regression.\n* The proposed algorithm solves the reformulated minimization problem $P_{\\Phi}$ rather than the original bilevel. This minimization problem looks fairly standard, and it seems that known algorithms are applied directly for its solution. Thus, it appears that there is no significant novelty in terms of algorithm design.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable insights and thoughtful feedback regarding this paper.\n\n# Weakness 1:\nWe should emphasize that the problem class considered here receives a lot of interest in the literature. \n\n- Simplicity: Although bilevel problems may appear straightforward, they have numerous applications and have garnered significant attention in the optimization and machine learning communities. For example, dictionary learning [1], lexicographic optimization [2], and lifelong learning [3].\n\n- Convexity: Almost all existing papers on simple bilevel optimization (SBO) investigate cases where the objectives at both levels are convex (see Section 1.1 and Table 1 of our paper). Although some practical models do not meet this assumption, they often exhibit local convexity in the vicinity of their minimizers. Additionally, we have considered the nonconvex case (refer to l. 140-142 and Appendix D).\n\n- Holderian error bound (HEB): In the literature on SBO, the HEB is a commonly utilized assumption [4,5]. In Appendix C of our paper, we demonstrate that this assumption applies to many practical problems.\n\n- Prox-friendly property: The requirement for the non-smooth term to be prox-friendly is widely adopted in optimization and is satisfied in many machine learning applications, such as $\\ell_1$- and $\\ell_2$-norms. It is important to note that our assumption is more general than existing literature.\n\n   In the simple bilevel literature, when employing proximal mappings, researchers often consider the scenario where only one level contains a nonsmooth term (see, e.g., [3,4,5,6]). The proximal mapping of the sum $f_2 + \\gamma g_2$ is then reduced to the proximal mapping of either $f_2$ or $g_2$, which is a more easily satisfied condition.\n\n   A similar case occurs when $f_2 = \\beta g_2$ for some $\\beta > 0$. For instance, when minimizing both the validation loss and training loss of the LASSO problem simultaneously, the nonsmooth terms of the upper- and lower-level objectives are identical, both being $\\ell_1$-norms. In this situation, the proximal mapping of $f_2 + \\gamma g_2$ corresponds to the proximal mapping of a $\\lambda \\ell_1$-norm, for some $\\lambda > 0$, which is straightforward to compute.\n\n   Generally, the prox-friendly properties of $f_2 + \\gamma g_2$ are challenging to maintain. However, some studies have identified conditions under which the sum of two proximal mappings can be easily computed (e.g., [7, 8]). For example, in regression problems, it is common to encounter situations where the nonsmooth parts of the upper- and lower-level objectives are the indicator functions of an $\\ell_1$-norm ball and an $\\ell_2$-norm ball, respectively. The joint proximal mapping is then the projection onto the intersection of these two balls, and the method in [9] can be used to compute it. Another case involves one level having an $\\ell_2$-norm regularizer and the other having an $\\ell_1$-norm regularizer. The sum $\\lambda_1\\\\|x\\\\|\\_2^2 + \\lambda_2\\\\|x\\\\|\\_1$ ($\\lambda_1, \\lambda_2 > 0$) is known as the elastic net, for which the proximal mapping has a closed form [7, Example 5].\n\n- Applications: The applications in Appendix A are widely adopted in the literature [3,4,6,10]. Additionally, there are other applications of SBO, such as sparsity representation learning, fairness regularization, and lexicographic optimization [2]. Following your suggestion, we conducted three additional, more practical, and complex simulations. The problem settings and experimental results are detailed in the global 'Author Rebuttal'.\n\n# Weakness 2: \nUtilizing the penalization method to solve the original SBO problem is a novel approach. Among the various studies on SBO (refer to Section 1.1 and Appendix B of our paper), we are the first to employ the penalization method. While the Tikhonov regularization appears similar to our framework, its origins differ. Implementing Tikhonov regularization requires the ''slow condition'' ($\\lim_{k\\to\\infty} \\sigma_k = 0, \\sum_{k=0}^{\\infty}\\sigma_k=+\\infty$), necessitating iterative solutions for each $\\sigma_k$. In contrast, our method only requires solving a single optimization problem for a given $\\gamma$, whose theoretical significance is clear. Theoretically, we establish the relationship between the approximate solutions of the original bilevel problem and those of the reformulated single-level problem $P_{\\Phi}$ with a specific $\\gamma$. This constitutes the first theoretical result linking the original bilevel problem to the penalty problem $P_{\\Phi}$ with the optimal non-asymptotic complexity result.\n\nMoreover, since $\\gamma$ relies on many parameters, as demonstrated in Section 3.1.2 of our paper, determining $\\gamma$ can be challenging. To address this, we propose an adaptive version of PB-APG that updates $\\gamma$ dynamically and invokes PB-APG with varying $\\gamma$ and solution accuracies.\n\n# Question 1: \nTable 2 of our paper provides examples and references [4,5] about the HEB, which is widely used in learning models. For instance, the piecewise maximum function and least-squares loss function can be employed to train classification and regression tasks, respectively. For problems involving the complex learning models of neural networks, although these models are generally nonconvex, they may have local convex structures and also KL (or PL) conditions, which are equivalent to the HEB in the convex case [11]. Indeed, [12, Proposition 2] demonstrates that many applications in neural networks (e.g., DNNs) satisfy the KL inequality. We will explore this in our future work.\n\n# Question 2: \nWe apologize for omitting the definitions of some parameters in Table 1. For IR-CG [13], the range of $p$ is $p\\in(0,1)$. For our methods, the ranges of $\\alpha$ and $\\beta$ are $\\alpha \\geq 1$ and $\\beta > 0$, respectively. We will clarify this in our revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KSO6bAYpRg", "reviewer": "Reviewer_j2Bu", "summary": "This article presents a nice extension to the broad class of penalty method problems, particularly for the case when the objective functions have a Hölderian error bound. This assumption for this class of problems appears new, and a thorough coverage of interesting results are claimed.", "questions": "The classical article on penalty methods,\n\nDmitri P. Bertsekas, \"Necessary and Sufficient conditions for a penalty method to be exact\", Math. Program., vol. 9, pp. 87 - 99, 1975.\n\nbasically states that, if the penalty function is smooth near the solution set, then the penalty must go to infinity in order to achieve exact penalization; and, if the penalty function is nonsmooth near the solution set, then a finite penalty will suffice. My question is: are your results consistent with this article? In particular,\n  - In the setting where $G$ is smooth, can you confirm that $\\lim_{\\varepsilon\\to 0}\\gamma^*\\to\\infty$?\n  - On the other hand, if $G$ is nonsmooth at its solution set, does $\\lim_{\\varepsilon \\to 0} \\gamma^*$ approach a finite value? Violating this second requirement would not contradict the aforementioned article, but it would significantly strengthen your results.", "limitations": "The authors do a good job of explaining the required assumptions for their results.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- New results presented for bilevel optimization for the Hölderian error bound setting\n- New relationships between the minimizers of a penalty problem and the exact problem; this is a particularly mature field, and finding new results here is meritorious.\n- Presentation of a standard prox-based method for solving these bilevel problems with their new theory, with complexity details explained.", "weaknesses": "- The article does not distinguish between what type of subdifferential is used. Since the authors also make a mention of the applicability of their results to nonconvex objectives, this is crucial point. Many classical results in optimization and convex analysis are proven using the *convex* subdifferential; however, even for differentiable nonconvex functions (e.g., $-x^2$), the convex subdifferential is empty, while other notions like the Clarke subdifferential is nonempty.\n- Assumption 3.2 is a very strong one; while I agree with the author(s) that the prox of a sum is widely studied, the list of settings in which one can compute this is still quite limited. However, this is not a major drawback for me, since handling HEB bilevel optimization even in the L-smooth setting appears to be new.\n- In my opinion, leaving lines 140--142 to stake claim to results for non-convex which are exclusively in the appendix seems improper. The appendix is technically \"unreviewed\" material; if the formal statement of the result cannot fit into this article, then I do not think it is worth including. I suggest that the authors either try to find a way to incorporate these results into the article (since they are indeed quite interesting), or save the results for another work.\n- The graphs of the numeric are too small for me to read, especially in-print.\n\nMinor comments:\n- The fact that the argmin of  a convex lsc function is closed and convex is a classical result which has been known for decades, so it seems odd to cite [Beck and Sabach, 2014] instead of a classical book, or the article where it was first proven.\n- The article makes mention to functions $f_2$, $g_2$ far before they are introduced, which is confusiung to the reader.\n- Names \"Pock, Tseng, etc.\" are not capitalized in the citations.\n- Citation on lines 391-392 is missing volume number.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We acknowledge the valuable insights you have provided for our paper. \n\n# Weakness 1: \nThank you for pointing this out. Our definition of the subdifferential is derived from convex analysis. We use the subdifferential for a convex function $f$: $\\partial f(x) = \\\\{ g : f(y) - f(x) \\ge g^T(y - x) \\\\}$ (cf. [1, Section 4.2]). In our analysis, the usage of the subdifferential is limited to convex functions (see Assumption 2.1 and equation (8)). For nonconvex functions, we do not use Assumption 2.1 but instead directly assume the Lipschitz continuity of $F$ to simplify our analysis.\n\nFor the general nonconvex case, we can also use other subdifferentials for 'stationary points' as discussed in Section 4 of [2], such as B(ouligand)-stationary points or C(larke)-stationary points, using the B-subdifferential or C-subdifferential, respectively. However, it is often challenging to obtain a simple definition of stationarity for the original simple bilevel optimization problem when the lower-level problem is nonconvex. Therefore, in our future work, we will explore the relationship between stationary points of the original problem and the penalized problem using general subdifferentials in scenarios where the upper-level problem is nonconvex but the lower-level problem is convex.\n\n# Weakness 2: \nThank you for recognizing the novelty of our work. The requirement for the nonsmooth term to be prox-friendly is widely adopted in optimization and is satisfied in many machine learning applications, such as $\\ell_1$- and $\\ell_2$-norms. It is also important to note that our assumption is more general than those found in existing literature.\n\nSpecifically, in the simple bilevel literature, when employing proximal mappings, researchers often consider the scenario where only one level contains a nonsmooth term (see, e.g., [3,4,5]). The proximal mapping of the sum $f_2 + \\gamma g_2$ is then reduced to the proximal mapping of either $f_2$ or $g_2$, which is a more easily satisfied condition.\n\nA similar case occurs when $f_2 = \\beta g_2$ for some $\\beta > 0$. For instance, when minimizing both the validation loss and training loss of the LASSO problem simultaneously, the nonsmooth terms of the upper- and lower-level objectives are identical, both being $\\ell_1$-norms. In this situation, the proximal mapping of $f_2 + \\gamma g_2$ corresponds to the proximal mapping of a $\\lambda \\ell_1$-norm, for some $\\lambda>0$, which is straightforward to compute.\n\nGenerally, the prox-friendly properties of $f_2 + \\gamma g_2$ are challenging to maintain. However, some studies have identified conditions under which the sum of two proximal mappings can be easily computed (e.g., [6,7]).\nFor example, in regression problems, it is common to encounter situations where the nonsmooth parts of the upper- and lower-level objectives are the indicator functions of an $\\ell_1$-norm ball and an $\\ell_2$-norm ball, respectively. The joint proximal mapping is then the projection onto the intersection of these two balls, and the method in [8] can be used to compute it. Another case involves one level having an $\\ell_2$-norm regularizer and the other having an $\\ell_1$-norm regularizer. The sum $\\lambda_1\\\\|x\\\\|\\_2^2 + \\lambda_2\\\\|x\\\\|\\_1^2$ ($\\lambda_1, \\lambda_2 > 0$) is known as the elastic net, for which the proximal mapping has a closed form.\n\n# Weakness 3: \nThank you for recognizing the significance of our analysis of non-convex problems. Due to space constraints, we initially placed the results in the appendix. In our revision, we will restructure the paper to include the analysis of non-convex problems in the main paper.\n\n# Weakness 4: \nWe apologize for any inconvenience. In our revision, we will adjust the size and format of the graphs to improve their readability and comprehensibility. Furthermore, we have included the experimental results of our main paper in 'Figure 4' and 'Figure 5' of the PDF in 'Author Rebuttal'.\n\n- Minor comment 1: Thank you for pointing this out. The correct references should be [1, Proposition 1.2.2 and Page 49].\n\n- Minor comment 2: We apologize for the omission of the introduction of $f_2$ and $g_2$ before their usage. \n\n- Minor comments 3, and 4: Thank you for pointing out these typos. We will correct them in our revised paper.\n\n# Questions:\nThanks for bringing Bertsekas [9] to our attention. We found that the assumptions and conditions in [9] are different from ours. \n[9] suggests a scalar penalty function $p(t): R\\to R$ satisfying that $p$ is convex and $p(t)=0$ for all $t\\le 0$ and $p(t)>0$ for all $t>0$. However, in our paper, we use $p(t)=\\gamma \\cdot t$, which contradicts $p(t)=0$ for all $t\\le 0$. Nevertheless, let us compare the results.\n\nFirst, in Section 2, [9] requires an assumption (A.2) that problem $(P_{\\text{val}})$\n$$\n\\min F(x)\\quad \\text{s.t.} \\quad G(x)-G^*\\le0.\n$$ \nhas at least one optimal Lagrange multiplier. This assumption often fails (the multiplier is often $\\infty$) in simple bilevel optimization as the Slater condition fails for $G(x)-G^*\\le0$.\n\nIn the case of $\\alpha=1$ in the HEB assumption, the multiplier exists. For $p(t)$ satisfying conditions in [9], Proposition 1 in [9] says that a necessary condition for exact penalization is $\\lim_{t\\to0^+}\\frac{p(t)}{t}\\ge y$ and a sufficient condition is $\\lim_{t\\to0^+}\\frac{p(t)}{t}>y$, where $y$ is an optimal Lagrange multiplier. Unless some multiplier is zero (this means  $(P_{\\text{val}})$ is essentially unconstrained), the latter happens only if $p$ is nonsmooth. We guess this leads to your question. However, the smoothness is related to $p$, but not $G$.\n\nIn our case, we always have  $\\lim_{t\\to0^+}\\frac{p(t)}{t}=\\gamma>0$. But as A.2 and C.2 in [9] fail here, there is no contraction between [9] and our results.\n\nThese observations indicate that the results proposed by [9] don't apply to our paper.\n\nWe sincerely hope that the preceding discussion addresses your inquiries. We appreciate your constructive questions once again.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
In this global 'Author Rebuttal', we upload our additional experimental results, as well as the clearer and more readable experimental results of Sections 4.1 and 4.2 in our paper.

# Linear regression problem
The first experiment is the sparse linear regression problem on the data ($3,000$ instances of 'YearPredictionMSD') same as the one used in Section 4.2 in our paper. We allocate $60\\%$ of the data as the training set $(A_{tr},b_{tr})$, $20\\%$ of the data as the validation set $(A_{val},b_{val})$, and the rest as the test set $(A_{test},b_{test})$ with $\frac{1}{2}\\|A_{test}x - b_{test}\\|^2$ as the test error. The sparse linear regression problem has the following form:
$$
\min\_{x}\frac{1}{2}\\|A\_{val}x-b\_{val}\\|^2 \quad \text{s.t.}\quad x\in\text{argmin}\_z ~\frac{1}{2}\\|A_{tr}z-b_{tr}\\|^2+\\|z\\|\_1.
$$

For the experimental results, please refer to 'Figure 1' in the PDF.

# Integral equation problem
In the second experiment, we explore the regularization impact of the minimal norm solution on ill-conditioned inverse problems arising from the discretization of Fredholm integral equations of the first kind [1], i.e., the solution of the integral equation problem. Following the same setting of [2], we solve the following problem:
$$
\min\_{x}x^T Q x\quad \text{s.t.}\quad x\in\text{argmin}\_{z\ge0}\frac{1}{2}\\|Az-b\\|^2,
$$
where $[A,b_T,x_T] = phillips(100)$ and $b = b_T + 0.2w$ with $w$ is sampled from a standard normal distribution, $Q = L^T L+I$ with $L=get\_l(100)$ and $I$ is the identity matrix. The functions '$phillips$' and '$get\_l$' follow from the ''regularization tools'' MATLAB package [3].

For the experimental results, please refer to 'Figure 2' in the PDF.

# Fair classification
Moreover, in the third experiment, we address the fair classification problem as described in [4], which features a non-convex upper-level objective. We randomly sample $3,000$ instances as the training set and $2,000$ as the test set. The domain of the lower-level objective is set to be $\{x:\\|x\\|_1\le10\}$.

For the experimental results, please refer to 'Figure 3' in the PDF. Given the non-convex nature of the upper-level objective, this experiment demonstrates that our algorithm can effectively handle some practical non-convex scenarios.

# Experimental results of our main paper
Here, we present the experimental results of our main paper (Sections 4.1 and 4.2) after resizing and formatting. For the detailed results of Sections 4.1 (Logistic regression problem (LRP)) and 4.2 (Least squares regression problem (LSRP)), please refer to 'Figure 4' and 'Figure 5' in the PDF, respectively.

# References

[1] Phillips, David L. A technique for the numerical solution of certain integral equations of the first kind. JACM 1962.

[2] Doron, Lior, and Shimrit Shtern. Methodology and first-order algorithms for solving nonsmooth and non-strongly convex bilevel optimization problems. MP 2023.

[3] Hansen, Per Christian. Regularization tools version 4.0 for Matlab 7.3. Numerical algorithms 46 (2007): 189-194.

[4] Jiang, R., Abolfazli, N., Mokhtari, A. and Hamedani, E.Y. A conditional gradient-based method for simple bilevel optimization with convex lower-level problem. AISTATS 2023.

Meta-review: I would like to thank both the authors and reviewers for the good discussion. The reviewers agree that the paper is interesting although two reviewers are a little hesitant only recommending "borderline accept". Having looked at the paper and read the reviews, I recommend acceptance, however I urge the authors to take the reviewers feedback into account when preparing the camera-ready version.
Decision: Accept (poster)