extfieldsofstudy:
Medicine
Computer Science
Mathematics

text:
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.


Chatbot for fitness management using IBM Watson

Chatbots have revolutionized the way humans interact with computer systems and they have substituted the use of service agents, call-center representatives etc. Fitness industry has always been a growing industry although it has not adapted to the latest technologies like AI, ML and cloud computing. In this paper, we propose an idea to develop a chatbot for fitness management using IBM Watson and integrate it with a web application. We proposed using Natural Language Processing (NLP) and Natural Language Understanding (NLU) along with frameworks of IBM Cloud Watson provided for the Chatbot Assistant. This software uses a serverless architecture to combine the services of a professional by offering diet plans, home exercises, interactive counseling sessions, fitness recommendations.

I. INTRODUCTION
Businesses benefit from chatbots because they increase operational efficiency and save costs while providing convenience and extra services to internal staff and external clients. They enable businesses to quickly answer a variety of client concerns and enquiries while decreasing the requirement for human involvement.
A firm can expand, customize, and be proactive all at the same time using chatbots, which is a key differentiation. When a firm relies exclusively on human power, for example, it can only service a certain number of people at any given time. Human-powered firms are compelled to rely on standardized models in order to be cost-effective, and their proactive and personalized outreach skills are restricted.
Chatbots, on the other hand, allow businesses to interact with an endless number of consumers in a personalized manner and can be scaled up or down based on demand and business needs. A company may give humanlike, tailored, proactive service to millions of customers at the same time by deploying chatbots.
Our focus in this paper is to implement an interactive chatbot for personal fitness management. To assist users in yoga plan, diet plan, scheduling, users can use this interactive and advanced chatbot. The origins of the chatbot may be traced back to Alan Turing's idea of sentient robots in the 1950s. Since then, artificial intelligence, which is the foundation for chatbots, has advanced to encompass super intelligent supercomputers like IBM Watson.
Chatbots are widely used to improve the IT service management experience, which focuses on self-service and automating internal operations. Common activities such as password changes, system status, outage notifications, and knowledge management may be easily automated and made available 24 hours a day, seven days a week with an intelligent chatbot, while expanding access to widely used voice and text-based conversational interfaces.
Chatbots are most typically employed in customer contact centers to manage incoming conversations and guide consumers to the right resource. Internally, they're typically used for onboarding new workers and assisting all staff with routine tasks like vacation scheduling, training, purchasing computers and business supplies, and other self-service activities that don't require human participation.
The possibilities they open up in the fitness business are practically limitless, but for now, they're mostly being used to meet initial marketing and communication objectives.
The rest of the paper is organized as follows. Section-II describes the problem statement, in section-III we also identified the related work on the proposed work, Section-IV we explained the implementation of the project and internals of the IBM Watson, in Section-V we proposed the future works that are to be implemented, Section-VI we described the conclusion and Section-VII are the References.

II. PROBLEM
Although going to the gym has several advantages, it is not for everyone. Approximately 67 percent of gym members do not go on a regular basis. People are apprehensive about unfamiliar environments or using difficult-to-use fitness devices if they haven't been properly trained. Introduction sessions are available at certain gyms, whereas personal trainers handle this at others.
In addition, there is a lack of interaction between gyms and gym members. Gym members are not incented or reminded to go to the gym on a regular basis in any meaningful way. Filling up the gym's facilities is really against the gym's interests.
Unfortunately, few gyms are built with a holistic health approach in mind. When emotional and mental health aren't supported jointly, it's challenging to achieve peak physical performance. Reduced physical performance results in poor outcomes, making it difficult to establish a regular gym program.
There are several fitness applications available that focus on delivering performance feedback, food recommendations, and activity routines. Fitness applications can be beneficial to those who are willing to put in the extra effort to use the program. Unfortunately, few people have the mental capacity to stay engaged with applications and enter personal fitness data, diets, or training regimens on a daily basis. Although analytics might aid in personal performance optimization, some users are intimidated by the prospect of monitoring statistics too frequently. Daily body weight swings, as well as failure to improve on prior weeks' performance, might sap motivation.
We aim to provide a technological solution to people who feel that maintaining a regular diet plan or a workout routine is tough and also an overhead to remember it all the time. Instead, users can use our chatbot to schedule all their workout plans and diet plans which will be saved in the database.
Education, constant reminders, compelling material, and prizes all help to motivate people to work out more often. These features add to the user's mental well-being and aid in the development of good habits. A constant accountability partner who reminds the user of their own objective increase's motivation significantly. We hope to mimic an accountability partner that sends out interesting push alerts on certain days by constructing a chatbot. A personal fitness trainer is a person who helps people become in shape.
Self-efficacy may be adjusted and strengthened with the correct stimulus, according to psychological research (Weinberg et al.,1979).
Finally, users must be rewarded for their efforts in order for their input to be linked to a beneficial outcome. While we're working on the feature roadmap, a rewards function and additional material will be added to the chatbot shortly.
The aim is to provide a tailored chatbot experience that isn't time consuming and keeps the customer engaged in their weekly exercise routines.

III. RELATED WORK
The advanced techniques have enabled smart applications in different scenarios [15-]. According to the International Health, Racquet & Sports club Association, the worldwide fitness sector generated $83.1 billion in sales in 2016, up 2.6 percent from $81 billion the previous year. It should reach $87.5 billion in 2018 if it continues at this pace. Currently, a number of AI companies claim to be able to help gyms with new client acquisition, nutrition and fitness program development, and customer relationship management. Some companies believe that chatbots can assist gym members in sticking to their own fitness plans.
Vida Health says that their software can assist people and business personnel maintain their health and fitness by connecting them with a oneon-one coach using a machine learning-based app.
Vida Health says that their app can connect people with a Vida Health coach or therapist based on their health objectives, preferred coaching style, biometrics, availability, and geographic region.
Users must first input information about their health objectives, whether they are connected to physical condition, weight reduction, or stress alleviation, before they can begin using the program on their mobile phone. They must also pick a coaching style that suits them best. Based on the data, the app's machine learning model searches its database for traits that are similar to those picked by the user and matches them with a coach who can assist them in achieving their objectives.
The business says that its methodology can assist trainers communicate with clients by providing push alerts and remotely tracking client progress via wearables and smart monitor integrations. Gym management, for example, will be able to see previous years' bookings for class spots. Managers may estimate which classes and time slots will be popular in the future using this information. The algorithm will be able to forecast a member's success in meeting their goals by scanning its database for outcomes with comparable qualities by combining data logs on nutrition, workout performance, age, weight, and gender. It also directs trainers to suggest additional exercises or dietary regimens if necessary.
Zara is a smartphone application developed by Zova, an Australian business that claims to give fitness fans with smart, tailored exercises via a chatbot. Zara tailors training routines to specific consumers, according to the firm.
The app also has an Activity Score function that calculates an intensity level for these activities by averaging the user's activity level over seven days, including all steps and exercises.
The algorithms may then search their database of trainings and workouts for exercises that are comparable to the user's lifestyle and suggest workouts that will assist the user in meeting their fitness objectives. Zova may be used to webcast and track the workouts.
Fitwell is a firm headquartered in the United Kingdom that promises to be able to assist people measure their fitness progress with a chatbot called Hailee.
The software includes training services tailored to the users' specific goals, such as becoming stronger, more flexible, or toned. The algorithms in the app will go through its database for training programs that fit the user's preferences. The algorithms will alter the exercises over time based on the user's prior performance to ensure that they meet their objectives.
The software also features a bot that, according to the business, allows users to keep track of their meals and snacks by delivering accurate nutritional information.

IV. IMPLEMENTATION
Conversational assistant aids in the automation of chat dialogues between users and computers. This chatbot is meant to address fitness needs and assist individuals in obtaining information about trainers and diet plans from the comfort of their own homes. These interactive chatbots will aid in the resolution of difficulties such as the lack of information on the proper food plan, exercise comprehension, and body care.

A. Chat Bot Architecture
In recent years, serverless architectures (Functions-as-a-Service) have gained traction as a way to deliver backend services without requiring a dedicated infrastructure. Serverless allows users to integrate stateless functionality into platform systems. Each invocation is independent of the previous ones due to its statelessness. IBM Watson cloud functions has been used as the backend infrastructure for our application. Our conversational bot is AI-powered and developed with serverless architecture. It has Natural Language Processing (NLP) and Natural Language Understanding (NLU) [12] built in to comprehend the user's inquiry and respond appropriately. NLP makes it easier to read, decode, comprehend, and interpret human languages. To interpret the semantic meaning of user input and locate morphemes, the user query is processed and decoded. The intents are detected and then mapped on to the Dialog skill in IBM Watson.
The intent mapping is then handled by the Dialogskill [4] which has been thoroughly trained with the different dataset and questionnaires and helps in drawing the inferences. The Watson Assistant V2 API are used to generate a HTTP POST request in order to send the query from the application to server. The request consists of query dialogskill then decodes the intent to understand actions, entities and then maps it to intent to define the response. The Dialogskill then sends the response back for the request with the help. The response message contains the response that the user should receive at the conclusion of the operation.
The main components of IBM Watson includes the following

B. Intent Classification:
A purpose or objective conveyed in a customer's input, such as answering a question or pushing a bill payment button, is known as intent. The Assistance service selects the appropriate dialog flow for responding to a customer's input by recognizing the intent indicated in it. It's a technique for steering the conversation in the right direction.
[8] The query formulated by the user must be analyzed by the intent classifier and must be able to distinguish whether it is in-scope (IS) or Out-Of-Scope (OOS), NLP plays a major role in classification of query correctly. Here we also have the concept if reformulation which will be discussed further.
The Dialogskill first does matching using the Rule -Based grammar matching, if no match found switches to the ML algorithmic approach, like Support vector Machine for understanding the semantics in the query formulated by the user. The AutoML uses the set of algorithms like Bidirectional Encode Representation from Transformers (BERT) [8] for the purpose of NLP pretraining. The Transformer is a focus mechanism that learns how words in a text are related to one another. It was trained unsupervised using a plain text library, such as Wikipedia or other freely available text data on the internet in any language. As a result, in any NLP classification challenge, BERT outperforms traditional ML systems. Here we use the confidence score in order to understand the relevancy of query with the intent, ranging from 0.0 (completely uncertain) and 1.0 (fully relevant). If the confidence score of the highest scoring IS intent is greater than or equal to the threshold setting, it is returned to match. Otherwise, an OOS is matched if no IS intents meet the criteria.
The intent detection also uses Meta-Learning [11] algorithms for Few-Shot Computer Vision to train from the larger dataset, and learn from them and form some predefined contextual intent for knowledge base and use this to work on newer, unseen queries.

C. Irrelevance Detection Algorithm
Another difficult difficulty in conversational AI is determining when end users are asking about off-topic topics. A banking virtual assistant, for example, should not be expected to respond to inquiries about dinosaurs and should gently divert the user back to banking. Watson Assistant, as we discussed in the intent detection section above, requires relatively minimal training data to effectively grasp user intents. However, recognizing in-domain and out-of-domain borders becomes more difficult as a result.
To accomplish so, we use deep learning models to model the training data's distribution by translating it to a domain representation. Any input whose representation does not match the distribution is considered irrelevant based on the learnt model. This implies that our algorithms are well-versed in the types of sentences users are likely to employ while discussing banking. When the models come across terms that aren't commonly used in banking, they recognize that the discourse isn't on track.

D. Autocorrection Algorithm
Remember, utterances are the many ways in which end users might ask a specific inquiry or request a certain action -for example, "password doesn't work" or "I can't log in" are two utterances that map to the "reset password" intent.
Because so much depends on accurately comprehending utterances, an autocorrection method is required to repair misspelled words. It can't be harsh, though, because business jargon frequently uses abbreviations and trademarks that are spoofs of actual words. Profanity screening, for example, is also required. All of this, and more, is available through Watson Assistant.
Watson Assistant is driven by language models, phonetic models, edit distance models, and deep learning under the hood, allowing it to correct a wide range of misspellings in corporate use cases.

E. Entity Recognition Algorithms
In the framework of conversational AI, let us define "entity." "IBM Watson Discovery" is a software product that we want the virtual assistant to pay special attention to. We want the system to comprehend "I need help with discovery" in the context of a product problem chatbot. In Watson Assistant, we have a variety of entity recognition methods.
• Contextual entities allow your virtual assistant to recognize entities depending on the context of the user's speech by applying deep learning features to train a named-entity recognition model. • Using grammar-based NLP approaches, system entity algorithms recognize date, time, range, number, currency, and other data in user utterances. • The administrator defines particular names, synonyms, or patterns for dictionary-based entities. Only when a phrase in the user input perfectly matches the value or one of its synonyms does the assistant identify the entity mentioned at run time. • Fuzzy match entities identify phrases that have similar syntax to the entity value and synonyms you supply, but don't need a precise match. • The user can construct a regular expression to match the entity when using a pattern-based entity.
Building these algorithms is a difficult process, especially when size is factored in. Furthermore, product limits to make it more user-friendlysuch as allowing for shorter training cycles to make it seem more responsive -contribute to the difficulty of creating and building NLP algorithms.
By reformulating initial user inquiries based on the user context and profile, we hope to increase the precision of information retrieval systems.

F. User's Profile and Context
When a user conducts a search, identifying and describing his or her working context may be reduced to identifying his or her current task and identifying associated terms from his or her profile. This is based on observing the current user's task as a contextual component (for example, searching for a restaurant or hotel, planning a trip, and so on). As a result, we create an intelligent assistant that extracts relevant phrases from the current search session, but what exactly do we mean by relevant terms? If a term is comprehensive and precise, it is relevant • Complete: The keywords are linked to a submitted query, user profile, and task at the same time. (Expanding the query.) • Exact: no stop words, repeated terms, or out-ofcontext terms are included in the terms.
These phrases are utilized to create a new reformulated query that will be sent to the information retrieval system in order to deliver context-based results. These phrases are not required to be associated with the next search session at the same user's task.
Here, we'll go over our method, which consists of three models: a task model, a user profile model, and a State Reformulated Queries (SRQ) model.
The task model is in charge of creating the current working context by selecting one task from a list of preset tasks to attach to the first query. The user profile model is in charge of utilizing the user profile by adapting the obtained results to this user using information included in the profile. The SRQ model is in charge of gathering characteristics from the current task, one attribute for each task state at the very least. The operational profile may be used to get the values of these attributes. To reformulate a user query, we first expand the query with relevant phrases before removing the unnecessary terms (query refinement). SRQ stands for the resultant query (State reformulated Query).

G. User Context Modeling
In this part, we'll provide a novel contextual analysis approach that considers the user's present task and how it evolves over time as the user's context. The shift from one stage to the next indicates that the user has finished this step of the current job. Thus, when we discuss the user context in this study, we are referring to the task that the user is working on at the time the information retrieval process happens, as well as the stages of that job. As a result, we must model the user's present task in order to broaden the user query with contextual task phrases that direct the search to the most relevant results.
As one of the contextual aspects that surround the user during the information retrieval process, the task model is used to detect and define the task that is done by the user when he sends his or her query to the information retrieval system.
To begin, we must separate the action from the job. In actuality, an activity might be something you're merely doing, with or without a purpose; it's the action you're taking, but a task is the goal you've set for yourself. In order to complete the mission, the activities are necessary. To put it another way, a task is a set of tasks that may or may not be completed. As a result, we may use a UML activity diagram to describe the user's job, which incorporates all of the actions required to complete it. The task state refers to the several stages required to complete the present work.
We rely on research questionnaires [5] in our task model, which were intended to generate tasks that were predicted to be of interest to individuals throughout the study. Subjects were instructed to think about their online information seeking behaviors in terms of tasks and to establish personal labels for each task in that research [5]. They were given some examples of activities to do, such as "writing a research paper," "traveling," and "shopping," but they were not directed, influenced, or prejudiced in their task selection in any way. The following nine task categories were created using a general classification system for all tasks specified by all subjects:

H. Conversational Flow:
Our bot's communication has been framed and intended to emulate human behavior in order to provide a user-friendly chat system that puts people at ease while overcoming the bias of machine contact.
Countless utterances that users can use while communicating with the chat system are taken into account while building conversational processes.
The Dialogskill Discussion API [14] is used in our application to create an automated conversational chat system that understands natural language and holds a conversation with the user. Dialogskill makes use of IBM Cloud Machine Learning technology, which enables apps to scale to hundreds of millions of users. When a user communicates with our software, they can use a wide range of expressions to achieve the same goal. Dialogskill, in example, offers a high-level dialogue flow for identifying user queries by mapping them to intents that have been thoroughly trained.

I. Issues Encountered
The challenges faced during the development of application includes a) Collection of data for training. The regular machine learning applications are trained using large amount of data sets which will cover most of the scenarios while the chatbots are trained on the conversations, intent detection systems are practically relied on the conversational data from the customers. So, collection of relevant data and training the model on the conversational basis is a challenging task to be done. b) Using different phrases and jargons by different individual to address the same problem or query. When used in real-world, chatbots They frequently work with test data that is drastically different from the training data. The difference in train and test data distributions is mostly due to the free-form nature of input user queries. Because these real-world questions use nonstandard paraphrases to describe the same goals, it's impossible to cover everything during training. The problem is exacerbated by the unavailability of large, high-quality training data C) Efficiency in Computation, the requirements from the user changes every moment and the retraining from the conversations and analyzing the new queries and inferencing and responding must be quick. So efficiency in responding and with contextual accuracy is the most challenging task.

A. Integrating Chatbots with Applications
Chatbots helps in interacting the user with the application in the swiftest way and they also make the application most interactive. These are helpful in maintaining a healthy relationship between the customer and application. Chatbots can be integrated in different applications like delivery, telecommunications, health care, web applications. They can also be integrated with applications like calendar, reminder and fitness tracking. By this, the users can easily communicate with the device regarding their appointments, scheduled meetings, and also to evaluate their fitness goals. Example is BookMyshow integrating a normal chatbot with WhatsApp to deliver the tickets online. Likewise, we can use Chatbot for fitness applications to remind about the exercise, diet plans to be followed and guide them. With the help of services like Amazon Web Services, Google services, IBM Watson the integration, scalability and maintenance of the chatbots have become easier.

B. Conversation-Driven Recommendation
Chatbots can also be the source for information about the customer interests. The information collected from user can be grouped together and the data can be used to understand about the trend and recommend the necessary suggestions for the user. The chatbot can recommend the diet plans, exercises by understanding the conversational flow and by learning from the previously asked questions using the Natural Language Processing (NLP) and building the relationship between user and the intent. The process has a problem "cold start problem" which means the process needs some data about customer to recommend. In order to overcome this problem, we recommend the most followed plans on which algorithm is trained. So, this would involve in the granular personalization at user level.

C. Scalable Automation with Multi-Part Queries
The Chatbots are replacing the Customer Service Individuals in every sector, so scalability and also understanding the query of the user is important to respond accurately and with speed. This study may be expanded in a number of ways. First, improve the quality of produced words, then the precision of outcomes; second, improve the task model to improve the identification of the user's task and its states. We may leverage the Chatbot technique to improve the assistant's capacity to create reformulated inquiries (SRQ), which allows the assistant to engage with a user while maintaining focused on the present task condition. We also plan to put this method to the test using a different evaluation protocol that entails creating a test collection and determining relevant results for several queries in a specific context, then comparing these relevant results to the results returned by our system for the same queries in the same context.

D. Multilingual Chatbots
To guarantee that a firm achieves its full potential, impediments such as language issues must be removed from the client journey. The impact on a firm will be disastrous if potential leads have communication challenges or if an inadequate solution is supplied simply because the user requirements were misunderstood. Language detection can be identified by using the Named Entity Detection by using the NLP algorithms, changing the SDK's supporting libraries for each language and training the chatbot in different languages rigorously will help in improving the conversations and reduce the error rate or non-contextual replies.

E. Voice Bots
Voice Bots make the communication between the customer and application touch-free making everything virtualized. Voice bots are artificial intelligence (AI)-powered software that allows a caller to navigate an interactive voice response (IVR) system using only their voice and natural language. Callers are not required to listen to menus or input digits on their keypads. They communicate with the IVR in a simplified simulation of a live operator. Voicebots go beyond limiting short-term remedies like Automated Speech Recognition (ASR) with predetermined expressions to improve voice interaction between callers and IVR. The process involves speech recognition and then processing the data using Natural Language Processing (NLP) and then training these bots on analysis, translation. These will improve the accuracy rate, customer quick and direct interactions.

VI. CONCLUSION
Artificial intelligence (AI) and machine learning have revolutionized the way we do business in recent years. The market has been captured by chatbots. Chatbots are now commonplace. Financial Services, Retail, Fitness Management, hospitals have all had breakthroughs as a result of its business implications. Chatbots can now manage client interactions 24 hours a day, seven days a week, while continually increasing the quality of replies and lowering expenses. Chatbots automate processes and relieve staff of tedious chores. It involves collection of relevant data for contextual accuracy, Using Deep Learning frameworks, NLP algorithms like "Multinominal Naïve Bayes" in order to train the chatbot on dataset on understanding users sentimental analysis, Intent detection and automate the process in order to improve the contextual accuracy. re-learning is most important aspect for improving the chatbot user experience. In this way, chatbots will build customer relationships, create brand awareness and automates tedious work and plays a huge role in shaping the business.