Provably Faster Algorithms for Bilevel Optimization and Applications to Meta-Learning
Authors: Kaiyi Ji
Junjie Yang
Yingbin Liang
Venue:  (2021)
Keywords: Bilevel Optimization
Computational Complexity
Meta-Learning
Hyper-Parameter Optimization

Abstract: Bilevel optimization has arisen as a powerful tool for many machine learning problems such as meta-learning, hyperparameter optimization, and reinforcement learning. In this paper, we investigate the nonconvex-strongly-convex bilevel optimization problem. For deterministic bilevel optimization, we provide a comprehensive finite-time convergence analysis for two popular algorithms respectively based on approximate implicit differentiation (AID) and iterative differentiation (ITD). For the AID-based method, we orderwisely improve the previous finite-time convergence analysis due to a more practical parameter selection as well as a warm start strategy, and for the ITD-based method we establish the first theoretical convergence rate. Our analysis also provides a quantitative comparison between ITD and AID based approaches. For stochastic bilevel optimization, we propose a novel algorithm named stocBiO, which features a sample-efficient hypergradient estimator using efficient Jacobian- and Hessian-vector product computations. We provide the finite-time convergence guarantee for stocBiO, and show that stocBiO outperforms the best known computational complexities orderwisely with respect to the condition number $\kappa$ and the target accuracy $\epsilon$. We further validate our theoretical results and demonstrate the efficiency of bilevel optimization  algorithms by the experiments on meta-learning and hyperparameter optimization.

Under review as a conference paper at ICLR 2021
PROVABLY FASTER ALGORITHMS FOR BILEVEL OPTI- MIZATION AND APPLICATIONS TO MEAA-LGG
Anonymous authors
Paper under double-blind review
ABSTRACT
Bilevel optimization has arisen as powerful tool for many machine learning problems such as meta-learning, hyperparameter optimization, and reinforcement learning. In this paper, investigate the nonconvex-stronglyy timization problem. For deterministic bilevel optimization, we provide a compre- hensive finite-time convergence analysis for two popular algorithms respectively based on approximate implicit differentiation (AID) and iterative differentiation (ITD). For the AlD-based method, we orderwisely improve the previous finite- time convergence analysis due to a more practical parameter selection as well as a warm start strategy, and for the ITDD-based method we establish the first theoretical convergence rate. Our analysis also provides quantitative comparison between ITD and AID based approaches. For stochastic bilevel optimization, we propose a novel algorithm named stocBiO, which features sample-efficient hypergradient estimator using efficient Jacobian- and Hessian-vector product computations. We provide the finite-time convergence guarantee for stocBiO, and show that stocBiO outperforms the best known computational complexities orderwisely with respect the condition number i and the target accuracy We further validate our the- oretical results and demonstrate the efficiency of bilevel optimization algorithms by the experiments on meta-learning and hyperparameter optimization.
bilevel op-
INTRODUCTION
Bilevel optimization has received significant attention recently and become an influential framework
in various machine learning applications including meta-learning (Franceschi et al. [0018] Bertinetto
ctt al. 2018 Rajeswaran et al. [2019] Ji et al. [2020a). hyperparameter optimization ( (Franceschi et al.]
2018 Shaban et al. 2019 Feurer & Hutter 2019), ), reinforcement learning (Konda & Tsitsiklis] 2000
Hong et al. 2020), and signal processing (Kunapuli et al. 2008 Flamary et al. 2014). A general
bilevel optimization takes the following formulation.
min (xx) = f(x, y (1)) S.t. y" y²(x) = arg min g(r, ZERP
yERv
where the upper- and inner-level functions f and g are both jointly continuously differentiable. The
goal of eq. I is to minimize the objective function (zx) w.r.t. æ, where y y²(x) obtained by solving the lower-level minimization problem. In this paper, we focus on the setting where the lower-level function g is strongly convex with respect to (W.r.t.) y. and the upper-level objective function (xx) is nonconvex w.r.t. x. Such types of geometrics commonly exist in many applications including meta-learning and hyperparameter optimization, where g corresponds to an empirical loss with strongly-convex regularizer and x are parameters of neural networks.
broad collection of algorithms have been proposed to solve such types of bilevel optimization problems. For example, Hansen et al.] (1992); (Shi et al.] (2005); Moore| (2010) reformulated the bilevel problem in eq. (1) into a single-level constrained problem based on the optimality condi- tions of the lower-level problem. However, such type of methods often involve large number of constraints, and are hard to implement in machine learning applications. Recently, more efficient gradient-baat based bilevel optimization algorithms have been proposed, which can be generally catego- rized into the approximate implicit differentiation (AID) based approach (Domke) 2012] Pedregosa
2016 Gould et al. 2016
Liao al. 2018 Ghadimi & Wang 2018 Grazzi et 2020 Lorraine

---

Under review as a conference paper at ICLR 2021
et al. 2020) and the iterative differentiation (TTD) based approach (Domkel 2012 Maclaurin al, 2013 Franceschi et al.] 2017: 2018 Shaban et al. 2019 Grazzi et al. 2020). However, most of these studies have focused the asymptotic convergence analysis, and the fimite-time analysis (that characterizes how fast an algorithm converges) has not been well explored except a few attempts recently. Ghadiii & Wang (2018) provided the finite-time analysis for the ITDD-based approach. Grazzi et al. (2020) provided the iteration complexity for the hypergradient computation via ITD and AID, but did not characterize the finite-time convergence for the entire execution of algorithms.
Thus, the first focus of this paper is to develop comprehensive and enhanced theory, which cov- ers a broader class of bilevel optimizers via ITD and AID based techniques, and more importantly. improve the exiting analysis with more practical parameter selection and order-level lower computational complexity.
The stochastic bilevel optimization often occurs in applications where fresh data need to be sampled the algorithms run (e.g., reinforcement learning (Hong al. (2020) the sample size of training data is large (e.g., hyperparameter optimization (Franceschi et al. 2018). Stackelherg game (Roth) al. 2016)). Typically, the corresponding objective function is given by
Ee + En_ ((),)()))
min D(x) f(== = .ERP
s.t. (z) = arg min g(z, = {
B (x);<) # E G(a, y (x))
(2)
yERv
where (xx, v) and g(,, y) take either the expectation form w.r.t the random variables & and Ç or the finite-sum form over given data Dn,m {Ea, S,, 2= I,..,, nt 1, .... m often with large sizes and m. During the optimization process, the algorithms sample data batch via the distributions of and from the set D, For such stochastic setting, Ghadimi & Wang (208)) proposed bilevel stochastic approximation (BSA) method via single-sample gradient and Hessian estimates. Based on such method, |Hong al. (2020) further proposed two-timescale stochastic approximation (TTSA), and showed that TTSA achieves a better trade-off between the complexities of inner- and outer-loop optimization stages than BSA.
The second focus of this paper is to design a more sample-efficient algorithm for bilevel stochastic optimization, which achieves an order-level lower computational complexity over BSA and TTSA.
1.1
MAIN CONTRIBUTIONS
Our main contributions lie in developing enhanced theory and provably faster algorithms for the nonconvex-stin soannvee-sttoggy-ooooe bilevel deterministic and stochastic optimization problems, respectively. Our analysis involves several new developments, which can be of independent interest.
We first provide unified finite-time convergence and complexity analysis for both ITD and AID based bilevel optimizers, which we call as ITD-BiO and AID-BiO. Compared to existing analysis in Ghadimi & Wang (2018) for AID-BiO that requires a continuously increasing number of inner- loop steps to achieve the guarantee, our analysis allows a constant number of inner-loop steps as often used in practice. In addition, we introduce a warm start initialization for the inner-loop updates and the outer-loop hypergradient estimation, which allows us to backpropagate the tracking errors to previous loops, and results in improved computational complexity. As shown in Table []] the gradient complexities Gc(f. e). Gc(g, e), and Jacobian- and Hessian-vector product complexities JV(g,e) e) and HV(g, e) of AID-BiO attain an e-accurate stationary point improve those of Ghadimi & Wang (018)) by the order of K, iCc 1/4 and respectively, where is the condition number. In addition, our analysis shows that AID-BiO requires less computations of Jacobian- and Hessian- vector products than ITD-BiO by an order of к and 1//2, which provides a justification for the observation in Grazzi et al. 2020 that ITD often has larger memory cost than AID.
We then propose a stochastic bilevel optimizer (stocBiO) to solve the stochastic bilevel optimiza- tion problem in eq. (2). Our algorithm features differentiation, where the core design involves a sample-efficient Hypergradient estimator via the Neumann series. As shown in Table the gradient complexities of our proposed algorithm w.r.t. F
hyper-gradien estimation via implicit
2

---

Under review as a conference paper at ICLR 2021
Table I: Comparison of bilevel deterministic optimization algorithms.
Algorithm
Ge(f.e)
Ge(g,
IV(g, e)
H)(g,e)
AID-BiO (Ghadimi & Wang 2018
O(w"67))
O(w'e-B/4)
O (
0 (
AID-BiO (this paper)
O (m-c-)
(1
ITD-BiO (this paper)
0(x(c-))
O(K²te))
Ö (K*C-")
Ö (m=tc-))
Ge(f.e) e) and Ge(g, c): number of gradient evaluations w.r.t. f and K the condition number.
(V e): number of Jacobian-vector products V, VVV9(T, y)u. Notation O: omit log terms.
HV e): number of Hessian-vees vector products Vzg(z,))
Table 2: Comparison of bilevel stochastic optimization algorithms.
Algorithm
()
Ge(G,)
JV(G,
HV(G,))
TTSA (Hong et al.
2020)
((poly(A)) 2
O(poly(K))
O(poly(K)e +)
(poly((ss)
BSA
GGaadimi & Wang 2018
((n
O(N"=
O (k=
Ô (n''
stocBiO (this paper)
(
O
O (x
① (150
We use poly(k) (x) because Hong et al. (0200) does not provide the explicit dependence on x.
and G improve upon those of BSA Ghadimi & Wang 2018) by an order of k and e- respectively. In addition, the Jacobian vector product complexity JV(G, e) of our algorithm improves that of BSA by an order of s. In terms of the target accuracy e, computational complexities improve those of TTSA (Hong et al. 2020) by an order of c-1/2
We further provide the theoretical complexity guarantee of ITD-BiO, AID-BiO and stocBiO in meta- learning and hyperparameter optimization. The experiments validate our theoretical results for de- terminisitic bilevel optimization, and demonstrate the superior efficiency of stocBiO for stochastic bilevel optimization. Due to the space limitations, we present all theoretical and empirical results on hyperparameter optimization in the supplementary materials.
1.2 RELATED WORK
Bilevel optimization approaches: Bilevel optimization was first introduced by Bracken & McGill
[1973.. Since then, number of bilevel optimization algorithms have been proposed, which include
but not limited to constraint-based methods (Shi et al., 20055: Moore] (010) and gradient-based
methods (Domke) 2012 Pedregosa 2016 Gould et al.
2016 Maclaurin et al. 2015 Franceschi
cct al.
2018 Ghadimi & Wang 2018: Liao et al. 2018 Shaban et al. 2019 Hong et al. [2000] Liu
al.
2020
Li et al. [2020] Grazzi al.) 2020 Lorraine al. 2020). Among them, Ghadimi &
Wang
(2018); y Hong et al. (2020) provided the finite-time complexity analysis for their proposed
methods for the nonconvex-strongly
bilevel optimization problem. For such a problem, this
paper develops a general and enhanced finite-time analysis for gradient-based bilevel optimizers for the deterministic setting, and proposes a novel algorithm for the stochastic setting with order-level lower computational complexity than the existing results.
Some works have studied other types of loss geometries. For example, Liu et al. (0020:: Li et al. (220)) assumed that the lower- and upper-level functions g -) and f(z, -) are convex and strongly- convex, and provided an asymptotic analysis for their methods. Ghadimi Wang (0188 Hong al. 2020 studied the setting where (--) is strongly-conve convex or convex, and gxr, -) strongly convee..
Bilevel optimization in meta-learning: Bilevel optimization framework has been successfully em- ployed in meta-learning recently (Snell et al. 2017 Franceschi et al. [0188] RRjeswaran et al. 2019 Zügner & Günnemann 2019 Ji al. 2220aa b). For example,|Snne [Snell et al. (2017) proposed a bilevel optimization procedure for meta-learning to learn common embedding model for all tasks. Ra- jeswaran et al. (2019) reformulated the model-agnostic meta-learning (MAML) (Finn et al. 2017) as bilevel optimization problem, and proposed iMAML via implicit gradient. The paper provides a theoretical guarantee for two popular types of bilevel optimization algorithms, i.e., AID-BiO and ITD-BiO, for meta-learning
Bilevel optimization in hy berraarameeeer optimization: Hyperparameter optimization has become increasingly important powerful tool in the automatic machine learning (autoMI.) (Okuno al.
3

---

Under review as a conference paper at ICLR 2021
Algorithm Deterministic bilevel optimization via AID ITD
1: Input: Stepsizes a, B 0, initializations æD, yo, Vp-
for 1, ... K
3: Set ut U4-1 if & > and yo otherwise
4:
=ort=1.-.. T do
Update y) = U 1-1 aV ( Uk vk-))
6: end for
Hypergradient estimation via
AID: 1) set vg o if & > and un otherwise
2) solve og from (2g(zn, Do = (rrf ui
N steps of CG starting from eo 3) compute Jacobian-voctov product V. V.Vyg(ra of Duğ" via automatic differentiation
4) compute (+((x)) V=f( v V. V.V vk )m
ITD: compute (Tx())) = 0 via backpropagation w.r.t.
8: Update Th+1 Thg (()
9: end for
2018 Yu & Zhu, 2020). Recently, various bilevel optimization algorithms have been proposed in the context of hy hyperparameter optimization, which include implicit differentiation based meth- ods (Pedregosal 2016), dynamical system based methods via reverse or forward gradient computa- tion (Franceschi et al. 2017 2018, (Shaban et al., (019), etc. This paper demonstrates the superior (0Taaa
efficiency of the proposed stocBiO algorithm hyperparameter optimization.
2 ALGORITTS
In this section, we describe two popular types of deterministic bilevel optimization algorithms, and propose algorithms for stochastic bilevel optimization.
2.1
ALGORITHMS FOR DETERMINISTIC BILEVEL OPTIMIZATION
As shown in Algorithm I we describe two popular types of deterministic bilevel optimizers respec- tively based on AID and LTD (referred as AID-BiÓ and ITD-BiO) for solving the problem eq. (II
Both AID-BiO and ITD-BiO update in a nested-loop manner. In the inner loop, both of them run T steps of gradient decent (GD) to find an approximation point vi close to (*x)). Note that we choose the initialization v of each inner loop as the output yī-1 of the preceding inner loop rather than random start. Such a warm start allows us to backpropagate the tracking error 1 - -y" (zx) to previous loops, and yields improved computational complexity.
At the outer loop, AID-BiO first solves vi from a linear system Vig(o v )c (T of using steps of conjugate-gradient (CG) starting from vg (where we also adopt warm start scheme here by setting of - and then constructs
(()))) (I vE V V.V Vyg(Ek, oe yo
as an estimate of the true hypergradient (*(()), whose form is given by the following proposition. Proposition 1. Recalling the definition (<x) == f(, v" (x)), it holds that
( -V ( y² (4x)) V. V ( y" (xx)))
where of is the solution of the linear system (Z y² (zx))u V
As shown in Domke 2012)
Grazzi et al. 2020). the construction of eq. 3 involves only Hessian-
vector products in solving uN via CG and Jacobian-vector product V, V gg(( vi yo which can
be efficiently computed and stored via existing automatic differentiation packages.
As comparison, the outer loop of ITD-BiO computes the gradient 0f(z..v (xx)) an approxima- disk
tion of the hyper-gradient V)((x)) (f (zx)) via backpropagation, where we write vo (rx)
dag
This equivalent to solve quadratic programing min, fe " Vig(zr, De T VVVuf(
4

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Stochastic bilevel optimizer (stocBiO)
1: Input: Inner- and outer-loop stepsizes a, initializations and yo-
for 0, 1, ...,
3: Set u1 94 if & > and yo otherwise do
4:
for 1,... 7
5:
Draw sample batch S:-1
6:
Update y) = 1/ aV G(a, ((-
7:
end for
8:
Draw sample batch Fr, and compute vo vaF(ax vi :D)
Draw sample batch DH, and construct ui via Algorithm
10:
Draw sample batch De. and compute Jacobian-vector product V, Gla, vi: Da)ee
11:
Compute gradient estimate (T)) via eq.
12:
Update # = Ig (V4((x)
13:
end for
Algorithm 3 Construct "Q given to
I: Input: An integer Q, data samples Dær {B5} and constant v7 > 0.
for = 1,2.... ... Q do
3: Sample B, and compute gradient Gy(y) = - v V
4: end for
5: Set
6: for Q, .... do
7: Ti-1 =
= B,)r via automatic differentiation
8: end for
9:
Return eq Ei0
because the output vLT of the inner loop has a dependence on Fy through the inner-loop iterative GD
updates. The explicit form of the estimate 0f(w2.0 (ma)) is given by the following proposition chain rule. For notation simplification, let ()=
dec
Proposition 2. The gradient af(m .v (xx))
takes the following analytical form:
ff(kk vT V vi)
T
T-1
Σ
V.V.gla vil
II (I - aV V.) ( vi
Ozp.
j=t+1
Proposition 2 shows that the differentiation involves the computations of second-order derivatives such as Hessian (.)((.)) Since efficient Hessian-fiee methods such as CG have been successfully deployed in the existing automatic differentiation tools, computing these second-order derivatives reduces to more efficient computations of Jacobian- and Hessian-vector products.
2.2 ALGORITHM FOR STOCHASTIC BILEVEL OPTIMIZATION
We propose a new stochastic bilevel optimizer (stocBiO) Algorithm 2 to solve the problem eq. ( It has a double-loop structure similar to Algorithm [ but runs T steps of stochastic gradient decent (SGD) at the inner loop to obtain an approximated solution y't Based on the output y of inner loop, stocBiO first computes gradient V F(rc, v ; Dr) over sample batch Dr, and then computes vector eq via Algorithm
3 which takes a form of
Q-1
II -[-1V/ ViG B,)) (I F(Ik, : Dr), S=Q-9
EQ
where [By,j = 1, ..., Q} are mutually-independeer sample sets, Q and are constants, and we let I8 = 7 for notational simplification. Note that our construction of rq. i.e., Algorithm is motived by the Neumann series Ei U (I U)- -!, and involves only Hessian-vector products rather than Hessians, and hence is computationally and memory efficient. Then, we construct
(Φ())) -V. F. D V VyG(K up Da)uq
5

---

Under review as a conference paper at ICLR 2021
estimate of hypergradient (T(T)) given by Proposition An important component of our algorithm is eq. which serves as an estimate of ug in eq. 4 Compared to the deterministic case, designing sample-efiicient Hypergradient estimator in the stochastic case is more challenging. For example, instead of choosing the same batch sizes for all B = 1, 1,,... Q in eq. (5). our analysis captures the different impact of components G vIc ;B).J = l,.... Q on the Hypergradient estimation variance, and inspires an adaptive and more efficient choice by setting |Bq-5| to decay exponentially with j from 0 to 1. By doing so, we achieve improved complexity.
3 DEFINITIONS AND ASSUMPTIONS
Let = (xz, y) denote all parameters. For simplicity, suppose sample sets S, for all t = o.... --.,--,, Da and Dr have the sizes of S, D, and Dy. respectively. In this paper, we focus on the following types of loss functions for both the deterministic and stochastic cases.
Assumption 1. The lower-level function g(æ, y) j-strongly-conver w.r.t. y and the total objective function Φ (z) = fzz y² (z)) ) is nonconvex w.r.t. z. For the stochastic setting, the same assumptions hold for (z y: {) and (z)). respectively.
Since the objective function (xx) is nonconvex, algorithms are expected to find an e-accurate sta- tionary point defined as follows.
Definition 1. We say I. is an e-accurate stationary point for the objective function ((x) in eq. if [=) S e, where is the output of an algorithm.
In order to compare the performance of different bilevel algorithms, we adopt the following metrics of computational complexity.
Definition For a function J [(x,,) y) and a vector v, let Gc(J,)) be the number of the partial gradient v.J or VyJ, and let (V(g,e) e) and HV(g, 6) be the number of Jacobian-vector products V. V.Vgg y)v. and Hessian-vector products (zg(z,)) For the stochastic case, similar metrics are adopted but w.r.t. the stochastic function Fz, E).
We take the following standard assumptions on the loss functions in eq. (2) which have been widely adopted in bilevel optimization (Ghadimi & Wang 2018 Ji al., 2020a).
Assumption 2. The loss function f(z) and g(2) satisfy
f()) is M -ipischhi,,, i.e. for any z, :', 15(z) - f(=') S M||= - ='||.
Gradients (z) and V fz) are L-Lipschitz, i.e., for any 2,
[V)(z) ff2'))l = L|| 1l [[])(=) - Vg(z')l S L||2 z'11-
For the stochastic case, the same assumptions hold for F(z: and G(z for any given and Ç.
As shown in Proposition [ the gradient of the objective function ((x) involves the second-order derivatives V. V yz(2)) and Vz)(()) The following assumption imposes the Lipschitz conditions on such high-order derivatives, as also made in Ghadimi & Wang 2018).
Assumption 3. Suppose the derivatives V. Vyg()) and V3,(() T- and p- Lipschitz, i.e.,
For any z', |/ V Vy)(z)= V Veg(=')l S TT|2= ='1l-
For any z' [Vg(()) Vig(=')1 S -
For the stochastic case, the assumptions hold for V V,V,G(2;)) and VeG((z; any Ç.
As typically adopted in the analysis for stochastic optimization, we make the following bounded- variance assumption for the lower-level stochastic function G(2;C).
Assumption 4. (2(2(() has a bounded variance, i.e.. Egl[VG(2: -V(())) o² for some o.
4
MAIN RESULTS FOR BILEVEL OPTIMIZATION
4.1
DETERMINISTIC BILEVEL OPTIMIZATION
We first characterize the convergence and complexity performance of the AID-BiO algorithm. Let L denote the condition number.

---

Under review as a conference paper at ICLR 2021
Theorem 1 (AI). Suppose Assumptions 7 2 3 hold. Define a smoothness parameter L 1²
L ++ 2L'-TM2 + +LM+L pL 0 (K*), choose the stepsizes a S I 3 u.n. and set
the inner-loop iteration number T 2 (x) and the CG teration number N 2 (VVR), where the
detailed forms T, N can be found in Appendix F
Then, the outputs of AID-BiO satisfy
1
K-1
64Le (+(2o)
inf, ((x)) + 5A0
Σ
[V
K
K
where Ag = llyo - y" (I + llug - -oll O.
In order to achieve e-accurate stationary point, we have
Gradient complexity: Gelf.e) = (cl -
Jacobian- and Hessian- product: (V O (12 HV(g, (1225
can be seen from Table that the complexities Gc(ff,), Go(g, v), and HV(g, c) of our analysis improves that of Ghadimi & Wang (2018) (eq. (2.30) therein) by the order of K, ke- 1/4 and K. Such an improvement is achieved by refined analysis with a constant number of inner- loop steps, and by a warm start strategy to backpropagate the tracking errors 11v - y (xx) and Ilul - rfll to previous loops, as also demonstrated by our meta-learning experiments.
We next characterize the convergence and complexity performance of the ITD-Bic Bi- algorithm.
Theorem 2 (ITD-BiO). Suppose Assumptions [ 2 and hold. Define the parameter L& as in I
Theorem and choose a S T. 3 ALo and T Z ( log )) where the detailed form of can be
found in Appendix F Then, the outputs of ITD--BO satisfy
(6 inf, R(x)) +
2e
[V((2)))
K
3
In order to achieve an e-accurate stationary point, we have
Gradient complexity: Ge(f,c) O Gelg,
Jacobian- and Hessian-vector product complexity:
JV(g,e) logge==oog""" logge"))
HV On=tt=110g ltg
By comparing Theorem and Theorem 2 it can be seen that the complexities Go(g,e), e). JV e), and HV(g.e) e) of AID-BiO are better than those of ITD-BiO by the order of log(?), log( ( and 0.5 (.) This is in consistence with the comparison in Grazzi et al. (020)) that AID-BiO often has a lower memory cost than ITD-BiO.
4.2 STOCHASTIC BILEVEL OPTIMIZATION
We first characterize the bias and variance of important component eq in eq. 5
Proposition 3. Suppose Assumptions and hold. Let the constant 1) S t and choose the batch sizes [BQ+1-11 BQ -nu))-1 for
Q. where 2 Q(1 Q(1-)))0-z Then, the bias satisfies
[Beq - Laga oh O Vf MTl
S 10 (1-1p)) MMM
(8)
Furthermore, the estimation variance is given by
4n L2 1 122
+ 4(1 m2)22++22211
2M
E| uQ VVg(ok vi 'V 'V f ve)
(9)
122
1.D,
Proposition shows that if choose Q and B at the order level of Oloog !) and O(1/c), the
bias and variance are smaller than O(e), and the required number of samples is ΣΦ BQ(1 qp))d1== 0 (c- log !)- Note that the chosen batch size |Bo+1-5l exponentially decays w.r.t. j.
In comparison, the uniform choice of all [B,] would yield a worse complexity of Oc- )).
We next analyze stocBiO when the objective function & (xx) fxx, y² (x:) is nonconvex.

---

Under review as a conference paper at ICLR 2021
Theorem 3. Suppose Assumptions 1 and hold. Define parameter L L +
2L²+ log (12+ 12 (L+ 12 Mr4 22 12))))) loR (VB(L+ Mr 1.1e)
+
"
2. 4TML + p.,MM O (1=). choose stepsize 3 ALo' and set 1] < I Algorithm
Set
16
max
2 )
loxl )
Then, we have
K-1
32L (D(o)) inf, F(x) + 31lv0 y (x0))l?
Σ
+ 72k2 2 m21)20
K
k=
40
L
+
LM 1
o²
16 M
(8+ 38+32*))MM²
+ 64x2
(10)
Tap
Dg
Dj
B
In order to achieve an e-accurate stationary point, we have
Gradient complexity: Gc
Jacobian- and Hessian-vector product: eV =((s HVVG))
Theorem 3 shows that stocBiO converges sublinearly with the convergence emror decaying expo- nentially w.r.t. Q and sublinearly w.r.t. the batch sizes S, Dy, D for gradient estimation and for Hessian inverse estimation. In addition, it can be seen that the total number T of the inner-loop steps is chosen at nearly a constant level, rather than a typical choice of ((log( ))).
As shown in Table the gradient complexities of our proposed algorithm in terms of F and G improve those of BSA in Ghadimi & Wang 2018) by an order of к and e-1 respectively. In addition, the Jacobian-vector product complexity JV(G, e) of our algorithm improves that of BSA by the order of k. In terms of the accuracy our gradient, Jacobian- and Hessian-vector product complexities improve those of TTSA in Hong al. (2020) all by an order of e
APPLICATIONS TO META-LEARNING
5.1 META-LEARNING WITH COMMON EMBEDDING MODEL
Consider the few-shot meta-learning problem with tasks (Ti, 1....mm m) sampled from distri- bution Py. Each task T; has a loss function L( wy; {) over each data sample ç, where e are the parameters of embedding model shared by all tasks, and w, are the task-specific parameters. The goal of this framework is to find good parameters e for all tasks, and building on the embedded features, each task then adapts its own parameters w; by minimizing its loss.
The model training takes a bilevel procedure. In the lower-level stage, building on the embedded features, the base learner of task T, searches w as the minimizer of its loss function over a training set Sp. In the upper-level stage, the meta-learner evaluates the minimizers w 1,..., m on held-out test sets, and optimizes & of the embedding model over all tasks. Specifically, let w (W1, ... Wm) denote all task-speciti parameters. Then, the objective function is given by
1
min Lo(d, 1")
L(ø, 5
D
CED
LD, (o.w;) task apsk-ipecific upper-level loss
s.t. 80 = arg min Ls(o,
arg min (Wn)) 1=1
Σ C(d, w;: R(w,)) EES.
(II)
S
Lss (dh.o;) task-specific lower-level loss
where S; and D; are the training and test datasets of task T, and R(w:) ) is strongly-convex regu- larizer, e.g., L2 Note that the lower-level problem is equivalent to solving each w as a minimizer of the task-specific loss Ls, (ò, w:) for i = 1, ..., m.. In practice, w; often corresponds to the param- eters of the last linear layer of a neural network and Φ are the parameters (e.g., 4 convolutional layers in Bertinetto et al. (2018); Ji al. (020a)), and hence the lower-level function is strongly-convex w.r.t. w and the upper-leved function (o( ü (o)) is generally non- convex w.r.t. Φ. In addition, due the small sizes of datasets D, and S; in few-shot learning, all
the remaining layers
8

---

Under review as a conference paper at ICLR 2021
updates for each task Ti use full gradient descent without data resampling. As result, AID-BiO and ITD-BiO in Algorithm [ can be applied here. In some applications where the number m of tasks is large, it is more efficient to sample batch B of i..d. tasks from {Tx, 1.., m) at each meta (outer) iteration, and optimizes the mini-batch versions Lo(ó, w; B) To EiEs Lrz (ò, w;)
and (o, wo B) TB Eies Ls, ( wx) instead. The following theorem provides the convergence analysis of ITD-BiO for this case.
Theorem 4. Suppose Assumptions 2 and 3 hold and suppose each task loss Ls, (o, w;) is p- strongly-convex w.r.t. Wi. Choose the same parameters (3, B.T as in Theorem 2
Then, we have
1 Σ ( K
16L (D(60) - inf (())
2E +
(1+
L M²
K
3
8|B|
Theorem 4 shows that compared to the full batch (i.e., without task sampling) case in eq. (I) the task sampling introduces variance term O ( due to the stochastic nature of the algorithm. Using an approach similar to Theorem 4 derive similar result for AID-BiO.
5.2 EXPERIMENTS
To validate our theoretical results for deterministic bilevel optimization, we compare the perfor- mance among the following four algorithms: ITD-BiO, AID-BiO-constant (AID-BiO with a con- stant number of inner-lopp steps as in analysis), HID-BiO-increasee (AID-BiO with an in- creasing number of inner-loop steps under analysis in Ghadimi & Wang (2018) ) and two popular meta-learning algorithms MAMI (Finn et al. 2017) and (Rahu et al. 2019). We conduct experiments over a 5-way 5-shot task on two benchmark datasets: FC100 and minilmageNet, and
the results are averaged over 10 trials with different random seeds. Due to the space limitations, provide the model architectures, hyperparameter settings and additional experiments in Appendix B
Traning securayy
gosss
AID BIO constant
AID BIO constant
AID BIO constant
AID BIO constant
AID BID increasing
SIO increasing
0.38
Increasing
ANIL
ANI.
ANIL
ANIL
NAME
622
MAML
MAML
MAML
1005
201
2002
628
120
1h6
1999
2009 200
110
20e running
100 ahc voo 4th running
running time
running time
(a) dataset: minilmageNet
(b) dataset: FC100
Figure 1: Convergence of various algorithms on meta-learning. For each dataset, left plot: training accuracy v.s. running time; right plot: test accuracy v.s. running time.
be seen from Figure T that for both the minilmageNet and FC100 datasets, AID-BiO-constant converges faster than AID-BiO-increasing in terms of both the training accuracy and test accuracy, and achieves a better final test accuracy than ANIL and MAML. This demonstrates the superior improvement of our developed analysis over existing analysis in Ghadimi & Wang (2018) for AID- BiO algorithm. Moreover, it can be observed that AID-BiO is slightly faster than ITD--BOO in terms of the training accuracy and test accuracy. This is also in consistence with our theoretical results.
6 CONCLUSION
In this paper, we develop general and enhanced finite-time analysis for the nonconvex-strongly convex bilevel deterministic optimization, and propose a novel algorithm for the stochastic setting whose computational complexity outperforms the best known results order-wisely. We also provide the theoretical guarantee of various bilevel optimizers in meta-learning and hyperparameter opti- mization. The experiments validate theoretical results and demonstrate the effectiveness of the proposed algorithm. We anticipate that the finit-timm analysis that we develop will be useful for analyzing other bilevel optimization problems with different loss geometries, and the proposed al- gorithms will be useful for other applications such as reinforcement learning and Stackelberg game.
2 MAML consists an inner loop for task adaptation and an outer loop for meta initialization training. ANII refers to almost no inner loop, which is an efficient MAMI. variant with task-specific adaption on the last-layer of parameters.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sehastien M.R. Arold, Praateek Mahajan, Debajyoti Datta, and Ian Bunner. learn2learn, 2019.
https://githui:
Luca Bertinetto, Joao F Henriques, Philip Torr, and Andrea Vedaldi. Meta-learning with differ- entiable closed-form solvers. In International Conference on Learning Representations (ICLR), 2018.
Jerome Bracken and James T McGill. Mathematical programs with optimization problems in the constraints. Operations Research, 21(1):37-44, 1973.
Justin Domke. Generic methods for optimization-based modeling. In Artificial Intelligence and Statistics (AISTATS), pp. 318-326, 2012.
Matthias Feurer and Frank Hutter. Hyperparameter optimization. In Automated Machine Learning, pp. 3-33. Springer, Cham, 2019.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proc. International Conference on Machine Learning (ICML), pp. 1126-1135, 2017.
Rémi Flamary, Alain Rakotomamonjy, and Gilles Gasso. Learning constrained task similarities in graphregularized multi-task learning. Regularization, Oplimization, Kernels, and Support Vector Machines, pp. 103, 2014.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning (ICML). pp. 1 1165-1173 2017.
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 (ICML), pp. 1568-1577, 2018.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02244 2018.
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On differentiating parameterized argmin and argmax problems with application to bi-level optimization. arXiv preprint / .0447, 2016.
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration com- plexity of hypergradient computation. In Proc. International Conference on Machine Learning (ICML), 2020.
Pierre Hansen, Brigitte Jaumard, and Gilles Savard. New branch-and-bound rules for linear bilevel programming. SIAM Journal on Scientific and Statistical Computing, (95)):194-1211) 1992.
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 arXiv:2007.05 2020.
Kaiyi Ji, Jason D Lee, Yingbin Liang, and H Vincent Poor. Convergence of meta-learning with task-specific adaptation over partial parameters. arXiv preprint 0004::2006609486, 2020a.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Multi-step madel-agnostic meta-learning: Convergence and improved algorithms. arXiv preprint arXtv:2002.07836, 2020b.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR), 2014.
Vijay Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in neural information processing systems (NeurIPS), pp. 1008-10111 1014, 2000.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
10

---

Under review as a conference paper at ICLR 2021
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.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE,
1998.
Junyi Li, Bin Gu, and Heng Huang. Improved bilevel model: Fast and optimal algorithm with theoretical guarantee. arXiv preprint arXiv:2009.00060 2020.
Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang, KiJung Yoon, Xaq Pitkow, Raquel Urtasun, and Richard Zemel. Reviving and improving recurrent nack-propagation. Proc. International Conference Machine Learning (ICML), 2018.
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.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International Conference on Artificial Intelligence and Statistics (AIS- TATS), pp. 1550- PMLR, 2020.
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-basee hyperparameter optimiza- tion through reversible learning. In International Conference Machine Leurning (ICML), pp- 2113-2122, 2015.
Gregory M Moore. Bilevel programming algorithms for machine learning model selection. Rensse- laer Polytechnic Institute, 2010.
Takayuki Okuno, Akiko Takeda, and Akihiro Kawana. Hyperparameter learning via bilevel nons- mooth optimization. arXiv preprint arXiv: 1.XXvv1806.012222 520, 2018.
Boris Oreshkin. Pau Rodríguez López. and Alexandre Lacoste. Tadam: Task dependent adaptive
metric for improved few-shot learning. Advances Neural Information Processing Systems (NeurIPS), pp. 721-731, 2018.
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International Con- ference on Machine Learning (ICML), pp. 737-746, 2016.
Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning or feature reuse? towards understanding the effectiveness of MAML. International Conference on Learning Rep-
resentations (ICLR), 2019.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with im- plicit gradients. In Advances in Neural Information Processing Systems (NeurIPS), pp. 113-124, 2019.
Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu. Watch and lear:: Optimizing from revealed preferences feedback. In Annual ACM Symposium on Theory of Computing (STOC), pp. 949-962, 2016.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Fei- Fei. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 2015.
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back propppropagttion for bilevel optimization. In International Conference on Artificial Intelligence and Statisties (AIS- TATS), pp. 1723-1732, 2019.
Chenggen Shi, Jie Lu, and Guangquan Zhang. An extended kuhn-tucker approach for linear bilevel programming. Applied Mathematics and Computation, 162(1):51-63 2005.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for sho- learning. In Advances in Neural Information Processing Systems (NIPS), 2017.
11

---

Under review as a conference paper at ICLR 2021
Oriol Vinyals, Charles Blundell, Timothy Lillicrap. and Daan Wierstra. Matching networks for one shot learning. In Advances in Neural Information Processing Systems (NIPS), 2016.
Tong Yu and Hong Zhu. Hyper-parameter optimization: A review of algorithms and applications.
arXiv preprint arXiv:2003.0500 056689, 2020.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In International Conference on Learning Representations (ICLR), 2019.
12

---

Under review as a conference paper at ICLR 2021
Supplementary Materials
A APPLICATION TO HYPERPARAMETER OPTIMIZATION
A.1 HYPERPARAMETER OPTIMIZATION
The goal of hyperparameter optimization (Franceschi et al. 2018 Feurer & Hutter 2019) is to search for representation or regularization parameters À to minimize the validation error evaluated the learner's parameters w", where w" is the minimizer of the inner-loop regularized training emor. Mathematically, the objective function is given by
min D (A) DDaal
Σ
(A):E)
RED
s.t. w w²(A) arg min CD, A) = [Drrl EEDr
(c(w, ):E) + R(w, A)),
(12)
where vat and Dur are validation and training data, L is the loss, and R(w, (, A) regularizer.
In practice, the lower-level function CD.(w (w, A) is often strongly-convex w.r.t w. For example, for the data hyper-cleaning application proposed by Franceschi et al.] (2018); Shaban et al. (2019), the predictor is modeled by linear classifier, and the loss function L(w; {) is convex w.r.t. and addition, the sample sizes of
R(w, A) a strongly-convex regularizer, e.g., L regularization. Deal and DD are often large, and stochastic algorithms are preferred for achieving better efficiency. As a result, the above hyperparameter optimization falls into the stochastic bilevel optimization we study in eq. (2), and we apply the proposed stocBiO algorithm here and Theorem establishes its finite-time time performance guarantee.
A.2 EXPERIMENTS
We compare our proposed stocBiO with the following baseline bilevel optimization algorithms.
BSA (Ghadimi & Wang 2018):
implicit gradient based stochastic bilevel optimizer via single-
sample data sampling.
TTSA (Hong al. 2020):
two-time-scale stochastic optimizer via single-sample data sampling.
HOAG (Pedregosa 2016): a hyperparameter optimization algorithm with approximate gradient.
We the implementation in the repository https://gitthe wtt.ccom//aaa//. anp/h
reverse (Franceschi et al. 2017): an iterative differentiation based method that approximates the hypergradient via backpropagation. We its implementation in httpsst//giiiii com/
prolearnerr/yperrorrr
AID-FP Grazzi et al.
2020 AID with the fixed-point method. We its implementation in
https: https://github ccm/ wwwpppolaaaaaea. learner///////rr hypertorch
AID-CG (Grazzi al. 2020): AID with the conjugate gradient method. We use its implementa-
tion in pestps://githhe com/ pro werooeeaeer/byertorrre
We demonstrate the effectiveness of the proposed stocBiO algorithm on two experiments: data hyper-cleaning and logistic regression.
Logistic Regression on 20 Newsgroup: with the existing baseline algorithms reverse, AID-FP, AID-CG and HOAG over logistic re- gression problem on 20 Newsgroup dataset Grazzi et 2020). The objective function of such problem is given by
We compare the performance of our algorithm stocBiO
min F(A, w²) = Deatl
Moaw""
(D
s.t. w" arg min in DERpxx
Σ
L(x,w, y1) (
Σ j=1
exp exp()))w??)
Derl
cp
(ED
13

---

Under review as a conference paper at ICLR 2021
where L is the cross-entropy loss, 20 is the number of topics, and p 101631 is the feature dimension. Following Grazzi et al. 2020), we use SGD as the optimizer for the outer-loop update for all algorithms. For reverse, AID-FP, AID-CG, ptsttss///g gii.tuub.b.............. cwm/cro/aaaaaoeo ea rne r s/hypert t/hypertorch eetechtt on this
the suggested and well-tuned hyperparameter
setting in their implementations application. In specific, they choose the inner- and outer-loop stepsizes 100, the number of inner loops as 10, the number of CG steps as 10. For HOAG, we use the same parameters as reverse, AID- FP. AID-CG. For stocBiO, use the same parameters reverse, AID-FP, AID-CG, and choose 0.5, Q 10. We use stocBiO- B as shorthand of stocBiO with batch size of B.
28
Accuracy
2.0
0.6
AID-CG
1.8
AID-FP
AID-FP
slocBiO-1000
0.5
slocBiO-1000
HOAG
HOAG
1.2
04
1.0
10
20
30
40
50
10
20
40
80
running time is
rumning time Is
Figure 2: Comparison of various algorithms on logistic regression on 20 Newsgroup dataset. For left plot: test loss v.s. running time; right plot: test accuracy v.s. running time
stocBiO-100
Accuracy
0.8
slocBiO-100
Test Loss
stocBiO-500
stocBiO-500
stocBiO-1000
stocBIO-1000
2.0
stocBiO-2000
0.4
stocBiO-2000
HOAG
HOAG
1.5
0.3
1.0
running time
running time Is
Figure: 3: Convergence rate of stocBiO with different batch sizes.
As shown in Figure the proposed stocBiO achieves the fastest convergence rate well as the best test accuracy among all comparison algorithms. This demonstrates the practical advantage of our proposed algorithm stocBiO. Note that do include BSA and TTSA in the comparison, because they converge too slowly with large variance, and are much worse than the other competing algorithms. In addition, we investigate the impact of the batch size on the performance of our stocBiO in Figure 3 It can be seen that stocBiO outperforms HOAG under the batch sizes of 100, 500, 1000, 2000. This shows that the performance stocBiO is not very sensitive to the batch size, and hence the tuning of the batch size is easy to handle in practice.
Data Hyper-Cleaning on MNIST. We first compare the performance of our proposed algorithm stocBiO with other baseline algorithms BSA, TTSA, HOAC on hyperparameter optimization problem: data hyper-cleaning (Shaban et al. 2019) on dataset derived from MNIST (LeCun al.) 1998), which consists of 20000 images for training, 5000 images for validation, and 10000 images for testing. Data hyper-cleaning is to train a classifier in corrupted setting where each label of training data is replaced by random class number with a probability (i.e., the corruption rate).
"We do include reverse, AID-CG and AID-FG hecause they perform similarly HOAG.
14

---

Under review as a conference paper at ICLR 2021
The objective function is given by
min E(,, w²) vDval
L(w" ais Vi)
A
s.t. w = arg min L(w, A) Dull Σ (ac.8))DD
a(Ai) v6) + Cr
where is the cross-entropy loss, a(.) is the sigmoid function, C, a regularization parameter. Following (Shaban et al. (2019). we choose C, 0.001. All results are averaged over 10 tri- als with different random seeds. We adopt Adam (Kingma & Ba 2014) as the optimizer for the outer-loop update for all algorithms. For stochastic algorithms, we set the batch size 50 for stocBiO, and 1 for BSA and TTSA because they use the single-sample data sampling. For all algo- rithms,
grid search to choose the inner-loop stepsize from {0.01, 0.1, 1, 10), the outer-loop stepsize from {10', i = -4,- -3, 22 -1, 0, 1, 2, 3, 4}, and the number T of inner-loop steps from {1, 10, 50, 100, 200, 1000], where values that achieve the lowest loss after a fixed running time selected. For stocBiO. BSA, and TTSA, we choose from {0.5 2', = -3 22
-, 0, 1, 2, 3),
and Q from {3 2', i 0, 1, 2.3).
HOMG
200BiO
220
17.
Traring wa
144
190
HDAG
1DAA
HOAG
TTSA
TTSA
TTSA
BBA
3BA
3BA
r.nring 1s
running 3m2 15
nunring B/11 15
rusringg fim 16
(a) Corruption rate p 0.1
(b) Corruption rate p p=
28.0
slocBIO
slaeBIO
HOAG
13.3
TTSA
18.
TA
B5A
7.
540
running
running
(c) Corruption rate 0.4
Figure 4: Convergence of various algorithms on hyperparameter optimization at different corruption rates. For each corruption rate p, left plot: training loss v.s. running time; right plot: test loss v.s. running time.
It can be seen from Figure that our proposed stocBiO algorithm achieves the fastest convergence rate among all competing algorithms in terms of both the training loss and the test loss. In addition, it is observed that such improvement is more significant when the corruption rate p is smaller. We note that the stochastic algorithm TTSA converges very slowly with a large variance. This is because TTSA updates the costly outer loop more frequently than other algorithms, and has larger variance due to the single-sample data sampling. As a comparison, our stocBiO achieves much lower variance for hypergradient estimation as well much faster convergence rate. This verifies our theoretical results in Theorem S
B FURTHER SPECIFICATIONS ON META-LEARNING EXPERIMENTS
B. DATASETS AND MODEL. ARCHITECTURES
FC100 (Oreshkin et al. 2018 dataset derived from CIFAR-100 (Krizhevsky & Hinton 2009). and contains 100 classes with each class consisting of 600 images of size 32. Following Oreshkin et al. 2018), these 100 classes split into 60 classes for meta-training, 20 classes for meta- validation, and 20 classes for meta-testing. For all comparison algorithms, we use a 4-layer convo- lutional neural networks (CNN) with four convolutional blocks, in which each convolutional block
15

---

Under review as a conference paper at ICLR 2021
contains 3 x 3 convolution (padding = 1, stride = 2), batch normalization, ReLU activation, and 2 x 2 max pooling. Each convolutional layer has 64 filters.
The minilmageNeet dataset (Vinyals al., 2016) is generated from ImageNet Russakovsky et al. (213),, and consists of 100 classes with each class containing 600 images of size 84 84. Following the repository /Arold al. (2019), we partition these classes into 64 classes for meta-training, 16 classes for meta-validation, and 20 classes for meta-testing. Following the repository (Arnold et al.) 2019), we use four-layer CNN with four convolutional blocks, where each block sequentially consists of 3 x 3 convolution, batch normalization, ReLU activation, and 2 x max pooling. Each convolutional layer has 32 filters.
B.2 IMPLEMENTATIONS AND HYPERPARAMETER SETTINGS
We adopt the existing implementations in the repository (Amold et al. 2019) for ANIL and MAML. For all algorithms, we adopt Adam (Kingma & Ba 2014) as the optimizer for the outer-loop update.
Parameter selection for the experiments in Figure I(a); For ANIL and MAMI, we adopt the suggested hyperparameter selection in the repository (Arnold et al. 2019). In specific, for ANIL, choose the inner-loop stepsize as 0.1, the outer-loop (meta) stepsize 0.002, the task sampling size as 32, and the number inner-loop steps as 5L. For MAML,, we choose the inner-loop stepsize as 0.5, the outer-loop stepsize 0.003, the task sampling sizeas 32, and the number of inner-loop steps as 3. For ITD-BiO, AlD-BiO-constant and AID-BiO-increasinng, we use a grid search to choose the inner-loop stepsize from {0.01, 0.1, 1, 10), the task sampling size from {32, 128, 256), and the outer-loop stepsize from {10', = 3, 2, - -1, 0, 1, 2, 3). where values that achieve the lowest loss after a fixed running time are selected. For ITD-BiO and AID-BiO-connttnt, we choose the number of inner-loop steps from {5, 10, 15, 20, 50}. and for AID-BiO-inae BiO--icreassin, we choose the number of inner-loop steps as [c(k + 1)1/4
adopted by the analysis in Ghadimi & Wang (2018), where choose e from {0.5, 2, 5, 10, 50}. For both AID-BiO BiO-constant and AID-BiO Bi---iiO--eeiinng we choose the number N of CG steps for solving the linear system from (5, 10, 15).
Parameter selection for the experiments in Figure I(b); For ANIL and MAML, we adopt the suggested hyperparameter selection in the repository (Arnold et al. 2019). Specifically, for ANIL,, we choose the inner-loop stepsize as 0.1, the outer-loop (meta) stepsize as 0.001, the task sampling size as 32 and the number of inner-loop steps as 10. For MAML, we choose the inner-loop stepsize as 0.5, the outer-loop stepsize as 0.001, the task samling size as 32, and the number of inner-loop steps as 3. For ITD-Bio,, AID-BiO- -o--B---onntantttt and AID-BiO BiO-increasing, we adopt the same procedure as in the experiments in Figure I(a)
B.3 ADDITIONAL RESULTS FOR META LEARNING
T=10
T=10
Training accuracy
0.65
0.7
Test accuraci
0.60
0.39
0.6
9.50
0.5
ITD-BIO ANIL
ITD-BiO
9.40
ANIL
0.4
0.35
1003
2000
2000
4200
1000
2503
10:00
4000
running time is
running time /s
Figure 5: Comparison of ITD-BiO and ANIL on minilmageNee dataset with T = 10.
In this subsection, we compare the robustness between bilevel optimizer ITD--BOO (AID-BIO per- forms similarly to ITD-BiO in terms of the convergence rate) and ANIL (ANIL outperforms MAML in general) to the number of inner-loop steps. For the experiments in Figure 5 we choose the inner- loop stepsize as 0.05, the outer-loop (meta) stepsize as 0.002, the mini-batee size as 32, and the number T of inner-loop steps as 10 for both ANIL and ITD-BíO. For the experiments in Figure 6 we choose the inner-loop stepsize as 0.1, the outer-loop (meta) stepsize as 0.001, the biti-bbtchhaac size 32, and the number 7 of inner-loop steps as 20 for both ANIL. and ITD-BiO.
16

---

Under review as a conference paper at ICLR 2021
T=20
T=20
0.55
Training accuracy
Test accuracy
0.50
M MM
ITD-BiO ANIL
ITD-BIO ANIL
3000
1500
2000
2500
5000
1000
1500
2000
2500
running time
running time
Figure 6: Comparison of ITD-BiO and ANIL FC100 dataset with T = 20.
It can be from Figure and Figure 6 that when the number of inner-loop steps become larger, i.e. T = 10 for minilmageNet and T 20 for FC100, the bilevel optimizer ITD-Bi0 converges stably with small variance, whereas ANIL suffers from sudden descent at 1500s minilmageNet and even diverges after 2000s on FC100.
C SUPPORTING LEMMAS
In this section, we provide some auxiliary lemmas used for proving the main convergence results. First note that the Lipschitz properties in A imply the following lemma.
imply Lemma Suppose Assumption 2 holds. Then, the stochastic derivatives VF(2;E), VG(z;E),
V. (=z and (2G(2; {) have bounded variances, i.e,, for any z and &,
E VF: - Vf(=)]I < M
Ex VeVVVVVGGe: - V. V ? s L?
Ex [= - [=)(1 1
Recall that =xx) - f(x (x)) in eq. (2) Then, we use the following lemma to characterize the Lipschitz properties of (2)), which is adapted from Lemma 2.2 in Ghadimi & Wang (2018).
Lemma 2. Suppose Assumptions and 3 hold. Then, we have, for any x, x' E R.,
(x) v Il
L || x ll.
where the constant Lg given by
La = L+ 2L T
pLM + L3 + TLL
PL
(13)
1
1B3
D PROOF OF PROPOSITIONS IN SECTION
In this section, we provide the proofs for Proposition
and Proposition 2 in Section
D.1 PROOF OF PROPOSITION I
Using the chain rule over the gradient V (f(FL.0'(x)) (zx)) we have Oek
( = (x,, (xxx)) + Oy (x*) V y (x 4d (xx)).
(14)
Ork
Based on the optimality of y (xx), we have V Vyg(En, yn (xx)) = O, which, using the implicit differ- entiation w.r.f. Tk, yields
Oy v2 V0 (xxx) 0.
V (xx))
(15)
Oxx
17

---

Under review as a conference paper at ICLR 2021
Let Vi be the solution of the linear system ing of at the both sides of eq. (15). yields
3 Vyf(ze. 8" (xx)). Then, multiply-
Oy (IR)
v Lo (x=)) = Oy 0y"(xx) V (ar( (xx)),
V V Vz y (zx))
ark
which, in conjunction with eq. (44 yields the proof.
D.2 PROOF OF PROPOSITION
2
Based on the iterative update line 5 in Algorithm I we have vf = v2 a Etzo V Vyg(as vi)) which, combined with the fact that V (2 v/)) is differentiable w.r.t 2h, indicates that the inner output oo is differentiable w.r.t 2g. Then, based the chain rule, we have
05( viE
[ ykt + Quk V. VyJ(on vεE
(16)
0zk
Ora
Based on the iterative updates that u Vk 1-1 - v 1-1) for 1 1= 1,..., T, we have
Oyk
Oyk
V V vyg(zkk 2 03h 1-1
Vig(tn uk 1
8z
Ouk
dy:.
(I
a (2 u/ 1) - aV vug(En, )
Or
Telescoping the above equality over from to yields
OUT.
0yk
T-1
T Σ t=
T-1
Ork
Ozk
[I
-
aV
V
V V Vog vk)
II (I a 2 -=++1
(=0
T-1
T-1
vk
II 5=1+1
(1 - a
V
(g(x,
(17)
where (i) follows from the fact that
dve Dagg
Combining eq. 16 and eq.
17 finishes the proof.
E
CONVERGENCE PROOFS FOR AID-BIO IN SECTION 4.
For notation simplification, we define the following quantities.
r T= +
3r
(1+ V
pM
n²² )² ōT,N = -41=- + 6L
VK - VK-1 2N
122
23ML
23LMX 2 Do = =1y00 - -y (2o) 1110 - 2
Ω 88
Bk²
(18)
112
42
We first provide some supporting lemmas.
The following lemma characterizes the Hypergradient where ( is given by eq. 3 via implicit differentiation.
estimation error
Lemma 3. Suppose Assumptions and hold. Then, we have
(4(T))) - v4(xx) (111--s1pppppppppp a4) 1000T1ll"2000000000 (xx) - 2 +6L VR 1
2N 1|
+1
where I' is given by eg.
18
Proof of Lemma
Based on the form of ( given by Proposition 1 we have
())))))) - ( <3 V 1f (xx)) V.I o 21 + 3// V yolee, 11 -o6
3 V V V (2 (œx)) V V Vag( 1
18

---

Under review as a conference paper at ICLR 2021
which, in conjunction with Assumptions | and yields
()(x))- (+(xx))l < 3T. 110" (mx) - ~ + 11 u/ +1 1337111111 y ?
<3 <3L (Ix) - 11 3L 1 1 11+ 37²
112 Ilui -y vxx)) 1. (19)
where (i) follows from the fact that || - |1 (zts y (xx))) |||| V y (Zk, (x+))]] - nh4
For notation simplification, let 0 (Vig( (z 0 ) V of (ok. of ). We next upper-bound log
2/
in eq. 19) Based on the convergence result of CG for the quadratic programing, e.g., eq. (17)
in Grazzi et al.
2020), we have lle Txll S vxl
vk-1 VK+1)
N
lleß ūxll. Based on this inequality,
we further have
VK 1 N |1u - of |1 1 - -ūxll + 11u - Txll S 11 - -xell + Vk
VK (1+1) 11u -
-
-
Tell
- )
Vk - )lma Vk +
Vk - 1) N
Tulll + vkl
- -02l-
(20)
vk +
Next, based on the definitions of 2x and U2. we have
||0| - 0xll
=I[ v ) v ff vie) (V (xx)) v
k
+
pM
| y (*x)]]-
(21)
n
Combining eq.
19 eq.
20
eq. (21 yields
312² + 37 111" (Ixx) 1/El1 11 +61²2x
/v-- 1 2N
|) (xxx))
1 -
-011
n12
VR 1
6T. (1 Vkl
vrr -1
1 N 2
)
+
PM n2²
looT y (*x)),
Vn
which, in conjunction with 11% (xx))l S (I-aw) & 11 y (Ix) and the notations in eq. 18 finishes the proof.
Lemma 4. Suppose Assumptions
7 and hold. Choose
T > log (36k(N+ + pM )² + 16(x²= +
1LMs / log
1 = Okk)
122
1²2
1 1 a
N 2 log(8n + 48(n² + 2MT.
2LMK
V + 1
+
32 L kt/ log
= O((R),
(22)
1²2
2²2
1
where I' is given by eq. 18). Then, we have
1
k-1
1 k-1-j
l102 V (Ix) +1lut 20112 <
Do
Ω
[2,(21))
(23)
2
j=0
where Ωi and Do are given by eq. 18)
Proof of Lemma Recall that v8 = vー Then, we have
1 yy (1=))]
< T - y² (xx- || + 2xl) y/" (x
(0)
22 / 1102 '² 2 2x² 21
52(1 - an))² 7 1 - '² (xx- 2
4x 1 - (0(
+ 4k2 332 ( 1)
(10
< (2(1 - TTI + 3x223I111- (31(1-44)7111 a)))")11" (x==)(xxx) - vi-111 112
VK - 11 2N
+ 2224-11.8
V v
11 + 4x² 32 ( 1)12. (24)
19

---

Under review as a conference paper at ICLR 2021
where (i) follows from Lemma 2.2 in Ghadimi & Wang 2018 and (ii) follows from Lemma 3 In addition, note that
1 u21l
=1loß 1112 S 22110-11 - 1 112 + 21 -
(1)
<4
1 + Vk) 2 (m+ PM) 2
122 (1 (1-a a y² (112
v k - 1 1|uk-1 - 112 + 21 -
4k
(25)
V +
where (i) follows from eq.
20 Combining eq.
25 with 1 - - || S (k²2 + 2ML + M
Tk-ille II we have
11og - 221?
(2)
16k
x +
PM 122
2
+ 4 4n2 +
ALMRY 2
(84)) - -app) - (xxx
12
2MT.
2LM
2
(vr= 11 110ā-1 - 11-1112
2N
+ An + 48
122 +
12 +
12
+ 4
n²²
2ML
2LMK
2
(
(26)
12
where (i) follows from Lemma
Combining eq.
24
and eq.
26 yields
1 (xxx))
+ ||
18k
+ PM 112
+8 x²²
4LMKY
(34)
(1-)) (ap))" - V (x(x==1))
112
4n + 24 (n² +
2ML
+
2LM
8222kk
(Viz- (
2N
11 - -0--11"
42
12
88( (n²
2ML
2LMK
1²
112
which, in conjunction with eq.
(2
111h y² (Ixx)1 + 11u - =2112 (110%_ - '² (Ix-
1)1= 11 11
+ +8( Bn² + 28ML
25LMK) 2
12 +
(27)
n2
Telescoping eq. (27 over k and using the notations in eq. I8)
we finish the proof.
Lemma 5. Under the same setting as in Lemma
we have
(((((=)) (<((x)) Sōr.N (2) Do + 8r
1-1
k-1-j
(2)22))
2
1=0
where 8y,N, Q and Ag are given by eq. (8
Proof of Lemma Based on Lemma 3 eq. 18 and using ab + < (a+c)(b+d)) d) for any positive
a, d, have
( ( <dT, (Ilv (xx) w2212 + |10g - =
which, in conjunction with Lemma 4 finishes the proof.
20

---

Under review as a conference paper at ICLR 2021
E.1 PROOF OF THEOREM
In this subsection, provide the proof for Theorem I bbased on the supporting Lemma 5 smoothness of the function ((x) established in Lemma we have
Based on the
Le
(xx++1) (x())) + (Z)) #6+1 - =4) 2
| - xx xx1
<m())) - 3
(p))))) - [)(xx)) - V (Lol11
+ 3 V . {1)))11
3 2
3 La [0(x)))1 + (5 + 1T, |[ - (o(n))?? (28)
<0(r))
which, combined with Lemma yields
( B Lo
[+((=)]1 (g- + LL Jor (1)² Au
(xx++1) <I(x))
2
R-1
+
_ 2/2
+ B² Log 8T,
Σ
(
(29)
-=
Telescoping eq. 29
over k from 0 to K yields
( - p La
K-1
[+(2))]
<
(<x0) - inf ((x) + (5 Lo
B
(L ST,NAO
K-1k-1
8
88 Lo ST Ω
which, using the fact that K- k= Ejz (4) 2 E [z=((=)) yields
k-
[+
E
E [+ s
(
B L (3n + 202 Lo) )OT,N
K-1
k=0
3 + 8 Jr, )
S (rro) - inf ((n) +
(30)
Choose N and T such that
(2 + 22, ST,N S 7 &, S
(31)
Note that based on the definition of 8 in eq. satisfy eq. (31. Then, substituting eq. 31 into eq. (30) yields
188 it suffices to choose T 2 (Kx) and N 2 @(vk)
- 3 Lo
( 3d (L Ao.
[ ((xa) inf (n
(32)
which, in conjunction with 3 <
8L. yields
1 K
64L (o(z)) inf, F(x)) 54u
|+)(2)))
(33)
K
In order to achieve e-accurate stationary point, obtain from eq. 33 that AID-BiO requires
at most the total number K = O of outer iterations. Then, based on eq. 3 we have the following complexity results.
Gradient complexity:
Ge(f,c) 2K
= - Ge(g. - KT= Ok4cc1))
Jacobian- and Hessian-vector product complexities:
(V K = O (1)) HV(g, = KN = (1:3.5
Then, the proof is complete.
21

---

Under review as a conference paper at ICLR 2021
F CONVERGENCE PROOFS FOR ITD-BIO IN SECTION 4.1
We first characterize important estimation property of the outer-loop gradient estimator (f in ITD-BiO for approximating the true gradient (ab(2))) based on Proposition 2
Ban
Lemma 6, Suppose Assumptions
and hold. Choose S +. Then, have
(f v v2( L(L + 11(1 ap)+ +
2M (Tp Lp) (1 - oss)) - )lee 11:8 4 (xx)l
0rs
P + LM(1 oo))²
1²
Lemma 6 shows that the gradient estimation enror |
(xx))
decays exponentially
dag
w.r.t the number I' of the inner-loop steps. We note that Grazzi et al. (2020) proved a similar result
via fixed point based approach. As comparison, our proof of Lemma 6 directly characterizes the rate of the sequence corresponding points along the inner-loop GD path well as the optimality of the point y (zx).
( ('y @ãzc" O...., T) converging to
dy (ar)) via the differentiation over all
8øg
Proof of Lemma 6 Using (*(())) = V yd (xx)) +
(mx) Ozz
vof (xxx (xx)) and eq. 16
and using the triangle incquality, we have
0 (a vit)
Ork
Oyk
(xy() Oxk
-I (IK: vie)
|1 [ (e ve'
+ Oy" (xxx)
(okk vk) (
VyJ(oKs (xxx))
aok
(
2 LllT - (xx))) M
Oyk
Oy" (ark)
+
Oy (xxx)
|10 - (xxx)ll
(34)
Ook
Oek
Ork
where (i) follows from Assumption
Our next step is to upper-bound
By
(xa)
in eq.
34
Ore
Oek
Based on the updates ví. = rule, we have
1-1-1 =yk
a Vyg(En, ui 1) fort = 1,... T ITD-BiO and using the chain
Oyi
Oyk
Oyi-11
yy +
(35)
0rk
0zk
Oxk
Based on the optimality of y" (axx), we have Vug(sk: y² (xxx) = which, conjunction with the implicit differentiation theorem, yields
V V vglg,, 8² (xx)) + (x*( (ook)/ggee Villz, 4 (xx)) 0.
(36)
Dxx
Substituting eq.
36
into eq.
35 yields
Oyk
Oy" (*x)
Oxz
Ouk
Oy 0y*(*k)
Oyk
V. VeVgg( 1
Violzx 2i
Oxk
Oxy
V V.V V.glEKK (xx)) + Oy (x*)) (xx)))
+
OzL
Oyh
(y)()k) a (V. Vyg(un 2 +1 V. Vng(an, (xx)))
Oy (xx)
Veg(zk.
Oy" (II)
+ a
(Viglani ViglEn vi -1)
(37)
Oek
22

---

Under review as a conference paper at ICLR 2021
Combining eq.
(36)
and Assumption 2 yields
Oy"
(ara)
V Veg(nn v (olas. yf (xx))] (
L
(38)
Ork
Then, combining eq.
(37
and eq.
38 yields
dyk
Qy (2x)
IA3
(ZR, 3/ -||| 0yk 1-1
dy (2xx
a v
0.k
Ozp
Oxx
7 Lp
l1ub y" (xx))l
(i)) (1
0yk 0x
Lp
ap)
T+
llok
y (xx)ll, (39)
Ōrk
Ork
1
where (i) follows from Assumption and (ii) follows from the strong-convexity of g(x, +). Based on the strong-convexity of the lower-level function g(x, -). have
llyk
---1
y² (a+= s (1 - apd t-1 1 (rx)))
(40)
Substituting eq.
40 0y (2x)
into eq.
39 and telecopting eq.
39
over from to T, we have
dyg
Qyk
By" (xx)
<(1 az)²²
Dokk
ark
aok
Ork
Lp
+ (+
(1 aa-a aa))----((1 axu) (14 n² (xxx)l
1
1=0
-(1 ar)rr
Oyh
0y" (y((TN)
2 (TH + Lp)
(1 -ap) - 11 y (Ix)]l
aok
Oak
112
L(1 axx)
2 (T Lp)
oip) 2 11 y" (xx))l
(41)
11
1
0u 8i
where the last inequality follows from
= 0 and eq.
(38). Then, combining eq. (34), eq. 38
eq. (40) and eq. (41) completes the proof.
F.1 PROOF OF THEOREM 2
af(xa.0) day
Based on the characterization on the estimation error of the gradient estimate we now prove Theorem 2
in Lemma 6
Recall the notation that (
Using an approach similar to eq.
28
we have
((+++) <x())) ( LL [[
g + Lo [V (
(42)
which, in conjunction with Lemma
6 and use 11 1³ (Ix))l < A, yields
8 LL [x+((==)]1
((z441) <(((x))
8
[L + 222
(1 aI) + 4M² (Tμ + Lp)?
+ 3A
+ LL)
(1 Tw))
112
4
3
1.2 24
+ 3
+ 3 LP)
(43)
2
112
Telescoping eq.
43 over k from to K - yields
K
Σ
2 LL (VL0(211)
((x0) infa ((x)
+ +3(1 ( 3LD)
L²M -app2r
K
3K
2
1²
k=0
+34
( + +BLO)
(18(T+ n22
(TT
Th +
4M2 (Tp T.p)²
(1 -1-
(44)
12
4t
23

---

Under review as a conference paper at ICLR 2021
Substuting 3 = 4L. and T = log
maxx {
3LM 91L )
36AM2 1p)
/ log -aa
(1 C-aa)p
On log )) in eq. (44) yields
V (xx))) 16Lo((()0))
inf, ((x))
26
(45)
K
K
In order to achieve an é-accurate stationary point, obtain from eq. (45) that ITD-BiO requires most the total number K = O(K of outer iterations. Then, based on the gradient form given by Proposition 2
we have the following complexity results.
Gradient complexity: Ge(f,c = 2K -(( = KT = 0
Jacobian- and Hessian-vector product complexities:
HV (V - KT -00x0 .VVG,
KT =0 -KT ( (0xx==tttt00000 1ox
Then, the proof is complete.
G PROOFS OF MAIN RESULTS FOR STOCHASTIC CASE IN SECTION 4.2
In this section, we provide proof' for the convergence and complexity results of the proposed algo- rithm for the stochastic case.
G.1 PROOF OF PROPOSITION
Based on the definition of uo in eq.
and conditioning on Tk, uf we have
BuQ
Enj
II (I C( B,) Fork : Dr),
j=Q-9
1 I V
Σ (1 Vilan ( V f v
"
q=Q+1
20
n(n Hggk, oft 1
( - Σ (I - 1 V 2 v Vy (
q=Q+1
which, in conjunction with the strong-convexity of function g(x, :), yields
Σ (1 M 5 (1 (1-11) -
Beq - Vig ve -
5n
(46)
24

---

Under review as a conference paper at ICLR 2021
This finishes the proof for the estimation bias. We next prove the variance bound. Note that
B
Σ
(T-
vē: Dz) (V20(o "
(1 vt)
1=Q=
Q-1
(1 - V (B) - (2)g(z2) 8/2 )) 1 1/2 +
2M2
2B
DRDs
P=Q-1
Σ
II (1
G.. - Σ (T - V/ (T 2E))
M2
Q=Q-
2M
+ 11
V (F )))) (()
M2
D2Ds
Q=0
(8)
241
Σ
- V - (1- ( ( )3
Q
M²
4(1 n1)2
2M²
1²
D2D1
4=0 Q++1-
T=0
(8)
Σ
Q
(I (.)
- (T
Vi
-=0
/=Q+1-Q
M,
4(1 4(1- m2) M²
22²
+ D2Ds
(47)
where (i) follows from Lemma I (ii) follows from eq. 446). and (iii) follows from the Cauchy- Schwarz inequality.
Our next step is to upper-bound Mg in eq. (47). For simplicity, we define a general quantity M, for by replacing q in Mg with i. Then, we have
Q II
EM, -E
v V (z vI (I
(I- G (B)) - (I
Q+2-1
Q
V 3 ;B)) 1
+ vy 2gg wx)
Volk, vT: B0+l-s))
πI
Q+2-i
+ 2F (1 - // V/ (ig vir
II (I- V- ve: (1 - 17 V2 DiY''
-=Q+2-
Q II (T- V 2ē B,))
1/( (V vtt) V.G BoH1-s))
/=Q+2-1
- (1 7 (zx, vf
II
(.: (1 n V (2
/=Q--i
12
+ n V (Ik. v Vi vT: i))
II (1- V- Gi ;1,) /=Q+2-i
(00
(1 n + 112 mnn 2 V2. V2 vi
VjG(z,, ui B)+1
(18)
1,2
2 (1 m + 12 - m/11 26-2
(48)
BB42-sl
where (i) follows from that fact that Esg11 V ut BQ+1-1) = Vi vk ) (ii) follows
from the strong-convexity of function G(z, :: :), and (Mi) follows from Lemma] 0
25

---

Under review as a conference paper at ICLR 2021
Then, telescoping eq. (48) over i from 2 to q yields
9
BMg < L11 m2122
[Q++-51
which, in conjunction with the choice of |BQ+1-51
= BQ(
m/4) - for -,,,, Q yields
L
1
5-1
EMM Stp - muu) 20
BQ
Tpp
j=1
11²
(1
mp)
2q
I-n
-1
1
nL
dplp BQ (1 np)".
(49)
BQ
(1
1-1/44
Substituting eq.
49)
into eq.
447
yields
Q-1
Q
Σ
II
n
; - (Vgg ,v,
f=Q-9
(1 nu 1 BQ (1 - -2) + 4(1 21))202MM² 2M
11!
<4n
12
0=0
4(1 mp) mp) 22
2M2
(50)
12
n²
D²D
where the last inequality follows from the fact that Σ x9 S -.-
Then, the proof complete.
G.2 AUXILIARY LEMMAS FOR PROVING THEOREM 3
We first use the following lemma to characterize the first-moment enror of the gradient estimate ( whose form is given by eq. 6
Lemma 7. Suppose Assumptions
and hold. Then, conditioning on vr and y we have
L MT
LMP
V =xxx))) + 2L 2 - mm))2Q
(+)(())) (xx))) < 2 T.
1
122
112
Proof of Lemma
7 To simplify notations, we define
(ΦT(T)) = V. f
V Vagg,,, v g w²ii - V fxx,
(51)
6 and conditioning on uy and of we have Based on the definition of ( (Ixx) in eq.
(xx) = -V. Vn v yi FEnQ
- V V Vyg(z vi ()) (V ot - V,
which further implies that
|| (=x22)
<2E V (2+) 2 = -
<2E ( v
21 1
V2g(ZRK vee
' ff vt )1
/2 - v 2L M nHe 2Q+2
(52)
where the last inequality follows from Proposition the right hand side of eq. (52). Using the fact that
3 Our next step is to upper- bound the first term at < I and based on Assumptions
2 (r y) -
26

---

Under review as a conference paper at ICLR 2021
and 3 we have
[V
9 Va Val(oNn (xx)))
I
11u1 1/" (I+)l1 + MT lIve - yx
+
1
+ L LM V ((g v -Vygooh 8" (xx))=²1
1 MT + LMP
L
11u1 y (rx))l
(53)
2²
where the last inequality follows from the inequality | - 15 S MM M₂
M2ll
for any two matrices M1 and M2. Combining eq. (52) and eq. (53
yields
[z)( v=(=>)| s 22
L
MT
LM 2 122
1 (xx))
2L M - m11
1²2
which completes the proof.
Then, we use the following lemma to characterize variance of the estimator ()(xx))
Lemma 8. Suppose Assumptions)
! andd
hold. Then, we have
E| ((()) (xx)) 5 4L M
18L
M
L2
16L 2 m2)2
+
+
+
+
122 DT
422
Dj
1²
422
L ++++
MT
LMp
2
+ [+ +
+
Ellyy y (xx))1
112
Proof of Lemma 8 Based on the definitions of (T(()) and V in eq. conditioning on 2y and ui. we have
44 and eq. 51) and
E ~ (=x))1
- V AΦt (x+))1 ((()) - (2(12)1
(10)
2M
< 2B
V. v, G(r, ; DeleQ
V. Vog(E vit Vig(t,, vi) Vyf(z v D|2++
D
L2
MT
LMp
2
+
L
+
11 y" (=x)))
12
(11) 2
E|
V
Gar vi: DG) V. Vog v1 AL - (Vg(( - n (I v
112
L
MT
LMp 2
2M2
L
4 -
1 J (xx))1
(54)
12
D,
where (i) follows from the fact that ED DD..Dn.D. Dr
(o(x)) (*K), (ii) follows from Lemma
and eq. 53 and (iii follows from the Young's inequality and Assumption
Using Lemma and Proposition 3 iin eq.
54
yields
M/
T2
16(1 m/1 1222T22
822
+
2
42
D2D
1
MT
LMP 2
2M
+ L+
4² 1111 y (xxx))1
(55)
D₁
which, unconditioning on and vp completes the proof.
can be seen from Lemmas 7 and g that the upper bounds on both the estimation error and bias depend on the tracking error 10r y (xx) The following lemma provides upper bound on such tracking emror Viv (xxx))))
27

---

Under review as a conference paper at ICLR 2021
Lemma 9. Suppose Assumptions
7
andd hold. Define constants
A
- 1
2T
(2
1.2
L
I
+
MT
))
L
u²
1
P
M
181,
M
16
1612
+
+2)
+
D&
112
Dj
u²
4²2
432
--
(56)
1+
Choose T such that X < and set inner-loop stepsize a Ltp Then, we have
Blluk (xxx)1
((1--)) T. (T++1)))
2T
11y0 - D (xxo)]] + a²
w +
Sx*
w Σ
1
VO(z)))
1 LNS
T,ss)
j=0
Proof of Lemma 9 First note that for an integer t < T
l1x yy" (2+))
=1lv/ ++ v/1l + 2(v vi.vi y (xx)) + 1 y" (1x))
=a =V ui: 8.)11 2 G u St). vi y (mx)) +lykk (xx))1 (57)
Conditioning on v\ and taking expectation in eq. 557). we have
E [+1 y (axx))²
(
2
0 + (0( 2a V Vug(E si) 2h vx
S
+ 11v1 y" (2x)
(10) a 0²0²
llvi (+ IV Ve( v11
+ + Vo
u11l - 2x
8
L +
L+
+ 11 -0((x)))"
0²
- (1²1--)
2
VV yo( 1111 (1 2014 11 - y" (Ir=)]?
(58)
S
+++++
++
where (i) follows from the third item in Assumption (ii) follows from the strong-convexity and smoothness of the function g. Since a = L+#
2
we obtain from eq. (58) that
E y (xx)
11
lIvi y (xx) + (L+ 5
4
(59)
+
Unconditioning on 2 in eq.
59 and telescoping eq.
559
over from t yields
L μ
2T
o²
E Eliy y (1x))1
Ely12 y (xx))1²
T. + 1
Lus
L - 1
Elibi 1²¹ (xxx + o²
(60)
1 1z
Iup''
where the last inequality follows from Algorithm that :/ = vĀ- Note that
El | y² (1x
<2E 1 1/" (21- + -2 (#R-1) 1²" (mx))l
2E 1 32 1112 + 21,²
Bl| - 11-
1122
<2E 1y 3¹' 1112 + 2,82
E|| 1 o (x<=
112
4,32
S2R 1 3/ (aa-1))² +
E 2[
112
1.2
E
(61)
412
28

---

Under review as a conference paper at ICLR 2021
where (i) follows from Lemma 2.2 in Ghadimi & Wang (2018). Using Lemma eq. 61 yields
yk VK=1
(xx)))
132
12
MT
LMP
2
4,2
(1+
+
+
1 - y (rk- 1)12 +
(+<=))))
12
11
P
122
1
+ L22
M2
18L2
M
161j L3 M²
16L2
mun
+
+
+
+
(62)
x²
D&
n
Dj
n²
B
n2
Combining eq. (60)
and eq.
(62)
yields
BllyÉ y² (xxx)1
レ- M. 27
4.3
L
MT
LMP) 2
2
L
+
+
Bllbk-
8 (Ixxx
L+ m
112
P
112
L 4-11 )
27' 4.8 L?
(4L
S8L2
M
1612 L*
16L M (1 n7)229
+
+
+
122
12D
112
Dj
112
B
1
4.8 1 122
L L-P p. V )| +
0²
(63)
L
Based on the definitions of X, w. A in eq.
(56). we obtain from eq.
66 that
FIVV - y 2 <ABIIRL - (xx-1))1 wA +
wiF
(
(64)
Lus
Telescoping eq. (64) over k yields
Bllyk y² (xxx)1
k-
WA + a²
<x"Ellvd - y² (xo))l + w Σ
-
11
Lps
1-X
1=0
S*at ((+-#)
27
- - y (z0)ll + o²
k-
w + Lus
+ w Σ
k --
LUS
1=
which completes the proof.
G.3
PROOF OF THROREM 3
In this subsection, we provide the proof for Theorem based on the supporting lemmas we develop in Appendix G.2
Based on the smoothness of the function (xx) in Lemma
we have
L
((Ix+1) <x(xx) (V #441 xn) +
| xx
< - (V (x(x)) + 3 La (+(x)))1 82 (vx) - (Ix)))
For simplicity, let Ea E( Ih v ). Note that choose 3 aL.. Then, taking expectation over the above inequality, we have E4(2*+1) <ED(xx) - (EVV E. (x(())
L. V
8 VD (2)) (1x)))
(8)
8 [ - (
<BD(Ta) + E E (()))) - vo(ax)) 4
E (xx))
2
RD(x)) 3
BL - 2
(x&))
112
3
M2
8L
2
16m M
M2 29
+2
4 D
112
Dj
#2
n22
53
1
MT
LMp
2
L
+
+
+
T..
y² (xx))1
(65)
p
112
29

---

Under review as a conference paper at ICLR 2021
where (i) follows from To simplify notations, Let
inequality, and (it) follows from Lemma 7 and Lemma 8
5
1
MT
LM
122 )
L+
(66)
4
Then, applying Lemma 9 in eq. 65 and using the definitions of w, A, À in eq. (56). we have
M [x] (1-m))a2
3
(*(++)) <BD((x)
+
n²
B
(1-+
27
σ²
+ A + SrA#
1190 - - (x0))1 +
4
LUi
Be(ws
0² I
BBw
Σ
Vo(x))
1-2
1=0
Telescoping the above inequality over k from 0 K 1 yields
K-1k-1
EΦ(ωx) ((xo)=
BDw Σ Σ V
E
k=0
KBA
27
Bv
+
(T.,+
1190 - y (fo))l +
4
TUS
1-
KBL 2 - m2)
KBu(ws + LP3)
122
1-X
which, using the fact that
K-1k-1
K-1
K-1
1 K-1
ΣΣ 2
Σ A
Σ B
<
Σ
E
V 13
k= j=
k=
yields
1 wW 1 K-1
E
(x++)
A K
k=
(1r)) inf (xx)
r( ((b
11:0 - 8" (20))1
LAs
o²
A
LP
(1
+
3K
K(1 -) X)
4
42
a² y(w A
LaS
(67)
1
log
(12 1802 2 (I+ Mr. )
Since and T
we have 1 and hence eq. (67) is
AL
logg 412)
further simplified to
-
Dw
4
5
K
A=
(20)
inf, ((x)
20((
you - 3d (2o)1 o²
T
A
L 12M2(1 mq
BK
K
4
n²2
+ 2v 20(wS)
)
(68)
30

---

Under review as a conference paper at ICLR 2021
log
(12+ 18:32
(L+ 1.2
Mr
By the definitions of w in eq. (56) and in eq. (66) and T
>
p²
n
2 log x=
have
5/
L 12
22'
L
MT
LMP 112
ww
112
T. 1
11
11
5
L +
+
MT
LM
1
2
5 48'
(69)
12 + 48
(L +
12
Mr
LMO y2
log (V3
12 Ms Life
In addition, since T
we have
log( LoE)
2T
_)
5 L 1 27
L
MT
LMp
2
5
L
<
(70)
L
I + p
1
pb
112
4,3
Substituting eq.
69
and eq.
770p in eq.
(68 yields
B B K
8( 8(0(z)) inf, ((x) + 211vo 12" (xT)
+ (1 (1+ K Lps
x) 16vo2
1 (xx)]l
BK
0
11
M2
+ A
1² (1 - n1) 2Q
(71)
3
which, in conjunction with eq. (56) and eq. (66). yields eq. (T) in Theorem
Then, based on eq. (10). in order to achieve an e-accurate stationary point, i.c., E [=] s e with E chosen from Fo. ... IK-1 uniformly random, it suffices to choose
K 32L4 (#())) in ((x) + ll - 3" (xo)) = -0 R3
T (k))
(()
2 = Q lo
D, (
B =
Note that the above choices of Q and satisfy the condition that B 2 2(1 (11ーwwターT required in Proposition 3
Then, the gradient complexity is given by Gc(F,c) KD, = O 3) Gc(G,e) KTS = O In addition, the Jacobian- and Hessian-vector product complexities are given by JV(G,e) = KD, = Onee and
BQ(1- - na)ーr KBQ 7H
6
R²
HV(G, K Σ
< 0
log
==1
Then, the proof is complete.
H PROOF OF THEOREM 4 ON META-LEARNING
To prove Theorem 4 we first establish the following lemma to characterize the estimation variance
Eg]
@Cn(or. [B)
(Cp deL
2 where wi is the output of inner-loop steps of gradient descent
D0% the 4thh outer loop.
Lemma 10. Suppose Assumptions and 3 are satisfied and suppose each task loss Ls, (cb, wi) is
p-strongly-comver w.r.t. Then, we have
0 @Cp(ou Φx w.: B))
aC (ok: w
L 2
Eg
5(1+
<
Jok
B
31

---

Under review as a conference paper at ICLR 2021
Proof. Let قh [w .... w ve) be the output of T inner-loop steps of gradient descent at the bthh outer loop. Using Proposition 2
we have, for task Ti
@L.D (0k; w
D. (On, "hl
0Φk
T
T-1
+
V on Ls, (dn, w(.k)
II
(1
aV w Ls. (0x, w1 m, LD, (dx, w(xs))
-=(+1
① SM + aLM Σ (1 - an) au)) M + LM
(72)
where (i) follows from assumptions 2 and strong-convexity of Ls, (0, -. Then, using the definition of (o, wi B) B EieB LD, (Ø, wi), we have
eL (tbk, :B)
OLD (LD(de, w
@LD, (0k, w
OLD (LD(On, W
Eg
E,
dek
dΦk
(4)
TLD, (ok; W...
E;
13
Oep
(1))
L
2
(73)
p.
[B]
0Cv, (du.
where (1) follows from E,
and (ii) follows from eq. (72)
Then, the
Dbk
8b
proof is complete.
Proof of Theorem 4 Recall (()) = (D ui (x)) be the objective function, and let (o((k))
BCD (cb. "
Using approach similar to eq. (42)
we have
Lo
4 ((x++1) (((()) + (V 04+1 - dx) +
|1u+1 - -xxl1
2
<Φ(Ø)) 3( ( @LD(du wi: :B 13)
8z 1B2.1
0L (1xe, wx :3)
+
(74)
Dōk
Ook
Taking the expectation of eq.
74 yields
(6) - AT (cb), v + L TE (dx))))
E (+((++1)
S <BD(
2
B Lo
(0x wh B)
2
+
E
2
Joh
(1)
L E (1 + 8 (1+ L
M2
<
BE (d())) vQ(σm))
2
2
B
33
(5 + L B() - (
B
<O - -22
Lo
+ E| (xxx))
LL La (1
L M
(75)
2
B
where (i) follows from EgCD (v, WH B) = Lo(ou, wf and (ii) follows from Lemma 10 Using
Lemma 6 in eq. (75) and rearranging the terms, we have
K
1
1
Σ
3L.
(0x))1
K K=
2
(00) inf (())
+ +3( + :LB
(1 -44)2T
ILD
L M2
(1+
BK
112
2
[
+ +34 ( + +B )
(.2(T.+ + 11)
(1- -Tp) +
4M2 (Tp Tpp
(1 ant) T-)-
112
4
32

---

Under review as a conference paper at ICLR 2021
where A max; 10 i" (0x)1l < co. Choose the same parameters T, T as in Theorem
Then,
we have
16I. (
inf (()))
2c + (1
L 2 M²
B]V <
=)
K
3
8|B|
k=
Then, the proof is complete.
33


Reviews:
[{"review_id": "dJe63UHHKv", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overall, I vote for rejecting. While most of the related literature focuses on computing the hypergradient, this paper tackles the full optimization problem, which is much harder and more interesting. In particular I really like the idea of taking advantage of the (finite sum) structure of the bilevel optimization problem (algorithm 2). The problem tackled is very important but I have a lot of concerns regarding the novelty of the 'proposed' algorithm 1. Moreover I do not understand the focus on avoiding to compute the inverse of the Hessian, since in such application the Hessian is never inverted, only linear systems are solved, which is much cheaper. \n\n##########################################################################\n\nAdvantages of the paper:\n- The paper is overall well written.\n- The idea of algorithm 2 is elegant.\n\n##########################################################################\n\nConcerns \n1- Authors may have missed an important reference [1], which is a seminal paper on bilevel optimization for hyperparameter optimization.\n\n2- Authors claim novelty on algorithm 1 'design a new bilevel optimization algorithm'. \nI may have missed something important, but it seems to me that algorithm 1 not new: it is exactly the algorithm in [1], Section 4.\n\n3- Moreover how do the authors chose the stepsize of the gradient descent $\\beta$? IMO this is a strong bottelneck in practice, that is why [2] uses LBFGS once the hypergradient is computed, and [3] uses a line-search procedure.\nDo authors have heuristics to choose the stepsizes $\\beta$ in practice?\nThis is paramount in practice, and the value of the stepsize is hidden in appendix, set to '0.001'. This seems very custom, and not general. How do authors know that the proposed algorithms converged for this choice of stepsize?\n\n4- 'proposition shows that the differentiation involves computations of second order derivatives'\nI do not understand. To my knowledge, the hypergradient $\\partial f$ can be computed in 3 differents ways: implicit[3], forward or backward [4].\nTo my knowledge there is not Hessian inversion, neither in the implicit nor in the backward: algorithm 1 in [3] solves a linear system to compute the gradient, and no Hessian are inverted in [1], Section 4. \nI am very confused with this Hessian inversion problem. Since I did not understand it, I lost a lot of the motivation for the introduction of algorithm 2.\n\n5- At the beginning of section 2.1 it seems that the end of an old sentence remains in the text.\n\n6- Part 4 is very technical and felt to me like an arid succession of theoretical results. IMO more insights and comments on the theoretical results would be very helpful for the reader.\n\n7- Part 5 proposes experiments using algorithm 1, which is already known (unless I missed something). Experiments on algorithm 2 are only in appendix.\nA comparison with  the approximated procedure of [3] would strength the paper: from my experience, approximated gradient like in [3] drastically improves the convergence time.\n\n\n[1]  Domke, J. Generic methods for optimization-based modeling, AISTAST 2012\n[2] Deledalle, C. A., Vaiter, S., Fadili, J., & Peyré, G. (2014). Stein Unbiased GrAdient estimator of the Risk (SUGAR) for multiple parameter selection. SIAM Journal on Imaging Sciences\n[3] Pedregosa, F. (2016). Hyperparameter optimization with approximate gradient, ICML2016\n[4] Franceschi, L., Donini, M., Frasconi, P., & Pontil, M. (2017). Forward and reverse gradient-based hyperparameter optimization. ICML2017", "extra_scores": {}, "extra_text": {}}, {"review_id": "XPpAeMHHvz", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents two algorithms - one for the deterministic and one for stochastic bilevel optimization. The paper claims the methods are lower cost in computational complexity for various terms and easy to implement. A finite-time convergence proof is provided for the algorithms.  Empirical results are presented for meta-learning, and (in the appendix) hyperparameter optimization.\n \n\nStrengths:\n \nThe deterministic bilevel algorithm is easy to implement and has a convergence proof given standard assumptions.\n\nThe stochastic bilevel algorithm has a convergence proof given standard assumptions.\n\nThey investigate in-depth how the complexity of their algorithms scales with various terms (GC, Hxy, Hyy, etc) showing benefits on some.\n \n \nWeaknesses:\n \nThe experiments presented in the paper are limited, and difficult to assess even after looking through the appendix.  What do the low-alpha parts of Figure 1 represent?  Why is CG used for the inverse with BA?  The algorithm you investigate (a Neumann Hessian inverse) was shown to work better in these kinds of problems by [1], [2], [3].\n\nAlgorithm 3 is not useful for practitioners to implement.  It seems like it does not use hessian-vector products, so I doubt the current incarnation would scale to any reasonably sized problem. See [1] or [2] for papers that provide memory-efficient Hessian Inverse estimators with the Neumann series and Hessian-vector products. Does Table 2 rely on storing the full Hessians in memory?  If so, this is infeasible in most applications and the complexity comparisons are not useful.\n \n[1] Lorraine, Jonathan, Paul Vicol, and David Duvenaud. \"Optimizing millions of hyperparameters by implicit differentiation.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2020.\n[2] Liao, Renjie, et al. \"Reviving and improving recurrent back-propagation.\" arXiv preprint arXiv:1803.06396 (2018).\n[3] Shaban, Amirreza, et al. \"Truncated back-propagation for bilevel optimization.\" The 22nd International Conference on Artificial Intelligence and Statistics. 2019.\n \n \nMy recommendation is to reject this work with a 4. The paper presents convergence proofs for variants of two common algorithms in bi-level optimization. If a version of algorithm 3 that uses Hessian-vector products is presented with similar convergence results I would change my score to a 6.  I would also increase the score if (quite a bit) stronger experimental results are presented -- the meta-learning results seem mediocre and all hyperparameter results are similar and in the appendix.  I am very familiar with this area, however, I worry I may have misunderstood some notation about the implementation, so I will put my confidence as lower than otherwise until author feedback.\n \n \nThe following points did not affect my score, but may help improve the paper:\n \nThe level of formality in the writing seems different than other submissions to ICLR.  For example, saying “etc.” or “and/or” in the abstract.\n \nI am not familiar with the term “order-level lower” complexity.\n \n“Inlcude” to “include” and “trails” to “trials”\n \nI think “hyperparameter” may be a more common spelling than “hyper-parameter.”\nAlso, “backpropagation” may be more common than “back-propagation”\n\nPassing the paper through a grammar checker might help catch a few other simple grammar typos.", "extra_scores": {}, "extra_text": {}}, {"review_id": "MHccZX65Da", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\nThe paper propose two algorithms for solving bilevel optimization problem where the inner objective is assumed to be strongly convex. The main idea is to use an iterative scheme to approximate the inner level solution, and apply to chain rule to compute the upper level gradient à la back-propagation. Similar techniques is used on a stochastic version in case where the objective function are written as an expectation. The authors also provide a nice complexity analysis (under relatively restrictive but common assumptions) and numerical experiments which confirm an improvement upon some others previous methods eg (Ghadimi and Wang, 2018). The paper is reasonably well written.\n\nI have only one concern on the novelty:\n\n- the paper (Franceschi etal, 2017, 2018) computes hypergradient by backpropagation (the reverse-mode) as well and the actual paper does not clearly describe the relation with these works (while claiming efficiency superiority). More there is no comparisons, neither theoretical nor practical. Note that its iteration complexity was recently provided in ICML (Grazzi etal, 2020). It should be interesting that the authors precisely comment on the differences and add this competitor in the numerical experiments. Specially clarification on the differences (if any) between hypergradient formula would be helpful, as well as the time and space complexity of the proposed algorithms.\n\nI am willing to raise my score after precise clarification of this point.\n\n- Also, it would be interesting to provide an easy to use open source implementation for the conference venue and futur comparisons.\n\nTypos:\n\"and and\" on page 1.\n\"fist\" on page 2.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Hy34h2839EL", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes two novel algorithms, named deterBio and stocBio, for the nonconvex-strongly-convex bilevel optimization problems, and presents a comparison with several existing algorithms to demonstrate their superiority by experiments. Besides, propositions and theorems are well proved in the supplementary materials.\n \n+ The idea of the proposal for reliable bilevel optimizers with better gradient complexities is meaningful.\n+ The paper is well organized attached with sufficient supplementary materials for different propositions, and give analysis about the gradient complexities of proposed algorithms and related methods.\n+ It gives a detailed description of the connection between conventional bilevel optimization and meta-learning problems and applications of respective fields.\n \n\n\nConcerns: \n- Duplicate ‘and’ appears in the last line of the 1st Page.\n- The involved batch size and parameters are significant and sensitive to different problems, and the comparison between stocBio and other algorithms maybe not enough, perhaps more analyses are recommended.\n- Seems that the experiments are not enough to prove the flexible applications in relative deep learning fields, such as reinforcement learning.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose two algorithms and their theoretical analysis for solving bilevel optimization problems where the inner objective is assumed to be strongly convex. The authors have greatly improved the paper to answer reviewer comments and three out of four reviewers have increased their scores. That said, given the large amount of new material added to this paper during the discussion phase, the program committee believes the paper requires a new round of reviews for a confident assessment. We encourage the authors to resubmit their work to a top conference such as ICML.
Decision: Reject