Provably Faster Algorithms for Bilevel Optimization
Authors: Junjie Yang
Kaiyi Ji
Yingbin Liang
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Bilevel Optimization
Momentum
Recursive Gradient Estimator
Hessian Vector Computation

Abstract: Bilevel optimization has been widely applied in many important machine learning applications such as hyperparameter optimization and meta-learning. Recently, several momentum-based algorithms have been proposed to solve bilevel optimization problems faster. However, those momentum-based algorithms do not achieve provably better computational complexity than $\mathcal{\widetilde O}(\epsilon^{-2})$ of the SGD-based algorithm. In this paper, we propose two new algorithms for bilevel optimization, where the first algorithm adopts momentum-based recursive iterations, and the second algorithm adopts recursive gradient estimations in nested loops to decrease the variance. We show that both algorithms achieve the complexity of $\mathcal{\widetilde O}(\epsilon^{-1.5})$, which outperforms all existing algorithms by the order of magnitude. Our experiments validate our theoretical results and demonstrate the superior empirical performance of our algorithms in hyperparameter applications.

Provably Faster Algorithms for Bilevel Optimization
Junjie Yang Department of BCE The Ohio State University yang. 49726osu edu
Kaiyi Ji Department of EECS University of Michigan taiyiji@uma edu
Yingbin Liang Department BCE The Ohio State University liang. 8898osu. edu
Abstract
Bilevel optimization has been widely applied in many important machine learning applications such as hyperparameter optimization and meta-learning. Recently, several momentum-based algorithms have been proposed solve bilevel optimiza- tion problems faster. However, those momentum- algorithms do not achieve provably better computational complexity than Ö(c-2) )) of the SGD-based algo- rithm. In this paper, we propose two new algorithms for bilevel optimization, where the first algorithm adopts momentum-based recursive iterations, and the second algorithm adopts recursive gradient estimations in nested loops to decrease the (0(c1lb) which
variance. We show that both algorithms achieve the complexity outperforms all existing algorithms by the order of magnitude. Our experiments validate our theoretical results and demonstrate the superior empirical performance of our algorithms in hyperparameter applications.
Introduction
Bilevel optimization has become timely and important topic recently due to its great effectiveness in a wide range of applications including hyperparameter optimization [7. 5], meta-learning [33, 16, 1]. reinforcement learning [14, 24]. Bilevel optimization can be generally formulated as the following minimization problem:
min (x)) = ((.,1'(((( s.t. y v²(x) arg min g(x, y). MERP
DER
Since the outer function ((x) = f(z, (x)) depends on the variable I also via the optimizer y² (z) of the inner-loop function g(x, 3). the algorithm design for bilevel optimization is much more complicated and challenging than minimization and minimax optimization. For example, if the gradient-base based approach is applied, then the gradient of the outer-loop function (also called hypergradient) will necessarily involve Jacobian and Hessian matrices of the inner-loop function g(x, y), which require more careful design to avoid high computational complexity.
This paper focuses on the sonconvex-strongly-comm nonconvex with respect to (w.rt.) x and the inner function g(z, y) is strongly convex w.r.t, y any Such case often occurs in practical applications. For example, in hyperparameter optimization [7], f(, y (xx) often nonconvex with representing neural network hyperparameters, but the inner function g (zz,)) -) can be strongly convex w.r.t. by including a strongly-convex regularizer on In few-shot meta-learning [1], the inner function (ax,)) often takes quadratic form together with strongly-convex regularizer. To efficiently solve the deterministic problem in eq. (1), various bilevel optimization algorithms have been proposed, which include two popular classes of deterministic gradient-based methods respectively based on approximate implicit differentiation (AID) [31, 9, 8] and iterative differentiation (ITD) [28, 7].
setting, where the outer function f(x,, y (x)) is
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Recently, stochastic bilevel opitimizers [8, 20] have been proposed, in order to achieve better efficiency than deterministic methods for large-scale scenarios where the data size large or vast fresh data needs to be sampled as the algorithm runs.
In partieular, such class of problems adopt functions by:
O (z)= == fxx y (a)) :- Ee[F(z, y" (x)) g( v) == Ez|G(z, y: O)
where the outer and inner functions take the expected values w.r.t. samples & and Ç, respectively. Along this direction, [20] proposed a stochastic gradient descent (SGD) type optimizer (stocBiO), and showed that stocBiO attains a computational complexity of Ō(c=²) in order to reach an c- accurate stationary point. More recently, several studies [2, 11, 22] have tried to accelerate SGD-type bilevel optimizers via momentum- -based techniques, e.g.. by introducing momentum (historical information) term into the gradient estimation. All of these optimizers follow single-loop design, i.e. updating I and y simultaneously. Specifically, [22] proposed an algorithm MSTSA by updating via a momentum-basee
recursive technique introduced by [3. 36]. [11] proposed an optimizer SEMA similarly to MSTSA but using the momentum recursive technique for updating both and y. [2] proposed an algorithm STABLE, which applies the momentum strategy for updating the Hessian matrix, but the algorithm involves expensive Hessian inverse computation rather than hypergradient approximation loop. However, as shown in Table 1, SEMA, MSTSA and STABLE achieve the same complexity order of (c-2) as the SGD-type stocBiO algorithm, where the momentum technique in these algorithms does not exhibit the theoretical advantage. Such comparison not consistent with those in minimization [3] and minimax optimization [15], where the single-loop momentum- based recursive technique achieves provable performance improvements over SGD-type methods. This motivates the following natural but important question:
Can we design a faster single-loop momentum based recursive bilevel optimizer, which achieves order-wisely lower computational complexity than SGD-type stocBiO (and all other momentum- based algorithms), and is also easy to implement with efficient matrix-vector products?
Although the existing theoretical efforts on accelerating bilevel optimization algorithms have been ex- clusively focused on single-loop design', empirical studies in [20] suggested that double-loop bilevel algorithms such BSA [8] and stocBiO [20] achieve much better performances than single-loop algorithms such as TTSA [14]. A good candidate suitable for accelerating double-loop algorithms can be the popular variance reduction method, such as SVRG [21], SARAH [30] and SPIDER [4], which typically yield provably lower complexity. The basic idea is to construct low variancee gradient estimators using periodic high-accurate large-batch gradient evaluations. So far, there has not been any study on using variance reduction to accelerate double-loop bilevel optimization algorithms. This motivates the second question that address in this paper:
Can we develop a double-loop variance-reduced bilevel optimizer with improved computational complexity over SGD-type stocBiO (and all other existing algorithms)? If so, when such a double-loop algorithm holds advantage over the single-loop algorithms in bilevel optimization?
1.1 Main Contributions
This paper proposes two algorithms for bilevel optimization, both outperforming all existing algo- rithms in terms of complexity order.
We first propose single-loop momentum- saasen recursive bilevel optimizer (MRBO). MRBO updates variables x and simultaneously, and uses the momentum recursive technique for constructing low- variance mini-batch estimators for both the gradient Vg(2,-) and the hypergradient V in contrast to previous momentum-basee algorithms that accelerate only one gradient or neither. Further, MRBO is easy to implement, and allows efficient computations of Jacobian- and Hessian-vector products via automatic differentiation. Theoretically, we show that MRBO achieves a computational complexity (w.r.t. computations of gradient, Jacobian- and Hessian-vector product) of Ö -1.5),
In the literature of bilevel optimization, although many hypergradient- algorithms include iteration loop of Hessian inverse estimation, such loop is typically not counted when these algorithms are classified by the number of loops. This paper follows such a convention to be consistent with the existing literature. Namely, the single- and double-loop algorithms mentioned here can include an additional loop of Hessian inverse estimation in the hypergradient approximation.

---

Table 1: Comparison of stochastic algorithms for bilevel optimization.
Algorithm
e)
G)
c
6)(G,) 6)
Hyy (G,c)
MSTSA [22]
O
O(E-)
O(c
Olc-9)
SEMA [11]
Ole-))
O(e-))
O((-))
O(e
STABLE [2]
((e
0
Ole
stocBiO [20]
O(e
0 (6
(c))))
RSVRB [12] (Concurrent)
O(e
O(e
( 1c)) 10)
(
SUSTAIN [23] (Concurrent)
O 1.5)
O(e 1.5)
(c
(6-1-)
MRBO (ours)
O(E
O 1.6)
(E
VRBO (ours)
O(e
O(e-1.5)
0 O 1.5)
Ge(F, e) and Ge(G, c): number of gradient evaluations w.r.t. F and G.
Jv(G, e): number of Jacobian-vector products V. V.V,G()). Ö()): omit log terms.
Hv(G, e): number of Hessian-vector products (.G())e.
Hyy"" (G, e): number of evaluations of Hessian inverse [
which outperforms all existing algorithms by an order of -.555 Technically, our analysis needs to first characterize the estimation property for the momentum- based recursive estimator for the Hessian-vector type hypergradient and then uses such property to further bound the per-iteration error due to momentum updates for both inner and outer loops.
We then propose a double-loop variance-reduced bilevel optimizer (VRBO), which is the first algorithm that adopts the recursive variance reduction for bilevel optimization. In VRBO, each inner loop constructs a variance-reduced gradient (w.rt. y) and hypergradient (w.rtt x) estimators through the use of large-batch gradient estimations computed periodically each outer loop. Similarly to MRBO, VRBO involves the computations of Jacobian- and Hessian-vector products rather than Hessians or Hessian inverse. Theoretically, we show that VRBO achieves the same near-optimal complexity of ((.51 as MRBO and outperforms all existing algorithms. Technically, differently from the use of variance reduction in minimization and minimax optimization, our analysis for VRBÔ needs to characterize the variance reduction property for the Hessian-vector type of hypergradient estimators, which only involves Hessian vector computation rather than Hessian. Such estimator introduces additional errors to handle in the telescoping and convergence analysis.
Our experiments show that VRBO achieves the highest accuracy among all comparison algorithms, and MRBO converges fastest among its same type of single-loop momentum based algorithms. In particular, we find that our double-loop VRBO algorithm converges much faster than other singlr- loop algorithms including our MRBO, which is in contrast to the existing efforts exclusively on accelerating the single-loop algorithms [2, 11, 22]. Such a result also differs from those phenomenons observed in minimization and minimax optimization, where single-loop algorithms often outperform double-loop algorithms.
1.2
Related Works
Bilevel optimization approaches: At the early stage of bilevel optimization studies, a class of constraint- based algorithms [13, 35, 29] were proposed, which tried to penalize the outer function with the optimality conditions of the inner problem. To further simplify the implementation of constraint-based bilevel methods, gradient-based bilevel algorithms were then proposed, which include but not limited to AID- AlD-based [33, 7, 34, 17], ITD-based [9, 31, 8, 16, 19] methods, and stochastic bilevel optimizers such as BSA [8], stocBiO [20], and TTSA [14]. The finite-time (i.e., non-asymptotic) convergence analysis for bilevel optimization has been recently studied in several works [8. 20, 14]. In this paper, we propose two novel stochastic bilevel algorithms using momentum recursive and variance reduction techniques, and show that they order-wise improve the computational complexity over existing stochastic bilevel optimizers.
Momentum- based recursive approaches: by [3, 36] for minimization problems, and has been shown achieve improved computational complexity over SGD-based updates in theory and in practice. Several works [22, 2, 11] applied the
The momentum recursive technique was first introduced
"Our codes are available online https///hhhubbb.oom/mmiiiaagg///
3

---

similar single-loop momentum based strategy to bilevel optimization to accelerate the SGD- bilevel algorithms such as BSA [8] and stocBiO [20]. However, the computational complexities of these momentum-base algorithms are not shown to outperform that of stocBiO. In this paper, we propose new single-loop momentum- bassd recursive bilevel optimizer (MRBO), which we show achieves order-wisely lower complexity than existing stochastic bilevel optimizers.
Variance reduction approaches: Variance reduction has been studied extensively for conventional minimization problems, and many algorithms have been designed along this line, including but not limited to SVRG [21, 26], SARAH [30], SPIDER [4]. SpiderBoost [37, 38, 18] and SNVRG [41]. Several works [27, 39, 40, 32] recently employed such techniques for minimax optimization to achieve better complexities, In this paper, we propose the first-known variance reduction-
bilevel optimizer (VRBO), which achieves near-optimal computational complexity and outperforms existing stochastic bilevel algorithms.
Two concurrent works: As we were finalizing this submission, two concurrent studies were posted on arXiv recently ([23) was posted on May 8 and [12] was posted on May 5). Both studies overlap only with our MRBO algorithm, nothing similar to our VRBO. Specifically, [23] and [12] respectively proposed the SUSTAIN and RSVRB algorithms for bilevel optimization, both using momentum- based design as our MRBO. Although SUSTAIN and RSVRB have been shown to achieve the same theoretical complexity of (c- as our MRBO (and VRBO). both algorithms have major drawbacks in their design, so that their empirical performance (as we demonstrate in our experiments) much worse that our MRBO (and even worse than our VRBO). SUSTAIN adopts only single- sample for each update (whereas MRBO uses minibatch for stability); and RSVRB requires to compute Hessian inverse at each iteration (whereas MRBO uses Hessian-vector products for fast computation). As an additional note, our experiments demonstrate that our VRBO significantly outperforms all these single-loop momentum-base -baed algorithms SUSTAIN and RSVRB as well as our MRBO.
2 Two New Algorithms
In this section, we propose two new algorithms for bilevel optimization. Firstly, we introduce the hypergradient of the objective function ((*x), which is useful for designing stochastic algorithms. Property 1. The (hyper)gradient of 2 (x) f(x, y (z)) in eq. (I) takes a form of (Φ(()= = (x, y (x)) - V. V vyg(r, y² (x)) Vioo y
(2)
However, it not necessary to compute y" for updating x at every iteration, and it is not time and memory efficient to compute Hessian inverse matrix in eq. (2) explicitly. Here, we estimate the hypergradient similarly to [20, 8), which takes form of
<Φ = v..f(.vv) - V V 10(2 v)n Σ (I - (0 v,,,),
(3)
where the Neumann series 17 Σ - r/) = G
1 is applied to approximate the Hessian inverse.
2.1 Momentum-based Recursive Bilevel Optimizer (MRBO)
As shown in Algorithm 1, we propose a Momentum-basee Recursive Bilevel Optimizer (MRBO) for solving the bilevel problem in eq. (1).
MRBO updates in single-loop manner, where the momentum recursive technique STORM [3] is employed for updating both x and y at each iteration simultaneously. To update y. at step k. MRBO first constructs the momentum-based based gradient estimator ug based on the current V y G(rk, Uk: B,)) and the previous V,G(==1 1: 1 B,) using minibatch B, of samples (see line Note that the hyperparameter fa decreases at each iteration, so that the gradient estimator is more determined by the previous ux-1. which improves the stability of gradient estimation, especially when V% is close to the optimal point. Then MRBO uses the gradient estimator for updating yu (see line 1 II). The stepsize 7i decreases at each iteration to reduce the convergence error.
Algorithm 1).
To update at step k, MRBO first constructs the momentum-bert based recursive hypergradient esti- mator 2A based on the current (x BB.) and the previous ( BB)) computed using several

---

Algorithm Momentum-basee Recursive Bilevel Optimizer (MRBO)
1: Input: Stepsize X, O, Coefficients crg Su, Initializers Fo, Yo. Hessian Estimation Number Q. Batch Size S, Constant C1, C2 m, d > 0
2: for k 0, 1,...: K do
3: Draw Samples By, Bg [B - -,, Qr, Ba} with batch size S for each component
4: if k: 0: then
5:
Uk = (Fx Bz), uk = V, Girk, yk: B,)
6:
else
7:
Uj = (zx B2) ) + (1 (011-a)(ux--- (Ux- (2 ::)))))))))))))))))))))))
8:
Ug V Go yki BB) (1 (uk(1 VV,G(IK 1k- B,))
9:
end if'
update: ? mm+k"
a++1 c: 8kt1 c
11:
3k+1 = FK Pk
Mk+1 = yk Amp uk
12: end for
B&} (see line in Algorithm 1). The hyperparameter aş; decreases at each iteration, that the new gradient estimation 22 is more determined by the previous Uk-1, which improves the stability of gradient estimation, especially when 2y is around the optimal point. Specifically, the hypergradient estimator ( B,) is designed based on the expected form in eq. (3), and takes form of:
independent minibatches samples B, = (B,(j= 2).
(1n (x)) V. F yni BF)
Q-1 V. V.ViG( yk: Ba)n
( (I- (I-NV,G(EN Uk: Fl Uu: BB)) g--1j-Q-9
Σ
(4)
Note that MRBO computes the above estimator recursively using only Hessian vectors rather than Hessians (see Appendix A) in order to reduce the memory and computational cost. Then MRBO uses the estimated gradient un for updating 24 (see line 11). The stepsize 7)s decreases at each iteration to facilitate the convergence.
2.2 Variance Reduction Bilevel Optimizer (VRBO)
Although all of the existing momentum algorithms [2, 22, 11] (and two current studies [23, 12)) for bilevel optimization follow the single-loop design, empirical results in [20] suggest that double-loop bilevel algorithms can achieve much better performances than single-loop algorithms. Thus, as shown in Algorithm 2, we propose a double-loop algorithm called Variance Reduction Bilevel Optimizer (VRBO). VRBO adopts the variance reduction technique in SARAH [30]/SPIDER [4] for bilevel optimization, which is suitable for designing double-loop algorithms. Specifically, VRBO constructs the recursive variance-reduced gradient estimators for updating both and y. where each update of x in the outer-loop is followed by (m + 1) inner-loop updates of VRBO divides the outer-loop iterations into epochs, and the beginning of each epoch computes the hypergradient estimator ( Mhs S1) and the gradient V VrG( M/s S1) based on a relatively large batch S₁ of samples for variance reduction, where (a(x,, Uki S1) takes form of
1 St
( Uk: 81) -
Σ
V
51
Q-1
Q
- V Ubi Cim
Σ
II (1 Q-
(5)
1,.., S1} independent. Note that eq. (5) takes a different form from MRBO in eq. (4), but the Hessian-vector computation method for MRBO is still applicable here. Then, VRBO recursively updates the gradient estimators for VyG Me. S2) and V V Tk,,; (which takes the same form as eq. (5)) with small sample batch S2 (see lines 11 to 16) during inner-loop iterations.
where all samples S = ( I,...
5

---

We remark that VRBO is the first algorithm that adopts the recursive variance reduction method for bilevel optimization. As we will shown in Section 3. VRBO achieves the same nearly-optimal com- putational complexity MRBO (and outperforms all other existing algorithms). More interestingly. as a double-loop algorithm, VRBO empirically significantly outperforms all existing single-loop momentum algorithms including MRBO. More details and explanation are provided in Section 4.
Algorithm 2 Variance Reduction Bilevel Optimizer (VRBO)
1: Input: Stepsize 3. >> 0, Initializer To, Yo. Hessian Q, Sample Size S1, S2, Periods q
2: for k = 0, ......... K do
3: if mod(k;g) g) = 0: then
4:
Draw a batch S, if.d samples
5: us = VrG( Uk: S1), Uk = (T Mk: S1)
6:
else
7:
Uj:: = ūk-11 1,, Uk = 1k-1
8:
end if
9:
#h+1 = Tk Ork
Tk, yk. -1 yk: FR.0 FK41, yk,, Uk.-1 Uk: ūk--1 We for = 0, m12 + do
Set TR.-1
11:
Draw a batch S2 of i.id samples
13:
UR.t = 1-, + (T 3i.ti S2)
14:
UR.1 Uk + V (T Mk. S2)
V,GG(Tk 1k,e-1i
15:
TR,1+1 = Tkies 1 = Wk.t - Büg,t
16:
end for
17:
yk-+1 Uk.++1
18:
end for
3
Main Results
In this section, we first introduce several standard assumptions for the analysis, and then present the convergence results for the proposed MRBO and VRBO algorithms.
3.1 Technical Assumptions and Detinitions
Assumption 1. Assume that the inner function G(x, y, () is p-strongly-conver w.t. for any Ç.
We then make the following assumptions on the Lipschitzness and bounded variance, as adopted by the existing studies [8, 20, 14] on stochastic bilevel optimization.
Assumption 2. Let = (x. v). Assume the functions F F(2; and G(z; () satisfy, for any & and C, a) F(z:)) is M M-Lipschitz. for any z, 2', - - {)) s M| z'|l.
b) (F(=;() and (Gzz{) are L-Lipxchitz, i.e., for any 2,
[v) - VF(( & L||2 - 2'11,
- VG((:()) L||2 -||2- 2'11.
- c) Va Vz(( () is -ipischhitz i.e., for any ='. I VV= V, V S ST||= 2'11-
d) GZ () is p-Lipschitz. for any ,, [V] V -||=- 2'|l.
Note that Assumption also implies that Eg (<==)) VS(=) S M Bx V. V.V(((
V, V vz < L22 and [< -V Vz L3
Assumption 3. Assume that VG(2; has bounded variance, i.e.. E -) V 0
Assumptions 2 and 3 require the Lipschitzness conditions to hold for the gradients and second- order derivatives of the inner and outer objective functions, which further imply the gradient of the outer objective function is bounded. Such assumptions have also been adopted by the existing studies [20, 14, 23, 22, 12] for stochastic bilevel optimization. Furthermore, these assumptions are mild in practice long as the iterates along practical training paths are bounded. All our experiments

---

indicate that these iterates are well located in a bounded regime. is also possible to consider bilevel problem over a convex compact set, which relaxes the boundedness assumption. By introducing projection of iterative updates into such a set, our analysis for the unconstrained setting can be extended easily to such a constrained problem.
We next define the e-stationary point for nonconvex function as the convergence criterion. Definition 1. We call ğ an e-stationary point for a function ((x) if S
3.2 Convergence Analysis of MRBO Algorithm
To analyze the convergence of MRBO, bilevel optimization presents two major challenges due to the momentum recursive method in MRBO, beyond the previous studies of momentum in conventional minimization and minimax optimization. (a) Outer-loop updates of bilevel optimization use hypergra- dients, which involve both the first-order gradient and the Hessian-vector product. Thus, the analysis of the momentum recursive estimator for such a hypergradient is much more complicated than that for the vanilla gradient. (b) Since MRBO applies the momentum-baser recursive method both inner- and outer-loop iterations, the analysis needs to capture the interaction between the inner-loop gradient estimator and the outer-loop hypergradient estimator. Below, we will provide two major properties for MRBO, which develop new analysis for handling the above two challenges.
In the following proposition, characterize the variance bound for the hypergradient estimator in bilevel optimization, and further use such a bound to characterize the variance of the momentum recursive estimator of the hypergradient.
Proposition 1. Suppose Assumptions 1, 2 and 3 hold and < + the hypergradient estimator ( BB) w.r. x based on minibatch B, has bounded variance
E d B&) (4 G
(6)
where G
2M2 -2-2M
11 + 4MP1=10--1100))"1 Further, let En (
3
where Uk denotes the momenium recursive estimator for the hypergradient. Then the per-iteratioon variance bound of U2 satisfies
E1 E[ + 2 -1x))1 o.) ||
x4-1
+ 2 - )4)) L 1y - - (1 ax) ax)
where 12 21.2 + + + +) + 1)²
+ M2 + 1)2.
The variance bound G of the hypergradient in eq. (6) scales with the number Q of Neumann series terms (i.e., the number of Hessian vectors) and can be reduced by that minibatch size S.
Then the bound eq. (7) further captures how the variance || || of momentum recursive hypergradient estimator changes after one iteration. Clearly, the term reduction per iteration, and the remain three terms capture the impact of the randommess due to the update in step k including the variance of the stochastic hypergradient estimator G² (as captured in eq. (6)) and the stochastic update both variables æ and y. In particular, the variance reduction term plays key role in the performance improvement for MRBO over other existing algorithms.
| indicates variance
Proposition 2. Suppose Assumptions 1, 2, 3 hold. Let 1, and y S Thamm where Lip =
2 OLM+L'+TML L a
pL. M Then, we have 4
x²
1 || xx21?
E [[ (xx)) + (T! 11 y (1x))) + || 2 + 08)
2
where Co (1-m))-1MM) 1/2 max ((L + La Mr LM )2, 1.2.-
Proposition characterizes how the objective function value decreases (i.e., captured by E ([(( [[0()))) due one-iteration update || 12 2 of variable (last term in the bound). Such value reduction is also affected by the tracking error y) - y (xx))11 of the variable y (i.e., y does not equal the desirable y" (xxx)) the variance || of momentum recursive hypergradient estimator, and the Hessian inverse approximation error Co w.r.t. hypergradient.
Based on Propositions 1 and 2, we next characterize the convergence of MRBO.
7

---

Theorem 1. Apply MRBO to solve the problem eq. (1). Suppose Assumptions 1, 2, and 3 hold.
Let hyperparameters ci 2
32
+
9h
02
3d
24
m z max dd, (cid)", (e
(0(2)) 7. 0. X &. Y S min AL.aK
V150L. 1211² 8A 12 123 J. Then, we have
Ay
1 K
Σ
2
ll (IX) 3xll2 + 1 |1xx 11 +
1 2x 121
M'
(m K)1/3,
(8)
K
4
1/
K
where 2 is defined in Proposition 2, and M' )(x))- yd
+ (26"
(c] +c2)0
20 e
log(m
Apa
ok
K)
2G
SAuddo
Theorem captures the simultaneous convergence of the variables Ik. yk and || I:: the tracking error lly (Ix) y&ll converges to zero, and the variance || of the momentum recursive hypergradient estimator reduces to zero, both of which further facilitate the convergence 25 and the algorithm.
By properly choosing the hyperparameters in Algorithm 1 to satisfy the conditions in Theorem 1, we obtain the following computational complexity for MRBO.
Corollary 1. Under the same conditions of Therrem I and choosing K = O(c-1.),, Q Olog(( )), MRBO in Algorithm finds an e-stationary point with the gradient complexity of O -1.5) and the (Jucobian-) Hessian-vector complexity of O(E-1.5).
As shown in Corollary 1, MRBO achieves the computational complexity of Ö which out- performs all existing stochastic bilevel algorithms by factor of ((550.) (see Table 1). Further, this also achieves the best known complexity of ( -1.5) for vanilla nonconvex optimization via first-order stochastic algorithms. As far as we know, this is the first result to demonstrate the improved performance of single-loop recursive momentum over SGD-type updates for bilevel optimization.
3.3 Convergence Analysis of VRBO Algorithm
To analyze the convergence of VRBO, we need to first characterize the statistical properties of the hypergradient estimator, in which all the gradient, Jacobian-vectte and Hessian- vector have recursive variance reduction forms. We then need to characterize how the inner-loop tracking error affects the outer-loop hypergradient estimation error in order establish the overall convergence. The complication in the analysis is mainly due to the hypergradient in bilevel optimization, which does not exist in the previous studies of variance reduction in conventional minimization and minimax optimization. Below, we provide two properties of VRBO for handling the aforementioned challenges.
In the following proposition, characterize the variance of the hypergradient estimator, and further use such a bound to characterize the cumulative variances of both the hypergradient and inner-loop gradient estimators based the recursive variance reduction technique over all iterations.
Proposition 3. Suppose Assumptions 1, 2, 3 hold. Let n < J. Then the hypergradient estimator ( St) defined in eq. (5) w.r.t. x has bounded variance as
V Uk: S1) (2((2)) S
S
where o²2 = "MM2+ 1)2. Let D (D(xx)
Vygl(k , 2) )l²),
where U2 and un denote the recursive variance reduction estimators for hypergradient and inner-loop gradient respectively. Then, the cumulative variance of uy and ug is bounded by
2 S
K-2
4 F A
Σ
A
22a 2
W v0)l1.
(10)
As shown in eq. (9), the variance bound of the hypergradient estimator increases with the number Q of Hessian-vector products for approximating the Hessian inverse and can be reduced by the batch size Sj. Then eq. (10) further provides an upper bound on the cumulative variance -K-] As the recursive hypergradient estimator and inner-loop gradient estimator.
K-1
8

---

Proposition 4. Suppose Assumptions 1, 2, 3 hold. Let 17 < 1. Then, we have
([ & [x+{ + aL El V Vyg(Z yall + aB (zx) - -
a² L
+ Mr + = and (+(x)) takes a form of where L2 (L+ 33 P
(0(x)) (.I us) V V Vyg yu (V (2 yn) 1 yf (IaR, y1))
(11)
Proposition 4 characterizes how the objective function value decreases (i.c., captured by [[x((++))]
(xx))) due to one iteration update ||x]| of variable x (last term in the bound). Such a value re- duction is also affected by the moments of gradient w.r.t. y and the variance of recursive hypergradient estimator.
Based on Propositions 3 and 4, we next characterize the convergence of VRBO.
Theorem 2. Apply VRBO to solve the problem eq. (1). Suppose Assumptions 1, 2, 3 hold. Let a 1 I:
20L3 B = I3LQ <
S2 2 2( L. 1)L3, m
16 1,9
LLBS2 where I.m = max Liq I.)].
a+L
Then, we have
K-
Qa K
Q
E (x)))
< 0
+
S + - (p(1))))20))
(12)
Theorem 2 shows that VRBO converges sublinearly w.r.t. the number K of iterations with the
@" is caused by the minibatch gradient convergence eπror consisting of two terms. The first eπror term Si and hypergradient estimation at outer loops and can be reduced by increasing the batch size S (in fact, Q scales only logarithmically with S1). The second error term Q* nnu)² is due to the approximation eгror of the Hessian-vector type of hypergradient estimation, which decreases exponentially fast w.r.t. Q. By properly choosing the hyperparameters in Algorithm 2, we obtain the following complexity result for VRBO.
Corollary 2. Under the same conditions of Theorem 2, choose S = Oc-"), S2 O = (log( o.s }), K =O(="). Then, VRBO finds an e-stationary point with the gradient complexity of Ö 1.5) and Hessian-vector complexity of (c-1.5).
Similarly to MRBO, Corollary 2 indicates that VRBO also outperforms all existing stochastic algorithms for bilevel optimization by a factor of Ö(c- 0.5) (see Table 1). Further, although MRBO and VRBO achieve the same theoretical computational complexity, VRBO empirically performs much better than MRBO (as well as other single-loop momentum-based algorithms MSTSA [22], STABLE [2], and SEMA [11]), as will be shown in Section 4.
We note that although our theory requires Q to scale as Olog at= )), a very small Q is sufficient to attain a fast convergence speed in experiments. For example, we choose Q = 3 in our hyper-cleaning experiments as other benchmark algorithms such AID-FP, reverse, and stocBiO.
4 Experiments
In this section, we compare the performances of our proposed VRBO and MRBO algorithms with the following bilevel optimization algorithms: AID-FP [10], reverse [6] (both are double-loop deter- ministic algorithms), BSA [8] (double-loop stochastic algorithm), MSTSA [22] and SUSTAIN [23] (single-loop stochastic algorithms), STABLE [2] (single-loop stochastic algorithm with Hessian inverse computations), and stocBiO [20] (double-loop stochastic algorithm). SEMA [11] is not included in the list because it performs similarly to SUSTAIN. RSVRB [12] is not included since it performs similarly to STABLE. Our experiments
over hyper-cleaning application MNIST', We provide the detailed experiment specifications in Appendix B.
As shown in Figure 1 (a) and (b), the convergence rate (w.r.t. running time) of our VRBO and the SGD-type stocBiO converge much faster than other algorithms in comparison. Between VRBO and stocBiO, they have comparable performance, but our VRBO achieves a lower training loss as well as
'The experiments CIFARIO are still ongoing.

---

more stable convergence. Further, our VRBO converges significantly faster than all single-loop momentum-bait methods. This provides some evidence on the advantage of double-loop algorithms over single-loop algorithms for bilevel optimization. Moreover, our MRBO achieves the fastest convergence rate among all single-loop momentum-bant our theoretical results. In Figure I (c), we compare our algorithms MRBO and VRBO with three momentum-basee algorithms, i.e., MSTSA, STABLE, and SUSTAIN, where SUSTAIN (proposed in the concurrent work [23]) achieves the same theoretical complexity our MRBO and VRBO. However, it can be seen that MRBO and VRBO are significantly faster than the other three algorithms.
algorithms, which is consistent with
All three plots suggest an interesting observation that double-loop algorithms tend to converge faster than single-loop algorithms as demonstrated by (i) double-loop VRBO performs the best among all algorithms; and (ii) double-loop SGD-type stocBiO, GD-type reverse and AID-FP perform even better stochastic algorithm MRBO; and (iii) double-loop SGD- type BSA (with single-sample updates) converges faster than single-loop momentum-acceleraaeel stochastic MSTSA, STABLE and SUSTAIN (with single-sample updates). Such a phenomenon has been observed only in bilevel optimization (to our best knowledge), and occurs oppositely in minimization and minimax problems, where single-loop algorithms substantially outperform double-loop algorithms. The reason for this can be that the hypergradient estimation at the outer- loop in bilevel optimization is very sensitive to the inner-loop output. Thus, for each outer-loop iteration, sufficient inner-loop iterations in the double-loop structure provides much more accurate output close to y (x) than a single inner-loop iteration, and thus helps to estimate a more accurate hypergradient in the outer loop. This further facilitates better outer-loop iterations and yields faster overall convergence.
than single-loop momentum-acceleratee
NSTEA STAOLE
VRS0
MSISA STAOLE
20
MRBO
Train laka
1kx00 rene
Train loss
15x
Train loss
VRBO
MSTSA
STABLE
SUSTAIN
150
200
1:0
200
running Time
running time 78
running time is
(a) Noise rate 0.1
(b) Noise rate 0.15
(c) Noise rate p 0.1
Figure 1: training loss v.s. running time.
Conclusion
In this paper, we proposed two novel algorithms MRBO and VRBO for the nonconvex strongly- convex bilevel stochastic optimization problem, and showed that their computational complexities outperform all existing algorithms order- wise. In particular, MRBO is the first momentum algorithm that exhibits the order-wise improvement over SGD-type algorithms for bilevel optimization, and VRBO is the first that adopts the recursive variance reduction technique to accelerate bilevel opti- mization. Our experiments demonstrate the superior performance of these algorithms, and further suggest that the double-loop design may be more suitable for bilevel optimization than the single- loop structure. We anticipate that our analysis can be applied to studying bilevel problems under various other loss geometries. We also hope that our study can motivate further comparison between double-loop and single-loop algorithms bilevel optimization.
nonconvex-strongly-
Acknowledgements
The work was supported in part by the U.S. National Science Foundation under the grants ECCS- 2113860, DMS-2134145 and RNS-2112471.
10

---

References
[1] L. Bertinetto, J. F. Henriques, P. Torr, and A. Vedaldi. Meta-lcarning with differentiable closed-form solvers. In International Conference on Learning Representations (ICLR), 2018.
[2] T. Chen, Y. Sun, and W. Yin. A single-timescale stochastic bilevel optimization method. arXiv preprint arXiv: 102.0467 1, 2021.
[3] A. Cutkosky and F. Orabona. Momentum-based variance reduction in non-convex SGD. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[4] 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 (NeurIPS), 2018.
[5] M. Feurer and F. Hutter. Hyperparameter optimization. In Automated Machine Learning, pages 3-33. Springer, Cham, 2019.
[6] I.. Franceschi, M. Donini, P. Frasconi, and M. Pontil. Forward and reverse gradient-base based hyperparameter optimization. In International Conference on Machine Learning (ICML), pages 1 1165-1173, 2017.
[7] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Machine Learning (ICML), pages 1568-1577,
[8] S. Ghadimi and M. Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02224: 2018.
[9] S. Gould, B. Fernando, A. Cherian, P. Anderson, R. S. Cruz, and E. Guo. On differentiating parameterized argmin and argmax problems with application bi-level optimization. arXiv preprint 1001v.160..0544 2016.
[10] R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo. On the iteration complexity of hypergradient computation. In International Conference on Machine Learning (ICML), pages 3748-3758, 2020.
[11] Z. Guo. Y. Xu, W. Yin, R. Jin, and T. Yang. On stochastic moving-average estimators for non-convex optimization. arXiv preprint arXiv:2 104. 14840, 2021.
[12] Z. Guo and T. Yang. Randomized stochastic variance-reduced methods for stochastic bilevel optimization. arXiv preprint arXiv:2 wtt.::2205002266. 2021.
[13] P. Hansen, B. Jaumard, and G. Savard. New branch-and-bound rules for linear bilevel program- ming. SIAM Journal on Scientific and Statistical Computing, 13(5): 194-1277, 1992.
[14] 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 arXiv:2007.05170, 2020.
[15] F. Huang. S. Gao, J. Pei, and H. Huang. Accelerated zeroth order momentum methods from mini to minimax optimization. arXiv preprini arXiv:2008.08 2020.
[16] K. J. D. Lee, Y. Liang, and H. V. Poor. Convergence of meta-learning with task-specific adap- tation over partial parameters. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[17] K. Ji and Y. Liang. Lower bounds and accelerated algorithms for bilevel optimization. arXiv preprint arXiv:2 /02.0392..9...... 2021.
[18] K. Ji, Z. Wang, Y. Zhou, and Y. Liang. Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization. In International Conference on Machine Learning (ICML), pages 3100-3109, 2019.
[19] K. Ji, J. Yang, and Liang. Multi-step model-agnostic meta-learning: Convergence and improved algorithms. arXiv preprint arXiv:2002.07836 2020.

---

[20] K. Ji, J. Yang, and Y. Liang. Bilevel optimization: Nonasymptotic analysis and faster algorithms. In International Conference on Machine Learning (ICML), 2021.
[21] R. Johnson and Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems (NeurIPS), 26:315-323, 2013.
[22] P. Khanduri, S. Zeng. M. Hong. H.-T. Wai, Z. Wang, and Z. Yang. A momentum-assisted single-timescale stochastic approximation algorithm for bilevel optimization. arXiv preprint arXiv:2102.07367V.. 2021.
[23] P. Khanduri, S. Zeng, M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A near-optimal algorithm for stochastic bilevel optimization via double- momble-momentum.. arXiv preprint arXiv:2102.07367, 2021.
[24] V. R. Konda and J. N. Tsitsiklis. Actor-critic algorithms. In Advances in Neural Information Processing Systems (NeurIPS), pages 1008-1011 1014, 2000.
[25] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient- basee learning applied document recognition. Proceedings of the IEEE, 86(11):2278 2324, 1998.
[26] Z. Li and J. Li. A simple proximal stochastic gradient method for nonsmooth nonconvex optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
[27] L.. Luo, H. Ye, Z. Huang, and T. Zhang. Stochastic recursive gradient descent ascent for stochastic comnconve--stronglyyoocec. minimax problems. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[28] D. Maclaurin, D. Duvenaud, and R. Adams. Gradient- baased hyperparameter optimization through reversible learning. In International Conference on Machine Learning (ICML), pages 2113 1112,2122, 2015.
[29] G. M. Moore. Bilevel programming algorithms for machine learning model selection. Rensselaer Polytechnic Institute, 2010.
[30] L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning (ICML), pages 2613-2621, 2017.
[31] F. Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference on Machine Learning (ICML), pages 737-746, 2016.
concave [32] H. Rafique, M. Liu, Q. Lin, and T. Yang. Weakly-convex conccce min-mas optimization: provable algorithms and applications in machine learning. Optimization Methods and Software, pages 1-35, 2021.
[33] A. Rajeswaran, C. Finn, S. M. Kakade, and S. Levine. Meta-leaming with implicit gradients. In Advances in Neural Information Processing Systems (NeurIPS), pages 113-124, 2019.
[34] A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots. Truncated hack-propagation for bilevel optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1723-1732, 2019.
[35] C. Shi, Lu, and G. Zhang, An extended Much--Tucker approach for linear bilevel programming. Applied Mathematics and Computation, 162(1):5 2005.
[36] Q. Tran-Dinh, N. H. Pham, D. T. Phan, and L. M. Nguyen. Hybrid stochastic gradient descent algorithms for stochastic nonconvex optimization. arXiv preprint 1rXiv:1905. 05590, 2019.
[37] Z. Wang, K. Ji, Y. Zhou, Y. Liang, and V. Tarokh. Spiderboost: class of faster variance-reduced algorithms for nonconvex optimization. arXiv preprint 1010::18100106900 2018.
[38] Z. Wang, K. Ji, Y. Zhou, Y. Liang, and V. Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. In Advances Neural Information Processing Systems (NeurIPS), 2019.
[39] Xu, Z. Wang. Y. Liang, and H. V. Poor. Gradient free minimax optimization: Variance reduction and faster convergence. arXiv preprint 20X1v:2006.09361, 2020.
12

---

[40] J. Yang. N. Kiyavash, and N. He. Global convergence and variance reduction for a class of nonconvex cencomnvx-noneoncvvee nonconcave minimax problems. Advances in Neural Information Processing Systems (NeurIPS), 33, 2020.
[41] D. Zhou, P. Xu, and Q. Gu. Stochastic nested variance reduced gradient descent for nonconvex optimization. Advances in Neural Information Processing Systems (NeurIPS), 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Section 4 dissusses that the proposed algorithm MRBO which is based on single-loop structure does not outperform several double-loop based algorithms.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This paper develops new algorithms and establishes the convergence theory for fundamental belivel optimization problem. Our results will not have any potential negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All assumptions are stated in Section 3.1.
(b) Did you include complete proofs of all theoretical results? [Yes] Complete proofs are included in Appendix C and Appendix D.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] The experimental details are specified in Appendix B.
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Figure Scction We ran 5 random seeds for every experiment.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] The details are in included in Appendix B.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work existing assets, did you cite the creators? [Yes] The details included in Appendix B.
(b) Did you mention the license of the assets? [Yes] The details are included in Appendix B.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes]
Our code is public GitHub.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We specify that the dataset we use are public Appendix (e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A] The dataset we use does not contain personally identifiable information, nor offensive content.
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "_fZ4nXw61qo", "reviewer": "Reviewer_5eE2", "summary": "The paper extends to usual algorithms of convex optimization with finite sum to bilevel optimization: SGD with momentum and SVRG. The main contribution of the paper theoretical: authors derive accelerated convergence rates toward the solution of the bilevel problem.\n", "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": "\nTheoretical results are interesting for the bilevel community, although this work does not fix the practical problem of hand-tuned stepsizes.\n\nComments:\n- In algorithm 1 and 2, how do you choose the stepsize s $\\lambda$, $\\gamma$, $\\alpha$ and $\\beta$ in practice. Do you have any insights on how to set in practice? From my experience, algorithms are very sensitive this hyperparameters.\n- How do you select $Q$ in practice? (the size of the \"Neumann serie\")\nFrom my experience it can also have a large influence of the result of the bilevel optimization algorithm.\nHow robust is the algorithm to this parameter?\n- Since computing $\\hat \\nabla \\Phi(x_k, B_k)$ (through (4)) requires an iterative procedure, I think it is misleading to talk about \"single\" loop algorithm for Algorithm 1, and \"double loops\" algorithm for Algorithm 2, do authors agree that the computation of $\\hat \\nabla \\Phi(x_k, B_k)$ add another loop?\n- Authors claim that the proposed techniques are order of magnitude faster than usual algorithms, regarding the experimental results, I would be less assertive.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8h"}, "extra_text": {}}, {"review_id": "Q38hUxQbwcI", "reviewer": "Reviewer_VGzP", "summary": "This paper presents two algorithms (one single-loop and one double-loop) which exploit variance reduction techniques to improve the best known sample complexity for stochastic bilevel optimization problems with strongly convex lower-level from $O(\\epsilon^{-2})$ to  $O(\\epsilon^{-1.5})$. \n\n\nBilevel optimization consists in two nested optimization problems: the upper-level aims at minimizing an objective function where some of the variables are a solution of the lower-level problem. In the stochastic setting, upper and lower-level objectives are not accessible and are instead replaced by unbiased estimators. In addition to several smoothness assumptions, this work and several recent others consider the case when the lower-level problem is strongly-convex, which guarantees that the lower-level solution is unique, the existence of the upper-level gradient, and allows to provide convergence guarantees to stationary points even when the lower-level solution is not computed exactly. \n\nThis work studies two algorithms (MRBO and VRBO) which both achieve a sample complexity of $O(\\epsilon^{-1.5})$, which improves upon the previous optimal complexity of $O(\\epsilon^{-2})$. Both algorithms exploit variance reduction  to achieve the desired complexity. MRBO is single loop and combines variance reduction and momentum while VRBO is double loop and uses large-batch gradients to reduce the variance. Recent works have already applied momentum and variance reduction to solve stochastic bilevel problems but this one is the first (together with two concurrent works) to achieve a sample complexity this low. The authors present experiments on the data hyperclearner setting which show that VRBO performs the best and double-loop algorithms seem to outperform single-loop ones.\n", "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 authors corrected Theorem 1 and 2 with related corollaries in the supplementary. For this reason I will only refer to the restated results of the supplementary.\n\n#### **Originality**\n1. Several works have recently tackled the sample complexity of (stochastic) bilevel optimization with smooth objectives and strongly convex lower-level problem. This work, together with two concurrent ones, is the first that achieves a convergence rate of $\\tilde O(\\epsilon^{1.5})$ using variance reduction techniques. Furthermore, the rate is achieved  with two algorithms (MRBO and VRBO). MRBO is very similar to the concurrent work SUSTAIN [20], while VRBO is the first that combines double-loop and variance reduction.  The contributions are stated clearly and related work is properly cited. \n\n#### **Quality**\n2. The theoretical claims (Corrected in the appendix) seem more or less correct, although I checked just a little part of the proofs also because they were not easy to follow (see major comment 8) and I am not so familiar with variance reduction techniques.\n3.  Drawbacks of the analysis could be discussed more. For example the fact that some parameters like step sizes or batch sizes depend on unknown constants and on the accuracy threshold. Also, I think that adding an additional discussion of the assumptions will be valuable since they seem quite restrictive.\n4. Experimental evaluation is narrow. Only one setting (data hypercleaner) is presented, despite that the strength of  the bilevel framework is that it can be applied to several practical scenarios. The authors could either comment on this in the contributions section or perform experiments on at least another setting like optimizing the regularization hyperparameter. On the positive side, they compare their methods with several others from recent literature.\n\n#### **Clarity**\n5. The main ideas of the paper are easy to grasp for someone acquainted with recent works in bilevel convergence rates. The paper contains numerous typos (see minor comments) and the proofs are quite hard to follow (see major comment 8). The work could also benefit from simple examples of bilevel optimization problems that could make it more accessible to people less familiar with the bilevel setting.\n\n#### **Significance**\n6. Bilevel optimization is becoming more and more relevant in machine learning since many problems like instances of meta-learning and hyperparameter optimization can be cast into this framework. This work develops two principled and efficient algorithms that improve the optimal rate for stochastic bilevel optimization with a strongly convex lower level problem. Although the experimental evaluation is narrow, the results are promising and show the potential advantage of these approaches in practice.\n\n#### **Final Score**\n7. I am giving 6 to the paper but I could increase the score if the authors improve the proofs section in the supplementary, comment more on the drawbacks of the analysis, or improve the experimental section.\n\n\n#### **Major comments**\n8. Proofs (in the supplementary) are quite hard to follow, they contain some typos and several references to lemmas contained in recent related works. I think they need more polishing and at least some referenced lemmas could be written in the supplementary to make it more self-contained. \n9. I think the complexity reported in the abstract and in the contribution should be up to logarithmic terms ($\\tilde O$ instead of $O$) to account for the hessian-vector products, which generally are more expensive than gradients.\n10. This work and related ones lack a more detailed discussion on the assumptions which it looks like they can be too restrictive in some cases unless the optimization problem(s) is over a convex compact set, a setting which this work does not cover. \n11. Since the authors mention concurrent work, it will bring value to the paper to include it not only in lines 131-142 but throughout the manuscript when comparing with related works, for example in Table 1.\n12. I think that the Justification in lines 100-105 is not well supported experimentally. Furthermore, it should not be in the contribution section.\n13. The concurrent methods SUSTAIN [20] and BSA [8] can be also applied with bigger batch sizes, while the authors seem to only consider batch size = 1 for these methods in the experiments (from the provided code). I think it will be good to see the performance of these methods with larger batch sizes. Probably in this case SUSTAIN will be equivalent to MRBO.\n\n\n#### **Minor Comments  and typos**\n14. From Theorem 2 statement it is unclear why the final complexity in Corollary 2 $O(\\epsilon^{1.5})$ holds, probably because the dependence on $\\mathcal{S}_2$ and $q$ is hidden in (12). It seems that the complexity is just $\\tilde{O}(\\epsilon^{-1})$. I do not know if there is a simple way to make it more clear.\n15. Experiments could be better detailed in the appendix by specifying what metric is used to fine-tune the parameters for best performance and what kind of CPU is used.\n16. I think adding some plots with the number of samples on the x axis to have results which are independent of the particular implementation and hardware can add value to the paper.\n17. Contribution section could be shorter by removing some details.\n18. Line 203. I think Assumption 1 should not include $\\Phi$ being non-convex. The results would hold also for convex $\\Phi$.\n19. Assumption 2 requires everything to be uniform also w.r.t. the random variables. This may be commented on because it is not present in works which instead do not use variance reduction.\n20. VRBO (Algorithm 2) could be written more clearly since it seems that uses different $\\tilde x$-s inside the $t$ for loop but then writes $\\tilde x_{k,t+1} = \\tilde x_{k,t}$. It would be clearer if $\\tilde x $ had only the $k$ subscript.\n21. I would change “by the order of magnitude” in line 72.\n22. Line 87 “periodically at each outer loop” is unclear.\n23. Line 92: unclear what “Hessian-vector type” means.\n24. Line 100: “outer-loop estimation”?\n25. Line 101: “inner loop output y” not clear, i would remove “y”.\n26. Line 109: “to further simplify the implementation”?\n27. order-wisely -> order-wise at lines 115, 174, 350.\n28. equations (2) and (3) could be with $x$ instead of $x_k$. Furthermore in (3) the last product could probably be replaced by an exponent since the index $j$ is not used.\n29. Line 231 “of dataset” can be removed\n30. Line 239: “one step iteration” -> “one iteration”\n31. whether -> when at line 68.\n\n#### **Post Rebuttal**\nThe authors have properly addressed my concerns and claimed to make several (quite straightforward) modifications for the next version of the paper. Thus I am increasing the score from 6 to 7. \n\n\n#### **References**\n[8] S. Ghadimi and M. Wang. Approximation methods for bilevel programming.arXiv preprint376arXiv:1802.02246, 2018.\n\n[12] Z. Guo and T. Yang. Randomized stochastic variance-reduced methods for stochastic bilevel386optimization.arXiv preprint arXiv:2105.02266, 2021.\n\n[19] P. Khanduri, S. Zeng, M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A momentum-assisted single-timescale stochastic approximation algorithm for bilevel optimization. arXiv preprint arXiv:2102.07367v1, 2021.\n\n[20] Khanduri, P., Zeng, S., Hong, M., Wai, H.-T., Wang, Z., and Yang, Z. (2021). A near-optimal algorithm for stochastic bilevel optimization via double-momentum.arXiv preprint arXiv:2102.07367\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Unaddressed limitation are at point 3 of the main review.\n\nThe authors justify the absence of a discussion about potential negative societal impact writing in the checklist that the nature of the work is theoretical. I agree with the authors.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "K2R7bOGAWqk", "reviewer": "Reviewer_YFpX", "summary": "The authors developed two algorithms MRBO and VRBO for  bilevel stochastic optimization problem, and showed that their computational complexities ($\\mathcal{O}(\\epsilon^{-1.5})$) outperform all existing algorithms ($\\mathcal{O}(\\epsilon^{-2})$) orderwisely. The authors claim two main contributions. First, MRBO is the first momentum algorithm that exhibits the orderwise improvement over SGD-type algorithms for bilevel optimization. Second, VRBO is the first that adopts the recursive variance reduction technique to accelerate bilevel optimization. Their experiments demonstrate that these algorithms  outperform existing algorithms, and suggest that the double-loop design may be more suitable for bilevel optimization than the single loop structure.", "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": "Originality: \nThe authors proposed two new algorithms for solving stochastic bilevel optimization program: MRBO is the first momentum algorithm that exhibits the orderwise improvement over SGD-type algorithms for bilevel optimization; VRBO is the first that adopts the recursive variance reduction technique to accelerate bilevel optimization. Both of these two algorithms improve the computational efficiency by a order of $\\mathcal{O}(\\epsilon^{0.5})$.\n\n\nQuality: \nBoth algorithms are supported with proofs of convergence guarantees. Also, experiments on simple MNIST tasks are conducted to demonstrate the superior performance of the proposed algorithms.\n\nClarity: \nThis paper is well-organized and  provides clear statements of algorithms and proofs.\n\nSignificance: \nBilevel optimization is an important tool for many ML tasks such as hyperparameter tunning. However, it is also well-know solving Bilevel optimization program is NP-hard. This paper proposes two algorithms that are well suited for a class of such programs.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Although the proposed algorithms are demonstrated in simple MNIST tasks, more experiments on large scale data (e.g., CIFAR or ImageNet) are necessary to further valid the computational efficiency.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours "}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers unanimously agree that this is a paper of high originality and soundness of the results. Some reviewers have raised concerns over inflated claims in light of experimental validation (5eE2, VGzP), as well clarity of the proofs and discussion of the limitations (VGzP). After a strong rebuttal and engaging in discussion with the authors, the reviewers have found that the authors have addressed their remark, and some reviewers increased their score.
Decision: Accept (Spotlight)