A General Descent Aggregation Framework for Gradient-based Bi-level Optimization

In recent years, a variety of gradient-based methods have been developed to solve Bi-Level Optimization (BLO) problems in machine learning and computer vision areas. However, the theoretical correctness and practical effectiveness of these existing approaches always rely on some restrictive conditions (e.g., Lower-Level Singleton, LLS), which could hardly be satisfied in real-world applications. Moreover, previous literature only proves theoretical results based on their specific iteration strategies, thus lack a general recipe to uniformly analyze the convergence behaviors of different gradient-based BLOs. In this work, we formulate BLOs from an optimistic bi-level viewpoint and establish a new gradient-based algorithmic framework, named Bi-level Descent Aggregation (BDA), to partially address the above issues. Specifically, BDA provides a modularized structure to hierarchically aggregate both the upper- and lower-level subproblems to generate our bi-level iterative dynamics. Theoretically, we establish a general convergence analysis template and derive a new proof recipe to investigate the essential theoretical properties of gradient-based BLO methods. Furthermore, this work systematically explores the convergence behavior of BDA in different optimization scenarios, i.e., considering various solution qualities (i.e., global/local/stationary solution) returned from solving approximation subproblems. Extensive experiments justify our theoretical results and demonstrate the superiority of the proposed algorithm for hyper-parameter optimization and meta-learning tasks. Source code is available at https://github.com/vis-opt-group/BDA.


INTRODUCTION
B I-LEVEL Optimization (BLO) are a class of mathematical programs with optimization problems in their constraints. Recently, thanks to the powerful modeling capabilities, BLO have been recognized as important tools for a variety of machine learning and computer vision applications [1], [2], [3], [4], [5]. Mathematically, BLO can be formulated as min x∈X ,y∈Y F (x, y), s.t. y ∈ S(x) := arg min y f (x, y), (1) where the Upper-Level (UL) objective F and the Lower-Level (LL) objective f both are jointly continuous function, the UL constraint X is a compact set, the set-valued mapping S(x) indicates the solution set of the LL subproblem parameterized by x, and Y ⊆ domF is a compact convex set. Indeed, the BLO model in Eq. (1) is a hierarchical optimization problem with two coupled variables (x, y) ∈ R n × R m which need to be optimized simultaneously. This makes the computation of an optimal solution a challenging task [6]. To overcome such an unpleasant situation, from an optimistic BLO viewpoint 1 , we decouple Eq. (1) as optimizing UL variable x and LL variable y separately. Specifically, for any given x, we expect that the LL solution y ∈ S(x) also leads to the best UL objective value (i.e., F (x, ·)) simultaneously. For this purpose, following the optimistic BLO idea, we incorporate some taste of hierarchy regarding the LL variable y, and Eq. (1) is thus reformulated as F (x, y).
Actually, the above stated optimistic viewpoint is general and has received extensive attentions in BLO literature [8], [9], [10], [11]. Such reformulation reduces BLO to a single-level problem min x∈X ϕ(x) w.r.t. the UL variable x. Although early works on BLO can date back to the nineteen seventies [6], it was not until the last decade that a large amount of bi-level optimization models were established to capture vision and machine learning applications, including meta learning [12], [2], [13], hyper-parameter optimization [14], [15], [3], reinforcement learning [16], neural architecture search [17], [18], [19], [20] and image processing [4], [21], [22], [23], [5], and etc. Due to the hierarchical structure and the sophisticated dependency between UL and LL variables, solving BLO is challenging in general, especially when the LL solution set S(x) is not a singleton [24], [6]. Actually, the most straightforward idea in existing learning and vision literature is to assume that S(x) is a singleton. Formally, we call the BLO model is with the Lower-Level Singleton (LLS) condition if 1. For more theoretical details of optimistic BLO, we refer to [6], [7] and the references therein. arXiv:2102.07976v3 [cs.LG] 3 Jan 2022 ∀x ∈ X . Under this condition, a variety of Gradient-based Bilevel Methods (GBMs) have been developed to solve BLOs in different machine learning and computer vision applications.
The key idea behind these existing GBMs is to solve BLOs with an approximated Best Response (BR) Jacobian (i.e., the gradient of the best response mapping w.r.t. the UL variable x). From this perspective, we can roughly categorize existing GBMs into two groups, i.e., explicit and implicit BR methods. For explicit BR methods, the BR gradients are obtained by automatic differentiation [25] through iterations of the LL gradient descent. This explicit structure mainly includes: recurrence-based [26], [14], [12], [27], initialization-based [28], [29] and proxy-based scheme [30], [3]. Specifically, recurrencebased BR first calculate gradient representations of the LL objective and then perform either reverse or forward gradient computations (a.k.a., automatic differentiation, based on the LL gradients) for the UL subproblem. In [28], [29], known for its simplicity and state of the art performance, initializationbased structure estimated a good initialization of model parameters for the fast adaptation to new tasks purely by a gradient-based search. For proxy-based scheme [30], [3], a socalled hyper-network is trained to map LL gradients for their hierarchical optimization. These explicit methods only rely on the gradient information of the LL subproblem to update LL variable that cannot cover the UL descent information. On the other hand, implicit BR methods ( [2], [31], [32], [33], [34] and [35]) are designed based on the observation that it is possible to replace the LL subproblem by an implicit equation. These implicit methods derive their BR gradients but involve computing a Hessian matrix and its inverse, which could be computationally expensive and unstable for large-scale problems.
Note that, for existing methods within the explicit BR category, the explicit BR approximation by optimization iteration dynamics raises an issue regarding approximation quality. In fact, without the LLS assumption, the dynamics procedures of existing methods, in general may not be good approximations. This is because in this case, the optimization dynamics converge to some minimizers of the LL objective, but not necessarily to the one that also minimizes the UL objective. This unpleasant situation was noticed by both the machine learning and the optimization communities; see, e.g., [12,Section 3]. In theory, research on the theoretical convergence is still in its infancy (as summarized in Table 1). Indeed, all the mentioned GBMs require the LLS condition in LL subproblem to simplify their optimization processes and gain theoretical guarantees. For example, the works in [12], [27] enforce the strong convexity assumption to the LL subproblem. Unfortunately, it has been demonstrated that such LLS assumption is too restrictive to be satisfied in most real-world learning and vision applications. Further, these existing methods only concern the convergence towards stationary or global/local minimum, thus lack comprehensive convergence analyses.
In response to these limitations, this work proposes a novel framework termed Bi-level Descent Aggregation (BDA). Specifically, we propose a gradient type method for solving BLOs by aggregating UL and LL objectives. Theoretically, this work provides a general proof recipe as a basic template for the convergence analysis. In particular, in the absence of LLS, the BDA convergence was strictly guaranteed as long as the embedded inner simple bi-level dynamics meet the so-called UL objective convergence property and LL objective convergence property; see Section 4 for details. Specifically, we construct dynamics for optimizing the inner simple bi-level subproblem and hence achieve a justified good approximation. By using some variational analysis techniques sophisticatedly, the new optimization dynamics are shown to meet UL objective convergence property and LL objective convergence property without imposing any strong convexity assumptions in either UL or LL subproblems. Thanks to the new proof recipe, we provide the convergence results, which are classified by global/local solution cases returned from solving the approximation subproblems (i.e., min x ϕ K (x)). Besides, if solving an approximation subproblems (i.e., min x ϕ K (x)) returns (approximate) stationarity, we demonstrate the stationarity convergence result under the designed algorithm scheme (i.e., BDA). Moreover, as can be seen in Table 1, a striking feature of our study is that all the sufficient conditions we use to meet the desired convergence are easily verifiable for practical learning applications. We designed a high-dimensional counter-example with a series of complex experiments to verify our theoretical investigations and explore the intrinsic principles of the proposed algorithms. Extensive experiments also show the superiority of our method for different tasks, including hyperparameter optimization and meta learning. We summarize the contributions of this work as follows.
• By designing a gradient-aggregation strategy to formulate the inner simple bi-level dynamics, we provide a new algorithmic framework to handle the LLS issue, which has been widely witnessed, but related research is still missing among existing gradient-based BLO approaches.

•
We establish a general convergence analysis template together with an associated proof recipe for BDA. This new proof technique enhances our understanding of the essence of gradient-based method's convergence, hence helps to eliminate the UL strong convexity assumption, which is required in [1]. 2

•
We provide a comprehensive theoretical convergence analysis of the developed algorithm. Focusing on different solution qualities (namely, global/local/stationary solutions), we elaborate the convergence properties respectively, thus significantly extend results in [1].
• As a nontrivial byproduct, the iterative gradientaggregation dynamics (i.e., Eq. (9)) are of independent interest in convex optimization. They can be identified as a new iterative optimization scheme for solving the simple bi-level problem without the UL strong convexity.

GRADIENT-BASED BLOS: A BRIEF REVIEW
As for the BLO model in Eq. (2), it is worthwhile noting that the LL solution set S(x) may have multiple solutions for every (or some) fixed x. However, it is challenging to solve BLO, especially when the LL solution set is not a singleton. Thus, in learning and vision application scenarios, the most 2. A preliminary version of this work has been published in [1]. straightforward idea of designing GBMs is to enforce the singleton assumption on S(x). With such LLS condition, the BLO model in Eq. (2) actually can be simplified as follows: Thus the optimization task reduces to solve a single-level problem (i.e., min x∈X ϕ(x) = F (x, y * (x))) with an optimal LL variable y * . In this way, the gradient of ϕ (w.r.t., x) can be written as where "grad." denotes the abbreviation of gradient and (·) means the transpose operation. In existing GBMs, they actually first numerically approximate y * by y K and thus define ϕ K (x) = F (x, y K (x)). Then the UL variable x can be updated based on the following practical formulation 3 (5) In particular, a variety of techniques [14], [12], [27], [28], [29], [30], [3] have been developed to explicitly formulate y K using dynamic systems. For example, by enforcing the LLS assumption on the BLO problem and considering x as the recurrent parameters of a gradient-based dynamic system, i.e., , these methods first calculate gradient representations of the LL objective and then perform either reverse/forward or automatic differentiation to obtain Eq. (5). However, the dynamic system generated by these GBMs can only reveal gradients of the LL subproblem, but completely miss descent information from the UL objective.
Theoretically, these existing convergence results all require that the LL dynamics {y K (x)} is uniformly bounded on X and y K (x) uniformly converges to y * (x) as K → ∞. We should also point out that the LLS condition actually plays the key role for most of existing GBMs (e.g., [12], [35]). These approaches often require restrictive assumptions (e.g., strong convexity) to meet this assumption. Besides, some researches [3], [27], [36] prove that UL valuefunction converges to a first-order stationary point, i.e., lim T →∞ ∇ϕ(x T ) → 0. To achieve the stationarity, they require the first-order Lipshitz assumption for the UL and LL objectives, the twice continuously differentiable property for the LL objective and some additional restrictive assumptions, such as nonsingular Hessian assumption in [3].

BI-LEVEL DESCENT AGGREGATION
In this section, we establish a general algorithmic framework to solve BLOs formulated in Eq. (2). In particular, by incorporating the numerical BR mapping y K (x) into Eq. (2), we actually aim to solve the following approximated singlelevel optimization model: It should be emphasized that different from these existing GBMs stated above, which only use the information of the LL subproblem to generate ϕ K (x) (i.e., obtain y K (x)), here we formulate it as the value function of the following inner simple bi-level model: Let T k (x, ·) 4 stand for a schematic iterative module originated from a certain simple bi-level solution strategy on Eq. (7) (with a fixed UL variable x). Then we can write the general updating rule of y as follows: where y 0 (x) = y 0 is the initialization based on y 0 ∈ Y.
For the particular form of T k (x, ·), here we would like to aggregate both the UL and LL subproblems to define it. Specifically, for a given x, we write the descent directions of the UL and LL objectives as , where s u , s l denote the corresponding step size parameters. Then we consider the following aggregated updating scheme as T k (x, ·), i.e., where Proj Y denotes the projection on Y, µ ∈ (0, 1) and α k , β k ∈ (0, 1] are the aggregation parameters and k = 0, . . . , K − 1. Here we should point out that the iteration scheme in [1,Eq. (10)] is just a specific case of Eq. (9) with β k = (1 − µα k )/(1 − µ).
As for solving the single-level problem in Eq. (6), we state that this UL optimization step straightforwardly follows the standard (stochastic) gradient scheme, which has been widely investigated in literature; see, e.g., [26], [14], [12], [27]. To close this section, we summarize the overall BDA scheme in the following Algorithm 1. 5 Remark 1. First of all, we emphasize that it will be demonstrated in the following sections that the main scope of introducing set constraints (i.e., x ∈ X and y ∈ Y) in Eq. (2) is to guarantee the completeness of our theoretical analysis. Thus in most optimization scenarios, we can straightforwardly define large enough X and Y (e.g., the whole space) to make the projection operation Proj inactive during our iterations. Besides, even if it requires to explicitly consider the set constraints for some specific applications, we actually simply introduce Clarke subdifferential (see [37] for detailed definition) for the projection operation during iterations.

A GENERAL CONVERGENCE ANALYSIS RECIPE
This part aims to provide a general convergence analysis recipe for GBMs (not only BDA, but also these existing 4. In fact, our theoretical analysis in Section 4 will introduce two essential properties, which can be used as guidance for designing T k . In other words, any T k satisfying these two properties all can be used as our fundamental modules. 5. When the identity of UL iteration step t is clear from the context, we omit the superscript t and write x instead of x t . To present the algorithm steps in a more explicit form, we provide detailed iterations with the superscript t of x in Algorithm 1; see the experiment in Sections 8.1.

Algorithm 1 Bi-level Descent Aggregation Framework
Input: The necessary parameters and initialization. Output: The optimized x, y.

12:
t = t + 1. 13: end while approaches). That is, we first introduce two essential convergence properties for the UL and LL subproblems and then establish a general convergence analysis template to investigate the theoretical properties of gradient-based bilevel iterations 6 .
To conduct the convergence analysis, we first make the following standing assumption.

Two Essential Convergence Properties
Now we are ready to establish the new convergence analysis template, which describes the main steps to achieve the converge guarantees for our bi-level updating scheme (stated in Eqs. (6)-(8), with a schematic T k ). Basically, our proof recipe is based on the following two essential properties: (1) UL objective convergence property: (2) LL objective convergence property: {y K (x)} is uniformly bounded on X , and for any > 0, there exists k( ) > 0 such that whenever K > k( ), Indeed, the general recipe provides us a criterion to design different stable algorithms. Under these two essential properties, we thoroughly analyze the bi-level optimization problem and provide comprehensive theoretical results. Based on the developed BDA algorithm scheme, we first provide convergence results towards global and local minimum in Section 4.2 and Section 4.3 respectively. Specifically, if a series of global/local solutions of approximation subproblems are found, then a global solution of the original bi-level problem can be approximately achieved. 6. We suggest readers to refer to [1] and the references therein for necessary definitions used in our convergence analysis.

Towards Global Minimum
Thanks to the continuity of f (x, y), we have the same semi-continuity over partial minimization as in [1]. In other words, with the continuity of f (x, y), we have that f * (x) := min y f (x, y) is Upper Semi-Continuous (USC for short) on X . Equipped with the above two properties (i.e., UL objective convergence property and LL objective convergence property), we establish our general convergence results in the following theorem for the schematic bi-level scheme in Eqs. (6)-(8).
Theorem 1. (Convergence towards Global Minimum) Suppose both the above UL and LL objective convergence properties hold and Then if ε K → 0, we have (1) Any limit pointx of the sequence {x K } satisfies that x ∈ arg min x∈X ϕ(x).
Proof. For any limit pointx of the sequence {x K }, let {x l } be a subsequence of {x K } such that x l →x ∈ X . As {y K (x)} is uniformly bounded on X , we can have a subsequence {x m } of {x l } satisfying y m (x m ) →ȳ for someȳ. It follows from the LL objective convergence property that for any > 0, there exists M ( ) > 0 such that for any m > M ( ), we have By letting m → ∞, and since f is continuous and f * (x) is USC on X , we have f (x,ȳ) − f * (x) ≤ . As is arbitrarily chosen, we have f (x,ȳ) − f * (x) ≤ 0 and thusȳ ∈ S(x). Next, as F is continuous at (x,ȳ), for any > 0, there exists M ( ) > 0 such that for any m > M ( ), it holds Then, we have, for any m > M ( ) and x ∈ X , Taking m → ∞ and by the UL objective convergence property and ε m → 0, we have By taking → 0, we have ϕ(x) ≤ ϕ(x), ∀x ∈ X which impliesx ∈ arg min x∈X ϕ(x). We next show that inf x∈X ϕ K (x) → inf x∈X ϕ(x) as K → ∞. For any x ∈ X , inf x∈X ϕ K (x) ≤ ϕ K (x), by taking K → ∞ and with the UL objective convergence property, we have and thus lim sup 7. This subscript K just corresponds to the subscript of ϕ K . So, if inf x∈X ϕ K (x) → inf x∈X ϕ(x) does not hold, then there exist δ > 0 and subsequence {x l } of {x K } such that Since X is compact, we can assume without loss of generality that x l →x ∈ X by considering a subsequence. Then, as shown in above, we havex ∈ arg min x∈X ϕ(x). And, by the same arguments for deriving Eq. (10), we can show that By letting l → ∞, → 0 and the definition of x l , we have which implies a contradiction to Eq. (11). Thus we have

Theorem 2. (Convergence towards Local Minimum) Suppose both the LL and UL objective convergence properties hold and let
Then we have that any limit pointx of the sequence {x K } is a local minimum of ϕ, i.e., there existsδ > 0 such that Proof. For any limit pointx of the sequence {x K }, let {x l } be a subsequence of {x K } such that x l →x ∈ X and x l ∈ B δ/2 (x). As {y K (x)} is uniformly bounded on X , we can have a subsequence {x m } of {x l } satisfying y m (x m ) →ȳ for someȳ. It follows from the LL objective convergence property that for any > 0, there exists M ( ) > 0 such that for any m > M ( ), we have By letting m → ∞, and since f is continuous and As is arbitrarily chosen, Then, we have, for any m > M ( ) and x ∈ X , Next, as x m is a local ε m -minimum of ϕ m (x) with uniform neighborhood modulus δ, it follows Taking m → ∞ and by the UL objective convergence property and ε m → 0, ∀x ∈ B δ/2 (x) ∩ X we have By taking → 0, we have Note that this work provides a series of approximate optimization problems to the bi-level problem, and we establish the convergence of such approximation problems to the original bi-level problem (i.e., Eq. (1)). Such kind of result is commonly used for characterizing the convergence of approximation type optimization method on nonconvex problems, see, for examples, Theorem 17.1 in book [38] for the convergence of the quadratic penalty function method and Theorem 7 in paper [39] for convergence of the interior point method.

CONVERGENCE PROPERTIES OF BDA
With the above discussions in Section 3, the BLO is reduced to optimize a simple bi-level problem in Eq. (7) w.r.t. the LL variable y, and subsequently solve a single-level problem in Eq. (6) w.r.t. the UL variable x. This part analyzes the convergence behavior of the developed iterative algorithm. In other words, this part is devoted to show that our proposed BDA meets two convergence properties stated in Section 4 (i.e., UL objective convergence property and LL objective convergence property).
Following the above roadmap, convergence behaviors of gradient-based bi-level methods can be systematically investigated. The desired convergence results can be successfully achieved once the embedded task-tailored iterative gradientaggregation modules T k meet the UL objective convergence property and the LL objective convergence property.

UL Convergence Properties
To investigate the convergence behavior of the proposed simple bi-level iterations T k in Eq. (9), with fixed x, we first introduce the following two auxiliary variables . We further denote the optimal value and the optimal solution set of simple bi-level problem (i.e., Eq. (7)) by ϕ(x) andŜ(x), respectively.
As the identity of x is clear from the context, in Section 5.1 and 5.2, for succinctness we will write Ψ(y) instead of F (x, y), Ψ * instead of ϕ(x), ψ(y) instead of f (x, y), S instead of S(x), andŜ instead ofŜ(x). Moreover, we will omit the notation x and use the notations y k , z u k+1 and z l k+1 instead of the y k (x), z u k+1 (x) and z l k+1 (x), respectively. With inner iterative module, this part demonstrate the convergence behavior of simple bi-level. We first provide a descent inequality of function value in the following lemma.
Not available and σ-strongly convex.
is LF -smooth, convex and bounded below.
Main results Here s − → and u − → represent the subsequential and uniform convergence, respectively. The superscript * denotes that it is the true optimal variables/values. "conti." and "diff." denote continuously and differentiable respectively. Lemma 1. Let {y k } be the sequence generated by Eq. (9) with α k , β k ∈ (0, 1], s u ∈ (0, 1 L F ), s l ∈ (0, 1 L f ) and µ ∈ (0, 1), then for any y ∈ Y, we have Proof. It follows from the definitions of z u k+1 and z l k+1 that Thus, for any y, we have As ψ is convex and ∇ψ is Lipschitz continuous with constant L f , we have 2 ) and Eq. (15) yields As Ψ is convex and ∇Ψ is Lipschitz continuous with constant L F , by similar arguments, we can have Multiplying Eq. (17) and Eq. (18) by 1 − µ and suµ s l , respectively, and then summing them up implies that By the convexity of · 2 , we have Next, as Proj Y is firmly nonexpansive (see, e.g.,[40, Proposition 4.8]), for any y ∈ Y, we have Then, since α k , β k ≤ 1, we obtain form Eq. (19) that for any y ∈ Y, (21) This completes the proof.

Lemma 2.
Let {a k } and {b k } be sequences of non-negative real numbers. Assume that there exists n 0 ∈ N such that Then lim k→∞ a k exists and ∞ k=1 b k < ∞. Proof. Adding the inequality a k+1 +b k −a k ≤ 0, from k = n 0 to k = n − 1, we get a n + n−1 k=n0 b k ≤ a n0 . By letting n → ∞, we get ∞ k=n0 b k < ∞. As {a k } k≥n0 is a nonnegative decreasing sequence, lim k→∞ a k exists.
The above Lemma 2 aims to analyze sequence inequality that will be applied in the following Theorem. We explore the boundness of inner iterative sequence in the following Lemma 3.

Lemma 3.
Let {y k } be the sequence generated by Eq.
L F , operators I − β k s l ∇ψ and I − α k s u ∇Ψ are both nonexpansive (i.e., 1-Lipschitz continuous). Then, since z l k+1 = y k − β k s l ∇ψ(y k ) andȳ =ȳ − β k s l ∇ψ(ȳ) for anȳ y ∈ S, we have If Y is compact, then the desired boundedness of {y k } follows directly from the iteration scheme in Eq. (9). And it With the above lemmas, we are now ready to obtain the convergence result of our proposed algorithm in the following theorem.

Case (b):
We assume that {τ n } is not finite and for It follows from the assumption that τ n is well defined for n large enough and lim n→∞ τ n = +∞. We assume without loss of generality that τ n is well defined for all n.

LL Convergence Properties
Specially, when we take α k = 1/(k + 1), we have the following uniformly complexity estimation. We first denote D = sup and µ ∈ (0, 1), then for anyȳ ∈ S(x), we have Proof. According to [40, Proposition 4.8, Proposition 4.33, Corollary 18.16], we know that when 0 ≤ β k s l ≤ 1 L f , 0 ≤ α k s u ≤ 1 L F , operators I − β k s l ∇ψ, I − α k s u ∇Ψ and Proj Y are all nonexpansive (i.e., 1-Lipschitz continuous). Next, as by denoting ∆ k α := α k − α k−1 and ∆ k β := β k − β k−1 , we have the following inequality , where the first inequality follows from the nonexpansiveness of Proj Y and the convexity of · 2 , the second inequality comes from the definitions of z u k , z l k and the last inequality follows from the nonexpansiveness of I − β k s l ∇ψ and I − α k s u ∇Ψ and the definitions of z u k , z l k . Then, since Theorem 4. Let {y k (x)} be the sequence generated by Eq.
and C 0 = max{2 + c 2 β /β 2 , 3}. Proof. Letȳ be any point in S, and set y =ȳ in Eq. (12), since ψ(ȳ) = min y∈R n ψ(y) ≤ ψ(z l k+1 ), we have Adding the Eq. (28) from k = 0 to k = n − 1, and since α k , β k ∈ (0, 1], we have where the last inequality follows from the assumption that inf Ψ ≥ M 0 . By Lemma 4, we have (30) and thus where Next, by Lemma 3, we have for all k, where the second inequality follows from the definition of z l k and the last inequality comes from y k − y k−1 ≤ D and β k ≥ β. This implies that for any n > n 0 > 0, Thus, since β k ∈ [β, 1], for any m ≥ 2 and n 0 = n − m + 1, the following holds where the last inequality follows from Eq. (32) that y k − y k−1 2 ≤ C1(1+ln n0) n0 for all k ≥ n 0 , and it can be easily verified that the above inequality holds when m = 1. By Eq. (29), we have Then, for any n, let m be the smallest integer such that m ≥ n 1 4 and let n 0 = n − m + 1, combining the above inequality with Eq. (34), we have Next, as n (1−µ)(1−s l L f ) , we have for any n ≥ 2, where the last inequality follows from √ 1 + ln n 0 ≤ 1 + ln n and m ≥ n 1 4 . By the convexity of ψ, and y n − z l n+1 = β n s l ∇ψ(y n ), we have ψ(y n ) ≤ ψ(ȳ) + ∇ψ(y n ), y n −ȳ = min ψ + 1 βns l y n − z l n+1 , y n −ȳ ≤ min ψ + D β 2 s l (2C 2 + C 3 ) 1+ln n n 1 4 . This complete the proof.

Approximation Quality and Convergence of BDA
This part is devoted to the justification of the approximation quality and hence the convergence of our bi-level updating scheme (stated in Eqs. (6)-(8), with embedded T k in Eq. (9)). Following the general proof recipe, we only need to verify that the convergence of T k in Eq. (9) meets the UL objective convergence property and the LL objective convergence property. Theorem 5. Suppose Assumptions 1 is satisfied, X and Y are compact, andŜ(x) is nonempty for all x ∈ X . Let {y k (x)} be the output generated by (9) with s l ∈ (0, 1/L f ), s u ∈ (0, 1/L F ), µ ∈ (0, 1), 2 with some c β > 0, then we have that both the LL and UL objective convergence properties hold.
Proof. Since X and Y are both compact, and F (x, y) is continuous on X × Y, we have that F (x, y) is uniformly bounded above on X × Y and thus min y∈Y∩S(x) F (x, y) is uniformly bounded above on X . And combining with the assumption that F (x, y) is uniformly bounded below with respect to y by M 0 for any x ∈ X , Y is compact, we can obtain from the Theorem 4 that there exists C > 0 such that for any x ∈ X , we have → 0 as K → ∞, {y K (x)} ⊂ Y, and Y is compact, LL objective convergence property holds. Next, it follows from Theorem 3 that ϕ K (x) → ϕ(x) as K → ∞ for any x ∈ X and thus UL objective convergence property holds.
Further, in the following, we will show that when f (x, y) is level-bounded in y uniformly in x ∈ X , compactness assumption on Y in Theorem 5 can be safely removed and Y can be taken as R m . Theorem 6. Suppose Assumptions 1 is satisfied, f (x, y) is levelbounded in y uniformly in x ∈ X , X is compact, andŜ(x) is nonempty for all x ∈ X . Let {y k (x)} be the output generated by (9) with s l = s u = s ∈ (0, 1/ max(L F , l f )), µ ∈ (0, 1), 2 with some c β > 0, then we have that both the LL and UL objective convergence properties hold.
Proof. According to the update scheme of y k+1 given in Eq. (9), y k+1 can be equivalently regarded as Since f (x, y) is assumed to be level-bounded in y uniformly in x ∈ X , there exists m 0 such that f (x, y) is bounded below by m 0 on R n × Y. By Assumption 1, F is bounded below by M 0 . And as α k and β k are positive and nonincreasing, it follows from the above inequality that Thus β k ∈ [β, 1] implies that ∀k the following holds Since both F and f are continuous and X is compact, is bounded on X , and thus f (x, y k ) is uniformly bounded on X for any k. Then, as f (x, y) is assumed to be level-bounded in y uniformly in x ∈ X , there exists C > 0 such that Then by the continuity of ∇ y F (x, y)and ∇ y f (x, y), there exists a compact set C ⊂ R m such that whereŷ k+1 (x) is defined in Eq. (9). This implies that the sequence {y k } coincides with the one generated by the update scheme in Eq. (9) with Y = C. Then since C is compact, the conclusion follows from Theorem 5 immediately.

Remark 2.
Following the analysis recipe, the entire Section 5 is devoted to show that the constructed algorithm (i.e., BDA) meet two convergence properties. In particular, the UL and LL convergence verifications are presented in Theorem 3 and Theorem 4, respectively. The proof of Theorem 3 mainly relies on the sufficiently decreasing inequality given in Lemma 1. Theorem 6 discussed the convergence behavior of BDA without the compactness assumption on Y.

STATIONARITY ANALYSIS OF BDA
This part provides the convergence behavior of the problem that min x ϕ K (x) is solved to (approximate) stationarity. We consider the special case where Y = R m and the LL objective function f (x, ·) : R m → R is σ-strongly convex for any x ∈ X . In this case, the solution set of LL problem S(x) is a singleton, and we denote its unique solution by y * (x).
In the following, we are going to show the convergence of BDA with respect to stationary points in this special case. Our analysis is partly inspired by [31]. We first make the following assumptions.
Assumption 2. F and f are both twice continuously differentiable. For any x ∈ X , f (x, ·) : R m → R is σ-strongly convex.
Before providing the convergence results, we begin with a lemma.
Proof. As b k → 0, there exists B > 0 such that b k ≤ B for all k. And we have for any k ≥ n 0 , 1−ρ , which implies the boundedness of the sequence {a k } and thus there exists A such that a k ≤ A for all k.
By applying implicit function theorem on the optimality condition of the LL problem, we obtain that y * (x) is differentiable on X and its derivative is given by Hence, the function ϕ(x) = F (x, y * (x)) is also differentiable and its derivative is given by Eq. (4). With the above Lemma 5, we have the following proposition. Proposition 1. Suppose Assumptions 1 and 2 are satisfied, f (x, y) is level-bounded in y uniformly in x ∈ X , X is compact, Y = R m , andŜ(x) is nonempty for all x ∈ X . Let {y k (x)} be the output generated by (9) with s l = s u = s ∈ (0, 1/ max(L F , l f )), µ ∈ (0, 1), Proof. According to the update scheme of y k+1 given in Eq. (9), and since Y = R m , we have where φ k (x, y) = α k µF (x, y) + β k (1 − µ)f (x, y). And we have As µ ∈ (0, 1), β k ∈ [β, 1], s ∈ (0, 1/ max(L F , l f )), ∇ y f (x, y * ) = 0, and f (x, ·) : R m → R is assumed to be σ-strongly convex, [42,Theorem 10.29] implies Let ρ := 1 − sβ(1 − µ)σ, then ρ ∈ (0, 1) and As shown in Theorem 6, there exists a compact set C such that y k (x) ∈ C for any k and x ∈ X . Then by the continuity of ∇ y F (x, y) on X × R m , there exists C > 0 such that ∇ y F (x, y k (x)) ≤ C for any k and x ∈ X . Then we have (37) Thus, ∀k ∈ N, the following holds Since α k → 0, we obtain from Lemma 5 that By taking derivative with respect to x on both sides of Eq. (36), we get Combining with Eq. (35), we have is convex and f (x, ·) is assumed to be σ-strongly convex, ∇ yy F (x, y k ) 0 and ∇ yy f (x, y k ) σI for any x ∈ X and k. Combining with µ ∈ (0, 1), β k ∈ [β, 1] and s ∈ (0, 1/ max(L F , l f )), we have ∈ (0, 1). Then, it follows from the above inequality that where Γ k (x) = ∇ yx F (x, y k (x)) + ∇ yy F (x, y k (x)) ∂y * (x) ∂x . Next, we are going to show that the last three terms in the right hand side of the above inequality converge to 0 as k → ∞.
First, as discussed above that there exists a compact set C such that y k (x) ∈ C for any k and x ∈ X . Since ∇ yx f and ∇ yy f are both continuous on X × R m and X , C are compact, ∇ yx f and ∇ yy f are both uniformly continuous on X × C, then, the fact that sup x∈X y k (x) − y * (x) → 0 as k → ∞ implies that sup x∈X dis f yx (x, y k ) → 0 and sup x∈X dis f yy (x, y k ) → 0 as k → ∞. σ-strong convexity of f (x, ·) yields the continuity of ∂y * (x) ∂x on X and thus sup x∈X ∂y * (x) ∂x < +∞. Then, we have ∂x → 0 as k → ∞. Next, as ∇ yx F and ∇ yy F are both continuous on X × R m , X , C are compact, and y k (x) ∈ C for any k and x ∈ X , then sup x∈X ( ∇ xy F (x, y k (x)) + ∇ yy F (x, y k (x)) ) < +∞.
Combining with the fact that sup x∈X Recalling Eq. (4) and we have the following estimate where dis F y (x, y k ) = ∇ y F (x, y k (x)) − ∇ y F (x, y * (x)) and dis F x (x, y k ) = ∇ x F (x, y k (x)) − ∇ x F (x, y * (x)). Since ∇ x F and ∇ y F are continuous on X × R m and thus uniformly continuous on compact set X × C. Then the fact that sup x∈X y k (x) − y * (x) → 0 as k → ∞ implies that sup x∈X dis F x (x, y k ) → 0 and sup x∈X dis F y (x, y k ) → 0 as k → ∞. The continuity of ∂y * (x) ∂x on X yields that sup x∈X ∂y * (x) ∂x < +∞ and thus sup x∈X dis F y (x, y k ) ∂y * (x) ∂x → 0 as k → ∞. Next, as ∇ y F is continuous on X × R m and y k (x) belongs to a compact set for any k and x ∈ X , it holds that sup x∈X ∇ y F (x, y k (x)) < +∞ for any k. Then Eq. (38) implies that sup x∈X Then we get the conclusion directly from Lemma 5. Suppose Assumptions 1 and 2 are satisfied, f (x, y) is level-bounded in y uniformly in x ∈ X , X is compact, Y = R m , andŜ(x) is nonempty for all x ∈ X . Let {y k (x)} be the output generated by (9) with s l = s u = s ∈ (0, 1/ max(L F , l f )),

Theorem 7.
and let x K be a ε K -stationary point of ϕ K (x), i.e., Then if ε K → 0, we have that any limit pointx of the sequence {x K } is a stationary point of ϕ, i.e., 0 = ∇ϕ(x). We compare our BDA with gradient-based BLO algorithm (i.e., RHG). We set the initial points (x, y) = (0, 0), n = 50 and K = 20. x t denotes the UL variable at the t-th UL iterations.
Proof. For any limit pointx of the sequence {x K }, let {x l } be a subsequence of {x K } such that x l →x ∈ X . For any > 0, as shown in Proposition 1, there exists k 1 such that Since ε k → 0, there exists k 2 > 0 such that ε k ≤ /2 for any k ≥ k 2 . Then, for any l ≥ max(k 1 , k 2 ), we have Taking l → ∞ in the above inequality, and by the continuity of ∇ϕ, we get ∇ϕ(x) ≤ . Since is arbitrarily chosen, we get 0 = ∇ϕ(x).

DISCUSSIONS
This section first provides a comparison with the existing LLS scheme by a high dimension counter-example in Section 7.1. Then, Section 7.2 lists the improvements of this work. Finally, we develops an one-stage extension scheme in Section 7.3.

Comparison with Existing LLS Theories
As aforementioned, a number of gradient-based methods have been proposed to solve BLO in Eq. (1). However, these existing methods all rely on the uniqueness of S(x) (i.e., LLS assumption). That is, rather than considering the original BLO in Eq. (1), they actually solve the simplification in Eq. (3). By considering y as a function of x, the idea behind these approaches is to take a gradient-based first-order scheme (e.g, gradient descent, stochastic gradient descent, or their variations) on the LL subproblem. Therefore, with the initialization point y 0 , a sequence {y k (x)} K k=0 parameterized by x can be generated, e.g., where s l > 0 is an appropriately chosen step size. Then by considering y K (x) (i.e., the output of Eq. (39) for a given x) as an approximated optimal solution to the LL subproblem, we can incorporate y K (x) into the UL objective and obtain a single-level approximation model, i.e., min x∈X F (x, y K (x)). Next, by unrolling the iterative update scheme in Eq. (39), we can calculate the derivative of F (x, y K (x)) (w.r.t. x) to optimize Eq. (3) by automatic differentiation techniques [14], [43].
The UL objective F is indeed a function of both the UL variable x and the LL variable y. Conventional gradientbased bi-level methods (Eq. (39)) only use the gradient Fig. 2. Illustrating the convergence behavior of gradient-based BLO algorithms about the UL variable x. We set the initial points (x, y) = (0, 0), n = 50 and K = 20. In the first subfigure, ϕ K (x) and ϕ * (x) denote the UL objective with LL computational solution y K and the optimal LL solution y * respectively. The second and third subfigures respectively show the errors of UL objective (i.e., |ϕ K (x) − ϕ * (x)|) and UL variable (i.e., x − x * ). The last subfigure illustrates the relationship among Optimal solution (short for "Opt.", the red star) and the iteration solutions of RHG and BDA.
information of the LL subproblem to update y. Thanks to the LLS assumption, for fixed UL variable x, the LL solution y can be uniquely determined. Thus the sequence {y k } K k=0 could converge to the true optimal solution, that minimizes both the LL and UL objectives. However, when LLS is absent, {y k } K k=0 may easily fail to converge to the true solution. Therefore, x * K may tend to be incorrect limiting points. Example 1. (Counter-Example) With x ∈ R n , y ∈ R n and z ∈ R n , we consider the following BLO problem: where X = [−100, 100] × · · · [−100, 100] ⊂ R n , e denotes the vector whose elements are all equal to 1. By simple calculation, we know that the unique optimal solution of Eq. (40) is x * = y * = z * = e. However, if adopting the existing gradient-based scheme in Eq. (39) with initialization (y 0 , z 0 ) = (0, 0) and varying step size s k l ∈ (0, 1), we have that y K = (1 − K−1 k=0 (1 − s k l ))x and z K = 0. Then the approximated problem of Eq. (40) amounts to Consider sequence x * K = arg min x∈X F (x, y K , z K ), it follows from the first-order optimality condition that, where which is a contradiction to 0 = 1 + (ā − 1) 3ā . Therefore, any subseuqnce of {x * K } cannot converge to the true solution (i.e., x * = e). Remark 3. Actually, even with strongly convex UL objective w.r.t. LL variable y, the existing bi-level based methods still may fail to reach an optimal solution. For example, with x ∈ [−100, 100] and y ∈ R 2 , we consider the following BLO problem: By simple calculation, we know that the unique optimal solution of Eq. (3) is x * = 1, y * = (1, 1). However, if adopting the existing gradient-based scheme in Eq. (39) with initialization y 0 = (0, 0) and varying step size s k l ∈ (0, 1), we have that It is easy to check that x * K ≤ 1 2 . So x * K cannot converge to the true solution (i.e., x * = 1).

Remark 4.
In applications, to achieve the LLS, people sometimes add a strongly convex regularization term to the LL subproblem. We must clarify that this strategy is only heuristic, which usually causes unpredictable large deviation from the true solution.
Indeed, even the strongly convex regularization is set to be vanishing, such an approximation procedure cannot guarantee any convergence to the true solution. We will take the counter-example in Remark 3 again for illustration. Specifically, we introduce a quadratic term 1/2ε y 2 2 to the LL subproblem min y∈R 2 Apparently, the LL objective becomes strongly convex. But it can be checked that the optimal solution to such bilevel problem with regularized LL min x∈[−100,100] becomes x * (ε) = 1 2 , y * 1 (ε) = 1 2 , y * 2 (ε) = 0 which is obviously no longer the true solution to the original bilevel model. Moreover, even with ε tending 0, unfortunately, x * (ε), y * 1 ( ) and y * 2 ( ) still fail to converge to the true solution (1, 1, 1).
To demonstrate the convergence behavior of our BDA and the most popular bi-level method (i.e., RHG [14], [12]), we first illustrate the optimization procedure of LL variable (i.e., y K ) in Figure 1. As can be observed that the LL variable y K can converge to the LL solution set S(x t ) for both RHG and our BDA in the left subfigure. But, the LL variable of our method can find the optimal point, i.e., y * , while RHG cannot. Note that we set the dimension n = 50.
x 0 x 5 x 20 In Figure 2, comparing with RHG, we then demonstrate the optimization procedure of UL variable (i.e., x). In the first subfigure, under fixed LL iterative solution y K , the UL objective ϕ K (x) illustrates that our BDA can efficiently fit the optimal objective function (i.e., ϕ * (x)) for any UL variable. To further demonstrate the convergence behavior, we plotted the errors of the UL objective (i.e., |ϕ K (x) − ϕ(x)|) and variable (i.e., x − x * ) in the second and third subfigures. With the above illustration, we summarize the relationship of Optimal solution (short for "Opt.", the red one in the last subfigure) with the iterative solutions of RHG and BDA in the last subfigure. Thus, we conclude that our BDA can find the optimal point, while RHG converge to a non-optimal point in S(x).

Comparison with the Work in [1]
First of all, this work significantly improves the assumptions required by our convergence analysis. That is, we successfully remove the strong convexity property on the UL objective, the level-bounded in y and locally uniformly in x ∈ X property on the LL objective. Furthermore, we replace the essential condition "LL solution set property" by "LL objective convergence property", which is much weaker and easily verifiable. In this way, we actually obtain a more general and feasible proof recipe for challenging real-world applications.
We also extend our convergence results to other optimization scenarios, such as local and stationary results. Specifically, we obtain convergence results for the case that there are only local solutions to the UL approximation (i.e., "min x ϕ K (x)"). Moreover, we provide new methodology to analyze the convergence behaviors of our BDA in the scenario that we can only obtain the stationary points for the UL approximation. Therefore, this work has comprehensively analyzed the convergence behaviors for our BDA in various (i.e., global, local and stationary) optimization scenarios.
Algorithmically, this work establishes a more general framework, in which we introduce the projection-based operations to handle set constrains in BLOs and design more flexible strategy to set the aggregation parameters during iterations. We also established a one-stage fast approximation to BDA for solving large-scale real-world problems.
We design a high-dimensional counter-example (see Eq. (40)) and conduct various experiments to verify our new theoretical findings, i.e., the efficiency of BDA for BLOs without the LLS condition and both the UL and LL objectives are convex but not strongly convex. We further do new experiments to more clearly analyze the components of BDA and report more results on real applications (e.g., with new evaluation metrics, on more challenging benchmarks and compared with more state-of-the-art approaches).

One-stage BDA: A Fast Implementation
Multi-step of the LL iteration modules T k will cause a lot of memory consumption that may be an obstacle in modern massive-scale deep learning applications. Thus it would be useful to simplify iteration steps. This part provides an extension scheme leveraging a one-stage simplification to reduce complicated gradient-based calculation steps [17]. By setting K = 1 in Eq. (9), the algorithm reads as where φ(x, y 0 ) = αF (x, y 0 ) + βf (x, y 0 ) and α, β ∈ (0, 1] denote the aggregation parameters. Indeed, if (y 0 − s∂ y φ(x, y 0 )) ∈ Y, with this one-stage simplification, we can simplify the back-propagation calculation with the following finite difference approximation where h ± 0 = y 0 ± ∂F (x, y 1 )/∂y 1 and ∂ x φ(x, y) = α∂ x F (x, y) + β∂ x f (x, y). Since Y can be a big interval, this case (i.e., (y 0 −s∂ y φ(x, y 0 )) ∈ Y) is often satisfied in general. If (y 0 − s∂ y φ(x, y 0 )) / ∈ Y, the above back-propagation can be calculated by the following form

EXPERIMENTAL RESULTS
This section first verify the numerical results and then evaluate the performance of our proposed method on different problems.

Numerical Evaluations
Our numerical results are investigated based on the synthetic BLO described in Section 7.1, i.e., Counter Example in Eq. (40). As stated in Section 7.1, this deterministic bi-level formulation satisfies all the assumptions required in Section 4, Fig. 4. Comparisons of BDA with RHG on ten different initial points. We set the dimensional n = 50 and K = 20. The left subfigure show the iteration solution of different initial points. We select five different initial points and show the UL objective behavior on the right subfigure. but it cannot meet the LLS condition considered in [28], [14], [12], [27], [2].
To show the influence of the LL iterations (i.e., K) on different methods, we first plotted the convergence behaviors (i.e., |f (x t , y k )−f (x t , y * (x t ))|, y k (x t )−y * (x t ) and y k (x t ) − y * with t = 0, 5, 20) under different given x (i.e., x 0 , x 5 , x 20 ) in Figure 3. This figure compare our BDA with the most popular bi-level based methods (i.e., T-RHG and RHG). Note that t = 0, 5, 20 are the UL iteration steps during the operation process. From the first and second row of Figure 3, we observed that with fixed UL variable x, the results of RHG and BDA converge to the optimal solution with corresponding given x t . The third row of Figure 3 plotted the distance between the current iteration step and the optimal solution y * . As can be seen, after a few UL iteration steps (i.e., t ≥ 5), BDA is close to the optimal solution y * while RHG and T-RHG cannot. In the above figures, we set α k = 0.5/k, k = 1, · · · , K, s u = s l = 0.1, β k = 1, µ = 0.1. Figure 4 plotted numerical results of the proposed BDA and RHG [14], [12] with ten different initialization points. We considered different numerical metrics, such as the relationship of (x, y) with optimal solution (x * , y * ) and the distance between F (x, y K ) and F * (i.e., |F (x, y K )−F * |), for evaluations. It needs to be noted that we select five different initial points to show the performance of |F (x, y K ) − F * |. As can be observed that RHG is always hard to obtain the correct solution, even start from different initialization points. It is mainly because that the solution set of the LL subproblem in Eq. (40) is not a singleton, which does not satisfy the fundamental assumption of RHG. In contrast, the proposed method can obtain a truly optimal solution in all these scenarios. The initialization only slightly affects the convergence speed of our iterative sequences.
To explore the performance under projection operator denoted in Eq. (9), we report in Figure 5 the results (i.e., x − x * and y − y * ) of comparing the performance with and without projection (i.e., w/ Projection, w/o Projection).
In this experiment, we set the initial value far away from the optimal point with relatively close projection interval Y.
As can be seen, with the projection operator, the iteration sequences reach convergence with fewer steps. Figure 6 evaluated the convergence behaviors of BDA with different choices of α k . We set β k = 1, µ = 0.5, s u = 0.1 and s l = 0.1. By setting α k = 0, we were unable to use the UL information guiding the LL updating. Thus it is hard to obtain proper feasible solutions for the UL approximation subproblem. When choosing a fixed α k in (0, 1) (e.g., α k = 0.5), the numerical performance can be improved but the convergence speed was still slow. Fortunately, we followed our theoretical findings and introduced an adaptive strategy to incorporate UL information into LL iterations, leading to nice convergence behaviors for both UL and LL variables.

Hyper-parameter Optimization
For the hyper-parameter optimization problem, the key idea is to choose a set of optimal hyper-parameters for a given machine learning task. In this experiment, we consider a specific hyper-parameter optimization example (i.e., data hyper-cleaning [14], [27]) to evaluate the developed bi-level algorithm. This task aims to train a linear classifier on a given image set, but part of the training labels are corrupted. Here we consider soft-max regression (with parameters y) as our classifier and introduce hyper-parameters x to weight samples for training. We define the LL objective as the following weighted training loss: where x is the hyper-parameter vector to penalize the objective for different training samples, (y; u i , v i ) means the cross-entropy function with the classification parameter y, and data pairs (u i , v i ) and denote D tr and D val as the training and validation sets, respectively. Here σ(x) denotes the element-wise sigmoid function on x and is used to constrain the weights in the range [0, 1]. For the UL subproblem, we define the objective as the cross-entropy loss with 2 regularization on the validation set, i.e., In particular, the UL and LL objective F and f w.r.t. y is required to be convex. To satisfy this requirement, we design the classifier with a fully connected layer.
We applied our BDA and One-stage BDA (O-BDA) together with the bi-level based methods, i.e., Implicit HG (IHG) [35], RHG and Truncated RHG (T-RHG) [27]. We first conduct the experiment on two datasets (MNIST dataset [44] and Fashion MNIST dataset [45]) that each with 5000 training examples (i.e., D tr ), 5000 validation examples (i.e., D val ) and a test set with the remaining 60000 samples. We randomly chose 2500 training samples from D tr and pollute the labels.
We use validation accuracy (i.e., Val. Acc.), test accuracy (i.e., Test Acc.), F1-score and running times as the metrics of our developed algorithm. As shown in Table 2, the developed method perform the best both on MNIST and Fashion MNIST dataset. The LL iterations are K = 200 and K = 50 on MNIST and Fashion MNIST, respectively.
For T-RHG, we chose 100-step and 25-step truncated backpropagation respectively from K = 200 and K = 50 to guarantee its convergence. Besides, the developed O-BDA still perform better when comparing with the existing bi-level based methods.

TABLE 4
The few-shot classification performances on MiniImageNet (N = 5 and M = 1). The second column reported the averaged accuracy after converged. The rightmost two columns compared the UL Iterations (denoted as "UL Iter."), when achieving almost the same accuracy (≈ 44%). Here "Ave. ± Var. (Acc.)" denotes the averaged accuracy and the corresponding variance.

Meta-Learning
Meta-learning aims to leverage a large number of similar few-shot tasks to learn an algorithm that should work well on novel tasks in which only a few labeled samples are available. In particular, we consider the few-shot learning problem [46], [47], where each task is to discriminate N separate classes and it is to learn the hyper-parameter x such that each task can be solved only with M training samples (i.e., N -way M -shot). Following the experimental protocol used in recent works that the network architecture is with four-layer CNNs followed by fully connected layer, we separate the network architecture into two parts: the cross-task intermediate representation layers (parameterized by x) outputs the meta features and the multinomial logistic regression layer (parameterized by y j ) as our ground classifier for the j-th task. We also collect a meta training data set D = {D j }, where D j = D j tr ∪ D j val is linked to the j-th task. Then for the j-th task, we consider the cross-entropy function (x, y j ; D j tr ) as the task-specific loss and thus the LL objective can be defined as f (x, {y j }) = j (x, y j ; D j tr ).
As for the UL objective, we also utilize cross-entropy function but define it based on {D j val } as F (x, {y j }) = j (x, y j ; D j val ).
Our experiments are conducted on Ominglot [48] and MiniImageNet [46] benchmarks. We compared our BDA to several state-of-the-art approaches, such as MAML [28], Meta-SGD [49], Reptile [29], iMAML [2], RHG, and T-RHG. As shown in Table 3, BDA compared well to these methods and achieved the highest classification accuracy except in the 5-way task. Further, with more complex problems (such as 20way, 30-way and 40-way), BDA shows significant advantages Omniglot dataset MiniImageNet dataset Fig. 7. Illustrating the validation loss (i.e., UL objectives F (x, y)) for three bi-level based methods on few-shot classification task. over other methods. Besides, we evaluate the performance of BDA and bi-level based methods (i.e., RHG and T-RHG) on the more challenging MiniImageNet data set and the corresponding results are listed in Table 4. As shown in the second column of Table 4 that the developed BDA perform better than RHG and T-RHG. The rightmost two columns demonstrate that BDA needed the fewest iterations to achieve almost the same accuracy (≈ 44%). The corresponding validation loss on Omniglot and MiniImageNet about 5-way 1-shot are shown in Figure 7. Moreover, to evaluate the effectiveness of the projection operator, we conduct an experiment evaluating orthogonal features of the network with two different strategies (i.e., max-norm regularization and spectral normalization). Note that we compute the orthogonality following [50]. As shown in Figure 8, BDA with both Max and SN training schemes show the lower orthogonal sum. This experiment implies that the projection operator can help obtain a better network.

CONCLUSIONS
This work established a flexible descent aggregation framework with task-tailored iteration dynamics modules to solve bi-level tasks by formulating BLO in Eq. (2) from the viewpoint of optimistic bi-level. We provided a new algorithmic framework to handle the LLS issue. Then, this work strictly proved the convergence of the developed framework without the LLS assumption and the strong convexity in the UL objective. Focusing on different solution qualities (namely, global, local, and stationarity), this work elaborated the convergence results respectively. Finally, extensive experiments justified our theoretical results and demonstrated the superiority of the proposed algorithm for hyper-parameter optimization and meta-learning.