Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis
Authors: Jie Hao
Xiaochuan Gong
Mingrui Liu
Venue: ICLR 2024 spotlight (2024)
Keywords: Bilevel Optimization
Unbounded Smoothness
Deep Learning
Primary area: optimization
TL;DR: This paper design and analyze a new algorithm for bilevel optimization under unbounded smoothness, with empirical validation on deep learning tasks.

Abstract: Bilevel optimization is an important formulation for many machine learning problems, such as meta-learning and hyperparameter optimization. Current bilevel optimization algorithms assume that the gradient of the upper-level function is Lipschitz (i.e., the upper-level function has a bounded smoothness parameter). However, recent studies reveal that certain neural networks such as recurrent neural networks (RNNs) and long-short-term memory networks (LSTMs) exhibit potential unbounded smoothness, rendering conventional bilevel optimization algorithms unsuitable for these neural networks. In this paper, we design a new bilevel optimization algorithm, namely BO-REP, to address this challenge. This algorithm updates the upper-level variable using normalized momentum and incorporates two novel techniques for updating the lower-level variable: \textit{initialization refinement} and \textit{periodic updates}. Specifically, once the upper-level variable is initialized, a subroutine is invoked to obtain a refined estimate of the corresponding optimal lower-level variable, and the lower-level variable is updated only after every specific period instead of each iteration. When the upper-level problem is nonconvex and unbounded smooth, and the lower-level problem is strongly convex, we prove that our algorithm requires $\widetilde{O}(1/\epsilon^4)$ \footnote{Here $\widetilde{O}(\cdot)$ compresses logarithmic factors of $1/\epsilon$ and $1/\delta$, where $\delta\in(0,1)$ denotes the failure probability.} iterations to find an $\epsilon$-stationary point in the stochastic setting, where each iteration involves calling a stochastic gradient or Hessian-vector product oracle. Notably, this result matches the state-of-the-art complexity results under the bounded smoothness setting and without mean-squared smoothness of the stochastic gradient, up to logarithmic factors. Our proof relies on novel technical lemmas for the periodically updated lower-level variable, which are of independent interest. Our experiments on hyper-representation learning, hyperparameter optimization, and data hyper-cleaning for text classification tasks demonstrate the effectiveness of our proposed algorithm. The code is available at [https://github.com/MingruiLiu-ML-Lab/Bilevel-Optimization-under-Unbounded-Smoothness](https://github.com/MingruiLiu-ML-Lab/Bilevel-Optimization-under-Unbounded-Smoothness).

Published as a conference paper at ICLR 2024
BILEVEL OPTIMIZATION UNDER UNBOUNDED SMOOTHNESS: A NEW ALGORITHM AND CONVER-
GENCE ANALYSIS
Jie Hao, Xiaochuan Gong, Mingrui Liu"
Department of Computer Science, George Mason University, Fairfax, VA 22030, USA {jhao6, xgong2, (angruui/@@mu...
ABSTRACT
Bilevel optimization is an important formulation for many machine learning prob- lems, such as meta-learning and hyperparameter optimization. Current bilevel optimization algorithms assume that the gradient of the upper-level function is Lipschitz (i.e., the upper-level function has bounded smoothness parameter). However, recent studies reveal that certain neural networks such as recurrent neu- ral networks (RNNs) and long-short-term memory networks (LSTMs) exhibit po- tential unbounded smoothness, rendering conventional bilevel optimization algo- rithms unsuitable for these neural networks. In this paper, design new bilevel optimization algorithm, namely BO-REP, to address this challenge. This algo- rithm updates the upper-level variable using normalized momentum and incor- porates two novel techniques for updating the lower-level variable: initialization refinement and periodic updates. Specifically, once the upper-level variable ini- tialized, a subroutine is invoked to obtain a refined estimate of the corresponding optimal lower-level variable, and the lower-level variable is updated only after ev- ery specific period instead of each iteration. When the upper-level problem is non- convex and unbounded smooth, and the lower-level problem strongly convex, we prove that our algorithm requires ((1/c*) iterations to find an e-stationary point in the stochastic setting, where each iteration involves calling stochastic gradient or Hessian//acobian-vettoo product oracle. Notably, this result matches the state-of-the-art complexity results under the bounded smoothness setting and without mean-squared smoothness of the stochastic gradient, up to logarithmic factors. Our proof relies on novel technical lemmas for the periodically updated lower-level variable, which are of independent interest. Our experiments on hyper- representation learning. hyperparameter optimization, and data hyper-cleaning for text classification tasks demonstrate the effectiveness of our proposed algorithm. The code available https: tht.tb..ttutgggggggg//gggg.g.t com/ /aan/Miigrrii MaauuuMLLaab Bilevel- weweeee--lpiimiee zati -nn underudddeee Unboundeeebd Smoothness.
INTRODUCTION
Bilevel optimization refers to optimization problem where one problem is nested within an- other (Bracken & McGill, 1973; Dempe, 2002). It receives tremendous attention in various machine learning applications such as meta-learning (Franceschi et al., 2018; Rajeswaran al., 2019). hyper- parameter optimization (Franceschi et al., 2018; Feurer & Hutter, 2019), continual learning (Borsos et al., 2020), reinforcement learning (Konda & Tsitsiklis, 1999; Hong et al., 2023), and neural net- work architecture search (Liu et al., 2018). The bilevel problem is formulated as the following:
min ((x) = f(x, y² (x)), s.t., #ER
y yx(x) E arg min g(x, y),
(1)
yER",
where f and 9 are referred to as upper and lower-level functions, respectively, and are continuously differentiable. The lever-level variable directly affects the value of the leper-level function f and indirectly affects the lower-level function via (ar). In this paper, we assume the lower-level func- tion (2,, y) strongly-convex in y such that y (æ:) is uniquely defined for any x E TR and f(x y) is potentially nonconvex. One important application under this setting is hyper-repressntation learn- ing with deep neural networks (Franceschi et al., 2018), where æ denotes the shared representation
"Corresponding Author: Mingrui Liu (mingruil 10 @mmu. (dd).
'err Ö(-) compresses logarithmic factors of 1/c and 1/6, where E (0, 1) denotes the failure prohability.

---

Published as a conference paper at ICLR 2024
Table I: Comparison of stochastic bilevel algorithms for finding an c-stationary point as defined in Definition 2.1. The oracle stands for calls to stochastic gradients and stochastic Hessian/Jacobian- vector products. C denotes o-times differentiability with Lipschitz k-th order derivatives. "SC" means "strongly-convex". We do not include results with O complexity and with extra mean- squared smooth stochastic gradient assumption (Yang al., 2021; Khanduri al., 2021).
Method
Oracle Complexity
Upper-level
Lower-level, Batch Size
BSA (Ghadimi & Wang. 2018)
Ōle-)
Ct
SC and C²
Õ(1)
StocBio (Ji al., 2021)
0(e-t)
C2
SC and 22
Ō(c-))
AmIGO (Arbel & Mairal, 2021)
Ō(e-))
C/
SC and C?,2
O(e-))
TTSA (Hong al., 2023)
Ö(c-9)
C
SC and c2
Õ(1)
ALSET (Chen et al., 2021)
O(e-*)
C2
SC and C2
O(1)
FSAA (Kwon et al., 2023a)
O(e-")
C/2¹
SC and C?,
0(1)
SOBA (Dagréou al., 2022)
O(c-))
C22
SC and C?
O(1)
MA-SOBA (Chen et al., 2023b)
O(c-*)
SC and C?2
O(1)
RO-REP (this work)
Ö(e-4)
(lgg,0
1, 1, Ly a. ) >-mmooth
SC and C??²
O(1)
layers that utilized across different tasks, and y denotes the classifier encoded in the last layer. In this paper, we consider the stochastic setting. We only have access to the noisy estimates of f and g: far y) = Eg-D, [xxx, y; C)] and g( y) = Ee-D, (zx y: E)], where Dy and D, are underlying data distributions for f and g respectively.
The convergence analysis of existing bilevel algorithms needs to assume the gradient is Lipschitz (i.e.. the function has bounded smoothness parameter) of the upper-level function f (Ghadimi & Wang, 2018; Grazzi et al., 2020; et al., 2021; Hong al., 2023; Kwon et al., 2023a). How- ever, such an assumption excludes an important class of neural networks such as recurrent neu- ral networks (RNNs) (Elman, 1990), long-short-term memory networks (LSTMs) (Hochreiter & Schmidhuber, 1997) and Transformers (Vaswani al., 2017) which are shown to have unbounded smoothness (Pascanu et al., 2012: 2013; Zhang et al., 2020b; Crawshaw et al., 2022). For exam- ple, Zhang al. (2020b) proposed relaxed smoothness assumption that bounds the Hessian by linear function of the gradient norm. There is line of work designing algorithms for single-level re- laxed smooth functions and showing convergence rates first-order stationary points (Zhang al., 2020b;a; Jin et al., 2021; Crawshaw et al., 2022; et et al., 2023b; Faw et al., 2023; Wang et al., 2023). However, they are only restricted to single-level problems. It remains unclear how to solve bilevel optimization problems when the upper-level function exhibits potential unbounded smoothness (i.e., (L 1,,1, Ly. 1 smmoothnsss 2).
Designing efficient bilevel optimization algorithms in the presence of unbounded smooth upper-level problems poses two primary challenges. First, given the upper-level variable, the gradient estimate of the bilevel problem (i.e., the hypergradient estimate) is highly sensitive to the quality of the estimated lower-level optimal solution: an inaccurate lower-level variable will significantly amplify the estimation error of the hypergradient. Second, the bias in the hypergradient estimator depends on both the approximation error of the lower-level solution and the hypergradient itself, which are statistically dependent and difficult to handle. These challenges do not appear in the literature bilevel optimization with bounded smooth upper-level problems.
In this work, we introduce new algorithm, namely Bilevel Optimization with lower-level initial- ization REfinement and Periodic updates (BO-REP), to address these challenges. Compared with the existing bilevel optimization algorithm for nonconvex smooth upper-level problems (Ghadimi & Wang, 2018; Grazzi et al., 2020; Ji et al., 2021; Hong et al., 2023; Kwon et al., 2023a), our algo- rithm has the following distinct features. Specifically, (1) inspired by the single-level optimization algorithms for unbounded smooth functions (Jin et al., 2021; Crawshaw et al., 2022), our algorithm updates the upper-level variable using normalized momentum gradient noise and possibly unbounded gradients. (2) The update rule of the lower-level variable relies on two new techniques: initialization refinement and periodic updates. In particular, when the upper-level variable is initialized, our algorithm invokes a subroutine to run first-order algorithm for the lower-level variable given the fixed initialized leper-level variable. addition, the lower-
control the effects of stochastic
Thhe formal definition of (Tez,o, o, I, Ty Iy is illustrated in Assumption 1.
2

---

Published as a conference paper at ICLR 2024
level variable is updated only after every specific period instead of every iteration. This particular treatment for the lower-level variable is due to the difficulty brought by the unbounded smoothness of the upper-level function. Our major contributions summarized as follows.
We design a new algorithm named BO-REP, the first algorithm for solving bilevel opti- mization problems with unbounded smooth upper-level functions. The algorithm design introduces two novel techniques for updating the lower-level variable: initialization refine- ment and periodic updates. To the best of our knowledge, these techniques are new and not leveraged by the existing literature on bilevel optimization.
When the upper-level problem nonconvex and unbounded smooth and the lower-level problem is strongly convex, we prove that BO-REP finds e-stationary points in ((1/²t) iterations, where each iteration invokes stochastic gradient or Hessian vector product oracle. Notably, this result matches the state-of-the-art complexity results under bounded smoothness setting up logarithmic factors. The detailed comparison of our algorithm and existing bilevel optimization algorithms (c.g., setting, complexity results) are listed in Table 1. Due the large body of work on bilevel optimization and limit space, we refer the interested reader to Appendix A, which gives a comprehensive survey of related previous methods that are not covered in Table
We conduct experiments on byper-representation learning, hyperparameter optimization, and data hyper-cleaning for text classification tasks. We show that the BO-REP algorithm consistently outperforms other bilevel optimization algorithms.
2 PRELIMINARIES AND PROBLEM SETUP
In this paper, we use (.)) and || || to denote the inner product and Euclidean norm. We denote f: Rd= x Rd, + I as the upper-level function, and g: Rd. x IRdv - I. as the lower-level function. Denote (xxx)) as the hypergradient, and it is shown in Ghadimi & Wang (2018) that
(xx) = Vas(a, (xr) - V V ua y (x)) y (x))) V y (x:)
= Vas(æ, (x))) Va v Var (z. y² (z))
where x= =xxx) = V2g(z, (x)) Vf (xx y (x)) is the solution to the linear system =" =xxx) arg min= 1 (V y" (z))z, 2) (V, y² (z)). z). We aim to solve the bilevel optimization problem (1) by stochastic methods, where the algorithm can access stochastic gradients and Hessian vector products. We will use the following assumptions.
Assumption 1 ((Lm,, L,,1, L,,, Lyg,1 )-smoothness), Define u = (ax, y) and u' = =(x', (x', there exists L0 L Ly,0, L such that [[ v=f(u')ll s (Læ,0 + L beenl//aa az) u u') and (w) v < + vl u- w'll iflluuu' s 1/ 2 + 12,1).
Remark: Assumption 1 is a generalization of the relaxed smoothness assumption (Zhang et al., 2020b;a) for a single-level problem (described in Section B. and Section B.2 in Appendix). A generalized version of the relaxed smoothness assumption is the coordinate-wist relaxed smooth- ness assumption (Crawshaw et al., 2022), which is more fine-grained and applies to each coordinate separately. However, these assumptions
designed exclusively for single-level problems. Our (La..0 LI,1, Ly.o. Ly J-smoothness assumption for the upper-level function f can be regarded as the relaxed smoothness assumption in the bilevel optimization setting, where we need to have differ- ent constants to characterize the upper-level variable x and the lower-level variable y respectively. It can recover the standard relaxed smoothness assumption (e.g., Remark 2.3 in Zhang et al. (2020a)) when Le.0 Ly = Lo/2 2 and L = Ly L1/2, The details of this derivation are included in Lemma B.3 in Appendix B. Assumption is empirically verified in Appendix G.
Assumption 2. The function f(x, y) and g(æ, y) satisfy the following: (i) There exists M > 0 such that for any x, y 3² (xr) S M; (ii) The derivative || a V Tyg(u)) is bounded, i.e., for any u (x, y), II a L (u)lll "gen" (iii) The lower function g(x, B) is pu-ttrongly convex with respect to y: (iv) g(u) is L-smooth, Le., for any u = (I, y), u' = (æ', vz). [[Vg(u) Vg(u')ll S T. u'll: (v) The derivatives Va V.Vgg (u)(u) and V2 V2 are and p-Lipschitz i.e,, any u, u', ||V VyV(())) V Veg(uu)) S Tillu- u'Il, [V Vzg(u') S pllu u'|l.
Remark: Assumption 2 is standard in the bilevel optimization literature (Ghadimi & Wang, 2018; Grazzi et al., 2020; Ji et al., 2021; Hong et al., 2023; Kwon et al., 2023a) and we have followed the
3

---

Published as a conference paper at ICLR 2024
same assumptions here. Under Assumption 1 and 2, we can show that the function ((x) satisfies standard relaxed smoothness condition: - I (Ko + (x'')((x')) (l)) |x===1|| with constant Kg and K2 if æ and x' are not far away from each other (i.e., Lemma C.3 in Appendix C). Assumption 3. We access gradients and Hessian/Jacobian vector products of the objective func- tions by unbiased stochastic estimators. The stochastic estimators have the following properties:
E Va v: [)] = V f v);
BewD, [IV F(a, C) - V=f( f)1l s o7,1,
Eç-D, vV y: ()] = V Vu/(a, y),
Be-DD (V - v.l(2, ||'] S 5
Eg-11, [V y G(z [)] = Ve v).
Be-DD [exp v: v æ y)ll /o - exp(1),
Eg-D, [ y (1v, y: {)] = Vi y):
EEWD, [[
(z y) || - 2g20
RgWD, V V G( a. y: E) = V V Vug( y), BEWDD [IV G( y V~ Vug(a, y)1 S 2.
Assumption 3 requires the stochastic estimators to be unbiased and have bounded variance and are standard in the literature (Ghadimi & Lan, 2013b: Ghadimi & Wang. 2018). In addition, we need the stochastic gradient noise of function to be light-tail. It is technical assumption for high probability analysis for y. which typical for algorithm analysis in the single-level convex and nonconvex optimization problems (Lan, 2012; Hazan & Kale, 2014; Ghadimi & Lan, 2013b).
Remark:
Definition 2.1. x E d is an e-stationary point of the bilevel problem (1) if (+)]| S.
Remark: In nonconvex optimization literature (Ghadimi & Lan, 2013b; Ghadimi & Wang. 2018; Zhang et al., 2020b), the typical goal is to find an e-stationary point since it is NP-hard in general for finding a global minimum in nonconvex optiiizttion (Hillar & Lim, 2013).
ALGORITHM AND THEORETICAL ANALYSIS
3.1 MAIN CHALLENGES AND ALGORITHM DESIGN
Main Challenges. We first illustrate why previous bilevel optimization algorithms and analyses cannot solve our problem. The main idea of the convergence analyses of the existing bilevel opti- mization algorithms (Ghadimi & Wang. 2018; Grazzi et al., 2020; Ji et al., 2021; Hong et al., 2023; Dagréou et al., 2022; Kwon al., 2023a; Chen et al., 2023b) is approximating hypergradient (2) and employ the approximate hypergradient descent to update the upper-level variable. The hypergradient approximation is required because the optimal lower-level solution y (a:) cannot be easily obtained. The typical approximation scheme requires to approximate y (x) and also the
vec- tor product x (z) by solving a linear system approximately. When the upper-level function has a bounded smoothness parameter, these approximation errors cannot blow up, and they can be easily controlled. However, when the upper-level function is (T.g.,, I_g,1, T.y.0: I-y.oo- as illustrated in Assumption 1, an inaccurate lower-level variable will significantly amplify the estimation error of upper-level gradient: the estimation error explicitly depends on the magnitude of the gradient of the upper-level problem and it can be arbitrarily large (e.g., gradient explosion problem in RNN (Pas- canu et al., 2013)). In addition, in a stochastic optimization setting, the bias in the hypergradient estimator depends on both the approximation error of the lower-level variable and the hypergradient in terms of the upper-level variable, which are statistically dependent and difficult to analyze. There- fore, existing bilevel optimization algorithms cannot be utilized to address our problems where the upper-level problem exhibits unbounded smoothness.
Algorithm Design. To address these challenges, our key idea is to update the upper-level variable by the momentum normalization technique and a careful update procedure for the lower-level vari- able. The normalized momentum update for the upper-level variable has two critical goals. First, reduces the effects of stochastic gradient noise and also reduces the effects of unbounded smooth- ness and gradient norms, which can regarded as a generalization of techniques of (Cutkosky & Mehta, 2020; Jin et al., 2021; Crawshaw et al., 2022) under the bilevel optimization setting. The main difference in our case is that we need to explicitly deal with the bias in the hypergradient es- timator. Second, the normalized momentum update can ensure that the upper-level iterates move slowly, indicating that the corresponding optimal lower-level solutions move slowly as well due to the Lipschitzness of the mapping y (z). This important fact enables to design initialization finement to obtain an accurate estimate of the optimal lower-level variable for the initialization, and the slowly changing optimal lower-level solutions allow to perform periodic updates for updating the lower-level variable. As a result, we can obtain accurate estimates for y (x:) at every iteration.
4

---

Published as a conference paper at ICLR 2024
Algorithm 1: BO-REP
Input: zo. Vn 20, me 0; B, 17, ao
y/ = Epoch Epoch-sGD@2o, Vo an)
# initialization refinement
for k = 0, .,....
do
yk+1 = UpdateLower
yk. 1: {x))
# periodic updates
2++1 24 vl v G yu Ez F( yk)
m = fmm + (1 3) F UK: V V G
yhi Ex)
m+++1
0k+1
end
WWe only sample & = -
-N-1(6 (& when = jI, where 1 S i S
K II_ and 1 denotes the update frequency
for yı in Algorithm 2; we do not update yı and hence do not sample & when * jí (i.e., & for & and j 2 1).
Algorithm 2: UpdateLower
Algorithm 3: Epoch-SGD
Input: x, yk- 7, Ex
Input: æo, 30 ag
if' k > 0 and k is multiple of I then yk yk
Initialize: Bo, To, kl; ;
2 for b,......k kt do
for t 0, ...,. N 1 do
3
for = 0, T. do
yk
yo g.t+1
BI R) yh GV, (0 (
118.
net a. G( 36"
yk f 1 1+1
s
end
yk+1 = Uh
yot ++10
- yo
else
Update B., Ts. a, via (28), (29), (30)
yk+11 yk:
8 end
return y/++11
t'.0 return yo
The detailed framework is described Algorithm Specifically, we first run a variant epoch SGD for the smooth and strongly convex lower-level problem (Ghadimi & Lan, 2013a; Hazan & Kale, 2014) (line 1) to get an initialization refinement. Once the upper-level variable æ is initialized, need to get Yo close enough y" (a:)). Then, the algorithm updates the upper-level variable æ, lower-level variable
and the approximate linear system solution z within loop (line 2~7).
In particular, we keep a momentum buffer to store the moving average of the history hypergradient estimators (line 5), and use normalized momentum updates for æ (line 6), stochastic gradient descent update for (line 4) and periodic stochastic gradient descent with projection updates for y (line 3). Note that Øi R) ;= {y R : l!l - ÿ I R} denotes ball centered at ý with radius R, II is denoted as the projection operator.
3.2 MAIN RESULTS
We will first define few concepts. Let F& denote the filtration of the random variables for updating 2g. my and By before iteration k. i.e., F3 == a .ob....,.--1 So.
.o.. GG-3 for any 1: 2 where a.)} denotes the o-algebra generated by the random variables. Let Fo denote the filtration of the random variables for updating lower-level variable Yo starting the s-th epoch before iteration in Algorithm 3, ie.. Fs.tt = o (5o .o 1 for 1 < t T, and < S kt 1, which contains all randomness in Algorithm 3. Let F% denote the filtration of the random variables for updating for 1 < < N and k = jī, where 1 S j < [ and denotes the update frequency for yı in Algorithm 2. Let Fx denote the filtration of all random variables for updating lower-level variable y) (A: 2 0), i.e., Fx = { { Foo
lower-level variable yı (k: 2 1) before iteration in Algorithm 2, i.e., F off......
(UK-TTN) }. For the overview notations used in
this paper, please check our Table in Appendix.
5

---

Published as a conference paper at ICLR 2024
Theorem 3.1. Suppose Assumptions 1, and 3 hold. Run Algorithm I for K iterations and
2212
let f2x be the sequence produced by Algorithm For e S min
Ko. Ki
min
320 SEN
and given E (0, if we choose a, as (30), v²
? as (44),
N as (45) and
o K 1
1
min 2M 2.2
min (1, 3202 bay
ce sny n²
(1 B),
80
160
5.2
7 min
8 min
RT Ko [V
C 2e. ) (1 (3),
1+
+ 12,1)
where A (x.)) ze ((x) and 22,0 == 1100 (2x0) 1|? then with probability at least
1 - 8 over the randonmess in Fk, Algorithm guarantees * Σk=o Ell [((()) S 30e as long
as K 4A where the expectation is laken over the randomness in Fk. In addition, the number of
oracle calls for updating lower-level variable y (in Algorithm 2 and Algorithm 3 is at most Ô
Theorem 3.1 indicates that Algorithm I requires a total Ö( oracle complexity for find- ing an e-stationary point in expectation, which matches the state-of of-the-art complexity results non- convex bilevel optimization with bounded smooth upper-level problem (Dagréou et al., 2022; Chen al., 2023b) and without mean-sques mean-squared smoothness assumption on the stochastic oracle 3. Please note that our complexity is optimal up to logarithmic factors due to the l((=") complexity lower bounds in the nonconvex stochastic single-level optimization for finding c-stationary points (Arje- vani et al., 2023). More detailed statement of the optimality is described in Appendix L.
Remark:
3.3 SKETCH OF THE PROOF
In this section, we present the sketch of the proof of Theorem 3.1. The detailed proof can be found in
Appendix E. Define y = y (mx)), zt x= (a*)) and ( yk. zui Sa. E.) = V F(x,, yxs Cu. V V, yni Ek =R. We use Es, EF,F and IE to denote the conditional expectation E |- FuJ. the expectation on F& and the total expectation over all randomness in FK, respectively. The main difficulty comes from the bias term | (V yk: Zx: Gx.E&) (=x=)) of the hypergradient (xx) by Assumption This quantity is difficult to handle because (i) // ( (zx) (I can be large; (ii) both |1. y and [[ are measurable with respect to F and it is difficult to decouple them when taking total expectation.
estimator, whose upper bound depends on L 3/
To address these issues, we introduce Lemma 3.2, 3.3 and 3.4 to control the lower-level error, and hence control the bias in the hypergradient estimator with high probability over the randomness in FK as illustrated in Lemma 3.5. Then we analyze the expected hypergradient error between the moving-average estimator (i.e., momentum) and the hypergradient, as illustrated in Lemma 3.6, where the expectation is taken over the randomness in FK. Lastly we plug in these lemmas to the descent lemma for (L 1 Ly.u, Ly,1) smoohh functions and obtain the main theorem.
Lemma 3.2 (Initialization Refinement). Given 8 E (0, and O, set the parameter k [log2 ( (128K)Vo) Vo/ [ where Vo is defined in (27). If we run Algorithm 3 for ket epochs with output yo. with projection ball B., the number of iterations T. and the fixed step-size as at each epoch defined as (28), (29) and (30). Then with probability at least 1 8/2 over ran- domness in o -
(this event is denoted as Eg), we have y y (2o)) S e/8Ku in Ö K2/ iterations.
Remark. More detailed statement of Lemma 3.2 can be found in Appendix D.2. Lemma 3.2 provides complexity result for getting good estimate of y (xx) with high probablity. The next lemma (i.e., Lemma 3.3) is built upon this lemma.
NNte that there are a few works which achieve Ō(c-) oracle complexity when the stochastic function is mean-squared smooth (Yang al., 2021; Guo al., 2021; Khanduri al., 2021), ) but our paper does not make such assumption.

---

Published as a conference paper at ICLR 2024
Lemma 3.3 (Periodic Updates). Given 8 E (0,1) and > 0, choose R.
- Under Eo, for any us
fixed sequences {0x 1K jkmi such that To = 2o and |0*+1 - TxIl = 7, where ri S 5ka if we run VK
Algorithm 2 with input { 1k=1 and generate outputs {ūk 1 and step-size ? = O K.) for N 2 ()) iterations in each update period (the exact formula of and N are (44) and (45)), then with probability at least 1 - 6//2 over randomness in a { JN (this event is denoted as E1). we have lyy (ātx) U S c/ o/4Ko for any k 1 in Ö(Ko 3.1 K K 2) iterations.
Remark. More detailed statement Lemma 3.3 can be found in Appendix D.3. Lemma 3.3 unveils the following important fact: as long as the learning rate 7/ is small, the upper-level solution moves slowly, then the corresponding lower-level optimal solution also moves slowly. Therefore, as long we have a good lower-level variable estimate at the very beginning (e.g., under the event Eg), we do not need to update it every iteration: periodic updates schedule is sufficient to obtain an accurate lower-level solution with high probability at every iteration. In addition, this fact does not depend on any randomness from the upper-level problem, it holds over any fixed sequence {ãt ) as long as ||06+11 Fxll = 1).
Lemma 3.4 (Error Control for the Lower-level Problem). Under event & = Eo n Es, we have (*xx) yx S c/4Ko for any k 2 0 and Pr(E) 2 1 - 8 and the probability taken over randomness in k.
Remark. Lemma 3.4 is direct corollary of Lemma 3.2 and 3.3. It provides a high probability guarantee for the output sequence { in terms of any given input sequence { as long as ||a - Fz || = Note that the event & E FR and is independent of the rest randomness in the Algorithm 1 (i.c., Fk). This important aspect of this lemma enables us to plug in the actual sequence { LK j== in Algorithm I without affecting the high probability result. In particular, we will show that under the event & (which holds with high probability in terms of Fx). Algorithm will converge to e-stationary point in expectation, where the expectation is taken over randomness in FK illustrated in Theorem 3.1.
Lemma 3.5 (Bias of the Hypergradient Estimator). Suppose Assumptions 1, 2 and 3 hold. Then under event E, we have
Lu.15 [<x()))) + [I2,,0 + Iz,11 Cory M + TM
E& ( yk. zxi Ex. v=(m)) S
+ Cszv 12x
zill-
1Kg
1Kg
Remark. Lemma 3.5 controls the bias in the hypergradient estimator under the event E. Note that the good event & make sure that the bias is almost negligible since it depends on small quantities c and 2| = (Lemma D.5 in Appendix D.5 shows that E| =žll ll is small on average).
Lemma 3.6 (Expected Error of the Moving-Average Hypergradient Estimator). Suppose Assump-
tions I, 2 and hold. Define òR = m ( to be the moving-average estimation error.
K
Then under event E, we have EE
Σ |
S Erri + Err2, where Err, and Err, are defined as
Erri =
La.1
[+(x))) + K
[om,0 + Ton,1
Cary M
TM
6
+ Coen VK.
Σ
2z =]]
4Ku
P
4Ko
2M
K-1
Erra = KVV 3
81031
22 V20
BBVK
Σ
E.
[[lEe
- =1]1
4²
King K-1
KoKn3
8 + I-
moo V
1-
kmd
Remark. Lemma 3.6 shows that, under the event E, the error can be decomposed as two parts. The Err, and Err, represent the error from bias and variance respectively. As long 1 1- B is small (as chosen in Theorem 3.1), then the accumulated expected error of the avviage hypergradient estimator grows only with a sublinear rate in K, where K is the number of iterations. This fact helps us establish the convergence rate of Algorithm 1. Lemma 3.6 can be seen as a generalization of the normalized momentum update lemma from single-level optimization (e.g., Theorem C.7 in Jin al. (2021)) to bilevel optimization.
7

---

Published as a conference paper at ICLR 2024
4 EXPERIMENTS
4.1 EUPER-REPRESENNTTIIO LEARNING FOR TEXT CLASSIFICATION
We conduct experiments on the hyper-repressntattio learning task (i.e., meta-learning) for text clas- sification. The goal is to learn a hyper-representation that can be used for various tasks by simply adjusting task- fask-specifie parameters. There are two main components during the learning process: base learner and a meta learner. The meta learner learns from several tasks in sequence to improve the base learner's performance across tasks (Bertinetto et al., 2018).
The meta-learning contains m tasks {Ti, = I,.... m) sampled from certain distribution Py. The loss function of each task L(w,, 0:: E), where w is the hyperr-epresenttation (meta learner) which extracts the data features across all the tasks and & is the data. 0; is the task-specific parameter of a base learner for i-th task. The objective is to find the best w to represent the shared feature representation, such that each base learner can quickly adapt its parameter 0, to unseen tasks.
This task can be formulated a bilevel problem (Ji et al., 2021; Hong et al., 2023). In the lower level, the goal of the base learner is to find the minimizer 0 of its regularized loss on the support set S upon the reperrrepresentttion w. In the upper level, the meta learner evaluates all the 0 , = 1, m on the corresponding query set Q., and optimizes the hyperpresentation w. Let 0 (0 (0,,.., Om) be all the task task-specific parameters, the objective function the following:
1
m
min
L(w, 077 (w): s.L. O" (w) arg min
L(w, C(w,0:()) 11:011 (3)
SED
CES,
where S, and Q, come from the task T. In our experiment, 0, is the parameter of the last linear layer of neural network for classification, and w represents the parameter of a 2-layer recurrent neural network except for the last layer. Therefore, the lower-level function ju-strongly convex for any given w, and the upper-level function is nonconvex in w and has potential unbounded smoothness.
Hyper-representation experiment is conducted over Amazon Review Dataset, consisting of two types of reviews across 25 different products. We compare our algorithm with classical meta- learning algorithms and bilevel optimization algorithms, including MAMI (Rajeswaran et al., 2019), ANIL (Raghu al., 2019), StocBio (Ji et al., 2021). TTSA (Hong et al., 2023), F'SA (Kwon et al., 2023a), SOBA (Dagréou et al., 2022), and MA-SOBA (Chen et al., 2023b). We report both training and test losses. The results are presented in Figure ((a) and Figure 2(a) (in Appendix F.I), which show the learning process over 20 epochs on the training data and evaluating process on test- ing data. Our method (i.e., the green curve) significantly outperforms baselines. More experimental details are described in Appendix F.I.
4.2 HYPERPARAMETER OPTIMIZATION FOR TEXT CLASSIFICATION
We conduct hyperparameter optimization (Franceschi al., 2018; Ji et al., 2021) experiments for text classification to demonstrate the effectiveness of our algorithm. Hyperparameter optimization aims find a suitable regularization parameter À to minimize the loss evaluated over the best model parameter wx from the lower-level function. The hyperparameter optimization problem can be formulated as:
min Dvail
Σ L(w" (A):E), s.t. w" (A) arg min EEDia
1
Σ CED.
A [[(w: () + 11111
(4)
|Dul
w
where L(w; {) is the loss function, w is the model parameter, and À denotes the regularization parameter. Dval and Drr denote validation and training sets respectively. The text classification experiment is performed over the Amazon Review dataset. In our experiment, we compare our al- gorithm with stochastic bilevel algorithms, including StocBio (Ji et al.. 2021), TTSA (Hong al., 2023), F'SA (Kwon et al., 2023a), SOBA (Dagréou et al., 2022), MA-SOBA (Chen et al., 2023b). As shown Figure 1(b) and Figure 2(b) (in Appendix F.2), BO-REP achieves the fastest conver- gence rate and the best performance compared with other bilevel algorithms. More details about hyperparameter settings are described in Appendix F.2.
4.3 DATA HYPER- CEEER-CEENNING FOR TEXT CLASSIFICATION
Consider a noisy training set Drr = {(x,, ) with label J. being randomly corrupted with probability p < 1 (i.e., corruption rate). The goal of the data hyper-cleaning (Franceschi et al.,
8

---

Published as a conference paper at ICLR 2024
0.7
0.7
0.68
Train Looe
Train Loss
0.67
AM. DieDe
0.5
0.66
0.4
0.65
2004
0.64
10
15
0
10
15
10
20
opochs
opochs
epochs
0.7
0.7
0.6
0.650
Test Loss
0.5
F85T Loss
Text Laos
0.625
ANL
0.600
0.4
0.3
MA-03A
0.3
MA5034
WA-COAA
0
10
15
10
15
0
10
20
opochs
opochs
epochs
(a) Hypeer-Rerresentttinn (b) Hyperparameter Optimization
(c) Data Hyper-Cleaning
Figure 1: Comparison of various bilevel optimization algorithms three applications: (a) results of Hyper-representation on Amazon Review Dataset. (b) results of hyperparameter optimization on Amazon Review Dataset. (c) results of data hyper-cleaning on Sentiment 140 Dataset with noise rate
p 0.3.
2018; Shaban al., 2019) task is to assign suitable weights A; to each training sample such that the model trained on such weighted training set can achieve good performance on the uncorrupted validation set D The hyper-cleaning problem can be formulated follows:
min
Σ ((w)(A): s.t. w² (A)) E arg min REDia
1 |Dul
Σ GED
((w)) + cllwl? (5)
VDall
where a(.) is the sigmoid function, and L(w; () is the lower level loss function induced by the model parameter w and corrupted sample Ç, and >> is regularization parameter.
conducted over the Sentiment] 10 dataset (Go et al., 2009) for text classification, where data samples consist two types of emotions for Twitter messages. For each data sample in the training set, replace its label with random class number with probability meanwhile keeping the validation set intact. We compare our proposed BO-REP algorithm with other baselines StocBio (Ji et al., 2021), TTSA (Hong al., 2023), F2SA (Kwon al., 2023a), SOBA (Dagréou et al., 2022), and MA-SOBA (Chen et al., 2023b). Figure 1(c) and Figure 2(c) (in Appendix) show the training and evaluation results with corruption rate p 0.3, and Figure 3 (in the Appendix F.3) show the results with 0.1. BO-REP demonstrates a faster convergence rate and higher performance than other baselines on both noise settings, which is consistent with our theoretical results. We provide more experimental details and discussion in Appendix F.3.
The hyper-cleaning experiments
CONCLUSION
In this paper, we design a new algorithm named BO-REP, to solve bilevel optimization problems where the upper-level problem has potential unbounded smoothness. The algorithm requires access to stochastic gradient or stochastic Hessian//acobian-veea.
product oracles in each iteration, and we have showed that BO-REP algorithm achieves ((1/c4) oracle complexity to find an e-stationary point. matches the state-of-the- complexity results under the bounded smoothness setting and without mean-squared smoothness of the stochastic gradient, up logarithmic factors. We have conducted experiments for various machine learning problems with bilevel formulations for text classification tasks, and our proposed algorithm shows superior performance strong baselines. In the future, we plan to design more practical variants of this algorithm (c.g., single-loop and Hessian-free algorithms).

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
We would like to thank the anonymous reviewers for their helpful comments. This work has been supported by grant from George Mason University, the Presidential Scholarship from George Ma- son University, a ORIEI seed funding from George Mason University, and a Cisco Faculty Research Award. The Computations were run on ARGO, research computing cluster provided by the Office of Research Computing at George Mason University (URL: https: //orc. gmu edu).
REFERENCES
Michael Arbel and Julien Mairal. Amortized implicit differentiation for stochastic bilevel optimiza- tion. arXiv preprint arXiv:2111.14580 2021.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1-2): 165-214, 2023.
Luca Bertinetto, Joao F Henriques, Philip HS Torr, and Andrea Vedaldi. Meta-learning with differ- entiable closed-form solvers. arXiv preprint 1rXiv:1805.08133 2018.
John Blitzer, Ryan McDonald, and Fernando Pereira. Domain adaptation with structural correspon- dence learning. In Proceedings of the 2006 conference on empirical methods in natural language
processing, pp. 120-128, 2006.
Zalán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. Advances in neural information processing systems, 33:14879-14890, 2020.
Jerome Bracken and James T McGill. Mathematical programs with optimization problems in the constraints. Operations research, 21(1):37-44 1973.
Lesi Chen, Jing Xu, and Jingzhao Zhang. On bilevel optimization without lower-level strong con- vexity. arXiv preprint arXiv:2301.007/2, 2023a.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 34: 25294-25307, 2021.
Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A single-timescall method for stochastic bilevel optimization. In International Conference Artificial Intelligence and Statistics, pp. 2466-2488. PMLR, 2022.
Xuxing Chen, Tesi Xiao, and Krishnakumar Balasubramanian. Optimal algorithms for stochas- tic bilevel optimization under relaxed smoothness conditions. arXiv preprint arXiv:2306. /2067, 2023b.
Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized-smooth nonconvex optimization as efficient smooth nonconvex optimization. arXiv preprint arXiv:2303.022 028554, 2023c.
Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang, Robustness to unbounded smoothness of generalized signsgd. Advances in neural information processing systems, 2022.
Michael Crawshaw, Yajie Bao, and Mingrui Liu. Episode: Episodic gradient clipping with periodic resampled corrections for federated learning with heterogeneous data. In The Eleventh Interna- tional Conference on Learning Representations, 2023a.
Michael Crawshaw, Yajie Bao, and Mingrui Liu. Federated learning with client subsampling, data heterogeneity, and unbounded smoothness: A new algorithm and lower bounds. In Thirty- Conference on Newral Information Processing Systems, 2023b.
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. International Confer- on Machine Learning, pp. 2260-2268. PMLR, 2020.
10

---

Published as a conference paper at ICLR 2024
Ashok Cutkosky and Francesco Orabona. Momentum-baut variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. Advances in Neural Information Processing Systems, 35:26698-2677 26710, 2022.
Stephan Dempe. Foundations of bilevel programming. Springer Science & Business Media, 2002.
Jeffrey L Elman. Finding structure in time. Cognitive science, 14(2):179-211, 1990.
Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smooth- ness: A stopped analysis of adaptive sgd. arXiv preprint arXiv:2302.06670, 2023.
Matthias Feurer and Frank Hutter. Hyperparameter optimization. Automated machine learning: Methods, systems, challenges, pp. 3-33, 2019.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. International conference on machine learning. pp. 1126-1135. PMLR, 2017.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient- hyperparameter optimization. International Conference on Machine Learning (ICML), pp. 1165-1173 2017.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riecardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International conference machine learning, pp. 1568-1577. PMLR, 2018
Saced Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly con- vex stochastic composite optimization, ii: shrinking procedures and optimal algorithms. SIAM Journal on Optimization, 23(4):2061-200 2089, 2013a.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal on Optimization, 23(4):2341 2013b.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming arXiv preprint 1eX.:0180..02246,, 2018
Alec Go, Richa Bhayani, and Lei Huang. Twitter sentiment classification using distant supervision. CS224N project report, Stanford, 1(12):2009, 2009.
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration com- plexity of hypergradient computation. In International Conference on Machine Learning, pp- 3748 3758. PMLR, 2020.
Riccardo Grazzi, Massimiliano Pontil, and Saverio Salzo. Bilevel optimization with a lower-level contraction: Optimal sample complexity without warm-start. Journal of Machine Learning Re- search, 24(167):1-37, 2023.
Zhishuai Guo, Quanqi Hu, Lijun Zhang, and Tianbao Yang. Randomized stochastic variance- reduced methods for mulk stochastic bilevel optimization. arXiv preprint arXiv:2105.02266, 2021.
Elad Hazan and Satyen Kale. Beyond the regret mininization barrier: optimal algorithms for stochastic strongly-convex optimization. Journal of Machine Learning Research, 15(1):2489- 2512, 2014.
Christopher Hillar and Lek- Hek-Heng Lim. Most tensor problems are harhard. Journal of the ACM (JACM), 60(6):1-33) 2013.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
11

---

Published as a conference paper at ICLR 2024
Mingyi Hong, Hoi-To Wai, Zhaoran Wang. and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147-180, 2023.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International conference on machine learning, pp. 4882-4892. PMLR, 2021.
Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. Advances in Neural Information Processing Systems, 34: 2771 277122782, 2021.
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum Advances in neural information processing systems, 14:30271-30283 2021.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning, pp. 18083- 18113. PMLR, 2023a.
Jeongyeol Kwon, Dohyun Kwon, Steve Wright, and Robert Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. arXiv preprint arXiv:2309.01753, 2023b.
Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Program- ming, 133(1-2):36--37, 2012.
Guanghui Lan, Arkadi Nemirovski, and Alexander Shapiro. Validation analysis of mirror descent stochastic approximation method. Mathematical programming, 134(2)425-458, 2012.
Haochuan Li, Ali Jadbahaie, and Alexander Rakhlin. Convergence of adam under relaxed assump- tions. arXiv preprint arXiv:2304. 2023a.
Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non-convex optimization under generalized smoothness. arXiv preprint 2rx.vv2306.01224, 2023b.
Junyi Li, Bin Gu, and Heng Huang. fully single loop algorithm for bilevel optimization without hessian inverse. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 7426-7434, 2022.
Bo Liu, Mao Ye, Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: A simple first-order approach. Advances in Neural Information Processing Systems, 35: 17248-17262, 2022a.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. Inter-
national Conferrence on Learning Representations, 2018
Mingrui Liu, Zhenxun Zhuang, Yunwen Lei, and Chunyang Liao. A communication dis- tributed gradient clipping algorithm for training deep neural networks. Advances in Neural Infor- mation Processing Systems, 35:26204-2622 262117, 2022b.
Risheng Liu, Pan Mu. Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order al- gorithmic framework for bi-level programming beyond lower-level singleton. In International Conference on Machine Learning (ICML), 2020.
Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A value-function-bart interior-point method for non-convex bi-level optimization. In International Conference on Ma- chine Learning (ICML), 2021a.
Risheng Liu, Yaohua Liu, Shangzhi Zeng, and Jin Zhang. Towards basdennttbbsedd bilevel optimiza- tion with non-convex followers and beyond. Advances Neural Information Processing Systems (NeurIPS), 34:8662-8611 b021b.
12

---

Published as a conference paper at ICLR 2024
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient- based hyperparameter optimiza- tion through reversible learning. In International Conference on Machine Learning (ICML), pp- 2113-2122 2015.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. Understanding the exploding gradient prob- lem. corr
(2012). arXiv preprint arXiv:/211.5663 2012.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pp. 1310-1318. PMLR, 2013.
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. International con- ference machine learning, pp. 737-746. PMLRR 2016.
Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning feature reuse? towards understanding the effectiveness of maml. arXiv preprint arXiv:1909.09157, 2019.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with im-
plicit gradients. Advances in neural information processing systems, 32, 2019.
Amirhossein Reisizadeh, Haochuan Li, Subhro Das, and Ali Jadbabaie. Variance-reduced clipping for non-convex optimization. arXiv preprint 2rXiv:2303.00888 2023.
Shoham Sabach and Shimrit Shtern. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640-660, 2017.
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back-propagee propagation for bilevel optimization. The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1723-1732. PMLR, 2019.
Han Shen and Tianyi Chen. On penalty- based bilevel gradient descent method. arXiv preprint 30X.0:2302.05185. 2023.
Daouda Sow, Kaiyi Ji, Ziwei Guan, and Yingbin Liang. A primal-dual approach to bilevel optimiza- tion with multiple inner minima. arXiv preprini arXiv:2203.0112 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- lion processing systems, 30, 2017.
Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng, Zhi-Ming Ma. Tic-Yan Liu, and Wei Chen. Provable adaptivity in adam. arXiv preprint arXiv:2208 0000000000.09000,, 2022.
Bohan Wang, Huishuai Zhang, Zhiming Ma, and Wei Chen. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions. In The Thirty Sixth Annual Conference on Learning Theory, pp. 161-190. PMLR, 2023.
Junjie Yang, Kaiyi Ji, and Yinghin Liang. Provably faster algorithms for bilevel optimization. Ad- vances in Neural Information Processing Systems, 34:13670-1368/ 2021.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 2020a.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. International Conference on Learning Repre- sentations, 2020b.
13

---

Published as a conference paper at ICLR 2024
Symbol
Description
Lm.0, L0.1
Relaxed smoothness constants for f with respect
Iy,u, Lyg.1
Relaxed smoothness constants for f with respect y
Ko, Ki
Relaxed smoothness constants for function &
M
Bound for V y (x, (x))
Cgay
Bound for V V v
L
Lipschitz constant for Vg(u)
Strong-convexity constant for with respect to y
Lipschitz constant for V (u)(u)
Lipschitz constant for (z
p
17. v
Step-sizes for updating æ, in BO-REE (i.e., Algorithm 1)
Y
Step-size for updating y in Updat (i.e., Algorithm 2)
8
Momentum parameter for in REP (i.e., Algorithm
Vo
Upper bound for g 30 0 (xo. yo) in Epoch-SGD (i.e., Algorithm Projection ball for s-th epoch Epoch-SGD (i.e., Algorithm 3)
B₂
T,
Number of iterations for s-th epoch in Epoch-SGD (i.e., Algorithm 3)
0g
Step-size for s-th epoch in Epoch-SCa SGD (i.c., Algorithm 3)
kt
Number of epochs for Epoch-SGD (i.e., Algorithm 3)
K
Number of iterations for updating æ in BO-REP (i.c., Algorithm 1)
N
Number of iterations for updating y in UpdateLower (i.c., Algorithm 2)
I
Update period for in UpdateLower (i.e., Algorithm 2)
R Radius of projection for UpdateLower (i.e., Algorithm 2)
Table 2: Description of Notations
A RELATED WORK
Bilevel Optimization Bilevel optimization used to model nested structure in the decision-making process (Bracken & McGill, 1973). Due to its broad applications in machine learning, there is a wave of studies on designing stochastic bilevel optimization algorithms for nonconvex smooth upper-level functions and strongly convex lower level functions. Ghadimi & Wang (2018) initiated the study of Bilevel Stochastic Approximation (BSA) method based on implicit gradient descent, and proved an O(E-5) complexity to e-stationary point. The complexity result was later improved by a series of studies under the framework of automatic implicit differentiation (AID) (Hong et al., 2023; Chen et al., 2022; Ji et al., 2021; Khanduri al., 2021; Chen et al., 2021; Dagréou et al., 2022: Guo et al., 2021: Yang et al., 2021; Chen et al., 2023b), which requires estimating Hessian inverse directly or approximating by Hessian vector products. Another class of algorithms fall into the category of iterative differentiation (ITD) (Maclaurin et al., 2015; Franceschi et al., 2017; Finn al., 2017: Franceschi et al., 2018; Shaban et al., 2019: Pedregosa, 2016; Li al., 2022; Yang al., 2021: Ji et al., 2021; Grazzi et al., 2023), which construct a computational graph of updating lower- level variables through gradient descent and compute the hypergradient via backpropagation. There are few works which use fully first-order methods to solve bilevel optimization problems (Liu et al., 2022a; Kwon et al., 2023a). There is a line of work designing algorithms in the case where the lower-level problem is not strongly convex and have multiple minima (Sabach & Shtern, 2017; Sow et al., 2022; Liu et al., 2020; 2021a;b; 2022a; Shen & Chen, 2023; Kwon et al., 2023b; Chen et al.. 2023a). However, all of these works need to assume the upper-level function is convex or has Lipschitz gradient and hence are not applicable to our bilevel optimization problem with an unbounded smooth upper-level function.
14

---

Published as a conference paper at ICLR 2024
Unbounded Smoothness Zhang et al. (2020b) proposed the relaxed smooth condition and analyzed gradient clippingnnommaizzttion under this condition. This analysis was further improved by the works of (Zhang al., 2020a; Jin et al., 2021). Crawshaw et al. (2022) considered coordinate-wist relaxed smooth condition and proved the convergence for the generalized signSGD method. Faw al. (2023); Wang al. (2023) studied Adagrad-type algorithms for relaxed smooth functions. Li et al. (2023a); Wang et al. (2022) analyzed the convergence of Adam under relaxed smooth assump- tions. Li al. (2023b) analyzed gradient-based methods under generalized smoothness condi- tion. Chen et al. (2023c) proposed a new notion of a-symmetric generalized smoothness and ama- lyzed normalized gradient descent algorithms. Reisizadeh al. (2023) considered variance-reduced gradient clipping when the function satisfies an averaged relaxed smooth condition. There is also line work focusing on federated optimization Crawshaw et al., 2023a;b). However all of these works only focus on single-level problems and cannot be applied to the bilevel optimization problem as considered our paper.
unbounded smooth functions (Liu et al., 2022b;
B PROPERTIES OF ASSUMPTION 1
B. DEFINITIONS OF RELAXED SMOOTHNESS
The standard relaxed smoothness assumption in Zhang et al. (2020b) is defined in Definition B.1. Definition B.1 (Zhang et al., 2020b, Definition 1)), A twice differentiable function f is L1)- smooth if V2 f())l S Lo + Li [.llff(()))
Definition B.2 is an alternative definition for the (Lo, Ls)ooshhmsnssss.. It is strictly weaker than Definition B. 1 because does not require the function f to twice differentiable.
Definition B.2 ((Zang al., 2020a, Remark 2.3)). differentiable function f is (Lo, Lm)-smooth if f - fu'')ll I (Lo + ( ||] - u' dl for any ||u u'll s 1/L1.
B.2 RELATIONSHIP BETWEEN ASSUMPTION AND STANDARD RELAXED SMOOTHNESS
The following lemma shows that our proposed (Lz,o. Lm, Ly.0: Ly can recover the standard re- laxed smoothness (e.g., Definition B.2) when the upper-level variable æ and the lower-level variable have the same smoothness constants.
Lemma B.3. When T. T.y,0 0 La/2 and T=n,1 Try,1 = L1/2, Assumption I implies that for any u, ui such that || u'll S 1/L,1, we have
Vuu((u) Vuf(u')l S (Lo + (llVvf(w\IDllu u'll-
(6)
In other words, (Im,, Im,, Iyy,0: Iy -soothhess assumption can recover the standard relaxed smoothness assumption.
Proof of Lemma B.3. When Lz,0 Lygo Lo/2 and Lx,1 Ly,1 L1/2, by Assumption I have for any u. u'
1
1
||ue u'll /2 (T22. 1.2,1)
L1
Moreover, we have
[Vuf(u) Vuf(u()l
+ 1 (Lo + V 2'12
$ Loo L L.ll
4
< (L3 +
-
< (To + L.IVV.J (u) ()))))))le ---u-ll u'll
which means that the function f is (Lo, -mmothh in terms of = (xx, 3) when Ln.0 = Ly.0 To/22 and T.n11 T L2/2.
17
15

---

Published as a conference paper at ICLR 2024
C TECHNICAL LEMMAS
In this section we provide some technical lemmas which are useful for our following proof. This section mainly provides useful properties of the considered bilevel problem under our assumptions.
Lemma C.I. The hypergradient ( takes the forms of
( Vaf(a, y (x)) + (
v "f
dæ
Vaf(a, y" (x)) V v Vaf(a, y" (x)) V Yaw
where 2² (a:) is the solution of the linear system:
z" (x) = V
(8)
Proof of Lemma C.I. Using the chain rule over the hypergradient (
af(x.y((=)) de
we have
(Φ(()= = Vel( y (x)) + 0y
V V (xx y (a:)).
By optimality condition of y" (xx), have V vog(#, y (a:) 0. Then taking implicit differentiation with respect to æ yields
(x) v2 "g = 0.
V V ug( y (x)) +
(10)
Ox
By Assumption 2. function g y) is p-strongly convex with respect to thus y non-singular. Plugging (10) into yields
(x))
(Φ(x)) (a y (a)) V V y)
(V, (11)
Also note that xx (z) takes the form
(a)) = V g yd (x))) Vv, " y
hence hypergradient (x) can also be represented as
(x) Vn y (æ)) V V v (x))) (x)))² (a)).
Lemma C.2. Suppose Assumption I and 2 hold. Then, we have
(a) y² (ι) is Caez (b) z² (x) is Lip-sihchhitz continous, ie.,
-ipschitz continous.
P
| [x'(x) z (2')ll 1 2'1l
( x 0'115
where Le-- is defined as
1
c2 (L2 +ig
1+
n
Ty = V1+
gon P
pM 212
(Iyyo + I
(12)
(c) Vaf(x, (x)) and (x))) satisfy the following:
(x))1 < [ + Cgry M
(13)
16

---

-Lppschitz continuous. For Published as a conference paper at ICLR 2024
Proof of Lemma C.2. By (10) in Lemma C.I, we have
dy" (a)
o (x))]
dæ
Now we proceed to prove the lemma.
(a). Note that by Assumption for any æ we have
(x)
C
V æ V y y (x)) (o y (x())]
dæ
Therefore, y yx)) is Can Lipschitz continuous.
(b). Let u = (z, yx) and u' (x', y² (x')), by condition (14) we have
2 - u'll = VII x'1 2 + (xx) y (xx')l
(i)
1+
|| x'1l s
222 + 12,1)
where (i) follows from (a) in Lemma C.2 that y (ar) Lipschitz. Hence the condition for applying Assumption is satisfied. By definition (8) of 2" (a:), for any n, xx we have
xx*(x) =- (x')l
= (a
V [
+ [
V
y"
< M
ff vuf(a' y
M V2r(( (r. (x))
(x)) Vig("' (*')))
+ (Ly L 1 v
2'12 1
y (2))
PM
VII - x:l 2 110) y-
(Iy.o + M) v || x (xx) y" (xx')1
2
pM
1 (Ly,0 + Ly, V|x - x'12 2 (x) ----8(()) 22')
+
122
pM
1
(Iyyo + M) / 11200 - 1011 + Cran
+
||:c x2/12
112
1
(Cerv)
(DM 122 + (Lyy, + lny. ||a0 - x'll
1+
where (i) follows from Assumption 1 and the fact that
- 11 IH, H2) < ||||| H2ll.
(if) follows from Assumption and (iit) uses the fact that y" (xx) is Ceez notation convenience, we define
P
L = W1+
(Cany 1
pM 42
+
-Ly, + Ly1ii)
to be the Lipschitz constant. Therefore, 2" 2x) is Tog- Lipschit continuous.
17

---

Published as a conference paper at ICLR 2024
(c). By Lemma C.I, we have
Dy
Ve - =
I (ax v (a:)
dæ
Ve Vyg(a, (2))lV y vvl( (x))
Cazu M
where (i) follows from Assumption Therefore, we have
Coay M
V vill S
Under the Assumption 1 and 2, we can show the following lemma that the function ((x) satisfies standard relaxed smoothness condition: (x) V II I (Kn + Kil V+(x'))] || x' with some Ko and K; if æ and æ' are not far away from each other. This is very important because
it allows to apply the descent lemma in the standard relaxed smoothness setting for analyzing the dynamics of our algorithm.
Lemma C.3. Suppose Assumption I and 2 hold. Then for any æ, x' such that
x 2'll
(14)
C2 (1+
2
(L2,1 + lg.1)
n²2
we have
[V v0(2')| S (Ko {2\\V((2')II) | x'1..
(15)
where Ko, K₃ are defined as
Cgaz
Cg., M Corz (Ly, Ly,1M) + M Con, P+ T/
Ko
V1 1-
Lix.0 Lox,1
+
122
Caaz
K1
1-
Lx.11
(16)
Proof of Lemma C.3. Let (x, y² (x)) and ut (x', " (x')), by condition (14) we have
lu u' |l = / || - x'1 + (x) y (2')
(i)
(Ceau
1
|| x'll 5
22112, + 12y1)
18

---

Published as a conference paper at ICLR 2024
where (i) follows from (a) in Lemma C.2 that (x) is Lipschitz. Hence the condition for applying Assumption is satisfied. Then we have
(+())) v
Va (a:) + (a)(a=)
V (= Val(z'. Oy
V
v
dx
Ox
By Var (a)) (x)) By 2yy(x²)
< V y' (x)) Vml( y (a')) (a)))]
Vy 20
dx
Ox
(x)) (x)
< v (1r, (x)) Vnl( y (a:) ))l
va (x)) Vul(a',
dx
+ Oyy (x)
0yy(2") V (a' ( (a')))
dx
Ox
V y (x)) Vaf(a' yy (z'))]1 + Cgay || ff Vv (x'))
M V. Va
(a:
V V Vgg
Casy | , fx
& |V>/ V
+M Ve
V Vug(z'
+ M V V y0
(x)))
V Vy
(a (
(I + Lx 1 V 2
22 y
+ Cun (Iyy I V
x
1y (2'))
p
TM
+
VIxx
V|xx- x212 -
(x) (x')]1
"
+ .M N*w ||[V ( (x) 11110 V Vzg(a' (x'))
(x)) Vzg(z' (x'",)"()')))
< (Tm,o + Tun, V / (ar, y (al) I)l / | x 12 1 yn (ar') 112
CoEN (Ly,0 + Ly M) ) M gryP
C
+ TH
v VII 2'1 + y (x) (x())12
1
122
(69)
Ogeu p
(Ly, + My + M Cguup TM
(Co. M ( + (1vo(("1))
v1+
+ Lamo + Lin,1
ysu
||0 x'll
12
11
11
(Ceev gaw ) LL + La,1 Coey M
Caux (Ly, + Ly,1M) M Caop+
= 11
L (
||00
x'1.
1
1
P
112
where (i) follows from (10), (ii) follows from Assumption 1, and the fact that
| - H1 |1 (HI))) S and (iii) follows from (a) in Lemma C.2 that y yax)) Lipschitz. Recall the definition of Kos K₃ in (16), therefore, the objective function ((z) is (Ko, Ks)-shoohh, i.c..
H2ll.
[V v < (Ko + K1 [[l[V | - x'Il
We now present a descent inequality for (Ko, Km)-shh functions which will be used our subsequent analysis. Lemma C.4 (Descent Inequality). Let to be (Ko. K₂ Km)-shooth. Then for any x, x E RRd such that
1
[ x'
C2 [
2
(L2,1 + 12,1)
a
19

---

Published as a conference paper at ICLR 2024
have
Ko K1 (()((())))
((x) ((x') (V x²) +
x xx113
where constants Ko and K₁ are defined in (16).
Proof of Lemma C.4. By Lemma C.3, for x: xe' such that
| æ'1l S
C2 2 11
(L2.1 + 1w.1)
x
have
[v V s (Ko + K1 (22(2 x'11. æ'1.
By definition above we have
((x) (xx') V x0)
(V2 +1 0)0² v x²) d0
1
IVD(6x (1-0)x²) v || - x' ||
- (Ko + [I 10( - x') e')ll || x' 1|d0
Ko [1]\V((=))] x'13.
Thus we conclude our proof by rearranging.
Next, we introduce simple algebraic lemma.
Lemma C.5 ((Zhang al., 2020a, Lemma B.1)). Let O, and u, IRd, then
(u, v)
w| (1 w)|| (1 + w)]l ull.
(17)
wlll
D PROOF OF LEMMAS IN SECTION 3.3
D.1 FILTRATIONS AND NOTATIONS
For convenience, we will restate a few concepts here. Let Fi denote the filtration of the random variables for updating my and Iy before iteration k. i.e.,
Fg = (So..... LA Co. CK-13
for k 1, where of-) denotes the o-algebra generated by the random variables. Let Fo denote the filtration of the random variables for updating lower-level variable starting at the s-th epoch before iteration 1, i.e.,
=
(000 20.0
201-11
for S T, and 0 S < kt -1 1. Let F% denote the filtration of the random variables for updating lower-level variable yt 2 1) before iteration 1, i.e..
F
.
20
for 1 st N and = -I, where و S 1 K and denotes the update period for yı. Let Fx denote the filtration of all random variables for updating lower-level variable (k 2 0). i.c..
K-1
)
Fx
= of
U ==0
U
T.
F
A=1
20

---

Published as a conference paper at ICLR 2024
D.2 PROOF OF LEMMA 3.2
In this section we first present one technical lemma which provides high probability bound for SGD. We follow the same technique and procedure as Theorem 1 in Lan (2012). just simplify the modified mirror descent SA algorithm to SGD. For completeness of proof and consistency of notations in our paper, we paraphrase Theorem Lan (2012) as the following lemma.
Lemma D.1. Consider the s-th epoch in Algorithm let D)2 be upper bound 2/2
160
yo
and assume that the fixed step-size as satisfies 0 < a S J. Apply T, iterations of the update starting from Yo s.9
1
y -1²+
a, Vy G(zo yo yot: (:: ))
arg min
(18)
2 BEB(1 vED)
where the stochastic gradient estimators V G( Vo (0-0)) satisfy Assumption 3. Then for any and T3 > O, we have
Pr g( 2o 2 - g( vτ) > Po(T,) + XP1 (T:)
S exx((~22/3) + Exp( -A),
(19)
where
Po(T,)= a,T,
D + 20² 9.1 TT)
(20)
PT(T.) = a,T,
22 O2 v To + 20 o
Proof of Lemma D.I. First, we have
(x0 Y0 111)
I a, g(00, '6 + Vug(zo, "0"),, vo s111
2.()
L
s.++1
8.1
27
yo
y00
2
5 0a
g yo 10 + V Veg vo yo 111
yo 2.2
+
1
y0
811+1
yo
0,0
Lots
Yo
s,1+1
y10 8.6
2
2
Sas
g yo ) + v Gy yo 50 yo
yo 8.t
}}
+
Yo
s11+1
Lots
y0
s.1+1
yo
2
2
a. (VyG(ao yo :6:::00 :):)) V Vag(ao. vo
r.t)
r1++1
yo"
I a, g( 4oth + G( f0th , 50 y0
9,111
y0 }}
+
1
yo
y0
2
+ a V, 2ot , (0 Vyg(wo (zo vo x1) >1
y6
ge+1
yu
g.t
La,
y0
9.0+1
y0
as
g f0 vo')) + Giro vot ") Vo" 3141 - yo*h
+
1
yo
+.0+1
yo
a.t
2
a² Gyoo 2oth 20d2 - V Vyg(wo yo 26:01 "11
2(1 Las)
(1)
5 as [g(0 voth) + (V, Gyyoo yo : (0 yo 2.141 y/;t
1
s.11
yo
2
+ a Go yo ; : Vug(zv. (uo(zv.0.")) }
(21)
where (i) follows from the inequality bu
au² 7
62 for any > 0, where we set
u = yo
++1
26
b b= a,
VyG(oo (0 Veg(zo. 26 0|| a= La
and (ii follows from as ZT.
21

---

Published as a conference paper at ICLR 2024
Also, we have
as 00(00.16 36" + (v G voth nt, "00"), Vo
,,1+1
v6ah)
y6
+
1
yo
8,++1
yo 0.2
2
())
S a 30 + [a. (V,G(zo: y6 :00 1) yo
y0
9.1
+
1
90
s,+1
2
+ as (V 36 : 5 v0 yo 1
1
yo
1.++1
y0
2.
1
||
-361
yo
1.t yo 11)
2
I as [g(20. yoth) + (V 7 F.. yo ) yo
yo
+ as
(Vo
30
V
Vug(
30
" ). yo
1 100" #. vōll
1+ vōl'
+2
y0
(1i)
1
a2 yo) + as
V yo elt
:000 200))
V vxlo yo ).00 yo
+ 2
yoll
y0
2
(22)
where (i) follows from
as v G(ao Yu" 50 ) vo yo
n.t 2edt
*1+1
yo
*1++
Yo 4,t
1
||
3/0
8,t
36
1|
3/0
st++1
yo
|
2
2
v # G(au. vo"
1. 20
:50
),,,. vo yo *1++1
1,1+1
yo
+ yo
yo" 5.1
2
+
1
5.6
vōll
3000
8. .++
yō
2
2
2
v v G(o,
Yd" 150
25.
) y0
yo
y6
yu" "1'
< yo
Vo.
yu
y0
2
2
1
+ 2
yo al
yo
yo
yu
1
02
V Gaao
yo
50
) y0
yo
a1+1
96
s1++1
y0
yo
8.111
Yo yo
yo
as
V G( Yd ). y0
yo
y0 s1+1
yd
yo
y6
yo s.
yo y6
Y0
20. y0 a. V G(au, yo
yo
yo
1.41
yū y0
11++
yn
= ~v6 +111 yn yo
V Go yo
:
yo
s.1+1
2 0,
and (ii) follows from (strong) convexity of g( y) with respect to y. Combing (21) and (22) yields
1 a.g(2a No. you s. a.g( yo) S 111ō* yo 2ō12
1 vūl + (16)))
(23)
2
where we define
(96) = 2 Gaoo : V uognno 26
(eapa//aaavviiiiiea (V,G(mo:v0 20 V
tas
Veg(wo. v0")) V
y0
Summing up (23) from = 0 to T, 1, we have
T--1
Os [g(00 yo ( g(00, 266
s Yb
5.0 vōl"
1
Yu
s.
TT T3(66)
T,-1
T -1
I|
yo
yōl
+
Te
s D2 +
m. (y6)
1=0
By (strong) convexity of g(æ, y) with respect to y, we have
1 T
T
g( yo 1-100 = g
Σ
g( yo ))
2o,
T,
T.
t=l
22

---

Published as a conference paper at ICLR 2024
which implies that
T. Σ as
20 vo+ - g( 2i) s DD2 +
Σ
ne (v6))
t=
==
Denote 1/2 == as v G 360
Vyg(2o, 31 ), yd yo and observing that
GaG(oo vo 36- :00 v Veg(w 16.0),y6"') 111
Te = 2/ + 2a
we then conclude that
Th
T,
Σ ax (0(20 yo v0 g(00, v6i)
1 DD2+
Σ 1=0
th + 20 VyG(xo, yo :60))
Veg(2n, vo 11?
(24)
Note that by Assumption we have Elubt Fo sequence. Moreover, yo yo s.t
0, thus fal is martingale-diffrrnnee
Vo - y/1"
5.0
5.0
+
yo 4.0
yo S 2v22, then we obtain
Vyg(ao, vo V V vo 16:05000
E exp
(2V2 3
Fe
$ E
exp
a²00 (2v2D)² 2
Fea
VyG(ev. vo 2000) Vyg(a 26 9 "//
S E
exp
Far
exp(1)
where (i) follows from Assumption By Lemma 2 in Lan al. (2012), for any X
we have
T
Pr
(2V22o
2V2Dog.
02
(25)
S exxp(~2233)
where the probability is taken over randomness in J..To Also, we have
a²
V. G( yn :60 - V Vgg(o yn 2.
1
T
0g11
1=0
V vo sit. 12
V Vug(20 26 "11²
1
<
a exp
T.a?
1=0
Then take expectations (with respect To on both sides and we get
T 1
a V G(oo 4o
Vag yot ))
(4)
T-
exp
Σ
o exp(1) S exp(1))
T,a302
T,o?
1=
where (i) follows from Assumption
Using Markov's inequality, for any À 2 0 we have
T
VyG(oo y0 5. ) - Vug(wo, yo 1 > (1 2oo2 20
Pr
< <exp(-A). (26)
1=0
23

---

Published as a conference paper at ICLR 2024
Combining (24), (25) and (26), and rearranging the terms, obtain
Pr
0
g (0 v60] > D2 ,. 2(1 + a
1=0
T
7,-1
Pr
D +
1/4
+
Σ
20
Vo 20 :660))
vo 26 96-1!'
(-0
1-0
D2 A (2VDoo..d.VT.
+ + 2)0
T-1
T,-1
Pr
Σ
Vi (2v (2V2Do
+r
Σ
a
Ga 1o (60)) vuglau, 0/ v6 > (1 1) 20
S + exp(->).
Note that Ee a₂ a.T', and recall the definition (20) of Po(T;) and PI())), by rearranging we finally conclude that for any À 2 O, we have
Pr gg(0 yo + g yn) > Po(I.) + API s exx(->2/33 + exp(-A).
In Lemma D.I, we got the high probability convergence results for SGD for one epoch. We now adopt shrinking ball technique with multiple epochs to improve the high probability bound com- pared with the one epoch result (Hazan Kale, 2014; Ghadimi & Lan, 201 The main difference in our setting is that we directly utilize SGD in each epoch and consider smooth and strongly convex functions (i.c., our lever-level problem). In contrast, Hazan & Kale (2014) considered a nonsmooth strongly convex function while Ghadimi & Lan (2013a) considered accelerated algorithm AC-SA for each epoch. This result is stated in Lemma 3.2.
For notation convenience, we define Vo as the upper bound for g(zo, 30 0.0) g( vo), i.e.
g( yo 000 g( 36) S Vo.
(27)
We also define the projection ball B, and set the number of iterations T, and the fixed step-size Os at s-th epoch in Alogorithm 3 as following:
Vo p2a S
B,
y E Rd
y yo
(28)
16T
32 max (0 g,1, 4
T,
max
9.1
(29)
pV02 (s+2)
μ
1
V02-
a, = min
(30)
2L
Jg.1
2
Lemma D.2 (Initialization Refinement, Lemma 3.2 restated). Given ô E (0. and é' > O, set parameter kt [log2(V//c)] where Vo is defined (27). If we run Algorithm 3 for kf epochs, with projection ball B., the number of iterations Ts and the fixed step-size ag at each epoch defined as (28), (29) and (30), where we set X to be
X = max (V
2k In
2k
3l
8
8
then with probability at least 1 6/2 over randomness
{ s=0
I j. we have
}.
8 Pr [g( yo) g(Eo, y² (æx)) > cl 2
(31)
Moreover, the total number of iterations performed by Algorithm 3 to find such solution bounded by ((T (E',)), 8)), where
[10 )= +
-g1 uc
2 2log (ogg(()/(c))
T((,5)) = max 1, log2
+
In
9.1
(32)
ue
24

---

Published as a conference paper at ICLR 2024
In particular, if set d' 222 (sx.)) then with probability least 6/2 over random-
ness in of { (this event is denoted as Eg), we have l/yo y²(x))) S e/8Ko in ① (o K// 2²2 iterations.
Proof of Lemma D.2. For any s 2 0, let V. Vo2 and denote the event A,
ga yo g( vo) I v.J. We first show that
Pr g( yo - g( yd) 2 Vs41 Ao}
S 2k-
(33)
By strong convexity of g(x, y) with respect to y. have
g(zo, yo = g(zo. 36)
V4
2 y0
yo
S
With this upper bound for y6 vol || under the event A., we can substitute V./p for D2 in (20) of Lemma D.I. Then we redefine Po(T.) and P1 (T,) as
V. + 20 20 a
Po(T.)
O,To
(34)
V. 2v2
PT(T.) a,T,
20 20
By Lemma D.I and definition (34) we have
Pr g( yo - g( vo) + xPI An] exxp(-A2/3) + exp(-A)) (35)
Define
2LV, 1 (4) 2LV,
V.
Vs+1
Ri (T,)
11 T, P 16L
8
4
(36)
20 V. 1
(6) 20 9.1
V. 4V02
(s+2)
V4+2V,
1++1
RT,
Tg
4
320
9.1
16
16
where both (z) and (ii) follow from (29).
Then conclude that
V2 1
Po(T.)
+ 20 20
pTa as
( V.
24
V02-
T.T
max
22, 22, 0g.1 V
V
+ 20
2TT.
2LV;
2V,
2V.
< max
LiTas -g9.1
+ 0g111
HT.
U.T
max
(RI (2)()s))
/ (2))TT)
Ve+1 + 4
Vs+1
V4+1
2
where (i) follows from (30) and (ii) follows from (36).
25

---

Published as a conference paper at ICLR 2024
Also, we have
V4
PT(T.)
2V20g,1
+ -2000 9.1 02
(1)
$ g0
V:
+ 20g.1 1/
Vo2-
I $2v20g.1
Vj
+ -20
Vs pTs
HT,
2uIo.
HT,
Va (1))
V.
11/22
gV V
S
3v/20 V
HT,
1
128A2
V,V++2
S <3v20g.1
128A209.1 g.1
3Ve+1
V++1
82
2
where (i) follows from (30) and (ii) follows from (29). Therefore, we have
Po(T.) XPI S Ve+1.
which implies that
Pr g( yo 160) g( vō) > Vs+1 Ag S (Zo: yo 1.0) - ((20033)) P (P. AA.
(6)
- exp( (xp(->2/3) exp(->)
(ii
5
2kt
(37)
where (i) follows from (35) and in (ii) we set
2k
2k
A = max
3/3
In
(38)
so that exp(->2/3) + exp(-A) < 8/2kt.
Next, we proceed to show that for any given ó (0, 1) and é' have
Pr g(z0, yo kt (t)) g vo) c
8
(39)
2
Let event A, be the complement of event A.. Obviously have Pr [Ao] and thus Pr [Aoo] 0. It can also be easily seen that
Pr g(
To.
Vo
1100
g g( 96) Va+1
[g(0o Vi
1100 g( yo) Vs+1 AA, Pr[A.] + Pr [0(x00.00110) vo v0. g(wo, v6) Vo+i 1 Pr [Aa)
Pr
Pr
g( yū
+++10) g( yo)= > Ve+1 A,
+ Pr [Ae]
8
2hf Pr [ yo
_ g zo. vo) > Vj]
where (i) follows from (37).
Summing up both sides of the above inequality from s = 0 kt 11, we obtain
Pr (o yo #t .0 g( v6) o'] Pr [x yo kt.0) g( v6) e] - Pr [Ao]
b1
=
Σ
{
Pr g (oo yo
yo 1.0) g(20. vτ6 > Vetal Pr [o( yo )00 g(zo. bo) > Vo
==0
8
8
<
bス
2k
2"
26

---

Published as a conference paper at ICLR 2024
Therefore, conclude
Pr (To, yo) - ( yd) > c'] (
Pr g( yo k0' g( yo) > >
2
where (i) follows by recalling line 1 in Algorithm 1 and line 11 in Algorithm 3, i... yo yo k'.0 the output of Algorithm 3.
is
Moreover, the total number of iterations can be bounded by
A
Σ
Tx
S
---1
Σ
16L
max 10 42
2.1
+ +1)
2V/22(0+22)
1
4=0
==0
< kt
16I
+1
+
32 max { {o2 g.1 4X2
9.1
k--1
Σ
2
1Vo
(40)
==0
ktt
119L
+1
32 max { {0 12.4420g
02
261
1
Vo
16L
256(4X2 + 1)0 +
loga
+
+
ue'
Using the above conclusion, the fact that Aet [log((V//e") the observation that A = (In(kt /6)). we conclude that the total number of iterations for Algorithm 3 is bounded by O(T(c', (0),, where
L T(d' = max 1,,0
)22))
Vo (
2.11 ucc
2 (2 (Vo/ee)
]
g.
+
In
(41)
uee
Specifically, for any given e > 0, if we need |1:0 y² (xo))
S
holds with probability at least 8Kg
1 - 6/2, then by strong convexity of g( y) with respect to y. we have to set é' = 8Ko
and
thus by (40) we need run Algorithm for at most
[ogg
V2 2
16L + +1) +
256 x 128K3(4X² + 1)0
+1
(42)
1222
iterations in total, where
2kt 31n
2k
A max
In
8
8
(43)
2
logz
12 juc
2
log,
128V K3 nie
max
3
In
5
Therefore, the total number of iterations performed by Algorithm 3 is at most δ (a g. K3/1222 iterations in total.
D.3 PROOF OF LEMMA 3.3
The following lemma follows the same technique in Lemma D.1, which can be regarded as high probability guarantee for one epoch SGD.
Lemma D.3 (Periodic Updates, Lemma 3.3 restated), Given d e (0, 1) and 0, choose R 4No Under Eo, for any 2s such that To = 3g and |
Txll = 1), where 1j S SKoICasp if we run K I k= and the fixed step-size ? satisfies
Algorithm 2 with input { and generate outputs (ğx
4e2
(44)
27

---

Published as a conference paper at ICLR 2024
and the number of iterations N for update in each period satisfies
64 9.1
Kg (A + VX + 1)²
vx+1)
N
(45)
12222
where we set X to be
2K In
2K
X max
31m
(46)
81
61
6/2 over randomness in {UK F% } (this event is denoted as
then with probability least
E1,, we have (3xx Tvll I e/4Ko for any 2 in O (o (A + vx+1) /In²(²
iterations.
Proof of Lemma D.3. We denote Dt = y (Txx) for simplicity. By Lemma 3.2, under event & we
have 13/0
Voll S 8ko Suppose S k S 1, then we have
1
Dill = 130
Dill S 10
36
+ 16
Vill
k-1 Σ
(4)
s 8Ko
1
Vi+1ll
Σ
9ay
x
(+1
8Kg
1
(47)
1=0
IC
(8)
n S
8Ko
4Ko
where (i) follows from (a) in Lemma C.2 and (ii) follows from S
8KalCszy
Now we proceed to update ÿ& (with T y at k-th iteration, where k = I. Following the same technique and proof as Lemma D.1, and note that 4Ko
2 is an upper bound for 1 flür ū7
then for lo I and any À 0 we have
Pr ( 1k+1) g( xR) Po(N) + (P exp(-X2/3) exp(-A),
2
where y
Σ y (see line Algorithm 2). Also, by substituting 1 Iko
for 1 in
definition (20) of Lemma D.I, we redefine Po(N) and Pi Pi(N)
Po(N) = 1
E
2
+
20 22.172
?N
2
4Kg
(48)
PI(N) = 7N
2
6
V + 202 22.
2
(KK/
Set such that exp(->2/3) + exp( -X) S
61 2K
then
A = max (Valn
2K
2K
In
8T
8T
Thus under event Eo, with probability at least 1
51 2
over randomness in F.N we have
g ( 1 ) - g (Tts Dtt < Po(N) + (P)
2
222272N
20
1
2
1
J + 20 20
N
2
4Kg
?N
2
4Ko
(49)
2
+ 202
9.1 + E0g.1
+ 20 27
32yK3N
2KoVN
2
Xeog.11
<
K
+ 20
2.1
(1 + 1)7 +
2K.VN
28

---

Published as a conference paper at ICLR 2024
If we choose
64 9.1 Kg (A+ VA vA+I) +1)
7 80 KovA IvN
N
11222
(50)
Then N = 1 kg/ and we have
g Dk+1) - g(02. D1. - c0.1V++1 Cog.A
2KovN N
2KovN
9. (A + VX+1)
2KovN
8Kg
By strong convexity g(x, y) with respect to y. we obtain
/
Wk+1
Vtll2 S g ūx+1) ga Uk S 2 8Kg
11
(51)
2
which implies
Ø l S 8Ko
for h: I. Thus for any A such that + 1 S k S 21, we have
1k
Dh
11
ykl || - 18r+1 771
+
Dell
c
+
h-
1 Vi+all
+
Σ
Corz
[ ē.41
8K
8K0
i=1
i=
ICaxz 17
(52)
8K0
4Ko
where (i) follows from (a) in Lemma C.2 and (ii) follows from v) 8KalC
In general, for k jí where j s [ we update ÿs by Algorithm 2. Under event Eg, with probability at least 1 1ál 2K
we have | Till
S 3Ko in at most
64202 g.1 K2
(*+
=
122
iterations, i.c., O (0² K3
10 (A ( V /12²2 iterations. Also, by repeatedly applying (49) +
(50) + (51) or (52) for all 1: 2 1 and using union bound, under event Eo we have l D S 4/o with probability at least 6/2 for any le 2 1. Moreover, we need to run Algorithm 2 for at most
K
KN N
64 9.1 KJ (A V\+1)²
(53)
11222
iterations in total, where
2K
2K
A = max
|3ln
In
(54)
81
8I
Therefore, the total number of iterations performed Ko 0. K3 (A + VX+T)² /T1262).
by Algorithm is at most
D.4 PROOF OF LEMMA 3.4
Lemma D.4 (Error Control for the Lower-level Problem, Lemma 3.4 restated). Under event Eo Ei we have Ily" (Øx) Tall I c/4Ko for any k 2 0 and Pr(E) 2 1 - 8 and the probability is taken over randomness in Fk.
29

---

Published as a conference paper at ICLR 2024
Proof of Lemma D.4. By Lemma 3.2 and 3.3, under event & Eg N&1, we have (zy( Uk ll 1
e/8Kg for = O and | (*x) Ukl I </4Ko for any k 2 1. Therefore, under event we have Ily (mx) yv l| I e/ n for any 0. Moreover, we have
Pr(E) Pr(Eo 6 = Pr(Eo U&) 2 1 (Pr(En) + Pr(E1) 21
2 2 = 1 8,
where the probability is taken over randomness in Fk. Thus we conclude our proof.
D.5 AUXILIARY LEMMAS
In the next lemma, the goal is to bound accumulated expected error of || zill. which is similar Lemma B.6 in Chen et al. (2023b).
Lemma D.5. Suppose Assumptions 1, 2 and 3 hold. Ie choose v S min
4pc 1603, ) then under
1
event E, we have
A..0
5K
p2
2
Bill
2t1?
+
+ (Ty,0 + Tyy...7
112
112
4Ko
k=
(55)
2
2M²
+ 07,11 ) u+
4L2. n?
K
0.2
4
422
112 v2
where we define Az.0 == 1|=0-
=il1 and the expectation is taken over all randomness in Fg.
Proof of Lemma D.5. First, we have
2
(1)
I
v/
||
[+ 3
||
=ī|l
3
(56)
(i
1 +
Uy
3 || - 2x11 + (1+ IZ--7"
v/4
where (i) follows from Young's inequality and (ti) follows from (b) Lemma C.2 that 2" (xx) is L Lipsccicc Then decompose 2k+1 2 follows,
2k+1 2 = zíz - = yr:Ek)22 V Fark, Uri Cx)) = Zi: v/ (2 (2t, zz Vzf(xx yı)) 2 GV (e:
yos Ex) - (2 yz)) 21
+ (x yni (e) Vyf( y+))
30

---

Published as a conference paper at ICLR 2024
Take conditional expectation on Fk and we have
E f|||| Ex+1 - =i|l"]
||| - VVzg(a y=) Vyl(az (()))))))))) =ill + 00 =x11 1 02
|I(I- vV (zx yr)) (2) zi) - - (V , Vuf(ozn, yx))l*
2v (112 zil² || + ~2 03
(8)
K (1 + M/
]|([ /V B) 2 2 + 2n 20²02.2 21 ==ill + || + +0og
2
2
+ (1 + mp
|| [ ( (. - V2 yz + Vyl(Ex, (() - V..((ER,,..))
S + 2 (11 - 2/22² 2 2v 02.2) 1| =111 + 2/ -2 || +1 + +00021
"
+ +122(1 + 2 V /g y.) - Vig(æn y | 2 + V f vı) V. (1x,
$ ((1 + / (1 - ) 2 + 2v 2222) 12x = + 20 02 = + 2² 2207,
+ (20² + 4" _ (p |1 + (Iy,0 + +,y,1 M) yk - vEll
I ((1 + nM (1 upn)² 2 2222)22 (1x zi12 + 2M²
1²² 02 + +7
2
(2w² 4u
1v )r 0² M12
122 + (Ly + 1y yil
(H())
(1 1 ||zE 2 + (
2M²
2² 02 + 07 + (2v² + 1w )( 0 M22
+ (Ly, + 2y yēll
3
x²
(57)
where (i) follows from Assumption 3 and the fact that stochastic estimators are unbiased, (it) fol-
lows from Young's 's inequality and the definition of linear system solution 2 i.e., Vzg( D²)=
V v (ase, vk). Inequality (dii) holds since we choose v S min( 44 1607.
and thus we have
(1 + vp
2 (1 - u2) + +22002
9.2 = 1
z²
3
+
-1
1
112 + +2 2020222
(
S 1
3
1
1 +
mM
2
2
2
32
8
43
= 1
vp
S vp vp.
32
where (1) follows from 2²212 < 1/16 and va 9.2
S n/16. Plug the inequality (57) into (56), then take conditional expectation on F2 for both sides of (56) and we obtain
Ex kk41 - 11
< (1 + m/
Ex
1 + (1
3 12..12
3
< (1 + vi [[[ 4UH ||ا = + (2v² + 4v
e2M²²
)
)
+ (Ly,0 + 13,1 y
3
112
+ (1 + / )(
2M
2
+ ,2,1)²²² + (1 + 1p
3
122,12
3
11 9.2
(1-14))lzz - 2 + 2v 4
4v + 10v²
2
M²2
+
+ (Ly,0 + Ly - will
3
/
3
112
2M²
+ (1 +
112 9.2 + 0 11,))²²
+ +(+
3
5v M²
+ (Ly,0 + Ly, 12) + 2
2M² 2(
4 L2. 12 12
x (1 - 1111))1zz - 2 +
42 0, + , of,))²² +
P n22
1/11
(1 (1-1)))1= - 2
5v M2
+ (Iy, + Iy, M)²) و 12 2(
222
0 + f )²
4 122 12g.0?
P 2
4Ko
112
31

---

Published as a conference paper at ICLR 2024
where (i) follows by - 4y
and (it) follows from Lemma 3.4. Take expectation with respect to
F& and have
B E =x|1 = Bx [& z 1|
k-1
5y
p 1²
+ (Ly, + Ly, 12,11 (
$ (1-1u) = + Σ
(1 01
4
1=0
2M 112 02 + 07.1
4
+ 2
1²+
12
L 1
n
Take summation on both sides and we finally conclude
= 2111
<
K-1
Σ
(1 - u1u)"1220 =5112 Σ
K-1k-
Σ
5v
(DM²
(Ly + km.
(11)) 2
4Ko )²
122
km0
k=0 i=0
2M
4
+ 2
12 9,2
+
+
f,1
v² + vp
12
1
1
K-1
5v
M²
(Ly,0 + 1x21
<
|00 zill?
1/u
vu
1
112
4Ko
k=0
+ 2
2
922
+o.1
2²
+
4
L2
12
112
(0) Az,0
5
p²
(Ly,0 ky)
2 2M
+ t0,11/ )
4L2. n?
+ K
+
022
V
vp
122
n12
4Ko
422 12a
where (i) follows from the definition of =0 2il1?
For simplicity, we denote hypergradient estimator as the following:
( yks, zui Sk. Ex) = Fx yki (k) V Vy yes )x)
(58)
In the following lemma, we bound the variance the hypergradient estimator.
Lemma D.6. Suppose Assumptions 1, 2 and 3 hold. Then under event E, we have
2M
((r,, yks zxi Sk. Ex) - E& (< yk, 2k3 So. M S so/1 +
42 9.2 + 20 211 - 21
(59)
where the expectation is taken over all randomness in Fk.
Proof of Lemma D.6. We first decompose ( yk, Zui CR. Ex) - EA (Z Uk. FM: Ca. Ex)) as follows,
V a yk. mxi Ck. Ex) Eg Ea (o yks zsi Ex.
V Fx Mii (+) V. V( yzg Eu =x]] /V [ yn) - V V V Uk)
= f yui (k) V (x yv)l - V v G, Eui - V v Vug(an, 3x)]
Take conditional expectation on Fs and we have
E, (2) yks zki Sc. (+) E, V (I Uk ZA: CA. Ex)
@ Ex V /gP(<k yki (k) V (x 3k
GriE) V V Vog((E (1)0 11
< o + - 1|
<o + 20 9.2 || žい - 2 + 20 20 11
< <of + 2M
122 0.2 + 20 202 1| =1
(60)
32

---

Published as a conference paper at ICLR 2024
where (i) follows from Assumption that stochastic estimators unbiased and Êk. Sk are mutually independent. Take expectation with respect to Fk on both sides of (60), and then we have
E|ll ( yk Zu: Ck. Ex) E& 2 ( yks Zni Ck. Ex]]11
EF [Ex V (2 Ur z Sh: Cx) Ex (V UR. Sa, Ex Ex]]
(61)
S <oy + 2M
122 g.2 + 20 2 =1117]1
D.6 PROOF OF LEMMA 3.5
Lemma D.7 (Bias of the Hypergradient Estimator, Lemma 3.5 restated). Suppose Assumptions 1, 2 and 3 hold. Then under event E, we have
Ba (xx you zxi Ex)] - v((xx)
Isa,16 || + LIx + Lan,1
Can M
TM ' + +C 2/ +
(62)
s
4Kg
P
4Ko
Proof of Lemma D.7. We first decompose E& (ax yks zui CRs Ex]] VD(())) as follows,
Eg (a yk: zx: Sk. [x]] v
= E& V Flrk. Cx) V Ge: -
(V.z/(aa yk) V
y())
V. V (1) zt) (V V..VVygee (akk yz) - V V (eg vti) zi.
Then we obtain
Eg V (2 Uke Zui
Fui So. Ex) v
[I(V (xX,, 4k) Vnn vil) Va Vegaea yx)(2z 2 (v Vog(as, 9k) V v Vug(EE, vii) 2
(Lm,o + Lmn,1 Vn. Il) 1 vill
C. 1| 2xll + Tlly y |
Le.0 + La,1
Cgny M
+ [[V
11
-illl + Co.yl || - = + TM
|1y - yi
Cgny M
TM
< Le,1113k - 1 + Le, + La,1
+
|lyk
will + Cgay ||
zill
H
(11) Lin
CaeM M
TM
Tin,0 + Ten,1
Cg., | 2 =
4Ko
4Kg
where (i) follows from Assumption 1, (ii) follows from (c) in Lemma C.2 and (ivi) follows from Lemma 3.4.
D.7 PROOF OF LEMMA 3.6
Lemma D.8 (Expected Error of the Moving-Average Hypergradient Estimator, Lemma 3.6 restated).
Suppose Assumptions 1, and 3 hold. Define ò, = m ( to he the moving-averit estimation error. Then under event E, we have
K
S Erri + Errz,
(63)
33

---

Published as a conference paper at ICLR 2024
where the expectation is taken over randomness in Fk, and Erri, Errz defined as
Erri
16
K-
[+((x))1
+
[L..0 + La,1
Cosy M
TM
E
Cozy
VK
R-1
Σ
Ell
=111
4Ko
1
p
4K0
k=0
2M
k-1
Errz
K KVI B
oj
22 g2 BVK
Σ
Elllz =2
x²a
R=D
Ki King
KoKng
8
[+b(=))]
+
B k=0
1 3
1 B
(64)
Proof of Lemma D.8. First denote
6% == m=+1 (xxk), 8 == V yk, #Ki So. Ex) (z)))))) S(a, -
We can upper bound (a, b) using the definition of (Ko; K1) ( -mmothhnsss
S(a. b) S (Ko + K1 (l)a))) || 10-b) bll-
(65)
By definition of my and S(a, b), we can get recursive formula on dg.
8141 mx++ (2(+++1)
Bmi+1 (1
(mi++ - v (V4 (60 + (1 - () Uk+1, Zk4 (441, (
-35g (35( 1 3)
(66)
Apply (66) recursively and we obtain
5% = = 3k-1- S(2, x.+1) + +(1 (1- B)
Σ
gk-1-18 8,41
1=0
A-
k-1
gh (m1 ()(()))) 3
Σ
1a-11-i((z;)) 11+1) +1
8k-1-18 8
1=0
k-
k-1
= 3h (smo + (1- (11-3)22 -) (
xo you 20i Co. - vQ(20) 8
((11,,111) + +11 3)
Σ
gk-1 1-1 1
8
1=
==
k-1
=ggh| (mo v (1 3)30 + Σ
gh-1-
S(2, x441) (1 B) Σ
gh 1 8:41
i=0
k-1
ggt+1 (ma V)((x))
Σ
S(2,, + (1 -3)
gk 8
Using triangle inequality and plugging (65) into the above inequality, we have
k + Bn
k-1
| s (1 3)
Σ
gh
6,
Σ
g 1 1-i (Ko + K₁ v+(x:))) + Bhh+1 Imo - V
1=0
34

---

Published as a conference paper at ICLR 2024
Take summation and we obtain
K-1
K-1
KgKng
Kin K
8
Σ ||6x| <1 8)
Σ 3h 8,
+
[ || +
1-3 ||mo v2((x)) ||
8
3
K-1
A
KnKnB
Kin3 K-1 1
$ (1 - (3
Σ
Σ
8
gk-s
( Vi, (t)
E. V 1 (2; yi, 21 2. Eo))
+
+
V
1- 3
1
8
k=0
k=
(a)
(1 B)
K-1
8h
E.
\ ( Uo 26,
vo(ar))
8
|mm V
1 $
(b)
(67)
Taking expectation (with respect to Fx) on both sides of part (a), we have
K 1
k
(1 3)
E
Σ 1=0
gh-i
(v Ui, C.)) - V ye z, zz: Se 6.1l Ge.
k=
(
K-1
k
S
(1 9)
E2
Σ go
(5 yi, y, S. E.) - EE, (. Ui 24 23 So (+))
i=0
K-1
3)
Σ B2(K- 1) E
p Di, 26, E,, (a yis 25 E,,
(M)
K
2M
B)
Σ
Σ (2(k-1)
0/, +
0g.2
+ 20
20 2;11s]
112
(10) (1 3)
K-1
2M
K-1
Σ (2(k-1) i)
of +
112 0/22 9.2
+ (1 B)
20
Σ
(2(k-1)B|112 - 2111
9.2 1=0
(1)
K 1 3
07, + 222
K-1 k
12 0.2 v20 -9)VK
2)(--0)(1 1|
VI+ + 3
K v1 11-1 3
2M
B VK
17,1 122 022 + 20
Bl|ez (
V1+ 3V
VI+
2M2 0/
K 3 /V07,1
122 0g + 22 BVK
Σ El| 2]]12],
(68)
where (i) follows from Jensen's inequality; (ii) follows from Lemma D.9; (Ri0) follows from
Lemma D.6; (ic) follows from the fact that Va + < vo + vT for all > 0. 6 > 0: (v) fol-
lows from the fact that Σn Vap S Vn as for all a; 0.
35

---

Published as a conference paper at ICLR 2024
Taking expectation (with respect Fx) on both sides of part (b), we have
K
K-1
k
(1 - 3)
E
8k-1
( yi, Gc, -
-
t=0
(
K
1c
Cgn M
TM
$ (1 B)
g
E [+ + (1 3)
gk-i
[La, La,1
+
4Kg
p
4Ko
k=
i=
k= i=0
K
+ (1 - 3)
Coan B [|| =
k=0
1
K-1
Bl|l (2x)))))) + K (La.0 + Lao1
Cs., .M
TM
5
+
4Ko
11
p
4Ko
k==
+ (1 g3
B E || -x
k=
(c)
(69)
where (i) follows from Lemma 3.5.
For part (c), we have
K- k
(6)
K-1 k
(1 - C-
Σ
Σ
gh
1|
2xll S (1 3)C
F|llzx
gay
k=0 0=
k=0
1=0
K
S Cgav
Blllz 2E
Caav
K
=]]
(70)
where (i) follows from Jensen's 's inequality and viy E as for all a; 0.
(ii) follows from the fact that E /as
S
Therefore, combining (67), (68), (69) and (70) yields
K-1
E
< - 3)
Σ
E
g
(., Di, 26, F. [. Ui 26 So 6.l1)
KgKng
K m
K-1
8
+
+
Σ
[ +
|lmo - v2(20))1
1 - 3
B
1-3
k=
K-1
+ (1 (1-8) 3)
Σ
E
3
Gi) (1 -
Vi,
k=0
i=0
2M2
K
S K <KVI- 1 3
07 +
07,
o22 + 220, BVK
Σ
EI[l mx =1
112
+ Tim,1e K-1
Cony M
TM
KoKn3
[+ + K [Im,0 + Loa,1
+
4Kg
4Kg
1 1-8 B
K-1
El|| =]|1=]+ + Kin3 R-1
B
+ Caey VK
+
mmo v
1 k=0
1- 8
A=
(71)
36

---

Published as a conference paper at ICLR 2024
Lemma D.9. We have the following fact
E
Σ g
( (1 Dis
(ea.))--E((ee (1 2,: Gis
(72)
32 E P0C ye S.) E, (2,, Ya 21 Se. E.)l
where the expectation is taken over the randomness in FR.
Proof of Lemma D.9. We will show (72) by using conditional expectation, the law of total expec- tation and recursion.
B
gh
Mo, E.
27
Byx
Ek
Σ
gk-i
( 2. E, (. 2si So Ei)l
1=0
(it)
Ex
go
(Q yks Zai Cx,
Ex (a yks NNi CR. Exl]]
(a)
Σ gh-i (70(2,,1, - E, D Ui z2 Sc.
+
(b)
(10)
32x0E V kk yks zki SK. Ex) - E& uk. Zki 24
Σ gh- (f
+ E
7 32(k-1)B
Vi, zz 25 Gi, 6.)
E. (ax ye, 21 G.))
Ex-1 Σ gh (F2 2R - zu Se. St.
E EF
(30)
g2(k 1)
( Uis 26 S.
E, (.
2-2
+ E
Σ gh- ( Uo.
E, (a, 2s: So. Ex)
2(k k-
E
bax v. z1 E.) E, E. v. z, C. E.ll
1=0
where (i) follows from the law of total expectation; (it) follows from the fact that part (b) is Fi- measurable and uncorrelated with part (a); (izi) follows from the law of total expectation; (iv) follows from the same procedures as (it) and (fi)); (u) follows from recursion and then proof is completed.
37

---

Published as a conference paper at ICLR 2024
E PROOF OF THEOREM 3.1
Before proving Theorem 3.1, we require the following lemma to characterize the function value decrease from iteration & iteration k + which is similar to Lemma C.6 in Jin et al. (2021).
Lemma E.1. For Algorithm 1, define og m,+11 (+(()) to be the the moving-average esti- mation error. Then we have
Φ(x++1) ((xx)) S - (1
1 _Kin ) 2
1 Kon + 2n/|oxl1-
(73)
Further, by telescope sum have
(1-2Kin) Kin
K-1
Σ [+
S
A
1
KoKn + |
(74)
1)
k=
where = ((200) - 4h and 4- inf we ((x).
Proof of Lemma E.I. For Algorithm we have || 2nll = 17, and by Lemma C.4 we obtain
((xx+1) - +(xx)) < m (V m "" (Ko k=l\V((=>)ll)
1 ~" (Ko + Ki [V\(aal)
( (1 + 2|16xl1) I1) +
1 Kin")
1
|v0(==)] + Kon² + 2n|16all
17 2
where (i) follows from Lemma C.5 with w =
With Lemma 3.6 and Lemma E. now we proceed to prove Theorem 3.1.
Theorem E.2 (Theorem 3.1 restated). Suppose Assumptions 2 and 3 hold. Run Algo- rithm for K iterations and let {2x) be the sequence produced by Algorithm For S
min
Ko Ki
22
2012 1
2.2
and given d (0,1), 1), if we choose a, as (30), Y as (44), N as (45),
min
Day
Kg
and
2
u²
Ca.
4²
2).
1
o Kō
1 - = min
min
1,
== (1 8), I
07.1 + 4² 02.2
32C2
Bzy
8o? 0.2
1602 9.2
4
P
162
17 =
g
min
Ki Ko'
[
Cg., Az, (1-3).
eA
ue 8Ko
C2
2
1+
(I2g + 12
(75)
where == (xx)) - int (xx) and Az,0 = 1120 25112 then with probability at least
1 8 over the randomness in FK. Algorithum 1 guarantees 1/2 "EK BVVV(() I 30c long
as K mp' where the expectation taken over the randomness in Fg. In addition, the number of oracle calls for updating lower-level variable y (in Algorithm and Algorithm 3) is at most δ 7/c
Proof of Theorem E.2. Taking total expectations (with respect to FK) both sides of (74) in Lemma E. we obtain
1 - 2
1 K1n
K-1
Σ
E
<
A + Kn + 2E
K
Σ
|
k=o
38

---

Published as a conference paper at ICLR 2024
Now plug (63) and (64) of Lemma 3.6 into the above inequality, rearrange and we have
1
1
2/3
La
1
K-1
K1T)
Bl
2
1-
1
2kg
K
k=0
2M
KonB
1
(Lae + L Cazy M
TM
I 2
v1 B
07 +
4² 9.2
+
1 -
B
+
4
Kom +
+
4Kg
①
K
23
+
+0
Bil
mk
x +
mmo - V
+
K
K(1 3)
K
k=
(I)
(76)
If we choose
S min
Ko
" + x²a 5.2
1-8 min
e²
min
1,
n²²
C²
Dzy
P
Ki¹
min
1, 320 asy
22
07.1 +
2M
n22
0
9.2
32C? 9ky
800
160 g.2
Ch Az.0 ) (1 (1- 9),
pe 8Kul Cayy
1
min
Ki Ko'
2 x²
2 1+
(L2, 12y1)
4A
(1 - 8),
mg = 0,
1
T/C
where A 4(xx) x* and Az,0 = ||2u 26.1 then for left-hand side of (76) we have
2B
Imm.1e
(1)
1 1
K16
2K
1 (77)
K1n
1
Kin
1- 3
2Kg
2(1 - B)
2Kg
3
where (i) follows from Lm, < Ki by definition (16) of KI.
For the first part (I) of right-hand side of (76) we have
(0)
2M2
cB(1 (81-8) 8)
c1 ((1-8) cKo
(1) 2
0 +
2M
n²
9.2
111
+
42
2
9.2
8(1 - B)
4Kg
(78)
1
45
2 2 c+
8
c +
32
+
4
4
6
16
C,
where (i) follows from the fact that (recall definition (16) of Ko)
2
(Lww + Laa Cge, TM
1 - -3
(1-3),
+
$ Ko-
2
2 4
8Ko
f.1
9.2
39

---

Published as a conference paper at ICLR 2024
Also, for the second part (II) of right- haatt-haddaee side of (76) have
(i)
C² Jay
K-1
28
A
(II) S 2
2V 20
9.2 9.21
+ 2Cazu
Σ
Elll
[
+
80
K
K(1 - B)
Kn
9.2
(18)
1
6C 9FM
Bl| =1|1
16
4
k=0
$ 6C 9my
5
p2M²2
+ (Ly + My
E
Kup
112
122
4Kg
2
2M
4I. 1721 1²2
5
+ 00,1
+
11
122
v2
16
(88)
C2
Az,0
502
(i²2²
2
6
Bay
(Iy. My
K(1
B)
112
16K
202 9zy
2M
402 12
ui=²
5 16
0g2
+ 0j,1
(1 (1-3) +
Dzy *"
112
122
12
64K3
Gan MEA 2,0
5Kie2
Kie²
+ 5
2 +
41(1 (3)
16K3
16
16Kg
16
6
C2 Bay x,0
7
2
+
6
4A(1 - -3)
16
16
1
7
6/ 32
2 +
2
+
16
16
5
3v2
+
16
(79)
where (i) follows from 1 3- < C² and m 0; (ii) follows from K 4A
and 17
80
(iit) follows from 17 S 8Kg and y 1-8, (iv) follows from K definition (16) of Ko and definition (12) of bz-)
<(1-9)
4A
and the fact that (recall
me
5C?
(DMM²² + (Iyy. + M2) S 5K3;
2
Cb,y S Kg. 1-B5
n22
112
07,1
2M 2
n²
0
32C
9xy
and (v) follows from 17 S 80 Ax, (1 B). Therefore, combining (76), (77), (78) and (79) yields
45 16e
5 16 c) 3v2++
(xx)) s
$ 30c.
K
Next, we give more details about update period 7, step-size y, step-size ag for 0 S S k based on the chosen parameters above, and then we compute the total number of oracle calls for Algorithm 2 and Algorithm 3.
a2 K3
Step-size and number of oracle calls for Algorithm 2. If we choose update period / in Algorithm 2, then by (44), need to set step-size to be
4E2
(80)
512K302
9.1 VVI
(>1 + VVI+11)
and by (53), (54) and Lemma 3.3, together with K =
1A
we need at most
K64 9.1 K3 (>1 + V 2
128 (11 + VA +1)
(81)
In222
1/C
40

---

Published as a conference paper at ICLR 2024
iterations in total performed by Algorithm 2 to update yk for k 2 1, where in (80) and (81)
A max (V3in
2K
2K
8ApEE
8Ap2E
57
In
57
max (1
ono a.1 Kg
,In
Enj gil Kg
(82)
Therefore, the order step-size Algorithm is y ((ue2 (K)0),)))
Step-size and number of oracle calls for Algorithm 3. The step-size as for Algorithm 3 is given (30). By (42), (43) and Lemma 3.2, we need at most
Vo
16L 1r
256 128K 1)00,11
loga
+1)
+
(83)
22
iterations in total performed by Algorithm 3 to update you where
2k1
2k
22 max
3 ln
In
(84)
loga
1288V KG Meet
log,
128VoK3 uuzt
max
3 In
In
5
Total number of oracle calls in Algorithm 2 and Algorithm 3. Combining (81), (82), (83) and (84), the number of oracle calls needed in Algorithm 2 and are most
128 A1 + v1
128K3V0 jie2
16L /
256 X 128 (4X3 1)0
logg
+
+
T/E
1222
Algorithm
Algorithm 3
which is at most Ô (A/ne) number of oracle calls in total (recall how we choose v and the order of 77). Also, recall that we need at most K AA/ne number iterations for Algorithm 1. Therefore, the total complexity is at most O(A //ne).)
F IMPLEMENTATION DETAILS OF EXPERIMENTS
F.1 EXPERIMENTAL DETAILS OF HYPER-REPRESENT REPRESENTATION
The meta-learning experiments are performed on Amazon Reviews Dataset (Blitzer et al., 2006) for text classification. The data contains positive and negative reviews, coming from 25 different types (domains) of products, where three domains (i.e. "office pocddepsoooss'. "automotive" and "com- puter_video_game games") are selected we randomly draw samples from random 3 domains, where 20 samples form support set S and 20 samples form query set Q. Every 20 tasks form task batch, and meta update (3) for upper-level w is performed over task batch (the size of task batch m 20). The lower-level update for vari- able (i 1,,, m) of base learner is updated by SGD. The total number of iterations (i.e., the number of outer loops) in one epoch for updating w is set as K 400. The total number of epochs (i.e., the number of passes over the data) for this experiment set as 20.
testing set, which contains fewer samples. For each task Tr,
For all the baseline methods, the meta model is 2-layer RNN with input dimension=300, hidden- layer dimension=4096, and output dimension=512. The base model linear layer with input di- mension=512 and output dimension=2. All the parameters are initialized to the range of (-1.0, 1.0) uniformly.
Parameter selection for the experiments in Figure 1(a) and Figure 2(a): We use grid search to tune the lower-level and upper-level step sizes from {0.001, 0.005, 0.01, 0.05, 0.1, 0.5) for all methods. The best combinations of lower-level and upper-level learning rates are (0.05, 0.1) for MAML and ANIL, (0.05, 0.05) for StocBio, (0.1. 0.01) for TTSA, (0.05, 0.05) for SOBA and SABA, (0.05, 0.1) for MA-SOBA, and (0.001,0.01) for BO-REP. For double-loop methods (i.e.,
41

---

Published as a conference paper at ICLR 2024
0.8
TING F2CA
0.650
Thain ACC
ACC
0.7
0.7
PACOJA
Train ACC
0.600
0.6
0.550
10
15
0
10
15
0
10
20
epechs
epochs
epochs
0.9
0.75
12
ACC
1186
ACC
0.8
Test ACC
0,70
0.65
0.6
10 opochs
15
10
20
epachs
opachs
(a) Seprer-Reprsenntatiinn
(b) Hyperparameter Optimization
(c) Data Hyper-Cleaning
Figure 2: Training and testing accuracy results for different algorithms. (a) Results of hyper- representation on Amazon Review Dataset. (b) Results of hyperparameter optimization on Amazon Review Dataset. (c) Results of data hyper-cleaning Sentiment1 140 dataset with corruption rate p p=0.3.
MAML. ANIL, StocBio), we tune the number of iterations in the inner-loop from {5, 10, 20} and the best value is 10. For SOBA, SABA, MA-SOBA, and BO-REP, the step sizes for solving linear system variable z are all chosen as 0.01, which is the best tuned value from {0.001, 0.01, 0.1}. For F2SA, since it an fully first-order method and have different three variables, we tune the learning rate for these three decision variables from the range {0.001, 0.005, 0.01, 0.05, 0.1, 0.5) and the best tuned combination of value is (0.05, 0.05, 0.01). The momentum parameter for MA-SOBA and BO-REP is fixed as 0.9. We increase the lagrangian multipler of F*SA (denoted as À in F²SA) by 0.01 for every meta update.
In particular, BO-REP updates lower-level variable O periodically with interval / = 2, which means there is one update for every two outer loops. The number of iterations (N) for each periodic update in Algorithm is set as 3. the ball radius R for projection is 0.5 (ablation study for R can be found in Section J.2). In addition, for simplicity, BO-REP just adopts SGD in the stage of initialization refinement, which can be regarded as special case of epoch SGD with only one stage.
F.2 EXPERIMENTAL DETAILS OF HYPERPARAMETER OPTIMIZATION
We conduct hyperparameter optimization on the Amazon Review dataset. We randomly sample 20000 training samples and 2000 testing samples from the training and testing set, respectively. A regularization parameter À in (4) is the upper-level variable, which is initialized as 0.0. w is the lower-level variable, the model parameter of 2-layer RNN with input dimension=300, hidden-layer dimension=4096, and output dimension=2. The lower-level variable w is initialized uniformly from the (-1.0, 1.0) range.
Parameter selection for the experiments in Figure 1(b) and Figure 2(b): We compare our pro- posed algorithm BO-REP, with other baseline algorithms. We conduct a grid search for lower-level and upper-level learning rates in the range of (0.0001, 0.0005, 0.001, 0.005, 0.01, 0.05, 0.1} and find the best parameter setting for all the baseline algorithms. Specifically, we choose the best lower-level learning rates as 0.001 for StocBio, 0.01 for TTSA, 0.05 for SOBA and SABA, 0.05 for MA-SOBA, and 0.001 for BO-REP. The upper-level step size 0.0001 is applied to all the algorithms. For SOBA, SABA, MA-SOBA, and BO-REP, the best learning rates for solving the linear system are 0.05, 0.05, and 0.01 respectively, which are scarched in the range of (0.001, 0.005, 0.01, 0.05, 0.1}. 1.. For F?SA, the best combination for step sizes of its three variables is (0.01, 0.01, 0.0001), which is tuned in
42

---

Published as a conference paper at ICLR 2024
0.9
0.6
200A
Train ACC
0.8
0.5
Train_
Sixdoo
0.7
0.4
P28A
CABA
0.6
0.3
opochs
opochs
F224
T154
0.60
0.75
Test ACC
MA-008
Test Losg
0.55
03-RPP
0.70
0.50
20DA
0.65
0.45
50
10
epochs
epochs
(a) Training and Testing Accuracy
(b) Training and Testing Loss
Figure 3: (a) Accuracy of data hyper-cleaning on Sentiment 140 with corruption rate = 0.1. (b)
Loss of data hyper-cleaning on Sentimentl 40 with corruption rate p = 0.1.
the range of {0.0001, 0.0005, 0.001, 0.005, 0.01, 0.05, 0.1}. In addition, the double-loop algorithm StocBio fixes inner loops as 5 for lower-level updates.
For BO-REP. the updating interval for the lower-level variable 0, set as 2, and the number of iterations (N) for each periodical update is 3, the ball radius R for projection is 0.5. All algo- rithms fix batch size as 64. Other hyperparameter settings, including momentum parameter (for MA-SOBA and BO-REP), step size for solving linear system (for SOBA, MA-SOBA, BO-REP), and the lagrangian multiplier setting (for (²SA) keep the same as Section F.1.
F.3 EXPERIMENTAL DETAILS OF DATA HYPER-CLEANDH
We conduct the experiments the data hyper-cleaning task on Sentiment140 (Go et al., 2009) for binary text classification. Since data labels consist of two classes of emotions, positive and negative, we flip each label in the training set to its opposite class with probability (set as 0.1 and 0.3, respectively).
two-layer RNN with the same architecture as that Section F.2 is adopted as the classifier, whose parameters are lower-level variables. The upper-level variable is the weight vector corresponding to each training sample. In practice, we initialize each sample weight A; = 1.0.
Parameter selection for the experiments in Figure 1(c) and Figure 2(c): We grid search for all algorithms to choose the lower-level and upper-level step size in the (0.01, 0.05, 0.1 The best combinations of lower-level and upper-level step size are (0.05, 0.05) for StocBio, (0.05, 0.01) for TTSA, (0.1, 0.05) for SOBA and SABA, (0.1, 0.05) for MA-SOBA, and (0.05, 0.05) for BO-REP. F2SA chooses (0.05, 0.05, 0.01) for updating its three decision variables. In addition, the learning rates for solving linear system z in SOBA, SABA, MA-SOBA, and BO-REP are all fixed as 0.05 chosen from the range of {0.01, 0.05, 0.1). The number of inner loops for StocBio is set as 5, which is chosen from {3, 5, 10). For BO-REP. The updating interval / and the iterations N for lower-level variable w are fixed as 2 and 3, respectively, the ball radius R for projection 0.5. Batch size is fixed to 512 for all the algorithms. Other experimental hyperparameters, including momentum parameters (for MA-SOBA, BO-REP) and the lagrangian multiplier setting (F2SA) remain the same Section F.1.
43

---

Published as a conference paper at ICLR 2024
20000
200
200
smoothnes
Iteration
smoothnass
25
150
terations
10000
100
15
5000
10
50
100
25
50
75
100
gradient
gradient
(a)
(b)
Figure 4: (a) Local gradient Lipschitz constant of the upper-level variable vs. its gradient norm along the training iterations for an RNN in the experiment of hyper-repreesenation. (b) Local gradient
Lipschitz constant of the lower-level variable vs. its gradient norm along the training iterations for an RNN in the experiment hyper-representation.
Classification Laye
Jofumey
Input-
Recureen Neural Layer
Y
T
2
S
L(s, a)
Figure 5: The model structure for Hyper-representation. The upper-level variable the parameter of the recurrent neural layer, and the lower-level variable is the parameter of the classification layer.
G VERIFICATION OF RELAXED SMOOTHNESS (ASSUMPTION 1) FOR RECURRENT NEURAL NETWORKS
In this section, we empirically verified that the Recurrent Neural Network model satisfies Assump- tion I. Figure 4, we plot estimated smoothness at different iterations during training neural networks. In particular, we conduct the rypee-representation experiments verify Assumption 1. We adopt the same recurrent neural network as that in Section 4.1. The lower-level variable the parameter of the last linear layer, and the upper-level variable is the parameter of the previous layers (2 hidden layers). variable V fu))l and the lower-level variable V,)(()),, and use the same method as described in Appendix H.3 Zhang et al. (2020b) to estimate the smoothness constants of æ and y. From Figure 4, can find that the smoothness parameter scales lincarly in terms of gradient norm for both layers. This verifies the Assumption empirically, Note that these results are consistent with the results in the literature, e.g., Figure in Zhang al. (2020b) and Figure in Crawshaw et al. (2022).
each training iteration, we calculate the gradient norm w.r.t. the upper-level
H VERIFICATION OF ASSUMPTION 2(i)
In this section, we theoretically prove that Assumption 2(i), i.e. the practical case of hyper-representation.. this case, we define the cross entropy loss
S M, holds in
C
Lla, 8) =
Σ a log(s:),
44

---

Published as a conference paper at ICLR 2024
where C' denotes the number of class, (d1, dg....,, ac) is the one-hot encoded label and ($1, ..,..., sc) is the probability distribution generated by the softmax layer. We also define (we can view notation y y vec(Y) in the main text) and b the weight and bias, 2' and 2 as the input and output of the last layer (classification layer). So we have 2 = Y z' +b. Figure 5 illustrates the model structure and the meanning of symbols.
First we calculate
8a, dz;"
By chain rule, we have
0s: dzj
i log
E
$ dzg
log(s:) = 81 dzz
= 84 Ozj
24 - log
Σ e
21=1
ezi
1=1
Ozi
0 log
)) 8:
81
Σ E
[Aii=st
θzj
Ozj
21=1 E0
Ozg 1=1
84 1 (img)
81 (1(m))) - -s))
Σi=1 ea1
Next we calculate
0c ōzy"
By chain rule, we have
0
C
ag Us:
a log(s;) = Σ
log(s;) = 2
ai Ozj
0z,
Ozj
Ozj
i=1
i=1
i=1
C
c
C
ai (I( - -83) = Σ ag (1 (i=s) - 8j)
0:8j
0
(1=))
1=1
1=1
Σ
8j i=1
0i aj =8 83 Ojj
where we use E = 1 in the last line. Hence we have
HC
Öz 8 a.
Again, by chain rule we have
OC
OC 0z
= (s - -a)
OY
Oz OY
Therefore, conclude that
Oc
S ||a a |||||=||| || x (1|s) + +Ial))=>'1| < 2|1²//,,
ØY
where we use ||s|| < and
||a||
= for any s and a.
I PERFORMANCE COMPARISON IN TERMS OF RUNNING TIME
For fair comparison of performance, compare our proposed algorithm with other single-loop and double-loop algorithms in terms of running time, the result is shown in Figure 6. To accurately evaluate each algorithm, we use the machine learning framework PyTorch 1.13 to each algorithm individually on an NVIDIA RTX A6000 graphics card, and record its training and test loss. As we can observe from the figure, our algorithm (BO-REP) is much faster than all other baselines in the experiment of eyperrrepresentattion (Figure 6(a)) and Data Hyper-Cleaning (Figure 6(c)). For the hyperparameter optimization experiment (Figure 6(b)), our algorithm slightly slower at the very beginning, but quickly outperforms all other baselines. This means that our algorithm indeed has better runtime performance than the existing baselines bilevel optimization.
J ABLATION STUDY FOR HYPERPARAMETERS
J.1 ABLATION STUDY FOR LOWER-LEVEL. UPDATE PERIOD I AND ITERATIONS N
We conduct careful ablation studies to explore the impact of hyperparameter I (the update period of the lower-level variable) and N (the number of iterations for updating the lower-level variable
45

---

Published as a conference paper at ICLR 2024
0.7
0.7
0.68
Train Looe
Train Loss
4M. DieDe
0.5
7254
0.4
0.4
KOSA
0.65
2004
0.64
35-1E7
2000
4000
500
1000
1000
2000
3000
running time 2s
running time
running time
0.7
0.7
0.650
Test Loss
0.5
ANL
Te5t LOSS
0.5
Test Loss
0.600
ITSA
0.3
0.575
MA-03A
0.3
MA50344
10427
0
2000
4000
500
1000
1000
2000
3000
running time
running time
running time
(a) Elyper-Representation
(b) Hyperparameter Optimization
(c) Data Plyper-Cleaning
Figure 6: Comparison of various bilevel optimization algorithms w.r. running time (s): (a) results of represttpressnttaiion on Amazon Review Dataset. (b) results of hyperparameter optimization on Amazon Review Dataset. (c) results of data hyper-cleaning on Sentimenti Dataset with noise rate
p 0.3.
Table 3: Test accuracy vs. Projection radius R
Radius
R-0.001
R=0.005
R=0.01
R=0.05
R=0.10
R=0.50
R=1.00
R=5.00
Test Accuracy
65.06%
67.64%
70.76%
81.22%
86.84%
88.84%
88.84%
88.84%
during each period). The experimental results in Figure 7(a) show that the performance of BO-REP algorithm decreases slightly when increasing the update period / from to 8 while fixing inner iterations N. That demonstrates empirically our algorithm is not sensitive the update period hyperparameter /. When the value of is too large (I 2 16), we observe significant performance degradation. In our experiments in the main text, we choose I 2 for all experiments and get good performance universally. The ablation result for inner iterations N is shown in Figure 7(b). where the update period 7 is fixed. The figure shows that the performance of BO-REP algorithm would increase as the number of inner iterations increases. The algorithm can achieve the best performance when 2 5. In our experiments, it is good enough to choose universally for all tasks.
to achieve good performance
Due to these ablation studies, it means that the algorithm does not need lots of tuning efforts despite these hyperparameters (e.g., and N): some default values of I and N (e.g.. I = 2, N 3) work very well for a wide range tasks in practice.
J.2 ABLATION STUDY FOR THE RADIUS R OF PROJECTION BALL
We experimentally explore how the ball radius R affects the algorithm's 's performance. We set the ball radius as (0.001, 0.005, 0.01, 0.05, 00 0.50, 1.00, 5.00] respectively, and then conduct the bilevel optimization on Hyper-represennttion tasks. We keep all the other hyperparameters. the same in Section 4.1. The result shown in Table When the ball radius is too small (i.e., R < 0.10), the performance significantly drops, possibly due to the overly restricted search space for the lower- level variable. When the ball radius R 2 0.50, the performance becomes good and stable. In our experiments in the main text, choose R 0.5.
46

---

Published as a conference paper at ICLR 2024
0.85
0.9
0.80
ACC
0.75
0.70
0.7
N=1, 1=1
N-3. 1-2
N=3. 1-2
N-3. 1-4
0.6
N-5, 1-2
N-3.
N=15, I=2
0.55
10
15
10 epochs
epochs
(b)
Figure 7: Ablation study of the update period and the number of iterations for updating lower-level variable during each period N (a) The performance of hyper-representation with different update period J. (b) The performance of byper-repressnnation with different numbers of update iterations N.
0.9
0.76
0.74
0.50
NANL
3 0.75
A18.
Secile
2 0.70
125A.
F254
0.66
ITEA
5054
06
9784
3553
0.00
H4 583006
0.64
0.55
31-20
0.
0.62
92-02/1000111221
3.0
e5ochs
epochs
eptenbs
(a) (lyper-Representatie
(b) Hyperparameter Optimization
(c) Data Clepei-Ce
Figure 8: Comparison results with the larger value of update iterations and update period on Seyper-Representation (b) Comparison results with the larger value of update iterations N and update period I on Hyperparameter Optimization. (c) Comparison results with the larger value of update iterations N and update period I on Data Hyper-Cleaning
K EXPERIMENTAL RESULTS WITH LARGE I AND LARGE N
In this section, we further explore the setting hyperparameters N and I. particular, we evaluate the algorithm performance on the larger value of N and (i.e., N 16, 12) compared with the value we used in the experiments described in main text (i.e., N = 3, -= 2). which may better fit our theory. The results are presented in Figure where Figure 8(a), (b), (c) show that the compared test accuracy on three different tasks, respectively. We can observe that the algorithm performance with the large value of N and / (green dash line) is almost the same as even better than) the original setting (green solid line). The larger number of N can compensate for performance degradation induced by long update period I. In particular, the new results in Figure 8(b), (c) (green dash lines) are obtained with slightly smaller lower-level learning rate (8 x 10-1 in (b) and 5 10 in (c)) than the original setting (green solid lines with 10-3 30 in (b) and 5 x 10-2 2 (c)). However, the setting of N 3, 2 is good enough in our experiments to achieve good performance for all the tasks.
L OPTIMALITY OF OUR COMPLEXITY RESULTS
In this section, we demonstrate why our proposed algorithm is optimal up to logarithmic factors no additional assumptions are imposed. We first introduce the definition of mean-squared smooth- ness (Arjevani et al., 2023) and individual smoothness (Cutkosky & Orabona, 2019) for single-level optimization problems, and then discuss how these assumptions being used in bilevel opti-
47

---

Published as a conference paper at ICLR 2024
mization literature to achieve Ō(1/e²) oracle complexity, and at last we demonstrate proposed algorithm with Ö(L/e*) is indeed optimal up to logarithmic factors under current assumptions in this paper.
For single-level problems, given differentiable objective function R E, we say the function I satisfies mean- meen--quared smoothness property (formula (4) in Arjevani et al. (2023)) if for any x, E IRd and any { ~~1 Pç.
EE (x: - (v: 12|| yl1
(85)
where we use S. VV(r;; E) and (the corresponding notations Arjevani et al. (2023) are 2, g(r, 2) and L, please check formula (4) in Arjevani et al. (2023) for details) to denote the random data sample, the stochastic gradient estimator and the mean-squared smoothness constant.
A slightly stronger condition than mean- squa-e smoothness is the individual smoothness property (please check the statement "We assume that f(x, {s) is differentiable, and L-smooth as a function of x with probability 1." in Section 3 of Cutkosky & Orabona (2019) for details). We say function has individual smoothness property if for any 2, y E IRd and any { ~ Pg.
(+; - V ( 1 < L||
v|l-
(86)
For bilevel problems, in order to obtain ((1/e²) oracle complexity bound, Yang et al. (2021), Guo et al. (2021) and Khanduri et al. (2021) actually require individual smoothness assumption (As- sumption (86)) jointly in (ar, v) E Rd x I& for both upper-level (i.e., outer function fæz y)) and lower-level problems (i.e., inner function g(x, y)). To be more specific, for upper-level problem they require for any (z, d' (x', ./) Rd x Rd and any E.
Vv,((u;) v E)ll S L u'll, vV; (u: E) S T, 11, w'll,
and for lower-level problem they require for any (x. y), v' (z',1/) Rd x Rdd and any Ç.
VV V V, (u; <)_l s L, 1- -'|l.
These three inequalities above be viewed as definition of individual smoothness property under bilevel optimization setting. For more details, please check Assumption 2 in Section 3.1 of Yang al. (2021), Assumption 2 in Section 2 and Assumption 4 in Section 4 of Guo et al. (2021), As- sumption 2 in Section of Khanduri et al. (2021). Please note that our paper does not assume any of these assumptions.
Notably, all the bilevel optimization literature (Yang et al., 2021; Guo et al., 2021; Khanduri et al., 2021) with ((1/e)) complexity use individual smoothness assumption, which is stronger than the mean-squared smoothness. Also, their algorithm design depends on the STORM tech- nique (Cutkosky & Orabona, 2019). In addition, it is shown in Arjevani et al. (2023) that without this assumption, ((1/E*) complexity is necessary for stochastic first-order optimization algorithms for single problems. This indicates that our complexity is optimal up to logarithmic factors for the bilevel problems we considered in this paper.
Let give more details to explain this. We consider potentially non-convex single-level opti- mization problems as considered in (Arjevani et al., 2023). Given differentiable objective function V dd + IR our goal is to find an e-stationary point using stochastic first-order algorithms. As- sume the algorithms access the function V through a stochastic first-order oracle consisting a noisy gradient estimator V Rd x = + Rd and distribution Pş on E satisfying
PE- \ V (z: {) V (x)) and Re- [| (ar; {) V (v)())) (1) 5
(87)
Also we make the standard assumption that the objective v has bounded initial subobtimality and L-smoothness property,
T (xx) inf V (x)
A and [V V (v)) L| 1ilx-w1) vll.
(88)
ZERd
where zo is the initialization point for the algorithm.
For potentially non-convex single-level optimization problems, Theorem 3 in Arjevani et al. (2023)
states that
48

---

Published as a conference paper at ICLR 2024
Under Assumptions (87) and (88), any stochastic first-order methods requires {2(1/c*) queries to find an e-stationary point in the worst case (please check Contribution Sec- tion 1.1, and formula (23) in Theorem 3 of Arjevani et al. (2023) for details);
Under Assumptions (87) and (88), plus mean-squared smoothness assumption, any stochas- tie first-order methods require (21/e²) queries to find an e-stationary point in the worst case (please check Contribution 2 in Section 1.1, and formula (24) in Theorem 3 of Arjevani et al. (2023) for details).
Note that our problem class is more expressive than the function class considered in Arjevani al. (2023) and hence our problem is harder. This is because standard smoothness is special case of relaxed smoothness and single-level optimization is special case of bilevel optimization. For exam- ple, if we consider an easy case where the upper-level function does not depend on the lower-level problem (e.g., ((x) f(x) such that independent y (x)) and does not have mean-squared smoothness, then the ((1/ct) lower bound in Arjevani al. (2023) be applied in our setting. Therefore the ((1/e*) complexity achieved in this paper is already optimal up logarithmic fac- tors.
49


Reviews:
[{"review_id": "4WndcJKY0K", "reviewer": "Reviewer_7Cii", "summary": "The authors present a novel algorithm for bilevel optimization called BO-REP. This method achieves $\\mathcal{O}(1/\\epsilon^4)$ convergence rates to find $\\epsilon$-stationary point in the stochastic non-convex setup assuming only a relaxed smoothness assumption. Moreover, this result matches the state-of-the-art complexity results under the more restrictive types of smoothness up to logarithmic factors. The key two technical ingredients - initialization refinement and periodic updates - are easily implementable. Finally, authors demonstrate the practical efficiency of the proposed approach on hyper-representation learning, hyperparameter optimization and data hyper-clearning for text classification.", "questions": "- Is it possible to relax the strong convexity assumption of the lower function to log-concavity? \n- What are challenges to provide high-probability guarantees for $\\epsilon$-stationary point for the given algorithm?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is very well-written and easy to follow. Moreover, it clearly demonstrate all the novelties of the proposed approach.\n- The complexity result matches the existing state-of-the-art methods with less restrictive smoothness assumption, that is critical for presented applications on RNNs.\n- The experimental validation shows the superiority of the proposed method over other methods for bilevel optimization.", "weaknesses": "- Lack of lower bounds does not allow to understand optimality of the proposed method under given assumption;\n- Proposed guarantees holds only for finding an $\\epsilon$-stationary point in expectation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y4CoMa1OdA", "reviewer": "Reviewer_fyzv", "summary": "This paper investigates bi-level stochastic optimization problems in which the upper-level function could have an unbounded smoothness parameter. To solve the above problem, the authors proposed to use $(L_{x,0}, L_{x,1}, L_{y,0}, L_{y,1})$-smoothness assumption for the upper-level function, which is a generalization of the relaxed smoothness assumption for single-level optimization. Then they designed a new algorithm named BO-REP for solving bilevel optimization problems with unbounded smooth upper-level functions. BO-REP used normalized momentum technique for updating the upper-level variable and initialization refinement and periodic update tecniques for lower-level variables. The experiments demonstrated the effectiveness of the proposed algorithm.", "questions": "1. In initilalization refinement step, what's the purpose to invoke a multi-epoch algorithm to obtain an accurate estimate of lower-level variables and why periodic update doesn't use such a multi-epoch strategy?\n\n2. The initialization refinement and periodic updates for are carefully designed for obtaining an accurate estimate of the lower-level variables at each iteration. Under current unbounded smoothness assumptions, is that possible to design algorithms with inexact estimate of the lower-level variables? Since the periodic update for the lower-level variables make the proposed algorithm a nested loop one, is there any potential strategies for us to design a single-loop algorithm for solving the unbounded smoothness bilevel optimization problems? \n\n3. In the experiments, how is the ball radius R chosen?\n\nMinor issues:\n1) caption of table: \"$\\mathcal{C}_L^{a, a}$ denotes a-times differentiability with Lipschitz k-th order derivatives.\" I think it should be $\\mathcal{C}_L^{a, k}$ here.\n2) In the pseudo-code for Algorithm 2, the outer loop with the iteration variable k spanning from 0 to K-1 is repeatedly defined, which may lead to ambiguity or confusion for the readers. To enhance clarity, I'd recommend passing the current iteration k as an input to the UpdateLower subroutine (which is a part of the BO-REP algorithm) and subsequently removing the loop from the algorithm.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "### Originality\nThe problem setting of this paper is novel. To the best of my knowledge, this is the first work in the literature of bilevel optimization that takes account into the unbounded smoothness assumption for the upper-level functions. \n\nThe proposed method is novel. To solve the above problem, the authors proposed two novel mechanisms for updating the lower-level variables.\n\n### Quality and Clarity\n\nOverall, this paper is well written, although it is not clear enough in some places.\n\n### Significance\n\nThis article explores a new problem and designs new algorithms to solve it. I think this will inspire researchers to thin about bilevel optimization problems from a new perspective and design more efficient algorithms.", "weaknesses": "The main drawback of the proposed algorithm is that the structure is complex, and each subroutine contains additional hyperparameters that need to be tuned.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yrjSu2o7po", "reviewer": "Reviewer_enk4", "summary": "This paper proposes bilevel algorithm, BO-REQ to address unbounded smoothness challenge. Specifically, the authors introduce the normalized momentum and initialization refinement techniques, and proposed algorithm achieves the convergence rate of $\\mathcal{\\widetilde O}(1/\\epsilon^4)$. The experiments across various settings also demonstrate the effectiveness of the proposed algorithm.", "questions": "Check the weakness.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The proposed algorithm outperforms other bilevel baselines in experiments across various contexts.", "weaknesses": "1. This paper relaxes the bounded assumptions but is not based unbounded assumption as stated in the abstract. The example pf RNN and LSTMs are misleading unless the authors are able to prove that these networks satisfy the Assumption 1.\n\n2. The second stated contribution in introduction section is not valid. As the author also mentions in the footnote 3, the SOTA complexity results under bounded smoothness is $\\mathcal{\\widetilde O}(1/\\epsilon^3)$. The proposed method does not achieve the SOTA complexity rate, even after considering the logarithmic factors.\n\n3. Momentum technique has been incorporated in the bilevel optimization area before. For example, MRBO [1] achieves the $\\mathcal{\\widetilde O}(1/\\epsilon^3)$ after momentum introduction. The authors are expected to improve the convergence rate of proposed algorithm.\n\n4. The authors are suggested to show the experimental results w.r.t. time rather than only epochs. The proposed algorithm involves three loops per epoch, which might introduce extra computational cost. It will be more fair to compare proposed algorithm with other single-loop or double-loop based algorithms in terms of running time.\n\n[1] Provably Faster Algorithms for Bilevel Optimization", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hTddkGTiKP", "reviewer": "Reviewer_ZUWL", "summary": "This paper investigates a bilevel stochastic optimization problem in which the gradient of the upper-level objective function is potentially unbounded, and the lower-level objective function is strongly convex. \nThe authors introduce a new algorithm, which integrates the normalized momentum technique for updating the upper-level variable and employs initialization refinement as well as periodic updates techniques for updating the lower-level variable. The authors also offer a theoretical complexity analysis. To substantiate the efficacy of the proposed algorithm, the paper includes a set of numerical experiments.", "questions": "1. The proposed algorithm incorporates an initialization refinement procedure for the lower-level variable. I am curious about whether the authors have taken into account the computational cost associated with this initialization refinement procedure when presenting the numerical results in Figure 1.\n\n2. While the proposed algorithm exhibits advantages over its competitors in terms of the number of epochs required, how about its performance concerning computation time?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper is clear, well organized, and easy to follow.\n\n2. The incorporation of the normalized momentum update for the upper-level variable, as well as the utilization of initialization refinement and periodic updates for the lower-level variable within the proposed algorithm weaken the bounded smoothness requirement of the upper-level objective function.\n\n3. Simulations have shown the empirical advantage of the proposed algorithm.", "weaknesses": "1. The theoretical complexity result of the proposed algorithm, Theorem 1, lacks persuasiveness. Specifically, the choice of the iteration number $N$ in Algorithm 2 for lower-level variable updates is left unspecified. Furthermore, the selection of the parameter $I$ appears improper, particularly in comparison to the selection of the parameter $K$. This peculiarity arises because, according to Theorem 1, $I = O(1/\\epsilon^2)$, while $K = O(1/\\epsilon)$. Consequently, for sufficiently small values of $\\epsilon$, $I$ is significantly larger than $K$. However, both the implementation of the proposed algorithm and the theoretical analysis, as exemplified by Lemma 2, necessitate $I$ to be smaller than $K$.\n\n2. Despite the authors' assertion that they do not require the boundedness of the norm of the gradient of the upper-level objective function, $ || \\nabla_y f(x, y) ||$, as stipulated in Assumption 2 (i), it is worth noting that they still demand the boundedness of $|| \\nabla_y f(x, y^*(x)) ||$. The rationale behind the relative ease of achieving this condition in practical scenarios, as opposed to the former requirement, remains unclear. Moreover, it remains unaddressed whether the problems examined in the numerical experiments exhibit unbounded smoothness yet satisfy Assumption 2 (i).\n\n3. The selection of the parameters $I$ and $N$ in the implementation of the proposed algorithm in the numerical experiments deviates from the parameters required by the theoretical analysis. Specifically, the theoretical analysis mandates that both $I$ and $N$ should be large as $\\epsilon$ becomes small. However, in the context of the numerical experiments, the authors have set the values for $I$ and $N$ as merely 2 or 3, which contradicts the theoretical analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zZWssBz8tr", "reviewer": "Reviewer_gGYZ", "summary": "This paper considers the bilevel optimization under unbounded smoothness and proposes a new algorithm based on the SOBA method. This paper gives the convergence analysis under the unbounded smoothness and the experimental results demonstrate the superiority of the proposed method.", "questions": "1. How will the iteration numbers affect the convergence performance? Is the inner loop necessary? Because this method seems to be a momentum method based on SOBA, why author use an inner loop? why not just update $y$ for a single step?\n2. Why only use the SOBA in [1]. SABA also proposed in [1]. I think it should be compared.\n3. How to ensure the problem considered in experiments is unbounded smooth? Because the applications considered in this paper are usually considered in other papers with bound smoothness assumption.\n\n\n[1] Dagréou M, Ablin P, Vaiter S, et al. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms[J]. Advances in Neural Information Processing Systems, 2022, 35: 26698-26710.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Under the unbounded smoothness, this paper obtains a similar convergence rate as that in other papers.\n2. The experimental results demonstrate the superiority of the proposed method.", "weaknesses": "1. Too many loops in Algorithm 1,2 which may lead to time-consuming.\n2. Some symbols are confusing. Both Algorithms 1, and 2 use K. In lemmas, what is $K_0$?\n3. Too many hyperparameters in algorithms. More experimental results of different hyperparameters are needed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)