BiAdam: Fast Adaptive Bilevel Optimization Methods
Authors: Feihu Huang
Junyi Li
Shangqian Gao
Venue: Submitted to ICLR 2023 (2023)
Keywords: Bilevel Optimization
Momentum
Adaptive Learning Rate
Variance Reduced
Hyper-Parameter Learning

Abstract: Bilevel optimization recently has attracted increased interest in machine learning due to its many applications such as hyper-parameter optimization and mate learning. Although many bilevel optimization methods recently have been proposed,  these methods do not consider using adaptive learning rates. It is well known that adaptive learning rates can accelerate many optimization algorithms including (stochastic) gradient-based algorithms. To fill this gap, in the paper, we propose a novel fast adaptive bilevel framework for solving bilevel optimization problems that the outer problem is possibly nonconvex and the inner problem is strongly convex. Our framework uses unified adaptive matrices including many types of adaptive learning rates, and can flexibly use the momentum and variance reduced techniques. In particular, we provide a useful convergence analysis framework for the bilevel optimization. Specifically, we propose a fast single-loop adaptive bilevel optimization (BiAdam) algorithm based on the basic momentum technique, which achieves a sample complexity of $\tilde{O}(\epsilon^{-4})$ for finding an $\epsilon$-stationary point. Meanwhile, we propose an accelerated version of BiAdam algorithm (VR-BiAdam) by using variance reduced technique, which reaches the best known sample complexity of $\tilde{O}(\epsilon^{-3})$ without relying on large batch-size. To the best of our knowledge, we first study the adaptive bilevel optimization methods with adaptive learning rates. Some experimental results on data hyper-cleaning and hyper-representation learning tasks demonstrate the efficiency of the proposed algorithms.

Under review as a conference paper at ICLR 2023
BIADAM: FAST ADAPTIVE BILEVEL OPTIMIZATION METHODS
Anonymous authors Paper under double-blind review
ABSTRACT
Bilevel optimization recently has attracted increased interest in machine learn- ing due to its many applications such as hyper-parameter optimization and meta learning. Although many bilevel optimization methods recently have been pro- posed, these methods do consider using adaptive learning rates. It is well known that adaptive learning rates can accelerate many optimization algorithms including (stochastic) gradient-based algorithms. To fill this gap, the paper, we propose a novel fast adaptive bilevel framework for solving bilevel optimization problems that the outer problem is possibly nonconvex and the inner problem is strongly convex. Our framework uses unified adaptive matrices including many types adaptive learning rates, and can flexibly use the momentum and vari- ance reduced techniques. In particular, we provide useful convergence analysis framework for the bilevel optimization. Specifically, we propose a fast single- loop adaptive bilevel optimization (BiAdam) algorithm based on the basic mo- mentum technique, which achieves sample complexity of Ö(E=4) for finding an c-stationary point. Meanwhile, we propose an accelerated version of BiAdam algorithm (VR-BiAdam) by using variance reduced technique, which reaches the best known sample complexity of Ö(e=3) without relying large batch-size. To the best of our knowledge, we first study the adaptive bilevel optimization methods with adaptive learning rates. Some experimental results data hyper- cleaning and hyper-representation learning tasks demonstrate the efficiency of the proposed algorithms.
INTRODUCTION
Bilevel optimization is known as a class of popular hicrarchical optimization, which has been applied to wide range of machine learning problems such hyperparameter optimization Shaban et al. 2019), meta-learning Di et al. (2021): Liu et al. (2021a) and policy optimization Hong et al. (2020). In the paper, consider solving the following stochastic bilevel optimization problem, defined as
min F(x)= = EE-D [ (2, (x): xE
(Outer)
(1)
s.t. y² (x) arg min Bc-oM (gla,vv())
(Inner)
DEy
where F(x) ((x (x)) = Be[ (c) is differentiable and possibly nonconvex func-
tion, and g y) = [o( () is differentiable and strongly convex function in variable y, and E and Ç are random variables follow unknown distributions D and M. respectively. Here C Rd and )/ C RR are convex closed sets. Problem ① involves many machine learning problems with hierarchical structure, which include hyper-paramen optimization Franceschi et al. (2018), meta- learning Franceschi et al. (2018), policy optimization Hong al. (2020) and neural network archi- tecture search Liu et al. (2018).
Since bilevel optimization has been widely applied in machine learning, some works recently have been begun to study the bilevel optimization. For example, Ghadimi & Wang (2018); Ji et al. (2021) proposed a class of double-loop methods to solve the problem (I). However, obtain accurate estimate, the BSA in Ghadimi & Wang (2018) needs to solve the inner problem to a high accu- racy, and the stocBiO in Ji et al. (2021) requires large batch-sizes in solving the inner problem.

---

Under review as a conference paper at ICLR 2023
Table 1: Sample complexity of the representative bilevel optimization methods for finding an e- stationary point of the bilevel problem [T] i.c., [[]] I or its equivalent variants. BSize denotes mini-batch size; ALR denotes adaptive learning rate. C(x, y) denotes the constraint sets in and y. where Y denotes the fact that there exists convex constraint on variable, otherwise is N. DD denotes dimension dependence in the gradient estimators, and denotes the dimension of vari- able y. 1 denotes Lipschitz continuous of V.. (z,, y; E), vz y; E) Vug(a, yi (), V Vz Vi and V (a yi () for all &, <: 2 denotes Lipschitz continuous of V= y). Vy v), V Vyg(a, y), v (z, y) and V2 ga, y): 3 denotes bounded stochastic partial derivatives V Vyf(2, y: {) and My az yr C); denotes bounded stochastic partial derivatives V=f(2z yi E), and V (x, yi C); 5 denotes the bounded true partial derivatives v,f y) and (z, y); denotes Lipschitz con- tinuous of function [(x,, yi {); 7 denotes g(2, yi () is -smoohh and je-strongly convex function
w.r.l y for all Ç: 8 denotes g(z, y) is Ssg-toothh and j-strrongly convex function w.E.L y.
Algorithm
Reference
Complexity
BSize
Loop
C(a.g)
DD
ALR
Conditions
BSA
Ghadimi & Wang 2018
0(1)
Double
Y.N
2. 7
TTSA
Hong al. 2020
Dir )
O(1)
Single
Y.N
1
1,
MloBiiO
et 2021
Oie 9
Oie
Double
N,N
1, 6, 7
STABLE
Chen al. 2022
Ole
0(1
Single
N.N
3, 4. 8
SMB
Guo al.
b02
Ole-))
011
Single
N.Y
8
2.
SUSTAIN
Khanduri et al.
2021
Oie )
0(1)
Single
N, N
1, 7
SVRB
Guo & Yang
2021
Oie
0(1
Single
N.N
8
1, 8
MRBO
Yang al.
2021
Ole
0(1)
Single
N.N
x²
6.
VRBO
Yang cl al.
2021
Oie
Ole
Double
N. N
1. 1.6.7 7
BiAdam
Ours
Oce
0(1)
Single
YNN, Y/N
12
2, 7
VR-BiAdam
Ours
Ole
O())
Single
Y/N. Y/N
5.
Hong et al. (2020) proposed a class of single-loop methods to solve the bilevel problems. Subse-
quently, Khanduri et al. (202T): Guo & Yang (202T); Yang et al, (202T): Chen et al. (2022) presented some accelerated single-loop methods by using the momentum- based variance reduced technique of STORM Cutkosky & Orabona (019). More recently, Dagréou et al. (2022) developed novel framework for bilevel optimization based on the linear system, and proposed a fast SABA algorithm for finite-sum bilevel problems based on the varaince reduced technique of SAGA (Defazio al., 2014). Although these methods can effectively solve the bilevel problems, they do not consider us- ing the adaptive learning rates and only consider the bilevel problems under unconstrained setting. Since using generally different learning rates for the inner and outer problems to ensure the conver- gence of bilevel optimization problems, we will consider using different adaptive learning rates for the inner and outer problems with convergence guarantee. Clearly, this can not follow the exiting adaptive methods for single-level problems. Thus, there exists a natural question:
How to design the effective optimization methods with adaptive learning rates for the bilevel problems? ?
In the paper, we provide an affirmative answer to this question and propose class of fast single- loop adaptive bilevel optimization methods based on unified adaptive matrices, which including many types of adaptive learning rates. Moreover, our framework can flexibly use the momentum and variance reduced techniques. Our main contributions are summarized as follows:
1) We propose a fast single-loop adaptive bilevel optimization algorithm (BiAdam) based on the basic momentum technique, which achieves sample complexity of Ō(c=4) for finding e-stationary point.
2) Meanwhile, we propose single-loop accelerated version of BiAdam algorithm (VR- BiAdam) by using the momentum-baan variance reduced technique, which reaches the best known sample complexity of Ō()-3).
3) Moreover, we provide useful convergence analysis framework for both the constrained and unconstrained bilevel programming under some mild conditions (Please see Table
4) The experimental results on proposed algorithms.
learning demonstrate the efficiency of the
2

---

Under review as a conference paper at ICLR 2023
2 PRELIMINARIES
2.1 NOTATIONS
241,2..... ..,, } denotes uniform distribution over discrete (I, -|- denotes the &2 norm for vectors and spectral norm for matrices. (x, v) denotes the inner product of two vectors and y. For vectors I and y, xx (r > 0) denotes the element-wiss wise power operation, z/y denotes the element-wise division and max(x, y) denotes the element-wise maximum. Ia denotes d-dimensional identity matrix. A denotes that the matrix is positive definite. Given function [( y). [(x, -) denotes function w.r.f. the second variable with fixing and [(; y) denotes function w.r.. the first variable with fixing y. a = O(b) denotes that a I Cb for some constant C' 0. The notation (.) hides logarithmic terms. Given a convex closed set X, we define a projection operation to X Px(z) arg min -|| - 2
2.2 SOME MILD ASSUMPTIONS
In this subsection, we give some mild assumptions on the problem 1 Assumption For any x. and s, g(x,y: is L--smooth and p-strongly convex function, i.e., Lg1p - gy ys S) & plp-
Assumption 2. For functions (ax y) and g(x, for all x E X and y E y, we assume the following (x.y) y) and V (x. y) are Ly-Lisschitz contimuous, Vyg(z, y) is Li-Lipschizz conditions hold: fz
continuous, V Vegg(a y) is Tegny-Lipschin Lipschitz continuous, Vggg(s, y) -ipschips continuous. For example, for all x. 31, D2 E X and y, yn, U2 E V, we have
[Vaf(x111)) v) Vzf(22. v\ll S L x2l1, [V=f(xx v1) Vaf(I, y2)ll S L y2ll-
Assumption 3. For functions E) and g(x, V) for all E X. YE V. & and S, sume the following conditions hold: VaJ(I, y: and vzJ(z, y. are T.p-Lipschitz continuous, V yzg y, Q) is Lipschitt continuous, 22y9(a, yi () is Logy- Lipscciit continuous, 4 Vyyg(z, () Lu Lipschitz continuous. For example, for all x, F1, U2 E X and y, V1, 2/2 Y, we have
Vaf(I, y23 v23 S Ly Ell1 B2ll Assumption 4. The partial derivatives Vys(o, and Vayg(1, are bounded, i.e.. [V,5(,,))11 < Cj2, and (2zg(1, u)1l Ogny
f {) -2f y. E)1l S. Ly[læ1 - -221.
Assumption Stochastic functions fxx y: and g(x, () have unbiased stochastic partial derivatives with bounded variance, e.g.,
= (x) (Z, Valla,))l S
The same assumptions hold for V of V vyg(z, v: 5). V2yg(z, () and p0,g(,, y; ().
Assumptions 1 are commonly used stochastic bilevel optimization problems Ghadimi & Wang
2018); Hong et al. (2 Di
al. (2221; Chen al.
(2022); Khanduri et al. (2021) Note
that Assumption 3 is clearly stricter than Assumption 2 For example, given Assumption we have (V,((11)) y) (= v) |
V 2 OI]l
y/
V (I2, |l < Ly
x2 ||l| for any C. At the same time, based on Assumptions Vyf(a,y)
we also have V (x. 12 1 [gf(r. yx
V ? < V fxr (x,ye E)
VyJ(x, + (x, y)
V,
20 +207 Jy and || | 20, C)Il 20 +20 gzy" Thus we argue
that under Assumption 5 the bounded V, f,, y) and V2 2z ((1)))) y) are not milder than the bounded
V J f(, E) and 2 2y9(2, for all and Ç.
2.3 BILEVEL OPTIMIZATION
In this subsection, we review the basic first-order method for solving the problem ① Naturally, we give the following iteration update the variables x, y: at the 1-th step
V1+1 Py (y Ao F++1
Px Pxx VVzf( (m))))
va)))
3

---

Under review as a conference paper at ICLR 2023
where À > 0 and y 0 denote the step sizes. Clearly, if there does not exist closed form solution of the inner problem in the problem (I), ie., Vt+1 * y (zt), we can not easily obtain the gradient
(x,, (az, y" (z+)). Thus, one of key points in solving the problem (I) is to estimate the gradient (Fx)).
Lemma 1. (Lemma 2.1 in Ghadimi Wang 2018 Under the above Assumption we have, for any x E X'
VF(x)= - (x v my az, v (x)) V Vg (x)) ( V (x)).
From the above Lemmal 1 it is natural to use the following form to estimate (F)),, defined as,
Vı(z, (z, (2 v) ( Va v)) 'V
V (z, v), Vo E EX
Note that although the inner problem of the problem ( is constrained optimization, we assume that the optimal condition of the inner problem still is V (yg y (z)) and y (x) E y
Lemma 2. (Lemma 2.2 in Ghadimi Wang 2018)) Under the above Assumptions T2 E X and )", we have
for all
[V v) (F I L (x) wll. (lv)(x1) - (x2))) x||æ] x2ll.
[ VF -1
where Ly = L L, / p + Cfy (Lago/ ut LgnnyCCnnn Gany/ 12), K = Casy/ and = L +L
Ly ggy/g Csy (Lyry//
Cgay/
For the stochastic bilevel optimization, Yang et al. estimator V Fx:) as follows:
2021
Hong et al. (020) provided a stochastic
Vf(,, = Vxf(x, v) V Vr,
Σ
II
v
1==-0
(3)
where 9 and Q 2 Here S , ... ( where is drawn from distribution D, and (G.5'....-59)) are drawn from distribution M.
ADAPTIVE BILEVEL OPTIMIZATION METHODS
In this section, we propose class of fast single-loop adaptive bilevel optimization methods solve the problem equation T Specifically, our methods adopt the universal adaptive learning rates as in Huang et al. (202T). Moreover, our methods can be flexibly incorporate the momentum and variance reduced techniques.
3.1 BIADAM ALGORITHM
In this subsection, we propose fast single-loop adaptive bilevel optimization method (BiAdam) based on the basic momentum technique. Algorithm shows the algorithmic framework of our BiAdam algorithm.
At the line 4 of Algorithm D generate the adaptive matrices Ar and B, for updating variables and y, respectively. Specifically, we use the general adaptive matrix A, > pla (p 0) for variable and the global adaptive matrix B, Lp (b, > 0). For example, we can generate the matrix A, as the Adam Kingma& Ba (2014), and generate the matrix B, as a novel version of AdaGrad-Nome Ward et al. (0119) defined as
W; aw;- + a) ( Wii E.) wo 0, A. = diag / Wr + p), 121 b. = Ab,-1 + (1 - V (x ue: G.1,, by > 0. B, = (b, T) t2 1,
(4)
(5)
where a, 8 E (0, and p 0, 0.
At the lines 5-6 of Algorithm we use the generalized projection gradient iteration with Bregman distance Censor & Zenios [1992] Huang al. (2021) to update the variables and y, respectively.
4

---

Under review as a conference paper at ICLR 2023
Algorithm BiAdam Algorithm
1: Input: T, K E N. parameters {7, X, tt. at, 3r} and initial input Φ1 E X and y1 E 3/
2: initialize: Draw K + 2 independent samples & = (f,, St. St....................... , <K-11 and Cı, and then V gg (z1, (1), and W1 Vf(11, E1) generated from 6
compute 81
3: for ......., do
4: Generate adaptive matrices A, Radxd B, Rpxp;
27 (x x²,²² A&(x 24)}. and F++1 = It + 7a ( xr)): 6: Øt+1 arg minyey {(v,, y) + 1 y1)² Br(y y/1 }. and yt+1 yt + no n8 ye);
5: #e+1 arg minzex { (w,, 2) + 1
7: Draw K + independent samples E(+1 = {f++1, S2+1> , KK11 and S4+1:
8: U++ 0+++1 V Veg( 1 + 044 juss
9: W+++1 = V M++1i + (1 B W4s
10: end for
11: Output: Chosen uniformly random from (Iz, Vt J
When X' = Idd and y = RP, i.c. unconstrained optimization problem An w. and 1+++1 1/+ Ar Ur.
I. we have Jz+1
At the line of Algorithm we draw K + independent samples & (5, 5 S.
(K-1) from
distributions and M, then we define a stochastic gradient estimator as in Khanduri et al. (202T):
k II 9
K L
1 v Ig
Vf(x,),)) = f( - v "2
(4
(6)
where K 2 and k ~ (1, 1,... K - 1) a uniform random variable independent on E. fact, the estimator (6) is specific case of the above estimator (3). In practice, thus, use tuning
parameter 9 (0, F.g. instead of T. in the estimator (6) as in Yang et al. (2021). Here we use the
1
term K
T.g 11 (4p- V yi (t) to approximate the Hessian inverse, i.e., (V Vugg(a yi ())
Clearly, the above ff y. V)
) is a biased estimator in estimating ff y), i.e. Eg f {)
+
(f(x, v). In the following, we give Lemma which shows that the bias R(x, y)
V Vs(,
[ fxx {)] in the gradient estimator decays exponentially fast with number K.
Lemma 3. (Lemma 2.1 in Khanduri et al. (2027) and Lemma in Hong et al. (2020)) Under the
about Assumptions 7 4 for any K > the gradient estimator in equation 6 satisfies
|R(x, CanyCry (1
11 )
H
Lg
where R(x,1) = V fzx v) - ((
From Lemma choose K Lx Cyy Algorithm we have [[( y)ll S + for all t 2 1. Thus, this result guarantees convergence our algorithms only requiring a small mini-batch samples. For notational simplicity, let RG R(x,, ys) for all t 2 1.
Lemma 4. (Lemma 3.I in Khanduri et al. (202T)) Under the above Assumptions
3 4
stochastic
gradient estimate V fI, y: () is Lipschitz continuous, such that for x, 11, T2 X and y, V1 82 E V
Eg V f21. - fx y: 1 < - 2:2 1|
Eg Vf vii fz 92: 12 < L 11y1 - y211
K3a L2 (2
2 gay where L3x = =21, + 6C 1 2pL, + 6C2 fy yuy p + 6C2 gay 13 [I,
3.2 VR-BIADAM ALGORITHM
In this subsection, propose accelerated version of BiAdam method (VR-BiAdam) by using the momentum- based variance reduced technique. Algorithmdddmonsttean the algorithmic frame- work of our -R-Biadam algorithm.
5

---

Under review as a conference paper at ICLR 2023
Algorithm 2 VR-BiAdan Algorithm
1: Input: T, K E N. parameters {7, X, tt, az 3t} and initial input ø1 E X and y1 E 3/
2: initialize: Draw K + independent samples & = (fi, St. St.................... , <K-11 and Cı, and then
compute 01 = V gz [I1, 91: (1), and W1 Vf(11, E1) generated from 6
3: for = .......,2 do
4: Generate adaptive matrices A, Raddd B, Rpxp;
5: #t+1 arg minzex { (w,, 2) + 1 27 (x xxx)² A&(x - 24)} and F++1 = It + n (#t+1 xr)):
6:
Øt+1 arg minyey {(v 8) + 1 y1)² Br(y y1) }. and yt+1 = yt + no(++1 - ye);
7: Draw K + 2 independent samples E(+1 = (f1+1, S1t1, ... -441 (-1) and S4+1;
8: Ur+1 = V (2 S041) + as+1) 11 - V va ye: St+1)];
9: Wr++1
V (((+i::++1ie+1)) + (1 3++1) Wi: V (x M65 Et+1)];
10:
end for
11:
Output: Chosen uniformly random from {Ie, 11
At the lines 8-9 of Algorithm 2 mate the stochastic partial derivatives Un and wy. For example, the estimator of partial derivative < f 9t-1) is defined
use the momentum-based variance reduced technique esti-
W++1 1
(e-
= -B++1 (e+1 + (1 B [w, + : -
Compared with the estimator W141 in Algorithm [ wx+1 Algorithm 2 adds the term (f Vf(e yri E(+1) to control the variances of estimator.
4
THEORETICAL ANALYSIS
In this section, we study the convergence properties of our algorithms (BiAdam and VR-BiAdam) under some mild conditions. All proofs are provided in the Appendix A.
4.1 ADDITIONAL MILD ASSUMPTIONS
The estimated stochastic partial derivative V f(a E) satisfies BE[ vi 5] = V v) + R(x, u), BeIlV V/(x,)) The stochastic partial derivative Vyg(2r, yr () satisfies
Assumption 6.
V yg, yi C)] = Vyg(z, v), Assumption 7. our algorithms, the adaptive matrices A, and B, for all 2 satisfy A, Z pla (p 0) and B, = blp (b., 2 b by > 0), respectively, where p, ba and by are appropriate positive numbers.
Vi Vug(z, y)11 s o².
Assumption iis commonly used in the stochastic bilevel optimization methods Ji et al. (202 Yang al. (2021): Khanduri al.) (202T). In the paper, we consider the general adaptive learning rates (including the coordinate- wise and global learning rates) for variable x and the global learning rate for variable y. Assumption 7 ensures that the adaptive matrices A, for all t 2 are positive definite as in Huang et al. (2021). Assumption 7 also guarantees the global adaptive matrices B, for all t 2 1 are positive definite and bounded. In fact, Assumption i mild. For example, in the problem minger> (z: { Ward et al. (2019) apply global adaptive learning rate to the update form 62_ + | (i bo > 0, > for all 2 1, which Zt-1 BB V f( Er-1 with B, b:lp and b, 2 ... 2 bo > 0. Li& & Orabona (2019); Cutkosky & Orabona (2019) use a global adaptive learning rate to the update form It+1 = 2t - ng./bo bt, where is stochastic gradient and b, = (w + Σi= [ (=)) k > 0, w > 0 and E (0, 1). which is equivalent to Ti+1
f(2, 1881-1 6i
3e = -
by
equivalent to the form
-,,," 9t with B, b, T and
b,
> 0. At the same time, the problem min f(z) [ff {)] approaches the stationary points, i.e., ff(x) = 0 or even V f(x { = for all ç. Thus, these global adaptive learning rates generally bounded, i.e., bn by b > 0 for all / 1.
by

---

Under review as a conference paper at ICLR 2023
4.2 USEFUL CONVERGENCE METRIC
In the subsection, we define a useful convergence metric for our algorithms and some useful lemmas. Lemma 5. Given gradient estimator W, is generated from Algorithms for all t 1, we have |10= - (=()))) < Lolly" (xte) y/ + 2 (1 Be)l
where r3 8(13 + Eg For our Algorithms 1 and 2 based on Lemma
C3 Lo Can 1,,02
we provide convergence metric TE[Ge,, defined as G. | - xxll + 22 - Vi(r,, ut)l + Lolly (xx) y/. vtll):
where the first two terms of Ge measure the convergence of the iteration solutions (.r ) and the last term measures the convergence of the iteration solutions {v. {y=)?-1-
Let de (x) = F0 A.x, we define a froxffuntiion (a.k.a., Bregman distance) Censor & Lent 1981
Censor & Zenios (992); Ghadimi et al. (016) associated with (2r) as follows:
Vi(2,, x4) (x) - [x+) + (V)) x - =m>] = 2 (z x,)" A.(x xz)-
xx))-
(8)
The line 5 of Algorithm| | or is equivalent to the following generalized projection problem:
Te+1 min (wrr,.) .²) + - Vi(a,, S
(9)
As in Ghadimi et al. (016)), we define generalized projected gradient Gx(m,, w1,7) = (x
Tt-1). At the same time, we define a gradient mapping Gx (ze, VF(xx),, = (x) - x/+1) with
1 vi(2z 7
2 = arg min zEX
(VF(=)), x) +
(10)
According to the Proposition of Ghadimi et al. (0016) we have |[xx(mr we,
Gx(x,, VF(2)), s [llV - well. Since 11 (Te, VF (zt), (1x We, 7)) + [1xx(1,, 7. - (x VF())) 7)I, have
( VF(a)), 7)1l < 11 (Ze, Wt, 7)1l [IVF((x)) - will
(11)
|1441 mx1l
+ p
221 We V f v1)l + Lo (x,) vill) G2.
where the last inequality holds by the above Lemma 5 Thus, our new convergence measure E is tighter than the standard gradient mapping [ [ Fzz;), 7) used in Hong et al. (2020). When
G. + O, we have [],, (F( + 0. where x, is stationary point or local minimum of
the bilevel problem equation Ghadimi al. (016); Hong et al. (220)).
4.3 CONVERGENCE ANALYSIS OF BIADAM ALGORITHM
In this subsection, we study the convergence properties of our BiAdam algorithm. The detailed proofs are provided the Appendix A.5
Theorem 1. Under the above Assumptions
2
in the Algorithm
1 given X C Rdd (1 (q,k) (czk)?),
(m++))//2 for all 2 O, at+1 117
Bt41
C2ll,. m Z max
k 0,
125L
C1 <
1/2
9
S C2 5.
1/2
min 15 4lfx oh,), 0 < 7
min
Voupp
m/2 and K
= Le log Log(Cany CaayyCry T T/p,, we have
Wo +1 1269 12
ALK
1
1
2 2/3Gmm/ 1/4 T1/2
2V3G T1/4
V2 Ō (
Ex VF(I.), Mi1
E|G.|
T
T
T
(12)
where G F(x1)-F"
+
5by 13 20
+
2nd 2
1(m+T) In(m+1)+
In
+ 8k 7T
and Do = 1111-y(011)
(x:))11
pkg
L3 = 125L.
121,,²²
+ 33
212

---

Under review as a conference paper at ICLR 2023
Remark 1. Without loss of generality, let k (1) and O(1), have G ( +
T)) Õ(1). Thus our BiAdam algorithm has a convergence rate of Ó (174). Let E(Gc]
+ - E[G.] = ( S we have T = O(E=t). Since our BiAdam algorithm only requires K + 2 Ls (gyTi)) + +2 Ó(1) samples to estimate stochastic partial derivatives in each iteration, and needs T iterations. Thus our BiAdam algorithm requires sample complexity of (K + 2)T = O(c=*) for finding an c-stationary point of the problem (7). Note that the conver- gence properties of our BiAdam algorithm for unconstrained bilevel optimization provided in the Appendix A.3
4.4 CONVERGENCE ANALYSIS OF VR-BIADAM ALGORITIM
In this subsection, we study convergence properties of our VR- algorithm. The detailed proofs are provided in the Appendix A.6
Theorem
2. Under the above Assumptions
7
3
2 given C Rdd c2lli. Z max (2, K. (crk)) (c2k)
in the Algorithm
Me
(m (m+))=73 for all 1.
k:
04
-cilli+
k
0,
3
2
125L
6p
02
2 34
+
0
<
X S min 15b b 16L 6Lg
0 < S
min
Gapp
m
m
and K
Le log ( yzy Cj T T/p) we have
24L22 x2 2 12562 Line
4LK
2v
3Mm 1/6
2/3M
V2
T
Gx VF(T)) mill S
T
B
T1/2
T1/3
T
=
Ō
T
(13)
where M P(z1)-F"
+
5b Li
+
2m o9
+
2x (cF+ In(m+T) +
6k(m+271//
Ao
11y1
y" (x1) 11 and I.2 pk7
p²T
12 L'x.
Remark 2. Without loss of generality, let = 0(1) and m = O(), we have M = (In(m +
T)) = =(). Thus our VR-BiAdam algorithm has a convergence rate of ((g Let B[gg] =
ΣL_ B[G.] ( I G, we have T Ō(E=3). Since our VR-BiAdam algorithm requires K + 2 = Lo log(CgnyyCy CJTT/P) + + Ō(1) samples estimate stochastic partial derivatives in 1
each iteration, and needs T iterations. Thus VR-BiAdam algorithm requires sample complexity of (K + + Ō(c=3) for finding c-stationary point of the problem (/). Note that the conver- gence properties of our VR-BiAdam algorithm for unconstrained bilevel optimization are provided in the Appendix
DSA
BSA
DSA
stocBIO
stocBiO
StocBIO
1.7
Validation Loss
SUSTAIN
Validation Loss
SUSTAINN
SUSTAIN
PSLA
FSLA
PSLA
VRBO
BiAdim VR-B-Adar
BiAdam
Validation
BlAdam
0./
VR-Bindam
VR-Diidam
6.9
6.9
0.4
0.5
20
10
15
20
Running Time (s)
Running Time (s)
Running Time (s)
Figure 1: Validation Loss vs. Running Time. We test three values of p: 0.8, 0.6, 0.2 from left to right. Larger value of p represents more noisy setting.
NUMERICAL EXPERIMENTS
In this section, we perform two hyper-paramedt optimization tasks to demonstrate the efficiency of our algorithms: 1) data hyper-cleaning task over the MNIST dataset; 2) hyper-representation learning task over the Omniglot dataset. In all experiments, we use a server with AMD EPYC 7763 64-Core CPU and I NVIDIA RTX A5000.
8

---

Under review as a conference paper at ICLR 2023
5.1 DATA HYPER-CLEANDE
In the hyper-cleaning task, we clean a noisy dataset through a bilevel formulation. The precise for- mulation of the problem is included in the Appendix A.I.I In particular, we use a training set and a validation set, where each contains 5000 images in our experiments. A portion of the training data are corrupted by randomly changing their labels, and we denote the portion of corrupted images as p. We compare our algorithms (i.e., BiAdam and VR-BiAdam) with various baselines. See the Appendix [A. for a brief introduction of the baselines. For all methods, we perform grid search over hyper- parameters and choose the best setting. The detailed experimental sctup is described in the Appendix A.I.I]] The experimental results are summarized in Figure | As shown by the fig- ure, our BiAdam algorithm outperforms its non-adaptive counterparts such as stocBiO, MRBO and SUSTAIN, furthermore, our VR-BiAdan gets the best performance, where it outperforms VRBO, which requires using large batch-sizes every a few iterations.
5.2 EMPER-REPRESENTATIUN LEARNING
In the syper-representation learning task, we Iearn a syper-representation of the data such that a linear classifier can be learned quickly with a small number of data samples. The precise formulation of the problem is included in Appendix AA.12 We compare our algorithms (i.e., BiAdam and VR- BiAdam) with various baselines. See Appendix A.. for brief introduction of the baselines. For all methods, we perform grid search over hyper-parameters and choose the best setting. The detailed experimental setup is described in the Appendix [A. The experimental results are summarized in Figure 2 As shown by the figure, both our BiAdam and VR-BiAdam algorithms outperform other baselines.
0.82
Test Accuracy
0.65
Tess_ Pecuraccy
0.85
E5A
BSA
madio
MARCCSUSTAR
M6S10//USTAN
HEBOOUSTAIN
RETEOISUSTAN FSLA
2:0-
VI8O
Slidam
BlAdor
V1-21kdam
VILBAAdU
Vi-Sidore
VO-0
06
23
40
20
42
20
60
20
60
Running Time 1s]
Running Time (5)
Running Time (4)
Running Time (5)
Figure 2: Test Accuracy es. Running Time. The plots corresponds 5-way- 5-way-5-shot, 20-way-1-shot and 20-way-5-shots from left to right.
6 CONCLUSIONS
In this paper, we proposed class of novel adaptive bilevel optimization methods for nonconvex- strongly-conver bilevel optimization problems. Our methods use unified adaptive matrices including many types of adaptive learning rates, and can flexibly use the momentum and variance reduced tech- niques. Moreover, we provided a useful convergence analysis framework for both the constrained and unconstrained bilevel optimization. Our VR-BiAdam algorithm reaches the best known sample complexity of Ö(E- for finding an e-stationary point.
REFERENCES
Yair Censor and Arnold Lent. An iterative row-action method for interval convex programming. Journal of Optimization theory and Applications, 34(3):321-353, 1981.
Yair Censor and Stavros Andrea Zenios. Proximal minimization algorithm withd-functions. Journal of Optimization Theory and Applications, 73(3):451-466) 1992.
Jinghui Chen, Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. Closing the generalization gap of adaptive gradient methods in training deep neural networks. arXiv preprint arXiv:1806.06700 081.880000066... 2018.
Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A single-timescale method for stochastic bilevel optimization. In International Conference on Artificial Intelligence and Statistics, pp- 2466-2488 2488. PMLR, 2022.

---

Under review as a conference paper at ICLR 2023
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. In 7th International Conference on Learning Represen- tations (ICLR), 2019.
Benoît Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Annals of operations research, 153(1):235-25) 256,, 2007.
Ashok Cutkosky and Francesco Orabona. Momentum- based 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. In Advances in Neural Information Processing Systems, 2022.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances neural information pro- cessing systems, 27, 2014.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Machine Learning. pp. 1568-1577. PMLR, 2018.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint 2018
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation meth- ods for nonconvex stochastic composite optimization. Mathematical 267-305, 2016.
ProgaattaaaaPPaPPaaiaaaa Programming, 155(1-2):
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.
Zhishuai Guo and Tianbao Yang. Randomized stochastic variance-reduced methods for stochastic bilevel optimization. arXiv preprint M...v:211S.022000 2021.
Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. A novel convergence analysis for algorithms of the adam family. arXiv preprint arXiv:2112.034555 2021a.
Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. stochastic moving-average
estimators for non-convex optimization. arXiv preprint arXiv:2104118444 2021b.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework
for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint 10x5 2020.
Feihu Huang, Junyi Li, and Heng Huang. Super- faster and universal framework of adaptive gradients. Advances in Neural Information Processing Systems, 0i49074-9085, 2021.
Kaiyi Ji and Yingbin Liang. Lower bounds and accelerated algorithms for bilevel optimization. arXiv preprint arXiv:2102.0392 2021.
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.
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang- A netr-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in Neural Information Processing Systems, 34:30271-30283 2021.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
10

---

Under review as a conference paper at ICLR 2023
Gautam Kunapuli, Kristin P Bennett, Jing Hu, and Jong-Shi Pang. Classification model selection via bilevel programming. Optimization Methods & Software, 23(4):475 489, 2008.
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, (0006266):1332-1333 2015.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (6(11):2278-2322 1998.
Junyi Li, Bin Gu, and Heng Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. arXiv preprint arXiv:2112. 2021.
Junyi Li, Feihu Huang, and Heng Huang. Local stochastic bilevel optimization with momentum- based variance reduction. arXiv preprint urXiv:2205.01608 2022.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 983- 992. PMLR, 2019.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint 17X6v:1806.0000
2018.
Risheng Liu, Jiaxin Gao, Jin Zhang. Deyu Meng, and Zhouchen Lin. Investigating bi-level optimiza- tion for learning and vision from a unified perspective: A survey and beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021a.
Risheng Liu, Yaohua Liu, Shangzhi Zeng, and Jin Zhang. Towards gradient- based bilevel optimiza- tion with non-convex followers and beyond. Advances in Neural Information Processing Systems, 34:8662-8675, 2021b.
Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A general descent aggrega- tion framework for gradient-based bi-level optimization. IEEE Transactions Pattern Analysis and Machine Intelligence 2022.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Confer- ence on Learning Representations, 2018.
Songtao Lu, Xiaodong Cui, Mark Squillante, Brian Kingsbury, and Lior Horesh. Decentralized bilevel optimization for personalized client learning. In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5543-5547. IEEE, 2022.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv
preprint arXiv:1904.092.. 2019.
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back-propag for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1723-1732. PMLR, 2019.
Davoud Atace Tarzanagh, Mingchen Li, Christos Thrampoulidis, and Samet Oymak. Fednest: Fed- erated bilevel, minimax, and compositional optimization. arXiv preprint arXiv:2205.022133 2022.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. In International Conference on Machine Learning, pp. 6677-6686. PMLR, 2019.
Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. Ad- vances Neural Information Processing Systems, 34:13670-136888 13682, 2021.
Yihua Zhang, Guanhuan Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, and Sijia Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. arXiv preprint arXiv:21 12376, 2021.
Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar C Tatikonda, Nicha Dvomek, Xenophon Pa- pademetris, and James Duncan. Adabelief optimizer: Adapting stepsizes by the belief in observed gradients. Advances in neural information processing systems, 13:18795-1888 2020.
11

---

Under review as a conference paper at ICLR 2023
A APPENDIX
In this section, we provide the additional experiment results, related works and additional theoretical results. We also provide the detailed convergence analysis.
A.1 ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS
In this subsection, we introduce more details of our experiments. We compare our BiAdam and VR- B--dddda algorithms with the following bilevel optimization algorithms: reverse Fransssschh et al.
2018), AID-CG Grazzi et al. (2020), AID-AD FrazzzzGiizaaa et al. (2020), stoc al. 20.1)), MRBOJi
& Liang 2021). VRBOU: & Liang (202T), FSLA ct 2021 MSTSA/SUSSAIN K Khanduri et al.
2021
SMB Guo et al. (2021b). SVRB Guo & Yang (2021).
A.1.1 DATA HYPER-CLEANDAL CLEANING
In this task, we perform data hyper-cleaning over the MNIST dataset LeCun et al. (9988 The formulation of this problem is as follows:
min feal (T, wown"(1 (T))
1
E
fa1 (T),
Dvvl
(e
s.t. w²( = arg min for w)) = Drl
1
Σ
((T)f((f w. v.) C/|
(a:a))EnT
where J(() denotes the cross entropy loss, DJ and Dy are training and validation dataset, respec- tively. Here r = {T+ JED, are hyper-parametert and C' 2 0 is a tuning parameter, o--) denotes the sigmoid function. In the experiment, set C = 0.001.
For training/validation batch-size, we use batch-size of 32, while for VRBO, we choose larger batch- size 5000 and sampling interval is set as 3. For AID-FP, AID-CG and reverse, we use the warm-start trick as our algorithms, i.e. the inner variable starts from the state last iteration. We fine tune the number of inner-loop iterations and set it to be 50 for these algorithms. For MRBO, VRBO, SUSTAIN and our TTAAdam/VR-BiAdaa
we set K = 3 to evaluate the hyper-gradient. For FSLA, K as the hyper-gradient is evaluated recursively. As for learning rates, we set 1000 as the outer learning rate for all algorithms except our algorithms which use 0.5 as we change the learning rate adaptively. As for the inner learning rates, we set the stepsize as 0.05 for reverse, AID-CG, stocBiO/AID FP, MRBO/SUSTAIN FSLA; we set the stepsize as 0.2 for VRBO; we set the stepsize as for SUSTAIN; we set the stepsize as 0.00025 for BiAdam and 0.0005 for VR-BiAdam.
A.1.2 HYPER SNTER--EEPESENNTTTION LEARNING
In this task, we perform the hyper-representation learning task over the Omniglot dataset Lake et al. 2015). The formulation of this problem is as follows:
min feas (T, n (T) = EE [frat (T, w (T): = Dv.el
Σ
f((W)) ((CT)))(TTT))))
s.t. w" (T) arg min for (T, (T) [DT
1
Σ
S(wJ (()G)) v.) ) Cllwl]
where f()) denotes the cross entropy loss, Dr.g and Dv.e are training and validation dataset for randomly sampled meta task. Here {TiliED, are ayperrrepresenttaion and C' 2 is tuning parameter to gaurantee the inner problem to be strongly convex. In experiment, we set C = 0.01.
In every hyper-iteration, we choose 4 meta tasks, while for VRBO, we choose larger batch-size 16 and sampling interval is set as 3. For StocBiO/AID-FP, AID-CG and reverse, we use the warm- start trick as our algorithms, i.e. the inner variable starts from the state of last iteration. We fine tune the number of inner-loop iterations and set it to be 16 for these algorithms. For MRBO, VRBO, SUSTAIN and our algorithms, we set K to evaluate the hyper-gradiem For FSLA, K = as the hyper-gradien is evaluated recursively. As for learning rates, we set 1000 the outer learning rate for all algorithms except our algorithms which use 0.001 as we change the learning rate adaptively. As for the inner learning rates, set the stepsize 0.4 for all algorithms.
12

---

Under review as a conference paper at ICLR 2023
A.2
RELATED WORKS
In this subsection, overview the existing bilevel optimization methods and adaptive methods for single-level optimization, respectively.
A.2.1 BILEVEL OPTIMIZATION METHODS
Bilevel optimization has shown successes in many machine learning problems with hierarchical structures such as policy optimization Hong et al. (2020), model-agnostic meta-learning Liu et al. (202 Ji et al. 2021); Lu et al. (2022) and adversarial training Zhang et al. (021). Thus, its
researches have become active in the machine learning community, and some bilevel optimization methods recently have been proposed. For example, one class of successful methods Colson et al.
(2007) Kunapuli al. (2008) are to reformulate the bilevel problem as single-level problem by replacing the inner problem by its optimality conditions. Another class of successful methods Ghadimi & Wang (2018); Hong et al. (2020); Ji et al. (202T); [Chen et al. (2022): : Khanduri et al.
(2021): Guo & Yangl (2021); Liu et al. (2021b bb 2022) Li al. (2021) for bilevel optimization are to iteratively approximate the (stochastic) gradient of the outer problem either in forward or backward. Specifically, Liu et al. (2022) proposed general madient-based descent aggregation framework for bilevel optimization. Moreover, the non-asymptotic analysis of these gradient- based bilevel optimization methods has been recently studied. For example, Ghadimi & Wang (2018) first studied the sample complexity of O(e of the proposed double-loop algorithm for the bilevel problem ① (Please Table DT. Subsequently, Ji al. (202T) proposed an accelerated double-loop algorithm that reaches the sample complexity of O(e relying on large batches. At the same time, Hong et al. (2020) studied a single-lopp algorithm that reaches the sample complexity of O(e without relying on large batches. Moreover, Khanduri et al. (202T); Guo & Yang (2021); Yang et al. (Khanuuri
(202T) proposed a class of accelerated single-loop methods for the bilevel problem (1) by using momentum-based variance reduced technique, which achieve the best known sample complexity of ((E More recently, Dagréou et al. (2022) proposed a novel framework for bilevel optimization
based the linear system. Meanwhile, Lu al. (2022): Li et al. (002);; Tarzanagh al. (2022)
studied the distributed bilevel optimization.
A.2.2 ADAPTIVE GRADIENT METHODS
Adaptive gradient methods recently have been shown great successes in current machine learning problems such training Deep Neural Networks (DNNs). Recently, thus many adaptive gradient
methods Duchi et al. (201)) Kingma Kinngma & have been developed and studied. For example, Adagrad et al. (2011) the first adaptive gradient method that shows good performances under the sparse gradient setting. One variant of
& (001:) Zhuang et al. (2020)
Adagrad, i.e., Adam Kingma & Ba (2014) is very popular adaptive gradient method and basically is default method of choice for training DNNs. Subsequently, some variants of Adam algorithm
Reddi et al. (019)) Chen et al. (2019) have been developed and studied, and especially they have convergence guarantee under the nonconvex setting. At the same time, some adaptive gradient methods Loshchilov & Hutter (2018); Chen et al. (2018); Zhuang et al. (2020) have been presented to improve the generalization performance of Adam algorithm. The norm version of AdaGrad (i.e., AdaGrad-Norm) Ward et al.] (2019) has been presented to accelerate AdaGrad without sacrificing generalization. Moreover, some accelerated adaptive gradient methods such as STORM Cutkosky & Orabona (2019) and SUPER-ADA Huang et al. (2021) have been proposed by using variance- reduced technique. Meanwhile, HHang al. (2021): b:; Guo et al. (2021a) studied the convergence analysis framework for adaptive gradient methods.
A.3 ADDITIONAL THEORETICAL RESULTS
In this subsection, we further give the convergence properties of our BiAdam algorithm for uncon- strained bilevel optimization.
Theorem 3. Under the above Assumptions
2
in the Algorithum
1 given X = Rdd,
n (m+0)1/2 for all t > O, a1+1 C17),
B1+1
C2Tb, m
max
(T (cIk)? (c)k)
k > 0. 12512
< C1
< m 2
<
< m
1/2 b
0
min
15 b 0 < ?
4L7F öL,
13

---

Under review as a conference paper at ICLR 2023
min
Vodup G
1/2 2) ALK
and K
Le
fo we have
E E A.l2
(266G'
2v6G'
2v3 = = -((TiA)) (14)
E V
T1/1 +
P
T1/2
where G p(F(w))-FT
1 54
20
2mo2 In(m + TT)
1(m+T)
8k T..
kAp
9KT
Remark 3. Under the same conditions in Theorem based on the metric BIVEFIV
our BiAdam algorithm still has gradient complexity of Ö(E=)) without relying the large hati-b Interestingly, the right hand side of the above inequality (4) includes a term
/ /EE E B.A. that can be seen
upper bound of the expected condition number of adap-
tive matrices {AitT=- When As given in the above (4), we have V GitA as in the existing adaptive gradient methods assuming the standard bounded stochastic gradient f[V e)l Gr.
Next, we further give the convergence properties of our VR-BiAdam algorithm for unconstrained bilevel optimization.
Theorem 4. Under the above Assumptions
7
7 in the Algorithm 2 given X Rdd
(m+1)173 for all t 2 0, Ou++1
&
P1+1
C2Tl. 2 max (2, l. (c (c2k))3)
C1
2
3k
1251. CH
C2
2
+ 8.
0
<
A S min 15b 2 16L2 ot,)) < S
min
VoAuo
m²/3
2 and K
Le log (0g(C Ctyy T/),, we have
22L2AR2 12562 L2KA
ALK
V + B|A111
V
E
(2V6M'm T1/2
2/6M
+
2/3
-( (15)
1
P
T
T
where M' p(F(a))-F") 5b 27
2/3
+ 2k- + 2)) In(m + TT) 6k(m+2)
Ky
kāp
k²
Remark 4. Clearly, the adaptive matrix A. generated from the above f we have
V+ E|A.
S GL+A X in the existing adaptive gradient methods assuming the standard
bounded stochastic gradient [VV((x E)ll S G1. Under the same conditions Theorem 2 based on the metric + ET F(x,)( (x:))l, our VR-BiAdam algorithm still has a convergence rate of Ō (17))
and sample complexity of Ö(=-3) without relying on the large mini tani-batches.
A.4 DETAILED CONVERGENCE ANALYSIS
In this subsection, we provide the detailed convergence analysis of our algorithms. We first review and provide some useful lemmas.
Given a p-strongly convex function (xx). we define a frox-function (Bregman distance) Censor & Lent 1981) Censor & Zenios 1192 associated with <(x) follows:
V(z, x) d(=) - [Ø(x) + (Vo(x), = x;)].
(16)
Then we define generalized projection problem as in Ghadimi et al. (2016):
x² = arg min { (2, w) + ((z,a)) - h(z)}.
(17)
sEX
?
where C Rd, w Rd and 7 > 0. Here h(x) is convex and possibly nonsmooth function. At the same time, we define generalized gradient as follows:
1
(x(x, w. 7) = (xr x²).
(18)
14

---

Under review as a conference paper at ICLR 2023
Lemma 6. (Lemma I in Ghadimi et al. (2016)) Let x' be given in 17 Then, for any X, w E IR and y > O, we have
(w, (x(x, 2 (1, w, m) - 11(1x)))) h(=)),
(19)
where p > depends on p-strongly convex function ((x).
When f(xx) in the above lemma we have
(w. (2, w. 7)) 2 11 ",, m)1
(20)
Lemma 7. (Restatement of Lemma 5) When the gradient estimator we generated from Algorithm or 2 for all i. 2 have
| VF(x))1 (xl))((x))
- -/ 21|w; (.r wc)l?
(21)
where I3 8(13 +
2 12a
or 12 C
Gap 13,02.. a
11a
Proof.
We first consider the term have
VF(x,))
fx v.)1 Since Vf(2, (x,))) = VF(x;), we
[VL (xx)) (5 wi)l
|V (x:)) - Vegg(er (am) "aah "V.
Vef(z,, 91) + V2 ( 81 V ( Vyyf(r,,
VV (z,) - - -
(V "(e
+ Vyyl /1 { -/a (V "v,
,,,,,, (x:))
2 2 v1
11 9))
V V vy 31 (V V
2 2zg9(ar 1/1)
4C7 12
V V (xx))
1
(xx))
V2 (
4
402 40
C2
4C2
gay 1
ft1
2 Poyg(zn ( (zx) pogg(E v1)1
Wuf( (zx) V vyf v0l
122
L2 C2
Low gay C7
13
< <4(L
gzy
)112" (xx)
1
112
n2
-I"Ill"(ze) voll..
(22)
where the second last inequality is due to Assumptions L + L2 C2 + 1 C Ciy 1.
2 and
4
the last equality holds by I
11
Then we have
VF(2))] I|w; (f(x,)))) B1) -
S 21
vf 2 ve) vF(2))]
< 2||
Vs(r, + - 12112.
(23)
Lemma 8. Under the Assumptions
4
we have
[V M(41))))))))))))))
Vf < L3 [1]
xell2 + 11 -vel3))
(24)
where T2 12==80 8(1,
12200 C2,
12
02
02
13,0
"
15

---

Under review as a conference paper at ICLR 2023
Proof.
(Te11, (2t,
[V=5(2t421(+11) - V 1 14 ( (V
(1+11 V vf ff(+11111111
Vxf(zz, 21) + V my ( y1 V (x 3e)) V vg wt)1
( 91+11 (,',, )1.)
V 1y y1+ ( V y1+ (
+ V 21 y1
V (0y
wy
+ 2 2z y1
V
20))
V (. Uc+1)
- 22
(V Ff F
+ V (Zr, y1
(1,, (1)1
4C,
41| / (xr,
fy
IV ( V (2g
112
4C2 goy
4C
sy (1(41,14111)))) - V sog 112 +
gay
V VyJ (11+1,064+11 V (x,, (1)1
112
812
C7
8T
-zell + |1 - -ell?) +
gay
(110+11 =x+|2 2 + || - vellz)
112
SL2
C2 CRany O7 (1|02+1 - -zel1 - yell3)
812,
an9
yow n²
(11:241 xrll? 3011 I1 yell 11)
11
-. (1|+++1 21 + 11bt+1 1=1l)),
(25)
where the first inequality holds by the Assumptions | and and the second inequality holds by the Assumption 2
Lemma 9. Suppose that the sequence {xi, Me FT-1 be generated from Algorithm or Let O <
l S and S 2Lmz
_ then we have
+ Th? F(1++1) S F(x.)
IVF()) - well=
Pile 27
|
x2e12
(26)
P
Proof. According to Lemma 2 the function F(x) is L-smooth. Thus we have
L stll2 -2al22
F(*+1) F(xx) (VF [VF())), xx)
||
(27)
2
L
=F(x)) + (VF (z)). mo (Tc+1 z1)) 2
[8141 x2)11
Lub
=((x)) + mi (w,, ē141 zz) the (F()))
We, #c-1 -21)
| 12l1?
2
=12
where the second equality is due Ft+1 = It + 9 (5++1 I².). According to Assumption 7 i.e., A, > pIa for any t 2 1, the function (.(x) = f A,x is p-
strongly convex, then we derine a prox- frox-function (a.k.a. Bregman distance) associated with (x) as in Censor & Zenios (1992); Ghadimi et al. (2016).
1 (x= xT Ax(x - xz))
Va xx) = (x()) - [0)(x,) + (Vo,(;;), x xz)] = 2
(28)
By using the above Lemma to the problem क[+1 arg argmingex { (ww,, x)) J/2 (x- 2T. (x
at the line of Algorithm for we have
1 (#t ((t1)) 2 pll (xx 1111)11
{wee 7
(29)
16

---

Under review as a conference paper at ICLR 2023
Then obtain
T (wi, R141 - -xt) S -1 -x+1l x2.1?
(30)
Next, consider the bound of the term 72, we have
T2 = (vF())) - wt; Tz+1 - rit)
2 [V(())) w. ||ā2 Izel
- 2 (VF(tt) - well + 47
l1 Iee
(31)
where the first inequality is due the Sehwary inequality and the last is due Young's inequality, By combining the above inequalities (27). (30) with (3I). we obtain
Luf
F(I(+1)= S F(xs) + (VF(z)) We: Tt+1 xx) + The ne(we; Ex+1 - xze) +
| xell
< F(r)) + 7
(F():)) wel1 +
PM
| - 22e1 pTl
| - -=zel2 + Lif
||
34
47
2
= F(.))) + 7 VVF(x)) well
|T++1 - 2z 11?
(
PT
Lnf
)|ā2+11 - xell?
27
47
2
< F(.)) + TEY (x;)) well
PM
|5++1
(32)
24
where the last inequality is due to < 7 S
0
2
Lemma 10. Suppose the sequence {It, yt Ve be generated Algorithm or 2 Under the above assumptions, given have
1/e S 1, B, = Ip p (bn 2 be 2 b 0) for all i. 1, and S GLg' we
M7tle 4b,
3nd
11 - (1(41)))
llye y" (1())11--
110+11 - 3ell2
4
25m A 6pb,
25x²n;
| Vyg(Ees U1) -.112
|| 2211
(33)
where K = Lg/Hu.
Proof. According Assumption
[
i.e., the function g(z, y) is y-strongly convex W.I.t y, we have
g( v) 2 g(z,, v1) + (Vgg(rs,Vi) vc), v1) + 2 ly - yell²
= gg wt) + (v., M(+1) + VV (z vt) Ue y - T1+1)
+ (V (0 1/), 0r+1 yn) + _
ly - well?
(34)
According to the Assumption 2 i... the function g(x, y) is Ly smooth, we have
g( D(t1) I g(2,, wi + (V Vyg((r, ve), Me+1 ve) + Tug |1 11.12.
(35)
2
Combining the about inequalities (34 with (35). we have
( v) g(xe, xt+1) + (w/, y/ 11+1) + (Vgl(re, ve) - v. (1t2)
+ 1 y vel12
Ly
11
(36)
2
By the optimality condition of the problem Øt+1 arg min (1r, v) 2x 2x(1 wz) B. yt
the line 6 of Algorithm or given B, b, Tp we have
b (Te+1 vr), y Tnt1) 20 Vy E.
(Ur + x
(37)
17

---

Under review as a conference paper at ICLR 2023
Then obtain
(vr.y Do+1) 2
(0t+1 Vt, U6-1 -1)
by
br (0c+1 - Ud. 1).
11 3ell2 + A
(38)
By pugging the inequalities 38 into 36 we have
bt (āe+1 yt, Ut - y) + by |1ūt+1 -vell
v) 2 g 01+1)
VVgg(ar 3e) u D1+1)
L 2
ll yell?
L 11:0+11 3ell?
(39)
Let y y" (zt), then we have
g(v,, v (xx)) 2 ( De+1 1) + by -/2 (Dt+1 yr, yt (xx)) + bq Lg >1lbeemm - yell?
x
2
+ V V ve) vt, v² (xxe - v(+1) + _ (x1) - yell?
(40)
2
Due to the strongly-convexity of g( v) and y (*())) g( y² (x+)) I g(2,, Mc11). Thus, we obtain
aigminyey g( v). we have
be \
0
(Je+1 ye, V1 y² (xx)) + (Vgg(E v1) vx,) - x(+1)
+ x
b
well² -
_ (xx)) -vel2.
(xx)
(41)
2
2
By Me+1 = + m (āt+1 )t), we have
|| y² (xx))1² = 11 + n/ (ūr++ - We) - 11" (xx))l²
11ye y (xx))12 + 2n7 (ūc+1 yc Vi -y- (xxx)) + n1bl11111 -eel (42)
Then we obtain
(0e+1 ye, U - (x+))
1 1luet1 (xx)))11
11ye - 3² (xx))11 ne l1 11112. (43) 217.
1
2Tp.
Consider the upper bound of the term (Vgl(ze, ve) ve, (xx) - (ltz),, we have
Vug(Ee v1) - Vt, v² (xx) - 1(+1)
(Voo(Ie vi) ve. (x,) - y1) + (V y1) 1/, ft De41)
2 | Vor - =, + (Il= vr112 | V xz, (z,,gr) - -2all2- 14 4lu. Fe+ill
4
Vyg((r ve) - v,1 4
L Ily" (mre) vell?
# 11ve To+1 112
(44)
"
By plugging the inequalities 43 and 44 into
we obtain
b.
|1 (xx))1
2m
x
b
4 Illve y² (x:) +
Lg
by M - 12ll2 Vyg(E,,)))) v1) - -vzl 11
2
+
+
2m
2X
2
/
bi
1 / Ilve 3² (xt)]1 +
3Lg
11
11112
+ 2 2 AiV.g((r.) vr) vz
2mp
4
2A
/
b,
a Illee (xx))1
3b,
b,
3Lg
2
= 2
4
82
+
8A
4
)1
vell2 +
V V we) - v2122
b,
m Ilve "² (xt))1
3b,
|
2ell2
+
2
Vug(ze, v.) u
(45)
2m
8A
18

---

Under review as a conference paper at ICLR 2023
where the second inequality holds by Lg 2 a and 0 ? and the last inequality is due to 0 < X
I by It implies that 6
by
3tt
4n
l1++1 - y (1))l = =11-
llee - y (2xx))1²- 2b,
11 - yell? +
V Vog( ve) - -v/l?
4
pbl
(46)
Next, we decompose the term |l y² 1I2 as follows:
Ilu+11 3" (#1+1)ll2
= || y (xi) + (xxe - 8" (2++1)ll
= ||ve+1 v (xx)) 2 + 2(Uc+1 V" (xx), v (xr) - v² (f(+1)) + 1111" (xxe) y (1++1)ll
- (1 + neHddd )lBcc+1 - y" (x,))1² + (1 + 4br
(x+) y2 (I(+1)l1
4b;
51 + MepA - (x,))1 + (1
4b:
-
)k² 1|=
xe+1l1?
(47)
4b,
where the first inequality holds by Cauchy-Schwarz inequality and Young's inequality, and the sec- ond inequality is due to Lemma 3 and the last equality holds by I++1 24 + (T 21).
By combining the above inequalities (46) and (47). we have
[lue+1 - 5/ (12+1))1 < (1 + 17.1e
V1paad 2b.
MeHLr 31/t
4b, )11
)lvve v =2x))
1
yell
4b;
+ (1 + Mud 4n
4bc
V Vvg(z,, ye) -vel2 + (1
)x² A|1Ez re+1 112
4b; pbc
Since 0 Th
S 1,
by_ ووا
and Lg 2 u. we have X S
b
and ne S 1 S
b
6L1g
64g
by
Then we have
Neftdd
Mtslr
1221222
(1 +
)
S
4b;
26
2b.
4b,
8b7
4b,
3mt
3tpt
(1
4b;
+ 7HA 41/1
4n/AA
25m
(1
$ (1
4b,
μb;
24
pb,
6Hb,
4b
bik²
4brk²
k5b,
(1 +
)n²²
TepeA
where the second last inequality is due to maa
<
and the last inequality holds by ondm 2 1. By
b.
h,
using J++11 It. + 7) (Te+1 w.)), then we have
MajM
3nt
11 - v² (1141))1 < (1
llye
y² =xx))1²==
110e41 - 30ll2
4b,
4
25 A +
25x²n1
| Vyg(Ee, v.) -u.12
|1
xz, 11.
(48)
6pb,
A.5 CONVERGENCE ANALYSIS OF BIADAM ALGORITHM
In the subsection, we provide the detail convergence analysis of BiAdam algorithm. For notational simplicity, let R2 R(x,, y1) for all 2 1.
Lemma 11. Assume that the stochastic partial derivatives Vt+1, and Wi+1 be generated from Algo- rithm 7 we have
Wc+1 V.(I 1++1) Re+1l1 < (1 Be+1 || We - Vf v1) - Roll + S (49)
3L2ME
+
(1ix - =x + 1lū++1 - vxll
B
3
R1 + [|R
B
19

---

Under review as a conference paper at ICLR 2023
E Blee411 (000x+11.1++2111 s (1 acte) Vug(ze, v1)l + 1
(50)
+ +2 /0441 (Bll@z+1 =ell² Bllie++ - -vell",
Ci 1
Li San St
1: and R. Vf ut) - VglVf(0e, Mes Vei
where Lg = 8((3 + for all t 2 1.
Proof. Without loss of generality, we only prove the term El Vf(++1, M(+1) 1121 The other term is similar for this term. Since wp+1 = Be+1 Ve ((41) + +11 - Be+ Ww,, we have
wl V (1E+11 Rut2l
(51)
B| i 11
(1 B1+1) (f(2441 - 112
[1 32+1)(w: (I( W1) -Ra) + Be+1 (2441, (I Mt+1) R(+1)
+ (1 (e+ (7 (Ie, M1) Rs - (V v1+1) + 11
= - EI| / / [++++ Br+ E1+1 - ([(=++ B(+1) - Re+1l 1|2
+ E][(1 - 3 () Wm Vf(zz, y1) - Rs + f + Rs- - (V + 12+
$ 1/ F / (1++1, 11:1: [ Mc+1 Re+1l + (1 - B(+1 ) B 1l Vs(e, Rell?
+ (1 B++1) (1 B0+1 EE| V ( V + R - ( (2 Vo+1) + Re+1)l1
1
$ (1 3 E we vf(r v.) R1112 2 + 04 +
Vf(zz, v1) + Re- (Vf(eo+1. + 1
Bi+1
(1 Be+1 )E| we ()(r)))) Rell 2 + 8441
3
+ Br+1
| ( - (F( 311 + Be-l
(1Rol1++ + +||+++11113
3
(1 Bo+1) Bo+1) w// (1rr))))) 2 + 844102
(1| 1| + [| 112)
Be41
3L B,41 (1ı241- - r2l12 + || -2ell))
(52)
where the third equality is due to Es,,, 1V f (0:e+1,,041:4441.. = (f M(+1) + Ri41; the
second last inequality holds by 0 I BB+1 I 1 such that (1 - (1 Be41) = - -B++1 B8 +
19-1 < 1 - B.41 and (1 -1-33 Be+ 12 + ) < (1 Be+1 (1 + Pe-1) -3c-1 + Dets < Det1*
and the last inequality holds by the above Lemma and #++1 = Ft + ne - xz), ye+1
Vc + nh (ū++1 ye).
Theorem 5. (Restatement of Theorem 1) Under the above Assumptions
1
2
in the
Algorithm given X C Rd, T)
(m++)117 for all 2 0, a1+1
C1
3t+1
C2T)
m
2 max (R², (crk), (c2k)?), (czk)) k v Vaapp
125L
6p
G1
m 1/2
2
I C2 S
1/2
0
< X s
min
L5 ALfF GLg)), 0 < 7 S min
m
and K = La log Cog(Cooy gay C T/P).
6 61 1252 13
4Lk
we have
T
T Elg.]
2 2 3/4
2V3G
v2
Σ
E E VF(..), S T
+ 71/4
+
(53)
T
T1/2
T
1=1
1=1
where G F(
pky
20² pak +
2mo² p*k
In(m + T) + 4(m+7)
9p2kT2
+
p²T,
8k
An ll
y² (x1)
and [.
12
125L.
+
213
3
Proof. Since ft. (1+77 on is decreasing and m 2 k2, we have 7tt S 110 = mi/z < 1 and
7 < 1/2 < 2Lr S 2i. for any 2 0. Due to m S and 2 kc, we have
ALK
20

---

According to Lemma 11 we have Under review as a conference paper at ICLR 2023
ac+1 017 - o m
I 1. Similarly, due to 2 (c2k)?, have B141 S 1. At the same time,
have c2, 02 k
E El|1++1 V
10( Me B V V2g(Fr,
(54)
-11 ug Me) vell + 2 nt/////// ca [8++1 22. + 10++1 - yell3) + eE
125L
E ( wc) v.112 12L3 T1
mnn 0²
(1ā741
xxll? 10++1 well?)
6p²
125
k
where the above equality holds by 04++1 = C17t,, and the last inequality due to Similarly, we have
125 6Fz
S
01
S
1/2
B 111+1 (f Me+1) R141 1|2
BBllw: Vf(Iz, Mc) -Rell
(55)
3L
S -Be+1 BBllu {s(ee 12.12
(11ē+41 - -xell² + -111t+11 - well
Be+1
3
(1122112 2 + [|[Be+111]] + 02410²
Bi+1
977
2L (101+1-2011*
Bllw; Vf v1) Rell2 +
xx11 aell++.. 11 yoll3)
2 (||
|| 12) mn, o²
31)²
k22
where the last inequality holds by ßi+1 come and /82 S < m²/2
According to Lemmas
andd 9 we have
F(1441) Fxx)
(56)
S ||., - V.(e, 2=)1 Laner 11 (are) - -1/112 PT)
20177
1 - xeel2
27
< 4mx7 ||,, (s(r)))) Rell2 + 4ne7 || Re + L8n1 (xx)) -vell2
ptpe
Jo+1 - 2: 2x112
2
According to Lemma 10 we have
Iluet1 - y² (x++1))1 llve - y (2:)))2
(57)
< MMd live 1² 3=xx))13-
37/,
25mA
25m2
1ū++1
1el1 +
V
Vug(ze, v1)
vell2 +
18+11
xz
4b,
4
6pbr
Next, we define a Lyapunov function (i.e., potential function), for any 2
T, = E[F(x:) + 56.
llve - v" (2x))12+ I 2 - Veg(or. w1l1 1| Vs(2, Rell3)].
App
21

---

Under review as a conference paper at ICLR 2023
For notational simplicity, let L3
12L 1251/
+
214
3
Then we have
T4+1- - Lt.
=((x+1)= - F(xe)+ +
(llue11 (x(+1))11 11ye y- (x=))l²)
? ((leett V ( M++1)ll 1
AMp
-1let Vug(Fe, w1)1 + || 7f(14+1. RR+2 1| 11:0e
Vf(ze, ve) Roll²)
LOneY
11y" (xxe yell2=
4 1
Vf( Me) -Rall 112 4
|Rlll
pi
|| =111?
p
2y
5by 1.gy
(- Muld
3/
1i++1 yell² + 25m X
Vug yv8 vell + 25n2m
11
|
11 sell?
App
4b;
4
V Vyg(ze, 31) - uel12 + 12Lzumm
(11 - zel1 + 11 - 8ell + m
7
+
E
125LØ
h2
9T7t
2L
man 0²
Bllue Vf(z,, Ue) - 12 + 3
(1(æ(+1 x211?
+ |1ūc+1 - wellz) + (1 + || +
2
3m/-
k.2
7/
(xx)))1
+2Bl|w: V
(s(t,
Rell3
Li7
125
L3x²
1) 1) |1
xx,
4p
2
P
6p222p
I,g) ) well
2myo²
27
41p:77
1/
2
(1|
+ || 12)) +
||
4xpp
p
k2p
3pm
P
7h
Loll:r 5/ (xx)))1 + +2Bl|u: A (11,,
Rell?
pTl
2m
1i
2
4p
47
k2p
27
(1I + [| + 4n | ||
+
(58)
3pm:
where the first inequality holds by the above inequalities (54). 555
(56)
and
(57p: the last inequality
is due to 0 7 V81:A2222 LiNZ
/6Xup
J6Aup
0 X
15b, 1
< 15b, 12 for all
1226p
427
427a
t t 1.
Let 4; = Lāll - y² +
+ 2||
VI vt) - -Rell
2 we have
7 Φb.
PT]
| 2:l12 < r, Te+1 +
2myo²
th
27
(1 + ||
49y7t ||
|
4p
47
k2p
3pm:
P
(59)
Taking average over i = 1,2,,.. on both sides of
59 we have
T1 Φ
p2m
(T, T(41)
1
2mo²
E
|+++1
122 m
T
472
T7
T
2
+
[[] + || 112) + 477 Re
3mp
Given E X and y1 V. let Ao llva y² (x11) )11
we have
r B(xr)( + 5b L67
- 5"(1))1 22 21v1 To((e1)111 +|| - Vf(ai, - R4 [13]
Ay4p
5b L37
270²
S F(x)) +
+
(60)
A
P
22

---

Under review as a conference paper at ICLR 2023
where the last inequality holds by Assumption 2
Since n/ is decreasing on i.., "T 1 2 1 for
any 0 I t
v T, we have
T
1
E2
P
T241 - xillz)
T
4
1=1
P
Σ
T
(T -((t1) +
1
Σ
T
2mo²
1
2
(I|Rg)
12
|Ret1l13) + 4m RRll
TyiT
T'T
h2
11
T
317;
1=1
1=1
1=1
TAm
P
(F(11)+
5bO 1
App
270²
P
F*)
TTT
1
2mo²
k2
1
2
3T
2
1/p
+
T
4
m
((F(z1)-1 -F
5b 13
20
2mo²
T
k2
2
(m + 122//2
+
+
dt
+
dt
ThTT
Tm
Tmr
Tirk22
m+t
37
k
4 [T
k
dt
T 11 (m 1)2/2
(((11)) - FF
5b 5b,
20
2mo²
8k
In(m + T) +
(m + T))//2
(m + TT 1/2 1/2
TYTT
Au
Tut
TIT
9KT
'
p(F (Z1)) - -F)
5b L3A0
202
2mo²
k In(m + T) + 4(m + T)
8k) T
(m + T)
key +
+
+
+
kdp
k
9k7
T
where the second inequality holds by the above inequality (60) and |ell
S F(m))
1
for all 2 1 by
T
choosing K Le log(O C/yT/H) in Algorithm
Let G
pby
F"
5b,
p=
+
20
p²
+
2mo² In(m + T) 9p²kT2 p2T: we have
1(m+T) 8k
n²k
G 1=ll3] 1
E 4p2
|8
s (m T)2/2.
(61)
4,2
According to the Jensen's 's inequality, we have
E
To41
xell +
1
(Lo l1yee (xx))) V2llur (s(r, Rell]]
T
27
2p
3
LE
2
1/2
<
|++1
xz 12 +
11 - 2² (xxe)12 +
Bllus - V5 21) - -R+113)
T 1=1
172
4p2
4p2
3 T
1
1/2
|1 - -xel?))
=
T 1=1
402
3G
1/4m!/4
V3G
(m
TT
(62)
T1/
T1/2
T1/4
where the last inequality is due to (a + 6)1/4 < 1/4 + +0/4 for all a, b 0. Thus we have
T
E 1
2.1l+
(Lollvr - 3² (²x))) + V2llur Vf v.) Rell)
2/33m
2V3G
(63)
T1/2
T1/1
23

---

Under review as a conference paper at ICLR 2023
Since ||w. obtain
V f 91)
Rell 2 ||1, Vf(I willl
||Rlll. by the above inequality 63 can
T
x+|1 + 1 (Tolllue - 1" (x+)) + V2[l
E[G.]
E
|
2/3Gm2/4
2V3G
V2 T
T1/4 +
Σ
E B|
T1/2
T
t=1
2/30m
2/3G
v2
T1/4 +
(64)
T1/2
T
where the last inequality is due to R S + for all 2 1 by choosing K
Le log Cy
Algorithm D
According to the above inequality [TT we have
T
2v3Gm 1/4
2V3G
v2
E (x VF(a.) 7011 T
B[Gd S
+
(65)
T
T1/2
71/4
T
Theorem 6. (Restatement of Theorem 3) Under the above Assumptions
7
2
4 6
in the
Algorithm 1 given X Rd 1)
(m++)17z for all 2 0, a++1
C177..
3++1
C2
m max (R2, (c) (cok)?). k O, 1251
6p
S C1
S
2
9
I
C2
1/2
0
< X
min
L5 4LiP 6Lg 0 < S min 22 + 1256 L8
2/2
and K
La Cog(Camy C T/P).
ALK
we have
1 T
ET T
E|AA,
2266'mm
2/6G' T1/4
2/3
(66)
P
T1/2
T
where G
((F(a))-F)) by
+
5b LeA
+
20"
+
2ma²
In(m + T) +
4(m+T)
+
8k
kdu
t
9kT
T
Proof. According to Lemma 7 we have
G.
00 T
+
Holly"(z)) - well + V2IV (I)) -wall)
1 / - will |I
||20 f+t1ll
0
||, well
F(+)( - will
1
|| will + p
|IVF((z)) - will
||l
1
[welll
[VFF(x)) w.ll
||A
|1xx11 +
||1| /VF(xt) - we
||
1
IV
||AII [VF(#)]]
(67)
where the equality (1) holds by Je+1 x, - -74,3 that can be easily obtained from the step 5
of Algorithm when X = Rdd, and the inequality (ii) holds by ||A+| 2 p for all > due to
Assumption Then we have
|F(())] S ||A, 19
(68)
24

---

Under review as a conference paper at ICLR 2023
According to Cauchy-Schwarzz Schwarz inequality, we have
T B
T
1
1 S T
1
1
V
B[G.I
-
B
Σ tm
B
A, 13.
(69)
T
T 1=1
T
Then we have
T
E
T
E
3Lg
M/
Vy" (x+)))
G||u, Vs(e, we)1
+ 72
3
| - xxel
T
T
p
P²
T
3Lg
11:
V
(x+))1
12 - Vs(ci, Me) - Rs 12
12 Rs
3
E
+
| - xx
T
P²
P²
72
1=1
24G
1
(m TT
T
T
p²
24G
12
$ T (m + T)
+
(70)
p²T2'
where the third inequality holds by the above inequality 66 + for all & 2 by choosing Lu Log(Cozy C CnyT (TTT
and the last inequality holds by
| s
By combining the inequalities 669 and 77
we have
1
E VF
S
E||A
+
Dr. Ar12
(2
(2V6G'm
2V66'
2v3
(71)
8
T1/2
T1/4
T
where G' = P²G
A.6 CONVERGENCE ANALYSIS OF VR VR-BIADAM ALGORITHM
In the subsection, we detail convergence analysis of VR-BiAdam algorithm.
Lemma 12. Under the above Assumptions and we be generated from Algorithmm 2 we have
assume the stochastic gradient estimators Ut
V Vyg( - 11+1 < (1 a E Vyg((,, 34. - 12/12 + 2a²_,0²
+ 4L [E| - Fell + Ell - -1:11))
(72)
11+11 (1(4411 Ret1ll 1|2 S (1- 3(41 3x41)Ellus, FE|lu,
V5 ve) - R2l12 + 2,3
4T 1/ (1 (1 - 1el + 11 yell 22)
(73)
gay where 1=x= =22 + 6C 1 2 + 6C
122
k + 602 L -I,
1º L2 kay
fy guy Ipl,
guy
(2uLg w2
Proof. Without loss of generality, we only prove the term Eljw441 Vf(I ((41) R241 The other term is similar for this term. Since wi+1 (/(mp1 E+t1) (1 (et1)(
25

---

Under review as a conference paper at ICLR 2023
Vf (c:t1))) we have
B|| - (I( Met1) - R
(74)
= ( + (1 -1- 16+1) f( (f - Ret1l 11
[5][(1 3 V vi) Ri) +
- Vf(Ie+1,)++11 - BR(+1)
(1 ( (V((E(-11 (5 9 - Ro+1 (Vf(2z, (()) - V5( Ve) R,))
= (1 - - 2 B|| - U1) R, 22 5 (V [1 M1+ 11:1: V
Re+1)
+ (1 - 11+1) ( ((+1) V--1
- R4
(V - vz( Ve) - -Ra))
$ - -1+1) 2B|| - (((( R, 12 + / (1++ - V ( M++1) - -Re+1 11
21 - B.+1 (1
(I - R4- - (V / (zz, Mri E)) (1 U1) - R&)l1
$ (1 3(+1) 2 We f y1) 1, [ 2 + - 31+1 ( / f (I 91+1 :1+1:+++1))))+ Vf( yes EI)
$ (1 Be+1) 2 R0ce (((e, y1) R2 + 2 2 0² + +4(1 ) 2 || 1el 11 + 11 31 11)))
S (1 1 w - f ye) -Rell + 1 + 4L (1(x211 - 2z + 11 - 3el 1x.l3)
where the third equality holds by [ [V[V (I Mt41i /t [++1)
(z ut+1) + R and
Eg [V yr: [t)] = fx 31) + Re: the third last inequality holds by the inequality ElKs-
2 $ 2|| the second last inequality due to Lemma 4 the last inequality holds by
0 < B < and Te+1 = It + nh (Te+1 Iz). Vi+1 B/ + mp 9e).
Theorem 7. (Restatement of Theorem gorithm
b)
Under the above Assumptions
4
in the Al- C2T m 2
given X C Rd, The = (m+43775 for all t 2 0, 0++1
= C17
Pt41
max k2, (cik)², (c2k))), k 0, e1 2 3k
125L
C2 2 3k
+
0 0 S min
(15b (T62g 2 6Lg
)
6p²
0 < 7 S min(
Tapp
1/3
and K
Lu log(Cozs Tog(CzznCyyT/uu /jyT) we have
2/ 2412X* x 2 1256, 13
4LA
T
T
2/3MM 1/6
2/3M
V2
( VF(..) 7)l S T
Σ
Eig <
(75)
T1/2
T1/3
T
where M F(z))-F" +
5b 12
+
2m21 p=ka
+
2k 2k ln(++T)
6/(m+ p²1
Ao
Ily1
pkq
pakAp
p
221)) and 1 = 12g + L2x.
Proof. Since Ne (m+1):73 on is decreasing and m 2 k3 we have Ne S 7o m1/ 1 and
k
7 < mr/33
ع 5 LLme for any 2 O. Due to 0- < T S 1 and 2 (cı we have
1L*
2mm
ac+11 = c < CiTt S m473
Gk
< 1. Similarly, due to m 2 (c2k)3, we have B,41 S 1. According to
Lemma
12 we have
1
E| V (1//E+111111411 - u+t1ll 1
E V v Vt) -val"
(76)
1/
1/-1
a1+1
1 )
El V (y 12112 + 41.3 ( (lā+++1 12,12 + | -311²))
2o + o0
1)t
11-1
1
1
cim)
B (I v1) - 12 + 41,3% (1ā++| - xx 12 + l1ūe+1 - y=ll²) + 2 3
17t
Th-1
where the second equality is due to a++1 = c1n.. Similarly, we have
1
Ellwee11 Vf(eet1. - R1 1
Ellwe - Vf - Rell2
(77)
m
77-1
3e41
1
E|| - Vf v.) - R&ll 112 + 4L (11ē111 - 2211 + ll vell²)) + 2,3__ 02
1/t
T/-1
1):
1
1
c2me
El| wr
vf(z Rell + 4L (115 1012 + 11 - yell?) + 222 0²
11
Th-1
26

---

Under review as a conference paper at ICLR 2023
By mi
(m+1)173> we have
&
1
(m + +t) -m (t +
3k (m + 1 - 1)2/3 v
77-1
3k 3kmm22 + t)
22/3
22/3
k2
22/3
2
3k(m + +)3/33
3k3
(m + t)2/3
3k33 1/8 -
343
T
(78)
where the first incquality holds by the concavity of function f(z) = x2/3, i.e. (x + 8) s
2/13 + 30473 the second inequality is due to m 2 2, and the last inequality is due to 0 < 1pp S 1.
Ler
2
1254 Gpz
we have
3F
1
El V v (1+11 ve411l2-
E Vgg Mr) uvll
(79)
1/t
9/-11
125L
5
V v)) vel1? 4L2T (1(T++1 -1112 11 30l13) 222
Me)
2n²
Let 02
343 7. we have
1 Bl Bllue+11 V (1 Re+1
1
El|w; (. We) Rell?
(80)
1/t
1/-1
< 9t/t [ (s(r,,))) 1 n - xell2 + 110r-1 - -bill)) + 2022
(1)
According to Lemmas
and
we have
F(1(41) F(x))
(81)
21177
Laner 11 (xre) - -2a112- pTh
S I|u, Vx(,, wt)1
1 - -Iel12
P
27
< 4mh7
Rell2 + 4n1y 1 Re 12 + 1.311 (x:)) - -vell2
||w, (F(e)))))
|+++1
xz xx|1?
2
According to Lemma 10 we have
Ilvet1 - '² (x++1))1 llve- - y (1:))1
(82)
MMA live 11" (I=))1?
37%
25m
25 25m2nmb 6nd
1i+11 - 11 +
V vyg(zr,3)) v:) vell +
12+1
xell?
4br
4
6pbr
Next, we define a Lyapunov function, for any t
O, E[(((t) +
5b, Lby
11y. --- (2:) +
? (1le
Vyg(z,, y0)1 + Imll Vf(a,, vr) Rell?)]
App
pm]-1
27

---

Under review as a conference paper at ICLR 2023
For notational simplicity, let L3 Lg + k Then we have
041 -0,
-F(x++1) - F(x)) +
56,L3Y App
(11v441 1/" (1+++))1 11 - -- (xx))13)
+ 7
(
Uc+1 V Vi (1 1,
1/t
1
Bllet Vug(Fe: 31)1
[ ((( Re+1ll
1
1
Bl| (s(e ye) 12
96-1
11t
9/--1
T. (1y)))))
yell2+
4n17 1|we - (x)(
41p67
||ell
pM
||
- =x+112
P
P
p
24
5b,
LBg
( nuad
37d
25m >
(z) 4/2) -vel? 11 25x
11 1/0e-(((x))) (xx))11
1 - yell?
vg
11 xell?
App
4b;
4
6μb,
7
125Lig
El (g( vell + 4T2 (11x++1 -x 2+l1?
+ -1411
20711002
P
6/2²
9T7t
B
wi
vi(ar, 3/) - 1el12 + +4 (1 - -x=ll2 + 11ūe+1 - 1el1²)
+2:2n10
2
7lk
- y" (xx2))12 +2Bl|u; w. - V f(11,11)) -Ral3)
-(f
4L37
125bg Lix2n
Me Tell - x211
4p
27
p
6p222p
156,,88
4L37,
) T1ll 1/1122 - + 417c7 ||,||1 +
2(c
o2)
-
4Xup
P
P
Lillyr - y0 (2xx))12 + +2Bll
f(z,, v1) -Roll)
MT)
|| - xee1
4p
47
A
R + 2 + 702 nh
+ P
(83)
where the first inequality holds by the above inequalities
79
80
81
and
(82)
: the last inequality
Vaxup
15b
15b, for
is due to 0 < 7 S 4/24033200+12000 L2 2 2//21322 2 1255? 2.006.2... Li
0
A
<
161.
16f.gn
all t > 1.
Let +; T.lllv1 - y" (xx))] + 2|| (i(t, Rell2, then we have
Me E p. +
|
2e 11| s0: 20,-60 -041
4n |Rell
2(c
c2)
m/.
(84)
4p
47
p
Taking average over 1 = 1,2, ., , on both sides of 84 we have
T
11 T +
p²y
|..41 - 2ell
<
T
p(. 1
+
4
Σ
nel
R
2(c +
22)00
Σ
T
mi
T
4,2
Ty
T
T
t=1
Given F1 E X and 8/ E V. let Ao = =1111 3² (211)1 we have
56 LĀ
|1 - - (x1))1 _ (1|e) - V.9(1119) 11)11
-|]w Vf R1
Apa
pro
5b, Ag 2-
F((11) +
(85)
A44
PM]
28

---

Under review as a conference paper at ICLR 2023
where the last inequality holds by Assumption 2
Since 7 is decreasing, i.., 1/' 7) for any
0
S
we have
1
T
P
p²
E
+
T1+1
(86)
T
4
472
1=1
T
2(cी + 02)00 T
4 T
P
Σ
(0,
Oc+1) +
Σ
1/8
3
+
Σ
T/e
Rell
Trm
TyT
T
t=1
1=1
1=1
P
(F(I1)
5b L87200
270²
Fr)
2(c + +z2
Σ 1
11t
TATT
App
TuT
((F(x)) -F))
5b Li40
20
2
o2)0²
k3
T
dt +
(m + t) dt
TATT
AUTrT
NOUTT
TuT
+
T
pl (x1) - -F*)
5b Di
20²
2k 21 + 22)02²
6k
In(m + T) + T2 (m + 772/33
TATT
XpmrT
Ttp
p( ((F(m))) - FF)) lo
5b 12 Ao
2m
133
(2) 22) In(m T) 6k(m +T)1/3
(m + 7)1/3
+2k (c) 2
kdp
122
T
T
where the second inequality holds by the above inequality (85) Let M = F(x1)-8"
50, PhApp
+
+
pka
2m m
2k (ef jo² In(m++1))
6k(m TT//3 have
p²
P²I
T
M S T
|
- 2tl|? -
(m + 131/33
(87)
T
4p2
47
According to Jensen's 's inequality, we have
1 (Lollve v2((1)) v21lu, Vf(z, - R&ll)]
E3
Te41
xell +
T
2p
3
2
1/2
[0
xz 12
11y y" (x0]11+
+
Bllu; Vf v0) R&11z)
T
4
4p2
402
3
T
1
1/2
+
|1111 - -zol
T
4p²
4,2
3M
V3M 1/6
v3M
(m
1/
(88)
T1/2
T1/2
T1/3
where the last inequality is due to (a + 6)2/6 < a/6 + 66/6 for all a, b > 0. Thus we have
T
E
[041 - 2+1l+
(Lollve - + (f( - Rell)]
T
1=1
2v3Mm 1/6
2
2V3M
(89)
T1/2
T1/3
Since ||w. obtain
V f(21, v1)
Rell 2 I|l, vf(x.. Rell by the above inequality
89
we can
T
E
[041
2211
(Lollye vx +2|luy Vf v.) R.ll)]
T
[=1
2/3MM
2/3M
22 Σ
<
Rell
T1/2
T1/3
T
2/3Mm 1/6
2V3M
V2
(90)
T1/2
T1/3
T
29

---

Under review as a conference paper at ICLR 2023
where the last inequality is due to ||R S 7 for all t 2 1 by choosing K in Algorithm 2
La
log(CaryCrgTli
According to the above inequality
we have
2/3M 1/6
2/3M T2/3
v2
( VF(m)
Elg S
(91)
T2/2
Theorem 8. (Restatement of Theorem 4) Under the above Assumptions
7
4
7 in the Al-
gorithm
given X' Red 1/ (m+4euu3 for all t 2 0, 0++11 = Ci
5t+1
c211i m 2
max (2, (c)k)² (c2k)*), k 0. 01
2 3k3
+
125
6
C2 2
32
2
+ 2. 0< min
1672a 6Lg
156 by
7 S min 24 + 12 18
Vuupo
1/3 P
and Le log
Dog(C Cru T /p), we have
ILK
E [ v V E B|AA|1
22V6M'm
2 6M'
2/3
Σ
(92)
T1/2
T1/3
T
where M p(F(x))-F")
5b 1. EAp
2m 1330 k2
+ (c) + c2) In(m + T) + 6k(++7)
ky
Proof. According to Lemma 7 we have
G.
21 T1+1/l (Loll> - well + V2IVS(I well)
|0, $ ||
/IVF((x)) - ww,ll
(
||
11-'1/ well
(xt)) wil
1
AA,1111,, w. || + - (VF((t) - well
|| |
[AAII
1
- IIF w.
IV IV3 MV
|wwll
||Ae||
1 [VF(z - we
||w:ll +
||
1
VF(x))]
(93)
||A
where the equality (i) holds by Tz41 2, - -, we that can be casily obtained from the step 5 of Algorithm when X = IRd, and the inequality (ii) holds by ||A:]] 2 for all Z due to
Assumption Then we have
[VF(())) $ ||A,
(94)
According to Cauchy-Schwarz inequality, we have
T
1 T VFF()) S
T
E
Σ BIglAAN 5
[[G))
-
E
A,
12
(95)
T
T
30

---

Under review as a conference paper at ICLR 2023
Then have
T
Elg
T
3L
y
y"
(x+)]l?
61lla
+ 73
3
| - 2;11?]
T
p²
2²
T
3L yh -V4())))
12 12
Vs(a,, M1)
R
12 Rel12
3
$
T
E
p²
+
p²
+
7
| - xel
1=1
24M
12 R
(m T)2/33
+
Σ
T
T
0
1=1
24M
12
(m + TT//33 +
(96)
T
G2T2'
where the third inequality holds by the above inequality 87 and the last inequality holds by || [R 1 for all t 2 by choosing K La Dog(Czzg yzy Cy
μ
By combining the above inequalities 95 and (96). we have
E BI
F S
Elgft
El|Ac|12
T Arl
+
22V6M'm
2V6M'
2v3
(97)
P
T1/2
T1/3
T
where M' M.
31


Reviews:
[{"review_id": "fvju_7adeOS", "reviewer": "Reviewer_LXpt", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This work focus on adaptive frameworks for bilevel optimization. It first introduce BiAdam that achieves $\\tilde{O}(\\epsilon^{-4})$ complexity. Then it introduces BiAdam with variance reduction and achieves $\\tilde{O}(\\epsilon^{-3})$ complexity. Both results matches  state-of-the-art complexities.  ", "summary_of_the_review": "The results in this paper is reasonable, but it may lack novelty. ", "strength_and_weaknesses": "strengths: \n\n\na) The complexities matches the previous results, and the algorithm does not need a mini-batch\n\n\nb) The algorithm can be used in the setting with constraints.\n\n\nweaknesses:\n\n\na) The novelty in this paper is quite limited. The results are built on the large body of bi-level optimization literature and super-ADAM. Noticeable, there are already many works for bi-level optimization can achieve the same complexities. \n\nb) The adaptive framework is not very meaningful here. Note that all the adaptivity is absorbed in the matrices $A_t$ and $B_t$ in the algorithms. The stepsize can be considered to be inversely related with eigenvalues of matrices. In Assumption 7, it assumes $A_t \\succeq \\rho I_d$ and $B_t=b I_p\\left(b_u \\geq b \\geq b_l>0\\right)$, which basically indicates stepsize for $x$ is upper bounded and stepsize for $y$ is lower and upper bounded. Then by controlling the other parameters in the stepsizes, e.g., $\\lambda$ and $\\gamma$, the stepsizes  can be treated just like non-adaptive stepsizes. Therefore, the analysis does not need too much novelty to accommodate adaptive stepsize, e.g., Lemma 10.  This leads to some drawbacks: 1) upper and lower bounds for adaptive matrices $A_t$ and $B_t$ need to be know in order to pick other hyperparameters, 2) usually, $\\rho$ in Adam is chosen to be very small just for stability. But when $\\rho$ is small, Theorem 1 needs a very small $\\gamma$ which may reduce the gain from Adam stepsize. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BmDo542Wdu", "reviewer": "Reviewer_LYRV", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposed a class of efficient adaptive bilevel optimization methods based on momentum techniques to solve the nonconvex-strongly-convex bilevel optimization problems. Moreover, it studied the convergence properties of the proposed methods, and provided the solid convergence analysis. It also conducted the empirical experiments on data hyper-cleaning and hyper-representation learning tasks to verify the efficiency of the proposed algorithms.", "summary_of_the_review": "This paper studied the adaptive bilevel methods for the nonconvex-strongly-convex bilelve optimization. One of the main contribution of this paper the the theoretical analysis for the proposed adaptive gradient-based methods for bilelve optimization. Experimentally, the proposed algorithms outperform various algorithms in data hyper-cleaning and hyper-representation learning tasks. \n\nSome Questions:\n\n1. Why use the momentum steps in the lines 5-6 of Algorithms? \n\n2. Why the norm of adaptive matrix has a lower bound in Assumption 7?\n\n3. Why the authors choose the decreasing parameter $\\eta_t$ ? Could we choose the \nconstant parameter $\\eta_t$ in the proposed algorithms ?\n\n4. How to choose the tuning parameters in the proposed Algorithms ?\n\n5. The convergence analysis does not show the advantage of the adaptive gradient method since \nit does not exploit the specific coordinate-wise adaptive stepsize used by Adagrad? In the best case, the convergence can be as good as the non-adaptive gradient descent ascent.", "strength_and_weaknesses": "**Strength:**\n\nThis paper proposed a class of efficient adaptive bilevel optimization methods, which build on the unified adaptive matrices and momentum techniques. Moreover, it provides the solid theoretical analysis for the proposed algorithms, and proved the proposed algorithm reaches the best known sample complexity.\n\n**Weakness:**\n\nThe proposed algorithms have many tuning parameters.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8slbziFKWaV", "reviewer": "Reviewer_7cUX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "Inspired from Adam, authors propose adaptive bilevel algorithms, and a variance reduced variation, coined \"biAdam\" and VR-BiAdam. They show respectively $1/\\epsilon^4$ and $1/\\epsilon^3$ convergence rate. Authors propose experiments on data hypercleaning and hyperrepresentation learning\n", "summary_of_the_review": "I have doubts on the practical and theoretical impact of the paper", "strength_and_weaknesses": "Major concerns:\n- I have doubt about the practical impact of the proposed work, as many bilevel optimization problems, it requires to select $3$ sequences of stepsize $\\eta_t, \\alpha_t, \\beta_t$. To me, it seems very unclear how to select these parameters in practice.\n- I also have doubt about the theoretical impact of the paper \"Our VR-BiAdam algorithm reaches the best known sample complexity of $1/\\epsilon^3$\". A recent paper [1] managed to prove $1/\\epsilon^2$ rate for a single loop algorithm. Could authors comment on this?\n\n[1] Dagréou, M., Ablin, P., Vaiter, S. and Moreau, T., 2022. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. NeurIPS2022\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5fZwQ5Oz2S", "reviewer": "Reviewer_5EBw", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposed efficient adaptive bilevel optimization methods based on the momentum techniques for the nonconvex-strongly-convex bilevel optimization. It provided the solid convergence analysis for the proposed methods, and proved that these methods obtain the best-known complexity. The experimental results on data hyper-cleaning and hyper-representation learning tasks demonstrate the efficiency of the proposed algorithms.", "summary_of_the_review": "This paper proposed efficient adaptive bilevel optimization methods based on momentum techniques for the nonconvex-strongly-convex bilevel optimization. It provided the solid convergence analysis for the proposed methods, and proved that these methods obtain the best-known complexity. The experimental results on data hyper-cleaning and hyper-representation learning tasks demonstrate the efficiency of the proposed algorithms.\n\nSome Comments:\n\n1. It would be great if the authors would write how they can solve the subproblems in lines 5 and 6 of Algorithms 1-2. \n\n2. What is the intuition to use the momentum steps in the lines 5-6 of Algorithms 1-2? \n\n3. These momentum steps improve the sample complexity in the proposed algorithms?\n\n4. In Theorem 6, the term $\\sqrt{\\frac{1}{T}\\sum_{t=1}^T\\mathbb{E}\\|A_t\\|^2}$ is bounded?\n\n5. How to choose the adaptive learning rates of Algorithms 1-2 in the experiments?\n", "strength_and_weaknesses": "Strength:\n\nThis paper proposed efficient adaptive bilevel optimization methods based on momentum techniques for the nonconvex-strongly-convex bilevel optimization. It provided the solid convergence analysis for the proposed methods, and proved that these methods obtain the best-known complexity.\n\nWeakness:\n\nThe parameters in adaptive matrices maybe depend on the tuning parameter in the proposed algorithms.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject