Amortized Implicit Differentiation for Stochastic Bilevel Optimization
Authors: Michael Arbel
Julien Mairal
Venue: ICLR 2022 Poster (2022)
Keywords: bilevel optimization
stochastic optimization

Abstract: We study a class of algorithms for solving bilevel optimization problems in both stochastic and deterministic settings when the inner-level objective is strongly convex. Specifically, we consider  algorithms based on inexact implicit differentiation and we exploit a warm-start strategy to amortize the estimation of the exact gradient. We then introduce a unified theoretical framework inspired by the study of singularly perturbed systems to analyze such amortized algorithms. By using this framework, our analysis shows these algorithms to match the computational complexity of oracle methods that have access to an unbiased estimate of the gradient, thus outperforming many existing results for bilevel optimization.
We illustrate these findings on synthetic experiments and demonstrate the efficiency of these algorithms on hyper-parameter optimization experiments involving several thousands of variables. 

Published as a conference paper at ICLR 2022
AMORTIZED IMPLICIT DIFFERENTIATION FOR STOCHASTIC BILEVEL OPTIMIZATION
Michael Arbel & Julien Mairal Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, IJK, 38000 Grenoble, France.
ABSTRACT
We study a class of algorithms for solving bilevel optimization problems in both stochastic and deterministic settings when the inner-level objective is strongly convex. Specifically, we consider algorithms based on inxxact implicit differenti- ation and we exploit a warm-starl stralegy to amortize the estimation of the exact gradient. We then introduce unified theoretical framework inspired by the study singularly perturbed systems (Habets, 1974) to analyze such amortized algo- rithms. By using this framework, our analysis shows these algorithms to match the computational complexity of oracle methods that have access to an unbiased estimate of the gradient, thus outperforming many existing results for bilevel op- timization. We illustrate these findings on synthetic experiments and demonstrate the efficiency of these algorithms on hyper-parametee optimization experiments involving several thousands of variables.
INTRODUCTION
Bilevel optimization refers to a class of algorithms for solving problems with a hierarchical structure involving two levels: inner and an outer level. The inner-level problem seeks solution y (x)) minimizing a cost g(2, y) over a set y given a fixed outer variable & in a set X. The outer-level problem minimizes objective of the form ((x)= y (z:) over X' for some upper-level cost f.
When the solution (x(x) is unique, the bilevel optimization problem takes the following form:
min [(x) == (x, y² (x)), #Ex
such that y²())= = arg min g(r,y) y) yEy
(1)
First introduced the field of economic game theory by Stackelberg (1934) and long studied in optimization (Ye and Zhu, 1995; Ye and Ye, 1997; Ye et al., 1997), this problem has recently received increasing attention in the machine learning community (Domke, 2012; Gould et al., 2016; Liao et al., 2018; Blondel et al., 2021; Liu et al., 2021; Shaban et al., 2019; Ablin et al., 2020). Indeed, many machine learning applications can be reduced to (1) including hyper-parameter optimization (Feurer and Hutter, 2019), meta-learning (Bertinetto et al., 2018), reinforcement learning (Hong et al., 2020b; Liu et al., 2021) or dictionary learning (Mairal et al., 2011; Lecouat et al., 2020a;b).
The hierarchical nature of (1) introduces additional challenges compared to standard optimization problems, such as finding a suitable trade-off between the computational budget for approximating the inner and outer level problems (Ghadimi and Wang, 2018; Dempe and Zemkoho, 2020). These considerations are exacerbated in machine learning applications, where the costs f and often come as an average of functions over a large or infinite number of data points (Franceschi et al., 2018). All these challenges highlight the need for methods that are able to control the computational costs inherent to (1) while dealing with the large-scale setting encountered in machine learning.
Gradient-based bilevel optimization methods appear to be viable approaches for solving (1) in large- scale settings (Lorraine et al., 2020). They can be divided into two categories: Iterative differenti- ation (TTD)) and Approximate implicit differentiation (AID). ITD approaches approximate the map y" (x) by a differentiable optimization algorithm A(x) viewed as function of x. The resulting surrogate loss -(x) = f(x A(x)) is optimized instead of L(x) using eoverse-mode automatic dif- ferentiation (see Baydin al., 2018). AID approaches (Pedregosa, 2016) rely an expression of the gradient VL resulting from the implicit function theorem (Lang, 2012, Theorem 5.9). Un- like ITD, AID avoids differentiating the algorithm approximating y* (x) and, instead, approximately

---

Published as a conference paper at ICLR 2022
solves a linear system using only Hessian and Jacobian-vector products to estimate the gradient VL (Rajeswaran et al., 2019). These methods can also rely on stochastic approximation to increase scalability (Franceschi et al., 2018; Grazzi et al., 2020; 2021).
In the context of lecrhing Ghadimi and Wang (2018) provided one of the first compre- hensive studies of the computational complexity for class of bilevel algorithms based on AID approaches. Subsequently, Hong et al. (2020b); Ji et al. (2021); Ji and Liang (2021); Yang et al. (2021) proposed different algorithms for solving (1) and obtained improved overall complexity by achieving a better trade-off between the cost of the inner and outer level problems. Still, the ques- tion of whether these complexities can be improved by better exploiting the structure of (1) through heuristics such as warm-start remains open (Grazzi et al., 2020). Moreover, these studies pro- posed separate analysis of their algorithms depending on the convexity of the loss L and whether a stochastic or deterministic setting is considered. This points out to a lack of unified and systematic theoretical framework for analyzing bilevel problems, which is what the present work addresses.
We consider the Amortized Implicit Gradient Optimization (AmIGO) algorithm, bilevel opti- mization algorithm based on Approximate Implicit Differentiation (AID) approaches that exploits a warm-start strategy when estimating the gradient of L. We then propose unified theoretical frame- work for analyzing the convergence of AmIGO when the inner-level problem is strongly convex in both stochastic and deterministic settings. The proposed framework is inspired from the early work of Habets (1974) on singularly perturbed systems and analyzes the effect of warm start by viewing the iterates of AmIGO algorithm as dynamical system. The evolution of such system is described by a total energy function which allows to recover the convergence rates of unbiased oracle methods which have access an unbiased estimate of VL (c.f. Table 1). To the best of our knowledge, this is the first time a bilevel optimization algorithm based on a warm-start strategy provably recovers the rates of unbiased oracle methods across a wide range of settings including the stochastic ones.
2 RELATED WORK
Singularly perturbed systems (SPS) are continuous-time deterministic dynamical systems of cou- pled variables (z(t), v()) with two time-scales where y(t) evolves much faster than z(t). As such, they exhibit a hierarchical structure similar to (I). The early work of Habets (1974); Saberi and Khalil (1984) provided convergence rates for SPS towards equilibria by studying the evolution of single scalar energy function summarizing these systems. The present work takes inspiration from these works to analyze the convergence of AmIGO which involves three time-scales.
Two time-scale Stochastic Approximation (TTSA) can be viewed as a discrete-time stochastic ver- sion of SPS. (Kaledin al., 2020) showed that TTSA achieves finite-time complexity of O(-1) for linear systems while Doan (2020) obtained a complexity of (<-3/) for general non-linear systems by extending the analysis for SPS. Hong et al. (2020b) further adapted the non-linear T for solving (I). In the present work, we obtain faster rates by taking into account the dynamics of a third variable 23 appearing in AmIGO, thus resulting in three time-scale dynamics.
Warm-start in bilevel optimization. et al. (2021); Ji and Liang (2021) used a warm-start for the inner-level algorithm obtain an improved computational complexity over algorithms without warm-start. In the deterministic non-convex setting, Ji et al. (2021) used a warm-start strategy when solving the linear system appearing in AID approaches to obtain improved convergence rates. How- ever, it remained open whether using a warm-start when solving both inner-level problem and linear system arising in AID approaches can yield faster algorithms in the more challenging stochastic setting (Grazzi et al., 2020). In the present work, we provide a positive answer to this question.
AMORTIZED IMPLICIT GRADIENT OPTIMIZATION
3.1 GENERAL SETTING AND MAIN ASSUMPTIONS
Notations. In all what follows, X' and y are Euclidean spaces. For differentiable function h( v) X x y + R. we denote by Vh its gradient w.r.t. (a, y), by O.h and 0,h its partial derivatives w.n.t
and y and by Ozyh and i h h the partial derivatives of a,h w.r.t x and y, respectively.
2

---

Published as a conference paper at ICLR 2022
Geometries
Setting
Algorithms
Complexity
BA (Ghadimi and Wang. 2018)
( V k2 log 1
(D)
AccBio (Ji and Liang, 2021)
O 1/2 1/2
Rig
log 1
AmIGO (Corollary 1)
O loge
(SC)
BSA (Ghadimi and Wang. 2018)
O 9 O 3 log
(S)
TTSA (Hong et al., 2020b)
O O + ne 3/2 loge
AmIGO (Corollary 2)
BA (Ghadimi and Wang. 2018)
O 6/14)
AID-BiO (Ji et al., 2021)
O
AmIGO (Corollary 3)
O
BSA (Ghadimi and Wang. 2018)
O + kge
(NC)
TTSA (Hong et al., 2020b)
0mm 5/2 log e
S
stocBiO (Ji et al., 2021)
O *t 'loge
MRBO/VRBO* (Yang et al., 2021)
Oppoly(n, (xgly((z))e ) 3/2 log c )
AmIGO (Corollary 4)
O
Table 1: Cost of finding an e-accurate solution as measured by E[C(xx)-<*)))
"E ||0b- x= I?]
when L is y-strongly-convex (SC) and Σ E [V(()))] when L is non-convex (NC). The settings (D) and (S) stand for the deterministic and stochastic settings. The cost corresponds to the total number of gradients, Jacobian and Hessian-vecte vector products used by the algorithm. Kg and Ky are the conditioning numbers of and g whenever applicable. The dependence on Kr. and Kg for TTSA and AccBio are derived in Proposition 11 of Appendix A.4. The rate of MRBO/VRBO is obtained under the additional mean mean-squared smoothness assumption (Arjevani et al., 2019).
To ensure that (1) is well-defined, we consider the setting where the inner-level problem is strongly convex so that the solution y² (I) is unique as stated by the following assumption:
Assumption 1. For any x E X. the function + g(2, y) is Lm-soothh and Hy- stronnyy convex.
Assumption 1 holds in the context of hyper- syper-parameter selection when the inner-level kernel regression problem (Franceschi et al., 2018), or when the variable represents the last linear layer of a neural network as in many meta-learning tasks (Ji et al., 2021). Under Assumption and additional smoothness assumptions on f and g, the next proposition shows that L is differentiable:
Let be a twice differentiable function satisfying Assumption 1. Assume that f is differentiable and consider the quadratic problem:
Proposition 1.
1 T (0wal(z u))z + 2 T00f( v). 22
min Q(2,v,2) EER
(2)
Then, (2) admits a unique minimizer 2" (xx y) for any (I. y) in X x V. Moreover, y (x) is unique and well-defieed for any x X and C is differentiable with gradient given by:
Vl(x) Oz 0z (x, (x)) + -2yg(x,,' (x.))²(x,)))))))
Proposition 1 follows by application of the implicit function theorem (Lang, 2012, Theorem 5.9) and provides an expression for VL solely terms of partial derivatives of f and g evaluated at (I,, y² (z:). Following Ghadimi and Wang (2018), we further make two smoothness assumptions on f and g:
Assumption 2. There exist positive constants Ly and B such that for all x, x' X and y, v.v/ e yy:
VV v) ff(a', v s (,)1(z,)) ('l. [1,f(zz $ B.
Assumption 3. There exit positive constants L. Mg such that for any x E X and v. e y: max {100,g((1, v) 0xng(2' g')ll. [1ll:110ype. (10))((x))) 3) 0gug(z', s/1l S Moll(, (/)))))
(10,9(r,)) v) 0n w)ll S f/y1 =e'll
3

---

Published as a conference paper at ICLR 2022
Assumptions I to 3 allow control of the variations of y" and 2" and ensure L is L-smooth for some positive constant L as shown in Proposition 6 of Appendix B.2. As an L-smooth function, is necessarily weakly convex (Davis et al., 2018), meaning that C satisfies the inequality ((z) S VL(x) (z y) - 5 I vll for some fixed μ E with lu| S L. particular, & is convex when 2 0. strongly convex when > O and generally non-convex when < O. We thus consider two cases for L. the strongly convex case (μ > 0) and the non-convex case (μ < 0). When L is convex, we denote by L* its minimum value achieved at a point x² and define <g= <c=L/μ when μ >> 0.
Stochastic/determiiitti settings. We consider the general setting where f( y) and g v) are expressed as an expectation of stochastic functions f(r y. E) and ((r, over a noise variable Ç- We recover the deterministic setting as a particular case when the variable has zero variance, thus allowing us to treat both stochastic (S) and deterministic (D) settings in a unified framework. As often in machine-learning. we assume we can always draw a new batch DD of i.i.d. samples of the noise variable & with size [D] 2 and use it to compute stochastic approximations of f and defined by abuse of notation as f1, y, D)= := কe CEED (I. y, E) and ğ(z, y, D) কoj EşED 9(xr, y, E) We make the following noise assumptions which are implied by those in Ghadimi and Wang (2:18):
Assumption 4. For any batch D, ff(a, y, DD) and 0g y. D) are unbiased estimator of V f v) and (z, y) with uniformly bounded variance, ie. for all x, E X y:
E fa D. - VS(a, vi
B [10000(E y, D) - 0yg(2, w)1l S D
Assumption 5. For any batch D. the matrices (,, D) == dzyğ(a, y, D) dnyg (z, y) and
F2( D)= == =0ggå(a, y, D) 0ggg(z, . y) have zero mean and satisfy for all y E X x y:
(x, Fi Fz y. D)] ll op S 02 IDI || v. D) Fz y. D) op S 02 xxx
|
For conciseness, we will use the notations
o3:= - 0 -
D
and
a2 =2
9,0 Ous [DI-1, without explicit reference to the batch D. Next, we describe the algorithm.
3.2 ALGORITIIMS
Amortized Implicit Gradient Optimization (AmIGO) is an iterative algorithm for solving (1). constructs iterates Fe. Vı and 2g such that Ty approaches stationary point of L while yh and 2n track the quantities y (*(x)) and =* (Ix, ys). AmiGO computes the iterate xx+1 using an update equation fx+1 Ia 2% for some given step-size "Ik and stochastic estimate thx of (((x)) based on (3) and defined according to (4) below for some new batches of samples D, and D Dany.
SR = 0xf(zks yk. Uk. Df) + 0 yke D yzy )T Zk.
(4)
AmIGO computes sha steps given iterates TR. yk-1 and Zk-1- A first step computes an approximation yh to (*x) using a stochastic algorithm Ay, initialized at yk-1. A second step computes unbiased estimates un a. (., yk: D5) and uk 0 yk, Dy) of the partial derivatives of f w.r.t. x and y. A third step computes an approximation 24 to 2 (Ix: yk)) using second stochas- tic algorithm B& for solving (2) initialized at zg-1- To increase efficiency, algorithm B₁ uses the pre-computed vector UY for approximating the partial derivative 0 in (2). Finally, the stochastic estimate Dhx is computed us- ing (4) by summing the pre-computed vector un with the incobian-vector product wvk Ouy9 (Ik: yks D Da zk. AmiGO is summarized in Algorithm 1.
Algorithm AmIGO
1: Inputs: zo. y-1, 2-1-
2: Parameters: 7k, K.
3: for h E (0,..., K} do
4: y/k 6 An Hk-1)
5: Sample batches Dj, Dgy
6:
(uR, vx)+ + Vf(IKK Mk Dj).
7:
2k + B& (I Uk: Uk. 2k-1)
8:
wk t Ozgg (#ks yk Dany) ) 2
9:
T to us
10: Ek s 1K-1 n
11: end for
12:
Return TK-
Algorithms Ar and B.. While various choices for As and Bg are possible, such as adaptive algo- rithms (Kingma and Ba, 2015), accelerated stochastic algorithms (Ghadimi and Lan, 2012),
4

---

Published as a conference paper at ICLR 2022
focus simple stochastic gradient descent algorithms with pre-defined number of iterations T and N. These algorithms compute intermediate iterates y' and x" optimizing the functions y + g 8/ and + (Tx yk: 2) starting from some initial values y and 20 and returning the last iterates y² and NN as described Algorithms 2 and 3. Algorithm AІ updates the current iterate y' using stochastic gradient 0,0(#k, y D2) for some new batch of samples Dy and fixed step-size оg-- Algorithm B₁ updates the current iterate 2'- using stochastic estimate of (zQ( yk. 2f-1) with siep 3x. The stochastic gradient is computed by evaluating the Hessian vector product ( Vk. D, Dauy )z"=1 for some new batch of samples D ayy and summing with vector vg ap- proximating (zk,, provided as input to algorithm Bk-
Warm-start for yd and 2 Following the intuition that (xx) remains close to y (xx=1) when Th = 15 and assuming that y is accurate approximation to (fx=11), it is natural to initial- ize A& with the iterate yk-1. The same intuition applies when initializing B₃ with 2ş-1- Next, we introduce framework for analyzing the effect of warm-start on the convergence speed of AmlGO.
Algorithm Axxxx, (2.
Algorithm 3 (x, y, 0,20)
1: Parameters: 0gk.
1: Parameters: BR. N.
2: for E (1...., do
2: for n. E {1,.... N) do
3: Sample batch Dú
3: Sample batch Do
4: 2 1n BR Opyg 1. )arx)= (at))
= + w).
4: y' +++ ----- 0n 2, ",,""1,, Dix))
5: end for
5: end for
6: Return y²
Return N.
ANALYSIS OF AMORTIZED IMPLICIT GRADIENT OPTIMIZATION
4.1 GENERAL APPROACH AND MAIN RESULT
The proposed approach consists in three main steps: (1) Analysis of the outer-level problem (2)
Analysis of the inner-level problem and (3) Analysis of the joint dynamics of both levels.
Outer-level problem. We consider quantity Eg describing the evolution of d4 defined as follows:
62 IF x² 113 + (1 1a0k
-1 u){(((r)) L*), /
Ef
27
(5)
6
<< 0.
where 1) is set to in the stochastic setting and in the deterministic and de is positive sequence that determines the convergence rate of the outer-level problem and is defined by:
òz := 7k.
M++1 = TT(11 + 74+1(1T - +)) + L1,
with fo such that 7o - 2n if p>0 and n if μ<0 and where choose the step-size Tik to be non-increasing sequence with To < +. With this choice for 6a and by setting covers the quantity considered the stochastic estimate sequences framework of Kulunchakov and Mairal (2020) to analyze the convergence of stochastic optimization algorithms when L is convex. When non-convex, E recovers a standard measure of stationarity (Davis and Drusvyatskiy, 2018). In Section 4.3, we control E using bias and variance error EY_ and V. of si given by (6) below where E2 denotes expectation conditioned on (IK, Dk. 21-1).
in (5), Eg re-
_
VC(xW)
V E pi ER
(6)
Inner-level problems. We consider the mean-squared errors Eg and EE between initializations -1- and =0=z--) and stationary values (y* (xx) and (IrK. v1.) algorithms As and By:
E E B y (=. = := || (* v+)1
In Section 4.3, we show that the warm-start strategy allows to control Ey and E in terms of previous iterates EV_1 and Ei_, as well the bias and variance errors in (6). We further prove that such bias and variance errors are, in turn, controlled by Fy and F.g.
5

---

Published as a conference paper at ICLR 2022
Joint dynamics. Following Habets (1974), we consider aggregate error Ex defined linear combination of Ei. EX and Ex with carefully selected coefficients Og and by=
= Dx + a by
(7)
As such ox represents the dynamics of the whole system. The following theorem provides an error bound for Ex in both convex and non-convex settings for a suitable choice of the coefficients dk and by provided that T and N are large enough:
Theorem 1. Choose a batch-size [Daan 2IV Lin and the step-sizes ay=Lig², (2 - Potty
7 Ix--- Set the coefficients ag and by be ag:=6[(1-appu) 1/2 and by:= (1 1 kk(gg) 1/2 and set the number of iterations T and N of Algorithms 2 and 3 be of order T - ( (Kig) and
N up to a logarithmic dependence on Kig. Let 2g 1 5001-5))222 - (
)x) x0 with
=o=ro. Then, under Assumptions
Ext0 satisfies:
6-) + Extt S (1 (1-(26c) 1 [Fattt + +E(((x)) [+]
2W2
B[((())
L
1
< (B[[(zo) - -1 + 2W k
E
< O,
k 1=1
where W defined in (20) of Appendix A.2, is the effective variance of the problem with W²=0 in the deterministic setting and, in the stochastic setting, W200 is of the following order:
W2 -0 (o kg Dal -2 + D Aow 1'02 Buy Suy
+ Kig Dazx
12 9xu + +
We describe the strategy of the proof in Section 4.3 and provide proof outline in Appendix A. with exact expressions for all variables including the expressions of T, N and W The full proof provided in Appendix A.2. The choice of ag and by ensures that E and E contribute less to Ex the algorithms Ar and B3 become more accurate. The effective variance W2 accounts for interactions between both levels in the presence of noise and becomes proportional to the outer-level variance of when the inner-level problem is solved exactly. In the deterministic setting, all variances vanish so that =2=0, Hence, we characterize such setting by W²=0 and the
57. og. gay and ō2 Suy stochastic one by W Next, we apply Theorem 1 to obtain the complexity of AmIGO.
4.2 COMPLEXITY ANALYSIS
We define the complexity C(c) of a bilevel algorithm to be the total number of queries to the gradients of f and g. Jacobian/hessian-vetto products needed by the algorithm to achieve error according to some pre-defined criterion. Let the number of iterations k. T and N and sizes of the batches [Dgl.
[Dyl. Pa..! and (Dauv , be such that AmIGO achieves a precision c. Then C(c) is given by:
C(E) k(T)P,) + N|P | + (Dyl).
(8)
We provide the complexity of AmIGO in the 4 settings of Table 1 in the form of Corrolaries to 4.
Corollary (Case p>0 and =²-0). Use batches of size Achieving ((xx) L* +++5 | requires C(c)=O Keling log E
x=' =1
Corollary 1 outperforms the complexities in Table 1 in terms of the dependence It is pos- sible to improve the dependence on Ky to Ky 1/2 using acceleration in A₁ and B, as discussed in Appendix A.5.1, or using generic acceleration methods such Catalyst (Lin et al., 2018).
Corollary 2 (Case p22=00. Choose (D.l=O(e- k |Da. =0 1222 82
I 63
Dzy
and [ Dowy/ 1 1
( Bou (2 (.Kgg))) rig)) Achieving E[[(8))- -+1 HE ||0 x² x²1]?] Se requires:
C(e) = o
(kk [c ( + +1 (1v Eki auv + 0 + x+ log
Etot + E((((x) - (21 -

---

Published as a conference paper at ICLR 2022
Corollary 2 improves over the results in Table I in the stochastic strongly-come connvex setting and recov- ers the dependence on of stochastic gradient descent for smooth and strongly convex functions up to logarithmic factor.
Corollary (Case p<0 and W2=0). Choose batches of size 1. Achieving Yo E [V S
requires C(c) = O " ((((x)) L*) + E. + EEi)
Corollary 3 recovers the complexity of AID-BiO (Ji al., 2021) in the deterministic non-convex setting. This is expected since AID-BiO also exploits warm-start for both As and Bx.
Corollary (Case f=00 and W>0), Choose (Dg.,
Ne 2000
|P suu -
2 -0("; o (1 viz)
[Dyl= and [Dy 1 <
Achieving error E E
|| [1
requires:
C(e) 0
Ni (1 v en Buv
o² + oî) (B([((r)) - L + Eg + E%)
og y
Corollary 4 recovers the optimal dependence on e of ( achieved by stochastic gradient descent in the smooth non-convex case (Arjevani al., 2019, Theorem 1). It also improves over the results in (Ji et al., 2021) which involve an additional logarithmic factor log(c-1) as N is required to be Okg, log(E 2)). In our case, N remains constant since By benefits from warm-start. The faster rates of MRBO/VRBO" (Yang al., 2021) are obtained under the additional mean-squared smoothness assumption (Arjevani et al., 2019), which we do not investigate in the present work. Such assump- tion allows to achieve the improved complexity of O -3/2 log(<-1))- However, these algorithms still require N=O(log((-t), indicating that the use of warm-start in B₁ could further reduce the complexity to O(E-3/2) which would be an interesting direction for future work.
4.3 OUTLINE OF THE PROOF
The proof of Theorem proceeds by deriving a recursion for both outer-level error Eg and inner- level errors EY and E and then combining those to obtain error bound the total error E
Outer-level recursion. To allow a unified analysis of the behavior of E in both convex and non- convex settings, define F& as follows:
FA u -"]1o + (E[[(xx) - [(xx E Eg) L
The following proposition, with proof in Appendix C.I, provides recursive inequality E involving the errors in (6) due to the inexact gradient eix: Proposition 2. Let be non-increasing sequence with <<<b<<2 Assumptions I to 3 ensure that: (10)
Fs E 5( (1 11---
2- pk 0x) TAS V + Th (s + Px -) E
with 8% defined as 8% f02= + (5 (1 u)) 1,,20
In the ideal case where yı = (2r)) and 21: = 2* (drk: Me. the bias F. vanishes and (10) simplifies to (Kulunchakov and Mairal, 2019, Proposition 1) which recovers the convergence rates for stochas- tic gradient methods the convex case. However, y/s and 24 are generally inexact solutions and introduce a positive bias EY. Therefore, controlling the inner-level iterates is required to control the bias b% which, in turn, impacts the convergence of the outer-level as we discuss next.
Controlling the inner-level iterates y/s and Zg. Proposition 3 below controls the expected mean squared errors between iterates yı and z and their limiting values (*x) and 2" (xK,, Wk):
Proposition Let the step-sizes Osk and Br such that a S and 3 -
Pa
Let
d::((1aa1pp) and II:= 3apa N
Under Assumptions 1, and 5, it holds that:
E [[llue- y (xx))1]] < A R2
E Ell - 2" =xx,, wk)
TT R (11)
where 12 (Ksg))) and R2 Ri m2302 t2g are defined in (14) of Appendix A.2.

---

Published as a conference paper at ICLR 2022
While Proposition 3 is specific to the choice of the algorithms A₁, and B₁ in Algorithms 2 and 3, our analysis directly extends to other algorithms satisfying inequalities similar to (11) such as acceler- ated or variance reduced algorithms discussed in Appendices A.5.1 and A.5.2. Proposition 4 below controls the bias and variance terms V and E% in terms of the warm-start error D and E. Proposition 4. Under Assumptions 1 to 5, the following inequalities hold:
FN S 21 + IT F + R where w ( (0+ + o2- -000 + + and Ly Ok=)( are positive
V S w o FT.
constants defined in (13) and (16) of Appendix A.2 with Ly controlling the variations of [vh)
Proposition 4 highlights the dependence of Pi and Vi the inner-level errors. It suggests analyz- ing the evolution of F% and E to quantify how large the bias and variances can get:
Proposition Let Çk > 2x2 matrix Pk. two vectors Us and Vk in R22 all independent of æ yh and be as defined in Proposition 8 of Appendix A.2. Under Assumptions to 5, it holds that:
E E
A R k-1 II 1 -
S Pk
27t 1 +V +S.EE-1 Vx-
(12)
Proposition 5 describes the evolution of the inner-level errors as the number of iterations k increases. The matrix Ps and vectors Uk and V& arise from discretization errors and depend on the step-sizes and constants of the problem. The second term of (12) represents interactions with the outer-level through 1 k-1 and Ex Propositions 2, and 5 describe the joint dynamics of (E% Ey Eg) from which the evolution of Ex can be deduced as shown in Appendices A.1 and A.2.
5 EXPERIMENTS
We run three sets of experiments described in Sections 5.1 to 5.3. In all cases, we consider AmIGO with either gradient descent (AmIGO-GD) conjugate gradient (AmIGO-CG) for algorithm Bg-- We AmIGO with AID methods without warm-start for B& which we refer to as (AID-GD) and (AID-CG) and with (AID-CG-WS) which warm-start for B& but not for Ag. We also consider other variants using either a fixed-point algorithm (AID-FP) (Grazzi et al., 2020) or Neumann series expansion (AID-N) (Lorraine al., 2020) for By. Finally, we consider two algorithms based on iterative differentiation which we refer to as (ITD) (Grazzi et al., 2020) and (Reverse) (Franceschi al., 2017). For all methods except (AID-CG DDD-CG-WS), we use warm-start in algorithm As. how- ever only AmIGO, AmIGO-CC and AID CD-CG-WE WS exploits warm-start in B₁ the other AID based methods initializing B& with d0 =0. In Sections 5.2 and 5.3, we also compare with BSA algorithm (Ghadimi and Wang, 201 8), TTSA algorithm (Hong et al., 2020a) and stocBi O (Ji et al., 2021), An implementation of AmIGO available in https: /g thub. com/ /Mi chae Arbe GO.
5.1 SYNTHETIC PROBLEM
To study the behavior of AmIGO in controlled setting, consider a synthetic problem where both inner and outer level losses are quadratic functions with thousands of variables as described in details in Appendix F.1. Figure (a) shows the complexity C(e) needed to reach 10-6 relative error amongst the best choice for T and M over a grid as the conditioning number Kg increases. AmIGO-CG achieves the lowest time and is followed by AID-CG thus showing favorable effect of warm-start for B5. The same conclusion holds for AmIGO-GD compared to AID-GD. Note that
AID-CG is still faster than AmIGO-CC for larger values of Kg highlighting the advantage of using algorithms B, with ((FKg) complexity such as (CG) instead non-accelerated ones with Okxr") such as Figure 1(b) shows the relative error after 10s and maintains the same conclusions. For moderate values of Kgg only AmIGO and AID-CG reach error of 10 20 shown in Figure I(c). We refer to Figures 2 and 3 of Appendix F for additional results on the effect of the choice of T and M showing that AmIGO consistently performs well for wide range of values of T and M.
5.2 HYPPERPARRMETTR OPTIMIZATION
We consider a classification task on the 20Newsgroup dataset using a logistic loss and a linear model. Each dimension of the linear model is regularized using different hyper-parameter. The
8

---

Published as a conference paper at ICLR 2022
(al: cte) at e 10 error vs. Kg
(b): Relative error after 10" s vs.
(c): Relative error vs time: Kg 10"
AmiGD-CO
2014
AmiGO-GD
20-1
AID-CG
10-10
10
ND-CG-WS
Relartve
20
AID-FP
AID-GD
13
300
RTD
Timeys
0.0
(d): Validation loss
(c): Validation accuracy
52%
(0: Test accuracy
AmIGO-CG
AmIGO-GD
0.7
Accuracy
Accuracy
AID
20%
AID.GD
68%
70%
ITD
0.3
7.5
TTSA
0.5
10
1.5 Time/s
2.0
25
3,0
2.5
1.0
1.5 Timels
2.2
25
3.0
2.0
1.5 Time/s
2.0
2.5
200
stocBIO
102
162
112
Figure 1: Top row: performance the synthetic task. The relative error is defined ratio between current and initial errors (f(x)) (Z)))))))) - L*). The complexity C(E) as defined in (8). Bottom row: performance on the hyper-parameter optimization task.
collection of those hyper-parametert form a vector x of dimension 1010663 optimized using an un- regularized regression loss over the validation set while the model is learned using the training set. We consider two evaluations settings: A default setting based on Grazzi et al. (2020); Ji et al. (2021) and grid-seach search setting near the default values of Bk. T and N detailed in Appendix F.2.
We also vary the batch-size from 10 10.1, 1, 4) and report the best performing choices for each method. Figure 1(d.e.f) show AmIGO-CG to be the fastest, achieving the lowest error and highest validation and test accuracies. The test accuracy of AmIGO-CG decreases after exceeding 80% indicating a potential overfitting as also observed in Franceschi et al. (2018). Similarly, AmIGO-GD outperformed all other methods that uses an algorithm B5, with ((kg) complexity. Moreover, all remaining methods achieved comparable performance matching those reported in al. (2021), thus indicating that the warm-start in B3 and acceleration in Bg were the determining factors for obtaining an improved performance. Additionally, Figure 4 of Appendix report similar results for each choice of the batch-size indicating robustness to the choice of the batch-size.
5.3 DATASET DISTILLATION
Dataset distillation (Wang et al., 2018) consists in learning synthetic dataset so that a model trained on this dataset achieves small error on the training set. Figure 5 of Appendix F.3 shows the training loss (outer loss), the training and test accuracies of a model trained on MNIST by dataset distillation. Similarly to Figure AmIGO-CG achieves the best performance followed by AID-CG. AmIGO ob- tains the best performance by far among methods without acceleration for B& while all the remaining ones fail to improve. This finding indicative of an ill-conditioned inner-level problem problem as confirmed when computing the conditioning number of the hessian 01y9(x, xr, y) which we found to be of order 7x 10 Indeed, when compared to the synthetic example for Kg =0= as shown in Figure 2, we also observe that only AmIGO-CG, AmIGO and AID-CG could successfully optimize the loss. Hence, these results confirm the importance of warm-stan start for an improved performance.
CONCLUSION
We studied AmiGO, algorithm for bilevel optimization based on amortized implicit differentia- tion and introduced a unified framework for analyzing its convergence. Our analysis showed that AmIGO achieves the same complexity as unbiased oracle methods, thus achieving improved rates compared to methods without warm-start various settings. We then illustrated empirically such improved convergence in both synthetic and a hyper-optimization experiments. A future research direction consists in extending the proposed framework to non-smooth objectives and analyzing acceleration in both inner and outer level problems as well variance reduction techniques.

---

Published as a conference paper at ICLR 2022
7 ACKNOWLEDGMENTS AND FUNDING
This project was supported by the ERC grant number 714381 (SOLARIS project) and by ANR 31A MIAI@ Grenoble MIAllGrenobbl Alpes, (ANR19-P31A-0003).
REFERENCES
Pierre Ablin, Gabriel Peyré, and Thomas Moreau. Super-effiiiency of automatic differentiation for functions defined as minimum. International Conference on Machine Learning, pages 32 22.41. PMLR, 2020.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv: 1912.02365, 2019.
Atilim Gunes Baydin, Barak Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic differentiation in machine learning: survey. Journal of machine learning research, 18, 2018.
Luca Bertinetto, Joao F Henriques, Philip HS Torr, and Andrea Vedaldi. Meta-learning with differ- entiable closed-form solvers. arXiv preprint arXiv:1805.08133 2018.
Mathieu Blondel, Quentin Berthet, Marco Cuturi, Roy Frostig, Stephan Hoyer, Felipe Llinares- López, Fabian Pedregosa, and -hillipp Vert. Efficient and modular implicit differentiation. arXiv preprint 2rXiv:2105./5511 2021.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic subgradient method converges at the rate o(k 1144 on weakly convex functions. arXiv preprint arXiv:1802.02900 2018.
Damek Davis, Dmitriy Drusvyatskiy, Kellie J MacPhee, and Courtney Paquette. Subgradient meth- ods for sharp weakly convex functions. Journal of Optimization Theory and Applications, 179 (3):962-4))) 982, 2018.
Stephan Dempe and Alain Zemkoho. Bilevel Optimization. Springer, 2020.
Thinh T Doan. Nonlinear two-time-scale stochastic approximation: Convergence and finite-time performance. arXiv preprint arXiv:2011.01862 2020.
Justin Domke. Generic methods for optimization-basel modeling. In Artificial Intelligence and Statistics, pages 318-326. PMLR, 2012.
Matthias Feurer and Frank Hutter. Hyperparameter optimization. In Automated machine learning, pages 3-33. Springer, Cham, 2019.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning, pages 1 1165 1173. PMLR, 2017.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta- meta-learning. In International Conference on Machine Learning, pages 1568-1577. PMLR, 2018.
Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly con- vex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal Optimization. 22(4): 2012.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02226. 2018
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On diffcrentiating parameterized argmin and argmax problems with application to bi-level optimization. arXiv preprint arXiv:/607.00 00547,, 2016.
10

---

Published as a conference paper at ICLR 2022
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration com- plexity of hypergradient computation. In International Conference on Machine Learning, pages PMLR, 2020.
Riccardo Grazzi, Massimiliano Pontil, and Saverio Salzo. Convergence properties of stochastic hypergradients. In International Conference on Artificial Intelligence and Statistics, pages 3826- 3834. PMLR, 2021.
P Habets. Stabilite asyptotique pour des problemes de perturbations singulieres. In Stability Prob- lems, pages 2-18. Springer, 1974.
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.055 2077.05/70, 2020a.
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.05170, 2020b.
Kaiyi Ji and Yingbin Liang. Lower bounds and accelerated algorithms for bilevel optimization. arXiv preprint arXiv:2102.0392 2021.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced
design. In International Conference on Machine Learning, pages 4882-4892. PMLR, 2021.
Maxim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, and Hoi-To Wai. Finite time analysis of linear two-timescale stochastic approximation with markovian noise. In Conference on Learning Theory, pages 2144-2203. PMLR, 2020.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Andrei Kulunchakov and Julien Mairal. Estimate sequences for variance-reduced stochastic com- posite optimization. In International Conference on Machine Learning, pages 3541-3550. PMLR, 2019.
Andrei Kulunchakov and Julien Mairal. Estimate sequences for stochastic composite optimization: Variance reduction, acceleration, and robustness to noise. 2020.
Serge Lang. Fundamentals of differential geometry, volume 191. Springer Science Business Media, 2012.
Bruno Lecouat, Jean Ponce, and Julien Mairal. Designing and learning trainable priors with non- cooperative games. arXiv preprint arXiv:2006. /4859, 2020a.
Bruno Lecouat, Jean Ponce, and Julien Mairal. A flexible framework for designing trainable priors with adaptive smoothing and game encoding. In Conference on Neural Information Processing Systems (NeurIPS). 2020b.
Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang, KiJung Yoon, Xaq Pitkow, Raquel Urta- sun, and Richard Zemel. Reviving and improving recurrent back-propagation. In International Conference on Machine Learning, pages 1092-3091. PMLR, 2018
Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. Catalyst acceleration for first-order convex optimization: from theory to practice. Journal of Machine Learning Research, 18(1):7854-7907, 2018.
Risheng Liu, Jiaxin Gao, Jin Zhang, Deyu Meng, and Zhouchen Lin. Investigating bi-level opti- mization for learning and vision from a unified perspective: A survey and beyond. arXiv preprint 101iv:2/01.115// 2021.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International Conference on Artificial Intelligence and Statistics, pages 1550-1552, PMLR, 2020.
11

---

Published as a conference paper at ICLR 2022
Julien Mairal, Francis Bach, and Jean Ponce. Task-driven dictionary learning. IEEE transactions pattem analysis and machine intelligence, 34(4):791-804, 2011.
Yurii Nesterov. Introductory lectures on conver optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. International con- ference machine learning, pages 737-746. PMLR, 2016.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-Learning with Implicit Gradients. H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Mextquotesingle Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32 (NeurIPS). Curran Associates, Inc., 2019.
Ali Saberi and Hassan Khalil. Quadratic-type Yyаpunov functions for singularly perturbed systems. IEEE Transactions on Automatic Control, 2946):54.-550 1984.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Muthematical Programming, 162(1-2):83-11) 2017.
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back-propagatto for bilevel optimization, The 22nd International Conference on Artificial Intelligence and Statistics, pages 1723-1732. PMLR, 2019.
Jonathan Richard Shewchuk et al. An introduction the conjugate gradient method without the agonizing pain, 1994.
H.F. Von Stackelberg. MurkfoomundCiiichgewwwchh Springer, 1934.
Tongzhou Wang, Jun Yan Zhu, Antonio Torralba, and Alexei A Efros. Dataset distillation. arXiv preprint 0rXiv:1811.10953. 2018.
Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. arXiv preprint arXiv:2106.04400 2021.
Ye and XY Ye. Necessary optimality conditions for optimization problems with variational in- equality constraints. Mathematics of Operations Research, 22(4):977-997, 1997.
JJ Ye and DL Zhu. Optimality conditions for bilevel programming problems. Optimization, 33(1): 9-27, 1995.
JJ Ye, DL Zhu, and Qiji Jim Zhu. Exact penalization and necessary optimality conditions for gener- alized bilevel programming problems. SIAM Journal optimization, 7(2):481-507) 1997.
12

---

Published as a conference paper at ICLR 2022
A CONVERGENCE OF AMIGO ALGORITHM
In this section, we provide proof of Theorem as well as its corollaries Corrolaries 1 to 4. In Appendix A.I, we provide an outline of the proof Theorem that states the main intermediary results needed for the proof and provide explicit expressions for the quantities needed throughout the rest the paper. Appendices A.2 and A.3 provide the proofs of Theorem and Corrolaries to 4. The proofs of the intermediary results are deferred to Appendices B and C.
A.1 PROOF OUTLINE OF THEOREM
The proof of Theorem proceeds in 8 steps as discussed bellow.
Step 1: Smoothness properties. This step consists in characterizing the smoothness of V L. y²,
as well as the conditional expectation E[bbx] [. yk 2*] knowing Tke yk and žj.- For this purpose, we consider the function V/ X x y y X' defined as follows:
V cr y, 2) (xr( 0,.
Hence, by definition of e'k it is easy to that E[ (Tk V/s zu] v (z yk zk). The following proposition controls the smoothness of V L. y², 2² and v and is adapted from (Ghadimi and Wang, 2018, Lemma 2.2). We provide proof in Appendix B.2 for completeness.
Proposition 6. Under Assumptions 1 to 3, L. V, Vn and 2" satisfy:
[1= v) - (z',, S L. | 2'1l+ lly - v/1) [[V(()) V (((')l & T.I - a'll. [V,,,,) VL(x)]I < L v'(x) + +|== (<<,,,)))
x'11, [x) (z')l) Ly|| 1
(I," (x)) S u '
where Ly. Los Ly and L are given by:
by = U9 g'
L = u1 2 Mg + Lo
(13)
L = max ((L Mop B L' Lz) L'gg)
L := (L, 1 2 M B + 11g 1 (Tig + M, B)) (1 p. T.)
The expressions of Ly. L,, Lg and L suggests the following dependence on the conditioning Ky of the inner-level problem which will be useful for the complexity analysis: Ly = O11g), Ly On2)). T,2 = (12)) and T. (x2))
Step 2: Convergence of the lnver-level iterates. In this step, we control the mean squared er- rors ||u y [mx) and TE || - 2 (* [w)ll] as stated Proposition 3. In fact we prove a slightly stronger version stated below:
Proposition 7. Les O and Br be two positive sequences with a.St and
3 2L, min (1. 1,t1,, " ogyy
2Lg
and define Am:=(1-asHg) and
BEMe 2
De-
note by žn the conditional expectation of 2 knowing Ik. yt and zh Let Ry and Ry be defined as:
R2 20 oy
R = BBB² -3 oz + +3 0z
(14)
Then, under Assumptions 1. 4 and 5 the iterates 2n and žn satisfy:
T 11ye - y (xx))1²) Ag R2
|| x" (xxs )1? < 11.E 11=2 z" (x yzx 11 + Rig
|| - x (Ix. w/x) 12]
- I
12 - 2 (xx 3311
zz
žz 12]
< 40324
||
== (xx, (0 )13 2RG.
(15a)
13

---

Published as a conference paper at ICLR 2022
is easy to see from the above expressions that R% = (kig0)) while R = ( + x2
stated in Proposition 3. Controlling Billyx - y² (xx))]1 follows by standard results on SGD (Kulunchakov and Mairal, 2020, Corollary 31) since the iterates of Algorithm uses i.i.d. samples. The error terms E
|| 2" (2k, 3x]ll more delicate since Algorithm 3 uses the same sample
(z 31.) for updating the iterates, therefore introducing additional correlations between these iterates. We defer the proof of Proposition 7 to Appendix B.3 which relies on general result for stochastic linear systems with correlated noise provided in Appendix E.
Step 3: Controlling the bias and variance errors V and E is achieved by Proposition 4. The bias Ex is controlled simply by using the smoothness of the potential near the point (IN, y² (Ix), =* (xx, . y² (xx)) as shown in Proposition 6. The variance term V is more deli- cate to control due to the multiplicative noise resulting from the Jacobian-vector product between O yk. D Bay )zk. ) We defer the proof to Appendix B.4 and provide below explicit expressions for the constants of and w²:
= (1+2Eghh 2 + +6(02,,
14g (
+ +L2))
(16a)
+2 03.. + (T'g)
B² Mg 3030 0z 2B² P1 3 20 gg
02 20 gay + + )2 pg
20? "gg.'
Note that -0 2
03
1 9vs oz gay
and -
0 (02 + gvy as stated in Proposition 4.
Step 4: Outer-level error bound. This step consists in obtaining the inequality in Proposition which extends the result of (Kulunchakov and Mairal, 2020, Proposition to biased gradients and to the non-convex case. We defer the proof of such result to Appendix C.I.
Step 5: Inner-level error bound. This step consists in proving Proposition 5. For clarity, we provide a second statement with explicit expressions for the quantities of interest:
Proposition 8. Let rk and On be two positive non-increasing sequences no greater than 1. For any 0 S v S 1, denote by db and Rs the following non-negative scalars:
du = (1 - -1)-v 3) a 20,
io : 2(1 Lggl 'T2 0T0000 + +RR
Çx : 2L (min ((1 u) L 1,200 Iwco)
Finally, consider the following matrices and vectors:
2T Th
Pk =
1 11+Tk Tk, 20 0p.
1 0z)
0
Uk:=
4T.2% Th Up
(1 41
Vs Ry (8120=1)
(17)
Then, under Assumptions 1 5, the following holds:
E
Pk
11 E 12 27M [b
1 ++++1 +1%-11
V2 1 + Vk.
E
We defer the proof of the above result to Appendix C.2.
Step 6: General error bound. By combining the inequalities in Propositions 2 and resulting from the analysis of both outer and inner levels, obtain general error bound on Exat in Proposition with a proof in Appendix C.4.
Proposition 9. Choose the step-sizes as and 3g such that they are non non-increasing in k and choose Tk and O2 such that E and 6,0=² are non-increasing sequences. Choose the coefficients a and by defining Etot in (7) to be of the form as durī Aं and by 0 11g for some 0 1. and fix a non-increasing sequence 0- < < 1. Then, under Assumptions I to 5 Elot satisfies:
FP + Etst < | Egot Vtot
14

---

Published as a conference paper at ICLR 2022
where Vi and As are given by:
1 1- (1- + 2G
4 L 1 1 16L 0z 2 (2u + 3 + Pk
A
(18)
I -9 [ 0% ( nh6
[2L3 + +o? (2 + + Pk: 1))
Viot =8 (AE(1 + +rk 161 0z "II; 2 Mi (2uk + + Pk R
+ 6% (1 + 0 IT - + 0 TT RM: + 7/h (sk + u
where we introduced u/ = = + U for conciseness with U( and U being the compo- nents of the vector Uk defined in Proposition
Proposition 9 holds without conditions the error made by Algorithms 2 and 3. The general form of aş and by allows to account for potentially decreasing step-sizes "/k, Og and 8g However, in the present work, will restrict to the constant step-size for ease of presentation
discuss next.
Step 7: Controlling the precision of the inner-level algorithms. In this step, we provide condi- tions on 7 and N in Proposition 10 bellow so that || 1 pk (6, in the constant step-size case. These conditions are expressed in terms of the following constants:
G ==1 + log (6 24433%
(19a)
C2 :2 log (1 +L max (m,, 8Co))
(19b)
C3 max 0, 02.22log (5L No 1)=)) -2 log L
(19c)
412
C = + 2 2og
(4 + 12 (21 + o..)
(19d)
C2 2 log
(1 122224, 2 2 16
(19c)
I
-2oog (7(02.) + (1z)²)
C max 0,-2 4T.2
(19f)
Proposition 10. Let Assumptions 1 to 5 hold. Choose Pk 2. the step-sizes to be constant:
O==aS L, :x=B$ 2L, and 7k= = 1 and choose the batch-size (Pavvl O PoLs
1
Puyy
Moreover,
1/2 rk 02 = 1. Finally, choose T and N follows:
T= La 11 max (C1, C2. Ca)l +1, N = 128- (max (C1, C22 C3) max (C1, Oz Cb)) +
with C1, C2, C2, C₁ C22y and C22 defined in (19a) to (19f). Then, || I (1 - pb)6, and
ttot S Sd, with W2 given by:
1
60L 8014 Lg oz
W2
50
u + w
(20)
We provide a proof of Proposition 10 in Appendix D. is easy to see from Proposition that that T=O(kg) and N=0(kg) when a a= プ,, and B= 2L, 1, where the big-O notation hides a logarithmic dependence in Kg coming from the constants {Ci, Cf E (1),,3)}
Step 8: Proving the main inequalities. The final step combines Propositions and 10 to get the desired inequality. We provide full proof in Appendix A.2 assuming Propositions 9 and 10 hold.
A.2 PROOF OF THEOREM 1
In order to prove Theorem 1 in the convex case, we need the following averaging strategy lemma, a generalization of (Kulunchakov and Mairal, 2020, Lemma 30):
15

---

Published as a conference paper at ICLR 2022
Lemma 1. Let C be convex X. Let I&k be (potentially stochastic) sequence of iterates in X. Let (Ex)x20- (V&) and (ōx) be non-negative sequences such that òR E (0.1). Fix some non-negative number [0. 1] and define the following averaged iterates &g recursively by t =
(1 6g yu) and starting from from any initial point Ct. Assume the iterates
(IK) satisfy the following relation for all k 2 1:
(1 - u ((11)))))(((( --'
Eu S - (xx (1 + Vk. (21)
Ler := -- 8k). Then the averaged iterates (fx) satisfy the following:
E[C(+x) - [*] Ex < ((((x)) L + u (C(0t) [*)) +Tx Σ VT
IStSk
Proof. For simplicity, write Fs B[((x)) L*j and Fs. E(f((n) L*). We first multiply (21) by T and sum the resulting inequalities for all K get:
Σ r1 u(1 +I= S
Σ r (1:)(1T))TT + (1 u) Fk-1) +
V Vx.
Grouping the terms in F3 together and recalling that 1 ' (1-1 6x) = - yields:
(4)
K P PE
K
Σ
( FR) Th- TT)
k Vv.
Simplifying the telescoping sums and multiplying by Tk, we get:
K
K + + Fo +o
Fx + aT K
-
rra Vi
(22)
1=1
k=1
Consider now the quantity Fr. Recalling that is convex and by definition of the iterates dg we apply Jensen's inequality to write:
P < u(1 5x.) PR (1 u(1 5x))
By iteratively applying the above inequality, we get that:
k
Fx S Fo +
+TK
u
k
kT
k
(1
u(( 5k))
k
k=1
K
K
FIkI + l'
u
K-
- FB
Σ
u K- Ik-IFF
k=1
k=1
K-1
= Fx + P
Σ
K Fk41)
We can therefore apply (22) the above inequality get the desired result.
We now proceed to prove Theorem 1.
Proof of Theurem I. By application of Proposition 9 and using the choice of and given by Proposition 10, the following inequality holds:
FR + Eoot < (1 -1-(1 (1 - px) + ?
(23)
with W defined in Proposition 10. We then distinguish two cases depending the sign of μz:
Case 2 0. Recall that F2 and ET are given by:
8k
F; (((R](((x)) - --',
E
||
x01
u)E((((*)) L*]
27k
16

---

Published as a conference paper at ICLR 2022
Since J > 0, L is convex function and apply Lemma with VA= V==ydoW and
Ex= 2% 10 - xx1 x=11² Eo The result follows by noting that I' > L' S 60"
Case μ < 0. In this case, recall that Fg and Eg are given by:
Fk B[((x)) [(xx-1)] E E
= [V
We then sum (23) for all iterations 0 S t k which, by telescoping, yields:
B[((xx) [(xo)]] + Fig Fx F Eooe
Σ (1- S kydo
1SISk
Using that [F(((()) - L1]+ + F F is non-negative since Ex - Fij = a& Fit + by Exg, we get:
Σ (1 - pr) ETT < (BI[(()) 6* a + by Ez) + 67
15T5K
Finally, since Pr 2. 6, = Ly, the result follows after dividing both sides by j LkLy
A.3 PROOF OF CORROLARIES 1 TO 4
Proof of Corollary Choosing u implies that Fg = - x=11² + L(xx) L S F.t.. We can then apply Theorem 1 for > 0 which yields the following:
Th x [(xx) - (1- (2nc) 1)
ptot + 2W2
(24)
L
In the deterministic setting, it holds all variances vanish o3=0ā- 9up =0 =0. Hence, W = 0 by definition of W2 Therefore, to achieve an error ((xx)- Se for some e>0. (24) suggests
choosing k=0 k2 log
mtot )) Additionally, T=O(Ki) ( and N required by Theorem
=0, it holds that NNO(Kg).. Using batches of size yields the desired complexity. and since o2 dyv
Proof of Corollary 2. Here we choose u and apply Theorem for μ > 0 which yields:
E(((()) L*] + E I (2k=))+ EE E([(20) L')) 2L 2
Hence, to achieve error E[[(ix) L*] e, we need k 0 log (E[[++[(())--21 to guarantee that the first term in the l.h.s. of the above inequality is O(e). Moreover, recall that L-1 = 0ng 3) from Proposition 6 and that Theorem ensure the variance W satisfies:
W2 =0= 5. No + 1g Boo
+ #no02 + =rgo7)
Hence, ensuring the variance term 2L- 122 is of order is achieved by choosing the size of the batches as follows:
(
0z
Kcng
2=2
Byl = 0
1Pyl
Dozx
Oux
E
[Dwwl
G2 Buo
Kig
Recall that (Kk(g)) and (n,) as required by, Theorem 1, thus yiclding the desired result.
Proof of Corollary 3. the non-convex deterministic case, recall that Eg [((=(()))1 s Egot. We thus apply Theorem I for μ < O, multiply by L to get:
2L (C(xo) L + (F) + E5)) + 222
|V(()))
ke
The setting being deterministic, it holds that = Moreover, recall that L = O from Proposition Hence, to achieve an error of order mini [|VC(=;))) S e, suffice to choose
k= C9 (C(xo) - L + (E8 + E- Thus using batches of size and T and N of order Kig O
17

---

Published as a conference paper at ICLR 2022
Proof of Corollary 4. the non-convex stochastic case, Ex 1 E
We thus
apply Theorem for μ < O, multiply L to get:
Σ [[(IVC())))11
S (B([(x0) - -0 (E% + Eg)) 2W2
2L
to achieve an error of order e, we need to ensure each term in the Lh.s. of the above inequality of order e. For the first term, similarly to the deterministic setting Corollary we simply need
k O - (A(z)) L + (E + E. For the second term, we need to have -²=0(e), which achieved using the following choice for the sizes of the batches:
K Kig Dwx
[Dyl = o
1Dgl = O
[Dgou| =0
Poou o
Nig 9ou (1 cgg'
3 22
Finally, as required by Theorem 1, we set T = (Kig) and N = -Kig) thus yielding the desired complexity.
A.4
COMPARAISONS WITH OTHER METHODS
In this subsection we derive and discuss the complexities of methods presented in Table 1,
A.4.1
COMPARAISON WITH TTSA (HONG ET AL., 2020B)
Proposition 11. strongly-conven case
0. The complexity of the TTSA algorithm in Hong et
(2020b) achieve error 7 || x² x²] I is given by:
C(c) c(c)== = ( ((13
17 1/2
1
+ RZ(
log
non-convex case < 0. The complexity of the TTSA algorithm in Hong et al. (2020b) to achieve an error & Eisish [(:)))) is given by:
C(e) = k(1 + N) = o (122)
16 log ()
11
K
Proof. strongly-convex case μ following bound holds:
Using the choice of step-sizes in Hong et al. (2020b), the
8 3(k + kin)
E
x²1
(A
+1:++1144 Lgpu, 2
L
Me + Mg I
+
Mg
4
112 (1))
k tia
where A = E BB|100 - x²1| 1²1 - y (x0))]
and kir given by:
I
(512) 2
hi = max
35
g
(1
+ 02)
By simple calculation, easy to see that IT 1
3(ktka)
<
(k- 1+11+
(k,-1)2
Moreover, using
that Tap O(17²) ) T.y O( we get that
|1 2
E |
xx xp] -
(K: ka 1)2 (1D2 1419
(hio 1)2
60-6A88 AA)
11g
- -p- 22
ka
18

---

Published as a conference paper at ICLR 2022
Using that L= 9) we get " e, need to control both terms in the above inequality. This suggests the following condition to control the second term which dominates the emror.
p- (1+ (
(g + mgx Hence, to reach an error
2
1g L
Pg
Moreover, the result in (Hong et al., 2020b. Theorem 1) requires N = ( log 2) where N is the number of terms in the Neumann series used to approximate the hessian inverse (8 v))= ! in the expression of the gradient VL. Hence, the total complexity given by the following expression:
((c) == k(1 + N) +N
= - (m0 1/2
Kig
7/2 Kig
1
log
Smooth Non-convex case μ Following Hong et (2020b), consider the proximal map of C for fixed > 0:
a(2) == arg min { [(x) f11x= =1(²}
sEA
and define the quantity A = EE [| - 1m where Tn are the iterates produced by the TTSA algorithm. Let K be a random variable uniformly distributed on {O.... K - 1} and independent from the remaining r.v. used in the TTSA algorithm. The result in (Hong et al., 2020b, Theorem 2) provide the following enror bound on A
o² +
k
h A
Σ
A
Hg
L
1SiSk
where p is set 2T. and A max (E(((xn)-L'))) E 19n y (xo)) nition of the proximal map, we have the following identity:
Now, recall that by defi-
Σ B =[IvC(=))1]]
22 13)
Σ 1SiSk
A < 12 Σ A
ISiSK
Hence, we obtain the following error bound:
Σ
e [[IVC(())]]] s (M + 22)0g) + ky)
15ick
where we used that Ly (n2)). Therefore, reach error of order e, TTSA requires:
1 10
k
+
15
Moreover, controlling the bias in the estimation of the gradient requires the Neumann series approximating the hessian. Hence, the total complexity of the algorithm is:
O(Kg log ! terms in
C(e) = k(1 N) = -0(1)) + ng F
1
log ) )
A.4.2 COMPARAISON WITH ACCBIO (JI AND LIANG, 2021)
Complexity of AceBio. The bilevel algorithm AccBio introduced in Ji and Liang (2021) uses celeration for both the inner and outer loops. This allows to obtain the following conditions on k; T and N to achieve an accuracy:
@ H2 log .).T )
.K=5).N=00 =0(nb log los!) :)-
19

---

Published as a conference paper at ICLR 2022
Note that, since AccBio do not use warm-start strategy when solving the linear system, N is : in order to achieve an e accuracy. This contributes an additional logarithmic à & 2 Kg (log : ) This is by contrast with AmIGO which exploits warm start when solving the linear system and thus only needs a constant number of iterations N (KKg) although the dependence on Kig is worse compared to AccBio. However, it is possible to improve such dependence by using acceleration in the inner-level algorithms A₁. and Bg as we discuss in Appendix A.5.I.
required to grow as log _
factor to the total complexity so that C(e) = (n
Complexity AceBio as function 11 and Hag- The authors choose to report the complexity as a function of and Mg instead of the conditioning numbers and Kig. To achieve this, they observe that, under the additional assumption that the hessian dy y) is constant w.r.t y. the Lipschitz
constant I has an improved dependence on Mg: I, O145²) instead of O 3) in the general case where O2g9(2, y) is only Lipschitz in This allows them to express K.C. and to report the following complexities in terms of and Pg:
C(c) - 0 p log 1 2
)
Note that, in the general case where L = (14 the complexity as function of μ and Hy becomes 0(1 ((- 2p= (log ) while still maintaining the same expression terms of Kg and Kg. Hence, using the expression in terms of conditioning allows more general expression for the complexity that is less sensitive to the specific assumptions on g and is therefore more suitable for comparaison with other results in the literature.
A.5 CHOICE OF THE INNER- ALGORITHMS A& AND B3.
The choice of Ak and Bg has an impact on the total complexity of the algorithm. We discuss two choices for Ar and B& which improve the total complexity of AmIGO: Accelerated algorithms (in Appendix 1.5.1) and variance reduced algorithms (in Appendix A.5.2).
A.5.1
ACCELERATION OF THE INNER-LEVEL. FOR AMIGO
AmIGO could benefit from acceleration in the inner-loop by using standard acceleration schemes Nesterov (2003) for As and B₁. As consequence, and using analysis of accelerated algorithms (Nesterov, 2003) in the deterministic setting, the error of the inner-level iterates would satisfy:
IIve y² (=x)]) s A
TE [Ivv - y" (xx))1² S Î. F.g
where dg and Iig are accelerated rates of the form Aς O(1 and I1 0 (kg)))))g) The rest of the proofs are similar provided that A& and 11, are replaced by their accelerated rates As and il., This implies that 7 and N need to be only of order T ( and N = O( so that the final complexity becomes:
C(c) c(c)== (()==0((k))) (KEK log +)
Note that using conjugate gradient for Bg also enjoys an accelerated convergence rate Shewchuk et al. (1994). This is confirmed in our experiments of Figure where AmIGO-CG enjoys the fastest convergence.
1/2 In order to further improve the dependence on Kg to K one would need to use an accelerated scheme when updating the iterates The analysis of such scheme along with warm-start would be an interesting direction for future work.
A.5.2 VARIANCE REDUCED ALGORITHMS FOR As AND B₁
1 Eision I6 (z, y) When the inner-level cost function g is a finite average of functions g y) " empirical average, it is possible use variance reduced algorithms such SAG (Schmidt et al.,
20

---

Published as a conference paper at ICLR 2022
2017). If every function Is is -mooto,h, then by (Schmidt et al., 2017, Proposition 1), the inner level error becomes:
E lyve - (xx))1² x A3E3 x
52 This has the advantage that the error due to the variance decays exponentially with the number of iterations T' As consequence, the dependence of the effective variance W on the conditioning numbers Rig and Kig can be improved to:
with Ao = (1
22 (I -0 + kigl Dawal
-2 Suv
-x x Sav
-00 + +
This can achieved by taking T = (rxkg) up to a logarithmic dependence on the condition numbers. As consequence, the complexity in the strongly convex stochastic setting becomes:
C(c) =0
no² /oc(no (<Me((( ko
+ + Bav + +0)) 1
Eo + B[((wo) 211 )
Kg V ekig)
log
In the non-convex setting, the complexity becomes:
C(t) - 2 (
Kig + (1 vel) + trggg.. + + --++
nog (no²
The downside of this approach is the dependence on the number n of functions gi in the total com- plexity.
B PRELIMINARY RESULTS
B.1 EXPRESSION OF THE GRADIENT
We provide proof of Proposition which shows that C is differentiable and provides an expression of its gradient.
Proof. Assumption ensures that y + g(x, y) admits a unique minimizer (x)) defined as the unique solution to the implicit equation 0,g(2, y (x)) = 0. Moreover, since is twice continu- ously differentiable and strongly convex, it follows that 0gvg(æ, y (x)) is invertible for any E X. Therefore the implicit function theorem (Lang, 2012, Theorem 5.9), ensures that x + (x) is continuously differentiable with Jacobian given by Vzy(x) = 02yg(11 y (z))) y" (x))- Hence, by composition of differentiable functions, L is also differentiable with gradient given by:
VL(x) = (x,
dzyg(1, (m))) y -=x)))=a,,ff "x, (x)).
We can thus define =0 y) = 0 ( y) ( y) to get the desired expression for V ((x) and note that 2* is the solution to (2).
B.2 SMOOTHNESS PROPERTIES OF C, AND W
Proof of Proposition 6. Lipschitz continuity of + (2)). By Assumptions 1 and 3, the implicit function theorem (Lang, 2012, Theorem 5.9) ensures y (z) is differentiable with Jacobian given by:
Vy² (④) -r, v² (x)) y (x)))
Moreover, by Assumption 3, we know that 0gg(z, y) is L' Lipchitz in æ for any E V, hence, [|0 y (x)))) is upper-bounded by Lig. Moreover, by Assumption 1, is Pg-Strongly convex in y uniformly X. Therefore, it holds that [00v y* 11 I p,² This allows to deduce that (x))())) Mo Lig and by application of the fundamental theorem of calculus that:
(x) - y (x'Il Mg 41, 11= - x'||-
This shows that yy is Lipshhit continuous with T.g 1.y" T.'-
21

---

Published as a conference paper at ICLR 2022
Lipchitz continuity of z + 2* (z, v). Let (a, y) and (a', v/) be two points in X' x y. Recalling the definition of x* y) in Proposition 1, it is easy to see that (xx y) admits the following expression:
x² (x, y) Svgg(a, v) a (x.
(25)
Recalling the expression of 2* (x, v) the following holds:
= <1, v) =" 2xx', ,/) = o (x' s/ 1 (z', 1/) - Oyn y) -0,((a,))))) 025
= g0 ./ - Ov v) )000))))0f(( (z'(('/)))
+ Omgg(z a. 1) (0,, ./) - 0yf(z, (z,1)) v))
puoa 1/) (0)g(1r,)))) v) Oyvg(a',
u)) Ougg(a, v) (0, (0, - y))
Hence, by taking the norm of the above quantity a triangular inequality followed by operator in- equalities, it follows that:
11 op 17 - H2 H2llop 11 10, s/''l + +1| where we introduced H1 Ogug(z; (z, 3) and H₂ = Ogug(z' (o'g ,/) for conciseness. Using As-
| - ==' 3/'
111,0 ||
(x,
sumption 1, we can upper-bound || !lop and || op by 15-- By Assumption we know that ||H| H2llop < M, v) (zl. Finally by Assumption 2, we also have that [10, v/) fz v)ll _ (,] v) - (z',2/)1 and that ( w')l B ensuring that:
|| (ar, v) == (z', w')ll S (M,2M, + M. (, v) (/'l
Hence, we conclude that =* is LipLcchhitz continuous with L, defined in (13).
boundedness of 2= (x.. y) Recalling the expression of 2" in (25), it is easy to see that I| y)ll is upper-bounded by N, B since 0ygg(x, y) is pg-- -ttoonlyy convex in y by Assumption 1 and 0 (z. y) is bounded by B by Asssupptio 2.
Regularity of w.
1/ (I. - (
v',²'' =.,((z,)) v) - 02f(2', 3²) - Oeyg(a, u) Ongg(a', )z')²'
= - v) - 0, 0zf(2', , y/) - Onyg(a, u) - z')
+ (02g0(1, y) - 22gg(1', v/)))²
By taking the norm of the above expression and applying triangular inequality followed by operator inequalities, it follows that:
(2, 4 ( // 2')ll $110,f 3) 0.f(2² lo''''/. 1/1 (10 v) 1|2
z'1l (26)
+ 100gg (x, v) 0zyg( (x', .// b/)llap ||=1l
<1, - 2'll + 1ly s'll) + r-111= z'1l
+ M, |1(|=//
1 2/ll).
To get the first term of the last inequality above, we used that 0, is L,-isshhhtzz by Assumption 2. To get the second term, we used that 0zyg(1, v) is bounded since 0yg(#, y) is L' -ipschitz by Assumption 3. Finally, for the last term, we used that 0zg9(1, y) is My-L.ipschitz by Assumption 3.
By choosing x' = x. y' (x) and z' = z" 2x, (z)), easy to see from Proposition that ((I,y" ==<xx""(())) (x()). Hence, applying the above inequality yields:
(x, V=(x)] s(L, + y²(x) (2.
Egll= (x, ve.v" (x))l
<(L, + (x]) +
-10====0(000000 (x.
As shown earlier, ||2 (z. y (x))) is upper-bounded by ,5 B, while || (x. y) - 2" (x. y (x)) is bounded by L=lly - y (-) This allows to conclude that v, v((x)] < L with L defined in (13).
22

---

Published as a conference paper at ICLR 2022
Lipschitz continuity of VL(x). We apply (26) with (v.2) (v"(2), (x, and (y',z') = (v"(=",, y0,,""(()))) which yields:
- ( + Mgll=" (a', (z)) x' + (1))((x))) - y (x')l)
+ (x. y (z)) 2" g
< (T. + M B+ (1) + Tug) | - x'11,
where we used that ||="(=', y² (x'))]l is upper-bounded by 1.2 B, n² is L Lipschitz and y" is Ly Lipschitz. Hence, VC is L-Lipschitz continuous, with L as given by (13).
B.3 CONVERGENCE OF THE ITERATES OF ALGORITHMS A AND B₁
Proof. Controlling the iterates y' of Ai.
Consider a new batch Dg of samples E. We have by definition of the update equation of y that:
1 (xx)) =11y (xxx) a2110,0( N0 (. 1| By 101 D2) (y--t- yy- (x(x))
Taking the expectation conditionally on Ix and y² we get:
E || - v" (xx) (aw)) xk. v' | =(1 - axH)) 1/ (xx))]
+ a |10 (KR,
( 8' ,D)) - v 1/11 Fe v0 v²11
22n ( v (1- -v((xa) 0yg(2k.1
<(1 - (xttt) y y² (zx))l 2 +2aj0²
The first line uses that 0,9 Tk, (D)) an unbiased estimator of 0g 11 For the second line, we use Assumption which allows to upper-bound the variance of 0,g by og Moreover, since g is convex and -mooth and since Og S L_ it follows that the last term in the above inequality non-positive and can thus be booure-buudee by O. By unrolling the resulting inequality recursively for 1 < < k, we obtain the desired result.
Controlling the iterates z" of Bg. The poof follows by direct application of Proposition 15 with 3r and the following choices for An, A, b, b:
A, - Uk, Davv),
=0 yk. Dj) 0, (Iok Uk))
A 00gg((k 8k)
This directly yields the following inequalities:
E || - =" ==<x, v/. 12
<ig ||=| - x (xxx M/ 3x)l( 11²
+ +Rz
E 2 - z (Ix, 8k 1?
<Ī,E || - 2 (xxx 2k 112
where 7i and i2 are given by:
nl = (1 3x
R = 32 0f [1
(mn. 33(NN N Bejty 03
1
N
Bully
First we have that n. < 4 Moreover, Proposition 6, we have that ||>* (xx yx)i 1 Byr hence, Ri < Rj thus yielding the desired inequalities. Finally (15a) also follows similarly using (45) from Proposition 15.
23

---

Published as a conference paper at ICLR 2022
B.4 CONTROLLING THE BIAS AND VARIANCE Eg AND VE
Proof of Proposition 4. Recall that the expressions of Ex and V in (6) involves the conditional
expectation E& ( knowing Us and 2- This can be also expressed using vi as follows:
Ex
VR
= E
E the Jus Nk: Fas I yk: FA
=I M (Tys Mhs zn 2x) I yk -k
(T yke Elzx 2k yk 2k-1]]) 1]]]
where we used the tower property for conditional expectations in the first line. then the fact that the expectation of th conditionally on 2h. ys and 2y: is simply (2g, yk: 2t). Finally, for the last line, we use the independence of the noise and the linearity of V/ w.r.t the last variable. In all what follows, we write ž = [2 [k yks 2k-1] which the same object as defined in Proposition 7. We then treat Eg and V separately.
Bounding Ex_ Using Propositions 6 and 7 we directly get the desired inequality:
Ex 221 18 11 y" (=x))) + 1 [I z² 2"(2,, (2x,,))) m11)1)
22 (A+ F.t IT Fx
Bound on v We decompose v into a sum of three terms Wa, W/ and W given by:
Wx = E [ (Fx. wk: Dj) - 0n (x mr
W = E |10 IAi Uks EN+1.8 - Onyg(Tk. uk)
T W = E (0. ua. Df) - Oz (1))) Omyg(ae an (=x - 2x)
where used that E1+1 is independent from 2 and D, to get the last term. Hence, using Assumption bound the first term of the above relation, we get V s o + W/ + 2W Thus, remains to control each of W/ and W..
Bound on W.. Using that D, is independent from Ên,s, we can apply Proposition 14 to write:
N
W = 3&E Oz - f)(x, T
Σ (1 BxA)
Og(f - f) 8k. DT)
where we used the simplifying notion (f ()k ykk (r,
flans yk Dy) f( vk). Assumption 1 to upper-bound
Using Assumption 3 to bound [|0zug(TK, yb wwlllon by Li
[[ (I M-) I,, by (EN, (1 (1-11a) (Balg) (-0) we get
N-1 W SBaTL /
Σ
(1 - (1)B) 'B [a( Man, yk, T Man, yks Di)
1=
[aulf f) uu. D,) T0,( f) uk DiD1
51 'B [|l (xx, Wh, D,)² $ - Mon, Dj 10' s
Ly
where we used that 11-1(1 (1 B2 1 for the second line, Cauchy-Schware inequality to get the third line and Assumption 4 to get the last line.
9en,
24

---

Published as a conference paper at ICLR 2022
Bound on W Using that ÉN+1,A is independent from 2ge write:
W%
-E
|1000
Oey 9) 2h, Uk., Ex+11)) 2x
+ E 11 100g((x: -xx
- - =2))1
S0 8m
E
|| 12²
(T,)) 2 |1=x =x|]?]
(0)
S 2
2
z| - x" (z 2/ )1?]
+ E || (xoke vx)l1]] + (L9)2 |1as - Ex 1
(10)
S 20 200
R
|| - x* (Jx. uk:) )11
+ 2 ||=E- - Ecll²]
20 sixu
B211
(1v)
20 85n
[1111 || - x (o yk 112 + Ri]]
+ (I'))²
[40 23 "1 I1 ||
2² 2xxx u/-)1 2R
20 B² B²Hrz
gay
52 02 Boy
+2 2 11
202
IIglE ||
=* (0 3/2
9vv
+ 2 2 2
+ (1,)²) R + 20
B² B²,²z
9zy
gzy
(i) follows from Assumptions and 5, (ii) uses that ||>X|| S 2 - -112 +1211111?) (ii) uses that
||a* (Iks yklll I B by Proposition 6. Finally (iv) follows by application of Proposition We further have by definition of Rj. that:
R S L
Hg -3 gou + +pg 20
(29)
Combining the inequalities on Wt. W and (29), we get that V/ tw with w and o² given by (16).
C GENERAL ANALYSIS OF AMIGO
C.1 ANALYSIS OF THE OUTER-LOOP
Proof of Proposition 2. We treat both cases 2 0 and μ separately. For simplicity we denote by Eg the conditional expectation knowing the iterates Tk. y/ and z and write t/s = R2 8h
Case p 2 0. Recall that E is given by:
Eg
7/ E 2
| x11]]] +1 -1)][(((()) L*).
For simplicity define e ud, + (1 w), E = (1 - ()(()))) - -L*) + Ti ||00 - x² and ekp
(dx()( L*). It is then easy that E(ex] is equal to the l.h.s of (10), i.e. E(ea] Fyg.
We
25

---

Published as a conference paper at ICLR 2022
will start by bounding the difference between two successive iterates of ek:
E/ + ex-
(f(xx)) - [ + (1 (C(x)) - ((Ix-1))
Ex-1
1
Is x=11² 1 | =x"11
2
2
(
S udd (f(x)) - -) + (1 (f((x) - ((xxx-1)
d
|| 1
x01² + 5z
(/- 16
11100-11 1²1 ([( (Oo - =a))
(Ork-
|| -27 (5m-1 v((2s-1)) (0x-1- - -x²)
22
+ 2
7k
2
2
1
(18)
udx (C(mk) - L*) + (1 - (00--((((() (f(xa) - ((xx-1))
d1TTK- -1 1|0a-1 - 1 -0 - L*)
16 1| 1|
2 - 27k (Wa-1- - V(( T
-x))
+ 2
S S(udy + (1 (((x)) - ((xx-1))
d 1 | - -x11 12- 5x(1 - w)([(o8-1)-
+ 2
Ilk
1
2
/ 1| - 27
-27 (W1-1- - VV((x=1) (0A-1-2'))
S/ (m(x)
- -[(xx-1)) - dxck-1
+ 17
||
| - -27 (4--1 V(( (00-1- -2*)
2
((6)
S d + Ex V((xx-1) 1) (Ix - xk-1) + 4b
|20 - IX-
2
+ 1/k
( 11 - 27 (w--1 - v((()-1))
T
(o - -x-1)
2
12
dkek-1
- -EEE V ((( 1 5h +
/
2
Se || 1 2710 (W--1~ v ((----=)))
2
+ 2
(i) follows from the update expression I&k = 2k-1 - Th U (ii) follows from the convexity of L and (iii) follows by L-smoothness of L. Taking the expectation conditionally on the randomness at iteration k- and using that Ex-1 [ = 1 we therefore get
7k (5x + Ex) || | 1|]
Ex-1/c + ck - -k-1l S- 56ck-1 - P V (( T 1/k-11 +
2
51(11-1 -1 VL((x-1)) (00-11 1Ck-1-x" xx))
Spet-1 7888 F [|| / 1/1-1 2
11] + +1192-1 (=(12-1)1
5x(0x-1 V (((xA-1))
-
(II-1 - 7/ (((x-1) - -x*)
7k (Ex 6τ) 1(11-1)11
2
(8)
SGEN-1 + 7888 Eb-1 || 1
+ -11ix-1 1/- 2
(((
- 66 - v(((k-1)) (IX-1 - 7h V -xx x²)
26

---

Published as a conference paper at ICLR 2022
where (i) follows from 6% S c₁ since by construction 6% S 1. Taking the expectation w.r.t all the randomness and applying Cauchy-Schwar inequality to the last term yields the following inequal- ity:
udx (C(wx) - (*) + E S(1 5x) + 7188 V/=- + ER-1)
(30)
+ 8u ( $E || 7n VL(xxx11) x -
Since L is convex, we have the inequality: | - V ( - x=1 1s || - -x"1l² Hence, we can deduce that:
6x||===1- - V/k VC(xx-1) - x²12 S 6 - x 2011 & - S 2Tx
where we used that 7n is non-increasing by construction. Combining the above inequality with (30) yields:
Fn + Eg <(1 -00-6 5x) + 76.8 (v= + =k +
22
2 o E ) 1 (E%_))
Case μ < Recall that for μ < O, we set EV. 1
[V
Using that L is L-smooth, we
have that:
L
((xx) C(x+-1) SVC(IK-1) (ok - IK--1) 1)+
2
|
2k
1
2
L2
- - VL 1) 186--111-111 +
1/2-11
2
- < V -7%
V ([(xk=))
( V v((xx11)
LAR x (1
2 + 2 (Wi--1 -vr-1) Un-1 + l1
2
Taking the expectation w.r.t. all randomness in the algorithm in the above inequality, we get:
[[((x,) - ((xx-1)] S 1x
[ 13 V[(xx=1) (( v((x+-1))
L +
E - - cxx 11) 11)]
+ IE 11166--111)
2
7n (1
Lik )
v V 1119
+ Ln
V + E
2
7M (1
LTx E
V T((x -- ST [1xx1111 v[((x=-)))
S Tkk E
VVL( || + L
Vi- + Ex/1)
+ mw
| ||p
" (EXT)
8x 8 1
5
2 k- + E
220 2 (BZ_))
where we used that 1- 1-14 Ag > of Fk yields an inequality of the form:
1 and 0
< 1 - Lik
to get the last incquality. Using the definition
F + 5 6.) 7ASK
( + E
V (E (EX-)) 1E
Hence, in both cases μ 2 0 and μ < 0 we get an inequality of the of the same form, but with different expressions for FR and sk. We get the desired result using Young's inequality, to upper-bound bound the last term in the r.h.s. of the above inequality. More precisely, we use that for any Pk <
22 02 (ER-1)² (E <
1 2 p E + Pk 1
27

---

Published as a conference paper at ICLR 2022
C.2 -NNER-LEVEL ERROR BOUND
In this section we prove Proposition 5 which controls the evolutions of the warm-start errors Ex and E As a first step, in Proposition 12, we provide a result controlling the mean squared error between two successive iterates Tg-1, Th and yk-1- yk which will be used in the proof of Proposition 5.
Proposition 12 (Control of the increments of Th and yn). Consider Sko on and Ry as defined in Proposition 8 for some fixed
Then, the following holds:
B
B
= E | xx-1 11
S k-1 + 2E k- + 25x
E llue yn y4- 112]
=2Øz Ex + 2
Proof. Proof of Proposition 12
We prove each inequality separately.
Increments of dg. By the update equation, we have that Ty. 2k-1 - hence we only need We have the following:
to control E 0
U/ tk-1 19]
E
<
+ 2E |/- - vL((x-
2E [
- k-1 + 2E + 21E
| C (x ()1}]
hence by setting Ç* == 2L, we get the desired inequality. In the convex case (μ 2 0), since L is L-smooth, we have that:
In the case (p < 0), we have E = 27
[v S 2L(((I=-1) - C*) < 2L(11 -2) 2
provided that 1. We also have that (L(x=-1) L*) < ||=2111 1- 1 which
yields [[((==>))] < 2 _ Hence, we can set CA = 2L min ((1 - u) LT
Increments of yv. Denoting by D batch of samples at time iteration t of algorithm A and using the update equation of y we get the following inequality by application of the triangular inequality: T
E 118k 11-1
Zak
$110,0(II,.' v. P
2
00 13 [llw -ou--yy'e v (xx))) & s az Σ
1=0
(o)
L2 E3)
axI (o) (1+ + + 12
1=0
where we applied Proposition for every 0<t 1 to get the second line with AA,:= a1s1tg)
This directly implies the following bound:
l
Uk
|2]
<
+ +22
(31)
On the other hand, using triangular inequality and applying Proposition also have that:
B I1 112]
< 2E
11ex - y" (xxx)]l + 2E [1ua- -y" (=x))) < (4E) + 2R
(32)
The result follows by combining (31) and (32) using coefficients 1-v and
C.3 PROOF OF PROPOSITION
Proof of Proposition 5. We will control each of Fgg and Eg separately.
28

---

Published as a conference paper at ICLR 2022
Upper-bound on Ex Let mh be non-increasing sequences between 0 and 1. The following holds:
Ex E2 [1 y2 (oR (1 )12] + E I1v" (ox y (xx-1))
+ 2E (UK-1 (zx (xx- 1)) (1r (In y (1x-1))
(
51 ra)B |1:R-1 1² (ox }|
(1 rk ) 11 (ara - y" (1x_
(00
$ (1 + rx) (A + R + 2r E |18 (Ix)) - y² (xx-1))1
(10)
< (1 + rw) (Ak- BK_1 R + 21 - B ||:0
x=
(iv) S (AK R + 2L 1 |2 11]
(33a)
(i) follows by Young's s inequality, (ii) uses Proposition 7 to bound the first term and that (1 (1+rr = 2r for the second term, (iii) uses that y" is LypLishchitz by Proposition and (iv) uses the update equation ve -k-1 71
Upper-bound on E Similarly, for non-increasing sequence 0 < 0s S 1, we have that:
E
IE || =x (xx
)1 + LE (xx, 8k) =² 11 Bk 11)
+ 21
(zx 1 x* (I Mh 1) (x (I Wk) =² ==( 1 |k-13)]
<1 + B
|| 2 (2 yk )|}
+11 0% )E 2 (Ir Mk) 2" 2x 1, yk 111)
(0)
S (1 + 0x) (I 15 1 12 + 20 EE' ||
(Ir ( 2n = "x Wk 1111
(00)
3 (1+ (1) (1 + R + 4L
(1 [1 -
- 111 + 1lue - -12-
(6)
A | ||| 2Φ E% 202
(1 0k) [I EE R + A0.0
(34a)
(i) follows by Young's inequality, (ii) uses Proposition 7 to bound the first term and that (1 + +1-00) s 20 for the second term, (iii) uses that 2* (xx v) is L.-Lipschitz in x and by Proposition 6 and, finally, (iv) uses the update equation I% = Fk-1 - n for the term E || I 112 and
Proposition 12 to control the increments E |lvee yk 1 112
In order to express the upper-bound on Ej terms of E instead of Ey, we substitute Eg in (34a) by its upper-bound in (33a) and use that (1 + rx) s 2 to write:
) b |1]
Et <(1 + (II + R 1) + 4L 0 7/ + 4L OurE
+ 8L300 (20r (Ak- R + R
(35)
We can then express (33a) and jointly in matrix form as follows:
E
A EV Pk
R R + 7x
Un Vv
E
II E
where the Ph is 2 x matrix and UR and Va are 2-dimensional vectors given by (17). The desired
result follows directly by substituting E [ | by its upper-bound from Proposition 12 in the above inequality.
29

---

Published as a conference paper at ICLR 2022
C.4 GENERAL ERROR BOUND
Proof of Proposition 9. First note that, by assumption, have that ōgrg" S δ and 6,0g² S 1x-10%=1- Moreover, since 0g and 23 are non-increasing, we also have that Ax-1 I Aş and 11 11.. This implies the following inequalities which will be used in the rest of the proof:
AR-1 S a Ak:
b -o-1 S by IIg.
(36)
Now, let Pk be non-increasing sequence with Pk < By Proposition 2, it follows that Fg satisfies the inequality:
1 (1- dx Ek-1 TKSK + 7M + PT E
P& + Ex <
(37)
On the other hand, by Proposition 5 we know that Fig and Eg satisfy:
E
A + 12) II E R Th (v= 2E + 2Cx Ek ) Vv
Pk
(38)
where the Pk. Un and Vi are defined in (17). For conciseness, define Sy and E to be:
ak 0
Sk
E
Sk Ex
by
By (36), we directly have that:
(A
0
(ve
A
0 (n) 11x
S PAPA
< Su
Pk.
(39)
where the inequality in (39) holds component-wise. Therefore, multiplying (38) by S₁. and using (39) yields:
R2-1)
Ey. P1 Su Pk
n2 (. 2E 2Cx 2cx 1 Un k Vio
(40)
R
Furthermore, by Proposition we can bound E and Ve follows:
E 521 (ax(ax) -1 a 1x-1Ek -b 2L2 R%
v zu (ba
where we used (36) second time to replace As-1 ( and (bx-1(bb-1) by (x(ax) and I1 (bxb))) By summing both inequalities (37) and (40) and substituting all terms E and V by their upper-bounds we obtain an inequality of the form:
FR + plot <A + A E + Alb2-1 1 + Vi
where AC. AV. A are the components of the vector A& defined in (18) and Vito is the variance term also defined in (18). The desired inequality follows by upper-bounding A Al A by their maximum value | loo
D CONTROLLING THE PRECISION OF THE INNER-LEVEL ALGORITHMS.
In this section, prove Proposition 10. To achieve this, first provide general conditions on Ag and II for controlling the rate A and which hold regardless of the choice of step-sizes. This is achieved in Proposition 13 of Appendix D.I. Then prove Proposition 10 in Appendix D.2.
30

---

Published as a conference paper at ICLR 2022
D.1 CONTROLLING II, AND Ag.
We introduce the following quantities:
D log
(1 pk)
(41a)
8
1 2rk
+ 21 2x.0%
8k + 1 + [2pm
( log ((161))
- "u
'ix" - 2
(41b)
log (4 p
(41c)
( 1 log
1- (1 px pu
(41d)
8
1 + Ok
1 + 12x0000
2213 + o3.
+ + (2px)) (2px))-]
D log (16I20=²000 ox))
(41e)
D log 2 4 ))))
(41f)
Proposition 13. Let Pk be non-increasing sequence of positive numbers smaller than 1. Consider Ag and H so that:
( ( .
log A₁ S <min
(42a)
log 1l S min (D (22) log An + D(.0)
(42b)
Then, the following inequalities holds:
||Aellx S (1-(11pt)b)
Ve S Voot
where As and Viot are defined in (18) of Proposition 9 and Viat is defined as:
veat := + 2L o (2 (sk + {))
+ & 22, R + SL30, 2 R + nh (sk + 4L w)
Proof. We first prove that u/ S <1 and p 1 under (42a) and (42b) with ut pt given by:
u = 2 7 Ag. p = 161 oz.
direct calculation shows v <1 whenever (42a) holds. Moreover, recall that w = +b² with ( and (r(2) being the components the vector Un defined in (17). Thus by direct substitu- tion, we get the following expression for ut:
u 20,
2 A 1 20,22 41 2R)
I
A
Therefore, (42b) suffices to ensure that 1// < u Finally, (42b) implies directly that p 1. We will control each component AG, A% and A of the vector Aş separately. Controlling Aü. Recalling the expression of AE, the first component of Aμ, in (18), it holds that:
Af = (1 1-5Pt PP 8x 2G
(
51
PP
5 + YA
(18)
<
Pk
8 + 2 pkdss = =1 p4)6
( holds since o/ Sut while (ii) follows from (42a) which ensures that 2GA S 3pndr.
31

---

Published as a conference paper at ICLR 2022
Controlling A Recall the expression of second component of A% in (18), we have:
A A 11- $ (1 + Fx 16 tx. + 2L 6 (2u1 + (sk + pk))
1 + 2r 1 + 2 (sk + (2px) ()) A} ) S 1 (1- pk)
(()
(i holds since pp == 161. 16 2Φ I 1 and of. S while (ii) is consequence of (42a).
Controlling Ag. Similarly, recalling the expression of the third component of Aş we get that:
A =11 (1 + 0g + n.. (2L + o2) (2uf + (sk + Px p)))
(58 ()) < (1 8 6 (2L o?) (1 (sk: + (22x))=)))
S 1 - -1-(1- (1-11-1p) pk)
where (i) uses that / S and (ii) follows from (42b).
Controlling Vi Recalling the expression of v from (18), we have that:
Viot 5g (AZ + F + 0 2 + 22 (2uk + (Sk + PK 1)) R
5c (1 + 0 1T
87 0 - R2 + Th( + u²)
56g (3r + 21 25
(2
(sk + Pk )) Ri
5x 28% - + SL 0/ 2 Ri + 7is (sk + ut) w² = Vi
where we use 16 < 1 and ut. < 1 for the first line and ut S u for the last line.
D.2 CONTROLLING THE NUMBER OF INNER-LEVEL ITERATIONS
We provide now a proof of Proposition 10 which is a consequence of Proposition 13.
Proof of Proposition 10. We first provide conditions on the number of iterations T and N of algo- rithms A and By to control the rate || and then provide an upper-bound on Vi
Conditions on T and N. We consider the setting with constant step-size >==7, ax and 3 3 and choose r==0 = 1 and - for some 0<0.11. We also take ==1 so that 2 and R. R By direct substitution of the parameters Tk. 02. @k. Tkk 8k, Pke and Çk. in the expressions of D ((2) ((0) (/ ((6) and ((6) defined in (41a) to (41f), we verify that:
k
-1 < DD0, - D/!,) -C2 S min (D (D
-C¹- S min (D1,,
Hence, we can ensure the conditions of Proposition 13 hold by choosing T and N so that:
log A S - max (1, Ci, C2), log 1I, S - log A max (1, C₁ C3).
This is achieved by for the following choice:
T= La - max (C1, C2, Ca) +1,
(43)
N = 12,8 1 (max (C1, C2, C2) + max (C,, C2 Cb)) +1 Hence, for such choice, we are guaranteed by Proposition 13 that | (1-(1-p)
Bound on the variance Viot, By choosing T and N in (43), we know that Ag and 11, satisfy (42), so that the variance term Viaa is bounded by Vitat. Moreover, by direct substitution of the sequences appearing in the expression of V. by their values, we get:
Vlst < Vi.o 5 (A) +1 + 16L 0 "II 21 Mi
(2uh + (sx + 1)) R² R
5x
(1
05' IT Ri + ST.3 (TH Th (sk + wh)w2?
<ō0
110
1 1
u
1 +
? 41,,A w
+ (2
321.
101 ) 18
50 (2 Ri 11331
32

---

Published as a conference paper at ICLR 2022
Furthermore, by definition of R and R 1. we have that:
R S 2/1 1:0000 1
R S 11 3 (B2 o²... auv
+ +z
Moreover, recall that - since we chose v-1. Thus 12 S 2 2 avoz This implies that:
Vhot 1 < 0 1-
2 + +1+ / 21 Ug
B² B2 guv 3uv
+ +11 (44)
+ (411 + SOL + 20L " an -
By choosing T and N as in (43), the following conditions hold:
M
Af S 5 I ( + (L)))),
II < 1
4L? Linoo!
4L2
By applying these inequalities in (44), we get:
vot 00 7
5 00
1 - u
+ 2
2 + 24g
(ogen + (Lg))) B B02 (
+ +z
2
60L 1/ -1
Li x 0g
Mg
1 u
60L $
$
+ 3
2 +
0² = W2
2
50 g
where we used that 2,0g 3 Therefore, have shown that Visat S W with W2 given by (20).
(02 9zy
+ (Lg))
BB 9on
+ 3/0077)
S w by definition of wg in (16a).
E STOCHASTIC LINEAR DYNAMICAL SYSTEM WITH CORRELATED NOISE
Let A be positive definite matrix in Fd x Rd satisfying 0 Mg lo,(A) Lg and b vector in Rd, We denote by 2² -b Consider Am be sequence of i.i.d. positive symmetric matrices in Rd x Idd such that [[[mm]] = A, and 6 a random vector in IRd such that EE = b, with Am and b being mutually independent. Define ΣA = E (A, - A) (An - -A] and denote by and LA the largest singular values of ΣA and A A-1 Let 3 be such that B < L, Finally let o be an upper-bound on E i b [ Let z and z' be two vectors in Red and define the iterates z" and nd such that z = = and
and using the recursion:
z" (I BAm)="~1 36, 3n = (1--AA)=~1 -bb.
Hence, from the definition of -² and .n we directly have that:
II BAn)= Σ II B(T - BA,)
E" II ( BA)=
Σ II B(T-3A)M
1-141
The next proposition computes the bias E n" 2m [=) Proposition 14. The following identities hold:
n z"l 6 =(1 - (A)" - -2')
(1-BA) B
BAjm- ) (6 (6-b)
E[2" z"] ([I-BA))(C -
Proof. The proof is consequence of A, and being i.i.d. and unbiased estimates of A and b. n
33

---

Published as a conference paper at ICLR 2022
The next proposition controls the mean squared errors IE ||a" =²]
and
||2" - 121
Proposition 15. Define n" (n, = min(n, Bpo ). Let 3 such that:
20 (,, "gg(1 + 11 2 032)
8 S 2T.
min
Then, the following inequalities holds:
E 122h -2- =01]] 5(1 - -B1kg)" (0 2 + B2 0 02112*1 02
+ ++3n. nM
1
(nn 1
Bpg
3pg
S(1 - 3pt)) "0 11 - =²1
Moreover, if = 2, then we have:
E 1[1= - =-11²] -0---=1--
<4n 2 2 (1 314 )d1|= - ==
(45)
2
+ 2 03 + n^ 1
n^ 1
02
8po
Proof. is straightforward to see that:
2|"" 11 (1- 111)Bp)) ==1
Now, let's control E ||=" - z"1 1 The following identity holds by definition of =" and g":
1="
(= (=--1_ ) - + (2-1
-
23E (2--1 -
= (1- -I-BA)(6 -b] b)]
32 E b1] b11 +E (3m-1) T 11
E
(w ) ((I BA)² + (E (3n (3--1-z~-1) 2m-11]
32 (z-11) T "ΛZnI + E (b- b) (1 +(1 - BA)D.)) (6 1)
where E, = B BB((An - A) (An (An A)] and Dr En= (1 -BA)² By simple calculation we can
upper-bound the last term by:
B (6 (b-b) (1 (1+2(1 (1A)(1BBA)..)) (b-b) $3 n^ B1tg
1
PE $19]
Moreover, provided that B S )(((+)))) where LA is the highest eigenvalue of A A- AAA-,, then have the following:
1
E
||="" - ="[]] s(1 - B1g 2"-11² |13]
+ 32 (sn-1) T -1 +3 A
E 6 - -0(1))
B14g
- 5(1- / || - zn-1 10 [|]
+ 8
03 0321|=0-11 |112 3
n
3pg 0z
1
Unrolling the recursion, it follows that:
||2" - 2n13] 5(1 Bpy)" 2/12 82 Σ
12
8pn) n--
0 -2]1==~111
+3
n
1
02
Bug
(46)
34

---

Published as a conference paper at ICLR 2022
In particular, if 2' 2", then 2" and get:
E ||2" - =²11²] <( 2 2²1 + 32 ( +3 ns !
+3(n
Bpg )o?
nn
1 8p4
To get the last inequality, we simply choose z' z and recall that:
| S 2((1 B11g)* 11 =01 + ||=
'1
Using the above in in (46) yields:
E B[12" - ="[3] 22n22o2( B1gg
2012 + 2 2,02 8 1111=*1| + nA 3pg
o
1
Bpug
Moreover, by Lemma 3 we know that n18² 12 Bpbg) n- < (1 3yg y and since Byg 1,
2
have that (1 3ug )= S 2 so that (1 BWg ) < 2(1 34g yr Hence, we can write:
2
B112" 2"11]] <4p0 2 B14g yml 2 211 2,3 x 03>11="11 33 )oa
oz n
2
Bpg
B14
Lemma Let and EA be symmetric positive matrix Red x Rdd with a its largest singular value of A and 0 < Mg S o. (A) S Lg. Let 3 be a positive number such that:
B
1 min
(1
1,
2L
2T
(1g( + 1ig x3.)
Then the following holds:
-[-- + B-BEAAll ol 1 33p..
Proof. First note that < L.,
1. so that [[ BA)² + - op I (1 Bpy)2 2 + 820 which holds since I 8A is positive. And since Pg we further have (1 31g))² )2 + 3 1- Bpg. which yields the desired result. C 15+0%
3A is positive. Now. we observe that
3 3
Lemma 3. Let < 1 and 1, then the following inequality holds:
b n-
nb² (1 - b)" S (1
2
Proof. We consider the function h(n,, b) defined by:
1 1-
h(n, b) (n log
log(nb").
1-b
We need to show that (i(n, 6) is non-negative for any n 2 1 and S 1. For this purpose, we fix b and consider the variations of h(n, 6) in n:
- à
0,h(n, b) = loo
2
I
b
--
and non-positive for all n S n². Hence, h(n b) achieves its minimum value in n² the (0, too). We distinguish case depending whether n² is greater of smaller than 1.
0,h(n, b) is non-negative for 2 = log
T-b
Case n* < In this case for n 2 n". Hence, h(n, b) 2 h(1, b) for all n 2 1. Moreover, since h(1, b) = - logg(b²) 2 the result follows directly.
h(n, b) is increasing the interval [1, +0c) since 0, b) 2
35

---

Published as a conference paper at ICLR 2022
Case n² > 1. In this case still have h(n,b) 2 h(n², b) for all 2 1, since n" achieves the minimum value of h. Thus we only need to show that h(n², 2 0. Using the expression n", we have:
1 -
h(n", =1
=100=1-00p -ll--oo loo
log (n D²)
1
1
=1
log (n*b²)
n2*
Since n² > 1, the first term 1 1 is non non-negative, thus we only need to show that n²8² Σ so that the last term is also non-negative. It is easy to see that n² < is equivalent to having h(6) 2 0, where we define the function h(6) as:
nx
((bb) - log b
6².
We can analyze the variations of be computing its derivative which is given by:
1
0,h(b) (1 -b)
26.
Hence, we have the following equivalence:
d,h(b) 2 + 26(1 - 6)(2 - b) S
This is always true for 0 < 6 < 1 since 6(1 b) < 1 so that 26(1 b) - 6)
< 2-b < 1. Thus
2
we have shown that h increasing over [0, 1) so that h(b) 2 i(() = As discussed above, this equivalent to having n²b² < 1, that h(n", b) 2 0 which concludes the proof.
F EXPERIMENTS
F.1 DETAILS OF THE SYNTHETIC EXAMPLE
We choose the functions ff and to be of the form: f(x, v) = 1xx Ayx +yyC, Cj and g(z, ==
y Agy + y/ B Bex where A, and Ag are symmetric definite positive matrices of size d, dz and by dy. By is a dyy d. matrix and Cy is a dy vector with dz 2000 and dy = 1000.
We generate the parameters of the problem so that the smoothness constants T, and I.g are fixed to 1, 16 and Kg taking values in {10', i {O..., 7}}. We then solve each problem using different methods and perform grid-searce on the number of iterations T and M of algorithms Ag and B,
We fix the step-sizes to 7>=1/L and a₁ = Ly and perform a grid-search on the number of iterations 7' and M of algorithms A₃ and B₁ from {10', í 0, 1, 3). For AID methods without warm-start in BR. we consider an additional setting where M increases logarithmically with k, as suggested in Ji et al. (2021), with M=|10² log(k) Similarly, for (ITD) and (Reverse), we additionally use an increasing of the same form.
F.2 EXPERIMENTAL DETAILS FOR LOGISTIC REGRESSION
The inner-level and outer-level cost functions for such task take the following form:
f(x,))
Σ L(y.E),
g(z, y) = Der
Σ L(r.E) EED
pd Σ exx())))l..Il
Dreat
ŞED...
For the default setting, we use the well-chosen parameters reported in Grazzi et al. (2020); Ji et al. (2021) where 1007,=100, 3.50.5, and -10 For the grid-search setting, we select the best performing parameters T, MM and 3x from a grid {10, 20 x (5, 10) x (0.5, 10), while the batch- size (chosen to be the same for all steps of the algorithms) varies from 10 * {0.1, 1, 2, 4]. We also compared with VRBO (Yang et al., 2021) using the implementation available online and noticed instabilities for large values of and N, as reported by the authors, but also drop in performance compared to stocBio for smaller T and N due inexact estimates of the gradient.
36

---

Published as a conference paper at ICLR 2022
AID-CG: 4p=1e100
AmiGO-CG, k=1e110
AmIGD-GD, xy=1e100
AID-N, k=1e000
AID:FP: sg
10
37
10
36
33
33
10'
30
30
10
16
33'
10
AID-CG: CG: my=10+01
AmiGO CG, k=1e+01
AmiGO GD, ky=1e+01
AID N; 1=11e001
AID:FP: 6==1++01
33
KC-
22
167
30"
18"
11
10
20
16-
167
227
10
AID-CG; 4p=1e103
AmIGO-CG, 103
AmIGO-GD, kg-ler03
AID 01:103
AID 11:003
10:3
321
11-2
32
522
204
1F
11-3
221
151
Timels
Times
Timels
Timels
Time/s
AID-CG;
AmIGO-CG,
AmIGO-GD,
12-1
16-
2212
3219
12-1
=e=10+05
k==ee+05
k=le+05
K s=1e=05
10
1005
22.9
AID-CG; 4e4104
ky=1e477
AmIGO-GD: ky11+07
AID-N ky=1e=07
AID-FF: kymle40
10
Look
10:11
Time/s
Timeys
Timets
Timeys
Time/s
Figure 2: Evolution of the relative error vs. time in seconds for different AID based methods the synthetic example. Each column corresponds to a method (AID-CG, AmIGO-CG, AmIGO-GD, AID-N, AID-FP) and each row corresponds method consider T and N from grid {1, 10, 10 10 x {1, 10, 102. 1033. Lightest colors corresponds to smaller values N while nuances within each color correspond to increasing values of T.
choice of the conditioning number Kig For each
37

---

Published as a conference paper at ICLR 2022
Reverse; Kymle+00
ITD; Kym1e+00
Reverse: Kg =y=1e+04
ITD: 1p=1e+04
10r
20-1
10"1
12-00
13:11
10
LOSS
10
20
100
10a
10'
10
10'
10
10a2
10
1M
15 10th
Reverse; ===e++01
ITD; x==1e+01
Reverse; Rg ==1e+05
ITD; x==1e+05
10
127
10
10-1
Los3
12-1
13-41
100
10f
10"
10
10
10"
197
1019
16
109
10
10th
10
12
10
15
15
12
10
k,m1e+3
Kym1e+03
Kg ===1e+07
Kym
121
109
Loss
100
101
20"1
3071
Figure 3: Evolution of the relative error vs. time in seconds for different ITD based methods on the synthetic example. From the left to the right, the first columns correspond Reverse and ITD method small conditioning numbers Ki E (1, 10, 103), last two column are for higher conditioning numbers Kg {10*, 10a, 107). For each method we consider E 10, 10?, 10 Lightest colors correspond to smaller values of T.
F.3 DATASET DISTILLATION
Dataset distillation (Wang et al., 2018; Lorraine et al., 2020) consists in learning a small synthetic dataset such that model trained this dataset achieves small error the training set. Specifi- cally, we consider classification problem of C' classes using a linear model and a training dataset Drr where each training point & E Drr is d-dimensional vector with class Gę {1, .... C). The linear model is represented by matrix y Roxd multiplying data point y and providing the logits of each class. The dataset distillation can be cas as a bilevel problem of the form:
min 1 GERoxd.AER
Σ
(x,
(Dell SED
n" (2, A) E arg min
1 CE(yse, + Cd Σ exp(AA))lv.al
Σ
yERexd
C
c=l
where E Rd vector of suppe-parammter for regularizing the inner-level problem which we found beneficial to add.
Experimental setup. We perform the distillation task on MNIST dataset. We the step- sizes - and T-N=10. We perform grid-search on the outer-level step-size (.E 0.001, 0.0001} and run the algorithms for k: = 10000 iterations.
38

---

Published as a conference paper at ICLR 2022
(d): Validation loss, [2| 100
(e): Validation accuracy, |0]
100
(f): Test accuracy, |D|
100
0.3
12%
AmiGO-Go GD
0.7
23%
50%
0.8
92%
Accuracy
AI
93%
AID-GD
BSA
95%
78%
ITD
85%
0.3
4294
76%
TTSA
0.4 68
100
2.0
02
04
10
12
24 as
03
10
Gradient eval vvaluations
Gradlent evaluations
Gradlent evaluations
(d): Validation loss, |D] 1000
(e): Validation accuracy, [2]
1000
(1): Test accuracy, [2] 1000
AmIGO-CG
48%
AmIGO-GD
0.7
95%
50%
0.4
22%
Accuracy
AID-FP
8
92%
78%
3 0.5
BSA
Reverse
74%
TTSA
0.25 6,50
1:30
1.50
0.25
1.30
6.25
0.50
100
1.50
Gradient eval uations
lez
Gradient evaluations
le2
Gradient evaluations
lez
Validation loss, 2000
(e): Validation accuracy, [0]
2000
(f): Test accuracy, 2000
AmIGO-CG
92%
10%4
AID-CG
0.6
Accuracy
AID.FP
78%
0.5
ESA
0.4
Reverse
0.3
76%
Lo
stocBIC
Gradient wvaluntions
1n2
Gradient evaluations
182
Gradient evaluations
te2
0.5
(d): loss. [2]
(e):
Validation accuracy, [D]
4000
32%
accuracy, [D]
AmIGO-cG
AID CG
Accuracy
Accuracy
78%
AID-GD
0.5
ESA
76%
0.4
15%
Reverse
0.3
52%
20 3.5
0.5
3.0
20
3.5
22
35
stocBiO
Gradient evaluations
Gradient evaluations
Gradient evaluations
Figure 4: Evolution of the validation loss (left column), validation accuracy (middle column) and test accuracy (right column) in time (s) for different methods on the logistic regression task. Each row correspond to different choices for the size of the batch [D] E {100, 1000, 2000, 4000) chosen be the same for all gradient, Hessian and Jacobian-vector products evaluations. Time is reported in seconds.
Training
accuracy
accuracy
AmiGO-GD
1.75
Accuracy
Accuracy
60%
ADD.CG
0.50
AP
40%
10%
ND-GD
TTSA
20%
20%
0.2
08
3.0
0.0
0.6
0.0
0.6
3.0
Time Js
Time
15
Time /5
Figure 5: Performance of various bi-level algorithms on the dataset distillation task on MNIST dataset.
39


Reviews:
[{"review_id": "nNb5JRKXpP5", "reviewer": "Reviewer_QCfa", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is not well-motivated, and the theoretical and experimental results are not convincing enough.\n\n1. This paper focuses on a class of problems: the inner objective is strongly convex (the strongly convex constant can be negative). But the authors do not explain why such a problem is essential and why it deserves study.  This paper follows [Bilevel Optimization: Convergence Analysis and Enhanced Design] in many places. The authors need to explain more details on the difference between that paper.\n\n2. The comparison between existing works (Table 1) is unfair. For example, the algorithm has no inner loop in [ A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic]. But in your method, the inner loops mean that your iteration complexity multiplies a large constant.\n\n3. Even the number of the inner loop is small in the deterministic case. The theoretical results shown in Table 1 mean that the proposed algorithm seems worse than existing algorithms in the strongly convex case. While for the non-convex case, the authors indeed consider the weakly convex function rather than general non-convex cases. The comparison is not convincing.\n\n4. The number of the inner loop $N=O(\\kappa_g^3\\sigma_{g_{yy}}^2)$, which seems very large. I doubt how to use the algorithm in practice, especially when  $\\kappa_g$ is not small.\n\n4. The experiments are weak. The authors only consider quadratic or linear ones. ", "summary_of_the_paper": "This paper proposes amortized implicit differentiation for the bilevel optimization when the inner  objective is strongly\nconvex.", "summary_of_the_review": "Due to previous work  [Bilevel Optimization: Convergence Analysis and Enhanced Design], I deem that the novelty of this paper is limited. I vote to reject.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ko2rjYTXWzQ", "reviewer": "Reviewer_ikrt", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper studies the problem of bi-level optimization using implicit differentiation. In particular, the paper focuses on methods that approximately solve the inner problem and the implicit differentiation. Warm-start strategy is used for solving the inner problem and the implicit differentiation, hence the name “amortized”, although I felt the word “amortized” is a bit less accurate than “warm-up” given that the method still does iterative updates with a warm-up strategy. \n\nThe convergence of the proposed method is analyzed by viewing the iterates of the optimization as a dynamical system. It is different front the previous literature in the way that it analyzes approximate inner optimization and implicit differentiation with warm-up strategy and with faster convergence in the stochastic setting. But I didn’t check the proofs since I am not very familiar with the techniques used in the literature.\n\nThe experimental results show that the proposed method AmIGO is better than its counterpart without warm-start. \nIn terms of weakness, I would hope to see how AmIGO compares to AID-BiO proposed in [1] with warm-start only for the inner-level problem or for solving the linear system in AID.\n\n[1] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. International Conference on Machine Learning, pages 4882–4892. PMLR, 2021.\n", "summary_of_the_paper": "The paper studies the problem of bi-level optimization. In particular, it considers algorithms based on inexact implicit differentiation, where the inner problem and the implicit differentiation are not solved exactly. Warm-up is used when solving the inner problem and implicit differentiation. The convergence of the proposed method is analyzed by viewing the iterates of the proposed method as a dynamical system using the idea of singularly perturbed systems. ", "summary_of_the_review": "The paper proposes a method that uses warm-up for both solving the inner problem and the linear system arising from AID. It also proposes an improved convergence analysis of the warm-start strategy with inspiration from the singularly perturbed systems. The proposed method shows faster convergence than its counterpart without warm-up. But I would like to see comparing it with warm-up only for the inner problem or for solving the linear system in AID.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "e8suA_ms4Yj", "reviewer": "Reviewer_6zLQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Their general proof strategy is to use previous results on singularly perturbed systems with different time scales and a lyapunov-esque analysis. Their rates/complexities improve significantly on previous works (except in the case of nonconvex upper level/strongly convex lower level stochastic methods, for which a previous work provides a better rate under a slightly stricter assumption) and their arguments encompass both the nonconvex upper level and strongly convex upper level cases at the same time (also the deterministic and stochastic cases at the same time), giving a unified analysis. \n\nThe assumptions, claims, and arguments in the paper are rigorously stated and seemingly rigorously proved. However, the majority of the proofs are relegated to the supplementary material, which isn't required to be checked during the review. When I did check some of the proofs, I found an error in one of them that could affect the validity of other arguments. In particular, in the proof of prop 11 in the supplementary material, there is an error in the update equation (should be k-1 in psi subscript) which affects (perhaps only superficially) the definition of zeta_k and perhaps of some other things. In section 4, after “Outer-level problem”, it is written \"and u\\in [0,1]\" Surely this should be u\\in\\{0,1\\}? Is u ever taken to be in (0,1)? I am inclined to believe these can be easily fixed but it’s not completely clear due to the overall density of the paper.\n\nRemarks about trivial/superficial details (I didn't use these for my evaluation but you might be happy to correct them anyways): \n* Immediately after proposition 1 it is written \"... provides an expression for L in terms of partial derivatives of f and g evaluated at (x,y*(x)).\" Should this be “an expression for \\nabla L”? \n* In Appendix A.2 the first line states \"In order to prove Appendix A.2 ...\" Should this be \"In order to prove Theorem 1\"? \n* In the proof of proposition 6 in the appendix it's written \"This allows to deduce that ... any by application\" Should this be \"and by application\"? \n* In B.3 it is written \"the second inequality\" but I can only find one inequality? \n* There are too many commas in the \"Controlling the iterates z^n of B_k\" section where it’s written “the following choices for A_n, A, \\hat{b}, b:”", "summary_of_the_paper": "The paper presents a quite rigorous analysis of approximate implicit differentiation with warm starts applied to strongly convex upper level/strongly convex lower level and nonconvex upper level/strongly convex lower level bilevel optimization algorithms in a very general yet also very practical framework. They allow for stochastic errors in the algorithms solving the upper and lower level problems, making their work practical and applicable to real problems in machine learning (hyperparameter optimization), while analyzing in a way that is agnostic towards which algorithms are specifically used for the lower and upper level problems.", "summary_of_the_review": "* Pros: rigorous arguments, clearly stated assumptions, problem framework is applicable to practice, very good rates in all cases (strongly convex/nonconvex, stochastic/deterministic) except one case (in which the previous related work uses a slight stricter assumptions), comprehensive bibliography/related work section, compelling experiments on both synthetic and \"real world\" problems with comparisons to many other methods of interest in the literature, generally well written and clear given the subject and level of rigor employed.\n* Cons: extremely dense and notation heavy for a conference paper (otherwise well written), I was unable to check several proofs in detail; in some sense this work is much better suited for a journal where it can be reviewed properly.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QvZVY4G7EMN", "reviewer": "Reviewer_Xg4d", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This is an interesting paper that gives nice theoretical links between the proposed algorithm, SPS, and also the stochastic estimate sequence framework. Here are some questions for the authors.\n\nQ1. In table 1, is it possible to include $\\kappa_l$ and $\\kappa_g$ dependence in stochastic settings as well?\n\nQ2. After Corollary 1, the authors point out that $\\kappa_g$ dependence can be further improved by using acceleration or variance reduction. Is it possible to have a more detailed comparison with [Ji and Liang 2021]?\n\nQ3. It looks like the choice for ${\\cal A}_k$ and ${\\cal B}_k$ is critical. More discussions should be provided on this point.\n\nQ4. In numerical tests, it looks like in real-world problems CG based algorithms (Amigo-CG and AID-CG) perform the best. Have the authors test it on other datasets? Some additional results to support nonconvex settings are also beneficial.", "summary_of_the_paper": "This work focuses on bilevel optimization. The key innovation here is the warm start, which enables improved complexity bounds (under some settings). The analysis nicely builds on singularly perturbed systems (SPS). Numerical tests are also provided on both synthetic and real problems, where the merit of warm start is demonstrated.", "summary_of_the_review": "In general this paper is theoretically interesting. This paper could benefit from more discussions on ${\\cal A}_k$ and ${\\cal B}_k$, as well as additional experiments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7AqypIzpkIr", "reviewer": "Reviewer_2dfc", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths\nSections 1 to 3 of the paper is well written and provides a clear overview of the problem and algorithm. The authors also propose a unified analysis which encompasses many of the existing results in the literature.\n\nWeaknesses\nI find Section 4 difficult to read.  The downside to this unified analysis seems to be that the results are difficult to parse (making it difficult to see how to apply these results beyond the known settings).  Here are some of the issues with the exposition:\n- Section 4.1 and 4.2 list properties of the inner and outer problem without providing any clear and concise statements on the conclusions. It would be better to first explain the main result (Theorem 1) before explaining the proof technique.\n- Theorem 1 makes use of notation from Proposition 1 without explicitly mentioning this. \n- There are a list of corollaries about the case of W = 0 and W>0, but W is not really described and it is difficult to see what this quantity corresponds to -- e.g. what are the situations where W = 0?\n- I'm not sure what the message of Proposition 4 is, it makes use of matrices and vectors P_k, U_k, V_k without saying anything about what these are, so I am not sure what to make of this proposition.\n\n", "summary_of_the_paper": "The paper studies the problem of stochastic bilevel optimisation, proving convergence rates for an amortised algorithm which makes use of unbiased estimates of the inner and outer function. The main contributions are theoretical, where they prove sublinear convergence rates.", "summary_of_the_review": "In general, I feel that a 'unified' analysis should be elegant and more instructive than existing ad hoc analysis, but this does not seem to be the case here. There is a lot of notation introduced without proper explanation of what they represent, so it is difficult to properly read and check the proofs of this paper in the limited reviewing time of ICLR.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a quite rigorous analysis of approximate implicit differentiation with warm starts applied to strongly convex upper level/strongly convex lower level and nonconvex upper level/strongly convex lower level bilevel optimization algorithms in a very general yet also very practical framework. They allow for stochastic errors in the algorithms solving the upper and lower level problems, making their work practical and applicable to real problems in machine learning (hyperparameter optimization), while analyzing in a way that is agnostic towards which algorithms are specifically used for the lower and upper level problems.

Three out of four reviewers were rather positive of the paper (scores: 6, 6, 8). One reviewer was very negative (score: 3). To my knowledge, the authors have convincingly answered all the points raised by the reviewer. Unfortunately, the reviewer did not follow up.

Similarly to reviewers, I found sections 1-3 to be extremely well-written and to give a nice overview of the field. Section 4 had slight clarity issues (dense notation) that were addressed in the revision. Reviewer 6zLQ partially proof-read proofs.

Overall, I recommend acceptance as a poster, as this paper is advancing stochastic implicit differentiation and should be of interest to many at the ICLR conference.
Decision: Accept (Poster)