Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond
Year: 2021

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.

heading: 1 Introduction
text: Bi-Level Optimization (BLO) has been widely used to formulate problems in the field of deep learning [1, 2], especially for hyperparameter optimization [3, 4, 5], meta learning [6, 7, 8, 9], neural architecture search [10, 11, 12], adversarial learning [13], and reinforcement learning [14], etc. BLO aims to tackle nested optimization structures appearing in applications, which has emerged as a prevailing optimization technique for modern machine learning tasks with underlying hierarchy. In the last decade, a large number of BLO methods have been proposed to address different machine learning tasks. In fact, Gradient Methods (GMs), which can effectively handle BLO 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 the evolution path of the dynamic system starting from a given initial point of the LL variable. The gradient of the Upper-Level (UL) variable can be directly calculated by automatic differentiation
*Corresponding author
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
based on the trajectory of LL variable. This class of methods can be further divided into three types, namely, recurrence-based EG (e.g., [3, 15, 6, 16, 10]), initialization-based EG (e.g., [17, 18]) and proxy-based EG methods (e.g., [19, 20, 21, 22]), differing from each other in the way of accessing the gradient of constructed dynamic trajectory. While most of this type of works assume the LLC 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, [23] 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 analysis has been recently witnessed see, e.g., [25, 26, 27].
Implicit Gradient Methods for BLOs. This type, also known as implicit differentiation [28, 7, 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 a 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.e., 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 a great influence on the training speed and performance [30]. As the most representative work in recent years, Model-Agnostic Meta-Learning (MAML) [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 [32, 33, 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, 38, 39] give comprehensive study on 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 are given based on 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.
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-convex program [41], which is numerically solvable. Typically, by reformulating the BLO into an Inner Single Bi-level (ISB) optimization problem with value-function approach, a gradient-based interior-point method name BVFIM [42] is proposed to solve the BLO tasks, which effectively avoids the expensive Hessian-vector and Jacobian-vector products. Generally speaking, the value-function does not admit an explicit form, and is always nonsmooth, non-convex and with jumps.

heading: 1.1 Our Motivations and Contributions
text: As mentioned above, some theoretical progresses have long been witnessed in diversified learning areas, but for most existing BLO methods, extra restrictive assumptions (e.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 a simplified problem structure. Unfortunately, it has been well recognized that LL non-convexity frequently appears in a variety of applications, e.g., sparse `q 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 a series of new techniques to address BLO with non-convex LL problems, which have been frequently appeared in various learning applications.
In particular, by introducing an Initialization Auxiliary (IA) to the LL optimization dynamics and operating a Pessimistic Trajectory Truncation (PTT) strategy during the UL approximation, we construct a 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 of 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, we establish the first strict convergence guarantee for gradientbased 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 a 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) or coupled network structures (e.g., data hyper-cleaning).

heading: 2 The Proposed Algorithmic Framework
text: In this work, we consider the BLO problem in the form:
min x∈X ,y
F (x,y), s.t. y ∈ S(x), (1)
where x ∈ Rn,y ∈ Rm are UL and LL variables respectively, and S(x) denotes the set of solutions of the LL problem, i.e.,
S(x) := arg min y∈Y f(x,y), (2)
where f is differentiable w.r.t. y. To ensure the BLO model in Eq. (1) is well-defined, we assume that S(x) is nonempty for all x ∈ 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. (1). The mechanism of a classical dynamics-embedded 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 yK(x) is accessed by operations repeatedly performed by K − 1 steps parameterized by UL variable x
yk+1(x) = yk(x)− s∇yf(x,yk(x)), k = 0, · · · ,K − 1, (3)
where s is a step size, and y0 is a fixed initial value.

heading: 2.1 Initialization Auxiliary
text: Embedding the dynamical iterations into the UL problem returns the approximate version F (x,yK(x)). As long as ∇yf(x,yK(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 assumptions 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 in an approximation of the bi-level problem, we propose a new gradient scheme to solve BLO in Eq. (1) without LLC restriction. Specifically, we let K be a prescribed positive integer and construct the following approximation yK(x, z) of the LL solution drawn from projected gradient descent iterations
y0(x, z) = z,
yk+1(x, z) = ProjY(yk(x, z)− α k y∇yf(x,yk(x, z))), k = 0, · · · ,K − 1,
(4)
where {αky} is a sequence of steps sizes. We next embed the dynamical iterations yk(x, z) into max1≤k≤K {F (x,yk(x, z))}, which can be regarded as a pessimistic trajectory truncation of the UL objective. The mechanism of the above scheme, in comparison, accesses the approximation parameterized by UL variable x and LL initial point y0. 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 a “bad” initial point y0 cannot return a desired point in the LL solution set, simultaneously optimizing the UL objective. To overcome such a difficulty, instead of using a fixed initial value, we introduce an initialization auxiliary variable z. Therefore, when it comes to solving the UL approximation problems, together with the UL variable x, the auxiliary variable z is also updated and hence optimized. As a consequence, we may search for the “best” initial value, starting from which the gradient descent steps approach a solution to the BLO in Eq. (1), i.e., a point in the LL solution set, simultaneously minimizing the UL objective.
Algorithm 1 The Proposed IAPTT-GM
1: Initialize x0 and z0. 2: for t = 0→ T − 1 do 3: y0 = zt. 4: for k = 0→ K − 1 do 5: % LL Updating with xt and zt 6: yk+1 = ProjY(yk − αky∇yf(xt,yk)). 7: end for 8: % Pessimistic Trajectory Truncation 9: k̄ = arg maxk{F (x,yk)}Kk=1.
10: % UL Updating with yk̄(x, z) 11: xt+1 = ProjX (x
t − αx∇xF (xt,yk̄)). 12: % Initialization Updating with yk̄(x, z) 13: zt+1 = ProjY(z
t − αz∇zF (xt,yk̄)). 14: end for

heading: 2.2 Pessimistic Trajectory Truncation
text: This is a striking feature of our algorithm that significantly differs from existing methods and leads to some new convergence results without LLC. The motivation for the design of pessimistic trajectory truncation comes again from convergence theory of non-convex firstorder optimization methods. It is understood that when LL is non-convex, Rα(x,yK(x, z)) may not uniformly converge w.r.t. x and z, whereRα(x,y) is the proximal gradient residual mapping defined as Rα(x,y) := y − ProjY (y − α∇yf(x,y)) 1, which can be used as a measurement of the optimality of LL problem in Eq. (2). Thus a direct embedding of yK(x, z) into UL objective F (x,y) may not necessarily provide an appropriate approximation. Fortunately, it is also understood that, for each x ∈ X , z ∈ Y and K > 0, there exists at least a K̃ such that along the selection yK̃(x, z),Rα(x,yK̃(x, z)) uniformly converges to zero w.r.t. x and z, as K tending infinity.
However, in general, it is too ambitious to expect an explicit identification of the exact selection yK̃(x, z). Alternatively, we consider a pessimistic strategy, minimizing the worst case of all selections of {yk(x, z)}, i.e., max1≤k≤K {F (x,yk(x, z))}. By doing so, we successfully reach a good approximation. In addition to the theoretical convergence, we also benefit from this pessimistic strategy in a 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, as shown in the numerical experiments.
To conclude this section, we state the complete IAPTT-GM in Algorithm 1. Note that K and T represent the numbers of inner and outer iterations, respectively.

heading: 3 Theoretical Investigations
text: With the purpose of studying the convergence of dynamics-embedded gradient method for BLO without LLC, we involve two signature features in our algorithmic design, i.e., 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.
1Rα(x,y) reduces to α∇yf(x,y) when Y is taken as Rm.

heading: 3.1 Convergence Analysis of IAPTT-GM for BLO with Non-convex Followers
text: In this part, we conduct the convergence analysis of the IAPTT-GM for solving BLO in Eq. (1) without LLC. Before presenting our main convergence results, we introduce some notations related to BLO. With introduced function ϕ(x) := infy∈S(x) F (x,y), the BLO in Eq. (1) can be rewritten as
min x∈X ϕ(x). (5)
With given K ≥ 1 and defining ϕK(x, z) := maxk {F (x,yk(x, z))} with {yk(x, z)} defined in Eq. (4), our proposed IAPTT-GM generates sequence {(xt, zt)} for solving following approximation problem to BLO in Eq. (5),
min x∈X ,z∈Y ϕK(x, z). (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 : Rn × Rm → R are continuous functions.
(2) ∇f is continuous and ∇yf is Lf Lipschitz continuous with respect to y for any x ∈ X .
(3) X and Y are convex compact sets.
(4) S(x) is nonempty for any x ∈ X .
(5) For any (x̄, ȳ) minimizing F (x,y) over constraints x ∈ X ,y ∈ Y and y ∈ Ŝ(x), it holds that ȳ ∈ S(x).
Note that Ŝ(x) denotes the set of LL stationary points, i.e., Ŝ(x) = {y ∈ Y|0 = ∇yf(x,y) + NY(y)}. It should be noticed that y ∈ Ŝ(x) if and only ifRα(x,y) = 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 in the preceding section, for each x ∈ X , z ∈ Y and K > 0, there exists at least a K̃ such that along the selection yK̃(x, z), Rα(x,yK̃(x, z)) uniformly converges to zero w.r.t. x and z, as K tending infinity. We next specifically show the existence of such index K̃. To this end, K̃ can be chosen by optimizing ‖Rα(x,yk(x, z))‖ among the indices k = 0, 1, ...,K. In particular, as stated in the following lemma, ‖Rα(x,yK̃(x, z))‖ uniformly decreases with a 1√ K
rate on X × Y as K increases.
Lemma 3.1 Let {yk(x, z)} be the sequence defined in Eq. (4) with αky ∈ [αy, αy] ⊂ (0, 2Lf ), there exists Cf > 0 such that
min 0≤k≤K ‖Rαy(x,yk(x, z))‖ ≤ Cf√ K + 1 , ∀x ∈ X , z ∈ Y. (7)
As shown in the Appendix, the proof of Lemma 3.1 for the existence cannot offer us an explicit identification of the exact selection of K̃. Alternatively, we construct the approximation by a pessimistic trajectory truncation strategy, minimizing the worst case of all selections of {yk(x, z)}, i.e., ϕK(x, z). By further solving the approximated problems minϕK(x, z), we shall provide a lower bound estimation for the optimal value of the BLO problem in Eq. (5).
Lemma 3.2 Let (xK , zK) ∈ argmin x∈X ,z∈Y ϕK(x, z), then
ϕK(xK , zK) ≤ inf y∈Ŝ(x) F (x,y), ∀x ∈ X . (8)
Upon together with the uniform convergence result in Lemma 3.1, the gap between the lower bound provided by minϕK(x, z) 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,
we need the continuity of Rα(x,y). Indeed, it follows from [43, Theorem 6.42] that ProjY is continuous. Combined with the assumed continuity of∇yf(x,y), we get the desired continuity of Rα(x,y) immediately.
Theorem 3.1 Let {yk(x, z)} be the sequence generated by Eq. (4) with αky ∈ [αy, αy] ⊂ (0, 2Lf ), and (xK , zK) ∈ argmin
x∈X ,z∈Y ϕK(x, z), then we have:
(1) Any limit point x̄ of the sequence {xK} is the solution to BLO in Eq. (1), that is x̄ ∈ argmin x∈X ϕ(x).
(2) inf x∈X ,z∈Y ϕK(x, z)→ inf x∈X ϕ(x) as K →∞.
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 of the bilevel problem in Eq. (1).
Theorem 3.2 Let {yk(x, z)} be the sequence generated by Eq. (4) with αky ∈ [αy, αy] ⊂ (0, 2Lf ), and (xK , zK) be a local minimum of ϕK(x, z) with uniform neighborhood modulus δ > 0, i.e.,
ϕK(xK , zK) ≤ ϕK(x, z), ∀(x, z) ∈ Bδ(xK , zK) ∩ X × Y. Then we have that for any limit point (x̄, z̄) of the sequence {(xK , zK)}, there exists a limit point ȳ of the sequence {yK(xK , zK)} such that ȳ ∈ Ŝ(x̄) and (x̄, ȳ) satisfies that there exists δ̃ > 0 such that
F (x̄, ȳ) ≤ F (x, z), ∀(x, z) ∈ Bδ̃(x̄, z̄) ∩ {x ∈ X , z ∈ Y | z ∈ Ŝ(x)}.

heading: 3.2 Theoretical Findings of IA-GM (A) for BLO with LLC
text: A byproduct of our study, which has its own interest, is 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 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 to the LLC setting, Rα(x,yK(x, z)) may uniformly converge to zero w.r.t. UL variable x and auxiliary variable z, thus the pessimistic trajectory truncation operation can be removed. Subsequently, we slightly simplify our algorithm that k̄ is simply taken as K, thus the approximation objective admits a succinct form, i.e., F (x,yK(x, z)).
In summary, by constructing yk(x, z) through following Nesterov’s acceleration dynamics,
y0(x, z) = z, t0 = 1, tk+1 = 1 +
√ 1 + t2k
2 , k = 0, · · · ,K − 1,
uk+1(x, z) = yk+1(x, z) + ( tk − 1 tk+1 ) (yk+1(x, z)− yk(x, z)), k = 0, · · · ,K − 1,
yk+1(x, z) = ProjY ( uk(x, z)− α∇yf(x,uk(x, z)) ) , k = 0, · · · ,K − 1,
(9)
where α > 0 is the step size, we propose an accelerated Gradient-based Method with Initialization Auxiliary, named IA-GM(A), via minimizing the approximation objective function,
min x∈X ,z∈Y φK(x, z) := F (x,yK(x, z)).
The detailed description of the proposed IA-GM(A) is stated in the Supplemental Material.
We suppose Assumption 3.1(1)-(4) are satisfied throughout this subsection. The convergence result of our proposed IA-GM(A) with LLC assumption is given as below.
Theorem 3.3 Assume that the generated sequence {yk(x, z)} satisfies that yk(x, z) ∈ Y , and yk(x, z) = z for any z ∈ S(x), x ∈ X , and either
(a) for any > 0, there exists k( ) > 0 such that whenever K > k( ), sup
x∈X ,z∈Y {f (x,yK(x, z))− f∗(x)} ≤
whenever K > k( ), or
(b) there exists α > 0, for any > 0, there exists k( ) > 0 such that, sup
x∈X ,z∈Y ‖Rα (x,yK(x, z))‖ ≤ .
Let (xK , zK) ∈ argmin x∈X ,z∈Y φK(x, z) := F (x,yK(x, z)), then we have
(1) any limit point x̄ of the sequence {xK} satisfies that x̄ ∈ argmin x∈X ϕ(x), i.e., x̄ is the solution
to BLO (1).
(2) inf x∈X ,z∈Y φK(x, z)→ inf x∈X ϕ(x) as K →∞.
Next, we show that the Nesterov’s acceleration dynamics satisfy all the assumptions required in the above convergence theorem.
Theorem 3.4 Let {yk(x, z)} be the sequence generated by Nesterov’s acceleration dynamics in Eq. (9) with α = 1Lf . Then {yk(x, z)} satisfies all the assumptions required by Theorem 3.3.
Remark 3.1 Our convergence result Theorem 3.3 is not only for yk generated by Nesterov’s acceleration dynamics. It is a general convergence result that is applicable for the case where yk 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.

heading: 4 Experimental Results
text: 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 are caused by non-convex regularization and neural network structures. In addition, we further validate the performance of the accelerated version (i.e., IA-GM (A)) under LLC with numerical examples and data hyper-cleaning tasks 2.

heading: 4.1 Numerical Verification
text: To verify the convergence property under assumptions provided in Section 3, we consider the following non-convex BLO problem:
min x∈X ,y∈R x+ xy, s.t. y ∈ argmin y∈Y − sin(xy), (10)
where X = [1, 10] and Y = [−2, 2]. Given any x ∈ X , it satisfies argminy∈Y − sin(xy) = {(2kπ + π/2) /x | k ∈ Z} ∩ Y and miny∈Y − sin(xy) = −1. The unique solution is (x∗, y∗) = (11π/4,−2). It should be noted that the LL problem of Eq. (10) 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 1, we separately compared IAPTT-GM with EG methods such as RHG [3], BDA [23], IG methods such as LS [28], NS [7] and IA-GM. From Figure 1.(a) to Figure 1.(b), we can observe that different initialization points only slightly affect the convergence speed of IAPTT-GM. With initialization points distant from (x∗, y∗), IAPTT-GM can still achieve optimal solution of UL variables and optimal objective value, while other methods fail to converge to the true solution. In Figure 1.(g) and Figure 1.( h), we compare the performances of IAPTT-GM with IA-GM, which has no convergence guarantee without LLC assumption. As shown, IA-GM fails to converge to the true solution eventually, which validates the necessity of PTT technique and the effectiveness of IAPTT-GM.
2The code is available at http://github.com/vis-opt-group/IAPTT-GM.
Runtime and Memory Analysis. In Figure 2, we report the average steps k̄ of IAPTT-GM for PTT and the iterative speed as the UL iteration increases. In comparison with IA-GM, which uses default K for the LL optimization loop, the changing k̄ for IAPTT-GM leads to less iterations for the backward recurrent propagation and thus faster iterative updates during optimization. Although IA introduces additional variables and iterations, the PTT technique can choose a small k̄, thus shortens the back-propagation trajectory for computing the UL gradient (see Figure 2). As can be seen in Table 1, the memory required by our IAPTT-GM is less than NS, LS, and BDA and the same as 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.

heading: 4.2 BLO with Non-convex Followers in Different Application Scenarios
text: To cover various real-world BLO application scenarios, we 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 hyper-cleaning tasks, respectively. Please note that the set constraint Y is only used to guarantee the completeness of our theoretical analysis in Section 3. In application scenarios, we can just consider the constraint as an extra large set, so that all the variables are automatically in this feasible set. In this way, it is natural to ignore the projection operation in practical computations.

heading: 4.2.1 Few-Shot Classification: Non-convex LL Objective
text: 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 to 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 yj) for j-th task. Define the meta training dataset as D = {Dj}, where Dj = Djtr ⋃ Djval 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., `q regularization with 0 < q < 1, have shown effectiveness to help the LL model converge and avoid over-fitting, existing methods can only guarantee the convergence when q ≥ 1, thus almost provide no support for non-convex objectives. We consider the LL subproblem with non-convex loss functions by adding `q regularization 3. Then the UL and LL subproblems can be written as
F ( x, { yj }) = ∑ j ` ( x,yj ;Djval ) , f ( x, { yj }) = ∑ j ` ( x,yj ;Djtr ) + ‖yj‖q. (11)
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 miniImageNet [47] and tieredImageNet [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.

heading: 4.2.2 Data Hyper-Cleaning: Non-convex LL Architecture Structure
text: 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: Dtr for training, Dval for validation and Dtest for testing, then a fixed proportion of the training samples in Dtr is randomly corrupted. Following the classical experimental protocol [3], we choose cross-entroy as the loss function `, and the UL and LL subproblem take the form of
F (x,y) = ∑
(ui,vi)∈Dval
` (y(x);ui,vi) , f(x,y) = ∑
(ui,vi)∈Dtr
[σ(x)]i` (y;ui,vi) , (12)
where (ui,vi) denotes the data pair and σ(x) represents the element-wise sigmoid function on x. We define the hyperparameter x as a vector being trained to label the noisy data, of which the dimension equals to the number of training samples. The LL variables parameterized by y contain the weights and bias of fully connected layers.
3Here, we use the smoothing regularization term defined as ‖w‖q = (‖w‖2 + ‖ε‖2)q/2, where 0 < q < 1.
Note that existing methods consider convex a 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.
In Table 3, we compare IAPTT-GM with IG methods (e.g., LS, NS) and EG methods (e.g., RHG, T-RHG [16]). As it is shown, IAPTT-GM achieves better test performance of both accuracy and F1 score on two datasets, including MNIST [46] and FashionMNIST [52]. Our theoretical results also show that the performance improvement comes from PTT and IA techniques to overcome non-convex LL subproblems.

heading: 4.3 Evaluations of IA-GM (A) for BLOs under LLC
text: In addition to non-convex BLO problems, we 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∈X ‖x− y2‖4 + ‖y1 − e‖4, s.t. (y1,y2) ∈ arg min y1∈Rn,y2∈Rn 1 2 ‖y1‖2 − x>y1, (13)
where n = 50, X = [−100, 100] × · · · [−100, 100] ⊂ Rn, and e represents the vector whose elements are all equal to 1. The optimal solution for this problem is x∗ = e,y∗1 = e,y ∗ 2 = e.
As shown in Section 3.2, our method IA-GM (A) incorporates Nesterov’s acceleration strategy for solving Eq. (2). Note that with LLC assumption, IA-GM maintains the convergence property.
As illustrated in the first two figures in Figure 3, IA-GM (A) shows significant improvement of convergence speed on UL and LL 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 3, we can easily find that IA-GM (A) also performs better than IA-GM on real-world applications.

heading: 5 Conclusion
text: This paper presents a 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.
Acknowledgments and Disclosure of Funding
This work is partially supported by the National Natural Science Foundation of China (Nos. 61922019, 11971220), the National Key R&D Program of China (2020YFB1313503), LiaoNing Revitalization Talents Program (XLYC1807088), the Shenzhen Science and Technology Program (No. RCYX20200714114700072), 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. 20200925152128002) and the Guangdong Basic and Applied Basic Research Foundation 2019A1515011152.

Review summaries:
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.

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.

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. 

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.  This paper provides theoretical analysis of IAPTT-GM, supported by sufficient numerical experiments, both on toy problems and real datasets.   This 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.  In 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.