Will Bilevel Optimizers Benefit from Loops
Authors: Kaiyi Ji
Mingrui Liu
Yingbin Liang
Lei Ying
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bilevel optimization
unified convergence analysis
optimization loops
lower bound.

Abstract: Bilevel optimization has arisen as a powerful tool for solving a variety of machine learning problems. Two current popular bilevel optimizers AID-BiO and ITD-BiO naturally involve solving one or two sub-problems, and consequently, whether we solve these problems with loops (that take many iterations) or without loops (that take only a few iterations) can significantly affect the overall computational efficiency. Existing studies in the literature cover only some of those implementation choices, and the complexity bounds available are not refined enough to enable rigorous comparison among different implementations. In this paper, we first establish unified convergence analysis for both AID-BiO and ITD-BiO that are applicable to all implementation choices of loops. We then specialize our results to characterize the computational complexity for all implementations, which enable an explicit comparison among them. Our result indicates that for AID-BiO, the loop for estimating the optimal point of the inner function is beneficial for overall efficiency, although it causes higher complexity for each update step, and the loop for approximating the outer-level Hessian-inverse-vector product reduces the gradient complexity. For ITD-BiO, the two loops always coexist, and our convergence upper and lower bounds show that such loops are necessary to guarantee a vanishing convergence error, whereas the no-loop scheme suffers from an unavoidable non-vanishing convergence error. Our numerical experiments further corroborate our theoretical results.

University at Buffalo edu Will Bilevel Optimizers Benefit from Loops
Kaiyi Ji Department CSE
Mingrui Liu Department of CS George Mason University mingruil langruil@@mu.. edu
Yingbin Liang Department of ECE The Ohio State University l Liang. 8890osu. edu
Lei Ying Department of EECS University of Michigan leiying@umich ch. edu
Abstract
Bilevel optimization has arisen powerful tool for solving variety of machine learning problems. Two current popular bilevel optimizers AID-BiO and ITD-BiO naturally involve solving
two sub-profe sob-problems, and consequently, whether we solve these problems with loops (that take many iterations) or without loops (that take only few iterations) significantly affect the overall computational efficiency. Existing studies in the literature cover only some of those implemen- tation choices, and the complexity bounds available are not refined enough enable rigorous comparison among different implementations. In this paper, we first establish unified convergence analysis for both AID-BiO and ITD-BiO that are applicable to all implementation choices of loops. We then specialize our results to characterize the computational complexity for all implementations, which enable an explicit comparison among them. Our result indicates that for AID-BiO, the loop for estimating the optimal point of the inner function is beneficial for overall efficiency, although it causes higher complexity for each update step, and the loop for approximating the outer-level ent complexity. For ITD-BiO, the two loops always coexist, and our convergence upper and lower bounds show that such loops are necessary to guarantee vanish- ing convergence error, whereas the no-loop scheme suffers from unavoidable non- non-vanis convergence error. Our numerical experiments further corroborate our theoretical results.
-iw-rne--veettoe product reduces the gradi-
Introduction
Bilevel optimization has attracted significant attention recently due to its popularity in variety of machine learning applications including meta-learning 9
34
17 hyperparameter optimization (9]
35 (, reinforcement learning [22] [5). and signal processing (3 In this paper, we consider the
bilevel optimization problem that takes the following formulation.
min (xx) == [(x, y1 (1:) S.t. y (ar) = arg min (x, ZERP
yERv
where the outer- and inner-level functions f and are both jointly continuously differentiable. We focus the setting where the lower-level function g strongly convex with respect to (w.r.t)) with the condition number x = I. (where I. and are gradient Lipschitzness and strong convexity coefficients defined respectively in Assumptions I and 3 in Section 3). and the outer-level objective function (xr) is possibly nonconvex w.r.t. æ. Such types of geometries arise in many applications
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Comparison of computational complexities of four AID-BiO implementations for finding an c-accurate stationary point. For a fair comparison, gradient descent (GD) is used to solve the linear system for all algorithms. (C(c): the total number of Jacobian- and Hessian product
computations. Gc(c): the total number of gradient computations. O: hide In factors. We write a(x) = ((b(z)) if cb(z) < a(x) < Cb(r)), where C' are universal constants.
Algorithms
Q
MV(e)
Gc(c)
BA 10
(n
(c+11)
(k: iteration number)
Ö(N
0(15c-1.25)
AID-BiO 19
O(n'c()
O(N't=))
N-Q-loop AID (this paper)
(n))
O(x'c=)
O(N'c
Q-loop AID (this paper)
1
Ō(n²(
N-loop AID (this paper)
O(1)
(x)
Ö(xtE
E(x'ctt)
No-loop AID (this paper)
O(1)
1
Ö(K7E-1)
Ö(n9E-1)
including meta-learning (which uses the last layer of neural networks as adaptation parameters), hyperparameter optimization (e.g., data hyper-cleaning and regularized logistic regression) and learning in communication networks (e.g., network utility maximization).
A variety of algorithms have been proposed solve the bilevel optimization problem in eq. ( For example, [14] 36, 32] proposed constraint- based approaches by replacing the inner-level problem with its optimality conditions constraints. In comparison, gradient-based bilevel algorithms have received intensive attention recently due to the effectiveness and simplicity, which include two popular approaches via approximate implicit differentiation (AID) 433 11 19] and iterative differentiation (TTD) 31 g 35.. Readers can refer to Appendix A for an expanded list of related work.
Consider the AlD-based bilevel approach (which we call AID-BiO). Its base iteration loop updates the variable x until convergence. Within such a base loop, it needs to solve two sub-problems: finding nearly optimal solution of the inner-level function via N iterations, and approximating the outer-level Hessian dlesssan--nvvese-e-e vector product via Q iterations. If Q and N are chosen to be large, then the corresponding iterations form additional loops of iterations within the base loop, which we respectively call as Q-loop and N N-loop. Thus, AID-BiO can have four popular implementations depending different choices of N and Q: N-loop (with large N x In i. and small Q = 0(1)), N-Q-loop (with large N = (x: k)) and large Q = Ok In k)), Q-loop (with N = and Q = and Q = O(1). Note that No-loop refers to additional
(k In k)), and No-loop (with N loops within the base loop, and can be understood as conventional These implementations can significantly affect the efficiency of AID-BiO. Generally, large Q (i.e., Q-loop) provides a good approximation of the Hessianniinverse-ecttn product for the hypergradient computation, and large N (i.e., a N-loop) finds an accurate optimal point of the inner function. Hence, an algorithm with N-loop and Q-loop require fewer base-loop steps to converge, but each such base-loop step requires more computations due these loops. On the other hand, small Q and/or N avoid computations of loops in each base-loop step, but can cause the algorithm to converge with many more bose-loop steps. An intriguing question here is which implementation is overall most efficient and whether AID-BiO benefits from having N-loop and/or Q-loop. Existing theoretical studies on AID-BiO are far from answering this question. The studies [0 19 on deterministic AID-BiO focused only on the N N-Q-loop scheme. A few studies analyzed the stochastic AID-BiO, such as 26) on No-loop, and 15 21l on Q-loop. Those studies were not refined enough to capture the computational differences among different implementations, and further those studies collectively did not cover all the four implementations either.
gegle-(base)-oogy algorithms.
The first contribution of this paper lies in the development of a unified convergence theory for AID-BiO, which is applicable to all choices of N and Q. We further specialize our general theorems to provide the computational complexity for all of the above four implementations (as summarized in Table Comparison among them suggests that AID-BiO does benefit from both N Noloop and Q-ooop. This is in contrast to minimax optimization (a special case of bilevel optimization), where it shown in 27 41 that (No-loop) gradient descent ascent (GDA) with N = often outperforms (N-loop) GDA with N = k (here N denotes the number of ascent iterations for each descent iteration). To explain the reason, the gradient

---

Table 2: Comparison of computational complexities of two ITD-BiO implementations for finding an c-accurate stationary point. For a fair comparison, gradient descent (GD) is used to solve the inner-level problem. The analysis in [9] for ITD-BiO assumes that the inner-loop minimizer y" (æx) is bounded at kth iteration, which is not required in our analysis. jr: the strong-convexity constant of inner-level function g(z,,). For the last two columns, 'N/A' means that the complexities to achieve an e-accuracy are not measurable due to the nonvanishing convergence error. We write a(z) = ()((x)))
a(x) > cb(x), where e is a universal constant.
Algorithms
N ((xlux)
Convergence rate
MV(e)
Ge(e)
ITD-BiO 19]
+e
O(N'E-) Ō(N²E=1) N/A
O(N''
N-N-loop ITD (this paper)
@(xIxx)
o
tc x
Ō(N'E=1)
No-loop ITD (this paper)
@(1)
x
N/A
Lower bound (this paper)
@(1)
(2xx2)
N/A
N/A
w.r.t. x in bilevel optimization involves additional second-order derivatives (that do not exist in minimax optimization), which are more sensitive the accuracy of the optimal point of the inner function. Therefore, a large N finds such a more accurate solution, and is hence more beneficial for bilevel optimization than minimax optimization.
Differently from AID-BiO, the ITD-based bilevel approach (which we call as ITD-BiO) constructs the outer-level hypergradient estimation via backpropagation along the Nolo iteration path, and Q = N always holds. Thus, ITD-BiO has only two implementation choices: NNN-llop (with large N = ri In k) and No-loop (with small N (1)). Here. N-N-loop and No-loop also refer to additional loops for solving sub- nub-problems within the ITD-BiO's s base loop of updating the variable
r. The only convergence rate analysis on ITD- -iiO was provided in [99 but only for N-N-loop.
which does not suggest how N-N-loop compares with No-loop. It is still an open question whether ITD-BiO benefits from N-loops.
The second contribution of this paper lies in the development of unified convergence theory for ITD-BiO, which is applicable to all values of N. We then specialize our general theorem to provide the computational complexity for both of the above implementations (as summarized in Table 2 We further develop convergence lower bound, which suggests that N-N-looy is necessary to guarantee a vanishing convergence error, whereas the no-loop scheme suffers from an unavoidable non-vanishing convergence error.
The technical contribution of this paper is two-fold. For AID methods, most existing studies including 19 solve the linear system with large Q O(x log x) so that the upper-level Hessian-inverse-vettn allow arbitrary (possibly small) Q, and
vanish. In contrast, hence this upper-level error can be large and nondecreasing, posing key challenge to guarantee convergence. We come up with a novel idea to prove the convergence by showing that this error, not by itself but jointly with the inner-loop error, admits an (approximately) iteratively decreasing property, which bounds the hypergradient error and yields convergence. The analysis contains new developments to handle the coupling between this error and the inner-loop error, which is critical in our proof. For ITD methods, unlike existing studies including [19, we remove the boundedness assumption on y" (z) via a novel eтror analysis over the entire execution rather than single iteration. Our analysis tools are general and can be extended to stochastic and acceleration bilevel optimizers.
product approximation error
2 Algorithms
2.1 AID-based Bilevel Optimization Algorithm
As shown in Algorithm I we present the general AlD-based bilevel optimizer (which we refer to AID-BiO for short). At each iteration à: of the base loop, AID-BiO first executes N steps of gradient decent (GD) over the inner function g(x, y) to find an approximation point y where N can be chosen either at a constant level or as large as N = x In k. (which forms an Noloop of iterations). Moreover, to accelerate the practical training and achieve stronger performance guarantee AID-BiO
3

---

Algorithm AlD-based bilevel optimization (AID-BiO) with double warm starts
1: Input: Stepsizes 0 >> O, initializations zo, yo, Vo-
2: for k 2, .... K do
Set y2 yk & and yo otherwise (warm start initialization)
4: for t= 1,.... .N do
5: Update vi vi 1--1 aV V
6: end for
7:
Hypergradient estimation via:
Set vgg 2 if > 0 and to otherwise (warm start initalization).
Solve eg from (zx ve D VuJ ui') via Q steps of iterative algorithms starting from ee Compute (xxx)) = V (=z, u V. Vyg(zx, ve )o
8: Update 2k+1 = 26 (T()
9: end for
often adopts warm-starr strategy by setting the initialization ye of each N-loop to be the output y of the preceding N N-loop rather than random start.
To update the outer variable, AID-BiO adopts the gradient descent, by approximating the true gradient (+(()) of the outer function w.r.t. (called hypergradient [33 IT] that takes the following form:
(True hypergradient:)
(+()))
y' (sre) (
V V Vgl y (xx))
where of is the solution of the linear system Vzgg(x. (zt))o= V (= y" (xx)). To approximate the above true hypergradient, AID-BIO first solves vf as approximate solution to linear system (5 v/ Je V vyJ (x*, vi using Q steps of GD iterations starting from vg. Here, Q can also be chosen either at a constant level or as large as Q x In E (which forms a Q-loop of iterations).
Note that a warm start is also adopted here by setting of u which is critical to achieve the convergence guarantee for small Q. If Q is large enough, e.g., at an order of kln ft. a zero initialization with 2 0 suffices to solve the linear system well. Then, AID-BiO constructs hypergradient estimator (*x)) given by
(AIDD-based hypergradient estimate:)
V V vx V. V ( Dk Jug
Note that the execution of AID-BiO involves only Hessian-vector products in solving the linear system and Jacobian-vector product V, VyVggrr y yu{ which are more computationally tractable than the calculation of second-order derivatives.
clear that different choices of N and Q lead four implementations within the base loop of AID-BiO: N-loop (with large N = x In k. and small Q (()), N-Q-loop (with large N = x In K and Q In x), Q-loop (with small N and Q O()). In Section we will establish a unified convergence theory for AID-BiO applicable all its implementations in order to formally compare their computational efficiency.
and large Q - x In x) and No-loop (with small N = 1
2.2 ITD-Based Bilevel Optimization Algorithm
As shown in Algorithm 2 the ITD-based bilevel optimizer (which refer ITD-BiO) updates the inner variable similarly to AID-BiO, and obtains the N-step output y of GD with warm-start initialization. ITD-BiO differentiates from AID-BiO mainly in its estima- tion of the hypergradient. Without leveraging the implicit gradient formulation. ITD-BiO com- putes a direct derivative )f(zcv(() via automatic differentiation for hypergradient approximation. drs Since y has dependence on ae through the N-loop iterative GD updates, the execution of ITD-BiO takes the backpropagation over the entire N-loop trajectory. To elaborate, can be shown via the chain rule that the hypergradient estimate 0f(*).y)) takes the following form drt
of af(r Vef(xs, v a D V. VgVgg( 2i [I a of vi) V vff((x, , vi ). As
aza
shown in this equation, the differentiation does not compute the second-orde derivatives directly but compute more tractable and economical Hessian products v2 Vig(zs, vi. J), = I,....N

---

Algorithm 2 ITD-based bilevel optimization algorithm (ITD-BiO) with warm start
1: Input: Stepsize 0. initializations and yo
2: for 0,, 1, .... do
and yo otherwise (warm start initialization) 4: for (= 1, 1,..... .N do
Set yl V4
5: Update y Uk 1-11
aV aV V
6: end for
7: Compute (xx)))= = 01(2 via backpropagation w.r.t. 2%
Update 2k+1 21 - (x
9: end for
(similarly for Jacobian-vector products), where each Bj is obtained recursively via U5-1 (I - (V-aV]g(zm vin J), with uN Vyfffmm v
Clearly, the implementation of ITD-BiO implies that = Q always holds. Hence, ITD-BiO takes only two possible architectures within its base loop: N-N-loop (with large N = k In ) and No-loop (with small N = 1). Section 5 we will establish unified convergence theory for ITTD-ii applicable to both of its implementations in order to formally compare their computational efficiency.
Definitions and Assumptions
This paper focuses on the following types of objective functions. Assumption 1. The inner-level function g(z, y) is p-stronglyycomwe conver w.z.t y-
Since the objective function ((x) in eq. ( is possibly nonconvex, algorithms are expected to find an e-accurate stationary point defined as follows.
Definition 1. We say an e-accurate stationary point for the bilevel optimization problem given in eg. if (=) [2] < where E is the output of an algorithm.
In order to compare the performance of different bilevel algorithms, we adopt the following metrics of computational complexity.
Definition 2.
Let Gc(E) be the number of gradient evaluations, and MV be the total number of Jacobian- and Hession-vector product evaluations to achieve an e-accurate stationary point of the bilevel optimization problem in eq. ①
Let (x, y). We take the following standard assumptions, also widely adopted by 10 Assumption 2. Gradients (z) and Vg(z) are L-Lipschitz. i.e., for any 2, 2,
[V - fz')ll s L||2 - =/11- [Vg(z) Vg(=') S L||z - -='-
As shown in eq. 2). the gradient of the objective function ((x) involves the second-order derivatives
V. V.,V, Vu)(() and (2)( The following assumption imposes the Lipschitz conditions such higher- order derivatives, as also made in [0)
Assumption 3. Suppose the derivatives V (z)(2) and (zg(2) are p-Lipschitz, for any z,
V vvV2)) V. V.V v.)(()))) - 2 [V)((2 - {)'('') = p|| -
To guarantee the boundedness the hypergradient estimation error, existing works 100 17 | assume that the gradient V (z)z) is bounded for all = (z, Instead, we make a weaker boundedness assumption the gradients V 5² (x)).
Assumption 4. There exists constant M such that for any v < M.
For the case where the total objective function (--) has some benign structures, e.g., convexity or strong convexity, Assumption can be removed by an induction analysis that iterates are bounded in 18]. Assumption can also be removed by projecting z onto a bounded constraint set X.
5

---

4 Convergence Analysis of AID-BIO
AID-BiO have four possible implementations depending on whether N and Q are chosen to be large enough to form an Noloopp and/or Q-loop. In this section, we will provide the convergence analysis and characterize the overall computational complexity for all of the four implementations, which will provide the general guidance on which algorithmic architecture computationally most efficient.
As we describe in Section 2.1
4.1 Convergence Rate and Computational Complexity
In this subsection, we develop two unified theorems for AID-BiO, both of which are applicable to all the regimes of N and Q. We then specialize these theorems to provide the complexity bounds (as corollaries) for the four implementations of AID-BiO. It turns out that the first theorem provides tighter complexity bounds for the implementations with small Q (1), and the second theorem provides tighter complexity bounds for the implementations with large Q = k In " Our presentation of those corollaries below will thus focus only on the tighter bounds. The following theorem provides our first unified convergence analysis for AID-BiO BiO.
Theorem 1. Suppose Assumptions 7 2 and 4 hold. Choose parameters a, and X such that
(1 + 2)(1 - aa4) (11 + r(1 +1+ mp < - TI,, where r = O(2 with Cq = =0((1 nu) 22 +
1- 1=(=-n))(1+ + (1 (1 ) Let Lg = =(12) be the smoothness parameter of ((). Let
w 0 nus"
x²
(1 nu
)) Choose such that / min
{
L. v TE
1
VTE Then,
np
n²
K-1
[D((x))12 = 0( (((z)) ((x))
x²1 x²11bol' + 3M + x²)
(4)
3K
Muk
The complete version of Theorem with full parameter specifications can be found in Appendix H Theorem [ also elaborates the precise requirements on the stepsizes 1) and / and the auxiliary parameter X, which take complicated forms. In the following, by further specifying these parameters, we characterize the complexities for AID-BiC ID-BiO in more explicit forms. We focus on the implemen- tations with Q (11) (for which Theorem ! specializes to tighter bound than Theorem 2 below), which includes the N N-loop scheme (with N = (K in k:) and the No-loop scheme (with N = 1).
Corollary 1 (N-loop). Consider N N-loop AID-BiO with N =(( and Q ( where 1 denotes the condition number of the inner problem. Under the same setting of Theorem 1
choose 1) +. +. and X 1. Then, we have t _K=1 [[ 0 xxx + ) and the complexity to achieve an e-accurate stationary point is Gc(e) = 0 ) (V(c) = (1²
Corollary 2 (No-loop). Consider No-loop AID-BiO with N = and Q = 6(1) Under the same بy 2 and n min 1 ax² a 1 }- Then,
setting of Theorem choose parameters a 1 A=
128 Q=LZ
pQ
# =KK [[ 0 + )) and the complexity is Ge(e) ()),,,)),,)))) MV(e) = -'
The analysis of Theorem [ can be further improved for the large Q regime, which guarantees a sufficiently small outer-level approximation error, and helps relax the requirement on the stepsize n-- Such an adaptation yields the following alternative unified convergence characterization for AID-BiO, which is applicable for all Q and N, but specializes tighter complexity bounds than Theorem in the large Q regime. For simplicity, we set the initialization eft = 0 in Algorithm !
Theorem Suppose Assumptions 7 Band hold. Define = @(1 - ap) (1 (1+++1++--))) " C3) x²) 3²2)) w @ (10(11 (x² C1 >>>))))),, where Co is a positive constant defined as in
Theorem 7 Choose parameters a, B such that T < and BT. + w0 + +.3T)) S hold. Then,
the output of AID-BiO satisfies
K-1
(((z)) (xx))
80 K -
Σ K=
(+x)))
+ x2 m1))2
K
3K
where 80 ((22 + C3) a1p)
1 1lvō yoll?) is the initial distance.
The complete version of Theorem 2 with full parameter specifications can be found in Appendix K We next specialize Theorem 2 to obtain the complexity for two implementations of AID-BiO with

---

Q = (nk N- N-Q-loop (with N (x ln k)) and Q-loop (with N = 1), as shown in the following two corollaries. For each case, we need to set the parameters X, 17 and a in Theorem 2 properly.
Corollary 3 (N-Q-loop). Consider N N-Q-loop AID-BiO with N = (K(lk)) and Q = @ 2).
Under the same setting of Theorem choose = a = + X = and = O "). Then, R Ex=D [[ 0 + +c), and the complexity is Ge(c) O MV(() (
Corollary (Q-loop). Consider Q-loop AID-BiO with N = and Q ((x )) Under the same setting of Theorem choose = 1) L. X 2 and B = 0(x Then, * Ekso [V
0 K K + c), and the complexity is Ge(e) O(k²6 MV(c) = 0(x
4.2 Comparison among Four Implementations
vs N = k In k)). We fix Q, and compare how the choice of N affects the computational complexity. First, let Q = @)),, and compare the results between the two implementations Noloopp with (x In k) (Corollary | and No-loop with N = (Corollary D Clearly, the N-loop scheme significantly improves the convergence rate of the No-loop scheme from O K to O(2)), ), and improves the matrix- and gradient complexities from =(K and Ô to O(w4e-1 -1 and (1)5e-1), respectively. To explain intuitively, the hypergradient estimation involves coupled error 7 "lle -y" (ax)) induced from solving the linear system Vag(za, yx )u vf v with stepsize 1). Therefore, a smaller inner-level approximation error llvi y (x=)]] allows a more aggressive stepsize 17, and hence yields faster convergence rate as well as lower total complexity, as also demonstrated in our experiments. It is worth noting that such a comparison is generally different from that in minimax optimization (27] 41), where alternative (i.e., No-loop) gradient descent ascent (GDA) with N = outperforms (N-loop) GDA with N = k in K. where N denotes the number of ascent iterations for each descent iteration. To explain the reason, in constrast to minimax optimization, the gradient w.r.t. x in bilevel optimization involves additional recond-order derivatives, which are more sensitive to the inner-level approximation error. Therefore, larger N is more beneficial for bilevel optimization than minimax optimization. Similarly, we can also fix Q = (xx In x); the N N-Q-loop scheme with N = k (Corollary 3 significantly outperforms the Q Qoloop scheme with N = (Corollary 4 in terms of the convergence rate and complexity.
Impact of N-loop (N
Impact of Q-loop (Q = 1 vs Q (x )) We fix N, and characterize the impact of the choice of
Q on the complexity. For N = 1, comparing No-loop with Q = ((1) in Corollary [add Q-loop with Q Oxx In x) in Corollary 4 shows that both choices of Q yield the same matrix-vect -vector complexity
E 1)), but Q-loop with a larger Q improves the gradient complexity of No-loop with Q = (())
from c() to c1) A similar phenomenon can be observed for N = O In k) based on the comparision between N N-Q-loop in Corollary 3 and Nolooop in Corollary [
In deep learning. Also note that in the setting where the matrix- vector complexity dominates the gradient complexity, e.g., in deep learning, such two choices of Q do not affect the total computational complexity. However, smaller Q can help reduce the per-iteration load on the computational resource and memory, and hence is preferred in practical applications with large models.
Comparison among four implementations. By comparing the complexity results in Corollaries D
3 and it can be seen that N N-Q-loop and N-loop (both with large N Ox In x)) achieve the best mautrix-vector complexity Ö(Nte )) whereas Q-loop and No-loop (both with a smaller N 1) require higher matrix- vector complexity of Ō(r:9c-1). Also note that N-Q-loop has the lowest gradient complexity. This suggests that the introduction of the inner loop with large N can help to reduce the total computational complexity.
Convergence Analysis of ITD-BIO
In this section, we first provide a unified theory for ITD-BiO, which applicable for all choices of N, and then specialize the convergence theory to characterize the computational complexity for the two implementations of ITD-BiO: No loop and N-N-loop. We also provide a convergence lower bound to justify the necessity of choosing large N to achieve vanishing convergence error. The following theorem characterizes the convergence rate of ITD-BiO for all choices of N.
7

---

Theorem 3. Suppose Assumptions 1 and hold. Define = 6 x² -mp AN + and
(AN+ ++++N2(1--0)) (444)) o4p) + w&x, where AN and uN are given by An = a- (1 -ر A (1 z(1))
" "i
WNN
@ ((1 a(1-(1-ap)) 4 all (1 (1--(1-p)) # (1 exl) 2 -). Choose parameters such that B jou
2
21 and BL. + au (2 + BLx ) u0 3. where La ((x²) denotes the smoothness parameter of (.). Then, we have
K-1 [+ =0 Ao
-Ag
(1-apl) opp)))
M2 (ap)))) axj) 1.2 app
+
(5)
3K
2²k
H
where A4 = 2 (x)) - ming (z) and A, = l1y0 y (xo))l?
The complete version of Theorem 3 with full parameter specifications can be found in Appendix N In Theorem 3 the upper bound on the convergence rate for ITD--iO contains convergent term
((²) (which converges to zero sublinearly with K) and an error term O M (1-wu) (which is independent of K, and possibly non-vani vanishinn if N is chosen to be small). To show that such a possibly non-vanishing error term (when N is chosen be small) fundamentally exists, we next provide the following lower bound on the convergence rate of ITD-BiO.
Theorem 4 (Lower Bound). Consider the ITD-BiO algorithm in Algorithm 2 with a S 1. Le and N S O(1), where Lg is the smoothness parameter of ((x). There exist objective functions f(z,y) y) and g( 3) that satisfy Assumptions 1 2 and such that for all iterates IK (where K Z 1) generated by ITD-BiO in Algorithm
3
such
V (F
1.
-ap) 2NN
Clearly, the error term in the upper bound given in Theorem matches the lower bound given in Theorem in terms of Mr2 future efforts to address. Theorem 3 and Theorem 4 together indicate that in order to achieve an e-aceurate stationary point, N has be chosen as large as N + log =). This corresponds to the N----lop implementation of ITD-BiO, where large N achieves a highly accurate hypergradient estimation each step. Another No-loop implementation chooses a small constant-level N ((1) to achieve an efficient execution per step, where a large N can cause large memory usage and computation cost. Following from Theorem and Theorem 4 such No-loop implementation necessarily suffers from a non-vanishing error.
2²² (1 au))2, and there is still a gap on the order of op,, which requires
In the following corollaries, further specialize Theorem 3 to obtain the complexity analysis for ITD-BiO under the two aforementioned implementations of TTD-BiO.
Corollary (N (N-N-loop). Consider N-N-loop ITD-BiO with = O(x (). Under the same set-
ting of Theorem 3 choose min
3L 2τ. Then, 1 Ek=o [V((x))]2 0(* R + +e), and the complexity Ge(e) = ( MV(E) = -0xx)-1)
K KK1
In F), we can guarantee that ITD-BiO converges to an e-accurate stationary point, and the gradient and matrix-vector product complexities are given by O(n²t-1). We note that [19] also analyzed the ITD-BiO with N ( In ?), and provided the same complexities as our results in Corollary 5 In comparison, our analysis has several differences. First, [19] assumed that the minimizer y (zx) at the t iteration is bounded, whereas our analysis does not impose this assumption. Second, [19] involved an additional error term 1. M2
Corollary 5 shows that for a large N (xx
max;=1,....K K |ly" (xx)
which can be very large (or even unbounded) under standard We next characterize the convergence for the small N = =(1).
Assumptions 2 3 and 4
Corollary 6 (No-loop). Consider No-loop ITD-BiO with N = ((). Under the same setting of
Theorem
choose stepsizes
2NL and 3 min 40w
BL Then, we have
1 +E K
[ O 8 M²
k=
agp
Corollary 6 indicates that for the constant-level N = @(1), the convergence bound contains a
non-vanishing error O M²42). As shown in the convergence lower bound in Theorem 4 under

---

standard Assumptions 1 and such an error is unavoidable. Comparison between the above two corollaries suggests that for ITD-BiO, the N-N-loop necessary to guarantee a vanishing convergence error, whereas No-loop necessarily suffers from non-vanishing convergence error.
Empirical Verification
Experiments on hyperparameter optimization MNIST. We first conduct experiments to verify our theoretical results in Corollaries L consider the following hyperparameter optimization problem.
and on AID-BiO with different implementations. We
Σ (A(w:)) X 211113))
min (inn())
Σ L(w,:E), s.t. w arg min REDia
vDval
(Dul EED,
where Dir and Deal stand for training and validation datasets, L(w; denotes the loss function induced by the model parameter w and sample ç, and À > O denotes the regularization parameter. The goal to find a good hyperparameter À to minimize the validation loss evaluated at the optimal model parameters for the regularized empirical risk minimization problem.
A-1 O-20
N-20
O+20 N-1 No:00
0-20, N
Qu1, Ni.0
Training 02
Tost
1000
1500
1000
1500
Running Time
Running Time
Figure 1: Training & test losses v.s. time (seconds) by AID-BiO on MNIST with different Q and N.
From Figure 1 we can make the following observations for AID-BiO. First, the learning curves with 1, indicating that running multiple steps of
N = 20 are significantly better than those with gradient descent in the inner loop (i.e., N > 1) is crucial for fast convergence. This observation is consistent with our complexity result that N-loop is better than No-loop, and N NNQ--lop is better than Q-loop, as shown in Table [ The reason is that more accurate hypergradient estimation can accelerate the convergence rate and lead to a reduction on the Jacobian- and Hessian- computational complexity. Second, N NNQ-llopp (N 20, achieve a comparable convergence performance, and a similar observation can be made for Q-loop (N 1, 20) and No-loop (N 1, Q 1). This is also consistent with the complexity result provided in Table where different choices of Q do not affect the dominant matrix-vector complexity.
20) and N-loop (N 20. Q 1)
25
N-50
0-50NN500
20
20
Training
16
10
10
1000 2000 3000 6000 5000 6000 Time
7000
1000 2000 3000 4000 5000 6000
7000
Time
Figure 2: Training & test losses v.s. time (seconds) by AID-BiO on MNIST with different Q and N.
In Figure 2 we plot the training and test losses versus running time AID-BiO, where we consider hyperparameter optimization problem on MNIST as in Figure [ and choose loop sizes Q and N from (1, (0, Similarly to Figure it can observed that the empirical results in Figure are also in consistence with our theoretical results in Table

---

N=1 N-20
N-1 N-20
14
-2
Training 10
Test
2000 4000
2000
4030
6000
Figure 3: Training & test losses v.s. time (seconds) by ITD-BiO on MNIST with different N.
In Figure we plot the performance of ITD-BiO with different choices of from {1,20) on the hyperparameter optimization MNIST. Figure 3 illustrates that N-loop ITD-BiO (i.e., N=20) converges to a much smaller loss value than No-loop ITD-BiO (i.e., N=1). This is in consistence with our thereotical results in Table 2
Experiments on ryper-representation. We consider a hyper-repressntttion problem [3),, where the inner problem is to find optimal regression parameters and the outer procedure is to find the best representation parameters A. In specific, the bilevel problem takes the following form:
1
1 [I(XX:: A)w Yrll 2 110l 1|
min (A)
[In(Xv; N)w -vv 2p
w argmin 2g
where X E R2xm and Xy E RRxm are synthesized training and validation data, Yr E R2, Yv E Iº are their response vectors, and h(-) is linear transformation. The generation of XT, Xv, YT, Yv and the experimental setup follow from [39]. For ITD-BiO, we choose N 20 for N-N-loop ITD and N = i for No-loop ITD. The results are reported with the best-tuned hyperparameters.
Algorithm
ke
10
50
k
100
500
1000
N-N-loop ITD
9.32
0.11
0.01
0.004
0.004
No-loop ITD
435
6.9
0.04
0.04
0.04
Table 3: Validation loss v.s. the number of iterations for ITD-based algorithms.
Table 3 indicates that N N-N-llop with N 20 can achieve small loss value of 0.004 after 500 total iterations, whereas No-loop with N = 1 converges to much larger loss value of 0.04. This is in consistence with our theoretical results in Table 2 where N can cause a non-vanishing error.
We also conduct the experiment for AID-BiO, where we choose N and Q from {1, 203 for four different loop implementations. We present the results for AID-BiO in Appendix F which also support our theoretical results in Table
7 Conclusion
In this paper, we study two popular bilevel optimizers AID-BiO and ITD-BiO, whose implementations potentially involve additional loops of iterations within their base-loop update. By developing unified convergence analysis for all choices of the loop parameters, we are able to provide formal comparison among different implementations. Our result suggests that N-loops are beneficial for better computational efficiency for AID-BiO and for better convergence accuracy for ITTD-BiO. This is in contrast to conventional minimax optimization, where No-loop (i.e., single-base-loop) scheme achieves better computational efficiency, Our analysis techniques can be useful to study other bilevel optimizers such as stochastic optimizers and variance reduced optimizers.
Acknowledgements
The work of Kaiyi Ji and Lei Ying is supported in part by NSF under grants 2002608, 2001687, 21 2112471, 2134081, and 2207548. The work of Yingbin Liang was supported part by the U.S. National Science Foundation under the grants CCF-1909291, DMS-2134145, and 1N4-2112471.
10

---

References
[1] I.. Bertinetto, F. Henriques, Torr, and A. Vedaldi. Meta-learning with differentiable closed-form solvers. In International Conference on Learning Representations (ICLR), 2018.
[2] T. Chen,, Y. Sun, and W. Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems (NeurIPS), 34:25294-255
2021.
[3] T. Chen, Y. Sun, and W. Yin. A single- timeel-t stochastic bilevel optimization method. arXiv preprint arXiv:2102.04671, 2021.
[4] Domke. Generic methods for optimization- modeling, In Artificial Intelligncce and Statistics (AISTATS), pages 318-326, 2012.
[5] M. Feurer and F. Hutter. Hyperparameter optimization. In Automated Machine Learning, pages 3-33. Springer, Cham, 2019.
[6] C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proc. International Conference on Machine Learning (ICML), pages 1126-1135, 2017.
[7] R. Flamary, A. Rakotomamonjy, and G. Gasso. Learning constrained task similarities in graphregularized multi-task learning. Regularization, Optimization, Kernels, and Support Vector Machines, page 103, 2014.
[8] I.. Franceschi, M. Donini, P. Frasconi, and M. Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning (ICML), pages 1165-1173, 2017.
[9] 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, 2018.
[10] S. Ghadimi and M. Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.002245 2018.
[11] R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo. On the iteration complexity of hypergradient computation. In Proc. International Conference Machine Learning (ICML), 2020.
[12] 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.
[13] Z. Guo and T. Yang. Randomized stochastic variance-reduced methods for stochastic bilevel optimization. arXiv preprint 10xXiv:20550225 2021.
[14] P. Hansen, B. Jaumard, and G. Savard. New branch-and -al--ann--bdddd rules for linear bilevel program- ming. SIAM Journal on Scientific and Statistical Computing, 13(5): 194-12174 1992.
[15] 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.
[16] M. Huang, K. Ji, S. Ma, and L. Lai. Efficiently escaping saddle points in bilevel optimization. arXiv preprint arXiv:2202. 03664, 2022.
[17] K. Ji, J. D. Lee, Y. Liang, and H. V. Poor. Convergence of meta-learning with task-specific adaptation over partial parameters. arXiv preprint N0X1:20006.09486 2020.
[18] K. Ji and Y. Liang. Lower bounds and accelerated algorithms for bilevel optimization. arXiv preprint wxXiv:2102.0322. 2021.
[19] K. Ji. J. Yang, and Y. Liang. Bilevel optimization: Convergence analysis and enhanced design.
In International Conference on Machine Learning, pages 4882-4892. PMLR, 2021.
[20] K. Ji, J. Yang, and Y. Liang. Theoretical convergence of multi-step model-agnostic meta- learning, Journal of Machine Learning Research (JMLR), 23:29-1, 2022.
11

---

[21] P. Khanduri, S. Zeng, M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. arXiv preprint arXiv:2102.07367, 2021.
[22] V. Konda and J. N. Tsitsiklis. Actor-critic algorithms. Advances neural information processing systems (NeurIPS), pages 1008-1014, 2000.
[23] G. Kunapuli, K. P. Bennett, J. Hu, J.-S. Pang. Classification model selection via bilevel programming. Optimization Methods & Software, 23(4):475-489 2008.
[24] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86( 01t:2227722244 1998.
[25] Li, B. Gu, and H. Huang. Improved bilevel model: Fast and optimal algorithm with theoretical guarantee. arXiv preprint arXiv:2009.0069) 2020.
[26] J. Li, B. Gu, and H. Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. arXiv preprint 1rXiv:2112.046600 2021.
[27] T. Lin, C. Jin, and M. Jordan. On gradient descent ascent for nonconvex-coneavy minimax problems. In International Conference on Machine Learning (ICML), pages 6083-6093. PMLR, 2020.
[28] R. Liu, X. Liu, X. Yuan, S. Zeng, and Zhang. A value-function--aase interior-point method for non-convex bi-level optimization. In International Conference on Machine Learning (ICML), 2021.
[29] R. Liu, Y. Liu, S. Zeng, and Zhang. Towards gradient- based bilevel optimization with non- convex followers and beyond. Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
[30] 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. In International Conference on Machine Learning (ICML), 2020.
[31] D. Maclaurin, D. Duvenaud, and R. Adams. Gradient-based hyperparameter optimization through reversible learning. In International Conference Machine Learning (ICML), pages 2113-2122, 2015.
[32] G. M. Moore. Bilevel programming algorithms for machine learning model selection. Rensselaer Polytechnic Institute, 2010.
[33] F. Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference on Machine Learning (ICML), pages 737-746, 2016.
[34] 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.
[35] 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.
[36] C. Shi, J. Lu, and G. Zhang. An extended kuhn-tucker approach for linear bilevel programming. Applied Mathematics and Computation, 162(1):51-63, 2005.
[37] J. Snell, K. Swersky, and R. Zemel. Prototypical networks for few-shot learning. In Advances in Neural Information Processing Systems (NIPS), 2017.
[38] D. Sow, K. Ji, Z. Guan, and Y. Liang. constrained optimization approach to bilevel optimiza- tion with multiple inner minima. arXiv preprint arXiv:2203.011133, 2022.
[39] D. Sow, K. Ji, and Y. Liang. bs-based jacobian enables faster bilevel optimization. arXiv preprint a Ttt::/10.000000 10.07004, 2021.
[40] Yang, K. Ji, and Y. Liang. Provably faster algorithms for bilevel optimization, Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
12

---

[41] J. Z.Zann, P. Xiao, R. Sun, and Z. Luo. A single-loop smoothed gradient descent-ascess ascent algorithm for nonconvex-coneayy min-max problems. Advances in Neural Information Processing Systems (NeurIPS), 33:7377-7389, 2020.
[42] M. Zhang, S. W. Su, S. Pan, X. Chang, E. M. Abbasnejad. and R. Haffari. idarts: Differentiable architecture search with stochastic implicit gradients. In International Conference Machine Learning (ICML), pages 12557-12566. PMLR, 2021.
Checklist
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] Table 2 shows that there exists gap of к between the upper and lower bounds for ITD-based bilevel optimization, which requires future efforts to address.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This paper develops the convergence theory for the fundamental belivel algorithms. Our analysis 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 B
(b) Did you include complete proofs of all theoretical results? [Yes] Complete proofs are included in the appendix.
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 [
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] See Appendix 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 included in Appendix E
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 E
(b) Did you mention the license of the assets? [Yes] The details are included in Appendix E
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
Our code is based on the existing asset. See Appendix E for details.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] The datasets we use are public. See Appendix D for details.
(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 crowdsourcing 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": "ujHGtMk21IS", "reviewer": "Reviewer_Kzzc", "summary": "This paper provides a unified convergence rate analysis for existing two types of widely-used bilevel optimization algorithms via so-called approximate implicit differentiation (AID) and iterative differentiation (ITD), under all different choices of loop sizes. Some interesting theoretical findings are provided as well. In particular, for AID-based approaches, two major loops exist within the base loop, i.e., a loop of size N for approximating the lower-level solution and a loop of size Q for estimating the Hessian-inverse-vector (HIV) product in the hypergradient computation. In the comparison among different loop choices, they specify their theories to several typical choices of interest in practice, including N= 1 or \\kappa and Q = 1 or \\kappa. Based on such comparisons, they show that the lower-level loop can improve the overall computational complexity w.r.t. both the matrix-vector and gradient computations, and the loop for HIV estimation can reduce the gradient complexity. For ITD-based method, they show via upper and lower bounds that loop size needs to be large for achieving a vanishing convergence error induced by the lower-level and HIV approximations. Some empirical results are also provided and seem to validate the theories well. ", "questions": "The paper is limited to the deterministic setting, and I am wondering if the developed analysis can be further extended to the stochastic setting with data sampling. Can the authors have some comments or provide some guidances on this extension?\n\nIn AID-based method, people sometimes use the acceleration methods for both the lower-level and HIV approximations to achieve a better complexity. It would be great to discuss how the current analysis can be extended to such scenarios, and whether the corresponding comparison still holds? \n\nTheorems 1, 2 and 3 seems involving complicated parameters and relations. It would be good to provide some proof outlines for readers to better understand the technical idea of this paper. \n", "limitations": "the authors adequately addressed the limitations and potential negative societal impact of their work", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work is well written and the motivation is clear to me. Bilevel optimization has attracted signification attention recently from both the deep learning and optimization communities, where AID and ITD are two widely-used methods so far. Characterizing a unified convergence guarantee for both of these two types of methods is fundamentally important because different loop schemes have been used in practice, but only some of them have guarantee. This work has done a good job in providing a tight characterization and systematic study for all these cases, which is a good contribution. \n\nThe theoretical findings are interesting and provide useful insights for practical applications. By capturing different dependences on the condition number \\kappa, they demonstrate the necessity of lower-level  optimization loops in both algorithms to improve the overall complexity, majorly in terms of the Hessian- and Jacobean-vector products. In particular, for ITD-based method, the lower bound is a nice and new contribution to justify the fundamental challenging for No loop scheme in achieving a vanishing error. Theories seem to be well supported by the experiments. \n\nThe technical analysis introduces some new developments, which may be of interest to the bilevel optimization community. Existing works on the convergence rate of bilevel optimization  mainly focus on the case when the HIV is solved at a good accuracy via large Q, but this paper allows small Q by showing that the coupled error is decreasing iteratively. This kind of characterization may be used in other settings with AID types of bilevel optimization. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "syBQsRgfTjB", "reviewer": "Reviewer_jDxR", "summary": "This paper provides a unified convergence theory to capture the computational differences among different implementations in bilevel optimization algorithms such as AID-BiO and ITD-BiO, with a focus on the different choices of inner and outer loops. By comparing different implementation, the paper draws the conclusion that different from the minmax case, in the bilevel optimization, having double loops always have some provable benefit. ", "questions": "* The lower-bound result in Theorem 4. See [Weaknesses]. It would be helpful to clarify. \n\n* Applicability of the results to the stochastic bilevel algorithms. See [Weaknesses]. It would be helpful to clarify. \n\n* In practice, stochastic bilevel optimization algorithms may be used more frequently. How does the conclusion in this paper compare to the conclusion in the recent work on *stochastic* bilevel optimization algorithms; for example, Theorem 1 and Proposition 2 in [Chen et al' 2021]. It would be helpful to clarify. \n\n    Chen et al \"Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems.\" Advances in Neural Information Processing Systems, 2021.\n\n* The performance metrics in the experiments. See [Weaknesses]. It would be helpful to clarify. \n\n* In the AID-Bio, is it possible to provide the lower-bound similar to ITD-Bio? \n\n* The discussion on the setting with small response Jacobian (line 304) is not clear. What conclusion do the authors want to draw from this discussion? Is this consistent with the main results? ", "limitations": "The limitations and potential negative societal impact of their work have been properly discussed. ", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[Strengths]\n* The paper is well written and the theoretical question studied in this paper is of practical interest.\n* The paper has done a good job of summarizing the theoretical results into two tables that have an explicit dependence on $\\kappa$ and $\\epsilon$. \n* The non-convergent result (both upper and lower bounds) of No-loop ITD-Bio is interesting, which suggests a gap between the performance of AID-Bio and ITD-Bio. \n\n[Weaknesses]\n* The lower-bound result in Theorem 4 is a bit loose. Not only because it has a large gap with the upper bound, but the worst-case example used in the proof also seems not carefully crafted. Does the lower bound also depend on $K$? Is there any possibility of improving the lower bound or upper bound? \n\n* The paper only focuses on the comparison of different *deterministic* bilevel optimization algorithms. Does the conclusion in this paper also hold in the *stochastic* setting? If not, it would be helpful by mentioning ``deterministic'' in the title or abstract. \n\n* It is not clear to me why the metic in the AID-Bio experiments is runtime, but that in the ITD-Bio experiments is iteration? Since the theory is mostly on the comparison on the number of iterations or MV and GC, comparing those metrics in both experiments will make more sense. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "mRmOUHVWT9_", "reviewer": "Reviewer_rZSp", "summary": "1.\tIn this paper, the authors study two popular bilevel optimizers AID-BiO and ITD-BiO, whose implementations involve different choices of loops. The authors first establish unified convergence analyses that are applicable to all implementation choices of loops for both optimizers.\n2.\tThe authors specialize their results to characterize the computational complexities for all implementations, and they then provide an explicit comparison across different implementations.\n", "questions": "1.\tWhat are the exact definitions of the notations $\\Theta$ and $\\Omega$?\n2.\tThe authors may want to provide references on the hypergradient in AID-BiO to help readers to understand the algorithms.\n3.\tThe authors consider a hyperparameter optimization problem on MNIST in the experiments on AID-BiO (in Line 315), while you consider another hyper-representation problem in the experiments on ITD-BiO (in Line 332). Why do you consider different problems for the two optimizers?\n", "limitations": "Yes, the authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.\tThe authors first establish unified convergence analyses that are applicable to all implementation choices of loops for both AID-BiO and ITD-BiO.\n2.\tThe authors compare the computational complexities among all implementations of the optimizers. The numerical experiments further demonstrate their theoretical results.\n3.\tThe paper is easy to follow.\n\nWeaknesses:\n1.\tThe exact definitions of some important notations such as $\\Theta$ and $\\Omega$ are missing.\n2.\tThe authors consider a hyperparameter optimization problem on MNIST in the experiments on AID-BiO (in Line 315), while they consider another hyper-representation problem in the experiments on ITD-BiO (in Line 332). They may want to explain why they consider different problems for the two optimizers.\n3.\tIn this paper, the authors only report the losses v.s. running time and the losses v.s. the number of iterations in experiments on AID-BiO and ITD-BiO, respectively. It would be more convincing if they report MV($\\epsilon$)(the total number of Jacobian- and Hessian-vector product computations), Gc($\\epsilon$)(the total number of gradient computations) or some more metrics in the experiments to support their theoretical results on the computational complexities.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HlY7w-_oVsW", "reviewer": "Reviewer_KmZV", "summary": "This paper studies the fine-grained convergence of gradient-based algorithms for bilevel optimization problems. The focus is on establishing the unified convergence analysis for both AID-BiO and ITD-BiO and on the comparison between the rate of convergence under different numbers of steps in the inner and outer loops. Under reasonable assumptions, the paper shows that AID-BiO and ITD-BiO can benefit from double loops in certain sense. ", "questions": "See my comments in weakness. ", "limitations": "Yes, it addresses the limitations. ", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Comments - Strengths**\n\n(+) The unified convergence theory for AID-BiO is new, which captures all choices of the inner-level gradient steps N and the outer-level Hessian-inverse-vector steps Q. The lower-bound on the nonconvex-strongly convex bilevel problem seems new. \n\n(+) The conclusion that bilevel optimization is in contrast to minimax optimization, where no-loop gradient descent ascent (GDA) with N = 1 often outperforms (N-loop) GDA is interesting.\n\n**Comments - Weaknesses**\n\n*Major comments*\n\n(-) The major concern I have is that the majority of the theory in this submission is a summary of previous convergence results in [17]. Indeed, this paper and [17] focus on the same setting, the same algorithms, and the same convergence results but now with explicit dependence on the number of steps in the inner $N$ and outer loops $Q$. While this is a good point to discuss, the technical content of this paper seems to be incremental. Therefore, this paper is more like a supplementary to [17].\n\n(-) The second major concern I have is that the theoretical comparison between the double-loop and the single-loop is in terms of the complexity upper bound. Note that the larger upper bound may not mean worse performance since the single-loop algorithm may be harder to analyze, leading to looser worst-case performance. For example, it would be interesting to compare the lower bound of the single-loop algorithm with the upper bound of the double-loop algorithms. \n\n(-) The third major concern is on the experiments. The experiments did not closely match the theoretical analysis. Since the separation between no-loop and double-loop is on $N={\\cal O}(1)$ or $N={\\cal O}(\\kappa)$, choosing $N, Q$ as $1, 20$ does not serve the purposes. In addition, it may be better to plot the dependence on $MV$ and $GC$ not the runtime nor the number of iterations.\n\n*Minor comments*\n\n(-) A similar conclusion for AID-Bio (e.g., $N={\\cal O}(\\kappa)$ is better than $N={\\cal O}(1)$) has already been drawn in the stochastic bilevel algorithms; see ALSET (Closing the Gap: Tighter Analysis of Alternating Stochastic Gradient Methods for Bilevel Problems). The connection and difference need to be discussed. \n\n(-) While the paper did provide a lower bound for ITD-Bio, it seems quite loose compared with the upper bound of ITD-Bio. They differ not only in the dependence on $\\kappa$ but also the dependence on $K$. \n\n(-) The main theorems (e.g., Theorems 1, 2, and 3) in the paper are presented in a very complicated way. They depend on many irrelevant constants such as $M, \\rho, r$, which make the main theorems difficult to interpret. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept