A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum
Authors: Prashant Khanduri
Siliang Zeng
Mingyi Hong
Hoi To Wai
Zhaoran Wang
Zhuoran Yang
Venue: NeurIPS 2021 Poster (2021)
Keywords: stochastic bilevel optimization
non-convex optimization
single time-scale stochastic approximation

Abstract: This paper proposes a new algorithm -- the  \underline{S}ingle-timescale Do\underline{u}ble-momentum \underline{St}ochastic \underline{A}pprox\underline{i}matio\underline{n} (SUSTAIN) -- for tackling stochastic unconstrained bilevel optimization problems. We focus on bilevel problems where the lower level subproblem is strongly-convex and the upper level objective function is smooth. Unlike prior works which rely on \emph{two-timescale} or \emph{double loop} techniques, we design a stochastic momentum-assisted gradient estimator for both the upper and lower level updates. The latter allows us to control the error in the stochastic gradient updates due to inaccurate solution to both subproblems. If the upper objective function is smooth but possibly non-convex, we show that {SUSTAIN}~requires $O(\epsilon^{-3/2})$  iterations (each using $O(1)$ samples) to find an $\epsilon$-stationary solution. The $\epsilon$-stationary solution is defined as the point whose squared norm of the gradient of the outer function is less than or equal to $\epsilon$.  The total number of stochastic gradient samples required for the upper and lower level objective functions matches the best-known complexity for single-level stochastic gradient algorithms. We also analyze the case when the upper level objective function is strongly-convex. 

A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum
Prashant Khanduri University of Minnesota khand0950umn edu
Siliang Zeng University of Minnesota zeng0176@umn. edu
Mingyi Hong"
University of Minnesota mhongOumn edu
Hoi-To Wai CUHK htwai@se. cuhk. edu.hi hk
Zhaoran Wang Northwestern University zhaoranvangggmiil.cc
Zhuoran Yang Princeton University zy6@princeton. edu
Abstract
This work proposes algorithm the Single-timescale Double- momentu Stochastic Approximation (SUSTAIN) for tackling stochastic unconstrained bilevel optimization problems. We focus bilevel problems where the lower level subproblem strongly-convex and the upper level objective function is smooth. Unlike prior works which rely two-fimescale double loop techniques, design a stochastic lower level updates. The latter allows to control the error in the stochastic gradi- ent updates due to inaccurate solution to both subproblems. If the upper objective function is smooth but possibly non-convex,
comeentum-assistene gradient estimator for both the upper and
show that SUSTAIN requires O(e-3/2 iterations (each using O(1) samples) to find e-stationary solution. The e-stationary solution is defined as the point whose squared norm of the gradient The total number of stochastic gradient samples required for the upper and lower level objective functions match the best-known complexity for single-level stochastic gradient algorithms. We also analyze the case when the upper level objective function is strongly-convex.
of the outer function is less than equal
1 Introduction
Many learning and inference problems take "hierarchical" form, wherein the optimal solution of one problem affects the objective function of others [27]. Bilevel optimization is often used to model problems of this kind with two levels of hierarchy [27, 8), where the variables of an upper level problem depend the optimizer of certain lower level problem. In this work, we consider unconstrained bilevel optimization problems of the form:
min Bw ((x) far y (x)) = 1 (x)
S.t. 3y (x) = arg min yeR% {g(x,)) v) = Eelg(a, ()),
where f.g R R. R with x E Rh and y E 1e; f(x.fflx... y: with E Ty (resp. g(x, y: {) with Ç ~ TT)) represents stochastic sample of the upper level objective (resp. lower level objective). Note here that the upper level objective f depends on the minimizer of the lower level objective g. and
we refer to (z) as the outer function. Throughout this paper, g(x, y) is assumed to be strongly-convex y, which implies that ((x:) is smooth but possibly non-convex.
The applications of (1) include many machine learning problems that have a hierarchical structure. Examples are meta learning [13, 31], data hyper-cleaning [35], hyper-parameter optimization [12,
"Conesponding Author: Mingyi Hong.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Algorithm
Sample (Upper, Lower)
Implementation
Batch Size
Per-Iteration Complexity
BSA [14]
O(c-9), (
Double loop
0(1)
Oldg. log
stocBiO [19]
0) O)
Double loop
O(e"))
Old log 7))
TTSA [18]
O(6-5/9), ((c-5/2)
Single loop
(11)
O(dg log 7)
STABLE [5]
O, ())-²)
Single loop
0(1)
(dd
SVRB [17]
O(e 4/9,, O 3/2)
Single loop O(1)
(dd))
SUSTAIN (this work)
O(e 4/2), O(E 8/2)
Single loop
((1)
Oide llg T)
Table 1:
Comparison of the number upper and lower level gradient samples required to achieve an e-stationary point in Definition 1.1. For the algorithms with Odd, log I') per-iteration dependence, the Hessian inverse can be computed via matrix vector products; algorithms with (df)) dependency requires Hessian inverses and Hessian projections, which incur heavy computational cost.
13, 29], and reinforcement learning [22], etc.. To better contextualize our study, below we describe examples on meta-learning problem and data hyper-cleaning problem:
Example 1: Meta learning. The meta learning problem aims to learn task specific parameters that generalize a diverse set of tasks [30]. Suppose we have M tasks iT, 1..... MM and each task has a corresponding loss function Lax yri Ex) with & representing a data sample for task Ti, x g the model parameters shared among tasks, and y E R% the task specific parameters. The goal of meta learning is then to solve the following problem:
1 EM BE [L (x)) m (Lo(e,, = M
s.t. 5" (x) E arg min SEREM oi (I, E M
(B yis + R(v:)),
(2)
where y - 1vi :..., whrl iT, R(-) is a strongly convex regularizer while S, and Dj are the training and testing datasets for task Ti Compared to the number of tasks, the dataset sizes are usually small for meta-learning problems, so the stochasticity in tackling (2) results from the fact that at each iteration we can only sample subset m out of M tasks. Note that this problem is special case of (1). O
Example 2: Data hyper-cleaning. The data hyper-cleaning is hyperparameter optimization problem that aims to train a classifier model with a dataset of randomly corrupted labels [35]. The optimization problem is formulated below:
min 2p ((x)) = EieD,, Ma, y" (x),
(3)
s.t. y (x) = arg min {cllull + E.ED, (a))) y, b.)}.
In this problem, we have dup = |Derl and di is the dimension of the classifier. Moreover, (a,, b,) is
the ith data point: L(-) is the loss function, with y being the model parameter: x; the parameter that determines the weight for the ith data sample, and o R + E4 is the weight function; e > 0 is a regularization parameter; Deal and Drr are validation and training sets, respectively. Clearly, (3) is a special case of (1) where the lower level problem finds the classifier y" (I:) with the training set Der. and the upper level problem finds the best weights x with respect to the validation set Dval-
A natural approach to tackling (1) is to apply alternating stochastic gradient (SG) updates. Let 3,a a > 0 be some step sizes, one performs the recursion
y+ + yg(z,)),
x + v-z-ov,((1))) y)
(4)
such that Vyg(a,)) y). Vzl(r;)) are stochastic estimates of V Vyg(a, v), V((x),, respectively. Notice that (4) is significantly different from the standard alternating primal-dual gradient algorithm for saddle point problems. Particularly, the design of v,((x;)) is crucial to the SG scheme in (4). Observe that V((x)) can be computed using the implicit function theorem, and its evaluation requires f(.-)) -) and y* (x), the minimizer of g(2, y) given (cf. (5)). This gives rise to unique challenge to bilevel optimization, where y" (z) can only be approximated by y obtained in the first relation of (4).
In light of the above observations, previous endeavors have considered two approaches to improve the estimate of y (x) while v_ y) is used as a biased approximation of V((x). The first approach to apply the double-loop algorithms. For example, [14] proposed to repeat the yt update for multiple times to obtain a better estimate of y (z) before performing the x update, [19] proposed

---

to take a large batch size to estimate V Vg)(r,y). While simple to analyze, these algorithms may suffer from poor sample complexity for the inner problem. The second approach is to apply single-loop algorithms where the -utuuttees are performed simultaneously with the -upuutts Instead, advanced techniques are utilized that allows yy to accurately track y (x)) For example, [18] suggested to tune the step size schedule with / > o, [5, 17] proposed single-timescale algorithms with advanced variance reduction techniques. However, the latter two algorithms require Hessian projections onto a compact set along with Hessian matrices inversion which scales poorly with dimension (i.e., in (dk))) )). We summarize and compare the complexity results of the state-of-the-art algorithms in Table 1.
careful inspection on the above results reveals a gap in the iteration/sample complexity compared to single-level stochastic optimization. For instance, an optimal stochastic gradient algorithm finds an e-stationary solution [ef. Definition 1.1] to min, 18 [[(;;; {)] in O(e iterations [10, 37, 42]. For bilevel optimization, the fastest rate available is only O(c 2) to the best of the authors' knowledge. In comparison, the proposed algorithm achieves a rate of ((e-3/2) During the preparation of the current paper, preprint [17] has appeared which extended [5], and achieves an improved rate of O(e-3/2). We remark that the latter work follows different design philosophy from ours and maybe less efficient; see the detailed discussion at the end of Sec. 3.
Contributions. In this paper, we depart from the prior developments which focused on finding better inner solutions v" (2) to approximate V (,((;;)) y) ~ V((x). Our idea is to exploit the gradient estimates from prior iterations to improve the quality of the current gradient estimation. This leads to momsntuun-assiseed stochastic gradient estimators for both Vz9(z, y) and V((x) using similar techniques in [7, 37] for single-level stochastic optimization. The resultant algorithm only requires (()) samples at each update, and updates x and y using step sizes of the same order, hence the name single-timescale double-momentum stochastic approxjmation(SSUS (SUSAAIN algorithm. Additionally, it is worth noting that our algorithm has O dee) per iteration complexity, compared to the ( complexity of STABLE [5] and SVRB [17]. That is, the SUSTAIN algorithm is both sample and computation efficient. Our specific contributions are:
We propose the SUSTAIN algorithm for bilevel problems which matches the best complexity bounds as the optimal SGD algorithms for single-level stochastic optimization. That is, requires O(e (32) [resp. ( D(E-)) samples to find an e-stationary solution for non-convex (resp. strongly- convex) bilevel problems; see Table 1. Furthermore, the algorithm utilizes single-loop update with step sizes of the same order for both upper and lower level problems. Such complexity bounds match the optimal sample complexity of stochastic gradient algorithms for single- problems.
By developing the Lipschitz continuous property of the (biased) stochastic estimates of V((x). we show that obtaining good estimate of V((x) does not require explicit (sampled) Hessian inversion. This key result ensures that our algorithm depends favorably on the problem dimension.
Comparing with prior works such as TTSA [18], BSA [14]. STABLE [5] and SVRB [17]. our analysis reveals that improving the gradient estimation quality for both V (1 y) and V((x)) is the key to obtain a sample and computation efficient stochastic algorithm for bilevel optimization.
Related works. The study of the bilevel problem (1) can be traced to that of game theory [36] and was formally introduced in [2-4]. It is also related to the broader class of problems of Mathematical Programming with Equilibrium Constraints [26]. Related algorithms include approximate descent [9, 38), and penalty- based methods [40]; see [6] and [25] for a comprehensive survey.
In addition to the works cited in Table 1, recent works on bilevel optimization have focused on algo- rithms with provable convergence rates. In [34], the authors proposed BigSAM algorithm for solving simple bilevel problems (with a single variable) with convex lower level problem. Subsequently, the works [24, 23] utilized BigSAM and developed algorithms for general bilevel problem for the cases when the solution of the lower level problem is not a singleton. Note that all the aforementioned works [34, 24, 23] assumed the upper level problem to be strongly-convex with convex lower level problem. In a separate line of work, backpropagation based algorithms have been proposed to approximately solve bilevel problems [12, 35, 16, 15]. However, the major focus of these works was to develop efficient gradient estimators rather than on developing efficient optimization algorithms.
Notation.
For any x E Rd, we denote ||>||| as the standard Fuclidean norm; as for X E RRuxd || induced by the Euclidean norm. For multivariate function [x, y), the notation VzJ(z,)) y) [resp. V,f(x, y) refers to the partial gradient taken with respect to (w.rt.) [resp. y]. For some μ
3

---

0, function fæz y) is said to be p-strongly-conye in x if f(z, 3) |||=|| 2 is convex in z. For some L > O, the map A: R² + I is said to be L-Lipschitz continuous if [|A(()) A(v)l S L yll for any y E R A function f R - R is said to be L-smooth if its gradient is L-Lipschitz continuous. Uniform distribution over a discrete set (T. is represented by 441...... T))
T
Finally, we state the following definitions for the optimality criteria of (1).
Definition 1.1 (c-Stationary Point). A point is called c-stationary if [V(xa) |2 < c. A stochastic algorithm is said to achieve an e-stationary point in t iterations if EI] V((x)) & e, where the expectation is over the stochasticity of the algorithm until time instant
- L" S C, where l' = min 2p ((r). A stochastic algorithm is said to achieve an c-optimal point in t iterations if E[((24) - 2 < C, where the expectation is over the stochasticity of the algorithm until time instant t.
Definition 1.2 (c-Optimal Point). point x is called c-optimal if {(x) -
2
Preliminaries
We discuss the assumptions on (1) to specify the problem class of interest. We also preface the proposed algorithm by describing a practical procedure for estimating the stochastic gradients. Assumption (Upper Level Function). f(r. y) satisfies the following conditions:
V v) and (ar y) Lipschitz continuous w.r.t. (x., E TRdup Rdd, and with constants I,, 2 O and I,,, 2 0, respectively.
(ii) For any (x, 3) E Rd x Rd, we have v/V v)ll S Cf2, for some C₁ 2 0.
Assumption (Lower level Function). g(2, y) satisfies the following conditions:
(i) For any Th and y E Rddh, g(z, y) is twice continuously differentiable in (ar, y).
(ii V (I, 8) is Lipschitz continuous w.r.t. (I, y) Rd x Rd, and with constant 4g 2 0.
(iii) For any E TRuuu, g(r.) -) is ( ug-sttrongly-conver in y for some By > O.
(iv) 2 (2r, y) and V2 (yyg(ar y) are Lipschitz continuous w.r.t. (I, y) E TRu x Ride, and with constants L.g 2 0 and I. O, respectively.
(v) For any (x,y) E Rd Rd, we have 11,2, y)1 S Coen for some Cgen Assumption (Stochastic Functions). Assumptions 1 and 2 hold for f(x, E) and g(ar, y: <). for all & E supp(xy) and Ç E supp(Tg) where supp(r) is the support of æ. Moreover, we assume the following variance bounds.
V.s(I, S <oj. f.:
(z,,0) (x)( < Jf.
E|| EII 2g0((,)) - Veyg(z, yi 2 S gax for some of 2 o 2 and 0a 2 0.
These assumptions are standard in the analysis of bilevel optimization [14]. For example, they are satisfied by range of applications such as the meta learning problem (2), data hypercleaning problem (3) with linear classifier. Notice that under these assumptions, the gradient Vε(.) is well-defined. By utilizing Assumption (-(1) and (ii) along with the implicit function theorem [33]. it is easy to show that for a given E E I2 dd, the following holds [14, Lemma 2.1]:
V((T) V fz (x)) V2,9(2, y (E) 2y y"
(5)
Obtaining y" (xx in closed-form is usually a challenging task, so it is natural to use the following gradient surrogate, At any (i, 3) Rd,. define:
vf(z. = (z) Va V by (e -V ff,
(6)
Evaluating (6) requires computing the exact gradients and Hessian inverse which can be non-trivial. Below, we describe a practical procedure from [14] to generate a biased estimate of V fz, Ø).
Stochastic gradient estimator for Vd(x). The estimator requires a parameter K E N and is based on a colleccion of K +3 independent samples E := (() ..... ((K) k(K)), where & ~ c. Tg.
i = 0.... K, and k( (K) ~ (0, ..., K 1). We set
V)(,n) = v.I(a,v:()
K v va.g((. Lg
v (0))
K(R
II
I
V Vevo(x, vi ((1)
(ol(a,))))
(7)
4g

---

where we have used the convention IT==1 = = O. It has been shown in [14, 18] that the bias with the gradient estimator (7) decays exponentially fast with K, as summarized below:
Lemma 2.1. Under Assumptions 2. For any K 2 1, the gradient estimator in (7) satisfies
Oas Cz (I (1-Ma) pg Lg (1-
[V (x
A (z. v) R x Rd.
(8)
Pg
The detailed statement of the above lemma is included in Appendix C. We remark that each computa- tion of V far y: {) requires at most K Hessian-vector products, and later we will show that setting K = ( (7') is necessary for the proposed algorithm. Since V g y; () is of size do dia the total complexity of this step is (Iog(TT)d))) On the contrary, STABLE [5] and SVRB [17] require (ad to estimate the Hessian inverse, which is more computationally expensive when di >> 1. Indeed, it has been explicitly mentioned [5] that "our algorithu (STABLE) preferable in the regime where the sampling is more costly than computation or the dimension d is relatively small".
Notice that (7) is not the only option for estimating the gradient surrogate V f(z, y). For ease of presentation, below we abstract out the conditions on the stochastic estimates of V V required by our analysis as the following assumption:
Assumption 4 (Stochastic Gradients). For any (z, v) Rd RR there exists constants of, 0g 2 such that the estimates V29(I, y: C). fz E) satisfy:
(i) The gradient estimate of the upper level objective satisfies:
E V f (z, E) Vf y) B(x, ())
(9)
where (xx, y) (z, y: <)]
V fz, y) is the bias in estimating V f y).
(ii) The gradient estimate of the lower level objective satisfies
E V 9g y:
Vug( m) og.
(10)
As observed from Lemma 2.1, the gradient estimator (7) satisfies Assumption 4(1).
Lastly, the approximate gradient defined in (6), the true gradient (5), well the optimal solution of the lower level problem are Lipschitz continuous, as proven below:
Lemma 2.2. [14, Lemma 2.2] Under Assumptions 1, 2 and 3, we have
[V,(,,)) - VE(x))I < (x) - yll. 11 (z1) y (x2)) S Ly - x2ll-
(11)
[((xx) - v((x2)) < Ly z2|1.
for all x, I1111 E Rd and E Rdd The above Lipschitz constants are defined as:
Cgg + Css
Lggu Cauy pg
L.
L Ls. +
+
L = L+
Ly
(12)
Hg
Hg
Mg
Mg
The first result in (11) reveals that ( y) approximates V((x) when y y (I)). This suggests that a double-loop algorithm which solves the strongly-convex lower level problem to sufficient accuracy be applied to tackle (1). Such approach has been pursued in [14, 19]. Next, we propose an algorithm which rely on single-loop updates with improved sample efficiency.
(x.
3 The proposed SUSTAIN algorithm
Equipped with a practical stochastic gradient estimator for V((x) [ef. (7)), our next endeavor is to develop single-loop algorithm tackle (1) through drawing (1)) samples for upper and lower level problems at each iteration. Our main idea to adopt the recursive momentum techniques developed in [7, 37]. Notice that these works utilize unbiased stochastic gradients evaluated at consecutive iterates to construct a variance reduced gradient estimate for single-level stochastic optimization.
In the context of bilevel stochastic optimization (1), few key challenges are in order:
5

---

Algorithm 1 The Proposed SUSTAIN Algorithm
1: Input: Parameters: [3:]1=0
17-1 {ar) 7-1
{n Jizo and {nl 1 with nó = no =
2: Initialize: zo. yos set I- y-1 hL, h_ =0
do 4: (u-update) Compute the gradient estimator hg by (13) and yt+1 yt 3.h1.
3: for = 0 to T
5: (x-update) Compute the gradient estimator by by (14) and set 21+1 21 ach
6: end for
7: Return: Ta(T) where a(T) ~ U(.....,
Recall from Lemma 2.1 that obtaining an unbiased estimator for the outer gradient Vε(z) requires using K samples in (7), this calls for the new techniques to control the bias arising from approximating V((x).
The gradient estimator (7) has a more complicated structure than a plain gradient estimator, as it involves up to three different stochastic vectors/matrices related to V faz y), f y), V (z, ( y), and one stochastic inversion that is related to Wyn((r, y)]- -2. It is not clear which are the most important objects for which variance reduction shall be applied.
Our key innovation is to develop a useful estimate of ff y) by using a novel double nomble-momentum technique. First, we build recursive momentum estimator for Vyg(z, y), based upon which the variable gets updated. Then, with such a "stabilized" inner iteration, we compute an estimate of Vf(x,)) v) as given in (7), by using the four stochastic vectors/matrices mentioned above but without performing any variance reduction. Such stochastic estimator will then be used to construct recursive momentum estimator for [ y)- The intuition that as long as y is accurate enough, then the stochastic terms in (7) are also accurate enough, so they can be used to construct the estimator for the outer gradient. Our approach only tracks two vector estimators, while still being able to leverage the low-complexity sample-based Hessian inversion as given in (7).
The SUSTAIN algorithm is summarized in Algorithm 1. Define of E [0, V/ E [0, 1]. For the lower level problem involving y, it utilizes the following momentum-asse assisted gradient estimator, hi E TRd defined recursively as
h
v( (t) (1-1)) (1) + Vyg(zs, - 10
(13)
For the upper level problem involving we utilize similar estimate, hf E Rdd defined as
bff nf (2 + -1-11 mmmmmm)) (1/ + (f V((=-1.M-1)))). (14)
The gradient estimators hi and hf are computed from the current and past gradient estimates V Vyg(z,, Rr, yri (.). (1 and fx,, yr: E.), (f Ex). Note that the stochastic
gradients at two consecutive iterates computed using the same sample sets G. for hę and & for h/.
Both and y-update steps mark a major departure of the SUSTAIN algorithm from existing algo- rithms on bilevel optimization [14, 18, 19]. The latter works apply the direct gradient estimator f Et) [ef. (7)] to serve as an estimate f y) [and subsequently Vf(x)). To guaran- tee convergence, these works focused on improving the tracking performance of yt+1 R y (az) by employing double-loop updates, e.g., by repeatedly applying SG step multiple times for the inner problem; or a sophisticated two-timescale design for the step sizes, e.g., by setting 3,/a, + oc.
recent preprint [17] suggested the SVRB algorithm which applies similar recursive momentum technique as SUSTAIN. However, SVRB is different from SUSTAIN as the momentum estimator applied exhaustively to all the individual random quantities involved (7) and requires Hessian projection. As a result, the SVRB algorithm entails a high complexity in storage and computation as the latter has to store matrix variables of size di x de and computes matrix inverse for each iteration. In comparison, the SUSTAIN algorithm only requires storing the gradient estimators hς hf of size do dup, respectively, and the computation complexity is only Odf.K) for each iteration.

---

3.1
Convergence analysis
In the following, we present the convergence analysis for the SUSTAIN algorithm when ((-) is smooth function [cf. consequence of Assumptions I, and 3]. Before proceeding to the main results, we present lemma about the Lipschitzness of the gradient estimate fx, yı given in (7):
Lemma 3.1. Under Assumptions 2 and 3. have for any (#1, v1), (22,, U2) E R x R
E (a1, 5) V f22, U25 v2l - 1 {1 x2ll + 1 -221
where
6C 12 K LK 1 /22 + 2pgLy 2
6C7 12 K dew 2gghy
6C G3 1.2 K3
+ Ng) 22 (2 p2g)
(15)
and K is the number of samples required to construct the stochastic gradient estimate given in (7).
The detailed proof can be found in Appendix C. We remark that the above result is crucial for analyzing the error of the gradient estimate fif defined in (14). To see this, let us first define the errors of the gradient estimates for the outer and inner functions as follows
ef : h!! V [( We) Be, ef = hi Vag(Er, Me),
(16)
where B₁ == B(x,, ve) denotes the bias. Rewriting of using (14) gives the following recursion:
of = (1-111))e n/)o//1 + (1 (V) Mei Ee) - (f (t -VVI wh) B, VI
B.-1)} + no (VI(I,,WEE.)) Vs( B.)- Lemma 3.1 allows us to control the variance of the second term in the above relation as Oaa h + 6 This subsequently leads to a reduced error magnitude for E|lle/ []a) Similarly, we can show a reduced error magnitude for B|[le] []2) for the inner gradient estimate.
The above discussion suggests that we can track the gradient V using only stochastic gradient estimates (7), without needing to track each component stochastic vectors/matrices. This allows to avoid costly Hessian inversions. In contrast, [5, 17] track the individual stochastic vectors/matrices of (7), and then combine them together yield an estimate of Vd(x). This approach is unable utilize the cheap stochastic estimates of Hessian and have to invert it directly.
Turning back to the convergence analysis of the SUSTAIN algorithm, the main idea of our analysis is to demonstrate reduction of a properly constructed potential function across iterations. For smooth (possibly non-convex) objective function, this potential function consists of a linear combination of the norms of the error terms Ellle/ [|a] and [E[]], along with the outer objective function ((x,) and the inner optimality gap ||yr - v-" (1²))
12 We obtain:
Theorem 3.2. Under Assumptions 1-4. Fix T 2 1 as the maximum iteration number. Set the number of samples used for the gradient estimator in (7) as K = (Lig/ Pbg))) log (Cazx Cr,T (P)) and
at (w + 1)1/3*
8i = Ca00t TH! Cnyy or, vp. On, Oit
(17)
where w, CB. Cayy : Cra are defined (29) of appendix. The iterates generated by Algorithm 1 satisfy
B| 0 (((x0) E Ilyo y (2o)11 log(T)o}
log(T)o
T2/3 + T2/3
(18)
T2/3
T2/3
Details of the constants in the theorem and its proof can be found in Appendix D. The above result shows that to reach an e-stationary point, the SUSTAIN algorithm requires Ö(E -322) (omitting logarithmic factors) samples of stochastic gradients from both the upper and lower level functions.
This sample complexity matches the best complexity bounds for single-level stochastic optimization like SPIDER [10], STORM [7], SNVRG [42] and Hybrid SGD [37]. We claim that this is a near- optimal sample complexity for bilevel stochastic optimization since for example, we have imposed additional smoothness conditions on the Hessian the lower level problem. We will leave this as an open question investigate the lower bound complexity for bilevel stochastic optimization.
Strongly-convex {(x). We also discuss the case when in addition to smoothness, E(-) is stroongyy convex. Here, a stronger guarantee can be obtained:
7

---

Theorem 3.3. Under Assumptions 1-4, and suppose {(x) is p.-stronglyy-oovve Fix any T 2 1, set the number of samples for the gradient estimator (7) as K = (Lg/ log (O2 gay 07 T/v2) and
L + 212 01 a=as p +1 2p G 8 + L," 13
1
Fg
my (ug + 1)a, B. ēga,
where TH. = Ög S + 8L2 + 2p1/Ug and Lg is defined in (15). The iterates generated by Algorithm 1 satisfy for any 12 1 that:
E(e(xs)) [*] S (1 -1yaa² Do
{ T H4
+ [[20g 82
2 + +1)ooj() (19)
where = ((ro) lt + of 11 5" (2r0)1?
The detailed proof can be found in Appendix For large T, setting x 1/T shows that the bound in (19) decreases at the rate of (1/TT).
Theorem 3.3 shows that to reach an e-optimal point, the SUSTAIN algorithm requires Ö(e-)) stochastic gradient samples from the upper and lower level problems, also see the detailed calculations in Appendix E. This improves over TTSA [18] which requires Ö (11)) samples, and BSA [14] which requires Ö(E-'), O samples for the upper and lower level problems. respectively. Again, we achieve similar sample complexity as SGD applied on strongly-convex single-level optimization.
Interestingly, in Theorem 3.3, we have selected r/ = where the momentum term in the lower level gradient vanishes. In this way, the SUSTAIN algorithm is reduced into single-momentum algorithm where the recursive momentum acceleration is only applied to the upper level gradient. Similarly, in Theorem 3.2, if SUSTAIN utilizes only the upper level momentum, i.e., n/ 1, then with appropriate choice of parameters, we get E| ( < O(1/VT) (please see [20] for further details). This implies that to achieve an e-stationary solution SUSTAIN with only upper level momentum requires O 2) stochastic samples for both the upper and the lower level functions. Note that this improves over TTSA [18] which utilizes a vanilla SGD update for both the upper and the lower level problems, i.e., ví = 1 and v/ and requires O(e-5/2) stochastic samples for both upper and lower level functions.
Numerical experiments
In this section, evaluate the performance of the SUSTAIN algorithm on two popular machine learning tasks: hyperparameter optimization and meta learning.
Hyperparameter optimization. We consider the data hyper-cleaning task (3), and compare SUSTAIN with several algorithms such as stocBiO [19] for different batch size choices, and the HOAG algorithm in [29]. Note that in [19], the authors shown that stocBio exhibits better practical performance compared with other bilevel optimization algorithms.
We consider problem (3) with L(-) being the cross-entropy loss (i.e., a data cleaning problem for logistic regression); (xx) := L+exp(-z)" e 0.001; see [35]. The problem is trained the Fashi IS dataset [41] with 50k, 10k, and 10k image samples allocated for training, validation and testing purposes, respectively. The step sizes for different algorithms are chosen according to their theoretically suggested values. Let the outer iteration be indexed by t, for SUSTAIN we choose o = 3 = 0.1/(1 + +/3 and tune for Cny and Cnp (see Theorem 3.2), for stocBiO and HOAG we select a; = da, Br dg and tune for parameters d, and dy in the range [0, 1].
In Figure 1, we compare the performance of different algorithms when the dataset has a corruption probability of 0.3. As observed, SUSTAIN outperforms stocBiO and HOAG. We remark that HOAG is a deterministic algorithm and hence requires full batch gradient computations at each iteration. Similarly, stocBio relies on large batch gradients which results in relatively slow convergence. This fast convergence of SUSTAIN results form the single timescale update with reduced variance resulting from the double-momentee variance reduced updates.
Meta learning. We consider a few-shot meta learning problem [11, 30] (ef. (2)) and compare the performance of SUSTAIN to ITD-BiO [19] and ANIL [30]. The task of interest is 5-way 5-shot
8

---

0.8
SUSTAIN
Training Loss
6
stocBío, Batch size
Testing Accuracy
stocßin, Ratch size 5k
HOAG
4
0.4
SUSTAIN
stooBio, Batch size 1K slocBio, Batch HOAG
0.2
0
2 Gradient Evaluations
Figure I: Hyperparameter optimization: Data hyper-cleaning task on the x10*
x10
Gradient Evaluations
dataset. We plot the training loss and testing accuracy against the number of gradients evaluated with corruption rate p = 0.3.
0.55
0.6
Training Accuracy
Testing Accuracy
0.5
0.55
0.5
0.45
SUSTAIN ANIL ITD-BiO
SUSTAIN
0.45
0.4
ANIL
ITD-BiO
0.4
0.35
0
500
1000
0
500
1000
Iterations
Iterations
Figure 2: Meta learning: 5-way 5-shot learning task on the mini ImageNet dataset. We plot the training and testing accuracy against the number of iterations.
learning and conduct experiments on the mini ImageNet dataset [39, 32] with 100 classes and 600 images per class. We apply learn2learn [1] (available: https: tgtbttb.......gg/ggg com/le htth/eeaanbbless. learn2learn) partition the 100 classes from mini ImageNet into subsets of 64, 16 and 20 for meta training, meta validation and meta testing, respectively. Similar to [1, 19], we implement 4-layer convolutional neural network (CNN) with ReLU activation for the learning task. At each iteration, we sample a batch of 32 tasks from set of 20000 tasks allocated for training and 600 each for validation and testing. For each algorithm, we implement 10 inner and outer update. The performance is averaged over 10 Monte Carlo runs.
For ANIL and ITD--iO, we use inner-loop stepsize of 0.1 and the outer-loop (meta) stepsize as 0.002. For ITD-BiO, we choose the inner-loop stepsize as 0.05 and the outer-loop stepsize be 0.005. For SUSTAIN, choose the outer-loop stepsize a₁ k/ /1 + /) and choose K E [0.1, 1]. choose the momentum parameter as ča /x² and tune for ē & (2, 5, 10, 15, 20). finally, we fix the inner stepsize as 0.05. For the outer loop update ANIL and ITD-BiO utilize SGD optimizer whereas SUSTAIN the hybrid gradient estimator.
the parameter selection suggested in [1, 19]. Specifically, for ANIL,,
From Figure 2 which compares the training and testing accuracy against the iteration number, observe that SUSTAIN achieves better performance compared to ANIL and ITD-BiO on the meta learning task. Also, notice that in the initial iterations SUSTAIN converges faster but then converges probably as a consequence of diminishing stepsizes (and momentum parameter). In contrast, ANIL and ITD-BiO slowly improve in performance and catch up with SUSTAIN's performance. In the appendix, we show that the SUSTAIN algorithm requires less computation time to achieve better performance compared the ANIL and ITD-BiO.
For further evaluation of the performance of SUSTAIN, we have included additional experiments on hyperparameter optimization and meta learning different datasets in the supplementary material.

---

Conclusions and limitations
We have developed the SUSTAIN algorithm for unconstrained bilevel optimization with strongly convex lower level subproblems. The proposed algorithm executes single-timescale without the need use either two-timescale updates, large batch gradients, or double-loop algorithm. We showed that SUSTAIN is both sample and computation efficient, because it matches the best-known sample complexity guarantees for single-level problems with non-convex and strongly convex objective (smooth) functions, while matching the best-known per-iteration computational complexity for the same class of bi-level problems. In the future, we plan rigorously show the sample complexity lower bounds for the considered class of bilevel problems. Further, plan develop sample and communication efficient algorithms for more general class of bilevel problems, such as those with constraints in the lower level problems.
Acknowledgement
We thank the anonymous reviewers for their valuable comments and suggestions. The work of Prashant Khanduri, Siliang Zeng, and Mingyi Hong supported by the National Science Founda- tion (NSF) through grant CIF-1910385. The work of Mingyi Hong was also supported by an IBM Faculty Research award. The work of Hoi-To Wai was supported by CUHK Direct Grant #4055113. Zhaoran Wang acknowledges National Science Foundation (Awards 2048075, 2008827, 2015568, 1934931), Simons Institute (Theory of Reinforcement Learning), Amazon, J.P. Morgan, and Two Sigma for their support. Zhuoran Yang acknowledges Simons Institute (Theory of Reinforcement Learning).
10

---

References
[1] S. M. R. Arnold, P. Mahajan, D. Datta, I. Bunner, and K. S. Zarkias. learn2learn: A library for Meta-Leaming research. CoRR, Aug. 2020.
[2] J. Bracken and J. McGill. Mathematical programs with optimization problems in the constraints. Operations Research, 21(1):37-44, 1973. ISSN 0030364X, 15265463.
[3] J. Bracken and J. T. McGill. Defense applications of mathematical programs with optimization problems in the constraints. Operations Research, 22(5):1086-100 1974. ISSN 0030364X, 15265463.
[4] J. Bracken, J. E. Falk, and J. T. McGill. Technical note-the equivalence of two mathematical programs with optimization problems the constraints. Operations Research, 22(5):1 1974. doi: 10. 00.128770pre.22.5.1000
[5] Chen, Y. Sun, and W. Yin. A single-timeseti stochastic bilevel optimization method. arXiv preprint M.Xiv:2102.066777 2021.
[6] B. Colson, P. Marcotte, and G. Savard. An overview of bilevel optimization. Annals of Operations Research, 153:235-256, 2007.
[7] A. Cutkosky and Orabona. Momentum- based variance reduction non-convex SGD. In Advances in Neural Information Processing Systems 32, pages 15236-15245. Curran Associates, Inc., 2019.
[8] S. Dempe. Foundations of bilevel programming. Springer Science & Business Media, 2002.
[9] Falk and J. Liu. On bilevel programming, part General nonlinear cases. Mathematical Programming volume, 70:47-72, 1995.
[10] C. Fang, C. Li, Z. Lin, and Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pages 189,699,75 2018
[11] C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks. Proceedings of the 34th International Conference Machine Ccarning-Volume 70, pages 1 1126-112 1135. JMLR. org, 2017.
[12] L. Franceschi, M. Donini, P. Frasconi, and M. Pontil. Forward and reverse gradient-based hyperparameter optimization. In Proceedings of the 34th International Conference on Machine Learning Volume 70, page 1165-1173, 2017.
[13] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning. arXiv preprint arXiv:1806.cm 04910, 2018.
[14] S. Ghadimi and M. Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246. 2018.
[15] R. Grazzi, Franceschi, M. Pontil, and S. Salzo. On the iteration complexity of hypergradient computation. arXiv preprint arXiv:2006.166 /0.222006666//8.. 2020.
[16] R. Grazzi, M. Pontil, and Salzo. Convergence properties of stochastic hypergradients. arXiv preprint arXiv:201 2020.
[17] Z. Guo and T. Yang. Randomized stochastic variance-reduced methods for stochastic bilevel optimization. arXiv preprint arXiv:2105, 02266, 2021.
[18] M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXi::2007.05170 2020.
[19] K. J. Yang, and Y. Liang. Bilevel optimization: Nonasymptotic analysis and faster algorithms. arXiv preprint arXiv: axXiv:2010.07962 2020. 2020.

---

[20] P. Khanduri, S. Zeng. M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A comentuu--sssssteee single-timescale stochastic upproximation algorithm for bilevel optimization. arXiv preprint arXiv:2/02.07367. 2021.
[21] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint A41: 6980, 2014.
[22] V. R. Konda and J. N. Tsitsiklis. Actor-critic algorithms. In Advances in neural information processing systems, pages 1008-1014, 2000.
[23] Li, B. Gu, and H. Huang. Improved bilevel model: Fast and optimal algorithm with theoretical guarantee. arXiv preprint arXi::2009.00690 2020.
[24] R. Liu, P. Mu, X. Yuan, S. Zeng, and J. Zhang. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. arXiv preprint arXiv:2006. 04045, 2020.
[25] R. Liu, J. Gao, J. Zhang, D. Meng, and Lin. Investigating bi-level optimization for learning and vision from unified perspective: A survey and beyond. arXiv preprint 1rXiv:2101.11517, 2021.
[26] Z.-Q. Luo, J.-S. Pang, and D. Ralph. Mathematical Programs with Equilibrium Constraints. Cambridge University Press, 1996. doi: (0.1017/CB0998051199838
[27] A. Migdalas, P. M. Pardalos, and P. Värbrand. Multilevel optimization: algorithms and applications, volume 20. Springer Science & Business Media, 2013.
[28] B. N. Oreshkin, P. Rodriguez, and A. Lacoste. Tadam: Task dependent adaptive metric for improved few-shot learning. arXiv preprint arXiv:1805.10123, 2018.
[29] Pedregosa. Hyperparameter optimization with approximate gradient. In International conference on machine learning, pages 737-746. PMLR, 2016.
[30] A. Raghu, M. Raghu, S. Bengio, and O. Vinyals. Rapid learning or feature reuse? towards understanding the effectiveness of maml. ICLR, 2019.
[31] A. Rajeswaran, C. Finn, S. M. Kakade, and S. Levine. Meta-learning with implicit gradients In Advances in Neural Information Processing Systems, volume 32, pages 113-124. Curran Associates, Inc., 2019.
[32] S. Ravi and H. I Larochelle. Optimization as model for few-shot learning. In Proceedings of the 5th International Conference on Learning Representations, 2017.
[33] W. Rudin. Principles of mathematical analysis. McGraw-Hill New York, 3d ed. edition, 1976. ISBN 007054235.
[34] S. Sabach and S. Shtern. A first order method for solving convex bilevel optimization problems. SIAM Optim., 27(2):640-66) 660, 2017.
[35] A. Shaban, C.-A. Cheng, N. Hatch, and Boots. Truncated back-propagation for bilevel optimization. arXiv preprint arXiv:1810.10660 2019.
[36] H. V. Stackelberg. The Theory of Market Economy. Oxford University Press, 1952.
[37] Q. Tran-Dinh, N. H. Pham, D. T. Phan, and L. M. Nguyen. Hybrid stochastic gradient descent algorithms for stochastic nonconvex optimization. arXiv preprint vrXiv:/905.08: 2019.
[38] L. Vicente, G. Savard, and J. Júdice. Descent approaches for quadratic bilevel programming. Journal of Optimization Theory and Applications, pages 379-399, 1994.
[39] O. Vinyals, C. Blundell, T. Lillicrap, k. kavukcuoglu, and D. Wierstra. Matching networks for one shot learning. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
[40] D. White and G. Anandalingam. A penalty function approach for solving bi-level linear programs. Journal of Global Optimization, 3:397-419, 1993.
12

---

[41] H. Xiao, K. Rasul, and R. Vollgraf. Fashion-main mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747, 2017.
[42] D. Zhou, P. Xu, and Q Gu. Stochastic nested variance reduction for nonconvex optimization.
arXiv preprint arviv: 18061081000, 2018.
13


Reviews:
[{"review_id": "tab32hizGc", "reviewer": "Reviewer_YpAh", "summary": "This paper tackles stochastic unconstrained bilevel optimization problems, where the lower level subproblem is strongly-convex and the upper level objective function is smooth. By applying momentum-assisted gradient estimator for both the upper and lower level updates, the paper proposes a new bilevel stochastic optimization method termed SUSTAIN. It has been established that the sample complexity of SUSTAIN matches the best-known complexity for single-level stochastic gradient algorithms. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is generally well-written. The followings are the positive points of the paper.\n+\tBy applying momentum-assisted gradient estimator for both the upper and lower updates, the paper develops a new momentum-based bilevel optimization method. \n+\tThe paper established that the new stochastic bilevel optimization method matches the best-known complexity for single-level stochastic gradient algorithms. \n+\tSome simulations have shown the empirical advantage of the proposed algorithm. \n\nHowever, I have concerns about the paper in the following aspects. \n-\tThe paper claims that it is a single-loop algorithm. However, by looking into the implementation of SUSTAIN, it seems that it needs another loop to calculate (7). \n-\tThe authors pose an interesting question at the bottom of page 5 that ``It is not clear which are the most important objects for which variance reduction shall be applied.’’ It seems that this question has not been addressed explicitly in the paper. \n-\tThe reduction of the SUSTAIN theory to existing results needs further elaboration. Specifically, what is the convergence rate if the momentum of lower-level update is off, e.g., eta^g=1; what is the convergence rate if the momentum of upper-level update is off, e.g., eta^f=1. Authors do provide some discussion in the strongly convex setting, but this should also be discussed in the nonconvex setting. \n-\tThe simulation is not convincing. The curve HOAG in Fig 1 looks a bit strange. It seems that authors do not plot all the accuracy at all the iterations but only at 2-3 iterations. It is important to see the performance of HOAG at the initial stage. Any particular reason for this?\n\nI am happy to raise my score if my concerns are addressed appropriately. \n\n\n========= After rebuttal =======\n\nThanks for answering my questions. Most of my initial concerns have been addressed. I encourage the authors to add the discussion. \nI updated my score accordingly. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "lBpOkmcqji6", "reviewer": "Reviewer_dpaA", "summary": "This paper investigates a bi-level stochastic optimization problem in which the upper level function depends on the minimizer of the lower level objective. A new algorithm based on stochastic momentum-assisted gradient estimator is introduced, by exploiting prior iterations gradient estimates to improve the quality of the current gradient estimation (by reducing its variance). The new algorithm matches the best complexity bounds as the optimal SGD algorithms for single-level optimization. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall comments\n\nTable 1 provides an excellent and clear overview of existing results in bi-level optimization problems and a clear position of the new contributions; much appreciated. The paper is concise, well written and the theoretical results seem correct and improve upon the existing state of the art.\n\n\nDetailed comments\n\n1. Does the Stackelberg equilibrium in non-cooperative game theory fall in this class of bi-level optimization class? If so, this also could be mentioned in the introduction section. \n\n2. The curves in the figures of the numerical results are not distinguishable (in black and white print). Some markers could be included for clarity.\n\n3. Theorem 3.3.  does not include the low-level momentum term. Some explanations on why this term is not required in strongly convex problems should be provided. \n\n4. The remark in the conclusion section regarding the rigurous lower bound for the sample complexity is not very clear. Some more details should be provided here. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is theoretical in nature and the reviewer does not see any evident negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "2h"}, "extra_text": {}}, {"review_id": "gFcvpdk1dp6", "reviewer": "Reviewer_LvzC", "summary": "This paper proposes an algorithm with double momentum solve stochastic bilevel optimization. Both the sample complexity and per-iteration complexity are state-of-the-art. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Merits: optimal sample complexity, low per-iteration complexity by replacing Hessian inverse process by an estimator from reference [14].\n\nFlaws:\n1. Some extra assumptions are made under Lemma C.1 in the appendix, including bounded stochastic gradients. It may help to make the settings more clear by moving these assumption to the main body of the paper. These are critical assumption in the area.\n\n2. The authors cite Lemma C.1 from reference [18] without providing a proof here. I could not figure out how eq(106) is proved in [18] (or corresponding terms in [14]).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "KehEOhh9alN", "reviewer": "Reviewer_wA7a", "summary": "The work developed a new algorithm for unconstrained bilevel optimization with strongly convex lower level subproblems. The proposed algorithm executes on a single-timescale, without the need to use either two-timescale updates, large batch gradients, or double-loop algorithm. Authors showed that SUSTAIN is both sample and computation efficient, because it matches the best-known sample complexity guarantees on single-level problems with non-convex and strongly convex objective functions, while matching the best-known per-iteration computational complexity for the same class of bi-level problems. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and the demonstration is clear. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations have been addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Large-scale bi-level and multi-level optimization has several emerging applications (e.g., robotics) where optimizers are themselves embedded in end-to-end deep learning pipelines as layers. Bilevel problems where the lower level subproblem is strongly-convex and the upper level objective function is smooth is an interesting special case amenable to complexity bound analyses for reaching a stationary point. As such, the contributions of this paper should interest both numerical optimization and application communities. The reviews ask for a few clarifications in the final revision.
Decision: Accept (Poster)