Generalized Smooth Bilevel Optimization with Nonconvex Lower-Level
Authors: Siqi Zhang
Xing Huang
Feihu Huang
Venue: ICML 2025 poster (2025)
Keywords: Bilevel Optimization， Nonconvex，Generalized Smooth
Primary area: optimization->nonconvex

Abstract: Bilevel optimization is widely applied in many machine learning tasks such as hyper-parameter learning and meta learning. Recently, many algorithms have been proposed to solve these bilevel optimization problems, which rely on the smoothness condition of  objective functions of the bilevel optimization. In fact, some machine learning tasks such as learning language model do not satisfy the smoothness condition of objective functions. More recently,  some methods have begun to study generalized smooth bilevel optimization. However, these proposed methods for generalized smooth bilevel optimization only focus on the (strongly) convex lower objective function. Meanwhile, these methods only consider the generalized-smooth upper-level objective, but still require the standard smooth lower-level objective in the bilevel optimization. To fill this gap, in the paper, thus we study the generalized-smooth bilevel optimization with the nonconvex lower-level objective function, where both upper-level and lower-level objectives are generalized-smooth.
 We propose an efficient single-loop Hessian/Jacobian-free penalty normalized gradient (i.e., PNGBiO) method. Moreover, we prove that our PNGBiO obtains a fast convergence rate of $O(\frac{1}{T^{1/4}})$ for finding a stationary solution, where $T$ denotes the iteration number. Meanwhile, we also propose a stochastic version of our PNGBiO (i.e., S-PNGBiO) method to solve stochastic bilevel problems, and prove that our S-PNGBiO has a fast convergence rate of $O(\frac{1}{T^{1/6}})$.  Some experimental results on hyper-parameter learning and meta learning demonstrate efficiency of our proposed methods.

Generalized-Smooth Bilevel Optimization with Nonconvex Lower-Level
Siqi Zhang' Xing Huang'
Feihu Huang
Abstract
1. Introduction
Bilevel optimization is widely applied in many machine learning tasks such as hyper-paramette parameter learning and meta learning. Recently, many algo- rithms have been proposed to solve these bilevel optimization problems, which rely on the smooth- ness condition of objective functions of the bilevel optimization. In fact, some machine learning tasks such as learning language model do not sat- isfy the smoothness condition of objective func- tions. More recently, some methods have be- gun to study generalized smooth bilevel optimiza- tion. However, these proposed methods for gen- eralized smooth bilevel optimization only foeus on the (strongly) convex lower objective func- tion. Meanwhile, these methods only consider the generalized-smooff upper-level objective, but still require the standard smooth lower-level ob- jective in the bilevel optimization. To fill this gap, in the paper, thus we study the generalized- smooth bilevel optimization with the nonconvex lower-level objective function, where both upper- level and lower-level objectives are generalized- smooth. We propose efficient single-loop Hessian/Jacobian-fe penalty normalized gra- dient (i.e., PNGBiO) method. Moreover, we prove that our PNGBiO obtains a fast conver- gence rate ( for finding a stationary solution, where denotes the iteration number. Meanwhile, we also propose stochastic version of our PNGBIO (i.c.. S-PNGBiO) method to solve stochastic bilevel problems, and prove that our S- PNGBiO has fast convergence rate of O (71/)) ). Some experimental results on hyper-parameter learning and meta learning demonstrate efficiency of our proposed methods.
In this work, we focus on studying the following nonsmooth nonconvex bilevel optimization, defined
min wER (EV
f(z v).
(UL)
(I)
s.t. y y²(x) arg min g v), yERP
(LLL)
where the upper-level (UL) function f(z, y) : R XRP + R is generalized-smooe and nonconvex with respect to (w.r.) the variables æ and y, and the lower-level (LL) function g(x, v) R2 R" + generalized-smoot and weakly convex w.r.t the LL variable y. Problem (1) frequently appears many machine learning tasks such meta learn- ing (Hao et al., 2024; Gong et al., 2024b) and deep neural network pruning (Gao et al., 2024). Recently, bilevel opti- mization has widely received attention in machine learning community, due to its ability of capturing the hierarchical structures in many machine learning tasks such as meta learning (Ji et al., 2021; Hao et al., 2024) and reinforcement learning (Hong al., 2023). Meanwhile, many algorithms have been developed to solve the bilevel optimization prob- lems.
When the lower-level objective function g(z, y) on the vari- able y is strongly convex and twice differential, fortunately, we can get a closed-form gradient of the upper-level objec- tive function F(x) = f(x,, y² (1:)), defined
VF(x)= ViJ(I, (1)) Vi2g(z, y² (x)) (x)).
(2)
Recently, based on the above closed gradient (2), some effective approximated gradient algorithms (Ghadimi & Wang, 2018; Ji et al., 2021; Hong et al., 2023) have been pro- posed to solve bilevel optimization by using the following approximated gradient:
V Vʃ(, () Vis(x, Ving(r, Vig(a (e)(x)))
'College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China. 'MITT Key Laboratory of Pattern Analysis and Machine Intel- ligence, Nanjing, China. Correspondence to: Feihu Huang <huangfeihu20186 2emn gmai..com>.
where is approximate of the solution y (x) arg min, g(z, y). For example, (Ghadimi & Wang, 2018) proposed class of approximated gradient methods based on approximate implicit differentiation. (Ji et al., 2021) 1) pro- posed an effective approximated gradient methods based on
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Snveralized-mmoole Bilevel Optimization with Nonconvex Lower-Level
Table Comparison of our method and the existing methods for generalized-smooth bilevel optimization. Here denotes the standard smoothness condition. GS denotes the suneralized-smoothnee condition. SC denotes the strongly convex condition. NC denotes the non-conver condition. H.J.F. stands for Hessian/Jacobian Free. Here f(. -) and g(: denote the upper-level and lower-level objective
functions, respectively. g(x, denotes function on the second variable with fixing variable x.
Algorithm
Reference
9(5))
f(..))
g
Single-Loop
H.J.E.
BO-REP
(Hao et al., 2024)
S
GS
SC
SLIP
(Gong et al., 2024b)
S
GS
SC
ACCBO
(Gong et al., 2024a)
S
GS
SC
ONGBIOIS-PNGBIO
Ours
GS
GS
NC
the iterative differentiation. More recently, (Huang, 2023; 2024) studied the nonconvex bilevel optimization where the lower-level objective function g( y) on the variable is lo- cal strongly convex based on the following projection-aided approximated function, defined as
functions. More recently, thus, some methods (Hao et al., 2024; Gong et al., 2024b) have begun to study generalized smooth bilevel optimization. However, these proposed meth- ods for generalized smooth bilevel optimization only focus on the (strongly) convex lower objective function. Mean- while, these methods only consider the generalized-smood upper-level objective, but still require the standard smooth lower-level objective in the bilevel optimization.
fax ()) (I,(2,0) 9)
(4)
Vi22(1 i) (5 (m. (229(1, 0)]
V (2, 0);
In this paper, to fill this gap, we study the generalized- smooth bilevel optimization problem (1), where both upper- level and lower-level objectives are generalized-smooth, and its lower-level is nonconvex. We propose an efficient Hessian/Jacobian-fiee penalty normalized gradient (i.e.. PNGBiO) method to solve the deterministic problem (1). Meanwhile, we also propose stochastic PNGBIO (i.e., S-PNGBiO) method to solve the stochastic version of prob- lem (1), defined as
where Si 5. denotes a projection on the set {X E Rd f S e(X)= S 1. and e(.) denotes the eigenvalue func- tion. In particular, (Huang, 2024) proposed an optimal Hessian/Jacobian-ffeer method by using finite-difference es- timator to approximate the projection-aidee function (4),
When the lower-level objective function g(r; y) on the vari- able y is not (local) strongly convex, unfortunately, we can not get a flosed-form gradient defined in (2). Thus, most of the existing methods (Liu al., 2021; 2022; Kwon al., 2023a; Liu et al., 2024) solve the following single-level con- strained optimization problem instead of directly solving the bilevel optimization problem, defined as
min BenD (F,,IF(E, E)], xER". s.t. (x)) 2 arg min I EG-o[G(x, 2) yERR
(UL)
(7)
(LL)
min #ER" NER"
(F s.t. gL.g( v) - min g(z, y) S.O (5) yERP
where [(x v) = [F= {)] and g(و, v) Eç~o y: {)]. Here & and Ç are random variables.
=
For example, (Liu et al., 2021) proposed a falue-function- based interior-point method for nonconvex bilevel optimiza- tion. Meanwhile, (Liu et al., 2022) designed an effective dynamic barrier gradient descent method for bilevel opti- mization. More recently, (Liu et al., 2024) solve a variant of the single-level constrained optimization problem (5), where uses its Moreau envelope instead of the problem minyeRe g(x, y) in the problem (5), defined as
In summary, our contributions are as follows:
(1) We propose an efficient single-loop PNGBiO method to solve the generalized-smoont smooth nonconvex bilevel prob- lem (1). Meanwhile, we also present a stochastic ver- sion of PNGBIO (i.e., S-PNGBiO) method to solve problem (7). In particular, our methods only use the first-order gradients instead of high computational Hes- sian/Jacobian matrices, so it has lower computation each iteration.
min yER" f(z. v) s.t. g(z, y) (x v) S 0,
(6)
uy (x, = min g(z, 0) + 27 0 - 21 - BER
(2)
We present a solid convergence analysis for our meth- ods. Under some mild conditions, we prove that our PNGBiO method obtains a fast convergence rate of O T774 for finding a stationary solution of the prob- lem (1). Meanwhile, we also prove that our S-PNGBiO 1 method has a fast convergence rate of O (17a) ) for find- ing a stationary solution of the problem (7).
So far, the above methods for bilevel optimization rely on the smoothness of its objective functions. In fact, some machine learning tasks such as learning language model (Zhang et al., 2019) and distributionally robust optimization (Chen et al., 2023) do not satisfy the smoothness condition of objective
2

---

Generalized-Smooth Bilevel Optimization with Nonconvex Lower-Level
(3) We provide some numerical experiments on data hyper- cleaning, hyper-parameter learning and meta learning to demonstrate efficiency of our methods.
jection operator to replace high-cost matrices with low-cost first-order gradients. On the other hand, (Liu et al., 2024) proposed the MEHA method for general bilevel optimiza- tion with nonconvex and possibly non-smooth LL objective functions, avoiding Hessian-related approximations and en- abling single-loop implementation.
2. Related Work
In this section, we review the generalized smoothness condi- tion in optimization algorithms and the algorithms of bilevel optimization with nonconvex lower-level.
Notation
For notational simplicity. let Vif(x, y) and V2f(2, y) de- note the partial differentiation of function f(z,, y) on the first variable x and the second variable y, respectively, || I|-Il denotes the lg norm for vectors and spectral norm for ma- trices. (x,, v) denotes the inner product of two vectors a and y. Jt == a (a:; y S0
2.1. Generalized smoothness condition
The generalized smoothness condition firstly was studied in (Zhang al., 2019), and was applied to the gradient clipping and normalized gradient methods. Subsequently, (Zhang et al., 2020) studied the momentum-basse gradient clip- ping method under the generalized smoothness condition. Meanwhile, (Qian et al., 2021; Zhao et al., 2021) studied the incremental gradient clipping and stochastic normalized gradient methods under the generalized smoothness condi- tion, respectively. Recently, (Chen et al., 2023) proposed new symmetric generalized smoothness, which extends the standard (Ln, L1 -eeneralizzd smoothness, and studied the variance reduction under this symmetric generalized smooth- ness condition. Subsequently, (Li et al., 2023) presented a more generalized smoothness condition and studied various gradient-basee methods under this condition. More recently, (Hao et al., 2024; Gong et al., 2024b) studied the bilevel optimization under the wwwrliieed-mmoohheeee condition. Mcanwhile, (Xian et al., 2024) also studied the nonconvex minimax optimization under the generalized-smoothnee condition.
So S0 g: g. ... , Sj. Sy St) is o-algebras. E[-]F;]] is the conditional probability given the t-th iteration. And B[.) is the expectation operator w.n.t. stochastic variables. Let {ar) denote a sequence.
Sy.
3. Preliminaries
In the problem (1), since lower-level objective g(,; y) is nonconvex on variable y. we can not easily get the mini- mum of lower-level problem minyeR> g(x, y)- Thus, reformulate the lower-level problem by using a value func- tion defined as:
((x)
- min g(Z, v). yERP
(8)
Then, the problem (1) is equivalent to the following nonlin- ear programming problem
min (R XRP
f v), s.t. g(r, v) v(x) 0,
(9)
2.2. Bilevel optimization with nonconvex Lower-Level
In recent years, numerous methods have been proposed to solve the bilevel optimization with nonconvex lower- level. For example, (Liu et al., 2022) proposed a first-order method for nonconvex-Pi PI. bilevel optimization with noncon- vex LLL satisfying the PL condition. (Shen & Chen, 2023) designed penalty-based gradient method for constrained nonconvex-PL cases. Subsequently, (Huang, 2023) pro- posed momentum based gradient methods for nonconvex- PL bilevel optimization. Meanwhile, (Kwon et al., 2023a) studied nonconvex bilevel optimization with L.L meeting the proximal error-bound (EB) condition similar to PL. (Kwon al.. 2023b) proposed the F²BA method for nonconvex- PL. bilevel optimization, achieving the O(- gradient complexity when finding e-stationary solutions. However, this method requires stricter conditions such as the Lips- chitz Hessian of the upper-level function f(z, y). Although achieving certain results, they both rely on computation- ally expensive projected Hcssian/Jacobian matrices. To address this issue, (Huang, 2024) proposed the HJFBIO method, using a mnite-differene estimator and new pro-
which was initially introduced by (Outrata, 1990). Unfortu- nately, the local solutions of the reformulated problem (9) do not necessarily correspond to the stationary points of the problem (1) (Alcantara & Takeda, 2024). Therefore, we consider Moreau envelope problem of problem (9) as in (Liu et al., 2024), which also can be seen as approximate problem:
min (x.g)eR xBo
(x,v), s.t. AL.g(z,)) - Vn, v) S 0, (10)
10 - yl? By (z. y) = min (x, 0) + 27
BER
where 7 > 0 is regularization tuning parameter. Here we solve the following Lagrange function (i.., penalized func- tion) instead of directly solving the problem (10), defind as:
min f(x, y) + &c (g(a,))) - (x, v)), wER' Weer
(11)
where e > is penalty parameter.
3

---

Generalized-Smoothh Bilevel Optimization with Lowervves
Lower-Level
Algorithm PNGBiO Algorithm
Bieevel Optmization min sell)saa1
Approximate
Input: Iteration number T, initialization xº, yº, 80, learning rates nr at, St,St, proximal parameter y > 0, penalty parame-
(*()) ang g) yelr
ter C. > 0:
Approximated Optimization
Output: x²' 1²
Equivalent
((aa)), (L.tz.)) 1,12.))
1: for t 0, 1, , do
(. 1ea 0)x 19-11 xip
2: g++ = 0¹ 77 V2g(x', (00(xx,000 89) + 1 (0' -v));
vort go
3: Compute dz = 1 Vif(e', 3 + Vig(o', y0)
s(e) mup pl
Approximate
Vig(z', 0
4: Update x²+1 = x' - a1
df
Figure I. Relationship of the bilevel optimization problem (1) and the approximated optimzation problem (10).
Compute d' 1
V2f(x' (x' ,,²) + V2g(a ,00
[ yy)); a
6: Update y = y² - Bg d
For the problem (11), we consider the following residual function, defined
end for
[Z v)= == dist(0, vf + a
Co (Vg(z, Vuy (ar, u))).
to update the variables and y. respectively. At the lines 4 and 6 of Algorithm 1, we use the normalized gradient descent to update the variables x and y. Compared with the MEHA algorithm of (Liu et al., 2024), our PNGBiO algo- rithm uses the normalized gradient descent iteration, which unify the feature scales make the gradient update more stable and efficient, and facilitating the rapid convergence of algorithm.
This residual function is stationary measure for the prob- lem (11). When (x. v) is the stationary point to the problem (11), it follows that V y) + aa (Vg(z,)) Ve, (x. v)) = O. Based on Theorem A.4 of (Liu et al., 2024), it is known that any limit point (I, 5) of sequence (x*, y²) is a solution to the problem (10).
4. Penalty Normalized Gradient Methods
Algorithm 2 provides an algorithmic framework for our S- PNGBiO method, which extends Algorithm to a stochastic setting. At the line 2 of Algorithm 2, we randomly draw three independent minibatch samples Sj { D, St = ) O, and S { O. Then at its line 3, update the variable @ as follows,
In this section, we propose an effective single-loop penalty normalized gradient (PNGBiO) method to solve the deter- ministic bilevel optimization problem (1). Mcanwhile, we present a stochastic PNGBiO (i.e., S-PNGBiO) method to solve the stochastic bilevel optimization problem (7).
The PNGBiO algorithm is provided in Algorithm 1. From the above section, our PNGBiO method solve the bilevel optimization problem (1) by directly solving the approxi- mated problem (10). Figure shows that the relationship of these problems. Here we use the penalty method to solve the approximated problem (10) by directly solving the problem (11).
B
0l-1 0¹ -
1 B
Σ
+ (0" --y)) s4)).
-1)
(15)
The gradients for updating the variables x and y are given,
In Algorithm 1, given the current {a², v², "0,, we begin with updating the variable 6, defined as
B, (iF(''
d
(16)
B₁
Ct
0++1 = 0² Th V V2g(2', 09) + 0¹
y¹ -"=""
i=!
(12)
B. Σ
+
where t/ > 0. Then we give two gradients:
1=1
B.
d=
1 Vif(='. Vig v²) Vig(o', 0(t1).
d
42F(x
1+
(17)
4
B
(13)
g++1 001-
V2f (1 ,14) V2g(2'+1 ..4 ge+1 gc+1-18 yd 4
1
+
V2G(1tt1 (cG()ttt.//:t)))) g/+())
d -
(14)
4

---

Generalized-Smooth Bilevel Optimization with Nonconvex Lower-Level
Algorithm 2 S-PNGBBO Algorithm
fuz ||y|l is convex on R2 RP.
Input: Iteration number T, initialization z², vo, 00, learning
Assumption 5.1 gives a lower bound of the upper-level ob- jective function, which ensures the feasibility of the prob- lem (1). Assumption 5.2 shows the generalized smoothness condition of the upper-level objective as in (Chen et al., 2023), which is milder than the generalized smoothness condition used in (Hao et al., 2024; Gong et al., 2024b), Moreover, we also give the generalized smoothness condi- tion of the lower-level objective in Assumption 5.3, which instead of the standard smoothness condition of lower-level objective used in (Hao et al., 2024; Gong al., 2024b). Assumption 5.4 shows that the lower-level objective func- tion is weakly convex as in (Liu et al., 2024). In fact, this nonconvex lower-level objective condition used in our paper is also milder than the strongly-convex lower-level objective condition used in (Liu et al., 2024).
rates TTe ozz, Pe. proximal parameter >> O, penalty parame- ter Ct > 0 and mini-batch size B, 2 1;
Output: x²', 8²
1: for t = 0, 1, ... T - 1 do
2: Randomly drawn three independent minibatch sam-
ples S = (4)) ~ S2 Sy = (G ~ O, S
[ ~ O:
3: Update gc+1 = 0f n n,
Σ Br V2G(x1, $3 +
1 10' y));
4: Compute d' B.
1 E
F g)
ViG(2', 7=G(2',0';3)) ViG(I', ; G)
5: Update x²t1 = x¹ at l
6: Compute dz = 1 Li= (2
V2 F (x 1+ . +14)+ +
Bi
V2G(x'+1 T2G: + g'tl
5.1. Deterministic Setting
7: Update y't = y' Br d
|
Theorem 5.5. Under Assumptions 5.1, 5.2, 5.3 and 5.4, given ? E (0, 28 ). Ct with e
8:
end for
= gtt + 1)1/4
O, and when P E (0.1) let 0 00 S 11 1 LLSa's of VVVV w
5. Convergence Analysis
A(Ko + K1 (+2kg2) 8(1+ manae )T ) 66 Vintar (++T)]I
In this section, we study the convergence properties of our PNGBiO and S-PNGBiO method under some mild assump- tions. All related proofs are provided in the following Ap- pendix A. We first give some standard assumptions on the lower-level objective f(x y) and the upper-level objective g(2,)) v)-
0 < 3 <
1[K K,+2Ks +88(1 menoy Mgz when 1
11, V2/(2" Il V V20(a' will
1 Vi w/
Vigl"aaa w wiIll
let 0 < 04 S A[Tg L,) 888(1 me- C V 1ig 1
V2 (x .0 2g
0
<
Br S
and
1(2+
C
For notational simplicity, let u = (z. u' = -x',1), E (0, 1) and un = uul + (1 u)u. Further let μ + (1- (2. y) and M = max, [0.1] || Vig(r, dn)ll, where
1+ 1+10
(Lar M) Tot
8t
E
2na2
where C = I + L. MP + S. The the sequence of {at, O generated by Algorithm I satisfies
1/7-Kg2
U1 ban Lov.1 (0 WV
(x) = arg min ,(x, 0) BER
|1e y/1
27
Assumption 5.1. The upper-level objective function f(u) is bounded below, i.e., f >RR f(u)= > -c.
Assumption 5.2. (Generalized Smoothness of UL Function) There exists L.f.,0. Liz,11 Lyy,0 and LIu.1 such that [[V - (w'lll < (Lmm0 + Lfn.1 m0 || (V,)()))))) - w'll and [/V - (2f(u')l & + max,e[[oa] (e)
min -0 ((a"",1 .y = 0 71/2
051ST
min R, ,1 = 0 (1( ostST g(0", v) - - (x .V4 )²) 0
T
w/I1. where p E [0, 1] is a constant.
T
Assumption 5.3. (Generalized Smoothness of LL Func- tion) There exists Lgz,0- Lgn,1, Lgg,0 and Lgy.1 > 0 such that V/V(( Vig(u')l I (Lga.0 + Lugz11 max |IVIg( "2g((")l| < (Lou.0 + Lig.11 max [/ (2g(v,))l)))ll 2//1. where p E [0, 1] is a constant.
Remark 5.6. From the above Theorem 5.5, the two terms minogesT ||0t 8, r²)l = (21l/)) and
minogest Ra(x*1 - o ( shows that our PNG-
w'll and I/V2g(u) -
BiO algorithm has a convergence rate O( (+++) to obtain the stationary solution of the problem (10). Adding the term g(xT. .y²" - v. (a","") = o ( ensures that the (Kg. Kgg) ) weakly convex on Rd x RRP, i.e., g(x, v) sequence (g(a", (g(a',y") y²)} approaches the sequence (u.(x", yy)),
Assumption 5.4. The lower-level objective function g(:-))
5

---

Scneralized-Smooll Bilevel Optimization with Nonconvex Lower-Level
so the above three terms show that our PNGBIO algorithm
ensures that the se- quence {g(x", [g(x",²")) 3/'} approaches the sequence (u,(a', y²)), so the above three terms show that our S-PNGBiO algorithm has convergence rate O
Elg(a" ,1²) ) ug (a==,"") (
T
has convergence rate O to obtain the stationary so-
T3
lution of the problem (1). Thus, our PNGBiO method can
obtain a gradient complexity of ((c=a) for finding an c- stationary solution of the problem (1).
to obtain the stationary solu-
tion of the problem (7). Thus, our S-PNGBiO method can obtain a gradient complexity of Ei= B, = T TB, = O(e (() for finding an e-stationary solution of the problem (7).
5.2. Stochastic Setting
Assumption 5.7. The stochastic gradient unbiased, i.e., BE<D[VF[ 5]] = vf(x, y). E [VG(z, y; c) =
6. Numerical Experiments
Vg(z, v). The variances of stochastic gradient estimators bounded:
In this section, we conduct some experiments on data hyper- cleaning, hyper-parament learning and meta learning to verify efficiency of our proposed methods. We evaluate the performance of our PNGBiO and S-PNGBiO algorithms in terms of loss and test accuracy by comparing it with sev- eral competitive baseline algorithms, including BOME (Liu et al., 2022), FASA (Kwon et al., 2023a), PBGD (Shen & Chen, 2023), MEHA (Liu et al., 2024) and SLIP (Gong et al., 2024b). Due to a high computational cost of com- puting Hessian and Jacobia matrices required in the SLIP algorithm, we omit it on conducting the meta learning task at theCIFAR1O dataset (Krizhevsky et al., 2009).
E Il - vz(z, M)P = 67. Eqrol VG(2, ()) Vo(z, w)l S S..
Assumption 5.7 is the classical assumption for stochastic algorithms (Hong et al., 2023; Kwon et al., 2023b). By As- sumption 5.7, we have the variance l|d" d² 1
69 2 B.
36,+0 Theorem 5.8. Under Assumptions 5.1, 5.2, 5.3, 5.4 and 5.7, given 7 (0, 2 Ct et + 1)1/4 with e
and I|dy -2y12= S B,
6.1. Data Hyper-Cleaning
and B, O(T and when p E 10.1) let 0 < at S 1 Vis((' +')l+ wi'll
In this experiment, we conduct the data hyper-cleaning task (Franceschi et al., 2017; Shen & Chen, 2023) on the on MNIST (Deng, 2012) and FashionMNIST (Xiao et al., 2017) datasets, respectively. Specifically, we solve the following bilevel optimization problem
4(Kg +2) " +6, 11 0
1 /2/(=' I1 V2g(2' I
31 a(K+ K, +2k +2+++)+++++0000 minoy 1age when o 1 let
11 1 yy + Vight IlIl
at S A(Lo La la +81+ 22 |1 1--1)1"
0 < 3 S
+ V2/(0' w0 IV w IIl
and
min
Σ iESval
Lval (ois ye; (2i, 6 01; (2))
4[L2+x+
Swall
02
1+, 1+40
21 Lgr. M) 12l
s.t. (*) arg min
Σ iEStr
diLer Vc: 0);
SSTT
me E
2n0z C
where Swal and S,, denote validation and training datasets, respectively, and I = (w. b) denotes the parameter of logis- tic regression.
1/7-802 21.1 max
where
C Lgz + 1 + S. Then the sequence of ("',y', 08) generated by Algorithm 2 satisfies
In the experiment, the dataset is partitioned into a training set, a validation set, and test set at ratio of 1:1:2. For our algorithm, we set T) = 0.01, 0₁ = (.+1)0.3 83
0.013
min E|| (, 3² |ll = 0 1 035T
m1/2),
(r+1)0.8 in MNIST dataset and 7/+ = 0.01, 0g = 0.013 0.011 9, = [++1)orr in FashionMNIST dataset. The learning rate settings of other algorithms are shown in the following Table and Table 3.
0.011
(++1)003
min Ex 1+ 1,c,,,,/+1) +]++ = 0( T1/6
ustgr
E[g(x" /²) -uy(u " 0 T(A))
1
From Figures 2 and 3, we can find that our PNGBIO algo- rithm achieves a higher accuracy and a lower loss value on the test set. However, during the experiment, the conver- gence speed of our algorithm is slower compared to that of the FAS This disparity can be attributed to the fact that the FSSA employs a momentum acceleration technique, which is absent in our algorithm.
Remark 5.9. From the above Theorem 5.8, the two terms minosest O 03 [""",,""")] ا''ل| = 0 (())) and minosesT (x E| = ( T
( shows that our S-
PNGBiO algorithm has a convergence rate O to obtain the stationary solution of the problem (10). Adding the term
TB
6

---

SnneralzeddSmmolle Bilevel Optimization with Noneonvex Lower-Level
DUP
POPE
PQU
PRGO
E0M2
D0F1
Figure 2. Experimental results of data hyper-cleaning on MNIST dataset.
1900
1943
PIZZO
ECMS
Figure Experimental results of data hyper-cleaning on MNSSi datasct.
6.2. Hyper- Learning
In this experiment, we conduct the hyper-parameter learning task (Franceschi et al., 2018) on MNIST (Deng. 2012) and FashionMNIST (Xiao al., 2017) datesets, respectively, Specifically, solve the following bilevel optimization problem
Table Data hyper-cleaning learning rates other algorithms on
MNIST datasct.
BOME
F'SA
PBGD
MEHA
SLIP
1.05
0.05
0.1
0.01
1.3
B,
1.05
0.05
0.1
0.03
0.5
min Cs (A)
Σ
Cla,, Wi vi:
0.01
0.01
0.01
0.01
S
iE
s.t. w" (A) arg min
Σ (C(2),)iiW) + Rw, VE
Ser
where w denotes parameters of model, and À denotes pa- rameters of regularization. Here Seat and Str are valida- tion and training data, L the cross-entropy loss, and RE, is regularizer. In the experiment, we use logis- tie regression. For our algorithm, we π/- 0.01, 1.3 a, (t+1)).75 Be
Table Data hyper-cleaning learning rates of other algorithms on FaShionMNIST dataset.
(++1)0.74 in MNIST dataset and 1.5
0.75
BOME
FSSA
PBGD
MEHA
SLIP
0.1
0,0006
T = 0.01, a, (.+1)0.45 8 = (E+1)0.44 in FashionM-
1.75
[1+1)1.5
[E+1)1
(+11)
[+1
3
0.01
0.001
0.1
0.001
0.001
NIST dataset. The learning rate settings of other algorithms are shown in the following Table 4.
7-T
[C+-11-
7/
0.01
0.01
0.01
0.01
Figures and also show that our PNGBiO algorithm achieves a higher accuracy and a lower loss value on the test set. Similarly, the convergence speed our algorithm

---

SnneralzeedSmmolle Bilevel Optimization with Nonconvex Lower-Level
DUP
PRLO
D011
Figure Experimental results hyper-parameter learning on MNIST dataset.
SUP PIDO
23
Teat Accthh
-23
PICEO
1000
26
320
Figure 5. Experimental results of hyper-parameter learning FashionMNIST dataset.
Table Hyper-paramene learning rates of other algorithms on
Table 5. Meta learning rates of other algorithms on CIFARIO
MNIISTFashhonMMNISTT dataset.
dataset.
BOME
F-SA
PBGD
MEHA
SLIP
BOME
F2SA
MEHA
PBGD
Ot
1.05
0.05
0.1
0.01
1.3
Ot
0.03
0.01
0.05
0.05
B,
1.05
0.05
0.1
0.03
0.5
Bi 0.03
0.02
0.01
0.01
7/
0.01
0.01
0.01
0.01
0.03
0.04
0.03
0.01
is slower compared to that of the F²SA.
where y (y1, (",, ,yK) In the experiment, fully- connected 3-layer used classifier for the LL, and neural network consisting of one convolutional layer and three residual layers used as the UL.
6.3. Meta Learning
In this experiment, we conduct the meta learning task (Franceschi et al., 2018), which can be represented by bilevel optimization problem. Specifically, given tasks and training sets [i 1, ....... K and validation sets (Dralli 1,.., K), we solve the following bilevel optimization,
We construct K = 3, where D and D. randomly sample disjoint categories from the CIFAR1O dataset (Krizhevsky et al., 2009), respectively. We Resnet-18 (He et al., 2016) task-shared model at the UL problem, and use 2-layer neural network as task-specific model at the LL problem. Clearly, both UL. and L.I. problems are non-convex. To ensure fairness, we adopt runtime as the metric. We run each method for 1800 seconds (CPU time) with minibatch size for both training and validation set. For our algorithm, we set ?) 0.05, a; = (++1)o.5 9 = (t=1)aus in CIFAR10 dataset. The learning rate setting of other algorithms are shown in the following Table
min
Σ
C(z,v(<z):5)
K
Deal
s.t. y² (x)
arg min Bf
1
Σ CED!
L(x, w: 5),
K
D
8

---

Saneralized-Smooll Bilevel Optimization with Nonconvex Lower-Level
ROUP
Figure 6. Experimental results of meta learning CIFAR1O dataset.
Figure 6 illustrates that under the same time, S-PNGBiO algorithm achieves faster convergence rate than these base- lines, and achieves higher accuracy and lower loss values on the test set. In other words, our algorithm S-PNGBiO consistently yields higher test accuracy and lower loss val- ues while maintaining performance stability throughout the evaluation, thereby showcasing a robust generalization ca- pability.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
References
Alcantara, J. H. and Takeda, A. Theoretical smoothing frameworks for general nonsmooth bilevel problems. arXiv preprint arXiv:2401.17852 2024.
7. Conclusion
In this paper, we studied the generalized smooth bilevel optimization with the nonconvex lower-level objective, and proposed an efficient penalty normalized gradient (i.e., PNG- BiO) method solve the deterministic bilevel problem (I). Moreover, proved that our PNGBiO method has fast ( to find stationary solution of the problem (1). Meanwhile, we proposed stochastic version of PNGBiO --PGBBO)) method, and proved that our S-PNGBiO method has fast convergence rate of O to obtain a stationary solution of the stochastic bilevel problem (7). In particular, our methods do not com- pute expensive Hessian/Jacobian matrices and also do not require any conditions on Hessian//acobian matrices, and can simultaneously deal with the generalized smooth upper- level and lower-level objectives in bilevel optimization.
Chen, Z., Zhou, Y., Liang, Y., and Lu, Z. Generalized- smooth nonconvex optimization is as efficient as smooth nonconvex optimization. In International Conference on Machine Learning, pp. 0396-5427. PMLR, 2023.
convergence rate of O T
Deng, L. The mnist database of handwritten digit images for machine learning research [best of the web]. IEEE signal processing magazine, 29(6):111-142, 2012.
Franceschi, L., Donini, M., Frasconi, P., and Pontil, M. Forward and reverse gradient- based hyperparameter opti- mization. In International Conference on Machine Learn- ing, pp. 1165-1173 PMLR, 2017.
Franceschi, I.,, Frasconi, P., Salzo, S., Grazzi, R., and Pontil, M. Bilevel programming for hyperparameter optimiza- tion and meta-learning. In International conference on machine learning, pp. 1568-1577. PMLR, 2018.
Acknowledgements
We thank the anonymous reviewers for their helpful sugges- tions. This paper was partially supported by NSFC under Grant No. 62376125. It was also partially supported by the Fundamental Research Funds for the Central Universities NO.N12023
Gao, S., Zhang, Y., Huang, F. and Huang, Bilevel- pruning: unified dynamic and static channel pruning for convolutional neural networks. In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pp. 16090-16100, 2024.
Ghadimi, and Wang, M. Approximation methods for bilevel programming. arXiv preprint 1xXv:2182.002246 2018.
9

---

Aaneralized-Smoole Bilevel Optimization with Nonconvex Lower-Level
Gong, X., Hao, J., and Liu, M. An accelerated algorithm for stochastic bilevel optimization under unbounded smooth- ness. arXiv preprint arXiv:2409.199 19212, 2024a.
Liu, R., Liu, X., Yuan, X., Zeng, S., and Zhang, J. A value- function-based interior-point method for non-convex bi- level optimization. In International conference ma- chine learning, pp. 3882-6892 PMLR, 2021.
Gong, X., Hao, J., and Liu, M. A nearly optimal single loop algorithm for stochastic bilevel optimization under unbounded smoothness. In Forty-firsi International Con- ference on Machine Learning, 2024b.
Liu, R., Liu, Z., Yao, W., Zeng, S., and Zhang. J. Moreau envelope for nonconvex bi-level optimization: A single- loop and hessian- solution strategy. arXiv preprint arXiv:240S 2rXiv:2405.09927, 09927, 2024.
Hao, J., Gong, X., and Liu, M. Bilevel optimization under unbounded smoothness: A new algorithm and conver- gence analysis. arXiv preprint arXiv:2401.09558 2024.
Outrata, J. V. On the numerical solution class of stack- elberg problems. Zeitschrifi für Operations Research, 34: 255-277, 1990.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In Proceedings of the IEEE conference on computer vision and pallern recognition, pp. 770-778, 2016.
Qian, J., Wu, Y., Zhuang, B., Wang, S., and Xiao, J. Under- standing gradient clipping in incremental gradient meth- ods. In International Conference on Artificial Intelligncee and Statistics, pp. 1504-1512, PMLR, 2021.
Hong, M. Wai, H.-T., Wang, Z., and Yang, Z. A two-
timescale stochastic algorithm framework for bilevel op- timization: Complexity analysis and application to actor- critic. SIAM Journal on Optimization, 33(1):147-180, 2023.
Shen, H. and Chen, T. On penalty-based bilevel gradient descent method. In International Conference on Machine Learning, pp. 30992-31015. PMLR, 2023.
Xian, W., Chen, Z., and Huang. H. Delving into the conver- gence of generalized smooth minimax optimization. In Forty-first International Conference on Machine Learn- ing. 2024.
Huang, On momentum-based gradient methods for bilevel optimization with nonconvex lower-level. arXiv preprint arXiv:2303.0392 03944,, 2023.
Huang, Optimal hessian/jacobian-free nonconvex-P bilevel optimization. In International Conference on Machine Learning, pp. 19598-19621. PMLR, 2024.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 170.0077777 2017.
Ji, K., Yang, J., and Liang, Y. Bilevel optimization: Con- vergence analysis and enhanced design. In International conference on machine learning, pp. 4882-4892. PMLR, 2021.
Zhang, B., Jin, J., Fang. C., and Wang, L. Improved anal- ysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 33: 15511 15511-15521, 2020.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009.
Zhang. J., He, T., Sra, S., and Jadbabaie, A. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint 190. 11881, 2019.
Kwon, J., Kwon, D., Wright, S., and Nowak, On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. arXiv preprint arXiv:2309.0/753 2023a.
Zhao, S.-Y., Xie, Y.P.,, and Li, W.J. On the convergence and improvement of stochastic normalized gradient descent. Science China Information Sciences, 64:1-13, 2021.
Kwon, J., Kwon, D., Wright, S., and Nowak, R. D. A fully first-order method for stochastic bilevel optimiza- tion. In International Conference on Machine Learning, pp. 18083-18111 133.. PMLR, 2023b.
Li, H., Qian, J., Tian, Y., Rakhlin, A., and Jadbabaie, A. Convex and non-convex optimization under generalized smoothness. Advances in Neural Information Processing Systems, 36, 2023.
Liu, B., Ye, M., Wright, S., Stone, P., and Liu. Q. Bome! bilevel optimization made easy: A simple first-order ap- proach. Advances in neural information processing sys- tems, 35:17245 17241-2-8--18 25:117288-1762. 2022.
10

---

Generalized-Smootle Bilevel Optimization with Nonconvex Lower-Level
A. Appendix
In this section, we provide the detailed convergence analysis of our algorithm. We first review some useful lemmas and give some new lemmas.
Lemma A.I. (Lemma A.7 of (Liu et al., 2024)) Let Y E (0, 2kgg ). (x', ,y) Rd R.. Then for any Kon 2 Kig Kug 2 7 and (x, v) on Ra x IR,, the following inequality holds:
(,((x, S -2n (Vu, (1' (x/, + K Ill, v) ,0)3,
(18)
where K = max N.
Lemma A.2. (Lemma 2 of (Chen et al., 2023)) f is generalized smooth if and only for any u, u' E R2 x I8,,
[Vif(u)) (ifld)-V((()))) (Lra, + Liz,1 S [Vif(tn)PPdiilll u|]:
(19)
and
[V2f(1') V2f(u)ll (Tefa, + L.pa1 L [Vass(n]]//d)))l" ull:
(20)
where un = ppu +(1 p)u, 1].
Lemma A.3. (Lemma 5 of (Chen el al., 2023)) For any x 2 20, C [0, 11, A >> 0 and 0 w S w', such that A 2 w/ w. the following inequality holds
Cx xdd +C5.
(21)
Proposition A.4. Under Assumptions 5.2 and 5.3, we have
(i) For p E [0, 1), then for any u, u' TR.d x R..
1 f(u) + g(u') < _ f(u) + g(u) + (Vi 1
1
1 2 + 11 o
(V=ffu) f(u) Vig(u), u) -
/
+
q
C7
+ +2K2llu' - -ll -| ||16 =ul2.
(22)
and
1 f((')) + g(u') +(u'))
1 u) - f(u) + +(()) (V2(= f(u) + ,())), u + 1 (Kss +
1
1 vef(w)l + +
a
+ 2Ks |1 u|| - u1|2
(23)
where Ko ( 10,0 + (22 = + 1), K1 == max L 2 21-0 30, K₂ (L
2 33(1 p) T-,, K3 ct ( (2 + 1), Ka = max LSy,1, Lag,1 2 3 and Ks
FI + ( _ 30 T+.
(ii) For p 1, then for any u, u' E Rdd x RR?.
- s(x') + s(u)) < f(u) + (()) + 1 v + Vig(u), - uu) + 2 (To + L [((1-vi((w) + (VVi(()))))
|| u 2 exp((1 ||u - u|))
(24)
and
f((") + gg(') < f(u + g(u) + ( 1 V2s(u)- + v uu) + [T2 L=llI- V2l(u)) + (2)2(())) I))
1
c
Ca
||'' - u1l2 exp((Tn) (Talll' - u|))
(25)
where To
1 I + I.gr, In = max(T [1,,11 Iegr,1), }. L = 2. I.fo.o + L.g.,o La == max(T1fy.1, I.

---

Generalized-Smood Bilevel Optimization with Nonconvex Lower-Level
Proof. According Assumptions 5.2 and 5.3,
(i) for p E [0, 1), we have
- [u'') + +g(u') [(u) - -(w)- -
1
- (Vi- + Vig(u), -u) u)
Ct
4
//¹
(Vi
1
[(pp) + Vig(un) V 1
f1)) - Vig(ul) (vl u)dp
0
C
4
1
1
1
|
(wu) + Vig(un) v (u) - -vi(())lll' - ulldu.
Ct
For n² E [o, 1], we have un = plul + (1 - pl) such that plu + (1- 1²) 1 prp + +(1- - 1 puy = upe-. Therefore,
we obtain
1 V v1l(up) 1 vis(
C2
Li0.0 Lsa.1 !
|
Vif(uw))lld 1lux ull
C
4
1 Li - (
11 c
(ilfwwwwlllpd I1'' ull-
(26)
Let H(p))= == 1 Ly + fzz So 11 Vifl(mewWl( 1 a e derivative formula
Lzz,p' + Lsaado 11 (if()))lddz, we have the
vi((w,)) - -v vl(()))l + L - f(Willl 0H(p') S L + Liz.1 1 +
1
$ 1
L + 11z, (1(')((()) + 1بm11 1 vi((w)l(
( (2-1120))))
s 33Lfa.1 (Glld- ul((() + - v +
(27)
3L
where the last inequality applies Jensen's inequality to the concave function h(x) = x.. Rearranging the above inequality yields that
31- P. -)]lll w|l
1
(1bmo) OH(H')
2 (1 - -)]lla wlll (11((10'- ull + +1| 11 vif(n)]++ +
a
C2
I
d [Iw' ull(H(()) + v.((w))l +
( (.
1-p
dpp
C2
Integrating the above inequality over /l E [0, yields that
(I (IV--|/H(R)) 1 v ct
( L 1-p
3 f
(1
or (2111 1-p
(1 - p)]l'' ullu+ + (ll'' - (0) +
1 -1-vi((()) +
Lian
( bz)
1-p
5 20 (3(1goa(1-- p)lled - u|lm - + c
-
1
L fz,1
12

---

Generalized-Smooth Bilevel Optimization with Nonconvex Lower-Level
where the last inequality follows from (0) and Jensen's inequality to the concave function h(x)) xt-PP obtain
Thus,
||u' uu'-u/oo (2(((()
$2 (1 ullu) i +
Vis(ui]] +
11
Vif(u)]l
a
1/22
(ceL)a,)²
such that
vis(w))l
-
S vis(mi)I + [.
-
Ct
4t
C2
Ct
$
vis(u)] =
$1 1
1| -ul
Liz0
221
- + | vi)(")] +
(c.
Then we have
1
Vif(u')
Vif(u)l
4
1
+ max 1
|-
(idww))lp)l''' w|l
4
4
(1 - p)llul - u|))= + 11 1 vil(w)]l + Liz000 )) |lu6 ull
Liap0 + 21, -
a
(aTT
L + 2 3'(L ( -01ppp)llll - ull) +11 - +1 v + Liz.0
(cel12,1)) 1|2 - -ull
Liwp(1 +2 + Laz,1 2f 301 1 Vif(w)]le + + 2f 38 - p) - r>
-ull 1| ull.
a
Similarly, we have
VVVg((') Vig(u)]
in (Lo 2 + Lyn,1 (VVVilll + L 2 3 - -) 11l - -ul - 1/ u//.
Therefore, we can obtain
IV 1 f(un) + Vig(u,) - -V 4
- ((o))--v Vig(u)lllu' ul|d
G
$ L-¹ 1lu ulll -T.,0,0(22 + 1) + Tifa,1 2 30
vif(u)ll + 2 30 - p) - || u|| =
Ct
4
+ L2x,0 +1)
(2) + L gz,1 21-0 - 3 V 19( |1
+
,2,1
2 2
30(1 p) 1 1 Ilu' u|l 1 )|u =u/du
= (' AllW - -ulp(= - --=
+
+ L 2 301
1
+ L fa,1 2 .8 p) خ || - ul| ==
Ct
+ L2 c +1)+ Lg 2 2 3 Vig(u)]| l| + L أ
2 30(1 p) -
||u'
ا/ل - )du
- 22ll'' u|l2
1
(- + L Lyx, o) f 1) + max f2
1 2 f 30(11
1
vIf(wi)l R + [[1g())11)+
C2
(Lizd + - 2.= 31 - ,/ ul| - / 1 d
S $ Ill - u1l2
Ko + Ki
-V][w\I + [[V1g())119) + 2K2llul - u|| -
13

---

Seneralized-mmooll Bilevel Optimization with Nonconvex Lower-Level
where Ko == ( + Lgm, 1), K1 max ann ....13222 3-2 30 and K2 (1,z Lggni) 2 (1 p) T-..
Similarly, (23) can be proved.
iii For p = 1, we prove (24) as follows.
1 f(u)) g(() - f(u) - g(u) (() + Vig(u), u)
f(u)
1 //'0 (V, [up) Vig(u,) )(=) Vig(u))T(w' uddp
2 V
WV-f(uu f(up) + Vig(un) V 1- f(()) Vig(u)llle' - ulldu. Ct
4
When p by (27), have
(H(H') S - LImo0 + Ls0,Illu' - w|| ((l)((() + Lsa,1l - v
where H(''):= == Lsz,pp + LI22 Vi 1 (un)lldj. It follows that
L - (1()
Lsgallul -ull- S
L + L - (l( + Lf211 V f(u)ll
In( - I.f200 + - ((() + L (()0))
du
and integrating the inequality over μf E [0, pl, we have
In( 1 LFz,0 + Lfz,illu' H(() L V1 Ce at
1 f(w)l)) s In( a
Lsa,0 LizallV1 1 f(u)ll) + Lszallu' -ull
a
which implies that
Lf (H) < (-Lyao L 1 (x)))))x((LLxlll) u|l)
1
1
- Lyn,1 V
fw)]l
Ct
a
Then, we have
I V--W(
1 [v f(w]]
| <
- f(u]]]
C
[ a
1
f(w)ll
( (-L + L V1 a
exp((ee ull)
Lf200
L
Li000 + (IVI-f(u)] exp(L - ull)
1
Liz.0
a
cL
and
(Vif(u)- vif(u)ll < ( Ljz00 - exp(Lra,al1e' - ull) ||' u/l-
Similarly, we have
- (Lono + Lgz - exp(Lgr,a ull) u/|-
14

---

Generalized-Smooll Bilevel Optimization with Nonconvex Lower-Level
Therefore, we can obtain
1V f(pp) + Vig(u,) V1 62
f(u) Vig(u)lllu' - u/
4
f(w))) exp(Lsaa11l ull) + Lg + LgeallVVs((uI]] % 1luy ( + 1 -
o
exp(Lgg,allk 11al -lfl Illl -ul'-u
/ ullul - ull ((= 11 Lig,,lIVi - - exp(bsa,lll' - u|l) + [igno + Lega, Ver,1IIVi.h (Vii///l(())))
exp(Leg,111l' uull) u|l)) du
[(wii] 2 I ull? L bysaallV V 1
exp(Lsa.1lu'' - u|l) + [ogno + 1gz,11VVig(0
Ct
exp(Lga,111 1ll' -ull) ull))
221 12ll'' ull2 + [1(IVV Ci
f(w)l exp( (Voo ||l ull),
where Lu = 1 Lamu + Lg,,u, L == max fz.1, Lg
Similarly, (25) can be proved.
Lemma A.5. Let y E (0, moz ) Then, there exists Le > 0 such that for any (x, u). (x', E IRd x R2, the following
inequality holds:
u) (2', 2/11 = Loll(o, u) - 1//)
(28)
where Lo = 1- v1= Foo)
max { - Lg [0.11 V2 (I, y) II } I := μi + (1 - -m)x'.
Proof. Since 07 (I, 2) is the optimal solution mingerr g(x, 0) + + 010 - 1/1²2 we have for any (x, v), (x',3/) E IRd I.P.
2
1
V2g(2, (1, (0, (.. y) y) 0,
V2g(2' 02 v)) (0,(''.v s/) - v/) = 0.
Then we can obtain
(0, v) - 07 (x',1/))
(1107(20,)) s( (Vng(x, 0z + (0) 1) -0000000//)000000000))00 V 1 (0, 5²) -y'))
< (z, - o V2g(2 (z. v)) + 107 8) y))
w/)) + (z' ,/) b)ll
+ (10(('',') * (2zg( (2', s)) + (0) v/) v) 07 0/) 0 0, ))))
1 (0 (2x,))))) ./) 9'
(29)
7
Due to 7 E (0, Kgz L), the function g(z, 0) + 11 y| is ( Nog)) )stronnyy convex respect to 0 RP, it follows that
1 7 (x, - y) - V29(2, 07 (xl. - (0,(00))))) - y), (), v) - 0,(2,, ./))
(V29(1, (I,, v))
7
2 1 Kgg kg)))107(77 - -7, s/)l2.
15

---

Generalized-Smootl! Bilevel Optimization with Nonconvex Lower-Level
1/2-Kin mi
Given 0 < < (gy ot byg, (0..c Nagl:102((.2))111333 we have
1 (x) s( e(V25) (2 (x, v)) + (0,((1.)) u)) - (z'2 3/ + V2 + 7 (0, - u))1
1
(gga) 521 1
2s(
Iug.a Lug.1 max pE(O,1)
|V 07 (2) 110
v) ( (7 s/)1
7
1 (oo)) (107(0))) 02
(30)
7
and
(17 3/) - s( s(V2g(2, (x', ,3)) + - (0 v/) - v)) - (1' v') + sVVg((' (3(2 + (0)(0'' 3/ii
S 8||o - x' dlll + Lgg.1
max 1
V 22 07 (o' M/11 =11 y 1/11,
(31)
where Fu == jæz + (1 - w)x', 07 y) +1 (2) v'). By combining the above incqualities (29), (30)
and (31), we have
(1, y) - (z
- - k000 (,,4'' w')ll + s((Lgy.0 + Lay.1 mE(0,1)
(3 x'1l - 2/1)).
Finally we can obtain
(1, v) (z',0'10)
(Lon + Lgu.1 max [e(0.1]
V2g(z - z'll -ly - vl)
/1 $(1 1kga))
(ar v) vdl.
where Lg 1- -kg)) max (Lgg + Lgg,1 pajoe [[ (1, u)) 2 It implies that the solution 05 is generally smooth with (x.
Lemma A.6. Under Assumptions 5.2 and 5.3, let Ve (x,1) (x, + (5x,)) vy v) with c+11 2 a for all I O, we have
(242) V, (x'. < Lu, Ll, 11att1 (2))) (x',
(32)
VV2
Ve (x², .1a'll s LN 11 (/((:ttlyy/)) (1 - (x",v²))l (x++1 1+ (xtt1,y/+1) (//t)
(33)
where Ly, Lgz,1 maxpe]o.1] / 07 Nn)) ( (1)))lP(1++ Lo)) and Lv, 1 L + Lig.1 max
1 Lfz,0 + Lfx,1 maxpejo.11 1 1 V mn)ll Lgg,00 + Lig max,e
| V19(I Uy) + (L +
<
1 (2f vn)ll + Lig +
Tegg,1 max
2 wn 11 + LoLo
16

---

Generalized-Smooth Bilevel Optimization with Nonconvex Lower-Level
Proof. When p E [0, 1]. we have
V V (x 11 - V v. (x',
Vif(xtt1, ./th)) 1 vif(=', y²) Vig(x(t1, (lt,tt,,//t) ,/tt) Vig(a'. .0) Vig(x (,((ttt s((t1))
=1 4
C
Vig(=', (,('''"'))
11 Vif(x't1, ,,, Vif(='. l + IVig( (odl=="1,,t)) , - Vig(z', 32')l + Vig(x (,((0 (((ttt1,(tt))) -
Vig(e' 07,
I.fa,0 + T,fa,1 max
1 V (Tp + Lugu,o + Izz,11 pe(0.1]
max
V ww)ll) (iloft,,(tt) - (xt, y²)
C1
+ ( + L max
V u, (Z yn)) (1 + Lo)i e , g (z', v')l
ME(U.1]
1
I.fa,,0 + Iag, max pE(O.1]
V ViS( + Ligr.0 + T.ga,1 max
|| | Vig(En Un) + (Ierr.
Ct
C2
ME(o.11
+ Lgz,11 max [E[O.1]
Vig(In (F V M1 + Lo)) [|(alt), (((att,,((t) ,')''
(34)
where the first inequality follows from triangle inequality and the second inequality follows from Assumptions 5.2, 5.3 and Lemma A.S. Similarly, we have
V 2 v c. ,21 V2Va, (x',8"))
(arltt,9et1) Vef(x', v²) + V2g(x*t1,y'* - V2g(2', v²) + 0 (3 ,1(t1) - sp+1 07 y²
(2f(x 1+] ,,,t,, (11)
Ct
a
?
?
1 Lin + Lini1
max | V2 (2s un) |1( + Lgy.0 + Lag.1 max we(0.1)
[[ || (iact,,,tt1 , - (xt 220)
we|0.1]
1 + Lo |((ett, , (x', n')"
( Ls3.0 + Lig.1 max
| V2f(I Hwll + Lyy.0 + Lov.1 max
Veg((z 1P + (E(0.1)
1 Lo
||( (tt) - (x /1)
(35)
where the first inequality follows from triangle inequality and the second inequality follows from Assumptions 5.2, 5.3 and Lemma A.S.
A.1. Deterministic Setting
1/7- Kgg and te E (0, (1/7+49u. Lov. 10(.)) (este ) the sequence {x v/, 000
Lemma A.7. Given 7 E (0, 2
generated by Algorithm satisfies
10r+1 (x", .10) s 0011 - (3(4", v')l,,
(36)
where = 11-1p(10 11//111// - Kgg))
Proof. Let (1") be the optimal solution of minger+ g(x',0) .) + 2, 110 y'1l. we have
07 1²' = (0, w²) - ne (22g(, (x .,)))))) + (0,(2' ,/) - -)))).
17

---

Snneralized-mmolle Bilevel Optimization with Nonconvex Lower-Level By using the update rule for 0 in the Algorithm
can obtain
1 (z',, y1)
s $110= (2 0²) + 1 (0 10'--19) -y 00 (V v9)) (07(=' 59 - rل)
9
$ V 1---nu nc(l/ r2g2)1 07 ,/)ll.
Lemma A.8. Under Assumptions 5.1, 5.2 and 5.3, suppose y E (0, 1 the sequence of {x', y², ) generated by
28
Algorithm I. We define function Ve, (x. = 2. f(x, v) + g(x, v) - ey (x, v) with c++1 2 > 0 all t 2 0, which satisfies
(i) when p E [0, 1),
Va, (x ,
s Vor (x ()) + ( 04
(Lor. + 110)
2/3
) 11041 -0 (21)
|
72 |d
04
1
Vif(z', ,3") + Vig(=',
+ a V1g(=', V ,0t + dg
3
Ko Ko+ K1 + +K2 +
4,3
4
C
2
>21(dt)]
Bg
1
V2f(x'+1 ,,²) V2g(2 .00)
+
BC 2
(K3 + + K₁ +KKs),
4
a
(ii) when p =1 1,
Vea (x ,1/11
( at (Iygr, + T MP + 3?11dh
2,3,
S Vea (x' (z)) +
|0t 10(t1-0((a', y/)
|d
1
3
Vig(( g(-1)11 of Lo + k L, +
43,
v (at, 1..,./ y²) + V x/ll| + ar
Ct
72||dg]
Be
(1 11 | ,,,)lll)))+++ + V2g(z +1 x'll)
+
(L2 + 1 La).
4
2
Proof. By the definition of function V.,, (z. y). we have
ii when E [0, 1).
De, (x ,8") < f(x", v²) + +g( - (, w2') ,0)+ ( Vif(=',8') + "ig("',8)) )) st)
1
a
1
Ko K (11 Vif(oo 1''l + 1V 10) + 2K₂ || x² 20||=50) || - 20112
+
2
Ct
1 <V (x')8") + (V, V. (x" 3/ ) x 111 - x²) Ko + K1(ll Vif(=', M' | ,2))
Ct
+ +2Kg || 21 - + K |1o| - 1012
= (xt, + (V, Ve, (2x 5²/ - d2 xt - x²) + (d 11 - x²
+ 1 Ko + K1ll a
v1f(2', w/) + Vig(a' 3² |P) 2K₂ || 2 20||=00 ||alt1 x'11?
(37)
18

---

Generalized-Smootl) Bilevel Optimization with Nonconvex Lower-Level
where the first inequality holds by Proposition A.4, and the second inequality holds by the Lemma A. Considering the update rule for the variable x in Algorithm 1, it follows that
(d (d,, xt1 x²)) = --aeldd,
(38)
And we have
(ViV (a', .3" - d2zg x - =²))
= (iig(e' ,0+1) - Vig(a', (x', ,y)) - z²)
V Vig(z', ,0++1- Vig(t' 03 y²) 1)) z'1l
L9p00 + Lgn,1
V 1g(2 n0 + (1 w) (at y 111) 117(0' - 0 - I|| -
max 10
|ctill ||0 4xxt
10113
04 |d
(Lzz + Lg
V Vig(e' pot+ + +11 - p)0 1114 - g 1|
max [
(39)
where the last inequality follows from Young's 's inequality.
For the sake of simplicity in presentation, let M = max | Vig('', p +11-1++11111)0)00100000) (1)00 ,1))) by combining (38)
with (39), we have
V c. (x 1+ )
Ve, (4', .0'' + ai
(Lou. + Mg |10 (0AA))))10011(((((
-83(=", (0(2"..' r/)11
||
|, 1²11
|
| x²" 12
|db2
4ag
at
1
Ko + Ki (11 (1 D' + VVVi(' e')ll") + 2Kg || - -2'11 + *xx | - x²12
+ 2
4t
I Ve, (a", (0)) + |d%1|
at
(Iegr. + Me) ||00-1 )11 4 aalld"
+ at
3(Ko + +x)ar+ + +(l1 1 Vif(a', 21) + 1|V ()) + 6Kja; + 6K2ag
6
Ce
< Vo, (xx" (y') + at
|12 (Lopo0 + Ligz,1 Mr) |100 - 07 r²)
(1)
1 v [(x w/)l + VIVigla' Ii)l
+ 3al
Vig 0(+1)| + of (Ko + K K1 + 2K2).
(40)
where the second inequality follows from the above Lemma A.3.
Similarly, we have
V (x 11 (,(t,,tt1 1)
1 1 K3 Kall--2/(e' V2l ,2')) + 12 2+1 "/tt,,","111 ())))
S V, (z++1, .1¹) + (V2 (x'+1,""),>"" ,1",,++11+)_) -5¹)
2
Ct
+ +2Kslly**1 1+| - y'1| +x 1112t1- - 221
< Va (1 y/) :,4))))++)))))))) +
72 ?21|c;]1 || (110412 07(x') )² + || 1a,t1=z011 20))
2,,
3/ddg] ||
1 y 11 1
K₃
45
2
+ -Kill [2f +1 w²' IP + 129(2 |1)) + 2K's
2K'lly 11g
-/01 +
|1 - y912
< V (x 11 .v²) + 72
28
(11041 - -0341 v²)l ||2 + || -x
Be
(1=
V2f(act1, ,
a
4
B
+ +1 -/)]||
+
(K3 + k + K₂ + 2Ks).
(41)
2
19

---

Ceneralized-Smmoole Bilevel Optimization with Nonconvex Lower-Level By combining the above inequalities (41) with (40), can obtain
Ve (x ,/tt) (xtt),
Vor (x', ,²)
(
ag (Lgn.0 Lg +
32110%/]1 100 (
20
||d%
a (1l
1
Vif(x', (z')'l)')) Vig(<',)'(l)> + 0rl
3
VillVig(a', ((+ at
Ko + K K1 + 2K2 +
4,
4 Ct
7.2 -211dt,))
3e (1l V2f(x't1 (+ n + V29(x ,y))l
1
-)')l) + 3
(Ks + - + K4 + 2K;).
C
iii When p similarly, we have
V a.
(1 "y 1 Dee (x",
(Lzz0 + Lin
23,
110
(z w²)11
Vi (
a/2
+ +|[Vig( w1
d
3?11chg]1
4
12
3
V Vig(=', ,0t,)
a?
Lo
+
72|18/]1 )
43
3:
(1
1
12f(x
+1
+ |
++ 3
4
2
4
Ct
(L2 + k L3).
(42)
2
The proof have completed.
Lemma A.9. Under Assumptions 5.2 and 5.3, suppose 7
(0, 2 ). ct+1 2
Ct O and nh satisfies m >
14 1+4(kgn, M 3333 t (ag 1214,
we have
26 (o 1 45)
Q--1 - -2
at (Il Vil(x'. 9 ("gg(",")")) 2 20)) + 11V ,'1l teiigg 10 (,, y/ y/)) $
8 C2
(43)
where l4+1 1 cots (xt+1, (ottly(t1) + (Loz,0 Lgv, MP + (3) 03 ||1
Proof. We first define useful Lyapunov function,
22 Ve, (x*. w²) + (T.ga,0 + T.ge, MP + 7 3 07 ((at,y/)) 11)
2
(at
(44)
where V,,
(x, v) 1 fr. y) + g(x, v) ux(2, v) and c+1 2 4 > for all f
20

---

Generalized-Smooll Bilevel Optimization with Nonconvex Lower-Level
By the above definition of Ω2 when p E (0,1), we have
R4+1 - Sz
-v -o (xlt), 1/+ Ve, (2'. + (Lex + 10 + ( 211100t1 (z(lt1), ((1
2
- -IIgz,00 + IigH,1 1MP + p 1100 07(a", 11)l
SVe, (x - (xlt),y/tt)
Wer (2', (z',z") + (Lor.0 + 1M +
72 - )1(et11 07(x0t], ,(1))
2
2
-I'gr,0 + Tign, MP + 7> 110 ((("",)))]
(L9z0 + 1 + 2
110 y²)
[1
1211d%/]|
01 1 V1 Vif(z', (('"x'') 1/)ll + 1i9''' y')ll + 3
of 2
43,
aall V Vig(z', +
Ko + + K1 + +Kg +
4
Ct
3e
1
32
(1l V2f(x' v/ || - VV2g(2 +1 ,l'l)) + (K's + 12 Ks + 2Kg)
a
2
+ (Lzz,0 + 1 + マ) | 07 (x , || (Lez,0 + M + +)]10= 110 - -07(0', (0(("..11 w/)'l²
2
S ai Vi ,/)Il + V V1g('* w²)) ||| 3 11g ,0+1)) -20g Ko+ K1 + 2K₂ + 72 3lddj] ))
4,8r
Ct
& 1 +11 n²) || + V2 ++ w')ll 233 + + K4 + +Kss)
at
(Lzz,0 + 1 + 72) |1 - , + |11 (Lyz,0 + Mp 2 110 -67(0' ""(''''''] v/)
2
2
Cr [dd
(Loz.D-
Me
23:
|10 (, ,y')
(45)
>?lldy
where the second inequality follows from Lemma A.7 and the last inequality by rearrangement. Next, we demonstrate that
110 03 y +1)2 - -100' -07 w0)²
ag 0,, 100+1-00 "'a',
|
1 + ut
a1
10s+1 (7,40' y1 110- 0, 2// 111 +
(+ 1
110 (10 ,, 1 0, >²)
||
11
+ Vt
Cq ||d%|||
02110'
0; 22)11 110º 10,00000, 12) (1
1
T2ll( ,2)) )')'))) (46)
1/
where the first inequality follows from Young's inequality with parameter in and the last inequality follows from Lemma A.7.
Given U2 = gi we have
|10
1, -100- -07(0', "2(a".''')1 ./)) + at
11 0,(2',
|d%
5-
( 1 kg
a1 110 (a s/1 (1 + 7e
1 L3ll ,g ,g/h1) lott./")12
(47)
|
21

---

SCneralized-Smoothh Bilevel Optimization with Nonconvex Lower-Level
Similarly, we have
2
110 - 0,(0011, ,3 111
- -110- - -07(2', , 2/) +
||ay] 110 - 03 .1)
23c
0f 02110' (2 /0)11 110 - f9 (1) v²)1 + (1+ 1
v1 ) L f01l( (x+ .gttt - -a'",'))²"
+ 112 +
||d;,
2
(2 w// + (1+
1 [ Lall( ( 111.
<- 17f Kgg
110
(48)
|dg]
Thtigg
Putting the above inequalities (45), (47) into (48), we have
a2+1 - S2t
s 0t (1 11 Vif(=', IVVig(aa 1')l VIg(=' , - 20r Ko + + K₁ + 2K2 +
48g
7P11dy 1
4 Ct
1 L3 Lg0,0 MM ) B1 (1 - ,2)1l + V2g(2 ,8"")
-4rr(1 +
1)t
( + Ig ) 1)-((11z)) (1ero + L9 2 mir
23,(KK + x K4 + +2Ks)
4B, (1+
netigg
-Togao + 1 MP)
04
Be
110' ,
|
Vif(2' ./ ) +1| V1g (0)'"/(''/)))
Given
a1
12 g0. Lgs M² + +6
V Viglo'
1 22f II| 22 12"
0
Be
<
4[K Ka +kkk) +81 "1
n Lo M +,)
and
1+ 1+l(hgn 1 MM4 3))
(k h Md)
or
we can obtain
2n (4 Lgr, 10 +2)
4411 S4 S4
S at 1 (af(f",''11 Vil( (1 1 Vef(a'.' + 1/22g(> (2))))
87 87 ,,,,))11 1746gg 110tt1
8 4
a
(49)
When = 1, according to Lemma A.2, we have
Or
(Igr,0 + M) +
721|dg1| ) |10
23,
Vis((' 9/) -
an
+ V (
|
4
4
+ 04
3
Vig(z', (0t+))
ot
Lo 1 In +
7:2 7211dt )
43,
Br
(
1
V2l(x
1-1 |
+ 12 1+1
4
2
4
C2
32
(L2 + K + La) + (Lgz + Lgn,1 M + ( 100 - -07(0't1 1|2
2
(L + Lgn ) ]|0e -8, v011
+
2
0: (1
1
1
<
V 1( , w/
+ VVVigl'' 1l - 3| V 11( 0(+1)|l -20 + In) 4an(1
)L T L.gn,
at
2,
3
1 Vef(c
2/5 + 11 3118-26((2 L3 + k)) 43, + 77
1 LZ
+ Lg MM
4
ct
+ Mg +
2)
(Lgr. + 1 M +
22 mm? (Lgg.0 + Lg M)
01.
3r
110 - (, .y²) y11
||dt
where the last inequality follows from Young's 's inequality with parameter Melig and rearrangement.
22

---

Generalized-Smoole Bilevel Optimization with Nonconvex Lower-Level
=1 Vi of V I')l
Given
3
1t 1+ 1 M )
( MP)
o4
V 1/ -l''l
Tus.
7 25
and 17
((Latxt
- "
14 gall at.0 be, Mo+ 33)
28 ( o 1
can also obtain
44+1 - S4
5 (11
at 1
V s( s
Viig(a (0)) - -1 w/)ll [[V2g(>', (2g((",)'))l) - 1/2 110 0z (3 (,",,""')) y1/
8 4
c
(50)
Thus the function 22 is descent.
Based on the Lyapunov function, the non-asymptotic convergence rate can be shown
Theorem
A.10.
(Restatement of Theorem 5.5)
Under Assumptions 5.1, 5.2, 5.3 and 5.4, given
7 E (0, 28
Ct = c(l + 1)1/4 with g
> 0, and when E
(0,1) let
< at S
Vif(='s V
1. (oa((a","""++|Vaddd" ,y')l
4 4(Ko + K2 +2 +811+ m002
0
<
B: S
K(Kat +8(1+ m100g )4z0* when = 1
I Vid(as --)l- (VVin(>""'>)))) wIll
1
V w/ll and
let 0
3
(bota+ha)+811 monaz 11006 Lalaatbr+1j
4(12 11) + m 1100
1ty
1440
D T
1/7-Ma2
E
26 C
(1/y+ oo Log.1 paxpe().s) V2 (2 ((.0)))))))))
where
C = Ligz,0 + Liga,1 MP= + 2. The the sequence of (x), ,,,,", OO generated by Algorithm I satisfies
min 100 - 00 w²)l = 0 TTTZ)
OS1ST
1
min 051S
Re(x+11 (1(h) = 0 T )
g(0² , - ,1y") 0 1
Proof. By using the above Lemma A.9, telescoping the above inequality (43) over the range 0, , 1, given
7 minosesT-1 Tet, we have
1 V
(1 1 Vel w + Veg(o', v')ll) + 1)5
(
w''l
00' 11
0, ,00,,"')) w²)
4
C
< 20 Ωr
1
< 20
r
< Ωo:
(51)
CT
where the last second inequality holds by Assumption 5.1. We obtain
Σ
100
03 y² < oo,
t=0
and then
8, - = 0C (1122))) ||0 0s151
min
23

---

Generalized-Smooll Bilevel Optimization with Nonconvex Lower-Level
According to the update rule of variables (xr 3) in Algorithm 1, we have
d
Ct
d
at
x ++1 - xx²== 0,
(52)
dy
Ct
Ct
(ytt1 - x²) = O.
(53)
dgyl
Be
Let
c/) V5(x ,((1) + cs (Vg(z'++ ,1th) - en (2tttt ,y(t1))
with
celd (zet1 - x²),
e = 4 V, Ve, ( - a.d
(54)
calld; (y/t1 y/)
= a .1 add
(55)
Br
Considering the term ||, we have
cilddell ||x x²1l
|| Sc V U (1tt1, // - v U., (+', w/''l Vl -cd"
0t
_ L 1,,,1(x0tt ++1 (2) -1= (+'. ,0','')l + c2 V v (xt ,2') - d21 + cald%'ll |:! - x01l
=,l,, , (2 - (x' ,3'''l + celld%]
| - x'1 + Vig(L' 00) Vig(a' ,0 ,y')))
at
(1) x Lv, 10,, -1 (x', v c+|
calldhgl
||
- + (Lga,0 + Mo) - ( y')lls
x01l
where the above inequality (i) holds by the Lemma A.6, and the above inequality (ii) is due to Assumption 5.3. Thus, we can obtain
x²ll + ce (Lggo + Lga.1 M0) - -0 07 w'')l - e:ld='11 ||a2t1
|e S ceLv, |1 +1+ ,2),'')l I|
ae
Similarity, based on Lemma A.6, we can obtain
cell celldtll
|e s a L. L.,,,l(z'' "atp//t,tt// + - (x", ,0)''>1= +
1
1/1 + Ct (1100 - -07(x", s/)ll + Lo L011 x²1)),
3e
where Le, = 2/2 (L + Lifu.1 ma 2 ( + Logg. + Lg, maxpee(.11 V2g( mu)llp + Lhe
Since Re(I,y) v) dist(0, Vf (Vg((z) v) V2y v))), we have
Re(x+t1, (())) cl g (()00)11- (<: |dd''l] + cgtio |1att2 - x²ll +
celldtyl
1 8/1l
a4
Br
ca(Lg Lin, M 1 07, ,2/)11
Given Cn < min [IVislo' w/) Vin(a" of (a) )/)+ Vagla' w'Il
we have
2Mag max [1 11111,11)
of R2 ( 22
< CR
@+ (1 1
Va w')ll (V .010) + (((1
V2f(x', (=f(""''')1 1/V2g(2 (2)))" + gr
07, "","',"'')' y/)112
24

---

Generalized-Smooth Bilevel Optimization with Nonconvex Lower-Level
By using the above inequality (51), then we have
Ra (a yy 2222 < co.
(56)
Since a = c((t + 1) with c O, we have
T-1
1/2
(
(T 2)
Σ
z
(57)
t++
1/2c²
Based on the above inequalities (56) and (57), we can obtain
min (x (1t)+ --)) 051ST
=0
1
T1/4
Since (x', y" Josest is a sequence generated from Algorithm 1, we can find m maxosesT (o. 5 (()))y') + g(x', ,'¹) - uyy),, y²), and (s", v²) 2 I for any L. Then we have
ce(o(x', .v)) - uy(a ,'') sm f", Vt > 0.
Based on e = c(( + 1)2/4, we can obtain
1 g(x -,(xx, 0 (T )
A.2. Stochastic Setting
Lemma A.11. Given E (0, wn
1/2-No2 1. and ne E (0, (1/r hww.ot Luv.1 max (a.)). ). the sequence {at , 8'7
generated by Algorithm satisfies
E| - (('","'))[(AA)) S 0f - (7'""', y1 + n2:60
(58)
B.
where 1 111// - kg2)) and (2, v) = arg ming
C) + 전े li - 0113).
Proof. By the update rule of 0 in Algorithm 2 in line 3, we have
10c+1 (7(a"t""))
B.
(0' v3)) (74", v"yl
B Σ 0z: + γ
m
Be
0¹ Ne( V20("" 000 + 1 (0- - (,(xt,0) - no
1
V2G(xt, 00:2)) 1 -1))
B,
7
Veg(e', 00) + 7 100 - x/4) ||
B
=10- nh ( V V2g(x*,00 0²) + マ 10' - - - 07 1/) + T/1
2
1
G2 Veg(a' ,00
B 1=1
-n '0' T (V2g(x' 0²) + 7
(0' - 07 ("","""""); )')
V2G(2' 0,:'''0':;11 V2g(a' (9).
25

---

Generalized-Smooth Bilevel Optimization with Nonconvex Lower-Level
Then,
(7, E B1 - (=((="00)11 [[
1 B,
V G2 02 0 - Vag(a', 03/ F5)
=110' - ne (22((=' 0²) + (0' - 5²)) - -07)))"'''' 22)1 + n E
B
n2
5|10 n7 V2g(2' (x 0¹) + (0) w/)) (7 , g/)) +
Bg
5(1 -11-1 -) (x',, 1²
B₁
where the first equality and first inequality follows from Assumption 5.7 and the last inequality follows from Lemma A.7.
Lemma A.12. Under Assumptions 5.1, 5.2, 5.3,and 5.7, suppose E (0, 20 the sequence of ve",y', generated by
Algorithm 2. We define function De, (Ir, v) = F () + G(z, Mr () u. (x, v)1 with c++1 2 c2 > for all t 2 0, 1 and 6 co 5 + 20 which satisfies
(i) when E (0.1),
E T (x 11 ,1 (++1)FF)
{ at (Igr.0 + MP) + 28,
pe (x", ,1") + E
|10 0,(x",,0'1'" Fi
[|dd;]
3211d;
0t
V ff(' n²)ll + VVig('' w')l 2 V Vig(z' ,0,,, + of ( Ko + + K1 + 2K2 +2+
3
4,3,
4 Ct
2
>211d%
1 Be (1)
W2f 11 ال + V2g( +1 ,lll)) + B2
8
(K3 + x + K1 + 2Ks +2) +
(as + 3c).
4
2
2B,
(ii) when p 1,
El (x'+1, 1),
Dr, (2' + BB
(L + L) +
2,3
110011 (3,2', 2/)3
F.
-
(
V ((r
[11d
||d
72
32112g]1
c
3
af
4,3
Br
(1
+ Vig(a' 2/11l)
arl
Vig(=', (/++)|1++++ (00(2(2)00+))11=1
Lu K L1 +2
V
V2f(x (x1 .14
4
2
7211dt,11
4
ct
32 + VV2((''* s'll) + (L2 + R Lu 2) +
5(ar Ba)
2
2B,
Proof. By the definition of function D.r (I. v), we have
when E
[0, 1).
El (x
11 ,3' F[]
D., (x', v²) + (V (x',8") - d' x' - z²))
+ (dh x' -z")
1 Ko Ki(ll 1 Vif(a' s' + (Vig('' y')l + 2K2 1-11- +xx | -x
(59)
2
c
Considering the update rule for the variable in Algorithm 2, it follows that
(d ++1 x²) S (d' d + d x x²)
| |l
< 1 ld I2,1² + || - 2012
|| - 2²12
(60)
26

---

Ceneralized-Smoothh Bilevel Optimization with Nonconvex Lower-Level
where the first inequality follows from Young's 's inequality and the update rule for variable æ in Algorithm 2. And similar as (39), we have
| |l
(Vi d² xtt1 xt)
|1
1011
a2
(Fgg.. + Tuga,1 MC) 110 ,y") 12, (61)
40x
||d;
where M = www.aaaeeeee pe|o1] Vig((", p0t+1 + (1 - (x) ,
By combining (59) with (61), we have
E E (x*+1 , [F
< $ (x", ,/) + E
0t ||
[yyr,0 + 1 - -00 (3') + =lld oz (
4 - Blldd [1] +
3
att
3(Ko + k))a + 3(1
1
Vil(=', ,/''| + Vi9(t' (|) + 6Kia + 6(K2 + 1)a
6
CE
Lg000 Lg 11 1100)110010-0100 -0 r²)ll + |ldd 2. Fi
+ E
||d
7 arllldg
3
+
ate 6
3(Kg + n))a + 3(1
Vis((o' ا/'1 + Vig('* w2)ll) + 6Ki + 6(K2 + 1)
1
at
S s (ar y²)) +
[Tggr. + T. - 2²) + 4 || 2z 1
1
||
at L - a (1l 4 Ct
304 V 0(+1)]
+ ot
| Vig(a', v')l))
(Ko + + K1 + 2K2 + 2),
(62)
4
2
where the first inequality follows from the above Lemma A.3 and Assumption 5.7, the second inequality follows from Jensen's inequity B[[|d" [F] 2 |[d%_]] and the last inequality follows from ||a bbll 2 ||a|| ||]||_
Similarly, we have
E Φ ca (x"+1.y (1 [FFF]
< 1 (x1 ,3') + (V2 (xt+1, "y "r'),"" ~²² +
-"" 1 2
K3 + Kall= (2l(xt+) ,'')ll + V29(2=t1 V2(")*11,00"1
-
c
+ -2KKlly' fly w'1l - 110 8²112
< D., (x 11/)) + E
23 (10441 (3' )² + || - 2'112) [r - -E
(3
1 - 01
48,
+
1
K3 + Ka(ll
Vel Valt ,>">>>> + /Vgg(="1
"aad"",,''0 (.))))))) + 2Kally**1 - - + ks + 2 1100-1 -012
-
2
+ E
| az, 12 Fi
23, (100+1 10041-0,66 07('0' w/>l + ||a -|(oht--x((())) + 111, - 1
< L, (x1 .3/") + EE
3 1 V2 v + V2g(a , +
B
(Ka + + K4 + +Ks +2).
(63)
4 C4
2
27

---

Generalized-Smoool Bilevel Optimization with Nonconvex Lower-Level By combining the above inequalities (63) with (62), can obtain
E E (a .1 [FF
Pe. (x', v/) )+ (
[
(L
(Lgz
1g)
2
110
(7(4", 33')1 Fi
|
3211dg]1
01 (1)
Vif(a', الIll [Vigg('' ,/ 0 Vigg(', + of
433
Ko + x K1 2K₂ +2+
4 C
2
>211
(1 1
3
V2l(x ++ , (2 e+1 -1' +
(K3 + + K4 + 2Kg + 2) + 2B.
(as + Br).
(64)
4 Gt
2
(ii When p = similarly, we have
ElPa (x (xt y [FFl
1 aa (x', (a'.n' y²) + 18
0t (Lgg0 + MM +
23,
11 6, y 2/)) F.
a:
(1
|
if
ff
||d
721 >21dg/1
4
+ +| //
Vigll'
a?
Lo + k L1 +
4,8
B. (
V2
2
72110%
|V2g(=**) w3)1) +
32
LL2 + k + La + 2) +
(ax. + 3x).
(65)
2
2B.
Consider
Te = (L + M + 72
( 110 (x0+1 ,,00011, + (x', .²).
111
(66)
Thus, we have the following Lemma.
Lemma A.13. Under Assumptions 5.2, 5.3 and 5.7, suppose
E (0, 2m C++1 2 C₁ and m satisfies m
de It bggg 1 332) ( M²) T 7id.
1
we have
20 (L Lgr, 180
ET +1 F.
ai (11 1 v Vaf w')ll | Vig(<'
v/1l)
Be 1 Vef 1''''
1122 ff)l)) -e 01100 07(2', 1/)112
Ct
8
Ct
1222 25
+ B, B,
(a: + 3.)
(67)
28

---

Generalized-Smooll Bilevel Optimization with Nonconvex Lower-Level
Proof. By the definition of T. when p [0, 1), we have
BT4++1 - [F]
at
(Zzz. + I.gr.1 MP) + 23,
7/1 | (2 v/ 211
<R
||d''1|
at (Il 1 (if(=' | 3²) (]) + 3
a Vig(I 0(+1)] ||| + ai
43,
Ko + K x K1 + +222 +
Ce
4
2
?2|ld"]|
Se (11 _ 22f(x't1 +1 / + V2g(att1 )1) + & (K3 + x + K2 + 2Kg 2) +
8
(al + B1)
4
2
2B,
+ (L + 1g +
2
||||0* 07 (z x || [il - (L.z,0 + Lgv, 1M + 72 ) 100 - -6,(2' , 2²)
2
72
04
| Vi' ال + V 11' 31 Vig(z' ,,t,)| - 20, [g + +x+ + 2K2 +2 + 43,
s
4
73|1dh
3e
V2s(x" + w || + | 22 11 -1'1| (3g + x + K4 + 2Ks + 2) +
5
(a: + Br)
4
C2
2B,
2
+ (Lgr.0 + L 1 MP+ +
Ell00t (7 2 | - (Lega, + 1gx, + 7 || 0 ((xx,)))]
72
(1011 (Lggo + M0) + 2
ai ||22l|
|1041 (7 (/) 2
E
(68)
32
Next, we demonstrate that
E1100+1 - 077 ,, )11 - 1100 - -07(0', ,²) + at | - -7,(1', (1
|| |l
n1:52
SE
1 11 +
at
of (110= - -07(0', ,//)11++ +
Be ) - 110 - 07 ,/)
|
1
+
1 +
I (x ++1 ,) (xt, : 11
(69)
vi
where the last inequality follows from Lemma A.11.
Given v/= = 1/:8igg we have
B1100+1 - 07 +1 211 - 1100 - -0,(2','' ,11)1 + at 10ct1- 03 3/))111
||
<B - (112 g2 |
at
(110 )(100= 0))2+
0502 B.
") + (1 +
1 ) 13ll(att1 ,/14t - (a'.0')) -0))11177
(70)
Metigg
Similarly, we have
28
El|0o* 0,(aat!, .g ( y|1 110- -7, v2')1²2
110 (,, e/))1
ldy
23,
n1:02
<
1 + 1/4 +
82(110" (0)22)0))12 +
110 (z,22"20))
|dg| |I
B,
1
+ Vt
L (x g - (x ,'))
1/. gz
2,3( (110- 0, " ,1)21 + n2
)+ + (1+
1
1 (((latt,..tt1)))) - (a", (af. 201999 (71)
|
29

---

Generalized-Smooth Bilevel Optimization with Nonconvex Lower-Level
Putting the above inequalities (70), (71) into (69), we have
BTT+1 - [e]Fa]
01
|1
Vif(a' ay | (iVii( 100) (Vg((",)))) - (otlf,
200 Ko + +
433 +2+ + 7211dh)) T
4
Ct
)) 72
2
Br
| V2f(ett1 ,²)ll + 122 ,,91
4a. (1+ +
Lgzz0 + 1 10
1| G
g/2
4
_11
1
2
E ( (Lozo + Lon, MM
2
-33 + + K4 2Ks 1
L
Lgn + Lgg,, MP
72
7
1/tiga
1/:330 - -(Lyz,0 + L.g0,1 MP)
a1
Br
(110'
(x" ,0))+
'/ n
F
+
8
8(au + Be))
(72)
| ||
b211d
B,
2B,
v. /( . IIV
Given
0
<
at
S
1(Ko K1 +2K
(ig 1L gz, Loy 1414 (2)4611 Vig(t 10+11
V2fle'
w'
0
<
3e
4(K+++ 22
M +,
1 and
14 40 bax, L MP+ 13))
bog Mo) 21
7115
we can obtain
2z gn + Lg ddu+ (22)
E (+1 - Fil
S a1 (1 Vi v/ || + VVigg(>
Be (1
Ves(at, ,'''l + 1V2g(' w/)l))
Tetigg (110 - 07 , y/)1
8
a
112 52 20(a: + Br)
+
+
(73)
B.
B₁
When p= 1, according to Lemma A.1 we have
E (+1 - [e|Fi]
<E
[(1
at
(Tigr,0 + Ign,1 M) +
23:
|10 - 00, (,(1,,"""11
0;
Vis(a' //
+ +1 VV x''ll
|222||
?2||dt]1
+
avl VollVig(2', (0+1)11+
a?
Lo + L1 + +2+
4,3.
B.
2 (1 ز3و + V1 (14t,,))1 2/)1
4
2
32||db]1
4
Ct
82 (L2 + Ly + 2) + (Lzz,0 + M + ) 110e
2
(Lgz.0 + MM 2 (p)) 7/2
+
(7
1100 - 07 ,''''''"" ( Fz
s 0t (1aa Vif(z', 2²) + Vig(at, -3)1==331 VIg((" ,(+1)| 20z + K + L1 +2+
48g
4
32l|dt,1'
-2a(11 +
1 L2 Lg +
2 {
B1
( Vef(elt1
)/0)
1|V2g(z'+ l1'6
Tlttig2
1
2
(IIooo + L.g M + 7
2
-, + L3 +2+ -1
[L + Lg +
E
)
-(I.rr,0 + T. M)
0t
Be
(110* ,
11252
F
20(cs: + (c)
||]]]]
72
221
B,
B.
where the last inequality follows from Young's inequality with parameter M6Kg and rearrangement.
11 Vif(s a/01l Vig(n",0"))
Given
at
(2) nengg ( bya M+ -33) V Vig(a 0+
B <
30

---

Generalized-Smootli Bilevel Optimization with Nonconvex Lower-Level
144(Tgn0 + Toga M+ (3)))
(Tige.0 M) ue Pt
1 V2/ (Vag("""""
1051
7 731
and de
2k Lz ot i
we can also obtain
E ++1 [.
01 1
[11==
vff("', D'Il + 1/Vig((''
6e (1 ("""""'')1 + V29((' 77 (110* - 07 v/)1
8 Ct
8 G
112 82
20 + (e)
+
Fi
+
Bt
Bi
Theorem A.14. (Restatement of Theorem 5.8) Under Assumptions 5.1, 5.2, 5.3. 5.4 and 5.7, given ?
(0, 2ngg Ct at + 1)1/1 with & and Bi O(TL/2), and when P (0,1) let at S
ViSi'' V/Vll+/Viaaa w000""")) +K +2ko+2)4814 "0 M,C446|Vvo6ee
0 < B. S A[KatxtK w' w/)l
LEge when y')ll
1
V. Vigl''
0 V2/ . )l V|
22
let 0- < ac 1Lotath m2
B
ma Lgg and
L Viglt M
1+, 1+10 (L M)
84 n +
" E
2na2 C
11 + Lan Lov.: (E..)) 2,
1/7 K97
where C = -Ign.0 +
T1 MP + Sz. Then the sequence of , u 0²) generated by Algorithm satisfies
1 E1100 - 07 s0)l 0 USIST
min
T1/2
E(R 1+| .y ,y(+ 0 ((-///) )
1
0StST
E[g(=" x - Un 12 x² = 0
(
TI7
Proof. By using the above Lemma 13, telescoping the above inequality (67) over the range t 0,,1,'. T 1, given -illoiis--i le, and take the total expectation, we have
E rl
TT
T
E
Vif v || 8/1l))
[1 -11-
1
22f
+ VV v'Ill)
Ct
C2
0=
17:02
20(a; :.))
gz (110- - 07 (x", y/ 3²
+
B,
B.
E
at (1) v f(x" w/') + V ig(2", 2/ 22)
Br
[11 ,0'' 1/ ,/)I))
8
8
0
-202)
28(ar + Bi)
go (100
03 "","""""))1²
(74)
B,
It follows that
T
T-1 at
(
1
92
E[| (7 (/))) -
+
Σ E
(1)
C2
1=0
Be (1)
17²03
25(ar; + 8.) }
Vef(x' ا V2g(2' w'')l)
+
B,
B.
31

---

Generalized-Smooth Bilevel Optimization with Nonconvex Lower-Level
and let B, O(T2/2),
= O
B
1=0
Consequently,
min 054ST
B|||0
(x', |l = 0 T1122
According to the update rule of variables (x, y) in Algorithm 2, we have
d
Ct
(x (x't1_ - xx'== = 0,
(75)
dd
0z
dg
Ct
+
Ct
(y(t1 1011-20 xx')= = O.
(76)
|d
Be
Let
(c cty) Vf(x (((1tt1,(t1)
y(t1) + ce (V , - en (xtt1 ,yt1)
with
c2 ||dsال| (1lt) - 2²),
< = v 0 00 ,1 -cadt
(77)
at
ce cg|ldbp1 (y - 3²)
+ - V2 (, adt
(78)
B,
Considering the term || we have
- (111 V. - -cccoll + colld:]]
E|| [| <E(ca || V Dr (x
V. (x',
| el1 - 26'l
a4
+lle,d2 - ciddt F(F
(0[Lo,11(<"** (-tt,,,++] 1 - (x' w² + 2 (x),8") d',11 G||dta|| |l
| 1 x² |1
+ +cc
Br - [Fil
0tt
+ c||dاا|| | - x'1l + cell
-ElccToo, (1a ((aatt,,,(()) (a', w²) (,",""')
Vig("' 0²) Vig(a ,0, ,y [[[F))
6 +av Be
<Elce La, 1-+11-1- (d''"'>l + cلlجقااl |
x'll I1 + ct (e + Lgg,,1 MP)] - -0,(2', (((a,,/))llFF))
+ +av Bi
Thus, we can obtain
Bllee
celida]]
8 | 2'1l + ce + M (a, (1)) + tav B,
< Ele,La, || y - (a", y²) +
Similarity, based Lemma A.6, we obtain
E[|le[ [[[=]]
celldty1
< (o ,yttt) - (x", v0 +
|
11y
41
v0 + 2t (110= (2 x/' + Lo Loll x x111)[=1l + +ay B,
3,
32

---

Seneralized-Smooll Bilevel Optimization with Nonconvex Lower-Leeel
where Laz 1 fL + 1nn max VV Un)ll Lovo + Lg,,1 maxpee0,1) [2g Mp)l1 + Lt.e Since <4
Re(x, v) - d0, Vf(z. +) (V -ey (2, we have
+
calld'
+ CoLo
E[ ,y [] c (| ,tt (x', -1')|
1ott - x'll
11 1t '4'
at
+ Ca( + MP + 1 1110 (7 y'lll + 200/ Bi
min Va (ill 11111 (25 IIV22 >'Dl)>
Given R
we have
MMag max [1 11:1145113
B[Ri(alt) "lpl""t,,"tt [
CRR
a
(11
1
Vif(
w0)' (000(1,00011
Br (11
1
22l (') 11V2g(11,
1oig 110 03 55 st)113)
8
a
8
ct
48
+ B
By using the above inequality (74), then we have
T-1
26
Σ
(aaea"t1,,/-t11> s E[To]-
- E[[r] +
Σ
(2 + at + 3:)
B₁
i=0
T-1
28
s [|[ - mn +
(2 + a2 +
Bt
==0
1
< + 4012
Σ
(79)
B₂
==
where iny] is the lower bound of :[] la is the upper bound of og 3r from i E {0, (0, ,7] and I, la positive
constants.
Based on the above inequalities (79), let c = c(t + 1)4/4, we can obtain
E [ y +1 = O TTT7)- 05tST
min
Since (xt, y² JoSeST is sequence generated from Algorithm 2, we also can find m' maxosesT ElP,, (xf, ,0), + g g((",'") v. (2', v²), and ((*,y") 2 f* for any Then we have
a f(x", +')+
Blll( .v'' v.y (2", w < m - f 4E O.
Based on c. = c(t + 1)4/4, we can obtain
Big(ØT , -, ()) = 0 71/1
33


Reviews:
[{"review_id": "hUIIc2SOqt", "reviewer": "Reviewer_LknT", "summary": "This paper introduces an efficient Hessian/Jacobian-free Penalty Normalized Gradient (PNGBiO) method for solving bilevel optimization problems, where the upper-level objective is generalized smooth and nonconvex, while the lower-level objective is generalized smooth and weakly convex. Furthermore, the authors provide a comprehensive convergence analysis of the proposed PNGBiO method. Some experimental results demonstrate the effectiveness of PNGBiO.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**: Using the same parameter $M$ to denote two different terms in the convergence analysis (at lines 240 and 266) could indeed be a typo or an oversight in notation.\n\n**A1**:  Thanks for your comment. There is a typo. We will correct it in the final version of our paper.\n\n**Q2**: Since the normalized gradient plays a crucial role, could you provide a more detailed explanation of its purpose and necessity?\n\n**A2**: Thanks for your insightful comment. Inspired by the paper [1], the generalized smoothing condition implies that the smoothness is unbounded, i.e., it depends on the gradient information at a certain point. During the iteration process, too large changes may produce too large or too small gradients, making the algorithm unstable and inefficient. Normalization can effectively solve these problems, making it more robust and faster convergence. Thus, in our algorithm, we use the normalized gradient descent iteration. \n\n[1] Chen, Z., Zhou, Y., Liang, Y., and Lu, Z. Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization. In International Conference on Machine Learning, pp. 5396–5427. PMLR, 2023.\n\n**Q3**: In the PNGBiO algorithm, how to choose the parameters $\\gamma$ and $c_t$ in the experiments?\n\n**A3**: Thanks for your comment. In the experiments, we set  $c_t=\\frac{10}{(k+1)^{0.25}}$ ,  $\\gamma=0.1$.\n\n**Q4**: This paper studied the nonconvex bilevel optimization with the generalized smoothness introduced in (Chen et al. 2023 ). Why not consider the nonconvex bilevel optimization with the generalized smoothness in (Li et al., 2023) ?\n\n**A4**: Thanks for your comment. We chose to study the generalized smoothness nonconvex bilayer optimization proposed in (Chen et al. 2023) based on the following points: \n\n1)\tThe framework of (Chen et al. 2023) is more compatible with our theoretical foundations and methodology, and facilitates the integration and extension of existing results.\n\n2)\tThe scope of our paper is limited, and focusing on the framework of (Chen et al. 2023) helps to explore a specific problem in depth and avoid an overly broad scope.\n\n3)\tWe recognize the importance of exploring different broad definitions of smoothness including (Li et al., 2023), which will be of interest for future research.\n\n**Q5**: In Table1, the first $g(\\cdot,\\cdot)$ should be $f(\\cdot,\\cdot)$.\n\n**A5**:  You are right, we will correct this typo in the final version of our paper.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, but using the same parameter $M$ to denote two different terms in the convergence analysis (at lines 240 and 266) could indeed be a typo or an oversight in notation.", "experimental_designs_or_analyses": "Yes, experimental results demonstrate the effectiveness of the proposed method.", "relation_to_broader_scientific_literature": "This paper proposed an effective Hessian/Jacobian-free penalty normalized gradient (PNGBiO) method to solve the generalized-smooth bilevel optimization with weakly-convex lower-level objective, while the existing methods only studied the generalized smooth bilevel optimization with strongly convex lower-level objective.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:  In addition to the strengths mentioned in the Summary. In theoretical analysis, the paper proved that the proposed PNGBiO has a low gradient complexity of $O(\\epsilon^{-4})$ for finding an $ \\epsilon$-stationary point under milder assumptions such as generalized smoothness condition. \n\nWeakness: Since the normalized gradient plays a crucial role, could you provide a more detailed explanation of its purpose and necessity?", "other_comments_or_suggestions": "Typo: In Table1, the first $g(\\cdot, \\cdot)$ should be $f(\\cdot, \\cdot)$.", "questions_for_authors": "Q1: In the PNGBiO algorithm, how to choose the parameters $\\gamma$ and $c_t$ in the experiments ?\n\n\nQ2: This paper studied the nonconvex bilevel optimization with the generalized smoothness introduced in (Chen et al. 2023 ). Why not consider the nonconvex bilevel optimization with the generalized smoothness in (Li et al., 2023) ?", "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": "O3WkUdEfnN", "reviewer": "Reviewer_4qTz", "summary": "This paper studies the generalized smooth bilevel optimization, where the upper-level objective is nonconvex with generalized smooth, and the lower-level objective is weakly convex and generalized smooth. \n\nIt proposes an effective Hessian/Jacobian-free penalty normalized gradient (PNGBiO) method to solve these bilevel optimization problems. \n\nIt also provided the convergence analysis of the proposed PNGBiO method. Some experimental results verify efficiency of the proposed PNGBiOalgorithm.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**: This paper studied the generalized smooth bilevel optimization relying on the generalized smoothness introduced in [1]. The proposed PNGBiO method could apply the generalized smooth bilevel optimization with generalized smoothness introduced in [2] ?\n\n**A1**: Thanks for your comment. We study generalized smooth bilevel optimization based on generalized smoothness introduced  in [1] based on the following points: \n\n1)\tThe framework of [1] is more compatible with our theoretical foundations and methodology, and facilitates the integration and extension of existing results.\n\n2)\tThe scope of our paper is limited, and focusing on the framework of [1] helps to explore a specific problem in depth and avoid an overly broad scope.\n\n3)\tWe recognize the importance of exploring different broad definitions of smoothness including [2], which will be of interest for future research.\n\n**Q2**: In the experiments, how to choose the proximal parameter $\\gamma$ and penalty parameter $c_t$ in the proposed PNGBiO algorithm?\n\n**A2:** Thanks for your comment. In the experiments, we set  $c_t=\\frac{10}{(k+1)^{0.25}}$ ,  $\\gamma=0.1$.\n\n**Q3**: From Figure 1 in the paper, the proposed PNGBiO method solves the approximated problem (1). In the convergence analysis, the convergence measure used in the paper is reasonable?\n\n**A3**: Thanks for your comment. The metric in the article is reasonable, as our problem uses two approximations to the original problem, in the metric in this article, we have effectively carved the deviations generated during both approximations to get back to the original problem. Since the lower problem is not (strongly) convex, we could not use the traditional hyper-gradient for the carving, but instead used the residual function for the metric.\n\n**Q4**: In the convergence analysis, the term $M=\\max_{\\mu\\ \\in[0,1]}\\|\\nabla_1 g(x,\\theta_{\\mu})\\|$ is bounded ?\n\n**A4**: Thanks for your comment. As you said, in the convergence analysis, $M$ has a bounded gradient paradigm for every fixed $x$. Since our iteration can be terminated in a finite number of times, for $M$ it can take the maximum value within $t$ values. Moreover, $M$ is bounded when the Lipschitz smoothness condition is satisfied for $x$ in the lower function.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "This paper studies the generalized smooth bilevel optimization with nonconvex lower-level, while the existing methods mainly focus on the generalized smooth bilevel optimization relying on the strongly convex lower-level.\n\nIt presented an effective Hessian/Jacobian-free penalty normalized gradient (PNGBiO) method to solve these bilevel optimization problems, the comparison methods are designed for generalized smooth bilevel optimization which need to compute Hessian and Jacobian matrices.", "theoretical_claims": "I have read the main proof of the paper.\n\nThe primary proof presented in the paper is well-constructed, exhibiting no apparent errors, and follows a coherent and smooth logical progression that aligns with established techniques in the field.\n\nThis paper provides a convergence analysis of the proposed PNGBiO method, and proved that the PNGBiOmethod has a low gradient complexity of $O(\\epsilon^{-4}) $for finding an $ \\epsilon$-stationary point.", "experimental_designs_or_analyses": "The experimental design is robust, free of glaring weaknesses, and effectively supports its conclusions.", "relation_to_broader_scientific_literature": "This paper studied the generalized smooth bilevel optimization relying on the generalized smoothness introduced in [1]\n[1] Chen, Z., Zhou, Y., Liang, Y., and Lu, Z. Generalizedsmoothnonconvex optimization is as efficient as smooth nonconvex optimization. In International Conference on Machine Learning, pp. 5396–5427. PMLR, 2023.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. This paper studied the generalized smooth bilevel optimization relying on the generalized smoothness introduced in [1]. The proposed PNGBiO method could apply the generalized smooth bilevel optimization with generalized smoothness introduced in [2] ?\n\n[1] Chen, Z., Zhou, Y., Liang, Y., and Lu, Z. Generalizedsmoothnonconvex optimization is as efficient as smooth nonconvex optimization. In International Conference on Machine Learning, pp. 5396–5427. PMLR, 2023.\n\n[2] Li, H., Qian, J., Tian, Y., Rakhlin, A., and Jadbabaie, A. Convex and non-convex optimization under generalized smoothness. Advances in Neural Information Processing Systems, 36, 2023.\n\n\n2. In the experiments, how to choose the proximal parameter $\\gamma$ and penalty parameter $c_t$ in the proposed PNGBiO algorithm?\n3. From Figure 1 in the paper, the proposed PNGBiO method solves the approximated problem (1). In the convergence analysis, the convergence measure used in the paper is reasonable ?\n\n4）In the convergence analysis, the term $M=\\|\\nabla_1g(x,\\theta^*_{\\gamma}(x,y)) \\|$ is bounded ?", "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": "OiNkUTO0Yn", "reviewer": "Reviewer_5XnN", "summary": "This paper proposes a gradient-based first-order algorithm called PNGBiO for generalized-smooth nonconvex-weakly-concave bilevel optimization. The authors provide the convergence analysis and claim that this algorithm achieve a convergence rate of O(ϵ^(-4)) for finding an approximation stationary point. The authors conduct some experiments to show the effectiveness of the proposed algorithm.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**: The authors claim that the proposed algorithm solve the generalized-smooth bilevel optimization with nonconvex condition for both upper and lower level but only give an assumption that the lower-level objective function is weakly-convex. Did I miss something?\n\n**A1**: Thanks for your comment. At the **line 19 ( in introduction part)** of our paper, we have pointed out that the upper-level problem belongs to the category of general non-convex problems. \n\n**Q2**: Regarding the experiments, the authors did not conduct the comparison with BO-REP because it consumes a significant amount of memory. But in [1] a similar Hyper-representation task shows that BO-REP have a good ...\n\n**A2**:  Thanks for your comment. Our PNBiO can be generalized to the stochastic setting. We have initially proved that our stochastic PNGBiO has a gradient complexity of $O(\\epsilon^{-6})$. In the final version of our paper, we will add this conclusion. \nMeanwhile, we have added some experimental results on stochastic version of our PNGBiO method.  Specifically,  we compare our stochastic  PNBiO algorithm with other baselines including BO-REF, F^2SA, SLIP, BOME. In the experiment, we conduct the meta-learning task at CIFAR10 dataset,  and use Resnet18 as task-shared model at the upper-level (UL) problem, and use a 2-layer neural network as task-specific model at the lower-level (LL) problem. Clearly, both UL and LL problems are non-convex. We run each method for 500 seconds (CPU time)  with minibatch size 64 for both training and validation set. We set learning rates as 0.01 at F^2SA and BOME algorithms,  and $\\alpha=0.0001$, $\\beta=0.01$ at SLIP and BO-REF. Our algorithm uses a vanishing step size, which is $\\alpha_t=\\beta_t=0.3/(k+1)^{0.5}$,$\\eta=0.01$, the rest of the parameter settings are the same as in the paper, and the experimental results are shown in the following table (we have recorded the loss): \n|  | PNBiO| F$^2$SA |BOME|BO-REF|SLIP|\n|-------|-------|-------|-------|-------|-------|\n|100s|1.591| 1.822| 1.831|1.691|1.948| \n|200s|1.494 |1.655|1.692|1.585|1.839|\n|300s|1.441|1.568|1.615|1.464|1.775|\n|400s|1.392|1.485|1.542|1.402|1.723|\n|500s|1.371|1.425|1.467|1.382|1.601|\n\nIn the final version of our paper, we will add these experimental results. \n\n**Q3**: About Theorem 5.10. Seems that the authors give some unusual settings for the stepsize α, β and η, with some complex form of the gradient norm in the iteration t and a variety of parameters instead of the commonly used constant stepsize in other works. Could the authors further explain that what do these parameters stand for and how can these settings make the gradient update stable and efficient as descripted in the end of Section 4?\n\n**A3**: Thanks for your comment. In our paper, we set the step size as follows:\n$\\alpha_t\\in\\left(0,\\ \\frac{||\\frac{1}{c_t}\\nabla_1\\ f(x^t,y^t)||+||\\nabla_1\\ g(x^t,y^t)||}{4\\left(K_1+2K_2+2K_3+\\kappa\\right)+C}\\right)$,\n$\\beta_t\\in\\left(0,\\ \\frac{||\\frac{1}{c_t}\\nabla_2\\ f(x^t,y^t)||+||\\nabla_2\\ g(x^t,y^t)||}{4\\left(K_4+2K_4+2K_6+\\kappa\\right)+C}\\right)$, \nand \n$\\eta_t\\in\\left(0,\\ \\frac{\\min\\{||\\frac{1}{c_t}\\nabla_1\\ f(x^t,y^t)||+||\\nabla_1\\ g(x^t,y^t)||,||\\frac{1}{c_t}\\nabla_2\\ f(x^t,y^t)||+||\\nabla_2\\ g(x^t,y^t)||\\}}{\\kappa_{g_2}\\ \\max\\{4\\left(K_1+2K_2+2K_3+\\kappa\\right),4\\left(K_4+2K_4+2K_6+\\kappa\\right)\\}+C}\\right)$,\nwhere $C=8(1+\\frac{1}{\\eta_t\\kappa_{g_2}})L_\\theta^2(L_{gx,0}+L_{gx,1}M^\\rho+\\frac{2}{\\gamma^2})$.\n\nThese step sizes are the bounds derived during the theoretical analysis process. It can be considered that during the experimental process, the selection of the step size not only depends on the parameters of the generalized smoothness of the objective function but also relies more on the gradient at the current iteration point. Due to the special structure of the algorithm, it can be viewed in the following form:\n$x^{t+1}=x^t-\\alpha'_t\\ \\frac{||\\frac{1}{c_t}\\nabla_1\\ f(x^t,y^t)||+||\\nabla_1\\ g(x^t,y^t)||}{||d_x^t||}d_x^t$,\n$y^{t+1}=y^t-\\beta'_t\\frac{||\\frac{1}{c_t}\\nabla_2\\ f(x^t,y^t)||+||\\nabla_2\\ g(x^t,y^t)||}{||d_y^t||}d_y^t$,\nwhere $\\alpha'_t\\ \\in(0,\\frac{1}{4(K_1+2K_2+2K_3+\\kappa)+C})$，$\\beta'_t\\ \\in (0,\\ \\frac{1}{4(K_1+2K_2+2K_3+\\kappa)+C})$. When $C$ is a constant, it can be regarded as a constant step size, but this depends on the boundedness of $M$. \n\n**Q4**: Specifically, in section 5 ... these lemmas in the convergence analysis? Also, which lemmas are main novel ones? The description is .....\n\n**A4**: Thanks for your suggestion. These new lemmas are crucial to our theoretical contributions, and we believe they will provide new insights for research in related fields. In the final version, we will provide a more detailed description of these lemma.  We admit that the current description may be too dense. We will reorganize this section, adding more explanations  to make it easier for readers to comprehend our arguments and conclusions.", "claims_and_evidence": "This article is technically sound. The theory seems to be correct", "methods_and_evaluation_criteria": "I think the main strength is that the proposed algorithm obtains an ϵ-stationary solution with pure gradient calls and extend the smoothness condition to generalized smoothness for both upper and lower level for nonconvex-weakly-concave bilevel optimization.\n\nThe overall presentation is not clear. Specifically, in section 5 the authors give some proposition and lemmas without further description. What are the roles of these lemmas in the convergence analysis? Also, which lemmas are main novel ones? The description is very dense and difficult to parse.", "theoretical_claims": "The authors claim that the proposed algorithm solve the generalized-smooth bilevel optimization with nonconvex condition for both upper and lower level but only give an assumption that the lower-level objective function is weakly-convex. Did I miss something?\n\n\tAbout Theorem 5.10. Seems that the authors give some unusual settings for the stepsize α, β and η, with some complex form of the gradient norm in the iteration t and a variety of parameters instead of the commonly used constant stepsize in other works. Could the authors futher explain that what do these parameters stand for and how can these settings make the gradient update stable and efficient as descripted in the end of Section 4?", "experimental_designs_or_analyses": "Regarding the experiments, the authors did not conduct the comparison with BO-REP because it consumes a significant amount of memory. But in [1] a similar Hyper-representation task shows that BO-REP have a good performance compared to other baseline algorithms. Also, how do the authors choose the parameters of these algorithms? I’m not sure whether these parameters setting are fair or not. Moreover, the computational gain compared to other algorithms seems limited as shown in the experiment results.\n\n[1] Gong X, Hao J, Liu M. A nearly optimal single loop algorithm for stochastic bilevel optimization under unbounded smoothness[C]//Proceedings of the 41st International Conference on Machine Learning. 2024: 15854-15892.", "relation_to_broader_scientific_literature": "No", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "no", "other_comments_or_suggestions": "no", "questions_for_authors": "The authors claim that the proposed algorithm solve the generalized-smooth bilevel optimization with nonconvex condition for both upper and lower level but only give an assumption that the lower-level objective function is weakly-convex. Did I miss something?\n\n\tAbout Theorem 5.10. Seems that the authors give some unusual settings for the stepsize α, β and η, with some complex form of the gradient norm in the iteration t and a variety of parameters instead of the commonly used constant stepsize in other works. Could the authors futher explain that what do these parameters stand for and how can these settings make the gradient update stable and efficient as descripted in the end of Section 4?\n\nRegarding the experiments, the authors did not conduct the comparison with BO-REP because it consumes a significant amount of memory. But in [1] a similar Hyper-representation task shows that BO-REP have a good performance compared to other baseline algorithms. Also, how do the authors choose the parameters of these algorithms? I’m not sure whether these parameters setting are fair or not. Moreover, the computational gain compared to other algorithms seems limited as shown in the experiment results.\n\n[1] Gong X, Hao J, Liu M. A nearly optimal single loop algorithm for stochastic bilevel optimization under unbounded smoothness[C]//Proceedings of the 41st International Conference on Machine Learning. 2024: 15854-15892.", "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": "qE4pYR8I9A", "reviewer": "Reviewer_RaRE", "summary": "The paper investigates bilevel optimization problems where the inner function is nonconvex, and both inner and outer functions satisfy a generalized smoothness assumption. To address this problem, the single-level constrained formulation of bilevel optimization is adopted, replacing the inner problem with the Moreau envelope of the inner function. A novel algorithm, PNGBiO, is introduced, which involves performing normalized gradient steps on the Lagrangian function of this constrained problem. The algorithm demonstrates a convergence rate of O(T−1/4)O(T−1/4). Additionally, the paper presents experimental results for two bilevel problems: hyperparameter tuning and data hypercleaning.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks so much for your comments and suggestions. We response to your questions one by one as follows:\n\n**Q1:** What is the meaning of stationary point in this context since the lower level problem is not assumed to be strongly convex?\n\n**A1:** In our paper, we use the same definition of stationary point as in [1]. From [1], the stationary point of problem (1) is equivalent to that of the relaxed problem $\\min_{(x,y)\\in \\mathbb{R}^d \\times \\mathbb{R}^q} f(x,y) s.t. \\nabla_y g(x,y)=0$. When the lower-level of problem (1) is strongly convex, this stationary point is equivalent to the stationary point used in [2,3].\n\n[1] Liu et al., Moreau envelope for nonconvex bi-level optimization: A single-loop and hessian-free solution strategy. arXiv preprint arXiv:2405.09927, 2024.\n\n[2] Ghadimi, S. and Wang, M. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246, 2018.\n\n[3] Ji, et al., Bilevel optimization: Convergence analysis and enhanced design. ICML, 4882–4892, 2021.\n\n**Q2:** ... Is it easy to extend PNGBiO to the stochastic setting? \n\n**A2:** Our PNBiO can be generalized to the stochastic setting. We have initially proved that our stochastic PNGBiO has a gradient complexity of $O(\\epsilon^{-6})$. In the final version of our paper, we will add this conclusion.\nMeanwhile, we add some experimental results on our stochastic PNGBiO (**S-PNGBiO**) method.  Specifically,  we compare our S-PNBiO algorithm with other baselines including BO-REF, F^2SA, SLIP, BOME. In the experiment, we conduct the meta-learning task at CIFAR10 dataset,  and use Resnet18 as task-shared model at the upper-level (UL) problem, and use a 2-layer neural network as task-specific model at the lower-level (LL) problem. Clearly, both UL and LL problems are non-convex. We run every method for 500 seconds (CPU time)  with minibatch size 64 for both training and validation set. We set learning rates as 0.01 at F^2SA and BOME algorithms,  and $\\alpha=0.0001$, $\\beta=0.01$ in SLIP and BO-REF. Our algorithm uses a vanishing step size, which is $\\alpha_t=\\beta_t=0.3/(k+1)^{0.5}$,$\\eta=0.01$, the rest of the parameter settings are the same as in the paper, and the experimental results are shown in the following table (we have recorded the loss): \n|  | S-PNBiO| F$^2$SA |BOME|BO-REF|SLIP|\n|-------|-------|-------|-------|-------|-------|\n|100s|1.591| 1.822| 1.831|1.691|1.948| \n|200s|1.494 |1.655|1.692|1.585|1.839|\n|300s|1.441|1.568|1.615|1.464|1.775|\n|400s|1.392|1.485|1.542|1.402|1.723|\n|500s|1.371|1.425|1.467|1.382|1.601|\n\nIn the final version of our paper, we will add these experimental results. \n\n**Q3:** Lines 205-208:  The papers claims that the generalized smoothness assumption…, is there any example of such function in machine learning?\n\n**A3:** 1) When $\\rho=0$, our generalized smoothness condition degenerates to standard Lipschitz smoothness condition. 2) When $\\rho\\in(0,1]$, this smoothness condition depends on the current gradient. For example, the polynomial function $f(x)=|x|^\\frac{2-\\rho}{1-\\rho}$, where $x\\in\\mathbb{R}$ and $\\rho\\in(0,1)$, satisfies this generalized smoothness condition. In this case, it does not apply when $\\rho=1$.\n\n**Q4:** Can the convergence result provided by the paper be translated in terms of convergence of the norm the hyper-gradient (equation (2) in the paper) when the inner function is strongly convex?\n\n**A4:** When inner function is strongly convex, we have proved that our method has the same convergence rate $O(\\frac{1}{T^{1/4}})$ based on the hyper-gradient metric as in [1], which shows  our algorithm has the same rate of convergence under the generalized smooth condition as  the  standard smooth condition. In the final version, we will add these results. \n\n[1] Liu et al., Moreau envelope for nonconvex bi-level optimization: A single-loop and hessian-free solution strategy. arXiv preprint arXiv:2405.09927, 2024.\n\n**Q5:** Some questions of experimental designs.\n\n**A5:** 1. In the experiments, the tuning parameters of all algorithms are selected to be optimal through the grid. \n\n2. In the data cleaning experiment, the problem is based on unconstrained conditions, so here $R$ should be infinite, and here is a typo. \n\n3. In the algorithms that require inner loops, we set 10 times. \n\n\n**Q6:** The partial gradients are denoted with number in subscript while the partial Hessians are denoted with letter in subscript...\n\n**A6:** In the paper, we have a different definition for the subscripts: 1 and 2 represent the derivatives with respect to the first and second parts, respectively. We will clarify this in the final version of our paper.\n\n**Q7:** Questions about essay structure, mathematical writing and typos.\n\n**A7:**  Thanks so much for your suggestions. In the final version of our paper, we will correct these typos and mathematical writing, and will reorganize the section 5 of our paper, explaining the main results to make them clearer. Meanwhile, some theoretical results will be added.", "claims_and_evidence": "I review the theoretical claims in the section **Theoretical Claims** and the experimental evidences in the section **Experimental Designs or analyses**.", "methods_and_evaluation_criteria": "See the section **Experimental Designs or analyses** for the evaluation criteria.", "theoretical_claims": "See the supplementary material section for a review of the proof of the theoretical results.\nBesides the proofs, I have the following remark:\n\n* **Stationnary point of problem (1)**: Several times (lines 130, 322, 324), the paper refers to stationary points of problem (1).  What is the meaning of *stationary point* in this context since the lower level problem is not assumed to be strongly convex?", "experimental_designs_or_analyses": "### Reproducibility \nThe numerical part presents several reproducibility issues:\n* **Code**: The code of the experiments is not provided, which does not foster the reproducibility of the results. This is an important concern.\n* **Step size choice**: How are set the step sizes? Is it a grid search? In this case, the parameters of the grid should be precised. Why some algorithms use decreasing step sizes and other not? \n* **Constraint**: For the contraint on $\\lambda$ in the data hyper-cleaning task, how is it handled in the different algorithms which are originally designed for unconstrained optimization? How is chosen $R$?\n* **Inner loop**: Some algorithms use inner loops (F2SA, BOME), what is the size of the inner loop?\n* **Batch size for stochastic algorithms**: F2SA and SLIP are stochastic algorithms. What are the batch sizes used? \n* **Number of runs**: How many runs are performed for each algorithm? Since some algorithms are stochastic, a single run is not enough to draw conclusions and error bars should be provided.\n\n### Presentation/clarity\n* **x-axis of the figures**: In figures 2 to 5, the x-axis is labeled as *\"Epoch\"*. What does the word \"Epoch\" refers to? In the context of bilevel optimization, the notion of \"epoch\" is fuzzy since there are two datasets (training and validation). Moreover, some algorithms use an inner loop or not, some others use second order information of the lower level problem or not, thus to be perfectly fair, curves in terms of wall-clock time would be more appropriate.\n\n* **Data hypercleaining**: It would be convinient to be more precise when talking about *\"contaminated training data\"*. Reader ununfamiliar with data hyper-cleaning should understand by reading the paper that *\"contaminated training data\"* means some labels of the training data are wrong. Moreover, it should be clearly to write explicitly the bilevel problem considered, as done in the hyperparameter tuning problem.\n\n* **Hyperparameter learning**: what is the regularizer $\\mathcal{R_{\\omega, \\lambda}}$?\n\n### Design\n* **No nonconvex lower-level**. If I understand appropriately, in both cases, the lower level problem is a multinomial logistic regression problem. But this problem is convex and thus this is a concern that there are no experiments with nonconvex lower-level problem when the title of the paper suggests treating this case.", "relation_to_broader_scientific_literature": "On the one hand, this paper extends the algorithm proposed in [1] to scenarios where both the inner and outer functions satisfy a generalized smoothness assumption. On the other hand, [2, 3] consider bilevel algorithm  where only the outer function meets this assumption, while the inner function is strongly convex. These algorithms are based on approximate implicit differentiation. Thus, the method proposed in this paper complement this line of work by considering the generalized smoothness assumption on both functions and providing a fully first-order algorithm for this case.\n\n[1] Liu, R., Liu, Z., Yao, W., Zeng, S., and Zhang, J. *Moreau envelope for nonconvex bi-level optimization: A single- loop and hessian-free solution strategy*. arXiv preprint arXiv:2405.09927, 2024.\n\n[2] Hao, J., Gong, X., and Liu, M. *Bilevel optimization under unbounded smoothness: A new algorithm and convergence analysis*. ICLR 2024.\n\n[3] Gong, X., Hao, J., and Liu, M. *A nearly optimal single-loop algorithm for stochastic bilevel optimization under unbounded smoothness*. ICML, 2024.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "### Strengths\n* To my knowledge, this is the first time that a fully fisrt-order algorithm is proposed for bilevel optimization under the generalized smoothness assumption. \n\n* The paper comes with non asymptotical convergence rates.\n\n### Weaknesses\n* **Presentation/writing**: The presentation and the writing of the paper need to be significantly improved. There are many typos, grammar issues and sentences that need to be rephrased. I provide a non-exhaustive list of these issues in the section \"Other Comments Or Suggestions\".\n\n* **Section 5, page 4, 5**: the presentation of the theoretical results is really hard to parse. There is no transition between the different proposition/lemmas and they are not discussed/explained. Moreover, letting all the raw constants in the main text blurs the message. I think this section requires in profund clean up by moving some lemmas in the appendix, only keeping the most important quantities in the main text, and providing some highlevel explanations of the results. \n\n* The algorithms comes with many hyperparameters (penalty parameter $c_t$, step sizes $\\alpha_t$, $\\beta_t$, and $\\eta_t$, proximal parameter $\\gamma$). This can make it difficult to use in practice.", "other_comments_or_suggestions": "### Typos/Unclear sentences\n* **Abstract**: *\"we stydy the convergence analysis\"* -> *\"we study the convergence property\"*\n* **Line 032**: *\"When the lower-level objective function $g(x, y)$ on the variable y is strongly convex and twice differential\"* -> *\"When the lower-level objective $g$ is strongly convex and twice differentiable with respect to $y$\"*\n* **Line 043**: *\"by using the following approximated gradient\"* -> *\"by using the following approximate gradient\"*\n* **Line 049**: *\"where $\\hat y$ is an approximate of the solution $y^*(x)$\"* -> *\"where $\\hat y$ is an approximation of the inner solution $y^*(x)$\"* or *\"where $\\hat y$ is an approximate solution of the inner problem $y^*(x)$\"*\n* **Line 82**: *\"can not\"* -> *\"cannot\"*\n* **Lines 95-98**: *\"More recently, (Liu et al., 2024) solve a variant of the single-level constrained optimization problem (5), where uses its Moreau envelope instead of the problem $\\min_{y\\in\\mathbb{R}^p} g(x, y)$ in the problem (5), defined as\"* -> *\"More recently, Liu et al. (2024) solve a variant of the single-level constrained optimization problem (5), where the Moreau envelope of the inner  function is used as a surrogate of the inner problem $\\min_{y\\in\\mathbb{R}^p} g(x, y)$ in (5). This yields the following problem formulation\"*\n* **Lines 109, 66-67**: *\"More recently, thus, some methods (Hao et al., 2024; Gong et al., 2024) have begun to study generalized smooth bilevel optimization.\"* -> *\"More recently, some authors (Hao et al., 2024; Gong et al., 2024) started to study bilevel optimization under generalized smoothness assumption.\"*\n* **Lines 106**: *\"The generalized smoothness condition firstly was studied\"* -> *\"The generalized smoothness condition was first studied\"*\n* **Lines 115-120**: *\"In the problem (1), since lower-level objective $g(x, y)$ is\nnonconvex on variable y, we can not easily get the minimum of lower-level problem $\\min_{y\\in\\mathbb{R}^p} g(x, y)$. Thus, we reformulate the lower-level problem by using a value function defined as: $v(x) = \\min_{y\\in\\mathbb{R}^p} g(x, y)$.\"* The logical sequence of these sentences is unclear. It textually tells that, when the inner function in non-convex, solving $\\min_{y\\in\\mathbb{R}^p} g(x, y)$ is too difficult, and thus it is replaced by $v(x)$ which is actually the same thing.\n* **Assumption 5.2 and 5.3**: *\"there exists\"* -> *\"there exist\"*\n* **Assumption 5.2 and 5.3**: comma missing before *\"and\"*: *\"$L_{fy,0}$ and $L_{fy,1}$\"* ->  *\"$L_{fy,0}$, and $L_{fy,1}$\"*; *\"$L_{gy,0}$ and $L_{gy,1}$\"* ->  *\"$L_{gy,0}$, and $L_{gy,1}$\"* \n* **Line 320**: *\"the above three terms shows\"* -> *\"the above three terms show\"*\n* **Lines 417 to 425**: there are several issues in the definition of the bilevel problem:\n    * $\\sum_{x_i \\in S_{val}}$ -> $\\sum_{i \\in S_{val}}$\n    * $\\omega^*$ -> $\\omega^*(\\lambda)$\n    * $\\omega^* = \\mathcal{L}_{S_{tr}}(\\omega, \\lambda)$ -> $\\omega^* = \\mathcal{L}_{S_{tr}}(\\omega^*, \\lambda^*)$ -> $\\omega^*(\\lambda) = \\underset{\\omega}{\\mathrm{arg\\,\\min}}\\mathcal{L}_{S_{tr}}(\\omega, \\lambda)$\n    * the third line of the equation should also be corrected.\n\n### Notation consistency\n* **Equations (2) and (3)**: The partial gradients are denoted with number in subscript while the partial Hessians are denoted with letter in subscript. It would be more consistent to use the same notation for both.\n* **Numeratical experiments**: In the data hypercleaning problem, the individual losses are denoted $\\ell$ while in the hyperparameter tuning problem, they are denoted $\\mathcal{L}$. Moreover, the full loss function are denoted $L$ in the data hypercleaning problem and $\\mathcal{L}$ in the hyperparameter tuning problem. Moreover, in the bilevel problem between lines 417 and 425, the individual train losses depend on $\\lambda$ while the individual validation losses do not.\n\n### Miscellanous\n* **Line 024**: *\"and distributionally robust optimization\"*: there should be a citation for this task.\n\n* **Line 157**: *\"Based on Theorem A.4 of (Liu et al., 2024), it is known that any limit point $(\\bar x, \\bar y)$ of sequence $(x^t, y^t)$ is a solution to the problem (9).\"* The sequence $(x^t, y^t)$ is not defined.\n\n* **Correct citation formating**: when the authors' name of a paper is part of the sentence, they should not be in parenthesis (in LaTeX it consists in using `\\cite`or `\\citet` instead of `\\citep` I think). For instance:\n    * line 50: *\"(Ghadimi & Wang, 2018)\nproposed a class of approximated gradient methods based\non approximate implicit differentiation. (Ji et al., 2021) proposed\nan effective approximated gradient methods based on the iterative differentiation. More recently, (Huang, 2023; 2024) studied the nonconvex bilevel optimization\"* -> *\"Ghadimi & Wang (2018) proposed a class of approximated gradient methods based on approximate implicit differentiation. Ji et al. (2021) proposed an effective approximated gradient methods based on the iterative differentiation. More recently, Huang (2023; 2024) studied the nonconvex bilevel optimization\"*\n    * Line 156: *\"Based on Theorem A.4 of (Liu et al., 2024)\"* -> *\"Based on Theorem A.4 of Liu et al. (2024)\"*\n\n* **Precision on AID-based methods**: Equation (3) makes think that the linear system that appears in the hypergradient is solved exactly. This is not the case. As the solution of the inner problem is approximated, the solution linear system is also approximated.\n\n* **Page header**: page header should be changed. Now it is still *\"Submission and Formatting Instructions for ICML 2025\"*.\n\n\n* **Notation definition**: In lemma 5.6, $\\theta^*_\\gamma$ is used without being defined. Actually, it is defined in the appendix. It should be defined before being used.\n\n### Mathematical writting\n* **Assumptions 5.2. and 5.3.**: Are the constants $L_{fx,0}\n$, $L_{fx,1}$, $L_{fy,0}$, $L_{fy,1}$, $L_{gx,0}$, $L_{gx,1}$, $L_{gy,0}$, and $L_{gy,1}$, independent from $\\rho$? In this case, it is necessary to revers the order of the quantifiers by writting *\"There exist constants $L_{fx,0}$,..., and $L_{fy,1}$ such that for any $\\rho>0$\"*. Otherwise, it means that these constants depend on $\\rho$ and in this case, this dependency should be made explicit.", "questions_for_authors": "* In many machine learning problems, having stochastic algorithms is crucial to handle large datasets. Is it easy to extend PNGBiO to the stochastic setting?\n\n* **Lines 205-208**: The papers claims that the generalized smoothness assumption used in Assumptions 5.1 and 5.2 is milder than the one usually used. But, I don't really see why since the proposed smoothness condition is supposed to hold for any $\\rho\\in[0,1]$ and not only at $\\rho = 1$. Could the authors clarify this point? Moreover, is there any example of such function in machine learning?\n\n* Can the convergence result provided by the paper be translated in terms of convergence of the norm the hypergradient (equation (2) in the paper) when the inner function is strongly convex?", "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:

Meta-review: This paper addresses bilevel optimization problems under generalized smoothness conditions, when both the upper-level and lower-level objectives are nonconvex. The authors introduce PNGBiO, a fully first-order, Hessian/Jacobian-free method that leverages normalized gradients. The theoretical contribution includes non-asymptotic convergence guarantees with a provable gradient complexity, and the empirical section demonstrates competitive performance across standard bilevel tasks.

I recommend acceptance. The paper makes a clear and novel contribution by proposing the first gradient-based algorithm under this generalized setting, supported by solid theoretical analysis. While presentation could be improved, the technical content is sound, and the reviewers acknowledge the approach and its convergence guarantees.
Decision: Accept (poster)