Unlocking Global Optimality in Bilevel Optimization: A Pilot Study
Authors: Quan Xiao
Tianyi Chen
Venue: ICLR 2025 Poster (2025)
Keywords: Bilevel optimization
nonconvex optimization
global convergence
linear neural network
Primary area: optimization

Abstract: Bilevel optimization has witnessed a resurgence of interest, driven by its critical role in trustworthy and efficient AI applications. Recent focus has been on finding efficient methods with provable convergence guarantees.  However, while many prior works have established convergence to stationary points or local minima, obtaining the global optimum of bilevel optimization remains an important yet open problem. The difficulty lies in the fact that unlike many prior non-convex single-level problems, bilevel problems often do not admit a ``benign" landscape, and may indeed have multiple spurious local solutions. Nevertheless, attaining the global optimality is indispensable for ensuring reliability, safety, and cost-effectiveness, particularly in high-stakes engineering applications that rely on bilevel optimization. In this paper, we first explore the challenges of establishing a global convergence theory for bilevel optimization, and present two sufficient conditions for global convergence. We provide {\em algorithm-dependent} proofs to rigorously substantiate these sufficient conditions on two specific bilevel learning scenarios: representation learning and data hypercleaning (a.k.a. reweighting). Experiments corroborate the theoretical findings, demonstrating convergence to global minimum in both cases.

Published as a conference paper at ICLR 2025
UNLOCKING GLOBAL OPTIMALITY IN BILEVEL OPTI- MIZATION: A PILOT STUDY
Quan Xiao
Tianyi Chen
Rensselaer Polytechnic Institute Troy, NY 12180, United States quanx1 8 8 gmail com
Rensselaer Polytechnic Institute
Troy, NY 12180, United States
chent:iany199egma com
ABSTRACT
Bilevel optimization has witnessed resurgence of interest, driven by its critical role in trustworthy and efficient Al applications. Recent focus has been finding efficient methods with provable convergence guarantees. However, while many prior works have established convergence to stationary points local minima, obtaining the global optimum of bilevel optimization remains an important yet open problem. The difficulty lies in the fact that unlike many prior non-convex single- level problems, bilevel problems often do not admit a "henign" landscape, and may indeed have multiple spurious local solutions. Nevertheless, attaining the global optimality is indispensable for ensuring reliability, safety, and cost-effectivennss. particularly high-stakes engineering applications that rely on bilevel optimization. In this paper, we first explore the challenges of establishing global convergence theory for bilevel optimization, and present two sufficient conditions for global convergence. We provide algorifim-dependent proofs to rigorously substantiate these sufficient conditions on two specific bilevel learning scenarios: representation learning and data hypercleaning ka. reweighting). Experiments corroborate the theoretical findings, demonstrating convergence to global minimum in both cases.
INTRODUCTION
Bilevel optimization aims handle two interconnected problems, where one problem is nested within another (Bracken & McGill 1973). Recently, bilevel optimization has gained significant attention due to their relevance various machine learning, signal processing and wireless communication applications, including hyperparameter optimization (Maclaurin et al. 2015 Franceschi et al. 2017]
2018 Pedregosal 2016), meta-lcarning (Finn et al. (017). representation learning (Arora et al. 2020: Shen et al. 2024), continual
2020),
reinforcement learning with human feedback (Stadie et al.
learning (Pham et al. [2021] Borsos et al. (2020) Hao et al. (0033 adversarial learning (Zhang et al.
2022 Robey al. 2024) and neural architecture search (Liu et 2019); recent survey (Liu et al.
2021 la
Sinha et al. 2017). In this paper, we focus on the optimistic bilevel optimization problem as
min fu, v), s.t. S(u) arg min g(u,
n,"ES(u)
where both the upper-level objective function f Rd x gd - R and the lower-level objective function g Rdd dR + R continuously differentiable.
To tackle the above bilevel problems, various efficient algorithms have been proposed with rigorous
guarantees on iteration and sample complexity. but most of them are only guaranteed converge
to the stationary points (ji et al., (02T)] Chen et al. 202T]: Hong et al. 2023 Dagréou et al. 2022
Ghadimi & Wang 2018 Kwon et al. (2023) or locally optimal solution (Huang et al.) 2022] Dempe 2019,[Chen et al. 2023a) instead of the global optima. However, identifying the global optimal solution for bilevel optimization is vital in various real-world applications where the quality of
solutions can have significant impacts. For instance, in policy-making (Dempe et al.) 2219),, energy systems WW et al. 2019; Razmara et al. 2016), resource allocation (Gao et al. 2020 Huang et al.) 2019 Shi & Luo| 2017) and network design (Gao al.] 2005), globally optimal solutions can lead to more cost-efficient and sustainable outcomes than local solutions. Furthermore, in high-stakes fields like healthcare, law, and robotics, attaining global optima ensures that the AI models are aligned with

---

Published as a conference paper at ICLR 2025
human values with minimal risks of harmful generation (Modares et al. 2015 Blyık al. 2022). Thus, the goal of this paper is to study the global convergence (in contrast to convergence to local optima) of bilevel optimization for certain (not all) machine learning applications.
1.1
OUR MAIN RESULTS
We summarize our main results to tackle the global optimality of bilevel optimization.
C1) The penalty reformulation of bilevel optimization has more benign landscape.
Recent advances in bilevel optimization algorithms can be generally classified into two categories.
Nested approaches solve the problem [ from its nested formulation F(u) == min f by optimizing first over one variable u and then over the order see e.g., (Ghadimi & Wang 2018
Ji et al. 2021 Hong et al. 2023 Chen et al. 2021
Constrained approaches incorporate the optimality condition of the lower-level problem in as constraint the upper-level problem and then optimize over u and v jointly; see e.g., (Sow et al.
2022a
Liu et al. 2022 Kwon et al. 2023
2024 Chen ct al. 2023a Shen al. 2023).
In this paper, we first investigate the loss landscape of the bilevel problem ( through the lens of nested and constrained bilevel reformulations, demonstrating that the constrained formulation is easier to yield a benign landscape.
C2) Benign properties of the penalty reformulation ensure convergence to global optimum.
We analyze the landscape of the penalty reformulation of the constrained version of ( and derive two sufficient conditions that ensure favorable landscape for bilevel problems. These conditions, inspired by practical applications, provide a stepping stone for global convergence of bilevel algorithms.
Specifically, we define the penalized objective L,, v) == f(u, v) + ((( v) g" (u)), where g" (u) = min, (2, v) is the value function and 7 > 0 is a penalty constant, and generalize the (PL) condition to the two-varia case below.
definition of the standard
Definition (Joint and blockwise PL condition). L,, v) satisfies joint PL with μi O(r) if
(u, v)1? 2 2pr(L, v) min Ly v)).
(2)
In addition, (u, v) is said to be blockwise PL with Pas My O()) if both of the followings hold |VuL, v)12 (L,(L min L. (u,
(3a)
(u, r) (L, min (u, v)).
(3b)
We use the term 'benign landscape' represent penalty function (u, v) satisfying either of the above conditions, or nested objective F(uu) min f',, v) satisfying PL condition over
From benign landscape global convergence. Under either of the above conditions,
establish
that the penalized bilevel gradient descent (PBGD) algorithm (Kwon et al. 2023 Shen et al. 2023 Kwon al.
2024 Chen et al., (023a),. a fully first-order method, globally converges to the optimal solutions of 1. Under the joint PI. condition, updating (u, v) in a Jacobi manner (c.f. (7b)-7c) will ensure the global convergence. Under the blockwise PL. condition, updating u and v in Gauss-Seidel
manner (c.f. 77 (7 ensures the global convergence.
C3) Two representative bilevel learning problems guarantee benign properties.
We validate two benign landscape conditions in Definition | through two representative bilevel applications: representation learning and data hyper-cleaning (a.k.a. reweighting) with least squares loss, respectively. We rigorously prove that the loss surfaces reached by PBGD, when employing a Jacobi update and a Gauss-Seide update, respectively, adhere to the joint PL condition and the blockwise PL condition throughout the optimization trajectory for these two problems. As result, we prove for the first time that PBGD converges to the global optimum for both problems.
Choice of problems and models. The particular choice of two bilevel applications exemplify two different types of bilevel interactions between the upper and lower-level problems, are suited to different update dynamics of PBGD. Compared with the landscape analysis of single-level problems,
2

---

Published as a conference paper at ICLR 2025
the uniqueness of the bilevel landscape lies in the intricate coupling structures between the upper-level and lower-level problems. Recognizing this, it is evident that even analyzing the linear models can capture the essence of the problem structure and exclude other confounding factors which might be less relevant to the bilevel landscape analysis. Moreover, as a challenging yet important problem, the glohal convergence analysis for single-level optimization also starts with linear models to gain insights such as in matrix completion (Sun & Luo, 2016 Ye & Du 2021) I) phrase retrieval (Ma et al. 2018), and linear neural networks (Xu et al.) 2023 Zou al. 2020). Therefore, our efforts will be put into understanding how coupling structure affects the bilevel landscape with a linear model.
1.2 RELATED WORKS
Stationary point and local convergence. The recent interest in developing efficient gradient- based bilevel methods with nonasymptotic convergence guarantees has been stimulated by (Ghadimi & Wang 2018: Ji et al. 2021] Hong et al. 2023 Chen et al.] 2021). Based on different Hessian inversion approximation techniques, these algorithms can be categorized into iterative differentiation (Franceschi et al. 2017 2018 Grazzi et al. 2020) and implicit differentiation based approaches (Chen) ct 202] Ghadimi & Wang 2018 Hong et al., 2023: Ji et al.] [021] Pedregosal 2016). Recent works have reformulated the bilevel optimization problem as a single-level constrained problem, and solved it via the penalty-based gradient method (Shen et al.) (203);; also (Liu et al. 2022
Kwon et a 2023 2024, Chen et al., [023a Lu & Mei (023). While the nonasymptotic analysia of stationary convergence has been extensively studied in bilevel optimization recently, finite-time convergence guarantee for local minimum remains under-explored Recently, (Huang et al., 2022)
and (Chen et al.) 2023a) have found the benefit of adding noise to gradient- based bilevel methods, which helps them to efficienlly escape from saddle points and converge to local minima. However, none of them analyze the landscape and the convergence to global optimal solutions.
Global optimum convergence. In general, finding the global optimal solution for bilevel opti- mization is NP-haad (Vicente et al. 1994). Historically, globally convergent algorithms for bilevel optimization (Gümüş & Floudas 2001 Muu & Quy) (003) were built upon the branch and bound method, globally convergent single-leve level algorithm. Despite its theoretical soundness, the branch and bound method is generally inefficient due to its exhaustive search nature. Another line of research focused on the bilevel problems with specific structures. A semi-definite relaxation method has been introduced in (Jeyakumar et al., 2016) for polynomial bilevel problems, and dual reformulation has been developed in (Wang et al. 2007) for quadratic bilevel problems with a linear lower-level More recent efforts by (Wang et al. 2021 2022) solved Stackelberg prediction games with quadratic regularized least squares problems at the lower level by applying semi-definite relaxation and spheri- cal constraints. However, these methods are problem-specific and are not suitable for more complex machine- learning scenarios, particularly where the lower-level problem presents multiple solutions.
1.3 NOVELTY AND TECHNICAL. CHALLENGES
We highlight the novelty and technical challenges for the analysis in our work as follows.
TI) We carefully examine the challenges posed by the complex landscape of nested optimization and the general non-additivity of PL functions (see Examples 1-5), underscoring the impor- tance of analyzing the landscape of the penalized problem and the additivity properties of specific PL functions. Even for the special case highlighted in Observation 2 the additivity remains non-trivial due to differences in the strongly convex and matrix mappings.
T2) Global convergence under the generic benign landscape conditions in Definition] is still insufficient for the two applications, even in the linear model case. This is because only local PL. and smoothness conditions are satisfied, with constants that vary along the optimization trajectory of PBGD. By leveraging induction-based proof and the advanced acute matrix perturbation theory, we establish the boundedness of the local PL and smoothness constants throughout the trajectory of PBGD, and thus this leads the global convergence results over the penalized objective (u,, e))
T3)
To bridge the gap in achieving global convergence to the optimal solution of the original bilevel problem for these two applications, we establish application-spect equivalence between the penalized problem and the original problem, relying solely on local PL and local smoothness conditions, which has not yet been explored in the existing literature. The conditions are also validated along the optimization trajectory of PBGD.
approximate
3

---

Published as a conference paper at ICLR 2025
(a) g(u, v)
(b) f(, v)
(c) F(u)
(d) (u, v)
Figure I: Visualization of g(u, v), f', v), F(u) and L, v) in Example In (b), [(, 2) is PL but F(u) is distorted by (w)). ). In (c), saddle points exist for F(u). suggesting that F(u) is not PL. In (d), the penalty objective L,(u, v) has better landscape because of additional dimension of
Notation. Let IR, R20, R Ry Z be the sets of real, nonnegative real, positive real and integer numbers. For given matrix A E RPxq, let (AA)) and a; (A) be the i-th eigenvalue and singular value in descending order, respectively. Denote maax (mmx((A) (A) = a (A), amin
Omin(p.q) : (A) and o.(A) = (iax( (A)))) the maximal, minimal, and minimal nonzero singular values. Let Aij represent the entry at the i-th row and j-th column of A. Lett |||||| and ||A|| 2 be the Frobenius and spectral norms of Let 8s0 be if and infinity otherwise. Let (-) denote the indicator function.
CHALLENGES AND TARGET OF CONVERGENCE
In this section, we will reveal the complicated landscape of the nested objective F(u)) and then state the target of global convergence.
2.1 CHALLENGESS IN THE NESTED FORMULATION OF BILEVEL OPTIMIZATION
Establishing the global convergence for bilevel optimization algorithms is fundamentally challenging because the nested bilevel objective F(u) exhibits different properties compared to the upper- and lower-level objectives fu, v) and g(u, v). This is primarily due to the distortion induced by S(u). To gain some intuition this distortion, consider the where both upper and lower-level objectives satisfy the PI. condition jointly over (u, v): there exists f Mg >> O such that
[V, 2)1 2 2 v) - min (u, v)) and [V, b) 2 2 2 v) min g(u, v)). (4)
u."
The following example shows that the PL condition on both levels is not sufficient to guarantee the PI. condition over the bilevel objective F(u), even the lower-level solution mapping S(u) is linear.
Example 1. With u E R and E IR, consider the following upper and lower-level objectives
1 f(u, = (u (u- (i-nsi)())) and g(u, v) (u u)²
1
We can verify that both [w, v) and g(u, v) satisfy the joint PL condition in 4 and the lower-level problem parameterized by u yields the unique solution S(u) = u. However, the overall bilevel function F(u) S(u)) [u sin(()) violates the PL condition over The graph of F(u) shown Figure and the formal proof is deferred to Appendix C.I]
Similarly, joint convexity of both levels can not ensure the convexity of the bilevel objective F(u) even if the lower-level solution is unique; see the Example in Appendix C.3
These suggest that the landscape of the nested bilevel objective F(u) can be casily distorted by the lower-level solution mapping (u)), which we do have the direct access to control.
2.2
SEEKING GLOBAL OPTIMUM VIA PENALTY REFORMULATION
To avoid directly dealing with S(u), some of recent works have focused solving the bilevel
optimization (T) from the perspective of constrained optimization, where the lower-level problem
treated constraint of the upper-level problem;
e.g.. (Kwon et al. 2023 Shen al.
2023 Liu et al. 2022 Mehra & Hamm 2021| Kwon et al., (024)) Defining the value function as min, g u. v). the bilevel problem in (1) can be equivalently reformulated
min fu, v), s.t. g(u,v) g (u) < O.
(5)
An (61, 62) optimal solution of the bilevel problem can then be defined as follows.
4

---

Published as a conference paper at ICLR 2025
Definition 2 (An (e1, 62) solution of bilevel problem). Civen u² R 00 E &R, we say point
(u", v²) is an (c), 62) global solution to bilevel problem (I) if g(g" v²) g" (2²) S E2 and for any R v R satisfying g(u,v) (u) S Ez. we have f(u" ,²)) S fu, +1.
To find an (e1, 62) solution of 5 one can resort to optimize its penalized problem (Shen et al.
2023
min (u, = fu, 2) + ((((,,))))))) g (u)).
(6)
It was shown in (Shen et al.
2023) that, the e-solution for 6 with penalty parameter = O(c-0.5)
the (c, O()) solution for bilevel problem in Definition 2
Therefore, analyzing the landscape of
the penalized objective L, (u, v) also leads to the global convergence to an (e, solution of (5)
v) bypasses the need to study the PL.- preserving property under composition in Section 2.1, making it easier to establish benign landscape property; see Figure [ Besides, the continuity and differentiablity of g" (u) is generally casier to be satisfied than that of S(u); see e.g., (Dontchev & Rockafellar 2014 Example 3B.6). This makes L, v) more likely to be differentiable than F(u). On the other hand, as min, L,, v) is an cetiivaleen-dimesiiinn proxy of F(u) (Kwon al. 2024). L,,,, v) offers a high dimensional
Benefits of L,(u, v) instead of F(u).. Analyzing
approximation of F(u), smoothing out the ravine of F(u) in high-dimensional space; see Figure
3 GLOBAL CONVERGENCE CONDITION IN BILEVEL OPTIMIZATION
In this section, we will propose counterparts to the global convergence condition from single-level optimization for bilevel optimization based on the penalized constrained formulation 6
3.1 BENIGN LANDSCAPE CONDITIONS
To characterize the global convergence in bilevel optimization, we generalize the PL condition (Karmmi et al. 2016), and define the joint PL and blockwise PL conditions of L,(u, v) in Definition
Two "bilevel PL" conditions. The joint PL condition in 2 extends the standard PL condition to two-variable setting by treating (u, v) as a new single variable, while the blockwise PL. condition in (3) reflects the hierarchical structure of bilevel problems by treating the optimization over u and v as
separate blocks. For simplicity, we define condition (3a) for the whole space, but it is also sufficient for global convergence if the condition (3a) holds only for v E arg min, (, v). It is also important to note that the joint PL. condition and the blockwise PL condition can not imply each other.
Rationale of two PL conditions. The two PL conditions correspond to bilevel problems with isomorphic and heterogeneous levels, respectively. Specifically, in representation learning (Section 4. the upper-level and lower-level variables are model weights from different layers, maintaining similar nature; and in data hyper-cleaning (Section 5). the lower-level variables are still model weights, but the upper-level variables are the classification parameters for each sample, which is a distinct type of variable from the model weights.
Following (Shen et al. 2023 Kwon et al. 2024), if we choose = (c. (c)) global solution of the bilevel problem in Definition 2 Therefore, we can then focus on developing a globally convergent gradient- based al algorithm for the penalized problem Ly(u,)) v) under the joint blockwise PL condition.
the e-global convergence
to the penalized problem 66) implies the convergence
3.2
GLOBALLY CONVERGENT ALGORITHM: PENALTY-BASED BILEVEL GRADIENT DESCENT
We revisit the penalty- based bilevel gradient descent (PBGD) algorithm (Shen al. 2023 Kwon
et al. 2023 2024 Chen et al. 2023a), a fully first-order method with provable stationary convergence. We will demonstrate that PBGD reaches the global optimum when the benign conditions are satisfied.
As the name implies, PBGD employs gradient descent on the penalized objective (6). Thanks to the Danskin type theorem (Nouiched et al. 2019), (L, v) can be calculated by
VuL,(u, v) (u,(u, + 7V u) V.g(u, w)). VoL,(u, V.s(u, + Veglu, v)
where w E Su) is auxiliary variable used for estimating Vg (u). Therefore, iteration k. PBGD first updates w to track S (w*) by Ti step gradient descent on g(u", initialized by wh =
ket+l
the VVog(u hit)
(7a)
5

---

Published as a conference paper at ICLR 2025
and update wh+1 = uh Then update u² and uh via the gradient descent update L, v) simultaneously that we term the Jacobi version if Lu v) is jointly PL; that is
u ut a (V (u w²) + +- (Vug(u,, v²) Vug(u" w())))) , 8t al [V. (u k )² + r VVg(ut )²)
(7b)
(7c)
or alternatingly that we term the Leauss-Seide version if L,(u, 2) is blockwise PL (with 500 as the initialization and e = y as the output); that is
k.tt11 ah ((V. wuitt + 7 + Vog(u of t= 1,2, Tk -++ - (V..(u², t1t) + (Vng(u rhtl) Vug(u w w**+))
(7d)
(7e)
The Jacobi and Gauss-Seidel versions of PBGD are summarized in Algorithm and 2 respectively.
Algorithm 1 PBGD in Jacobi fashion
Algorithm 2 PBGD in Gauss- fashion
1: Initialization fu², v0, w²), stepsizes {a, $).
1: Initialization {u², v², w"} stepsizes {a, 8, 3), penalty constants ?
penalty constants
2: for 0 K
2: for k = to K 1 do
3: initialize w w
3: for f
T do update whitt1 by 7a
4: for t= 0 to T - 1 do
4:
5: update w.++1 by 7a
5: end for
6: end for
6: for m- T 1 do
7: set w*+11 miTk
7: update u by (7d)
8: update u A+1 by 7b
8: end for
9: update k+1 by 7c
9: update *+1 by 7e
10:
end for
10: end for
To prove the convergence, make the following assumptions; see also in (Shen et al. 2023
Kwon
ct al. 2024 Ghadimi & Wang 2018 Hong et al. 2023 Chen et al. 2021 et al. [022]).
Assumption 1. Assume f fu, v) and g(u, u) are E-- and Ey-smooth over (u, v). fu, is f,a-- Lipschitz continuous over v, and g(u, .) is Py over
The following theorem shows that PBGD is globally convergent to the bilevel problem with almost linear convergence rate when the penalized problem has a benign landscape.
Theorem 1 (Global convergence of PBGD). Suppose Assumption 7 holds, then g (u) is smooth with Lg = (1 + L /24g)) Given a target accuracy e, we set 7 = O( O(--0.5) stepsizes / S r, inner loop Tr O (log (7²c-1)). Then if Lu, v) satisfies the joint Pt. condition Q with in > and we
choose a S ( T,,' there exists 6, = O(e) s.t. the iterates of PBGD in Algorithm satisfies
f(u ,k UI, < ((11 - amt) ) + O(c) and glu" ,xx) minn
) min g(u v) S S 0(c)
for any (u, u) with g(u, g" (w) S e, = O(e).
Alternatvell, if (u, v) satisfies the blockwise PL. condition 3 with pus thv > 0, arg aig, (u,
is independent of and we choose the stepsizes B < 1,+T5, +. where Lo = (ls + 76g) (E, + /lg)/222 + Lg then the iterates of PBGD in Algorithm ssaiisfiss
flukk ((uKK,KK]) kt1) f((, v) < 0((1 ((1--ap)))) Occ) and glu" k+1) min glu , S ey
for any (u,v) with g(u, v) 9" (w) < c, = O(e).
Theorem I shows that, with properly selected stepsizes, PBGD employing either the Jacobi update under the joint PL condition or the Gauss-Seidel update under the blockwise PL condition, converges to an (O()) (()) solution for the bilevel problem within O(K max T&) O(log( -1)2) iterations. The proof of Theorem T is provided in Appendix D
Remark 1 (Other choices of algorithms). It is worth mentioning that other first-order bilevel
algorithms based on the penalty formulation (6). such as F*SA (Kwon al. 2023 2024 Chen et al,
2023a) and BOME (Liu et al. 2022), could also have global convergence. We provided the global
convergence based on the PBGD algorithm Shen et al. 2023 here as an example.

---

Published as a conference paper at ICLR 2025
3.3 ENSURING GLOBAL CONVERGENCE CONDITIONS
In this section, we will provide some key observations to help us establish the global convergence conditions in Section 3.1 Let us first revisit the definition of the penalized objective
Additivity Pl. functions bolds? Observation 2
(u,
[(u
(g( 9 (u)
joint PL. & blockwise Pt.
Observation
D joint PL. & blockwise PL over
We have the first observation on the landscape of g(u, v) 9 (u) over (u, v) and that over v.
Observation 1. Under Assumption 7 g(u, v)-g"(u) is joint PL over (u, v) and blockwise PL over v.
Therefore, if the upper-level objective additionally satisfies joint PL or blockwise PL condition, then whether L., (u, v) satisfies joint PL or blockwise PL condition over v depends on the additivity of PL functions. In general, the sum of two joint/blockwise PL functions is necessarily a joint/blockwise PL function. For the counterexamples in join/blockwise PL condition, see Appendix C.2
The lack of the additivity of PL functions in general impedes the development of a unified global convergence theory for bilevel problems. However, we highlight another key observation to establish the PL. condition of (u, v) for a special class of problem. This observation implies that strongly convex function composite with a linear mapping preserves the PL condition under additivity.
Observation 2. Let h1 R + and hz2 : IR" - R be strongly convex functions with constant h1 and (2g, respectively. Given any matrix A Rmxd B Rn h (Az) and h22 (Bz) satisfy the PL condition over E IRd with constant 11 and p2g. (B), respectively. Moreover, hu (Az) h (2)) satisfies the PL condition with constant min of (2) (B)).
This observation is particularly valuable for analyzing global convergence in bilevel optimization problems involving linear neural networks with strongly convex loss functions, such as the least squares loss or cross-entropy loss within a bounded region.
Dealing with problem-specifie challenges. In Sections 1 and 5 we will show how to use our bilevel global convergence framework in two problems: representation learning and data hyper-cleaning, In these two applications, we choose linear or bilinear models with least-squares losses. Although these models are relatively simple, only local (non-uniform) versions of the joint PL and blockwise PL conditions are satisfied due to the coupling within the linear network, and the local constants vary with the algorithm's 's iterations. Nevertheless, we will judiciously verify the joint PL condition and blockwise PL. condition along the optimization trajectory of PBGD by carefully bounding these constants and establish the optimality equivalence of ( and (6)
at the limit point of PBGD.
GLOBBAL CONVERGENCE IN REPRESENTATION LEARNING
In representation learning, we are given a training dataset (e and a validation dataset {2,, ūi YN',, with data sample x,, 2; E R and label ys, Rt E R". We aim to train a model capable of excelling with unseen data by adjusting only the top layer's weights W1 while keeping the backbone model W2 fixed. For simplicity, we consider the two-layer linear neural network and the mean square loss in this paper, so the resultant bilevel problem can be formulated
min W.. (WW.) 2
||Yvall - X W1 W2W2l12 s.t. S(W1) = arg min W2
2
| - X W1 22l
(8)
where Xum = [-1,..., _NN] Nxm Xya = [a,,... TN-1 E N'm are the training and
validation data matrix, Yer = [vi..... yNl E RNx, Yval = Ii...... :N..]" E g. xm are the training and validation label matrix and W1 E Rmxh W2 E Rhxn are the weight matrix. We consider the overparameterized case with m 2 max(N, N") so that S(W1) has multiple solutions. We also assume the neural network is wide 2 max(m,n) and Xim, Xval are of full row rank !
Let us denote Lim Amm(W (W1, W2) = 1/ |Yuo - Xim W1 W2ll Lval (W1, W2) = 1/2 |Y Xval W W2ll as the loss of two-layer linear neural network. We are interested in the scenario where the backbone
Our theory also works for rank-deficient case by changing main ( (xa)), mmin (Xum) a2 (Xum), 0n (Xuma)-
7

---

Published as a conference paper at ICLR 2025
Dilvdd Iow howily afFICGn
8
+1.
Dimike 2
0.5
Directann
Figure 2: The landscape of F(W1) and (W1, W2) with different penalty constant 7 = 0.1, 50 in representation learning. The orange terrain is F(W1), while the blue surface is (W,,,, W2). The black line is the trajectory of PBGD which converges to the global optimum of bilevel loss.
model, when learned from the validation dataset, also achieves good fit on the training dataset. This ensures that there are hidden patterns applicable across training and validation datasets so that a generalizable backbone model exists. Note that although we employ a two-layer neural network structure to model both the backbone and adaptation layer for representation learning, our analysis is adaptable to multi-layer neural networks as well. To this end, we make the following assumption.
Assumption 2. For any 61, E RR there exists (W WS) being the (f1,e2) solution to the bilevel representation learning problem (8) such that Ltrn (tr. W2) - -iin,, Ltmn (W1, W2) S 62.
Assumption 2 ensures that the bilevel problem has at least one full-rank solution WI so that is not degenerate. We present some sufficient conditions for it in Appendix F1
To solve 8 we resort to its penalized function as stated 6 with the upper-level function f(u, 1, W2), Lval [1,,
and the lower-level objective g [u, v) Ltrn (W1, W2). which is defined as
(W1, W2) == (W1, W2) + 7 ( W1, W2) - (i,))))))
(9)
where Lig (W1) = minw, Lim (W1, W2). Then we can run PBGD with (u, v, w)) = (W,, W2, Wa) where W3 R is an axillary variable used estimate the gradient of the value function.
To verify the global convergence condition (2) we first observe that both (wa, W2) and Limn (W1, W2) are in the form of a quadratic function composite with a linear mapping. More- over, we find that Lin,W, = 0 if W is of full row rank and W will maintain full row rank on the trajectory generated by PBGD, so that Lirn W2) - (Wi) will be in the form of a quadratic function composite with linear mapping along the optimization trajectory. Therefore, Observation
2 implies that (W,, W2) is a PL function. Figure 2 shows the landscape comparison of F(W1) minw,es(w,) Lvai (W,, W2) and (W,, W2) in representation learning. From Figure 2 it can be seen that the nested bilevel function F(W,) is nonconvex and discontinuous, while the penalized loss L, W₂) has a smoother landscape, effectively steering the weight matrix updated by PBGD towards the global optimal solution. Formally, we have the following lemma.
Lemma (Joint PL condition and descent lemma over trajectory). Let X., = [Xvaii Xrmu be the concatenated data matrix. Then under Assumption 2 if oz (W+') > O, of (W+) > O, the joint PL inequality holds with
μış = (o (WF) + oin (W7)) (Xx,), that is |IV (WT. w 2 2pm (L,, (L, Wh)
min L,1,,, W2)). W.,W2
The descent lemma holds with La defined in (51 and || being the estimation error of VL;(W+)
L, (W Wh++) S L. (W wh)
Lx) (W w + G + a ab2z)) 1162112.
To this end, using the joint PL condition together with the standard descent lemma leads to one-step contraction in the optimality gap of the penalized objective. Through induction, we can then establish the lower bounds of (W.+) and oi.n (W²), as well as the upper bounds of o (Wf) and a ( (W*). Consequently, these yield k-independent lower and upper bounds for μu and Lx. which enable us demonstrate the almost linear convergence of PBGD.
Theorem 2 (Global convergence of PBGD for representation learning). Under Assumption 2 and choose 7 = (0(-00.)) T3 = (log(e-))) there exists μ = O(7), T, 0(y), a = 0(1-1), such that μk 2 p. La S L, and the iteration complexity of PBGD in Algorithm 7 to achieve (c,c) global
optimal point of the bilevel representation learning problem ( is Ollog"
8

---

Published as a conference paper at ICLR 2025
5 GLOBAL CONVERGENCE IN DATA
Data hyper-cleaning aims to leverage a small, clean validation dataset to enhance the quality of a larger training dataset, which may be hindered by some noisy or unreliable data points. This process is widely used when the access to clean data is costly but the noisy data is not like in recommendation systems (Wang et al.
2023 Chen et al. 2022). To do so, we are given a training dataset {z,, Vi Pimi with data sample 2i E and label Us E RR., where each label may be corrupted.
We are also given the clean validation data { 3k J to guide the training. Let E R be the classification vector trained to label the noisy data and W E <Rmx be the model weight, the bilevel problem of data hyper-cleaning is given by min
Li= _. WY?, s.t. S(u)
arg minw 2 Zi-1 (y, x W)² where U = [-ū, ūj is used to avoid trivial solution U4 -00 and 17(-) is the sigmoid function.
Let Xum = [11, ... IN E RNNM Xval= [1. [ E Xmm, Yim = Iy..... - wN] T
RNxx Yval = 19...... UN. E IR xn be the training and validation data and label matrix. e (-) denotes the diagnal matrix of element wise sigmoid function and v denote the elementwise square root operator. We can formulate the data hyper-cleaning problem as the following bilevel problem
1 2 Vee(()) (Yum - Xum Xmml) (10)
|| Yeal - Xva WI1,, s.t. S(u) = arg min W
min NEW, WES(W))
Note that for data hyper-cleaning, where the primary concern involves the interaction between the classification parameter u and the model weight W, we adopt one-layer neural network structure for simplicity in notations. Nonetheless, our results can also be extended to multi-layer linear networks.
We consider the overparameterized case with m 2 NN To model a corrupted training setting, we assume the concatenate data matrix [Xvali Xtrn] is rank-deficient so that the training and validation objectives do not share a common weight minimizer, but there exists a parameter u" E 2 such that the selected concatenated matrix [Xval v N (u*) [ is nearly full rank by neglecting the rows with small (i()), meaning that rank ([xvati / (u" )xem)))))))) = N + N' - [t: ((u)) < $ where d 0 is threshold close O and denotes the cardinality of the set {t: ((f)) < w)
Let us denote (u, W) = 1 / VN (Yim Xtm I? and the value function in data hyper- cleaning as E (u) minw Luo (u, (1, W). To solve (10), we resort to its penalized reformulation
(u, W) = (v) + (feralu, W) (f (u)).
(11)
Then we run PBGD with (u, U1 v.,...) w) (u, W. Z) where Z E Rm is axillary variable used to estimate Ven (u) (u). Since both (val(W) (W) and frmn (u. W) are in the form of strongly convex functions composite with linear mapping, (u, W)) blockwise PL with respect W from Observation 2 To prove the blockwise PL condition over u, we first show that S(v) is independent of u and obtain the form of firm (u) by plugging in the closed form of Suu), for which we defer the details in Lemma 23 in Appendix G.I As a result, the penalized objective has the closed-form expression as
(u, W) (W) 7 Σ (bu))
|IuT x WIF ((Xtm Xtull # 11)-
(12)
Thus the landscape of (u, W) over u is fully characterized by the sigmoid function, which is PL on E U. Consequently, (u, W) is blockwise PL. We formalize our findings in the next lemma.
Lemma 2 (Blockwise PL condition). If XernX is a diagonal matrix, then for any u e U and W. there exists Iy 12 = O(7) such that Ey (u. W) is s3.-shh and 12 over W. Moreover, (u, W) is ylera (W) smooth and 7e(W) w(a))² .PL. over u E U. where
c(W) = =min { {IIvT- - w11 ll 1 ([X Xtakk # 1) >
is defined as the lower bound of the positive mismatch in the training loss.
Although the blockwise PL constant of & (u, W) depends W. we can derive uniform positive lower bound of μ., := min c(W, (u)) based on the acute matrix perturbation theory, and thus, we can obtain the global convergence results for PBGD (Algorithm 2 data hyper-cleaning problem.

---

Published as a conference paper at ICLR 2025
Iog (uppardood crno)
0.1
Fn Dower deve ltte)
10
50
50
100
-10
-10
1000) 2000
Iteration K
3000
Diemiion K
Iterztoon
10
20
Ieeration
(a) (Wi, W2) Li (b) Lirn (Wi, W2) Li. (Wi) (w)
Gasl
(d) Eten W)
Grn (u)
Figure 3: Relative errors upper-level and lower-level in log scale of PBGD versus iteration K under different 7, where Lial "eeesW,WeSWWW (Va W2) and Ex =
mess, (W).
(a)-b) are for PBGD i representation learning, and (c)-(d) are for PBGD data hyper-cleaning.
aglilaatiee apper lond kme))
00
FooD BOME
Jopiebatiee upeelend
Salicattee sppordooo
SOMB
10
1500
200
400
100
400
600
Figure 4: Relative emrors in log scale of different methods under different stepsizes in representation learning. (a)-b) are ablation study for stepsizes a, PBGD, and (c)-(d) are for different methods.
Theorem 3 (Global convergence for data hyper-cleaning). Suppose [Xumi X [ Xval is diagonal matrix. If the stepsizes Algorithm 2 satisfy a S t. O(177), 3 (log(c-1)), and ū 2 1, then the iteration complexity of PBGD in Algorithm global optimal point of the data hyper-cleaning problem 10 is O(log( 127)).
, E Th. = to achieve (c, c)
NUMERICAL EXPERIMENTS AND CONCLUSIONS
We verify the global convergence property of PBGD for representation learning and data hyper- cleaning with different penalty constant y see results Figure 3 and the detailed setup in Appendix We also conduct ablation studies of stepsizes a, 8 for PBGD and test the performance of other state-of-the-art fully first order bilevel methods (F2SA (Kwon et al. 2023). BOME (Liu et al. 2022 The results shown in Figure We summarized empirical findings below.
H
Almost linear onvergence of PBGD. PBGD with proper stepsizes converges almost linearly to the optimum of bilevel representation learning and data hyper-cleaning, which is aligned with the convergence rate we obtained from Theorem 1-3.
Impact of 7 on optimality gap. Enlarging the penalty constant y reduces the target optimality gap e. consistent with Theorems 1-3, which establish that 7 is inversely propotional to the target error e.
Stepsize sensitivity. Stepsizes a, 3 of PBGD should carefully chosen. Excessively large step sizes may cause divergence, while small step sizes result in slow convergence. Theoretically, Theorems 1-3 provide an upper bound for a, guarantee the convergence of PBGD.
Convergence of penslty-based first-order bilevel methods. All tested first-order bilevel methods (PBGD, F'SA BOME) successfully converge the global optimum in representation learning task in an almost linear rate. This observation suggests that our local Pl--based analysis can be extended to other penalty reformulation-hase algorithms.
Conclusion. In this paper, we proposed two benign landscape conditions for bilevel problems, tailored to isomorphic and heterogeneous bilevel learning problems. We proved that PBGD, in either Jacobi or Gauss-Seidel fashions, converges to the global optimal solution at an almost linear rate under these conditions respectively. These global conditions were rigorously verified in representation learning and data hyper-cle plerninn along the optimization trajectory of PBGD by local non-uniform analysis. The global convergence property PBGD over two applications is thus guaranteed. Numerical results validate our theory and confirm that PBGD is globally convergent.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENT
The work was supported by National Science Foundation (NSF) project 2134168, NSF CAREER project 2047177, NSF ECCS 2412486, and the IBM-Rensselaer Future of Computing Research Collaboration. We also thank Ziqing Xu and Liuyuan Jiang for their insightful feedback and constructive suggestions, which are instrumental in enhancing the clarity and quality our paper.
REFERENCES
Michael Arbel and Julien Mairal. Amortized implicit differentiation for stochastic bilevel optimization. In Proc. International Conference on Learning Representations. virtual, 2022.
Sanjeev Arora, Simon Du, Sham Kakade, Yuping Luo, and Nikunj Saunshi. Provable representation learning for imitation learning via bi-level optimization. In Proc. International Conference on Machine Learning, virtual, 2020.
João Carlos Alves Barata and Mahir Saleh Hussein. The Moore-Penrose pseudoinverse: A tutorial review of the theory. Brazilian Journal of Physics, 42(1):146-166, 2012.
Erdem BIyık, Dylan P Losey, Malayandi Palan, Nicholas C Landolfi, Gleb Shevehuk, and Dorsa Sadigh. Learning reward functions from diverse sources of human feedback: Optimally integrating demonstrations and preferences. The International Journal of Robotics Research, 41(1):45 67, 2022.
Zalán Borsos, Mojmír Mutný, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. In Proc. Advances in Neural Information Processing Systems, virtual, 2020.
Jerome Bracken and James T McGill. Mathematical programs with optimization problems in the constraints. Operations Research, 21(1):37-44, 1973.
Can Chen, Chen Ma, Xi Chen, Sirui Song, Hao Liu, and Xue Liu. Unbiased implicit feedback via bi-level optimization. arXiv preprint arXiv:2206.00147, 2022.
Lesi Chen, Yaohua Ma, and Jingzhao Zhang. Near-optimal fully first-order algorithms for finding stationary points in bilevel optimization. arXiv preprint arXiv:2306. 1rXiv:2306.1483, 2023a.
Lesi Chen, Jing Xu, and Jingzhao Zhang. On finding small hyper-gradients in bilevel optimiza- tion:hardness results and improved analysis. arXiv preprint arXiv:2301.007/2, 2023b.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. In Proc. Advances Neural Information Processing Systems, virtual, 2021.
Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, 2022.
Stephan Dempe. Computing locally optimal solutions of the bilevel optimization problem using the kkt approach. In International conference on mathematical optimization theory and operations research, pp. 147-157. Springer, 2019.
Stephan Dempe, Felix Harder, Patrick Mehlitz, and Gerd Wachsmuth. Solving inverse optimal control problems via value functions to global optimality. Journal of Global Optimization, 74(2):297-325, 2019.
Asen Dontchev and R Tyrrell Rockafellar. Implicit Functions and Solution Mappings: A View from Variational Analysis. Springer, 2014.
Chen Fan, Christos Thrampoulidis, and Mark Schmidt. Fast convergence of random reshuffling under wverpaarametrrization and the polyak-\1 ojasiewicz condition. arXiv preprint arXiv:2304.00459 2023.
11

---

Published as a conference paper at ICLR 2025
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Modee--gnostic meta-leamiing for fast adaptation of deep networks. In Proc. International Conference on Machine Learning, Sydney, Australia, 2017.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-basek hyperparameter optimization. In Proc. International Conference on Machine Learning, Sydney, Australia, 2017.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimilano Pontil. Bilevel programming for hyperparameter optimization and meta-learingg In Proc. International Confer- ence on Machine Learning, Stockholm, Sweden, 2018.
Yuan Gao, Jiajun Yang, Ming Yang, and Zhengshuo Li. Deep reinforcement learning based optimal schedule for a battery swapping station considering uncertainties. IEEE Transactions on Industry Applications,, 56(5):5775-5784, 2020.
Ziyou Gao, Jianjun Wu, and Huijun Sun. Solution algorithm for the bi-level discrete network design problem. Transportation Research Part B: Methodological, 39(6):479 -49044994494 2005.
Robert Gardner. Matrix rank and the inverse of a full rank matrix. URL. Atttss://acuu
etsu. et.su.tdu/ /etpe///e//addeer/00000..../0 hotes/Chapter::
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint 1:Xiv:880.00224::: 2018
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complex- ity of hypergradient computation. Proc. International Conference on Machine Learning, virtual, 2020.
Thomas Nall Eden Greville. Note on the generalized inverse of matrix product. Siam Review, 8(4): 1966.
Zeynep H Gümüs and Christodoulos A Floudas. Global optimization of nonlinear bilevel program- ming problems. Journal of Global Optimization, 20(1):1-33) 2001.
Jie Hao, Kaiyi Ji, and Mingrui Liu. Bilevel coreset selection in continual learning: A new formulation and algorithm. In Proc. Advances in Neural Information Processing Systems, 2023.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147-180, 2023.
Minhui Huang, Kaiyi Ji, Shiqian Ma, and Lifeng Lai. Efficiently escaping saddle points bilevel optimization. arXiv preprint arXiv:2202.0366 2022.
Pei-Qiu Huang, Yong Wang, Kezhi Wang, and Zhi-Zhong Liu. bilevel optimization approach for joint offloading decision and resource allocation in cooperative mobile edge computing. IEEE transactions on cybernetics, 50(10))4228 4241, 2019.
Vaithilingam Jeyakumar, Jean B Lasserre, Guoyin Li, and TS Pham. Convergent semidefinite programming relaxations for global bilevel polynomial optimization problems. SIAM Journal on Optimization, 26(1):753-780, 2016.
Kaiyi Ji, Junjie Yang. and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In Proc. International Conference on Machine Learning, virtual, 2021.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-lojasiewiez condition. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, Riva del Garda, Italy, 2016.
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai. Zhaoran Wang, and Zhuoran Yang. A optimal algorithm for stochastic bilevel optimization via double-momentum. Proc. Advances in Neural Information Processing Systems, virtual, 2021.
12

---

Published as a conference paper at ICLR 2025
Prashant Khanduri, Ioannis Tsaknakis, Yihua Zhang, Jia Liu, Sijia Liu, Jiawei Zhang, and Mingyi Hong. Linearly constrained bilevel optimization: A smoothed implicit gradient approach. In Proc. International Conference Machine Learning, Honolulu, HI, 2023.
Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. A fully first-order method for stochastic bilevel optimization. In Proc. International Conference Machine Learning, Honolulu, HI, 2023.
Jeongyeol Kwon, Dohyun Kwon, Steve Wright, and Robert Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. In Proc. International Conference on Learning Representations, Vienna, Austria, 2024.
Junyi Li, Bin Gu, and Heng Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. In Proc. Association for the Advancement of Artificial Intelligence, virtual, 2022.
Bo Liu, Mao Ye, Stephen Wright, Peter Stone, et al. Bome! bilevel optimization made easy: A simple first-order approach. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, 2022.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In Proc. International Conference on Learning Representations, New Orleans, LA, 2019.
Risheng Liu, Jiaxin Gao, Jin Zhang, Deyu Meng, and Zhouchen Lin. Investigating bi-level optimiza- tion for learning and vision from a unified perspective: A survey and beyond. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2021a
Risheng Liu, Yaohua Liu, Shangzhi Zeng, and Jin Zhang. Towards gradient-based bilevel optimization with non-convex followers and beyond. Proc. Advances in Neural Information Processing Systems, 2021b.
Risheng Liu, Yaohua Liu, Wei Yao, Shangzhi Zeng, and Jin Zhang. Averaged method of multipliers for bi-level optimization without lower-level strong convexity. In Proc. International Conference on Machine Learning, Honolulu, HI, 2023.
Songtao Lu, Siliang Zeng, Xiaodong Cui, Mark Squillante, Lior Horesh, Brian Kingsbury, Jia Liu, and Mingyi Hong. stochastic linearized augmented lagrangian method for decentralized bilevel optimization. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, 2022.
Zhaosong Lu and Sanyou Mei. First-order penalty methods for bilevel optimization. arXiv preprint WxXiv:2001.01766. 2023.
Cong Ma, Kaizheng Wang, Yuejic Chi, and Yuxin Chen. Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In Proc. International Conference on Machine Learning, Stockholm, Sweden, 2018
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-basse hyperparameter optimization through reversible learning. In Proc. International Conference on Machine Learning, Lille, France, 2015.
Akshay Mehra and Jihun Hamm. Penalty method for inversion-free deep bilevel optimization. In Asian Conference on Machine Learning, virtual, 2021.
Hamidreza Modares, Isura Ranatunga, Frank I. Lewis, and Dan O Popa. Optimized assistive human- robot interaction using reinforcement learning. IEEE transactions on cybernetics, 46(3):655-666 667, 2015.
Le Dung Muu and Nguyen Van Quy. global optimization method for solving convex quadratic bilevel programming problems. Journal of Global Optimization, 26:199-219 2003.
Maher Nouiched, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving a class non-convex min-max games using iterative first order methods. In Proc. Advances in Neural Information Processing Systems, Vancouver, Canada, 2019.
13

---

Published as a conference paper at ICLR 2025
Samet Oymak and Mahdi Soltanolkotabi. Overparameterizze nonlinear learning: Gradient descent takes the shortest path? Proc. Interaational Conference on Machine Learning, Long Beach, CA, 2019.
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. Proc. International Conference Machine Learning, New York City, NY, 2016.
Quang Pham, Chenghao Liu, Doyen Sahoo, and HOI Steven. Contextual transformation networks for online continual learning. In Proc. International Conference on Learning Representations, virtual, 2021.
Meysam Razmara, Guna Bharati, Mahdi Shahbakhti, Sumit Paudyal, and Rush D Robinett. Bilevel optimization framework for smart building-tor -ooggiig systems. IEEE transactions on Smart Grid, 9 (2):582-593, 2016.
Alexander Robey, Fabian Latorre, George Pappas, Hamed Hassani, and Volkan Cevher. Adversarial training should cast as a non-zero-sum game. In Proc. International Conference on Learning Representations, Vienna, Austria, 2024.
Han Shen, Quan Xiao, and Tianyi Chen. On penalty-based bilevel gradient descent method. arXiv preprint:2302.05783. 2023.
Han Shen, Zhuoran Yang, and Tianyi Chen. Principled penalty- methods for bilevel rein- forcement learning and RLHF, In Proc. International Conference on Machine Learning, Vienna, Austria, 2024.
Nian Shi and Yi Luo. Bi-level programming approach for the optimal allocation of energy storage systems in distribution networks. Applied Sciences, 7(4):398, 2017.
Ankur Sinha, Pekka Malo, and Kalyanmoy Deb. A review bilevel optimization: from classical to evolutionary approaches and applications. IEEE Transactions on Evolutionary Computation, 22 (2):276-299) 2017.
Daouda Sow, Kaiyi Ji, Ziwei Guan, and Yingbin Liang. A constrained optimization approach to bilevel optimization with multiple inner minima. arXiv preprint arXiv:2203.01122 123, 2022a.
Daouda Sow, Kaiyi Ji, Ziwei Guan, and Yingbin Liang. A primal-dual approach to bilevel optimization with multiple inner minima. arXiv preprint arXiv:2203.01123, 2022b.
Bradly Stadie, Lunjun Zhang, and Jimmy Ba. Learning intrinsic rewards as a bi-level optimization problem. In Conference on Uncertainty in Artificial Intelligence, virtual, 2020.
Gilbert W Stewart. On the perturbation of pseudo-inverses, projections and linear least squares problems. SIAM review, 19(4):634 662, 1977.
Ruoyu Sun and Zhi-Quan Luo. Guaranteed matrix completion via non-convex factorization. IEEE Transactions on Information Theory, (1111))53355 2016.
Davoud Ataee Tarzanagh, Mingchen Li, Christos Thrampoulidis, and Samet Oymak. FEDNEST: Federated bilevel, minimax, and compositional optimization. In Proc. International Conference on Machine Learning, Baltimore, MD, 2022.
Luis Vicente, Gilles Savard, and Joaquim Júdice. Descent approaches for quadratic bilevel program- ming. Journal of Optimization theory and applications, 81 (1(2):379-399 1994.
Guangmin Wang, Xianjia Wang, Zhongping Wan, and Yibing Lv. globally convergent algorithm for a class of bilevel nonlinear programming problem. Applied Mathematics and Computation, 188(1):166-11) 1726, 2007.
Jiali Wang, He Chen, Rujun Jiang, Xudong Li. and Zihao Li. Fast algorithms for stackelberg prediction game with least squares loss. In Proc. International Conference on Machine Learning, virtual, 2021.
14

---

Published as a conference paper at ICLR 2025
Jiali Wang. Wen Huang. Rujun Jiang, Xudong Li, and Alex L Wang. Solving stackelberg prediction game with least squares loss via spherically constrained least squares reformulation. Proc. International Conference Machine Learning, Baltimore, MD, 2022.
Zongwei Wang, Min Gao, Wentao Li, Junliang Yu, Linxin Guo, and Hongzhi Yin. Efficient bi-level optimization for recommendation denoising. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023.
Ming Wu, Lingfeng Kou, Xiaogang Hou, Yu Ji, Bin Xu, and Hongjun Gao. A bi-level robust planning model for active distribution networks considering uncertainties of renewable energies. International Journal of Electrical Power & Energy Systems, 105:814-822 2019.
Quan Xiao, Songtao Lu, and Tianyi Chen. generalized alternating method for bilevel optimization condition. In Proc. Advances in Neural Information Processing
under the colyak-tojasieve Systems, New Orleans, LA, 2023a.
Quan Xiao, Han Shen, Wotao Yin, and Tianyi Chen. Alternating implicit projected sgd and its constrained bilevel optimization. In Proc. International Conference
efficient variants for on Artificial Intelligence and Statistics, Valencia, Spain, 2023b.
Siyuan Xu and Minghui Zhu. Efficient gradient approximation method for constrained bilevel optimization. In Proc. Association for the Advancement of Artificial Intelligence, Washington, D.C., 2023.
Ziqing Xu, Hancheng Min, Salma Tarmoun, Enrique Mallada, and René Vidal. Linear convergence of gradient descent for finite width werrparametrrize linear networks with general initialization. In Proc. International Conference on Artificial Intelligence and Statistics, Valencia, Spain, 2023.
Ziqing Xu, Hancheng Min, Salma Tarmoun, Enrique Mallada, and Rene Vidal. A local Polayk- Eojasiewicz and descent lemma of gradient descent for overparameterized linear models. 2024.
URL htttps://pperrevieeee
net dode:/ooomdddd-ooooooo.. http://...pppaaeeeeeeee/eeeeeee.
Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. In Proc. Advances in Neural Information Processing Systems, virtual, 2021.
Shuoguang Yang, Xuezhou Zhang, and Mengdi Wang. Decentralized gossip-based stochastic bilevel optimization over communication networks. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, 2022.
Tian Ye and Simon S Du. Global convergence of gradient descent for asymmetric low-rank matrix factorization. In Proc. Advances in Neural Information Processing Systems, virtual, 2021.
Runtian Zhai, Chen Dan, J Zico Kolter, and Pradeep Kumar Ravikumar. Understanding why generalized reweighting does not improve over ERM. In Proc. International Conference on Learning Representations, Kigali, Rwanda, 2023.
Yihua Zhang, Guanhua Zhang, Prashant Khanduri. Mingyi Hong, Shiyu Chang, and Sijia Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. In Proc. International Conference on Machine Learning, Baltimore, MD, 2022.
Difan Zou, Philip M Long, and Quanquan Gu. On the global convergence of training deep lincar resnets. In Proc. International Conference on Learning Representations, virtual, 2020.
15

---

Published as a conference paper at ICLR 2025
Supplementary Material for Unlocking Global Optimality in Bilevel Optimization: A Pilot Study
Table of Contents
Additional Related Works
B Auxiliary Lemmas
17
C Proof for Examples I and
19
C.I Proof for Example
19
Pl. functions do not preserve PI. condition under additivity in general
20
C.3 Nonconvexity of (u)
21
D Proof Theorem 1
22
D.I Proof under the joint PL. condition
22
D22 Proof under the blockwise PL. concition
23
E Proof of Observations 12
25
E. Proof of Observation
25
Proof of Observation
25
Proof for Representation Learning
F
Sufficient conditions Assumption
................................
26
F2
Landscape nested bilevel objective F(W1)
................................
27
F3
Preliminaries penalty reformulation
28
F4
Proof of Theorem
31
F35
Proof of Theorem
37
G
Proof for Data Hyper-cleaning
41
G.1
Independence of the lower-level solution set S(u)
41
G
Proof of Lemma [] Local blockwise PL and smoothness
................................
42
Lipschitz continuity solution the penalized problem
44
G.4
Global solution relations data hyper-clcaming
45
G.5
Parameterized data and label matrix family acule
................................
46
G.6
Monotonicity of loss functions
47
G.7
Gradient estimation error
50
G
8
Proof of Theorem|3]
51
Numerical Experiments
52
Representation lcarning
53
Data hyper-cleaning
53
A ADDITIONAL RELATED WORKS
Stationary point convergence. The recent interest developing efficient gradient- bilevel methods and analyzing their nonasymptotic convergence rate has been stimulated by (Ghadimi & Wang 2018 Ji et al. 1021 Hong et al.) 2023 Chen et al.] 2021). Based on different Hessian inversion approximation techniques, these algorithms can be categorized into iterative differentiation
(Franceschi et al. 2017 2018 Grazzi et al., 2020) and approximate implicit differentiation based approaches (Chen al.
2021: Ghadimi & Wang 20088 (Hong al. [023] Ji et al.) 2021| Pedregosal 2016). Later on. the research has been extended to variance reduction and momentum based methods
(Khanduri et al.
2021
Yang al. 2021
Dagréou et al. 2022;; warm-started algorithms (Arbell
16

---

Published as a conference paper at ICLR 2025
& Mairal 2022 Li et al. 2022 Liu et al. 2023); distributed approaches (Tazzanagh et al. 2022
Lu et al. 2022.
Yang et al.
2022): ; and methods that are able to tackle with constrained (Xiao
lower-level problem (Xiao et al. 2023a Liu et al. 2021b at Chen et al. 2023b; Sow et al. 2022b). Recent works have reformulated the bilevel optimization problem
al.] [202bb Khanduri al.
2023 Xu & Zhu 2023) non-strongly-come
single-level constrained problem, and solved it via the penalty-based gradient method (Shen et al. 2023); see also (Liu et al. 2022, Kwon et al. 2023] 2024, Chen et al. 2023a Lu & Mei, 2023). This method not only further enhanced the computational
efficiency by using only first-order information, but also broadened the applicability of the bilevel framework to a wider class of problems. Nevertheless, none of these attempts the issue of global optimum convergence.
B AUXILIARY LEMMAS
Additional Notations. Let matrix A E R=xx" The range space of A is denoted as Ran(AA = {Ay : R. while the null space of A is given by Ker(A)= = {y E R" AA 0}. Let Asj represent the element located at the i-th row and j-th column of matrix A. Let ||| and || be the Frobenius norm and spectral norm of A, respectively. [B,,,) r) == {A' E Roxq || All S a}
denotes the closed ball with center A and radius Let 0 E E be point and S E be set, we define the distance of 0 to as d(0, S) = inf infillo - all E S}. Let us denote lm = Im Xtm W|] 1² (aa(W) = 2 V - x W|| as the square loss.
Lemma (Matrix Inequality)-
B) < |||| ||B|,
(13)
A|| ||A|] + ||B|1
(14)
||B + CDI|2 < [ (A) + onax [[IB3 + [D]]3)
(15)
| |1| < 2|| B1F
(16)
max (AB)= < max maax(A) (A)o (B).
(17)
Moreover, if A has full column rank and B + or if A + 0 and has full row rank, it holds that
miin ( (AB) 2 min (A (A)ominl (B)
(18)
Lemma 4 (Zou et al. 2020 Lemma B.3)). Let A E Rexe be runk-s matrix. Then for any B E Rxxy we have
Mmin BI) |AB|| & (mxx(A))
Lemma 5. In representation learning, we consider the overparameterized wide neural network case max(m,n) and Xum. Xval are full row rank. Therefore, we have,
with m 2
min lum (W) = min Ltm (W1,W) 0, min (v) 0, min Lva(W1, W2) 0 W
W.,Wz
W
W.W22
min(Cmm + +lva)) min (Ltrn + YLeen))Wi W2) W,
holds for any 7. Moreover, for W1 with amin minw, Lem(W, (W1, W2) 0
O, it holds that (ii(
Lemma ((Karimi al., 2016, Theorem 2)). We say a fanction hu(0) is μh PL if satisfies ||V(0)]| (p)(h(()) - ht")
where h* min h(0). If (()) is L, Lipschitt smooth and PL in 0 with μh. then it satisfies the error bound condition with phy i.e.
VV(()) 2 p))
(19)
where S = arg min h(0). Moreover, it also satisfies the quadratic growth condition with Ph. i.e.
4h S)².
h(0) h
(20)
2
where h² min (()). Conversely, if h(()) L Lipschitt smooth and satisfies the error bound condition with pho then it is PL. in with us/ Tup.
17

---

Published as a conference paper at ICLR 2025
2019 Theorem 5.2)). Suppose that h(0) is La Lipschitz smooth and μA PL over B. If we execute step gradient descent following g = 3Vh((')
Lemma 7 (Oymak & Soltanolkotabi
with 3 < I the output satisfies
h(0²) min h0)) S (1 - Bum)* (h(00) min h()))
Moreover, the iterates generated by gradient descent is bounded, i.e.
100 0oll 110+1 - -0ele, 1 (8(h(B)) min h(0))
The following lemma gives the gradient of the value function.
Lemma 8 (Nooiiehed al., 2019, Lemma A.5)). Suppose g(u, v) is Mg PL over v and is g61 Lipschitz smooth, then 9 (u) is differentiable with the gradient
Vgg (u) Vug(u, v), Vu E S(u)..
Moreover, 9" (u) is -m-stmoth with Lg = () + fg/22g))
Lemma 9. If f| S 8 and min (W+) > 0, mmin (W2) > 0, then the following inequalities hold 2 2 L, ( W + 5v)) Vw,L. | < IVL W + 12 + VL, 11?
(21)
|| w. w (W W + 6k)) Vw,L, W
< 20 max (Xa) max (W* (L. (W w L + max (WT) (X,) W/) - LT)
(22)
[1(w,, Wx) + 6x) W + W W.V WWW w
< (o (W + o (W?)) V 20 max (X,) (L, W LG) + 80 max (W2)
(23)
Proof:
21 holds from [4 by letting A = Vw, (W7 w + 6y and B = Vw,L,(WH, Wh).
Note that when miia (W+) O, miin (W2) 0, we have L, LWF W = L,t,, (WF,W?) = (WW+) where by = Eval + Teamn Thus (22) can be derived from
w + 5k) WW, w VW,, < Vw, Lw W (W V whll|
Ve, (W**)(W))) [O whll
<
+ (
< 0max ( ( max (W (W*'))
(3)
20 max (X,) (L, w - L.)) da max (W+) v 20 20
w L7)
where W W and (a) holds because ey is o² o (X,)) smooth so that
|V [W*)W)) < 20 (X,) (W.
20 mux (X,) ( - L3). (24)
Likewise, derive 23 similarly by
W + 5&) W + WW,,, whyll
TwiL(WH W:th do (W/) + [W/Vv,,,,Wt, w
(e, w + d0 (W3) + ([: (V,,
2 (W + 2 (W/))
[W**) + 50 50 (W:)
C (W+) + 2 (Wz)) / S (X, (L, (Wk W/) - LG) + S0 (W
18

---

Published as a conference paper at ICLR 2025
Lemma 10 (Pseudoinverse of matrix product). For two real matrix M1 E m and M2 E Rm if M1 is a diagonal matrix and is invertible and M2M2 is diagonal, then have (M, M.
Theorem 2), (M, MIMM MIM, holds if and only if both M, M2,M and M, M, M,M, are Hermitian matrix. As M1 and M2 are real matrix, it remains to prove that both M/ M1 M2M and Mi M1 MMM are symmetric. By the invertiability of M1,
Proof: According (Greville 1966
M,M, M.'MMMMMM " M,M, M2
so M M2M symmetric.
For Mj M, M2MM the starting point a fact that diagonal matrix is commutative with diagonal matrix. This is because for diagonal matrix A1 and diagonal matrix A2, it holds that
A (A]AT) (A2A1) A2A1
where the last equation is due the symmetricity of A2A1.
Since both MtT M1 and M2 are diagonal matrix, we then have
Mt M M2MIMM M1 (M M,M)
so that MTT M1 M2 is also symmetric, which completes the proof.
Definition 3 (Stewart 1977 Acute matrix)). Let PA AAt, PB BBt be the orthogonal projection matrix onto the range space Ran(A) A) and Ran(B). We say matrix A E Rmxa and B E Rmxa are acute if [| PB < 1. Moreover, class of parameterized matrix family {A(u)}, E U. is said to be acute if for any u', uu E U, A(u') and A(u²) are acute.
Proposition Stewart 1977))
IfA E Rmxx and E BRxx are acule, then (an(() = Ran(Ba (B).
Lemma 11 (tewarr 1977
Theorem 2.5)). Matrix A E Rmxn and B E Rmxn are acute if and
only if
rank(A) = rank(B) (ank(P
where PA = AA', A A are the orthogonal projection matrix onto the column space Ran(A) and the row space Ran(A").
Lemma 12 (Rank equations (Gardner)). For A E RR B E Roxp, C TRPx9, if A is full column rank, and C is full row rank, then holds that
rank(AB) rank(B), rank(BC) = rank(B).
Moreover, for any D E m rank(DDD) raan(an)))
C PROOF FOR EXAMPLES AND
C. PROOF FOR EXAMPLE
The gradients of the two objectives in Example can be computed as
Vu u - (i) (u - 2 sin cos(v)
11 - v -(u-w) v)
and Vg(u, v)
Besides, also using the fact that min,,r s(u, w) = min g(u, v) = 0. we have
[V w) = (u 2sin(r))² x (1 + (2)
2 2 x 2
(u (osssin))) = x f(u,,) - min f(u, t))
19

---

Published as a conference paper at ICLR 2025
Not convex!
-00
(a) g(u, u) for Example 4
(b) fu, v) for Example
(c) F(u) for Example 4
Figure 5: Visualization of g(u, u), [u, v) and F(u) in Example
(u u)= w)² x (g(u.)) u) min g(u, v) a.e
Vg(u, w)| = 2(u - o)² 2 4x
2
which suggests f(u, u) is 2-PL and g(u, v) is 1-PL. The lower-level solution set is earned by setting u v. In this way, the overall objective is F(uu) = S(,))(w) 3 2 sin( u1)² and is minimized
when u = 0. By calculating its gradient (u = (u 2 2sn (i)) cos(:)). we have
[VF (u 2 sin u)) (1)
cos( (2))²
Since (1 2 cos( = 0 when u 3 + 2kT, k E Z. Thus, there does not exist μ >> 0 such that [VF(2)] = -u - 22innnn (2) 2 cos(w)) u)) 2 (p(((u)) - min F(u)) = p(u - sin(u)
holds for any u. This means F(u)) is not PL in u.
C.2 PL FUNCTIONS NOT PRESERVE PL CONDITION UNDER ADDITIVITY IN GENERAL
Let's take look at similar example with Example | that is joint PL at both levels.
Example 2. With u E R and E I, consider the following upper and lower-level objectives
1 f(u, v) = (u -u--imn sin()) and g(u, v) - u)
We can verify that both (u, and g(u, v) satisfy the joint PL condition in 4 and the lower-level problem parameterized by u yields the unique solution S(u) = u.
The following lemma shows that joint PL upper- and lower-level objectives can lead to non-joint PI. penalized objectives.
Lemma 13. In Example _ the joint PL. condition on both levels does not guarantee the joint PL
condition Lu(,, v); see also the landscape of the penalized function shown in Figure o
Proof: For Example as (u) 0 for any u. the gradient of L, v) can be computed as
(u, = u 2 sin + 7 - v)
-2 2 sinn cos(v) -ru v) ]
On the other hand, (u, v) is minimized when u 0 with the minimal value O. For any there exists (ū, 0) with 2v 14y.
2TT such that
ū 2 2sn + + - 1)
0
(u,
2 (ū 2 (T)) cos(T) 7 8)
However, L. (ū. 8) ] (a - 22) + (ū - 7)² > 0 = min,, L(ū 8). This means that saddle points (ū. 6) exist for any 7 that L, 6) does not satisfy the joint PL condition.
Similarly, the following example shows that blockwise PL conditions on upper and lower-level objectives are also not sufficient to ensure the blockwise condition of (u,
20

---

Published as a conference paper at ICLR 2025
Example 3. With E R and v [11 U2l E RR, consider the bilevel problem with the following blockwise PL upper-level objective f(u, v) and the blockwise PL lower-level objective g(u, v). i.e.,
u + - f(u, v) 2 2
1
and g(u, v) = (u+ uutur u1 + sin(v2))
2
where ("))= O. However, the penalized loss function Ly (u, v) is not blockwise PL. The landscape LfL,(u, 1) when 11 2 is shown in Figure 6
Proof: The gradients of two objectives in Example 3 can be computed as
1 (2 + 01 - sin(v2))
(u + un + +in((2))
VS(uv)) =
(5 + U1 sin(02))
and Vg(u,v)= =
(u + u1 + sin(ey)
- (5 + sin COS(U2)
(u + + sin cos(U2)
We first verify that both fu, v) and g (1, v) are blockwise PL. As 21 sin( 21 + (2) spread out in R, then both 7 + v1 - sin((z)) = 0 and u + en +in((2>) = 0 always have a solution. Therefore, we have min, f(u,,) min, [u, u) min, g(u, u) min, gu, v) 0. On the other hand,
V x)122
4 + sin((e)) 2 (f(,,)) min f(u,
1 ("
V.f(uu x0)12 _ + 01 sin(v))
x (1 + cos2 (12)) 2 2x (f(u. -min f(u, ui)
[V,g(u, 1) (u + 1n + sin(v2)) 2 x (g(u, u) min
Veg(u, o)[?² = (u + 2 + 2in(vz))² x (1 + cos (v2)) 2 x (f(u, 2) min f(u, 01)
which suggests both fu, v) and g(u, v) are blockwise PL. For any 7, since g" (u) = 0, V.LLy (u, v) gives the equation
1
2 sin(w2) 0. + ( 2
( + 4 " + 7
(25)
can be verified that both u = 21 = 1/2 = and u = 47+1" U1 = 2, = 0 are solutions to (25).
4+88
which yields two different objective values Ly u) 0 and Ly(,, v) 8, This means there
(4++1yz-
exists saddle points for (u, 1)) so that (u, 2) is not blockwise PL over u. Same phenomenon happens for v, suggesting that (2, u) is also not blockwise PL over u.
100
100
200
50
100
100
0
13
10
-10 -0
12
(a) 7 = 0.5, Example
2
(b) 7 = 1, Example
(c) = 0.5, Example
(d) 7 1, Example
Figure 6: Visualization of L,, (u, v) in Example 2
and 3 Saddle points exist for L, u) in Example
and Example
3
suggesting that penalized objective does not satisfy the PI. condition.
C.3 NONCONVEXITY OF F(u)
Example 4. With u E R and o E IR, consider the following upper and lower-level objectives
f(u, ((, = is obvious that both fu, v) and g(u, v) are jointly convex with regard to (u, v) and minimizing the
and g(u,u) = c" + (u++ +
lower-level problem parameterized by u yields the unique solution S(u) {v 44uu + +e" = 0). However, the overall bilevel loss function F(u)
= S(u) is not convex over u. A
visualization of F(u) S(u) is shown in Figure
21

---

Published as a conference paper at ICLR 2025
Proof: Let calculate the gradient and Hessian of f(,, b) and g(u, 2) in Example 4 by
0
4(u + o)s
v),
and Vg(u,
4(u 7) + e²
0 0
and (() = 12(u + u)² 12(u + u)² 12(u w) e²
0
From the Hessian, both [(u,, v) and g(u, v) are convex because the determinants of all x k submatrix are nonnegative. Besides, the lower-level optimal solution is obtained by letting 4(u+v)² +e" O. Since when fixing u. 4(u + v)3 + e" is strictly increasing with respect to e and spread out over (-oo, 00), the solution set S(u) (u 4(" + v)3 + e" = 0} is unique and nonempty.
We will then prove F(u) not convex by contradiction. We choose u
and 1
then S()) {v 4(u v)8 + e" 0} 0 and S(ū) = { 4( v)s + ee =03 1, so that
F(u) = f(V 4' 0) = and F(ū) = f( - 1,1)
Assume that F(u)) is convex, and thus the function value F(ū) at the medium point ū w+ 3 7-11 satisfies F(ū) < F(w)+F()) 1. which means there exists v S Y such that 4(ū + 3)3 - = 0. However, 4( + e)3 + c is strictly increasing and
3
1 2
4(U + u)² te" lu=1/2 =4
+ed = 0007 0.
2
So for any
1. 4(ū + v)3 e" O, which yields contradiction, and thus, F(u) is not convex.
D PROOF OF THEOREM
Lemma 14 (Gradient bias). Under Assumption
1 denoting dt (u++1 w/)/ we have
22 a (1 Bpg) (g((", " - g" (u²)).
llat VuL,(u )1
(26)
fg
Proof: First, according to Lemma g comes from the inexactness of the value function's 's gradient, i.e.
( V ( v), Vo S(u). By the update rule, the bias
- V.L,
Vg (u²* Vz(u", w x s rlyd(w k+1 , ,((tt)).
(27)
According to Lemma and Lemma 6 we have
2 2 (1 Bu,) Buy) (g("",, w²) - 9" (u²))
d(w^~1 S((tt))
<
P'g
from which plugging into 27 yields the conclusion.
D.1 PROOF UNDER THE JOINT PL CONDITION
From Lemma g we have the smoothness of g" (u) and thus Ly(u, v). Therefore, by defining
di (u u a/a and by Taylor expansion, we have
Ly (u 6+1 x1 S L. (u/ ,,*)) + (VuLy x*),, k+ utt + ( (VoLy (ut,, 2rt), w x²))
+ Ey +lg L.g) || ++1 11122 ey + 7 Lgg) |1 1111
x ).d))))))))))) - (a (e, + (6g (e/+>(l =g)))aa)
$ (n, ,
- - a a.V (u,,),,,
1/V.L, 2))
2
22

---

Published as a conference paper at ICLR 2025
+ (ly + 1(4, + +,,))²² ||
2
(a a
(Cs + +lg + Lol]aa l1ati1?
= L, ,0)) - 3/1 1 ,t)
2
2
(4y+ + 7lgg + Ig]]a²
a
|| VoL (u*, 2 )² +
ah
Ilat (uL, 1111
2
2
L,
a
2 (u
2
a72 62
+
911 B11)) Th (g(u", w²) -0- ))(
1gg
VL )12 + e
= (uM,
2/2
a
2 (1 - 3pm) Th (glu" ( - -g((1())
2
Mg
Lu oth) (L, xt min (u, + e u.v
2 (1 (1- 3pg) (g(u", w²) 9" (ut))
Ug
where (a) is because S +Lo and Lemma
14 and (b) is because of the joint PL. condition.
Subtracting both sides by minn, (u, v) yields
Lu 1oke+,1ot)))) min L, (u, v) S (1 - aau)(( 0*) -min mm v)) 6,0
26 2 (1 - 31n) 2h ( (o(u", w - (²(xt)))
My
Letting Ti = log (2" and telescoping the above inequality yields
L,(u* (uk) min (u(u)) v) S (1 - (1-aw) (k 00 min min (u, v)) Σ (1- ((ae)
(009)mmmLLyyp 0,e"
x (1- (1-)44 K (L, v0)
min min v)) + O())
0ee
On the other hand, according to (Shen et al.
2023
Theorem 1) and denoting Ey := glu* uk)
g" (u)),, we have for any E1 and y 2 2n = 1 c the following
7,04
c+c (c)(++ and S(u w - s(u, w) S (1 - a1-) (L, (u,, 97004
e S 7 7-"
S
(L.a v0)
-min (u, 1100
(u, e)) + (c))
holds for any (u, v) satisfying g(u, v) - ge (u) S Ey. The choice of 61 = O(v{) gives ey = O())
and 7 = O(c-0.6) which completes the proof.
D.2 PROOF UNDER THE BLOCKWISE PL. CONDITION
Define (u( = min, Lu, v) and (u) = arg min, (u, v). According to Lemma Vug(u, v), Ve E S(u). Since Lu is (l, + +76)) smooth over v, then according to Lemma g we also have (L) = (ul,(u,
V
v), Vu E (u). Moreover, (,( is Ly smooth with L., (E, + (1 + (l, + 241) + bug Also (1) is PL with nv because L, (u, v) is blockwise PL. over u.
If we denote dt. = (u - wt)/a, then by the update rule, the bias comes from the inexactness of the value function's 's gradient, i.e.
| VL; = IIV u Vn,(ut, + Vu mtt1) Vg(u*, .v,)ll
+ +>ll w - vo(utt rill
$ (l, + ( ylyd(w x4
S((²))
where uy (.,( 1 u S(nt).
23

---

Published as a conference paper at ICLR 2025
According to Lemma and Lemma 7 we have
2 (1 - (11g)* (g(u² = - 9" (2(²
d(w ((u+t,s(u"))" )(ux)))² v
B4
2 (1 Bpo) (Ly(u* w²) 1;(1)))
d(c (u
=
Mv
As a result, the bias of the gradient estimator can be bounded by
A(ls + xgg)² (1 BPo)) = (L, w0) (,(()))
l (L;(1>)1
Hoo
472 (1 Bpg)) Th (g(u* u0) - gg(("))
(28)
Mg
Therefore, by Taylor expansion and the smoothness of (1)),, we have
(i ) S
(w²), (VL; k+1 - -ut)
L
- 11
1|
2
S <L5(w²)- a (VL da) + Lga2
l1d
2
L3(4*) 2 |VL; (u
112
2
-
+ ah ( (u+)) - 1 + I,aa ||dt!1?
2
(1(h)) - |V || 2a(1s + )
(1 - Bym, (L,( - L;(
Hv
2 2 (1 3p()) To (g(u", -
- (1(1)
(8)
0)) + 20(le + rlg)²
Li (xtt) afpa (L;((L min Ly (u, uee
(1 ]th (L, - L;((t²))
20 9 (1 (11g) TTe (g(u", w²) -" (2(1))
Ug where (a) is because a S +, and Lemma 14 and (b) is because of the PL condition of Lz)
Subtracting both sides by mina, L,(u, v) yields
Li min Lu, v) S (1 - aap (L² min Lu, v)) u,
u,
2a(e, + 7l))2 (1- BB,,) (L, w0 -L;))((((t)) L((tt)
+
My
20 9 (1 Bpg) Th (a(u", w0) - g" (u')))
14g
When Me O(7). the last term is dominating over the second term. Letting Tç log 7 (la(a","")>'"" and telescoping the above inequality yields
((((+1)- min L, (u, r) < (1 - app) (1-a ( (L7 - min (u,,,) w)) + O(c)
Combining with the results of
Ly(u,, ex+1)- - Li (u+) < (c) and (u+ (utt1,,8t2) (i
s 50(()
we know that Lu(",, y K+1) min Lu v) < (1 apun K (L, min L, v)) + O(E)
On the other hand, according to (hen et al.
2023
Theorem 1) and denoting by == gluk uk)
g" ),, we have for any 61 and y 2 27
G 1 the following
1
c + 8c(e+te) and fluk, (() f(u, v) < (1 (aj1-aj)KK (lj))((L((t)))) ( min Lin u,e
G S 7-
O())
holds for any (u, v) satisfying g(u, v) - g" (u) S e.. The choice of e = 0(ve) gives e, = =(c)
and 7 = (cc-0.5) which completes the proof.
24

---

Published as a conference paper at ICLR 2025
E PROOF OF OBSERVATIONS 1
E.
PROOF OF OBSERVATION
Proof: The blockwise PL condition of ((((u, v) - g"()) over e is obvious under Assumption I
because 9" (u) is independent of v. On the other hand, with Assumption the gradient of (g(u, 9" (w)) can be lower bounded by
v) 9" (2)))]2 V2lVV v) - Vug" V.
> Vl, w)1
1 IvE
7Ml(7 0) - g²(())
" v) - - (u)) minn(g(u, gg"(4))
where (a) because g(u, v) is Mg PL in v and (b) is due min,,, r(((u,) (u))
E.2 PROOF OBSERVATION 2
The result that fi (Az) and h (Bz) satisfy the PL condition is well-known; see c.g. (Krimi et al. 2016, Appendix B). We will show h1 (Az) + h2( (2) satisfies the PL inequality. For arbitrary 21, 22. we denote U1 = A21, u2 = Az2, = B21, U2 = Bz2. By the strong convexity of h2 and h2, we have
hn (Az2)) (Az)) (m1( (O0)((AAA (Az2 A2i) + MI
|| Azal1
2
(B 2 (B2) + V12(v1) T (B22- B21) + #2
[2 B32 112
2
By the fact of (Azz) A 4h, (u:) and F/ (B2,) B Wh2 (v:) for 1,2, we get
h1 (A22) 2 h1 (Azi) + // (Az)) ) (22-21) +
2 | - A
(29a)
h2 (22) 2 h22 (B2) + (B2) T (22 - 21) + 1/2
B21 B22l1
(29b)
2
Letting 2/2 = Proj z- (21) be the projection of 21 onto the optimal solution set Z arg min, hj (Az) h2 (2)). Clearly, 22 is the solution of
min " || 21 112 s.t. Az A=", Bz Bz*
(30)
where: =" E arg min, hn (Az) ha B2) is arbitrary optimal point. Strong duality holds for 30 so that KKT conditions must hold at 22, i.e. there exists d1 E Rm A2 E RR" such that
22 B =.
A
B
(31)
Without loss of generality, we can consider only two cases: i) Ran(AT) = Ran B )); and, ii) Ran(AT) 1 T.. Otherwise, we can decompose Ran(B [ T) into the direct sum of two orthogonal subspaces: one parallel and the other orthogonal to Ran(A R...
For Case i), is clear that 22 21 E Ran AA ) and 22 21 E Ran TT) by (3).. Therefore, letting
C" = ()oo((A) + u2o and adding 29a and 29b up yields
C' 2
(1(2))) + h2 (Bz)) 2 h1 (Az1) + (B21) + (4)((A2)) + Vhg( (22-222-)00 - 21) +
|| - =2212
C"
2 (Az1)) + 12 + min
(Az, (h,, (2 - 21) +
- |z - =11??
2
= hA1(A)) + h2(12)) (h1 + (h2
(32)
For Case ii), since A \1, BT E RAT(AT) RT by (1I) we have
21 22 A T BT)a Span(Ran(AT)) Ran(B )).
25

---

Published as a conference paper at ICLR 2025
By definition, there is finite number of orthogonal e; E Ran(AT) U Ran(B") and of ag R so that 21 - 22 = 01 U1 + ..... + 0g As each v is either in Ran(AT) or Ran(B") ) and they are orthogonal, we have || - 22 Σi= || 2 and we can focus on each of v independently.
Let C = either || 2 b |,u;1| or Ba, 2 & || 12 Therefore, adding (29a) and (29b) yields
(B)). since eq E Ran(A) U Ra ) we have that for each u,
hi (Azz) + h2 (B22) 2 h1 (Azi) + h2 (Bz) (Vh1 (Azi) + 2h2 (22 21) + C || - 2212
2
C
ž (1(1)) h2 (211) min (Vh1(A2)) + VB2(1))) (s 21)
||
= h1 (Azi) + h2 B21)
V/i (A21) + Vh2(B22)]
(33)
C
According to (32) and 33
as h1 (A22) + (B22) min, (1z) + h2 and C < C², this
completes the proof.
F PROOF FOR REPRESENTATION LEARNING
In this section, we provide the proof of lemmas and theorems omitted for representation learning.
F.1 SUFFICIENT CONDITIONS FOR ASSUMPTION 2
Assumption 2 ensures that the bilevel problem has least one full-rank solution WT. Note that the full rank solution Wi always exists for the single training or validation problem because the objective value is solely dependent on the product W, W2. For any solution pair (W1, W2), it is possible to transform W, into a full rank matrix W by altering its kernel space components and simultaneously, one can identify a corresponding matrix W5 that mirrors W₂ within the range space of W1 and is nullified within the kernel space of W1, such that Wi W2 = WTW In this sense, Assumption 2) quantiffes the singularity of solving two non-singular problems together. To get more sense of Assumption 2
we present some sufficient conditions for it.
Lemma 15. Assumption 2
hholds if one of the following conditions holds.
(a) NWW,WW) E arg min Lvai(W) W2) s.t. (WT, W2) E arg minw,, Lum (W1, W2).
(b) The concatenated data matrix [Xvali Xtm] fill row rank.
Proof: The condition in (a) indicates that (Wi, W.) is a minimizer of the validation loss. Therefore, for any W1, W2, we have (Wr, W5) S Lvai (W1, W2). Furthermore, we are given any 61, 62- Then for any W2 in the cy lower-level optimal set, Lvai (W" W2) < Lva W2) S (W,, W2 )=²= e, holds. Together with the 62 feasibility of (WT ) to the bilevel problem, it means (Wi, W is an (e1,e2) solution to the bilevel problem. Moreover, since (Wi, W2) is also minimizer of the training loss, we have
L tm (Wi) = Leen (Wi, W2) = min Lun (um, W2) Lemma
S 62
W,,W2
which verifies Assumption
For the condition in (b), it implies there exists
(WT, W?) E arg min (W, W2) + Lynn (Wi, W2)) Wi.Ws
such that Lvai (W7, W2) + Lern (Wi, WT) 0. Due the nonnegativeness of both validation and training loss, it must hold that Lvai (WI. 1 W = (w", W3) = O. This suggests (Wi, Wi) is the joint minimizer of both training and validation loss, which satisfies condition (b), and thus, Assumption is verified.
Remark 2. Condition (a) says that the training and validation problem share at least a global solution, situating us within the interpolating regime between training and validation. This means
26

---

Published as a conference paper at ICLR 2025
that minimizing the combined objective leads to solution that simultaneousty minimizes both problems (Fan et al.) (023). In this case, the model trained from representation learning matches the performance attained by optimizing both layers of model directly based on validation loss. Condition (b) is sufficient condition of Condition (a) and Condition (b) itself means there are no redundant information contained in the training and validation set.
F.2 LANDSCAPE OF NESTED BILEVEL OBJECTIVE F(WG)
According to the loss definition and the knowledge in linear algebra, of the bilevel objective in representation learning as shown in the following lemma.
derive the explicit form
Lemma 16 (Analytical form of F(W1) and its nonconvexity). The bilevel objective for two layer linear neural network representation learning (8) can be explicitly written as
F(W1) = 2 A 1
(X) (I (Xura (1) (X bl]
(34)
with Yval val W (X Wi)'Ynn Yu and = [(Xval (1 (Xera (Xmm Moreover, F(W1) nonconvex even when Xtm Xvall Yira
Yval =
When Xum, Vva = Yua = Vaal = I, it is obvious that any invertible matrix W1 and inverse W2 W," are the solutions the bilevel problem (I) as both upper and lower-level objective the same. In this sense, the above lemma indicates that the landscape of the bilevel objective is not convex in the trivial case. A possible explanation to this phenomenon is the discontinuity and nonconvexity of the inverse operator WTT at the rank-deficient point.
Proof: First, according to (Barata & Hussein 2012 Theorem 6.1,, the lower-level solution set of ( can be represented by
S(W)) {( Wi) + (X-( (X (Xer b, vb} (Xtra Wi) Ker( Xum Wi).
(35)
Then VW,, we aim to solve the following problem
min ||.1 (1) (T (Xmm bl@
(36)
where A - Yval X W (Xtra W1) Y is fixed when Wi given. Applying (Barata Hussein 2012 Theorem 6. to (36) again, we know (36) achieves minimal when
= [( W1) (I (Xum W1)t Wi))]* A.
When Xim Xvval Yum Yval= I, we have
b [ [[]]] A 0, and A= X Wi
W1W
Therefore, the bilevel objective has the form of F(W1) = } ||ll|2 = - w.w.1.. Without loose of generality, we consider Wi E R2x2 and the objective value at two point
((o1))=
0 0
F
However, the function value at the median point does not satisfy the convexity condition, i.c.
))-)))==
( ((:0()) - - + x 0
2 x 0 0
2 (0_1) -F
=F
+
x
4"
As result, F(W1) is not convex.
27

---

Published as a conference paper at ICLR 2025
F.3 PRELIMINARIES OF PENALTY REFORMULATION
Ideally, we want to solve the penalized problem ( instead of the original bilevel representation learning problem (8) However, the following lemma shows that Larn(Wi (Wi;)) is not Lipschitz smooth and PL over W2 uniformly for all W1 E _m Therefore, the equivalence of the penalized problem to the bilevel problem and the differentiability of lower-level value function (im(() cannot be established directly from (Shen et al. 2023). In this section, we provide the complete proof of them.
Lemma 17 (Non-uniform smoothness and PL.. The lower-level function Lum (W1,) is smooth with Fmax (Xern) Jo minee (W1) and PL with (X W1). Moreover, min (W1) 0, then Lirn (W1, is PL with o (Xtm)o min (W1).
Proof: First, we know that h(W) =||X..m W| 2 is 1-strongly convex and 1-Lipschitz
smooth. Given matrix W,, then according to (Karimi et al. [2016] Appendix B), Lum (W,, W2) = h(Xum W2W2) is in the form of strongly convex composite with a linear mapping so that it (X Wi) PL over W2. Also, Lum (W1, W2) h(Xera W22 is m (Xtu Liipsicct smooth over Wz. Therefore, the Lipschitz smoothness constant of Ltrn (W1,-) can be upper bounded by
(0) 2 (Xera Wi) S max Jo (W1)
where (a) comes from 17 If W1 and Xum are full row rank, the PL constant is lower bounded by
(b) iii (Xura) (W1)
(X W1) min (Xim W1)
where (b) is derived from (88). Xtm # 0 and W1 is full row rank which is inferred from W1 is fat matrix with min (W)) > 0.
Definition (e- solution of penalized problem). We say (Wi, W2)) is an e- global solution to penalized problem 2 if for any (W1, W2), it holds that
(WT, W2) < L,WW, (2) +
Theorem 4 (Relations of global solutions). Suppose Assumption 2 holds. Any E2 solution to the penalized problem with y an (62,5n) solution to the bilevel problem ( for some e,, = (eE)). Conversely, for any E,, there exists 7 (( such that for any & > ?", the global optimal solution of bilevel problem 8) must be 61 optimal solution of penalized problem with n.
The above theorem shows that to ensure the penalized problem ( is an (c,c) approximate solution to the bilevel problem 8 i.c. E, = O(e), one need choose E2 ((VE) and 7 = O( 0.5).
Proof: We will prove the relations through four steps.
Step 1:
First, we prove that under Assumption 2 there exists an (e1, 62) solution the bilevel representation learning problem (8) with full rank W..
Choose any (G1, solution (Wi, W2) the bilevel representation learning problem (8) that satisfies Assumption 2 If WI is not full rank, then we can find full rank Wi and W2 such that W, W = W W by the following process. By singular value decomposition, we can decompose
Σ
Wi UVVT T with Σ
E Rmxh and orthogonal matrix U = UU* U2] E R and
V [V1 1/2= Raxk Also, by assuming Rank r, we know that U1 E mxxr V1 E Roxr and Σ, E x are full rank submatrix. Therefore, Wi can be decomposed by
Σi
Vi VT
Vi V
: = U, U2l
= UE 0]
= -
and V/2 is the orthogonal basis of Ker(Wi). Furthermore, we can decompose V22 (h-rr with V/2 E (m--r), In this way, we can construct W, and W2 as
(V/ Va)
Wi W U.V U. U2V and W₂ Vi ViV, W
28

---

Published as a conference paper at ICLR 2025
where W1 is of full row rank By Lemma 5 Lim (W1) = 0. On the other hand, the training and validation losses only depend on the value of W, 2 and W1 W/2 = W2 we have
LVn W2) = Lvai (WI, W3), Ltm (Wi, W2) - Limn (Wi, WG)-
Since (Wi, W satisfies Assumption 2 and Lim (W)) = 0, we have
Lirn (W1, W2) ( = Ltmn (W1, W2) Lim (WI. W S c2.
With the fact that (W1, W2) Lvai (W1 W2), we know (W1, 1, W2) is also an (el, e2) solution of the bilevel representation learning problem and W is full row rank by the construction.
Next, we will prove that any e2 solution to the penalized problem with y is an (e2, solution to the bilevel problem for some Ey, For any solution of the penalized problem (WT, W2). we can find W₂ arg (3s(w))( ||W W || and
Step 2:
max (W2) max (onoissww))[()) S a max (W2).
Then we can derive the Lipschitz continuity of Lv (W?,) by by
Laai (W7, W2) Lva(( (2) V val W7 W2'' 1|2
2 |1 X W7W21
(2Y - X W7 (W2 W2). -X W7 - WW2)
S L( IW2 - 1
where L(7) = (omax + o max (X (ax max lows
(W7)) ma
(W7). So fol-
(W7, W2) + (L (W7, W2) - (W7))
< Lvai (WT, (2) +
$ Leal (W7, W2') + I(>)lI W2ll +2
< Leai w2) +
o.(Xim L(7) / Lorn (W7, W2) Lue (W7) + e2
(37)
where the first inequality comes from the definition of 62 solution of penalized problem and (W7 W2) Lira (W7) 0. and the last inequality is derived from the PL. condition of Ltm (W7)
and Lemma According to (37 we have either
2t2
(W7, W2) (im
(38)
or c2 < 3:' (W7, (W7)) and thus
7 2
(Lom W2) - Lorn (W7)) < V Vo.(Xim WT)
2
M()) Lern (W77 W2) - Lern (W7)
which yields
8
[(>) 2
Lira (W7, W:) - Lura (w,7) < oz(Ntm WP)
(39)
By choosing 7 =O((2) and noting that (I()), ax WimuW)) (1),
38 and
39 indicate that
c- Luea =or=Ler (W7, Liru (W7) S max 262
8
[(())
o
62
O (+²)
(X W7)
Moreover, for any (Wi, W¹) satisfying Lim (W1, W2) - Lim (Wi) S ey, it holds that
Lvai (v7, WW?) + 7LLra W - Lim (W?)) < (va,(W,, W2) + >Lera (W1, W2) - Lir (W1) + e2
and thus
Lval (W7. W3) Lval W1, We) S (Lura (W, W₂) Lim. (w;) (.) + c2 S 62
which indicates (W7, W; is (E2, c,) optimal solution of the bilevel problem. This concludes that any 62 solution to the penalized problem is an 6x) solution to the bilevel problem.
29

---

Published as a conference paper at ICLR 2025
To prove the converse part, first claim that for any c2. there exists é2 solution to the penalized problem with full rank W1, which is built on the previous two steps. Take the E2 solution (W7. W of the penalized problem in the second step, it is an (c2, (2),E)) optimal solution of the bilevel problem. From the first step, we know there exists an (42, 6,) optimal solution of the bilevel problem (Wi, W with full rank WT. Therefore, we have Lval (W W2) = LLa W3) and the feasibility
Step 3:
(W.. W2) - Lim (W1) S = (W1, W2)
Lira( (W?).
Adding these two inequalities together, we have L, W3) I L,W,, W."), which suggests that (W1, W5) is also E2 solution to the penalized problem. As Wf is full rank, we prove the claim.
Step 4:
We will then prove the converse part, i.e. for any 61, there exists y" such that any global solution of bilevel problem is an 61 solution to the penalized problem for any 7 7- Take any global solution of bilevel problem and denote that there exists a global solution to the bilevel problem (WI, W with full rank Wr. Also there exists an 6 solution the penalized problem (W?, W3') with full rank W7. Therefore, we can restrict the bilevel and penalized problem on the following constrained sets
(W1, W2). According to the first step, we know
Wi = { ri S Tmin mmin(W1) (W1) S max (max S R1}, and W2 = { : max (W2) S R2)
where r1 < m (WT), m minn (W7)). R₃ > max mmxx (W;), max m000 (W7)), = 1,2. In this way, W3 is convex closed set while Wi closed but nonconvex set, and
min WSEWs
LWW W2) = min (W W2) W..Ws
because the constrained sets include the minimizer of penalized problem. Also, (W1, is
uniformly Lipschitz continuous on W1 and W2, and Ltm,W,,, uniformly smooth and PL on Wi and W2. Adapted from (Shen et al. 2023 Theorem 1), there exists y O(TT)) s.t. for any ? y
we have
L, (WT. W3) S
min WoWw,
(W1, W2) + 61
min L, (W1, W2) +
W1.W2
Since (W1, W2) = (Wi W2) = LW Wg) = L, (WW,, we know (W1, W2) is an él optimal point of the penalized problem, which concludes the proof.
The following lemma shows that L' ('W1) is not differentiable at the whole space, but is differentiable for W1 with lower and upper bounded singular value.
Lemma 18 (Danskin type theorem). Assume there exists R E Rso such that for all W1 W, r S Tmin (W1) S max (Wi) < R. Then Lim (W1) differentiable on Wi with the gradient VL (Wi) Vw, Lum (W1, W2,,W2), Moreover, VL (W1) = 0 on Wi.
VWZ S(W1) with finite norm.
Proof: First, VW1 E W1, without loss of generality, we can set W = (Xura Wa)'Yaa E &S(W)) with finite &g norm
(a) 2 m (max((XX) (())nn (Ytm)
max (W3) = mmax ((Xer W1) Wi)tY
Fmax (Xmm)
Tmax (Xmm)
T maxx (Xim)
Gmin (X erm Wi) amin (Xtr)) (W1)
Omin (Xtrn)
where (a) comes from maax (A)) 1/amin (A!) if amin (A') this way is to ensure Vw, Lim (W,, Wi) ) is Lipschitz continuous over Wi, which can be proved by
>
The benefit of choosing W in
wg (W1, W3) Lw W2)ll2
= || (X W1) (Vim X W,,) + (Xern WT) (Yim - X W/W
Shen al.
2023
Theorem 1) only requires the convexity of W2
30

---

Published as a conference paper at ICLR 2025
(I Xera(W; - wi) + [I(W1 - wi) Kin Xura W2W2)l2
max (Xur)) (Wi Wm)x (W W Will
T (Xir)) l max (Yern) + max ( max (Wi) max
( (W - Will
Tmax (Xtrm) ( (Yin)
+ m (Xtrn) (Yirn) 0 maax (Xrm)) R ]
[1+
[|W] Will
Omin (r
min (Xtrm)r
where W1, Wi E..
On the other hand, for any W1 E W1, as long as it does not belong to the boundary, we can find ā > O such that for any a S a, W1 + ad E W2 holds for any unit direction d E IRmx Even for Wi at the boundary of Wi, one can slightly enlarge Wi by adjusting r and R correspondingly to ensure the singular value of any W E B( a) is uniformly lower and upper bounded. Then based on the Lipschitz continuity of V W, Lum (W,, W ) over Wi and W₂2 and the PL property of Li (W1, 1), and according to (Nouiehed al.. [019 Lemma A.3), there exist L > 0, for any 0 < a S ā and any unit direction d E I=**,, one can choose W (a) E S(W1 + ad) such that (W - -W51 s La. By the Taylor expansion,
Lim (Wi- + ad) - Lun (W1) = (Wi + ad, (a)) - (Wi, W()
= =aV w. Lorn (W,, W2)d + Vir. WW,, (2)(WW - ())()))-W33---30 + O(a))
a w. Lura W2). + O(a²)
By the definition of directional derivative, we know
Lim (W1 + ad) - Lum (W1)
dW1:d) lim r-0+
= Vir, Lira (W1, W
Since the above relationship holds for any direction d, then get VLim (W1) Vw, Ltrn LW1, W In addition, the above discussion holds for any bounded Wz. which yields the first part of the conclusion. Moreover, as V (W1, W2) = WW, W X.T brea (W, W W and fum (W, W2) minw, Ltmn ( [W1. W2) = 0 according to Lemma 5
we get VLern (W1)
Vw, Ltrn Larnnt (W1, = Ww, Lum (W,, W2) = 0.
Lemma 19. Under Assumption 2 for any O, there exists an c-solution to the penalized problem
(Wi, W with Li... (W]) =
Lemma 19 is pivotal in ensuring that the penalized problem is well-posed, Otherwise, we encounter the situation where the optimal weight (Wi. W5) learned from the penalized method
Lim (WT) * min Lum W2) = O. W..W2
This implies that the learned bottom layer weight fails to fit well on the training dataset- scenario we want to avoid. Without making assumption on the penalized problem, the well- well-poseness of derived from the singularity assumption of the bilevel problem and their approximated equivalence.
Lemma 19 is a side product of Theorem According to Step 2-1 the proof of Theorem we know that for any there exists an e-solution to the penalized problem with full rank Wi. Together with Lemma we arrive at the conclusion.
Proof:
F.4 PROOF OF THEOREM
We restate Theorem D and the descent lemma in the following theorem. Theorem 5 (Local joint PL and smoothness). Suppose Assumption 2 holds, assume o (W1) >
2 (W²)= > 0 and denote X,- [X (ym). Then the descent lemma holds with Ta defined in and the local joint PL inequality holds with 14u- = (m (WF) + omin (W:))))))))) i.e.
IWL w 2ux(L, W -L:)
L,(2-11 s L,( - @ a a² LB) || (2*))11 + ( + + 110x112.
where Z = (W1, W2), 2 = (WF. w ) a and L; = ming L, (Z). Moreover. one has
L,(Z -
L $ (1 - at4 + 2a La (L+ - L;) + (2 + +a²Lx) 11&
Proof: We first prove the local PI. inequality by four steps.
31

---

Published as a conference paper at ICLR 2025
Step 1-1: Local PL inequality for (Wi, W2) and Lvai (W1, W2). First, know that h(W) Y trm 2 is 1-strongly convex and 1-Lipschitz smooth. Given matrix W, then according in the form of strongly convex composite with linear mapping so that it is (X )-PL over W. As Xurn is full rank, have o (Xtm) = omiu (Xeen) and &m (W) = h( (tm W) is (Xtm) over W. On the other hand,
to KKrimi et al. 2016, Appendix B), 4m (W) = h(Xtmn)
also have
min 4mm (W)
min Ltmn (W1, W2) W,,Wa
(40)
because
min (eraWW S lura (WIW2) = min Lum (Wn, (2) W
(41)
Wi.W2
where WI, W = arg minw, Wa Ltm (W1, W2). The reverse direction (41) holds true because for any W E arg miny (mm(W) it can be decomposed to
Imxm ((h-m) xm
W
W Onx(h-m))
Based on the above facts and denoting = W2 we can prove the local PI. property of Ltm over (W,, 1, W2) by
| Lu (W1, 22)ll
= Vm (W) W V um)
= Vlmm (W) 1| W V fm W (W)
(a) -im (W₂) V (
-. (w V (W)]
moin (W1) + - (W, V (W)
2 (Wi) + σ min W (frm
-iinnn Lern (er( (W))
W
(0)
2 20 (Wi) + mai (W2) (Xn)
(Xtm) (W1, W2) min Lern (Wr, W2)) Wi,Wa
(42)
where (a) comes from Lemma (b) derived from 6m (W) is oin (Xur)) -PL, and (c) is because minw Lera (W) minw,, Wa Ltm (W1, W2). Similarly, for the validation loss, holds that
Lv (W1, 11 2 2 (W1) o (W2))o (X (Laa) W2) min Lvai (W,, W2)). W..W,
Step 1-2: Local PL inequality for L, W2) =: LWa, W2) 7Lim (W, W2).
By noticing the fact that (fval + (W) = - - W,1 with Y, = [Yrati vyYum and X- = (aat v/ (em),, we have
[WC, W2)l
[[v + 7 (W)) 1 || ((hral (ltr)))) (W))12
2 2 (Wi) + o (W))) (L, (Wi, Wc) - min [WW, Wo)) W..W2
(43)
where (a) derived similarly from the derivation of 442
Step 1-3: We then prove the relation of L,W,, W2 and L, (W1, Wa) that
min W..W3
L, W2) min L. (W1, W2). W..Wa
(44)
Since Lern (Wi, W2) 2 O, know Lim (Wi) minw, Len (W1, W2) 0, and thus (WW, W2) Lyal (W1, W2) + (Lumm(W W2) 7L (W1) < (W,, W2) 7Lm (W,, Wz).
32

---

Published as a conference paper at ICLR 2025
Taking the minimization over both sides yields
min L,WW, W2) 2 min (Lva1(W1, W2) (LuraWW W2)) min W1:W2
[W1,, Wz). (45)
W2
Ws.W2
By Lemma 19 for any c > 0, 3WW W)) is an c-solution of L,W,, W2) with Lim (WT) 0, so
min (W1, W2) 2 (W1, W5 Lv (W1, W2) 7 (W1, W() W1.W2
2 min (wa W2) + yLarn (W1, W2)) = min (W1, W2) Wi.W2
W1,W2
holds for any e. Letting e - O, we get
min W1.W2
(WW,, W2) 2
min (WW,, W2) W1.W2
Together with 455
must hold true.
Step 1-4: Local PL property of L. W2). IVL, (W,, W2)ll (va + V 4mm (W)W: - ~VLLin (WI)l2
+ |[W Veaa (W) W Vem (W)II
Vloa + 7 VV 1 + || Vevai + WW Veen (W)ll²
((vall + 7 [ [[W] (lvaa + 7lm)
(6)
2 2( (W1) + minn (W2)) (L.Wi, W2) - min Wi,W, (, W22
1 2(0 (W1) + min (W2) (X,)) W2)
min Wi,W2,
L, W2))
W2) min
(W,, W22)
W..W;
where (a) comes from Lemma 18 and (b) is derived from 43 and (c) holds because of and Lim (W1) 0 when 0 miin minn() (W1) > O.
Next, will prove the descent lemma. Denoting Zt =WW W the update of PBGD can be formulated as
zk+1 = 2h (Z + 5x)
(46)
where 6x ><(V (WT) - Vw, Lw, (WP, W )). Let denote
(K)) = VLi, ((1-x) W/ + +
w + xW
L, (Z + 6x)), W axV axVW.LL(Zt)) = V'i, (W+- - an (V L, (2 + 0z), W - anVWs,L,
v'I, (W/+
= -vii, h an Van + 64)
(47)
then by second order Taylor expansion, we have
)((h+) < (z
= + zh+1 zht1- 22) ( (1 Hx, 2²4) dr
@ L,(24) a VL, (z*). (Z,) + +0x) + 1/' (1 (1-k) (Zo+1 Zz, Hx) -zh1) di
.0
(8)
a VV (2 12
al 01102|1
1
< L
+ 2
(1 k) (VL, + & (( + 8x)) dr
2
jo
33

---

Published as a conference paper at ICLR 2025
@
al VLIVL, (Z))
allbal1
+ Q2 + 6xl12 S. (1 (1-m) 1)) (9te H gk) de
L2
+
2
2
(4)
S L2* al| [Z
2o (IVL, )12 1| [1ōx|l3) S/' (1 L.
2
-z
2 a a LR)
| (Z |1 + + a² 11ó=|12
(48)
where (a) is derived from
44 minn (Wf)= > 0, Lemma and Lemma
18 (b) holds because
6) |all
|bb11 ||a
b1
||.
aa
b11
2
2
2
2
)+, and (d) is earned by Lemma 9e in (c) is defined as (ZL)(2*)+6]]]
22
Finally, according to (48) and the local PL property of L, (W1, W2), we have
S (Z*) lz _ a² a²Ls) |VL, (z*))² + 2 + a² a²²L)) l1óul1
< (Z) - (a 2a 20²Ln) pm (L - L ( + a aa>ia) |1ōall?.
Subtracting both sides by L3 yields
(,(2tt) - L; S (1 ape + 2a LaHun) - + (
a + a² LxLLx 11ó111?
We give the characteristic of Lt. the bound of (gk, H (x) by showing (gk, H (()ggx) and Kgx: (H(x) H())) ) are bounded subsequently. The upper bound of (gk, (()gg)) is adapted
from (Xu et al. 2024 Lemma D.I) as it is independent on the update direction, as long as It. is
normalized.
(2-
Lemma 20 ((Xu et al. it holds that (gk. H()gg)
2024
Lemma D.I)). Let gs- = [VL,)2")+0]] and H (1s) defined in 47 then
d a211VL, (W7, W + 50112
1
M(s) (VEC,A(s)),
ds²
===
1
d
A(s)) + max((X))]
A(s + k)]l
(W W + Sull2
ds²
ds
==0)
< 2 (o max (W+)
+ o (W:3) + v 20 2 (X,, (L, (W w/) - L:))
(49)
To show the boundedness of (g), (H(s) H())) |. we define the loss at the intermediate point and the product of W - sOx Vw: LW W/) + 5&) and W sa Vw, (WF. W as follows.
(s) = Ly (W sa (Vw, (W,, wx) + 6τ) W sa sa ww (W W3))
A(8) = W sa ((Vw, W,,,,,WW W3) + 5%) W + WFV,,L, W/))
+ s²aa (W w + 6k) WwgL, w()
where W W and by = lual + 7etm. this way, we have
M(0) (W w M(1) = (W w ) and M(s) (A(s)).
Then establishing the bound of || [()) - (0)l depends on the amount of [|A(s) A(O)] because (x) = (M))) =
Lemma 21. For any K E 10, if ||6x|| - 5 and omin (WF)) O, min (W2) > 0, then it holds that
[[(()) A(0)] S a (o (W/)) + mnne (Wz)) / 22 (X,, (L, (WF, W/) - L:) + aδo max (W/) + 2a² m (X,, o max (W (L, w - -L
+ a 2ax (W+) 20 (X,) W -L5)
(50)
34

---

Published as a conference paper at ICLR 2025
Proof:
According to the definition, we have
||((x) - A(O)I|
|| (WF, W - 5t) W + WWF W
ax
W2) + 6z) Vw: W
S kα (VV,,, W + +d)) W +
+ x2a || [ii,,, (WI, W 6x)) Vw,L, w/)l
22 &
25
Koc maa (W+) + max (W V 20 (L, (WT, w3) L3)
+ kadoomax (W2) + 2n²² 2 max (X ) (W )) (W, way - -L)
+ x=2 a² max (WT), v 20 max (L, W -L)).
Letting < 1, we get the conclusion.
Lemma 22. For any n. E [0. 1), let 8 = | then it holds that
(9k, H(:)ga)) S mnax (X,) maxe (W()) (W + mmax (W2)) + 3ado max ( (X ) max (W2)
+ (1 + 3ao max (Xx) (o max (W1) + max (W21)) v 120 max (X,)(L W3) L:)
+ 3a 3a²0zz maxx( (X,) (W 20 (x,) (W1,, w/y) - -L7)
+ 6a max (X,) (x (W*) (L, (WF, why) - -G;) =: Lx
(51)
Proof:
First, we observe that (gk. H (K)gs) is the second-order directional derivative of L, with respect to the update direction, i.c.
d M(s + +x)
(gk, (())gk) = a2IVVL, W/) 6z dsa
(52)
s=0
For the directional derivative, we have
d
((s + k:)
ds2
d²
(A(s + xx))
ds²
k=0
d
d
ds (VE,(A(s + k)),
A(s + k))
ds
==0
(VL,(A(s + +k)),
d²
Als -i))
+ "Ts A(s k), Vee,(Als + k)) d
A(s = + x))
d
a=0
a=0
& (7(((()+KK))
de Als + k)))
o (x,) d
_: A(s x)]l 0=
(53)
0=0
where (a) uses the fact that by is max (X,) smooth. Then bound (VL,(A(s + k)), de
de
Als
<))
and dee A(s + x]
as follows.
==0
d² ds² A(s K²))
(Ve, + K)),
==0 = (V W + 51) Vw,L(WH, w3h)
= -2V4,441)---7444400,.==T// w + 5x) WwgL,Wt, wa))
+2 6 (w, w:))
< 2a 4(0)
+ 6x) Ww,,,,,WW,,, whhll
d²
+ (A()), ds² A(s))
(54)
On the other hand,
d
A(s + x)]l2
ds
35

---

Published as a conference paper at ICLR 2025
(2)
w
-2xa² (,,, w
=a
+ +n=2a* (1w. 1
4xa²
w 6x) W WWV w
- 11 d A(s)11
1==0 + 4 L, (WF. w + 6λ) Vw.L, (
ds
- 4ka (V W + 6k) V Lw (W w3))
(V L, (W ) + 5x) W + W w. W (w7,w
(55)
Plugging
and 555 into 533. we get
(s + K)
do
$ 'aaa 00 max (X,, -
A(0) ((0)
W3) + 5x) w. (W (
d2
d A())1
+ (A)))
A(s))
+ + (x,)) d8
do2
==0
==0
+ 4n o maxe (X,) || L, w3)) + 5x)) Vw, SwsLy (W w |²
4Krx m (x)) (VV,, w + +5x) Vw,L(WWt wh),
(WiiL w + 5x) W + V (
S a o maax (Ax)) A(O) VL. W - 6x1l
+ max (Xx) (Xx) (o + max (W )) + 20 Pnax (X,) W/) - Li)
VLI w3) + 1
204 + 4R² 2n20 a' max (Xy)0man (W (L, Whh) V.) w + 1x
2n² o0 (Xx)00 max (W+)
20 manx (L, W L:) (W+ W + 6x
2na mux (X₂) (o maxx (W+) max (W V 20
L1) w + 8
+ 2naa o (X,) )60 max (W²) || (W w 5
where the last inequality follows from Lemma 9 and (49). Plugging the above bound and the bound
of [|)) A(O) in 55)) into (22) and note that K S 1, we obtain that
d² M(s + x))
(gx, (x:)ga)= = a2 VLI + 0z ds
==
S ao max (X₂) no (Wt) + (wa)) v 20 20 (L, W/b) L:)
+ ado? I (X,, 10 max (W?) 2a² o (X,,) maxx (W (W*)) (L, wh) L7)
+ a 602 max (X,, )o mmax (W+) 20 mux (L)((,,()) (WF. W/)) - L5)
+ o 2 (X, (0 max (W+) + o (W?))= + v 20 (X,, (L, (W), Lt)
+ 4 max (X,, )0 max (W*) ( W -L;
+ 20 a (X, 60 max (W / 20 20 (X,, (L, (W/, - L;t)
+ 2002 max (X2) (o m (WH)- + n (WZ)) / /2 muax (X,, (W, W/) - L:)
+ 2002 max (X,, (X7)00mmx(()) max (Wh))
Tmxx (o maxx (W+)) 2 max (Wz)) + 30d0 3xx (X, (xxx) (W/k)
36

---

Published as a conference paper at ICLR 2025
+ (1 + 30d max (X,) max
(WT) + (max(W2)) / /2 max (X,) Wy) -L;)
+ 3a 0 max (Xx)000 (W/)) 20 max (L,) W L(;)
+ 6a20 max mm* (W2) -L7)
which completes the proof.
F.5 PROOF OF THEOREM 2
We restate Theorem 2 in a formal way as follows.
Theorem 6 (Almost linear convergence rate). Suppose that Assumption Cataunptionnholdds letting ai be the smallest positive solution of the following equation of a
(56) If the above equation does not have positive solution, set 01 Similarly, let a2 be the positive solution of aL = with T, defined in (64). Moreover, let 0: < (log(2 + - ))² Then for any
m (X,)(L, W - L,, - (1 -1- exp=xv(va)) + 02 exp(va)))o2(X.)
0 < min a22 0a) and 0 < B S oz there exists T = Oloog loge -1 + K) such that
oWp" 0(2114) and
5 S min
2adV of exp(VV)) 2a²8² 30 expl (Xx)) K
002 exp( (oxxpvaajmmat (Xy) (L, W22 -Lē).
(57)
Therefore, when 7 O(c-0.5,, μ O()), L 007), a = O0r have ap O(1) and to achieve the (c stationary point, i.e. (W Wh) minw, WW Lwa W2) S c and Ltm W - mini, (1n,W,, W2) I 6, one need KT = O(lo(( 1)2) iterations.
Denote W W and D2 = (Wf)TW? (Wz) T as the imbalanced matrix. We will prove this theorem by induction. Define the following properties as
Proof:
Pi(k): (W wh+1)= L; s (1 2)) (W Wh) L:) + 3a52
P2(k):: I mmin (W++1) S m (W S W2
*
* Pa(k): || - -Doll 5
(01+20x )03(X.) (L, W - L;)
5acs exp exp(va)o i (X-)
P.(k):: ci 2c - exx((va)
of (W? ) S oa (W!++) I ca exp( Va), i= 1,2
where e + = o + cz. Suppose that the above properties hold at iteration 0, ..... , - 1, we aim to prove that (kb) (s(,), Pa(k) hold recursively.
Step 1: (k) holds. If we can prove the following uniform bounds of the local PL, smoothness constants and the lower-level error
μ ž H,
LA S L, || 8
(58)
then it holds that
1 0:44 + 202T4p4 =1 1 - (a 20 T.k)
and
( + a²2x.)
|1&a|12 <
(
a
a))
a²
82
(0)
(b)
3
ula 20 TTk)
4
(c) osp
(59)
2
where (a) comes from < + S +.2 (b) and (c) are due a 1 and La < L. Then according to Theorem 1 we get the conclusion.
37

---

Published as a conference paper at ICLR 2025
Next, we start prove (58) According Pa(k - 1), the lower bound of μ4 is earned by
Pk = mo (Wf) + min (x2)) 2 (ci + (2 exp(va)) (. =
(60)
where 0 = o + of and c = cf + ca. We then prove the upper bound of | By definition,
||o&| || = V Lera (W1, W - Vw, (wrLera(W)]]
I 122 2 (Xem)o (WF) dist(W S((())
< 27 max (Xtra)o max()) (1
min (Xtr) (W+)
T
(WF W:) Lim (W/))
o max (X Jo max (Wh)
o max (Xtrm) )orm)oman max (W+) (1
Juin (X J (W+)
T
S 27
Lim W3)
o max (X )o maxe (W?))
where the first inequality is due to the Lipschitz continuity of Lemn (W+, :), the second inequality comes from Lemma 7 and Lemma 17 According Pa - 1). mmax ( (W m (W+) is upper and lower bounded, so the upper bound of ||óx|| S exists and it exponentially decreases with T.
Finally, we prove the upper bound of Lu. As (W.. W [, W/) when amin (W+)) > 0.
according to the definition, it holds that
Lk
51
max (X,) (m (WT) + iax ( (W2)) + 3adomix (axxmmxxx)) (o Jmax (W:))
(1 3cxo max (X,) (omax (WT) + o (W²)) v 20 max (L,) W3) LT)
+ 3a 02 max (0))0mmxx (w 202 2 (X (L, W - LL:)
+ 6a 2 max (axx (W*)) (L, (W -
(61)
Therefore, to prove the upper bound of L,. we need the following upper bounds
Pa(k-1)
2 max (W+) + omax (W²)
S
C2 c2exp(Va)
(i(K-1)
(1- anl (L, W2) - -L;) 3 h-1
L,WW/ Wh) - LG
Σ
(1
k=0
$ (1 and &
382
(W,, (W) LG+++ +
11 121
(62)
244
(W W - い
(63)
Pa(k-1) 2 max (W?)
P2(k-1) I
I
of exxp(va)),
muxx (W*)
W2
| S 8.
where (a) comes from 8 S
Plugging the above upper bounds to 61 we get
LA S (Xy)o2 + 3ado max (X₂)) 02 exp(va)
+ (1 + 2 max (X, exp((
20 max (L,), w/) L7)
+ 30 max 16, 02 expppp((v 20 max (x,), Wh) LT)
+ 6a²o4 max (X,, W2 (L, (Wf: W2) L:) =: L.
(64)
After obtaining the bounds for μkx [| Lt, P1 (k) holds because of Theorem and (59).
Step 2: (2) holds.
Since (Eval + (atrr) is o (X,, Liipschitz smooth, we have
(Eval + 7lm (lrm)) (W s (Eval + (lor))(W) + (V + xWm))(W), Wh+1_ W) + o 2 (X,,
| - W113
2
38

---

Published as a conference paper at ICLR 2025
Setting W = W E arg ming (fral + (W) yields
(fral + (leua) min(Cral + (lmm)()) + o max
(Xx) | W/
2
and thus
0² 2
(X,)]lWbtt_ 2 v (fral + (aam))))))))) (llm))(+ht)) min(fral + (Wam)
W
(W wh+1) min (W1, W2) L, 1
Wi.W2
Also, (bral + (W))))()) is ) -PL, so the quadratic growth condition with holds by Lemma 6 (x,((x))lWk++ 1*11 < (fral + 7 (WWk))) W
min(fral ylarn) (lar)(()) = (WT+1 w L
where W arg mill Earg minw (6vrs (W) | W112. As result, we have
max (W
max (Wh+1 W +W*)
S max (W*) + || W" 2
< max (W*) + ||W W"
max (W*)+ + V 2x²(X,) (L, (W/ wott) L.))
max (W*)+
(x, (L, (W (W W3) L7) =: W2
where the first inequality is derived from the Weyl's inequality. Similarly, the lower bound of singular value is achieved by the Weyl's inequality
o min (W++1)
min (W W +W)
min (W*) | 1/
Omin (W*) || WI
min (W*) V 2x²(X.) (WT, WT) L.).
As the singular value is always nonnegative, we can define a lower bound
W1 = Omin (W*) V 2x,(X.) (WP W() - LL;)
(65)
which is strict positive when initializing WT, W close to the optimal.
Step 3: (k) holds. Denoting W = WW ly Eval + ylem and utilizing the PBGD update
w w - a ((V + 6²) and What W -
(66)
we can expand the difference of imbalance matrix as follows
Da-1 - D2 - W, w - wh W1++, w - (WT) w/ + (Wa)) w
(W1 - aVVe, + 0x)) _ - -VV 6k))
-(W3 (WW5- (V, (W² T - (W1) w + (W/) W
( ++))++++++++0) =0)= 5T (VE,(W'((1))) + 6x)
+ 2a T (Whh) w - ( T (WWTTVE, Ve((W*))
39

---

Published as a conference paper at ICLR 2025
2a(W 8x + (VV + +6)) T (Ve((()) + +
a² Ve, (WWF)TVe,(M))
Taking the norm of both sides yields
|D++1 Dxll - 20d0 max (Wf) a (VV, + +a (L,
< 2ado (Wt) 2a (o [ a max (W (W
a
max (Wt) 8d 2 220 max W + max (W )) V 31
20dy V cb expp(v (a)) + 2a 6² + 2a c2 expl Va) max (X, | (L, (W, w LT)
2000 c3 exp((v)) + 2020²
auy & + 20 02 exp( max (X₂) ((1- 2 (L, w3) - -L7) + 30
2/ (67)
where the third inequality is due to Pa 1) and by is (X,) Lipschitz smooth. As result, it follows
D Doll S
|| Dx+1 Dw
67
2adj / (dexp(va)= + 2a282
k +
2a 02 exp( V (a (X₂) (1-22) & (L,(WP, - -Lē)+ +
382
2p
k=0
2 + 3a²8 exp( exp(Va)o maa (Xn) K
2ad V cl exe((va) + 2a²8+
4ac2 exp(va)o Max (W, Li)
500z exp( cxp( 2 max (X₂)
(LTWW,, - -L5)
(c1 c2(2 exp( (X,,)
where the last inequality holds by
57 and (60
Step 4: (k) holds. bounded by
According to (uu et al. 2023
Appendix C), the initial weights can be
of S min (WT) S max (W s c
et < mmin (W:9) S mmax (w:9) < o
and the singular values of weight matrix can be bounded by the imbalance matrix
b/ = c - 21 - Doll S mmin (W/++)) < T (W (W++)) ) S cp + || - Doll = b1
bi = -21 Doll I amin (W Tmax (W < og + || Doll = bg.
Moreover, we have
by = c + | - -Dol
5ac2 exppexx(a))l 0 2 (X,)
<c + (cl + 20 - exp([a)) (X,) (L, w2) - L:)
C2 exex((VV Va)
<ch + (1 (xp(-va)) -xp(eexp(]a) ((()))
(c + exp(vo)) )f({))
< <exp(Vo)ce
40

---

Published as a conference paper at ICLR 2025
where the first inequality holds due to (k)()), and the second inequality holds because of the condition (56). Since bj + 2 = cj + 20² and by S exp(va)ch, Pa(k) holds because
(V)) - bf S min (W S o max (W s by S exp(va)cc-
Therefore, the iterates of PBGD satisfy
Ly (W1, w Li - (1 (1- ) (W, -2)
Together with Theorem and Theorem we arrive at the conclusion.
G PROOF FOR DATA HYPER-CLEANING
We provide the omitted proof of lemmas and theorems for data hyper-cleaning.
G.1 INDEPENDENCE OF THE LEEER-LEVEL SOLUTION SET S(u)
Lemma 23. If Xtm X is diagonal matrix, then for any S(u) that is independent of u. and thus
fim (1) [Vw(()) (r-
Xtr
Yum
(u:)) (IXomX + #1). (68)
Proof: According to (Barata & Hussein 2012 of (T0) should satisfy
Theorem 6.1), one of the lower-level solutions W
W = (VUN(N))) (2)ml)))))))
UN (u)
( xim VVN(u) V (u)
(Xera)
(69)
where (a) holds because / No (u) is invertiable for any a E l and Lemma 10
Therefore,
Lir (w) Ven(() (1-Xamxxin) Yern ||
((,,)lla ([Xum A 1)
2
where [XeenXXtrlkss denotes the element of matrix [Xum at the position (i,
Remark 3. Lemma 23 suggests that the (e, 0) solution to the bilevel problem is meaningless since the static lower-level solution set makes the bilevel objective in (TO) independent of u. This is also aligned with the observation that the model achieved by data reweighting is independent of data weight when the training dataset is linear independent (Zhai et al.) 2023 Theorem 1). However, the c-lower-level solution relies on u (the rationale is detailed below). This could also explain the reason why solving bilevel problem by nested approach to the (e, 0) stationary point has accuracy drop over the (c. e) stationary point attained by penalized method in the data hyper-cleanin task (Xiao et al. 20236).
Explanation of Remark 3 The gradient of lower-level objective can be computed as
) (V)xx(u)Xmn) (V)(u) -Xmm W)
Vwlum W)
2 X (u) W)
2 Σ (u,)a., (x.W T.
(70)
When the weight of i-th sample (uu) is close 0, i-th sample minimally influences the lower-level optimization. Ideally, the optimal response weight which fits the dataset excluding the i-th sample, will also perform approximately well on the weighted objective.
41

---

Published as a conference paper at ICLR 2025
To see it, let u' (u, 8, -U, u...., with -ū at the i-th position and ū elsewhere. We
can then choose the minimal norm solution W(u') E arg mrgmmn 2 Ejzs | W - y || such that
" 2z(22 W- y O. According Lemma 23 W (u") arg miny = 11=, W y is
also solution to Σ bu,))la W - y3 11 so that jn (uy) (z)))z((a))) W - v, = 0. By (70).
Vwlema (u', W('')) 6
T. ( W(n') v.
2
holds for any i. Taking the norm yields
Vwlumu''s ((x')( (
| W (p'(("')8-) -.-il
2
which is very small because (f(- is close to 0 and |, [
(u') v, IIl is bounded. According
to the PL property of the training loss, we know the function value gap & W (w')) fim((") is also small enough, suggesting that W W(u') is e-solution of lower-level for some
Lemma 24. If [Xeen: Xval[[er Xvall' is diagonal matrix, then for any u and arg miny (u, W) independent of u.
Proof: The proof follows that of Lemma 23 by replacing Xuna with [Xerai Xval]-
G.2 PROOF OF LEMMA 2 LOCAL BLOCKWISE PL AND SMOOTHNESS
We first restate Lemma in formal way as follows.
Lemma 25 (Local blockwise PL and smoothness of f, W)). If Xumm is diagonal matrix, then for any u E li and any W, the penalized objective E, (u, W) is Ly -mmooohth and p.y PLL over W, where the constants are defined as
12 = oz (Xaa + 7(1 (x XIm) LT o max (x (Xv vip X Xern).
Similarly, the lower-level objective erralu. W) 3 is T-n-Smooth and P over W, with the constants Hwu := 02 ((1- ((1-v(1)) Xm L == m ((1 (b) xx) Xura)
Moreover, by(u, W) is 7lem smooth and 2e(W))(a) w(n))? PP over u E U, where we define
c(W) min [lv. - x ww - I1 ([Xtmx # 1) }
as the lower bound of the positive mismatch in the training loss. If there is no positive mismatch, we can set c(W) to any positive number.
Proof: We first show that Sigmoid function (u(4) is (() ( PL and 1 smooth u, where u, is the i-th element u. According to the definition, the gradient of the Sigmoid function can be computed (ws( = ()u))(1 (uu)), and its Hessian has the form of
Vou( (1 ((u)))² + ((-)((())(((()))
=1u)(( (1)))) (bu))
= (bu)(( ((44))(1- 11
(71)
which validates the smoothness. On the other hand.
|| [[b(()))) = (1 (ux)))
{ min (1 ((l))((uu)))))
asau5a
a w w - -()-)
min(6(@?11~0(i),, (T) (
(72)
v ((()(( ((z)) min (u4))
4
42

---

Published as a conference paper at ICLR 2025
where the third inequality holds since (((-) = -1 (b)) the fourth inequality comes from ū 0 so that (+) > 1 1 ((), and the last inequality follows from ming, (b(4) = 0. This proves that ((,) is ( ( PL when u, [-ū, ti].
Recall that the penalized objective can be written as
(u, W) Eval (W) + 7
(1()) [1u. - x2, W 1 # 1)}
Therefore, the gradient of L, (u, W) satisfies
|/ Vall 2I1
V (u, W)ll
2 (us) [10x - - X fmml ) * 1) ||
22 N
(uz |107 - -x, w11 11x111 (( x Xtenls # 1)] }
4
(1) ((7))
- [IITT - w11 x # 1)
( (1)(1 (())2 N
Σ (ux) [IuT - x, w11 l1 ((X * 1))
4
xc(W))b(a((1 (T))
(e, W) - Lval(W))
(e((W)b(1))) (2))²
(v, - min (u, W))
(73)
2
where the last inequality holds from min, (u, W) (W). This shows (u, W) is >(W)e(a)(--(a)) PL over u. The Hessian of (u, W) can be calculated by
N
(2, WIll =
Σ
7 (())) |INTT x w|1 11 Xtrale + 1)
2
?
|| 2/ - - w11
2 i=1
N
7
11 x2 W1| 7
(74)
2
which indicates (2, W) is (mm smooth over u.
For the property over W. we can use the matrix form of the objective and define
(W) : - X
7 2 Vw(()) (Ymm - KemwW) = [1)(()) - -
where (u) = [Xvll: / N (w) Xtm] and (u) = [Yvali / (N)
Then according to KKrimi et al. 2016 Appendix B), (W)) is of (u)) smooth and o²(X, (w)) PL. Since
(u, W) = (w) h(u)) with h(u)
7 2
1(xx) # 1)
where huu) is independent of W, we have (u, W) is o (x)( smooth over W and
[u,
(x),
(W))W)
min (w() W
43

---

Published as a conference paper at ICLR 2025
20 (X,, (e> W) - min (u, e
(w,
(75)
W
indicating that (", W) is (x)) PL over W. On the other hand, we have
Xval Vrrin(u)Xe
(u) T (u) = (XTa) X vVNN(u)
= X + (N())eem
As (-) is strictly increasing and (- = 1 - vb(2), we have (1 - (ū)) < WN (N(()) = v())l and
Xval + 7(1 (ū)) Xern & (u) (w)
(u)) x X X + 7 ( Xem-
Moreover, the definition of X Xy(u) (u) suggests that it is of constant rank when a E U. In this way, the singular value of the data matrix will be bounded by
(x)( 2 0, (X vat + 7(1 (x) X =: 1h
(76)
max (x)( S max Xmal + r X Xum) =: Li
(77)
which means b, W) is uniformly smooth over W with Li and is uniformly PL over W with pm- Similarly, the lower-level objective lrrm W) is uniformly smooth over W with Ln and PL over W with Peu which are defined as
Nw == (1 - -bbūt)) (XTTxXem)
Taw = mmax (X Xtro)
G.3 LIPSCHITZ CONTINUITY OF SOLUTION TO THE PENALIZED PROBLEM
Lemma 26. There exists W arg argmin (u, W) such that W; (u) is L Lipschitz continuous over u where I. = 011. Moreover, [W](w)) s I." = 0(1)
Proof:
This result can be deduced from a general result under the PL. condition and the smoothness
of (u, -), demonstrated by (Nouiehed et al. 2019 Lemma A.3). Given that (u, -) is a squared loss composite with a linear mapping -- a specific case of a PL function we aim to separately derive the Lipschitz continuity of the solution set for clarity and simplicity.
Let W = X, (u) Y (u) be the minimal norm solution of miny (u, W), where (,) = [Xval: Xu) and (u()) [Yval: v (u) According 76 and (7)). we have
||x, (x()((u)
(
(0)
(ux)t (u3)
3
V2 max { ||x (u M1ا [x, (1)) (u'))) (u3))
V2
(u X2 (131)
a.
(7))2
V2
Vill ((l(V))((*) (
pd
V2
Vill
(
WN
v2
V/ [ | (u') (n(2)))12
2 /1
Tb(ū)
v2
/7 Kmml ||| u21 = o ( +)] u²1
21
where (a) results from Stewart 1977
Theorem 3.3), (b) is derived from the definition of Xx, (u). and
(c) because va- vb= comes from the 1-Lischitz continuity of the Sigmoid function (-).
Va+VE and the bound of / (ux)) + (v5()) 2 2 (77,, Vi and (d)
44

---

Published as a conference paper at ICLR 2025
Similarly, can derive the bound for Y, (u)
[Yx(u)ll2 = mmax (X,()) - V max Yval Xval + yV( t (um) =mm 0
- (0)
villyy WN (u²) (Nv(u²)) Ym
(6) 7 || II'' 20
0 = 10
2 (())
where (a) comes from the definition and (b) is derived from the Lipschitz continuity of Sigmoid
function, ||B||| - || and va vb a-b As result, for any ut and u², it holds that
va+vb'
[ - W (u - (x, (12)) (u²) + (1ll, X, (u
m2y0mux (Y vaal + + Vum)
Y 2 p1 ((ū)
||
||u u²ll.
2ph v ((ū)
Let us denote
Y trnl
max (Y vul ( Vim)
Lww =
[ = 0()
(78)
2/ (ū))
2p / (b(
then (w) is E Lipschitz continuous on Besides, the boundedness of W (u) can be earned by
[W)(w)] [xx (2) S max(n, + N
max(n, N + N' max (Y.T val + vbb()) Vum) I. = 01))
V
G.4 GLOBAL SOLUTION RELATIONS IN DATA
Based on the smoothness and PL of berm (u, W) over W, we are expected to analyze the approximate
behavior of the penalized problem (1]) to the bilevel hyper-cleaning problem IT). Since upper-leve level
problem is not Lipschitz continuous globally, the result in (Shen et al., 2023) can not be applied directly. light of Remark 3 we only focus on whether é2 solution of the penalized problem can recover some approximate solution of the bilevel problem in the following lemma.
Theorem 7. For any and any e2, suppose that there exists an solution (u, W) to the 7-penalized problem (TT) which has bounded norm ||W]| S R. and R is independent of and y. For such ez solution (u, W). there exists X* -OGT)) such that for any y > 7", (u, W) is also an (x))
solution to the bilevel problem 10 for some Ey
Similar to the representation learning, to ensure the penalized problem 11p is an e-approximate solution to the bilevel data hyper-cleaning problem (T)). i.e. 6y O(e), one need to choose ((V)) and set the penalty parameter y O(e Oce-05), Therefore, if we can verify the iterates generates by PBGD achieves c-solution of the penalized problem and are bounded with radius independent of and u, then PBGD can converge to some approximate solution of bilevel problem.
Proof: Given y, we first prove the Lipschitz continuity of the upper-level objective (validation loss) at the lower-level solution set, i.e. for any e2 solution (u, W') of 7-penalized problem with ||W]| < R. let Wa arg miny (irnu, W), ), then we have |[Wal = Projs(s) (W)ll S |[]] < R and
1
(w)((W= - lma \ X W112 111 - X Wa.l
(2Yval Xwa Xval Ww))
2 (1/Yaill + |X [ X |a||||||
|||
W.ll
45

---

Published as a conference paper at ICLR 2025
Yaall + [Xvval] R) [ ||l - W.ll.
Then by choosing 7" = [1] +| X || [2) X it follows that
Eval (W) + 7" (6 Ceral (u, W) -m) (u)) Lval (Wa)
2 (I) + Xvall It) [vailll| W.,1 + (fum (u, W) - ferm (u))
2 - (l/ + Xaai Rt) [vaall|| Wull + KwY
I W
2
2 min - (Ia (a |xaai| 1wy
2²
sERt
2
vaa II + (2) vavllll
(79)
2
According to the definition of e2 stationary point of y penalized problem, have (va((W) + (4rm(u, W) (u)) z lval (w)) + (lem(u, W..) firm (t)) + vval (W,)) ) + E2
vall (W) + 7"' (lor W/ fi (u)) t1 E
Substracting (W) from both sides and rearraging yields
eq = bern (u, W) tr (1) S El 62
77"
when y > 7² Then for any (u', W satisfying farn(', W') - -iim(u') S Ey,, it holds that
Evai(W) + 7(lern (u, W) (u)) S loai(W") 76tm (u', W") lirm (u')) +
Rearraging terms yields
Lvaa (W) S (W') + (Ceraa (u', W") Ct. (1') c2) + lval(W") + which means (u, W) is an (e2; ex) solution to bilevel problem.
G.5 PARAMETERIZED DATA AND LABEL MATRIX FAMILY ARE ACUTE
Lemma 27. For U, data matrix family (x,, u U) is acute, and (Yz(u), U} is acute. Therefore, Ran( X,, (u)) remains the same for u E U and so does (u))),
Proof: For any u, we can write (u) and (u) as
(v) [
Xval Xtm
[ I
Yval Yum
Ys(u)
(u)
(n)
According to Lemma 12 it is obvious that rank X (w)) rank([Xval val: Xum and rank(Y, (u))
rank([Yvat) Y Yuml)) which verifies the constant rank condition in Lemma property, we need to further prove that for any u and 2² if we denote A X., and B (u?). then ran rank(P PA PAB with PA AA and RA A'A.
show the acute
To do so, we first notice that, there exists diagonal matrix A such that B AA where
1
A
(oN(u))/oN(u')
Then we can write
A) (2) rank(AA'
rank(PABRA)
(80)
where (a) is because AAA A A. Furthermore, by singular value decomposition, decompose
Σ 0
A = TEVT with Σ =
E [NN+N')xm and orthogonal matrix U = [U U2] E
0 0
46

---

Published as a conference paper at ICLR 2025
Rmxm Also, by denoting rank(A) = r, know that Un E (( V1 E Rmxr and EΙ E Rexr are full rank. Thus, can be decomposed by
(N and V = [V1 V22
Σ1
V
ViT 122
A A= U1 U2]
0]
U.
0
V2
Besides, based on linear algebra knowledge, At Vi U.T In this way, we can further write
rank(PABRR)
rank(AAtA) (A) rank(U AUTEN)
rank(U, AU1) AU1)
(8) rank (VA VAU1)
(ank(VAU,) rank(U;) = =r=rank(1)
(81)
where (a) is derived from Lemma 12 with full column rank U1 and full row rank V, Σ₁, (b) is because a nonsingular diagonal matrix, (c) and (d) come from Lemma 12 Combining (80) and (81) with Lemma I1 we know A = (2') and B = xx,(2) are acute. Due to the arbitrary choices of uu.tu u² E Ur the family (u), u E Uf) is acute, which also holds for (Y)( E Uf.. By the acute matrices in Proposition [ the range space remains the same, which completes the proof.
G.6 MONOTONICITY OF LOSS FUNCTIONS
Lemma 28. Given w., v² E u and assuming u² S u² in the sense that un S ut for any then
((,)) lloT I W )12 S (uu - x. I, (u )1?
lovTT de (;( )1 - VI .t Wx("2
where {xi, yib are training data samples and (2/,, s/} are validation data samples. Moreover,
X ( X.In + 1) $ llv x (w)l
Proof: For a matrix A, we denote A, as the i-th row of A. For any a E U, we have
1l x W (2)122 = llvT x. (2)
lly, x, X
1lYYrm (m)
-= 1/
(Po (Y,
(82)
Then for u² < w², it holds that
llvT xx (,²))) 7 Pro (ron)>))
(x)) (V,
( 7 (b(())) Pro Proj (Y, 12
((()) " (X)
- > (o(()) -,
(uff)
vw()) - -'I((1 X, x (xxxx
vuu))
(uf2) x(ut)
1 = (12))2
where (a) is because Ran(X, (u=)) = Ran (X, (w²)) from Lemma 27 (b) is because each element
Y, (u+) ) is no greater than (u(x), ). For the validation loss, it can be proved similarly, while the only
difference is the fact that
2
W (w)l (1))((u) Xx(r))((())
47

---

Published as a conference paper at ICLR 2025
without magnitude of 1 ((u))= because (u) and (u) do not have such magnitude validation data points.
Finally, lrra (u, W) fm (u) 2 0 holds for any E 24 and W, we have
2 Σ (u,) [1iTT - w1? T
(IXim + 1) 20
holds for any U. Then letting u be the vector which equals to at i-th position and equals to -u elsewhere and taking ū + oo, we know
11 z. w - 11 (1 Ximm l + 1) 2 0
holds for any i and W. Taking W = (w) yields the conclusion.
Lemma 29. If [Xtmm X (Xtri Xvail' diagonal matrix, (u)u) is uniformly PL over u E U with Nu and is uniformly smooth over E U with Lu, and the constants are defined as
Na (1 (1-0(1--)))) x2
min; ll - O())) I
N
1 0(7).
(83)
2
1=1
Moreover, the gradient of E (u) is also bounded by Las i.e. V (u)l S Lu.
Proof:
Since (u, -) is smooth and PL., according (Nouiehed et al. (") = minw e (u, W) is smooth with the gradient
2019 Lemma A.5), we know
VV,(u) = Vu, W), vW arg argmin (u, W) = arg & ().
w
We write the minimal-norm optimal solution of penalized problem Wy(u) e min lu W). Plugging W (u) into (3). we know
|[VE,( I (u, (w, (w)) (o) - (v))) (L, W2(4)) min (u, W (u)))
2
(u))))) -()))²
(e min (u))
2
which suggests that (u) is ( [ū.... ut]. we have
PL over u E U. Besides, letting uo =
(w)) = min x; WW # 11} >0
min {1 ((())) (((I- 112 |1 ([Xemaxxx # 11} 2o
min (00 1]
min {> (1
(6) (- min {1u0 2. -0 0(1)
(84)
(())
where (a) comes from
yー ('4) |[((T (1
1 # 1) > 0
> 0 and [Xem x!m)s 1, (b) is due to Lemma 28 This means e (u) uniformly PL. over u E l/ with constant
and only if - (ps) -1|((( X,
Pn (1 (2))² min; flluT
x. (- un)
= 0(r).
(85)
48

---

Published as a conference paper at ICLR 2025
Moreover, Vulg(u, at W (u) can be upper bounded by
(V, Σ 2 (b({)) [IB.T - x. ww)(1 11 llv:l12
X * 11]
N
V2 vu(iil [IV. - x; w.)](1)) - 11:111 ([xtm Ximll + #1)
V1
1012
|IoTT x W)) Ilv ([XtrxxXim # #1]
2012
VA
[|lB (w)((1))
lluT - = (w))'))²
(86)
where (a) comes from similar derivation as of (84.. Similarly, for any W = (W( where a E [0, 1), Va Vunla (u', W) can be bounded by
(u', = Σ h Vubl)a xI
- w)ll
N
- -
S
Σ
|,,7 x.! (aW (1')) + (1- a)) (u²)))
7
1=1
| x. W W,(u"))) (1 a)r Σ
| - 2. (x2)))
ay
N
||wl|||u - x. (20)) (0)
(87)
Together 86 and 87
indicate that (u) is smooth because for any u., u, E R.N holds that
IV (u+)) - V.E((1P)
Vuls(u²
Wx(w")) (,e,((,,,,((")) - V,C(u",;;
V by (u), (W((") w; )\|l +
[ V. (V -
(u,, W7 (u ))ll - u/ + 22 (u W -
( llwT a. (1o x2ll
| |all - - W (wn) - ||u1 u21
where (a) comes from the mean value theorem with x' au + (1 a)u² and W bW (1 (1- (1-b)W; W) for some a, b E [0, 1], and (b) holds from 86 and (87). Therefore, we can define the smoothness constant of t
N
T.g 1o x.J Ww))il + 7
Σ | IllTT - 22. W; (
(88)
Besides the bounded Hessian, the gradient of (u, (w)) is also bounded by L,, because
[v)e(())|= 1\V (u, W W7 (u))l
49

---

Published as a conference paper at ICLR 2025
N
|Iv.- - =x x; WF 1 im Xtinle o 1)
N
Vub(u))) [IBT - w3))1
((X * 1)
1=1
N
[lly? - - xTT5(111))
(a)
7
1 z. (wo))l S Lo. Σ
N
(89)
where (a) can be obtained by (86)
G.7 GRADIENT ESTIMATION ERROR
Lemma 30. The gradient estimator has the bounded error
[V 7 (V Wh+1)
Vulara (u", [Z+t1)]]
5 C(221)) 20rmn (20)
26 (W0)) Mio
C(WO))
(1 -Bpkmo) 2//2
(90)
where Bpw = (3in(Biuon Mon, 321120
Proof: Let Z' = Projssut)) (Z we know |2'|| S |2 || and thus,
Veiinn (u²) Valum z (4)
V Veleral (ut )' Valum (u z11
N
Veb()))(l)) x._ 1111 ||u x. z=+1 12)
N
|2 - x. (Z' + z [ - 24+1
2
(lwell + || |==|||/z*++|||||=|||||| |>>||>/11|| - 24+111
Σ (llvell +
S(at))
(91)
where (a) results from the Danskin type theorem (Nouiched et al. 2019 Lemma A.5) that
(u* Vulera(u Z), VZ E S(u*). Then according to Lemmas 6 and tion k we have
each itera-
8lim (w 20) (a)
8lim (Zo)
| < 11 - 2011 112 112 +
1 +
(92)
and
d(zx+1 (((t))) d(Ztt.,S(utt))
,(( <
2 (lumlut, Zh.TT)
min leea("t, 2))
P/
2(1 Bpmw) (erm(ud 2k:00 mo lern
lern(ut (ut 22)
1ho
min lam (u+ 2)) 2(1 3Tpw)T (lmmlu 20)
P/
2
(6) 2(1 B Thrmu 700
(93)
p/
50

---

Published as a conference paper at ICLR 2025
where (a) and (b) hold because ming Erra l , Z) 2 0 and (b()) I 1. Plugging (92). (93 into 91
and defining C(Z%) >i= | 1(1 10 + v
8lem (20)
| vlll obtain that
28 21 (29) (1 31 T/2
E - Vleea(u., , z(+1)|| - =c(29)
(94)
Hww
Similarly, we define (u, W) = Eval (Va +7) W) and (5) == minw (u, W), as (u,-) is also smooth and PL, the gradient estimator of fú can be also bounded by
2e, (W
( - Vul, I
(1 B2122)
(95)
P
We then define (u) == minw (u, W) and since (u, W) = En(u, W) - (u), we have
(n) min (u, W) min (1, W) 2 (u) (u) (l
W
and thus (u) is differentiable and (u) = V (w) (w) - 7 Venn (u). Therefore, the gradient estimator of the penalized objective E can be bounded by
(v) 7 (V Wulimuu w - vul 10,,,z=11 1*)1
$ <IVV,(('*) (ul Wk+1)]l + V (2+))
Vleen (u z
s <
26 (29) (1- -1-1PMm) 31 +
22, (1 32
Mw
pd
1 (c1201)
2leru (29)
2E, (W0))
+ c(WO)))
(1 )
pile
where Bhw = m Bhr 32H
G.8 PROOF OF THEOREM 3
Proof:
We first prove the error bound condition of (u) over the constraint u E U. We denote
|| (u) llvT x. (1w
# 1)
(96)
so that (u) == vall W (u)) + 3 EN (u) Since (u, :) is uniformly PL, so the gradient of (u) can be calculated by the Danskin type theorem as
2 ((((a) [INT x; W (w)l ([Xum #1]
(w)
2
7 (((a)(( ((u))) [1oTT x; WW (w)l2
|| PP1(( [[ Xtealé # #1]
2
7
2 -(())(-v(u))a ((u)))
which means e, (u) is non-decreasing and (projected) gradient flow will never fluctuate, i.e. u/+11 < = holds for any k. In this way, the projection operator is effective at most at the end point. If (u) attains minimum for some u E int then cu(u) = In this case, iterates generated by projected gradient descent converge to min E, (u) = min, E (u) because the projection operator is ineffective along the trajectory.
If (u) attains minimum on the boundary projected gradient descent will still converge to min (u) by contradiction. is clear that lim (u²) < mingeu E, (u) can not hold because = E U. Therefore, without loose of general- ity, we assume that limg-ro E (u*) > min E, (u). Then according to the non-decrggg property of E, (u), we know limg- a > so that the projection operator is ineffective at any iteration
U. we will then prove the sequence generated by
51

---

Published as a conference paper at ICLR 2025
K. By smoothness and denoting Vet(u") == (Vulumu", Wh+1)- ( Vulerauu Fulam(u(,Zht!1) z(+1)) ,eg
min fn (u)) for any k < K,
(1 S (7(2)) + (V - (u a²Lة (
2
- kg(4") all ) aLLu |V ||1 - -eg((") + veg(u())
+ سb5م (1 + Ve)("") (eg("r) VEG(ut)
2
L Ve (u (ū + - -
2 (u - a
2
(
3 ((()) ann (u*) (g) + aLu (u + 22) vE((a\)
(9)
3 (g()) (E (u*) - -Eg
(W7 1bu
2lmm (2 Veu
+ + + 2)7
+ +C(29)
(1 (1--3pp ) (97)
where (a) comes from the Cauchy-Swei Swartz inequality, [V (t)ll S L., in Lemma 29 ab S 1 and
a ( = |u* - -Proiz (w*- a (. S
2u
(b) results from blockwise PL condition, and (c) is derived from 90). Subtracting E from the both sides of (97). we get
f7 (1 Eú s (1 (1)))))((((()))))))))))))))))))) -G)
(C(No)) 22,, (W, 1/b6
2lrra (202) ) (1 - )
+ (abn(++)) 2)7
+ C(Z9)
(98)
Telescoping 988 from & = 1 to K yields
(1()) E s (1 amt) K (e,, (u") -x))
L. 2
C(WO))
2F, (Wo)
C((Z))
2tra (Z4)
Mui
8pw) T/2,
(99)
Taking + co, we know lim (, = min C,(1) S min f (u) which yields a contradic- tion to limg-roc (7(2²) min (u). In conclusion, choosing 7 = Oce.5), and to achieve the e-stationary point of the penalized objective, we can set T = Ollog 1 and K = Olloge
Besides, according to Lemma 26 the minimum norm solution W arg minw (u, W) is
bounded by L.j = (1). Moreover, according to (Oymak & Soltanolkotabi] 2019). GD on lincar regression converges to the closest minimizer the initialization. Therefore, the iterates of PBGD satisfics
[W*|| < || Projw; (W)))) + ||Proiw; (wt) (W < 0(1)( 3ppm. T/2 L'
where the bound independent of ry. Then according to Theorem 7 the e-stationary point of the pe- nalized objective with y = (c0.5) recovers an (c,c) optimal point of the bilevel problem. Therefore, the iteration complexity of PBGD to achieve an (e, optimal point is TK = O(loge-1) -1)2).
H NUMERICAL EXPERIMENTS
In this section, we provide numerical results for global convergence of PBGD in representation learning and data hyper-cleaning.
52

---

Published as a conference paper at ICLR 2025
H.1 REPRESENTATION LEARNING
Considering the overparameterized and wide neural network case, we choose N = 30, N' = 20, m 40, n = 10, h = 300. First, we respectively generate data matrix Xue E RR Xval E R xm from Gaussian distribution (5,, 0.01) and (--3, 3, 0.01) to model different cluster of data. Then we generate optimal W E _ W E Rk*a from Gaussian distribution N (0, 0.01) and (2, 0.01), respectively. Moroever, we generate the optimal weight under validation dataset W R by W3 ~ VWW,, 0.001). This ensures that I - -W2 is not too large with high probability, satisfying Assumption Finally, we use WT. W W to generate the label matrix. For the bottom layer, we want both training label and validation clean label finds the shared optimal weight WT. However, for the adaptation layer, they should exhibit distinct behaviors due to the different clusters. Specifically, the training labels should find the optimal weight W2. while the validation label should find the optimal validation adaptation weight W Inspired by this, we generate the label matrix by
Yum ~ NX WT Wg 0.01); Yval (Xtmn Wi 0.01).
We test the PBGD in Algorithm on this synthetic representation learning problem and plot the upper- level and lower-level relative eπror versus iteration in Figure We measure upper-level relative error by Lval (W,, -2)-L اiاا where Li minw, mins,, (Wa, W2), and lower-level relative error measured by Lern ( (W,, Wa) Lim (.)). By the closed form of Lir (W1) in Lemma 16] lower-level relative error is accessible. On the other hand, Lis R Lvai (WT, W2) because W E S(Wi) is
is closed the unconstrained minimal value Lvai (WT, W3) which is also small. As (aa W2) is only an estimate of Liag. there exists cases where Lval (W1, W2) - Lva W2) < 0, so in practice, we use [Lva( W2) Lval Lva W2)l to estimate the upper-level relative error. Since the convergence of lower-level relative error suggests W2 WT, the convergence of upper-level relative error will indicate that W1 + W7-
feasible and [W2 Wall S so that (W7, W2)
We select the best stepsizes a. 3 and the number of inner loop Tg = T by grid search. It can be observed from Figure PBGD converges almost at a linear rate certain accuracy, and the relative error decreases as increases. The fluctuation in the upper-level error near convergence due the global convergence result Theorem [ not being strictly decreasing because of the (E) error at each step. When upper-level and lower-level relative errors are sufficiently small, the additional ((e) error has larger impact, leading a slight increase in error. However, the final error remains small, around 10-5 when K and is large enough. This validates Theorem I that by setting target accuracy determined by y at almost linear rate.
y large enough, PBGD globally converges
The fluctuation in the upper-level error near convergence in representation learning is due to the global convergence result in Theorem [ not being strictly decreasing because of the (E)) error error at
each step. When upper-level and lower-level errors are sufficiently small, the additional O(e) error has larger impact, Ieading to a slight increase in error. However, the final error remains small, around 10-5 when K and is large 7 10, 500. This validates Theorem I that by setting y large enough, PBGD globally converges to a target accuracy inversely determined by y at almost linear rate.
H.2 DATA HYPER- CLEANNNG
Considering the overparameterized linear regression with small clean validation dataset and large dirty training dataset, we choose N = 100, N' = 10, m = 200, n = 10. First, we respectively generate data matrix Xtra E N .Y,al E IR N' xm from Gaussian distribution (55 0.01) and (--3. 0.01) to model different cluster of data. Then we generate optimal clean weight W e m=' from Gaussian distribution (1,, 0.01) and generate the clean label matrix for validation dataset as Yuu ~ (X Wai W* 0.001). For the training label matrix, we first generate optimal classification parameters (b4) ~ (ernoulli(0.2) and then generate the label matrix as
Yum ~ (N W', 00.01) + ((u) C (10, 10)
where (u) = (u1); ((z)):: ... ( ) and @ denotes the Hadamard product. This ensures the training dataset is polluted with probability 0.2.
We run PBGD in Algorithm 2 on this synthetic data hyper-cleaning problem and plot the upper-level and lower-level relative errors versus iteration in Figure 3 We measure the lower-level relative
53

---

Published as a conference paper at ICLR 2025
error by lrra (u. W) - (u) with closed form in Lemma 23 and the upper-level relative error by (aa(())( val where (va = mist, (W). We estimate (val se minw (va(W) vall (W*) because there exists such that the selected data matrix V VbN (u) is almost full rank so that selected training dataset and validation dataset share a joint minimizer W.
We select the best stepsizes a, 3, 3 and the number of inner loop Ti T by grid search. It can be observed from Figure that PBGD converges almost linear rate certain accuracy, and the relative error, especially at the lower level, decreases as " increases. The final error remains small, around 10-5 when K and is large enough. This coincides with our Theorem I that PBGD globally converges to a target accuracy inversely determined by 7 at almost linear rate. Furthermore, sensitive to the choice of 7 noted in Theorem where the
the lower-level relative error is lower-level relative error Ey is inversely related to
54


Reviews:
[{"review_id": "4dHzy7ypzd", "reviewer": "Reviewer_GMWV", "summary": "This paper studies the convergence properties of a penalized bilevel gradient descent (PBGD) algorithm, aiming to obtain global optimal solutions of bilevel optimization problems under the joint and blockwise Polyak-Łojasiewicz (PL) conditions. The joint and blockwise PL conditions are validated in the context of two specific applications: representation learning and data hyper-cleaning. Numerical experiments are provided to substantiate the theoretical results.", "questions": "In Line 1226, why is the blockwise PL condition of $L_\\gamma$ over $u$ sufficient to ensure the PL condition for $L^*_\\gamma$?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThe study of convergence of bilevel algorithms to global solutions is an interesting topic, and this paper offers an approach.\n2.\tThe paper includes concrete application examples that validate the assumptions necessary for establishing global convergence results.", "weaknesses": "1.\tWhile the topic of global optimal convergence in bilevel optimization is engaging, the approach presented in this work does not appear as innovative as suggested by the title. The main idea relies on the joint/blockwise PL condition of the penalized objective $L_\\gamma$. However, it is well known that when the PL condition holds, any stationary point is globally optimal, and the proximal-gradient method can achieve linear convergence to this global optimum (see, e.g., Hamed Karimi, Julie Nutini, and Mark Schmidt, Linear Convergence of Gradient and Proximal-Gradient Methods under the Polyak-Łojasiewicz Condition, ECML PKDD 2016). Furthermore, the convergence of PBGD to a stationary point of $L_\\gamma$ under the PL condition has been well studied in existing literature (e.g., Bo Liu, Mao Ye, Stephen Wright, Peter Stone, BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach, NeurIPS 2022, and Shen, Han, and Tianyi Chen, On Penalty-Based Bilevel Gradient Descent Method, ICML 2023). Thus, the approach in this work may lack novelty, and the contribution seems somewhat incremental.\n2.\tAlthough the authors have put considerable effort into verifying that the joint/blockwise PL condition can be satisfied in specific applications, such as representation learning and data hyper-cleaning, only very restricted cases are analyzed, with strong assumptions imposed. For instance, Assumption 2 in the representation learning setting and the assumption $X_{trn}X_{trn}^{\\dagger}$ is a diagonal matrix in data hyper-cleaning narrow the applicability of the results and limit their general applicability. The theoretical analysis appears heavily dependent on these assumptions, raising doubts about whether the joint/blockwise PL condition would hold in broader or more practical cases, or even in other bilevel optimization applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CPlIsvV3dc", "reviewer": "Reviewer_Bn7x", "summary": "This paper presents a theoretical framework for achieving global convergence in bilevel optimization. The authors propose that a constrained reformulation generally yields a benign landscape, and they analyze the global convergence of penalized bilevel gradient descent (PBGD) algorithm for bilevel objectives under the proposed joint and blockwise PL conditions. The paper illustrates that the specific applications of representation learning and data hyper-cleaning can satisfy these PL conditions. Theoretical results are then supported by experiments conducted on these applications.", "questions": "1. How should one choose between joint and blockwise PL conditions for a given application?\n1. Could you please clarify which aspects of the convergence results would generalize to more complex settings like non-linear models?\n1. What practical takeaways does this work provide for achieving global convergence in more complex bilevel applications?\n1. How robust are the convergence results if the PL conditions are only approximately met?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The main strength is that it is a pioneering work that studies the challenging and important problem of global convergence in bilevel optimization, a topic with substantial real-world relevance. The proposed analysis extends PL to both joint and blockwise PL conditions and verifies them on two application cases. Overall, the paper is well-organized and easy to follow.", "weaknesses": "I have several concerns and comments on the submission (please correct me if I am wrong):\n\n1. The applicability of the developed theorem seems unclear. The proof closely dependent on and follow existing convergence theorems for PBGD, and it’s unclear whether the analysis could extend to other bilevel algorithms. The non-additivity of PL conditions poses a great challenge for applying the developed theorem and no practical solutions are provided. The two applications studied rely on linear models and strong convexity of loss, which is overly idealized and simplified.\n\n1. Moreover,  in line 228 (Section 3), the authors mention that convergence analysis may need “fine-tuning per application,” but it remains unclear which parts of the analysis are generally hold, such as whether the iteration complexity $𝑂(log⁡(𝜖^{−1}))$ generally holds to other settings that satisfy PL conditions. It also mention that \"This may also shed light on a broader range of bilevel problems involving sophisticated neural network architectures in machine learning\", but the paper lacks clearly summaries practical takeaways got from the developed theorem for achieving global convergence in such complex applications with modern non-linear deep models.\n\n1. The numerical analysis lacks depth and discussion on robustness. I am suggesting throughly evaluating how values of parameters $\\alpha$, $\\beta$, $\\gamma$ are set theoretically as well as practically, and whether the observed results match theoretical expectations on the convergence rate. Also, exploring how slight violations of PL conditions affect convergence would help clarify the robustness.\n\n1. Section 2 provides an example to illustrate the complexity of the nested objective $𝐹(𝑢)$ caused by the lower-level mapping $𝑆(𝑢)$, but it lacks rigorous analysis of how the constrained formulation reliably produces a more benign landscape and to what extend. A precise definition of benign landscape in the context of bilevel optimization is also helpful. The conclusion that constrained reformulation yields a benign landscape relies heavily on prior literature (lines 211-215) rather than in-depth analysis in this paper.\n\n1. In line 373 (page 7), matrix $𝑊_3$ is introduced without a clear explanation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XOjXBIcXem", "reviewer": "Reviewer_Dv2u", "summary": "The paper explores global convergence in bilevel optimization, a crucial yet challenging objective due to the non-convexity and potential for multiple local solutions in bilevel problems. To address this, the authors propose sufficient conditions for global convergence and illustrate these in bilevel learning applications such as representation learning and data hyper-cleaning.", "questions": "1. Could the authors expand Section 1.1 with detailed theorems? The sentence following C3, “The joint and blockwise PL condition… are not assumptions, but the properties of the penalty reformulation,” is confusing. The authors should clarify the assumptions needed to establish global convergence rigorously.\n\n2. In what specific way is “global optimality” used in the paper?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper offers conditions that ensure global convergence in bilevel optimization by generalizing the Polyak-Lojasiewicz (PL) condition.", "weaknesses": "While global optimality is underscored as essential, the precise definition or context of “global optimality” within this framework is unclear. A clear explanation of how this term is specifically applied in their method would strengthen the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UWgp9Eaxg4", "reviewer": "Reviewer_5tcw", "summary": "The paper proposed two PL conditions, by satisfying which the global optimality of bi-level optimization can be achieved using simple algorithms like Gauss-Seidel.", "questions": "Can it be applied to a more general bi-level optimization with constraints in (1)?", "limitations": "", "rating": 3, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "Achieving Global optimality is an important property.", "weaknesses": "The paper's assumptions are very restrictive. For most bilevel optimization problems, the Joint and blockwise PL conditions cannot be guaranteed, and even checking these conditions can be challenging.  The representative problems illustrated in the paper are very specific simple cases. For example, only linear models can satisfy the assumption for representation learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9Ji93dEJ0W", "reviewer": "Reviewer_4hB6", "summary": "This paper propose a new bilevel optimization algorithm. This paper is generally very well written and provide plenty of theoretical results. Overall this paper is clear a good paper. If all these results are correct, this paper should be clearly accepted (However, I am inadequate to go through all proofs).", "questions": "1. What does the a pilot mean in the title?\n\n2. Line 057, a benign landscape, is there a direct meaning for that?\n\n3. Line 53, the  goal of this paper, this sentence is not important. Do not need to emp{}. \n\n4. The numerical results seem too little? Does the proposed method outperform SOTA bi-level methods?\n\n5. What are the best convergence results for bi-level optimization method before this paper?\n\n6. line 414, what does \\gamma to be O(\\epsilon^{-0.5}) mean? If gamma is very very large (with a very large constant), can the algorithm still converge? What is the meaning of O(xx) here?\n\n7. Will PL condition a bit too strong?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "good. This paper is overall well written and provide plenty of theoretical results.\n\nThe proposed method also solves the neural network cases. That's especially good.", "weaknesses": "1. Experiments are not adequate. \n\n2. Some fonts seem strange.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "P0xpd23Rct", "reviewer": "Reviewer_FJVZ", "summary": "This paper studies the global convergence rate of bilevel optimization. The main result is that if the penalized objective satisfies the PL condition, then the bilevel problem have almost linear global convergence rate if PBGD method is used to solve the problem. Then the authors give two applications: representation learning and data hyper-cleaning. These problems can be formulated as bilevel optimization problems, and their penalized objectives satisfy the PL condition. Thus, when applying PBGD algorithm, they should converge almost linearly. The preliminary computational results also support the theorem.", "questions": "1.\tMajor Concerns:\n\n(a) In line 261, Danskin theorem is mentioned, then the gradient is calculated. Also, the variable $\\omega$ is introduced later. I think it would be better to explain the connection and point out that the using Danskin theorem, the auxiliary variable $\\omega$ will help us to find a good estimation of the gradient with respect to $u$.\n\n(b) It may be better to put Algorithm 1 and 2 on Page 6 after the authors have summary these algorithms. It will give the readers a smooth reading experience.\n\n(c) In section 6, you may want to specific the choice of $\\alpha$ and $\\beta$ and make sure that they satisfied the conditions stated in Theorem 2 and 3.\n\n(d) If possible, adding more baseline methods would help readers better understand the convergence rate of the PBGD method. This is not necessary given the limited time.\n\n2.\tMinor Concerns:\n\n(a) The sentence in line 199 is not very clear, please double check.\n\n(b) There’s a “?” in line 309, please make sure it is correct.\n\n(c) Misspelling in Line 973 and Line 2189. “invertiable” to “invertible”.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Clear Problem Statement: The authors articulate the limitations of existing methods, particularly those that only guarantee convergence to local minima or stationary points, which motivate them for pursuing global convergence.\n\nTimeliness and Relevance: The paper proof the global convergent rate for a certain type of bilevel optimization problems. Given the increasing application of bilevel optimization in machine learning and high-stakes fields, this work has substantial relevance.\n\nTheoretical Contribution: The authors provide sufficient conditions for achieving global optimality. By leveraging the penalty reformulation approach, the paper establishes an almost linear global convergent rate for some linear bilevel optimization problems.\n\nExperimental Validation: The empirical results test on bilevel learning problems like representation learning and data hyper-cleaning. The preliminary computational results support the almost linear convergence theorem.", "weaknesses": "Assumptions and Limitations: While the paper claims global convergence for bilevel problems, it focuses primarily on linear models. Expanding the theoretical foundation to nonlinear models or other loss functions would improve the paper’s generalizability.\n\nComparative Analysis: While the paper mentions other approaches, a direct empirical comparison with state-of-the-art methods for bilevel optimization would strengthen its validation.\n\nConnection between Theory and Experiment: the author should clearly specified the connections between the theory and experiment so that the experimental results can support the theory. For example: in section 6, the author should specific the choice of the step length and make sure that they satisfied the conditions stated in Theorem 2 and 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)