Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond
Authors: Risheng Liu
Yaohua Liu
Shangzhi Zeng
Jin Zhang
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Bi-level programming
gradient-based method
asymptotic convergence
few-shot classification
data hyper-cleaning

Abstract: In recent years, Bi-Level Optimization (BLO) techniques have received extensive attentions from both learning and vision communities. A variety of BLO models in complex and practical tasks are of non-convex follower structure in nature (a.k.a., without Lower-Level Convexity, LLC for short). However, this challenging class of BLOs is lack of developments on both efficient solution strategies and solid theoretical guarantees. In this work, we propose a new algorithmic framework, named Initialization Auxiliary and Pessimistic Trajectory Truncated Gradient Method (IAPTT-GM), to partially address the above issues. In particular, by introducing an auxiliary as initialization to guide the optimization dynamics and designing a pessimistic trajectory truncation operation, we construct a reliable approximate version of the original BLO in the absence of LLC hypothesis. Our theoretical investigations establish the convergence of solutions returned by IAPTT-GM towards those of the original BLO without LLC. As an additional bonus, we also theoretically justify the quality of our IAPTT-GM embedded with Nesterov's accelerated dynamics under LLC. The experimental results confirm both the convergence of our algorithm without LLC, and the theoretical findings under LLC.

Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond
Risheng Liu!.2 Yaohua Liul
Shangzhi Zeng²
Jin Zhang +4,5 Pazhou Lab, Guangzhou
International School of Information Science & Engineering, DUT
Department of Mathematics and Statistics, UVic
Department Mathematics, SUSTech Naational Center for Applied Mathematics Shenzhen rsliuudlut. edu. cn SSuy10hua_9180163. com
liuyaohua, 9180163.
Lengshangzhi@gmail com
zhangj90sustech. edu.
Abstract
In recent years, Bi-Level Optimization (BLO) techniques have received extensive attentions from both learning and vision communities. variety of BLO models complex and practical tasks are of without Lower-Level Convexity, L.L. for short). However, this challenging class of BLOs is lack of developments on both efficient solution strategies and solid the- oretical guarantees. In this work, we propose new algorithmic framework, named Initialization Auxiliary and Pessimistic Trajectory Truncated Gradient Method (IAPTT-GM), to partially address the above issues. particular, by introducing auxiliary as initialization guide the optimization dynamics and designing a pessimistic trajectory truncation operation, we construct a reliable approximate version of the original BLO in the absence of LLC hypothesis. Our theoretical in- vestigations establish the convergence of solutions returned by IAPTT-GM towards those of the original BLO without LLC. As additional bonus, also theoreti- cally justify the quality of our IAPTT-GM embedded with Nesterov's 's accelerated dynamics under LLC. The experimental results confirm both the convergence of our algorithm without LLC, and the theoretical findings under LLC.
follower structure in nature (a.k.a.,
Introduction
Bi-Level Optimization (BLO) has been widely used to formulate problems in the field of deep
learning I 2. especially for hyperparameter optimization 3 5] meta learning 7 D neural architecture search [00 12), adversarial learning [13]. and reinforcement learning 14] etc. BLO aims to tackle nested optimization structures appearing in applications, which has emerged prevailing optimization technique for modern machine learning tasks with underlying hierarchy. In the last decade, a large number of BLO methods have been proposed address different machine learning tasks. In fact, Gradient Methods (GMs), which can effectively handle BL.O problems of large scale, thus gain popularity. According to different types of strategies for gradient calculations, existing GMs can be divided into two categories, i.e., the explicit approaches which aim to replace the Lower-Level (LL) problem with dynamic iterations and implicit schemes that apply the implicit function theorem to formulate the first-order optimality condition of the LL problem.
Explicit Gradient Methods for BLOs. In this type, solving the LL problem is regarded as evolution path of the dynamic system starting from given initial point of the LI. variable. The gradient the Upper-Level (UL) variable can be directly calculated by automatic differentiation
*Corresponding author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

based on the trajectory of LL variable. namely, recurrence- based EG (e.g.. g... B
This class of methods can be further divided into three types,
EG (e.g.. [7 [8] and 22 D) differing from each other in the way of accessing the gradient of constructed dynamic trajectory. While most of this type of works assume the L.I.C and Lower-Level Singleton (LLS) to simplify their optimization process and theoretical analysis, cases where the LLS assumption does not hold have been tackled in the recent work (23 24]. In particular, to eliminate the LLS assumption which is too restrctive to be satisfied in real-world complex tasks, [3 first considers incorporating UL objective information into the dynamic iterations, but the more general cases where LLC does not hold remain unsolved. On the other hand, while most of the mentioned works focus on the asymptotic convergence, the progress on nonasymptotic convergence
[3
6
16
TO), initialization-basee
proxy-based EG methods (e.g., [9
20
21
analysis has been recently witnessed see, e.g., 25 26 27].
Implicit Gradient Methods for BLOs. This type, also known as implicit differentiation 28 29
replaces the LL problem with its first-order optimality condition and uses the implicit function theorem to calculate the gradient of the UL problem by solving a linear system. This method decouples the calculation of UL gradient from the dynamic system of LL, resulting in a significant speed increase when the dynamic system iterates many times. However, because of the burden originated from computing Hessian matrix and its inverse, IG methods are usually computationally expensive when linear systems are ill-conditioned. To alleviate this computational issue, there are mainly two kinds of techniques, i.c.. IG based on Linear System (LS) (28 7 and Neumann Series (NS) [29]. On the theoretical side, IG methods rely on the strong convexity of LL problems heavily, which is even more restrictive than the LLC and LLS together.
Initialization Optimization for Learning, In deep learning, the selection of initialization scheme has great influence on the training speed and performance [30]. As the most representative work in recent years, Model-Agnostic Meta- Learning (MAMI.) 31 applies the same initialization to all tasks, and is optimized by a loss function common to the task that evaluates the effect of the initial value, resulting in an initialization that achieves good generalization performance with only a few gradient steps on new tasks. Due to its simple form this method has been widely studied and applied 34 35 36) noticed that not all network parameters are suitable for the same initialization, and therefore proposed a strategy to apply co-initialization only on a part of parameters. In theory, 37 33 39] give comprehensive study the convergence and convergence rate of MAML and some MAML-type approaches based on the meta objective function. However, the convergence theory of these existing results given based the loss function for evaluating initial values, and the convergence analysis of such type of methods from the perspective of each task is still lacked.
32
33
Value-Function Approach. The value function based methods have also emerged as a promising branch to solve BLO problems [40]. Under the special case where the LL is jointly convex with respect to both the UL and LL variables, the BLO problem can be equivalently reformulated into a difference-of--cmye the BL.O into an Inner Single Bi-level (ISB) optimization problem with value-function approach, gradient-based interior-pone method name B BVFIM [2) is proposed to solve the BLO tasks, which effectively avoids the expensive Hessian- vector and Jacobian-vector products. Generally speaking, the
program (1), which is numerically solvable. Typically, by reformulating
does not admit an explicit form, and is always nonsmooth, non-convex and with
jumps.
1.1 Our Motivations and Contributions
As mentioned above, some theoretical progresses have long been witnessed in diversified learning areas, but for most existing BLO methods, extra restrictive assumptions (c.g., LLS, LLC and LL strong convexity) have to be enforced. Their algorithm design and associated theoretical analysis actually are only valid for optimization with simplified problem structure. Unfortunately, it has been well recognized that LL non non-convexity frequently appears in a variety of applications, e.g., sparse Eg regularization (0 < q < 1) for avoiding over-fitting, and learning parameters of coupled multi-layer neural networks, etc. Therefore, in challenging real-world scenarios, we are usually required to consider BLO problems where these assumptions (e.g., LLS, LLC and even LL strong convexity) are naturally violated. These fundamental theoretical issues motivate us to propose series of new techniques to address BL.O with non-convex L.I. problems, which have been frequently appeared in various learning applications.
2

---

In particular, by introducing an Initialization Auxiliary (IA) to the LL optimization dynamics and operating Pessimistic Trajectory Truncation (PTT) strategy during the UL approximation, we construct Gradient-based Method (GM), named IAPTT-GM, to address BLO in challenging optimization scenarios (i.e., with non-convex follower tasks). We analyze the convergence behaviors of IAPTT-GM on BLOs without LLC and also investigate theoretical properties of the accelerated version of our algorithm on BLOs under LLC. Extensive experiments verify our theoretical results and demonstrate the effectiveness of IAPTT-GM on different learning applications. The main contributions our IAPTT-GM are summarized as follows:
We propose IA and PTT, two new mechanisms to efficiently handle complex BLOs where the follower is facing with a non-convex task (i.e., without LLS and even LLC). IA actually paves the way for jointly optimizing both the UL variables and the dynamical initialization, while PTT adaptively reduces the complexity of backward recurrent propagation.
To our best knowledge, establish the first strict convergence guarantec for gradient- based method on BLOS with non-convex follower tasks. We also justify the quality of our IAPTT-GM embedded with Nesterov's accelerated dynamics under LLC.
We conduct series of experiments to verify our theoretical findings and evaluate IAPTT-GM on various challenging BLOs, in which the follower tasks are either with non-convex loss functions (e.g., few-shot learning) coupled network structures (e.g., data hyper-cleaning).
2
The Proposed Algorithmic Framework
In this work, consider the BLO problem in the form:
min F(x,y) y), s.t. y S(x),
xeX
where x E R",y R" are UL and LL variables respectively, and S(x) denotes the set of solutions of the LL problem, i.c.
S(x) == arg min yx, yEy
where f differentiable w.r.t. y. To ensure the BLO model in Eq. (I is well-defined, we assume that S(x) is nonempty for all x E X. Observe further that the above BLO is structurally different from those in existing literature in the sense that no convexity assumption is required in the LL problem.
In the following, we describe the proposed IAPTT-GM to solve the class of BLOs defined in Eq. (T) The mechanism of classical dynamics embeddde gradient method, approximates the LL solution via a dynamical system drawn from optimization iterations. Choosing gradient descent as the optimization dynamics for example, the approximation y xxx) is accessed by operations repeatedly performed by K steps parameterized by UL variable x
(k) = (x) - s fxx k 0...... K-1, 1,
(3)
where 5 is a step size, and yo is fixed initial value.
2.1 Initialization Auxiliary
Embedding the dynamical iterations into the UL problem returns the approximate version F(x, (x.xxx(x)) As long as (x,((x (x)) uniformly converges to zero w.r.t. UL variable x varying in X, we call this a good approximation. To this end, usually restrictive LL strong convexity assump- tions are imposed, thus the desired convergence of solutions of approximation problems towards those of the original BLO follows. By drawing inspiration from the classic dynamics-embedded gradient method which replaces the LL problem with certain optimization dynamics, hence resulting an approximation of the bi-level problem, we propose a new gradient scheme solve BLO in Eq. (I) without LLC restriction. Specifically. we let K be prescribed positive integer and construct the following approximation yK (x, z) of the LL solution drawn from projected gradient descent iterations
yo(x, 2) z,
(4)
Yk-1 1 2) Projy(ys(x,2) - yxx, == -.....,K
3

---

where } is sequence of steps sizes. We next embed the dynamical iterations ys(x, z) into maxi<AsK {F (x, z))}, which can be regarded as pessimistic trajectory truncation of the UL objective. The mechanism of the above scheme, in comparison, accesses the approximation parameter- ized by UL variable x and LL initial point yo. Our motivation for the initialization auxiliary variable z comes from convergence theory 42 of non-convex first-order optimization methods. In fact, when the non-convex LL problem admits multiple solutions, the gradient descent steps with "bad" initial point yo cannot return desired point in the LL solution set, simultaneously optimizing the UL objective. To overcome such difficulty, instead of using fixed initial value, we introduce initialization auxiliary variable z. Therefore, when it comes to solving the UL approximation problems, together with the UL. variable x, the auxiliary variable is also updated and hence optimized. As consequence, search for the "best" initial value, starting from which the gradient descent steps approach a solution to the BLO in Eq. I i...& a point in the LL solution set, simultancously minimizing the UL objective.
may
2.2 Pessimistic Trajectory Truncation
This is a striking feature of our algorithm that significantly differs from existing methods and leads to some new convergence results with- out LLC.C The motivation for the design of pessimistic trajectory truncation comes again from convergence theory of non-convex first- order optimization methods. It is understood
Algorithm 1 The Proposed JAPTT-GM
1: Initialize x" and z"
2: for L 0 - T do
3:
zz.
4:
for k: == 0 K- do
5:
% LL Updating with x' and z'
that when LL is non-convex, R. (x, YK (x, 2)) may not uniformly converge w.r.t. and z, where (x. yx. is the proximal gradient resid- ual mapping defined Projy (y a (x. r which can be used as measurement of the optimality of LLL proh- lem in Eq. ( Thus a direct embedding of (x,X, z) into UL. objective F(x.y) y) may not necessarily provide an appropriate approxima- tion. Fortunately, it also understood that, for each x E X, z E ) and K > O, there exists at least a K such that along the selection y (x, z), Ra (x, uniformly converges zero w.E.t. x and z, as K tending infinity.
6: Yk+11 = Projy(yx og v yx))
7:
end for
8:
% Pessimistic Trajectory Truncation
Rx.xx)) == y
9:
k arg max ( (x, )
IK=I
10:
% UL Updating with yı (x, Z)
11:
x++1 Proj x (x' - 0x V FxF(x', yg)).
12:
% Initialization Updating with YE 2)
13: z'+1 Projy(z' 02 F yz)).
14: end for
However, in general, it is too ambitious to expect explicit identification of the exact selection Y& (x, 2). Alternatively, we consider a pessimistic strategy, minimizing the worst case of all selec- tions of (y 2) i.e., maxig&<K (F(x, yı z))) By doing so, successfully reach good approximation. In addition to the theoretical convergence, we also benefit from this pessimistic strategy in numerical sense. The pessimistic max operation always results in a favorable trajectory truncation smaller than K. Consequently, this technique offers inexpensive computational cost for computing the hyper-gradient through back propagation, shown in the numerical experiments.
To conclude this section, we state the complete IAPTT-GM in Algorithm ! Note that K and T represent the numbers of inner and outer iterations, respectively.
3 Theoretical Investigations
With the purpose of studying the convergence of dynamics-embeddee gradient method for BLO without LLC, we involve two signature features in our algorithmic design, i.c., initialization auxiliary and pessimistic trajectory truncated. This section is devoted to the convergence analysis of our proposed algorithm with and without LLC assumption. Please notice that all the proofs of our theoretical results are stated in the Supplemental Material.
'Ra (x reduces a V when ) is taken as T

---

3.1 Convergence Analysis of IAPTT-GM for BLO with Non-convex Followers
In this part, we conduct the convergence analysis of the IAPTT-GM for solving BLO in Eq. (I) without LLC. Before presenting our main convergence results, we introduce some notations related to BLO. With introduced function pp(x) == infyes(x) F(x. y), the BLO in Eq. ( can rewritten
min xE
pxx).
(5)
With given 2 and defining fpx (x, 2) := maxe {F(x, ya 2))} with (yx(x, 2)} defined in Eq. (4) our proposed IAPTT-GM generates sequence {(x', 2 for solving following approximation problem to BLO in Eq. 5
PK (x, z). xxX,xy
min
(6)
This section is mainly devoted to the convergence of solutions of approximation problems in Eq. (6) towards those of the original BLO in Eq. (5).
Assumption 3.1 We make following standing assumptions throughout this section.
(1) F.f: :2 x R. are continuous functions.
(2) V continuous and y.f is L5 Lipschitz continuous with respect y for any X.
(3) X and convex compact sets.
(4) S(x) is nonempty for any X.
(5) For any (x. y) minimizing y) over constraints x E &, E y and y E S(x), it holds that y E S(x)..
Note that S(x) denotes the set of LL stationary points, i.c., S(x) = {y E y/0 =
(y) should be noticed that y E $(x) if and only if (x. = 0. Assumption 3.1 is standard in bi-level optimziation related literature, which will be shown to be satisfied for the numerical example given in Section 4.1
As discussed the preceding section, for each x E X, 2 E y and K > 0, there exists at least a R such that along the selection Yg 2x, Ra,x,, (x, uniformly converges
w.r.t. and 2, as K tending infinity. We next specifically show the existence such index R. To this end, K can be chosen by optimizing |iRR,, (x, y x))ll among the indices k = 0, 1, ..... K. In particular, as stated in the following lemma, || (x. y (x,
(x,x))) z))l uniformly decreases with a vK rate on X' x y
as K increases.
Lemma 3.1 Let {xx(x, 2)} be the sequence defined in Eq. (4 with az E lay Tyl c (0, 2,), there
exists Cf > 0 such that
C
Re, (x. (x(, osksK
min
Vx XxE
VK +1
As shown in the Appendix, the proof of Lemma 3.1 for the existence cannot offer us an explicit identification the exact selection of K. Alternatively, we construct the approximation by a pessimistic trajectory truncation strategy, minimizing the worst of all selections of (y&(x, z)}. i.e. Φ (x, z). By further solving the approximated problems min p xx 2), we shall provide a lower bound estimation for the optimal value of the BLO problem in Eq.
Lemma 3.2 Let (XK, 2x) E argmin sox (x, 2), then xEX.ZEy
pk(*,, inf F(x,y), Vx E X. xES(x)
Upon together with the uniform convergence result in Lemma 3.1 the gap between the lower bound provided by min p (x, x) and the true optimal value of the BLO problem in Eq. (5) eventually vanishes. To fill in this gap and present the main convergence result of our proposed IAPTT-GM,
5

---

we need the continuity of y). Indeed, it follows from 43 Theorem 6.42] that Projy is continuous, Combined with the assumed continuity of V (x, we get the desired continuity of (x. y) immediately.
Theorem 3.1 Ler {y,(x, 2)} be the sequence generated by Eq. (4) with aÿ E lay Tyy c C(0, 2ry)
and (xK, zx) argmin (o (x. 2), then have:
xEX2zE)
(1) Any limit point x of the sequence {xx} is the solution BLO in Eq. L that is X argming((x). XEX
(2)
xEX (x - inf x as K xEX,NE)
inf
oc. oc.
xEX
In the above theorem, we justify the global solutions convergence of the approximated problems. We next derive a convergence characterization regarding the local minimums of the approximated problems. In particular, the next theorem shows that any limit point of the local minimums of approximated problems is in some sense a local minimum the bilevel problem in Eq. !..
Theorem 3.2 Let (y 2)} be the sequence generated by Eq. 4 with ot [ay Gyl (0, t.y) and (xx, 2x) be a local minimum of 1pxc (x, 2) with uniform neighborhood modulus >> 0, i.e.
(K(XK, zk) S spx (x, Z): v(x,z) E [x(( zx) N x y
Then we have that for any limit point (x, 2) of the sequence {(*,, 2x)), there exists limit point y of the sequence {yK (Xx, zk]} such that S(x) and (X satisfies that there exists ō >> 0 such that
F(X,8) S F(x,2) v(x, 2) E B Bg 2) n fx X, 2 S(x))
3.2 Theoretical Findings of IA-GM (A) for BLO with LLC
byproduct of our study, which has its own interest, that thanks to the involved initialization auxiliary, our theory can improve those existing results for classical gradient methods with accelerated gradient descent dynamical iterations under LLC. Nesterov's 's acceleration technique 44] has been used widely for solving convex optimization problem and it greatly improves the convergence rate of gradient descent. To illustrate our result, we will take the Nesterov's acceleration proximal gradient method 45 as the embedded optimization dynamics in classical gradient method for example.
Thanks the LLC setting, (x, y (x) may uniformly converge zero w.r.t. UL variable and auxiliary variable z. thus the pessimistic trajectory truncation operation can be removed. Subsequently, we slightly simplify our algorithm that is simply taken K, thus the approximation objective admits a succinct form, i.e., F(x,y yx (x, 2)).
In summary, by constructing y& (x, through following Nesterov's acceleration dynamics,
1 1+
/1
th
Vo 2) z, to 1, tx+1
k= K 1,
u² k+1 (x, z) = kt (x, z)) +
tv tx=11 1
(x,z)) z)), k 0.... K 1, (y (x, z) yx
(9)
tx+1
Yk+1 (x, 2) = Projy (u* (x, VxX, (x, 2))) = 0, , 1-
where a > is the step size, we propose an accelerated Gradient- based Method with Initialization Auxiliary, named IA-GM(A), via minimizing the approximation objective function,
Φx z) F(x. yx (x, xEX
min
The detailed description of the proposed IA- IA-GNN GM(A) is stated the Supplemental Material.
We suppose Assumption 3.1 ()-(4) are satisfied throughout this subsection. The convergence result of our proposed (A-GM(A) with LLC assumption is given below.
Theorem 3.3 Assume that the generated sequence (yε(x,z)) 2)} satisfies that yı(x, 2) Y, and Y& (x, z) for any z S(x), x E X, and either

---

(a) for any > O, there exists k(c) > 0 such that whenever K > k(e),
sup xEX,,E
{f (x, 2)) fx(x)] c
whenever K k((c), or
(b) there exists > 0, for any > 0, there exists k(c) >> O such that, RR (x, (x 2)) e.
sup
xEX,aEy
Let (xK, zk) argmin Ox ox (x. xEλ
F(x, z)), then we have
(1) any limit point T the the sequence {xK} satisfies that x E argming(x)) ie., T is the solution
xEX
to BLO T
ØK (x,2) xEX zEy
inf
inf (x() K oc.
XEX
Next, we show that the Nesterov's acceleration dynamics satisfy all the assumptions required in the above convergence theorem.
Theorem 3.4 Let [yv(x, 3)} be the sequence generated by Nesterov's acceleration dynamics in Eq. 99 with T.y. Then (yu(x, 2)} satisfies all the assumptions required by Theorem 3.3
Remark 3.1 Our convergence result Theorem 3.3 is not only for yı generated by Nesterov's ac- celeration dynamics. It is general convergence result that is applicable for the case where yu is generated by other dynamics. And the assumptions required in Theorem 3.3 is weak enough to be satisfied by the dynamics introduced by many first-order methods on convex LL problem in Eq. 2
4 Experimental Results
In this section, we first verify the theoretical convergence results on non-convex numerical problems compared with existing EG methods and IG methods. Then we test the performance of IAPTT-GM and demonstrate its generalizability to real-world BLO problems with non-convex followers, which caused by non-convex regularization and neural network structures. In addition, further validate the performance of the accelerated version (i.c., IA-GM (A)) under LLC with numerical examples and data hyper-cleaning tasks
4.1 Numerical Verification
To verify the convergence property under assumptions provided Section B we consider the following non-convex BLO problem:
min + ry, s.t. y argmin sin(xy), wEX WER
(10)
yEy
where X' [1, 10] and y 2_ Given any x X, it satisfies argmin sin(ry) {(2kT 7 x/2) /z Z) and mingey - sin(xy) -1 The unique solution is (x", (11//4, 22). It should be noted that the LL problem of Eq. (TO) has multiple global minima, which can significantly show the advantage of initialization auxiliary technique. It can be easily verified that the above toy example satisfies Assumption 3.1
In Figure I we separately compared IAPTT-GM with EG methods such RHG 3. BDA (33, IG methods such as LS (28). NS 7 and IA-GM. From Figure 1.(a) to Figure I.(b). we can observe that different initialization points only slightly affect the convergence speed of IAPTT-GM. With initialization points distant from tt",")). IAPTT-GM can still achieve optimal solution of UL variables and optimal objective value, while other methods fail converge the true solution. In Figure 1.g) and Figure I. we compare the performances of IAPTT-GM with IA-GM, which has no convergence guarantee without LLC assumption. As shown, IA-GM fails converge the true solution eventually, which validates the necessity of PTT technique and the effectiveness of IAPTT-GM.
Thhe code is available at http://gihhub.commiiss..ggggg//p

---

I I1
TAPFT-CM
UL lteraiin
Iteration
UL Iteration
lteration
(a) JD
1. V0
(h) .20
1, yo
(c) mo
7,80
(d) 370
7, 300
FA-OM OM - FLAFTT -OM
-88
LATTI Cillie-iii-- -.
-BDA
CAPTL-GMI OMi
TAPTT-GM
LLGGMi -
[APPTT PMPT
Ieraaion
Iteration
Iteration
Iteration
(c) Jg 5, Vo
(f) xo 3o
(g)
(h)
Figure 1: Illustrating the convergence behavior of || F1I and - 1//l</ as the
training proceeds. FIAPTT-CE and FIA-GM denote the UL objectives of IAPTT-GM and IA-GM, respectively. Three representative initialization points for UL and LL variables are (æo. yo) (1. 2). (wo, 90) (5, 1), (wo, 30) = (7,-1).
Runtime and Memory Analysis. In Figure 2 we re- port the average steps of IAPTT-GM for PTT and the iterative speed as the UL iteration increases. In com- parison with IA-GM, which uses default K for the LL optimization loop, the changing k for IAPTT-GM leads less iterations for the backward recurrent propagation and thus faster iterative updates during optimization. Although IA introduces additional variables and iter- ations, the PTT technique can choose small k, thus shortens the back- pack-propagation trajectory for computing the UL gradient (see Figure 2) As can be seen in Ta- [ the memory required by our IAPTT-GM less than NS, LS, and BDA and the same that for RHG. As for the runtime, IAPTT-GM is a bit slower than RHG and NS, and faster than BDA. But please notice that the performance and the theoretical properties of IAPTT-GM are better than these existing approaches.
Speed, seofter
00.00
Steps
TA-CM
JAPTT-GM
-IA-GM
-IAPT-GM
3000
266
UL Iteration
Figure 2: Illustrating average steps for PTT technique and average running speed the numerical example. Note that we conduct the experiments using more LI. iterations so to reduce the measurement error.
Table Memory and runtime of existing methods for solving the above BLO problem. We conduct the experiments using the same parameter settings in Section C of the supplementary materials.
Metrics
LS
NS
RHG
BDA
TAPTT-GM
Memory (GB)
10.426
10.387
10.153
10.154
10.153
Runtime (Sec)
5.120
10.815
9,990
16,800
10.835
4.2 BLO with Non-convex Followers Different Application Scenarios
To cover various real-world BLO application scenarios, consider two categories of non-convex LL problems caused by non-convex regularization term and neural network architectures, which refer to few-shot classification and data byper-cleaning tasks, respectively. Please note that the set constraint ) only used to guarantee application scenarios, we can just consider the constraint as extra large so that all the variables are automatically in this feasible set. In this way, is natural ignore the projection operation in practical computations.
completeness of our theoretical analysis Section 3 In

---

4.2.1 Few-Shot Classification: Non-convex LL Objective
In few-shot learning, to be more specific, N-way M-shot classification tasks [46], provided with M samples from each class, we train models take advantage of prior data from similar tasks to quickly classify unseen instances from these N classes. Following the experimental protocol [47], the model parameters are separated into two parts: the hyper representation module (parameterized by x) shared by all the tasks and the last classifier (parameterized by y²) for j-th task. Define the meta training dataset D {Di}. where D = D UD corresponds to the j-th task.
The cross-entropy loss function is widely used for UL and LL objectives. Referring to Section 3 IAPTT-GM covers the convergence results with non-convex LL model, thus allowing flexible design of the LL objective function. For instance, while non-convex regularization terms, e.g., ly regulariza- tion with 0 < < 1, have shown effectiveness to help the LL model converge and avoid over-fitting. existing methods can only guarantee the convergence when g 2 1, thus almost provide no support for non-convex objectives. We consider the LLI subproblem with non-convex loss functions by adding by regularization + Then the UL and LL subproblems can be written as
F (x, (x)))) -e (xxxx)x; (x.x'::Dia) S [(x, (x, (x = Σ (x Dis)) + lly" la-
(11)
Table 2: Mean test accuracy of 5-way classification on tieredImageNet and minilmageNet, and the + represents 95% confidence intervals tasks.
Minilmagenet
Taeree
Methods
Backbone
5-way 1-shot
5-way 5-shot
5-way 1-shot
5-way 5-shot
Proto Net
ConvNer-4
49.42 + 1.84
68.20 + 0.66
53.31 + 0.89
72.69 + 0.74
Relation Net
ConvNet-4
50.44 + 0.82
65.32 = 0.70
54.48 + 0.93
65.32 + 0.70
MAMI
4onvNet-4
48.70 + 0.75
63.11 0.11
49.06 0.50
67.48 0.47
RHG
ConvNet-4
48.89 + 0.81
63.02 + 0.70
49.63 + 0.67
66.14 + 0.57
T-RHG
ConvNet-4
47.67 + 0.82
63.70 + 0.76
50.79 + 0.69
67.39 + 0.60
BDA
CouvNet-4
49.08 + 0.82
62.17 0.70
51.56 + 0.68
68.21 + 0.58
MAML
ResNet-12
51.03 + 0.50
68.26 + 0.47
58.58 + 0.49
71.24 + 0.43
RHG
Re
50.54 + 0.85
64.53 + 0.68
58.19 + 0.76
75.20 + 0.60
IAPTT-GM
ResNet-
56.69 0.66
70.21
0.55
60.71 0.77
75.85 + 0.59
Detailed information about the datasets and network architectures can be found in the supplementary materials. We report results of IAPTT-GM and various mainstream methods, e.g., Prototypical Network [48], Relation Net [49] and T-RHG [16] on minilmageNeet [47] and tieredImageNett (50)
datasets with two different backbones [6] 51 in Table 2 As it is shown, our proposed method outperforms state-of-the-art methods on both 5-way 1-shot and 5-way 5-shot tasks.
4.2.2 Data Hyper-Cleaning: Non-convex LL Architecture Structure
Data hyper-cleaning (3] aims to cleanup the corrupted data with noise label. According to [16,, the dataset is randomly split to three disjoint subsets: Drr for training. Dvai for validation and Deest for testing, then fixed proportion of the training samples in De is randomly corrupted.
Following the classical experimental protocol [3] we choose cross-entroy as the loss function L, and the UL and LL subproblem take the form of
y =
Σ (x((x); v:), f(x,y) =
Σ (D.
(o(x))l
(12)
where (u, v;) denotes the data pair and o(x) represents the element-wise sigmoid function on x. We define the hyperparameter equals to the number of training samples. The LL. variables parameterized by y contain the weights
vector being trained to label the noisy data, of which the dimension
and bias of fully connected layers.
Here, the smoothing regularization term defined as ||w||e (||w]| 1/2 where 0 < L.

---

Note that existing methods consider convex single fully connected layer as the LL model, while more complex neural network structure is not applicable. Under our assumption without LLC,, we employ two fully connected layers as the LL network architecture.
Table Reporting results of existing methods for
solving data hyper-cleaning tasks. Acc. and FI score denote the test accuracy and the harmonic mean of the precision and recall, respectively.
MNIST
FashIonMNIST
Method
In Table B we compare IAPTT-GM with IG methods (e.g.. LS, NS) and EG methods (e.g..
Acc.
Fl score
Acc.
Fl score
LS
89.19
85.96
83.15
85.13
RHG, T-RHG [T6).. As it is shown, IAPTT-GN achieves better test performance of both accu- racy and Fl score on two datasets, including MNIST 46 and FaSH [52]. Our theo- retical results also show that the performance im- provement comes from PTT and IA techniques to overcome non-convex LL subproblems.
NS
87.54
89.58
81.37
87.28
RHG
87.90
89.36
81.91
87.12
T-RHG
88.57
89.77
81.85
86.76
BDA
87.15
90.38
79.97
88
IAPTT-GM
90.88
91.57
83.67
90.37
4.3 Evaluations of TA-GM (A) for BLOs under LLC
In addition non-convex BLO problems, also raise concerns about the acceleration strategy of our method with LLC condition. We first consider the following BLO with LLC condition [23]:
min x y2ll* + Ily: - ell s.t. (y1, E arg xEX
yIeR" Yekk" 2 1l - x y yı.
min
(13)
where n 50, X' [- 100, 100] ---((-100 100, 100] C R" and represents the vector whose
elements are all equal to 1. The optimal solution for this problem is x" e, y e, y e.
As shown in Section 3.2] method IA-GM (A) incorporates Nesterov's acceleration strategy for solving Eq. 2 Note that with LLC assumption, IA-GM maintains the convergence property.
IA-CM GMM
JA.MM
Mean UL LOsS
IA GM (A)
Meun Accuir
2.
UL Iteration
UL Iteration
UL Iteration
UL Iteration
(a) Convex toy regression Convex toy regression
(c) Data hyper-clcaning
Data hyper-clcaning
Figure 3: The left two subfigures report the curves of lly - Jy-y"li and ||x xx for IA-GM and IA-GM (A). The figures on the right illustrate the results mean UL loss and accuracy on the convex data hyper-cleaning problems.
As illustrated in the first two figures in Figure 3 IA-GM (A) shows significant improvement of convergence speed on UL and LLI. variables, which verifies the convergence results of Theorem 3..4] under LLC. We further study the convex data hyper-cleaning problem, which simply implements single fully connected layer as the network structure. From the right half of Figure we can easily find that IA-GM (A) also performs better than IA-GM real-world applications.
Conclusion
This paper presents generic first-order algorithmic framework named IAPTT-GM to solve BLO problems with non-convex follower. We introduce two features, initialization auxiliary and pessimistic trajectory truncation operation to guarantee the convergence without the LLC hypothesis and achieves better performance on various applications. Meanwhile, we also validate the performance and speed improvement for BLO with LLC condition.
10

---

Acknowledgments and Disclosure of Funding
This work is partially supported by the National Natural Science Foundation China (Nos. 61922019, 11971220), the National Key R&D Program of China (2020YFB1313500 LiaoNing Revital- ization Talents Program (XLYC1807088) the Shenzhen Science and Technology Program (No. XCCX2020071411470000000000
the Fundamental Research Funds for the Central Universities, the Pacific Institute for the Mathematical Sciences (PIMS), the Stable Support Plan Program of Shenzhen Natural Science Fund (No. 202009251521 28002) and the Guangdong Basic and Applied Basic Research Foundation 2019A15150111 1152.
References
[1] Risheng Liu, Jiaxin Gao, Jin Zhang, Deyu Meng, and Zhouchen Lin. Investigating bi- level optimization for learning and vision from unified perspective: A survey and beyond. arXiv:2101. 1157, 2021.
[2] Risheng Liu, Zi Li, Xin Fan, Chenying Zhao, Hao Huang, and Zhongxuan Luo. Learning deformable image registration from optimization: perspective. modules, bilevel training and beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
[3] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. arXiv:170..01785, 2017.
[4] Takayuki Okuno, Akiko Takeda, and Akihiro Kawana. Hyperparameter learning via bilevel nonsmooth optimization. arXiv::806.000 015200 2018.
[5] Matthew MacKay, Paul Vicol, Jonathan Lorraine, David Duvenaud, and Roger B. Grosse. Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. In ICLR, 2019.
[6] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In ICML, 2018.
[7] Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. NeurIPS, 2019.
[8] Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In ICLR, 2018.
[9] Yaohua Liu and Risheng Liu. Boml: A modularized bilevel optimization library in python for meta learning. In ICMEW. IEEE, 2021.
[10] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: differentiable architecture search. In ICLR, 2019.
[11] Hanwen Liang, Shifeng Zhang, Jiacheng Sun, Xingqiu He, Weiran Huang, Kechen Zhuang, and Zhenguo Li. Darts+: Improved differentiable architecture search with early stopping. arXiv: met.:9999...55 2019.
[12] Xin Chen. Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In CVPR, 2019.
[13] David Pfau and Oriol Vinyals. Connecting generative adversarial networks and actor-critic methods. arXiv preprint arXiv:1610.01945 2016.
[14] Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. In NewrIPS, 2019.
[15] Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-based hyperparameter opti- mization through reversible learning, In ICML, 2015.
[16] Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back- propagation for bilevel optimization. In AISAATS, 2019.

---

[17] Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-leaming algorithms. arXiv:1803.02999 2018.
[18] Alex Nichol and John Schulman. Reptile: scalable metalearning algorithm. arXiv:/803.02999 2(2):1, 2018.
[19] Ke Li and Jitendra Malik. Learning to optimize. arXiv:1606.01885, 2016.
[20] Yoonho Lee and Seungjin Choi. Meta-learning with adaptive layerwise metric and subspace. CoRR, abs/1801.055555 2018.
[21] Eunbyung Park and Junier B Oliva. Meta-curvature. arXiv: 2019.
[22] Sebastian Flennerhag, Andrei A Rusu, Razvan Pascanu, Francesco Visin, Hujun Yin, and Raia Hadsell. Meta-learning with warped gradient descent. 1XXiv:/909.0000 2019.
[23] Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. In ICMI, 2020.
[24] Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. general descent aggregation framework for gradient-based bi-level optimization, 2021.
[25] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Nonasymptotic analysis and faster algorithms. arXiv:2010.07902 2020.
[26] Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complexity of hypergradient computation. In ICML, 2020.
[27] Kaiyi Ji and Yingbin Liang. Lower bounds and accelerated algorithms for bilevel optimization. arXiv:2102.0399622 2021.
[28] Fabian Pedregosa. Hyperparameter optimization with approximate gradient. arXiv:1602.02355, 2016.
[29] Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In A/STATS, 2020.
[30] Iya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In ICMI., 2013.
[31] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-leaming for fast adapta- tion of deep networks. In ICML, 2017.
[32] Pan Zhou, Xiaotong Yuan, Huan Xu, Shuicheng Yan, and Jiashi Feng. Efficient meta learning via minibatch proximal update. 2019.
[33] Liam Collins, Aryan Mokhtari, and Sanjay Shakkottai. Task-robust aodel-agnostic meta- learning. 2020.
[34] Ren Wang, Kaidi Xu, Sijia Liu, Pin-Yo Yu Chen, Tsui- Weng, Chuang Gan, and Meng Wang. On fast adversarial robustness adaptation in model-agnostic meta-learning. arXiv:2102.10454 2021.
[35] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Generalization of model-agnostic meta-learning algorithms: Recurring and unseen tasks. arXiv:2102.03832, 2021.
[36] Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning or feature reuse? towards understanding the effectiveness of maml. In ICLR, 2019.
[37] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. On the convergence theory of gradient- based model-agnostic meta-learning algorithms. In SIATATS, 2020.
[38] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Theoretical convergence multi-step -odel-ag meta-learning. arXiv e-prints, pages arXiv-2002, 2020.
12

---

[39] Kaiyi Ji, Jason D Lee, Yingbin Liang, and H. Vincent Poor. Convergence of meta-learning with task-specific adaptation over partial parameters. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, NeurIPS, 2020.
[40] Risheng Liu, Xuan Liu, Shangzhi Zeng, Jin Zhang, and Yixuan Zhang. Value-function-basee sequential minimization for bi-level optimization, 2021.
[41] Jane Ye, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. Difference of convex algorithms for bilevel programs with applications in hyperparameter selection. arXi::2102.0900 0900000,,, 2021.
[42] Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A celuu-function-beee interior-point method for non-convex bi-level optimization. In JCML, 2021.
[43] Amir Beck. First-order methods in optimization. SIAM, 2017.
[44] Yurii E Nesterov. A method for solving the convex programming problem with convergence rate o (1/k* 2). Dokl. akad. nauk Sssr, volume 269, pages 543-547, 1983.
[45] Amir Beck and Mare Teboulle. A fast iterative shrinkage-thresholling algorithm for linear inverse problems. 2009.
[46] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE,
1998.
[47] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. In NeurlPS, 2016.
[48] Jake Snell, Kevin Swersky, and Richard S Zemel. Prototypical networks for few-shot learning. 17X3v:1003.05177 2017.
[49] Flood Sung, Yongxin Yang, Li Zhang, Tao Xiang, Philip HS Torr, and Timothy M Hospedales. Learning to compare: Relation network for few-shot learning. CVPR, 2018.
[50] Mengye Ren, Eleni Triantafillou, Sachin Ravi, Jake Snell, Kevin Swersky, Joshua B Tenen- baum, Hugo Larochelle, and Richard S Zemel. Meta-leamiin for supissuer few-shot classification. arXiv: 2018.
[51] Boris N Oreshkin, Pau Rodriguez, and Alexandre Lacoste. Tadam: Task dependent adaptive metric for improved few-shot learning.
2018.
[52] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion- a novel image dataset for benchmarking machine learning algorithms. drXiv:1708.07747.222 2017.
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] Please refer to Section I.I for detailed description
corresponding to the abstract.
(b) Did you describe the limitations of your work? [No]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(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] Please refer to Section
(b) Did you include complete proofs of all theoretical results? [Yes] We put most of the detailed calculation process in the supplementary materials.
3. If you experiments...
13

---

(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [Yes] Instruction for the code, datasets are provided in the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Information about the dataset and hyperparameters for numerical experiments can be found in the supplemental material.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(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] We specify the detailed configuration of computing devices, GPUs in the supplementary materials.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent obtained from people whose data you' 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] We conduct all the experiments based on public data.
5. If you used crowdsourcing or 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 describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "bvXYyOxG72G", "reviewer": "Reviewer_hf2w", "summary": "This paper proposes a bilevel optimization method based on unrolled gradient-descent iterations of the lower-level (LL) problem, while providing a theoretical connection between the ideal bilevel optimization and the unrolled one when LL problem might not be convex. The main idea is two-fold: Regarding the initial point (i.e., z) of LL variable as another variable in the UL problem, and taking the pessimistic value from the unrolled iteration, i.e., max_k F(x, y_k(x, z) ). The theoretical derivation presents that the ideal bilevel problem (min phi(x)) is asymptotically equivalent to the unrolled version (min phi_K(x, z)). The resulting algorithm is very simple: (1) perform a few unrolled steps (with computational graph) for LL, (2) take the pessimistic estimate (y_k) from the steps, (3) and perform gradient descent for x and z for the UL problem based on the y_k(x, z). The paper also proposes a Nesterov version (for LL iterations). The proposed method shows state-of-the-art performance for a toy problem and two applications.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "++ Relevant contribution for an important problem: Bilevel optimization with nonconvex objectives is popularly used nowadays. Solving this with unrolled iterations has been frequently used in the literature, but without any apparent theoretical guarantees. Providing this is definitely relevant.\n\n-- Discrepancy between the theory and the algorithm: The most crucial problem I think is that the theory and the algorithm are describing different things. The convergence guarantee to global optima is true only because the inf operators in all the theoretical derivation are in fact global optimizers. However, the optimizer for the UL problem used in the proposed algorithm is actually a local one (projected gradient descent). For example, let us suppose the following case: F(x,y) = x + 1/2 y + cos(y), S(x) = argmin_y 1/2 y + cos(y), -1 <= x <= 1, -2pi <= y <= 2pi, and all the variables are scalars. In this case, if we pick a wrong z (and hyperparameters), then Algorithm 1 will converge to a non-global optimum. Moreover, the derivation says nothing about the convergence to local optima. This suggests that the proposed method excelling in the experiments might be not because of the guarantees provided in the paper. This is somewhat misleading and can confuse readers. I suggest the authors address this limitation in the main paper.\n\n[After rebuttal]\nMy main concern has been well addressed in the authors' response. Providing the local solution convergence will be definitely helpful for the completeness. I'm satisfied with the response and I stay with my original score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Explaining the above limitation (the discrepancy) can be helpful for the completeness of the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "PxaRSo4lnKn", "reviewer": "Reviewer_b25m", "summary": "This paper presents a first-order algorithm for solving bilevel optimization problems where the lower-level problem is non-convex. The proposed algorithm, named as IAPTT-GM, in my understanding, is roughly alternating projected gradient descent in the upper level and lower level variables, combined with two key ideas, namely initialization auxiliary and pessimistic trajectory truncation.\n\nThis paper provides theoretical analysis of IAPTT-GM, supported by sufficient numerical experiments, both on toy problems and real datasets. \n\nThis paper is well motivated and well written. The theoretical part is clean and concise, while the numerical experiments are well conducted, together with texts to describe the main takeaways.\n\nIn general, I like this paper and want to see it published. However, I am a bit skeptical about the theory. I may downgrade my score if there are severe theoretical issues. See main review.", "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 biggest confusion for me is, Theorem 3.1 seems to be so strong that it violates NP-hardness results of generic non-convex problems.\n\nThe bilevel optimization problem considered in this paper, neither has a convex upper level problem, nor has a convex lower level problem. Therefore, to me the problem is obviously non-convex and NP-hard, not to mention about the extra difficulty imposed by the bilevel structure. In addition, the proposed algorithm is a first order algorithm.  However, Theorem 3.1 claims that the algorithm can find a \"solution\" to the upper level problem.  How can this be possible? I wonder what does the term \"solution\" mean in this context, does it mean a first-order stationary point, or does it mean the \"globally optimal solution\"?  Intuitively, the best thing one can hope for first order methods is convergence to a first-order stationary point. So this result is a bit too strong for me. Am I missing some strong assumptions of Theorem 3.1?  I'd like the authors to clarify this point. I will also read the reviews. from other reviewers to see if they have similar concerns.\n\nThe other major comment is, how efficient is the proposed IAPTT-GM algorithm, compared with other methods? From the description of Algorithm 1, it seems many inner and outer iterations are required. Could the authors, in the experimental section, comment more on the runtime and efficiency of IAPTT-GM when compared with other baselines?\n\nBilevel programming is an active area of research in the mathematical programming community. I also wonder if the authors could draw connections to literature in that field when presenting related works. In particular, the value function approach seems to be a preferred approach for solving such problems. For example, see [Ref1] and references therein (the authors of [Ref1] seem to have made great efforts along this vein).\n\n[Ref1]: Ye, Jane J., Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. \"Difference of convex algorithms for bilevel programs with applications in hyperparameter selection.\" arXiv preprint arXiv:2102.09006 (2021).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "8qGvhgJPLmc", "reviewer": "Reviewer_BsfL", "summary": "This work proposes a truncated unrolling type method for solving a bilevel optimization problem with non-convex lower-level problem and the convergence of the proposed method is also shown. Compared to the results in the existing literature, the convergence analysis in this work does not require any convexity assumptions on both upper level and lower-level objective functions. Efficiency of the proposed method is shown in the numerical experiments of artificial problems and real application problems.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work proposes a truncated unrolling type method for solving a bilevel optimization problem with non-convex lower-level problem and the convergence of the proposed method is also shown. Compared to the results in the existing literature, the convergence analysis in this work does not require any convexity assumptions on both upper level and lower-level objective functions. Efficiency of the proposed method is shown in the numerical experiments of artificial problems and real application problems.\n\nI noticed that two interesting ideas, namely, Initialization Auxiliary and Pessimistic Trajectory Truncation, are applied in the designing of the proposed method. Initialization Auxiliary is a well-used technique in meta-learning, but the Pessimistic Trajectory Truncation technique is quite new. Thanks to the Pessimistic Trajectory Truncation technique, the proposed method admits a convergence guarantee, meanwhile, the computation cost in the numerical implementation is reduced. I think that such Pessimistic Trajectory Truncation technique may bring something new to other bilevel optimization algorithm designs.\n\nCons:\n1. The convergence result of the proposed method is based on the sequence x_K being global minimum of the approximated subproblems. Since the approximation is just with respect to function values, I understand that it is usually too ambitious to establish the stationary points convergence in such a general case (nonconvex LL) considered in this paper. However, since the subproblems are always nonconvex, this referee would like to ask is it possible to derive convergence analysis for the case where x_K are local minimum. \n2. I understand that the LL compact set constraint Y is imposed for theoretical convergence analysis. The authors should clarify that how to set and deal with this extra Y in numerical experiments. \n3. In section 3.2, the authors embed the Nesterov’s acceleration dynamics into their algorithm. It seems that the convergence analysis does not rely on any particular features of the Nesterov’s acceleration dynamics. This referee feels that this part can be generalized to other acceleration dynamics.\n4. The LL subproblem is now set to be differentiable. This referee wonder if the general non-differentiable case can be considered to capture more real applications. \n5. In the numerical experiments, the authors conduct a comparison for the proposed methods with and without Pessimistic Trajectory Truncation on an artificial problem. Empirically, the Pessimistic Trajectory Truncation technique brings a great improvement. I was wondering whether such an improvement also exists for real application problems.\n\n**Final Comment (Post Rebuttal)** \n\nI acknowledge that I read and other reviewers' comments and authors' responses. I would like to keep my score as most concerns of mine have been well addressed.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "N.A.", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "2arglpb3hU", "reviewer": "Reviewer_pFSa", "summary": "The paper introduces a gradient-based bilevel optimization algorithm called IAPTT-GM that does not require the non-convex inner-level assumption. Specifically, the authors propose two methods: (1) initialization auxiliary that guides the optimization dynamics and (2) pessimistic truncation operation to build theoretical convergence. The authors theoretically show convergence of IAPTT-GM that does not assume the non-convexity of the inner-level problem and empirically show that the proposed method has improved performance on few-shot classification and hyper cleaning compared to previous approaches.\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": "1. Originality\n * The task of solving bilevel optimization that does not require the lower-level singleton (LLS) assumption has been explored in previous works (e.g. [1]).\n*  However, I am not aware of the pessimistic trajectory truncated method to solve this particular issue and I believe that the algorithms & theoretical analysis presented in the paper are interesting and novel. \n\n2. Quality\n* The submission is technically sound. I checked the derivation and proofs and they look correct.\n* The potential limitations of the proposed approach are not addressed in the paper. For example, what would be the computational & memory overhead compared to previous approaches?\n\n3. Clarity: \n * The manuscript is overall well written and easy to understand. However, the paper uses several abbreviations that are not properly defined (e.g. UL, LL, LLS, LLC). It would be much helpful to properly define these abbreviations. Having a table describing these abbreviations would be helpful.\n* Moreover, it would be helpful to summarize all mathematical notation used in the paper. Some notations have quite different interpretations with a subscript which makes proofs hard to read.\n\n4. Significance: \n * Gradient-based bilevel optimization that does not require the lower-level singleton (LLS) assumption is a recently emerging topic in the literature and I believe that result is important. It is relevant to the Neurips community.\n\n5. Additional Comments:\n* I don't exactly understand line 150: \"The pessimistic max operation always results in a favorable trajectory truncation smaller than K\". What would be the reason behind this statement?\n\n6. Minor Comments:\n* For gradient-based methods, I feel like the argmin formulation in equation 2 is weird. Can the rational reaction set S(x) map a solution of the local minima? Shouldn't the version that incorporates local minima (e.g. [2]) be more correct?\n* In line 122, relevant references on convergence theory of non-convex first-order optimization would be helpful.\n* In line 136, the footnote should be inside the comma.\n* Introducing variables like T, K would be helpful in describing algorithm 1.\n* I feel like showing the baseline algorithm next to algorithm 1 would help readers to better understand contributions made in this paper.\n\n[1] Liu, Risheng, et al. \"A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton.\" International Conference on Machine Learning. PMLR, 2020.\n\n[2] Fiez, Tanner, Benjamin Chasnov, and Lillian J. Ratliff. \"Convergence of learning dynamics in stackelberg games.\" arXiv preprint arXiv:1906.01217 (2019).\n\n------\nThank you for your clarifications. I acknowledge that I read and other reviewers' comments and authors' responses.\n\nI agree that properly defining abbreviations and showing the baseline algorithm would further add clarity to the paper (as well as the new assumption suggested by the authors). Given that these modifications would be made in the manuscript, I will increase my score to 7 (from 6).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "While the authors did not address the potential negative social impact of their work, I believe that it is not necessary for this submission.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a truncated unrolling type method for solving a bi-level optimization with non-convex lower-level. It contains two interesting ideas, namely, Initialization Auxiliary and Pessimistic Trajectory Truncation. The proposed method admits a convergence guarantee, meanwhile, the computation cost is reduced. The techniques and analytic framework are novel, and enhance the understanding of gradient-based bi-level optimization methods. In summary, this work will possibly inspire some new bi-level optimization algorithms and technical analysis.
Decision: Accept (Spotlight)