A New First-Order Meta-Learning Algorithm with Convergence Guarantees
El Mahdi Chayti Martin Jaggi




 numbers, compressnatbib






=1













 
    
       
            
       

       
       
      
         









 







framedtheoremTheorem
framedlemmaLemma
framedcorollaryCorollary
framedexampleExample
framedassumptionAssumption
framedpropositionProposition

theoremTheorem
exampleExample
definitionDefinition
corrolaryCorrolary


corollaryCorollary

















    [ 9.5cm11.5cm⟨⟩#1figure <ref>#1Figure <ref>#1#2figures <ref> and <ref>#1#2#3#4figures <ref>, <ref>, <ref> and <ref>#1section <ref>#1Section <ref>#1#2sections <ref> and <ref>#1#2#3sections <ref>, <ref> and <ref>#1<ref>#1chapter <ref>#1Chapter <ref>#1#2chapters<ref>–<ref>#1algorithm <ref>#1Algorithm <ref>#1#2algorithms <ref> and <ref>#1#2Algorithms <ref> and <ref>#1part <ref>#1Part <ref>#1#2parts <ref> and <ref>#1⌈ #1 ⌉#1⌊ #1 ⌋1ϵ𝕀ηbcdefghijklnopqrstuvwxyzϵθ𝐚𝐛𝐜𝐝𝐞𝐟𝐠𝐡𝐢𝐣𝐤𝐥𝐦𝐧𝐨𝐩𝐪𝐫𝐬𝐭𝐮𝐯𝐰𝐱𝐲𝐳abcdefghijklmnopqrstuvwxyz𝐀𝐁𝐂𝐃𝐄𝐅𝐆𝐇𝐈𝐉𝐊𝐋𝐌𝐍𝐎𝐏𝐐𝐑𝐒𝐓𝐔𝐕𝐖𝐗𝐘𝐙ABCDEFGHIJKLMNOPQRSTUVWXYZ01μθabcdefghijklmnopqrstuvwxyzϕαβϵλωμψσθabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZβΦΛΣmslboldbxnABCDEFGHIJKLMNOPQRSTUVWXYZ𝒜ℬ𝒞𝒟ℰℱ𝒢ℋℐ𝒥𝒦ℒℳ𝒩𝒪𝒫𝒬ℛ𝒮𝒯𝒰𝒱𝒲𝒳𝒴𝒵𝒪ℬℒ𝔸𝔹ℂ𝔻𝔽𝔾ℍ𝕀𝕁𝕂𝕃𝕄ℕ𝕆ℙℚℝ𝕊𝕋𝕌𝕍𝕎𝕏𝕐ℤΛABCDEFGHIJKLMNOPQRSTUVWXYZΣΛABCDEFGHIJKLMNOPQRSTUVWXYZnumbersnatbibA New First-Order Meta-Learning Algorithm
             with Convergence Guarantees
                
              El Mahdi Chayti
            
              Machine Learning and Optimization Laboratory (MLO), EPFL
            
            
              Martin Jaggi
            
              Machine Learning and Optimization Laboratory (MLO), EPFL
            
                September 9, 2024
            ================================================================================================================================================================
            
            § ABSTRACT 
              Learning new tasks by drawing on prior experience gathered from other (related) tasks is a core property of any intelligent system. Gradient-based meta-learning, especially MAML and its variants, has emerged as a viable solution to accomplish this goal. One problem MAML encounters is its computational and memory burdens needed to compute the meta-gradients. We propose a new first-order variant of MAML that we prove converges to a stationary point of the MAML objective, unlike other first-order variants. We also show that the MAML objective does not satisfy the smoothness assumption assumed in previous works; we show instead that its smoothness constant grows with the norm of the meta-gradient, which theoretically suggests the use of normalized or clipped-gradient methods compared to the plain gradient method used in previous works. We validate our theory on a synthetic experiment.
            
            
            § INTRODUCTION
            
            One key aspect of intelligence involves the capability of swiftly grasping new tasks by leveraging past experiences from similar tasks. Recent research has delved into how meta-learning algorithms <cit.> can acquire such a capability by learning to efficiently learn a range of tasks. This mastery allows for learning a novel task with only minimal training data, sometimes just a single example, as demonstrated in <cit.>. 
            
            Meta-learning approaches can be generally categorized into three main types.
            
            
              * Metric-learning approaches: These methods learn an embedding space where non-parametric nearest neighbors perform effectively <cit.>.
                
              * Black-box approaches: These train a recurrent or recursive neural network to either take data points as input and produce weight updates <cit.> or to generate predictions for new inputs <cit.>, attention-based models <cit.> can also be used.
                
              * Optimization-based approaches: These usually involve bi-level optimization to integrate learning procedures, such as gradient descent, into the meta-optimization problem <cit.>. The "inner" optimization involves task adaptation and the "outer" objective is the meta-training goal: the average test loss after adaptation over a set of tasks. This approach, exemplified by <cit.> and MAML<cit.>, learns the initial model parameters to facilitate swift adaptation and generalization during task optimization.
            
            
            Additionally, hybrid approaches have been explored to combine the strengths of different methods <cit.>.
            
            In this study, we concentrate on optimization-based methods, specifically MAML <cit.>, which has been demonstrated to possess the expressive power of black-box strategies <cit.>. Additionally, MAML is versatile across various scenarios <cit.> and ensures a consistent optimization process <cit.>.
            
            
            
            Practical challenges. While meta-learning initialization holds promise, it necessitates backpropagation through the inner optimization algorithm, introducing challenges; this includes the requirement for higher-order derivatives, leading to significant computational and memory overheads and potential issues like vanishing gradients. Consequently, scaling optimization-based meta-learning to tasks with substantial datasets or numerous inner-loop optimization steps becomes arduous. We aim to devise an algorithm that mitigates these constraints.
            
            These challenges can be partially mitigated by taking only a few gradient steps in the inner loop during meta-training <cit.>, truncating the backpropagation process <cit.>, using implicit gradients <cit.>, or omitting higher-order derivative terms <cit.>. However, these approximations may lead to sub-optimal performance <cit.>.
            
            Theoretical challenges. One additional challenge such methods face is theoretical relating to the convergence analysis of such methods. While it was shown in <cit.> that even the MAML objective with one inner gradient descent step is not smooth, which entails the need for complicated learning rate schedules, other works such as <cit.> simply assume that it is, even when having more than one inner step.
            
            Contributions.
            1)To address the practical challenges, we propose a new First-order MAML variant that, as its name suggests, avoids any use of second-order information, but unlike previous first-order algorithms such as FO-MAML and Reptile <cit.>, our algorithm has the advantage of having a bias (to the true meta-gradient) that can be made as small as possible, which means that we can converge, in theory, to any given precision.
            2) To address the challenges of theoretical analysis, we show that the general MAML objective satisfies a generalized smoothness assumption introduced in <cit.>. This result suggests that clipped gradient descent is better suited in this case as it was shown to outperform vanilla gradient descent under such an assumption, for example, this explains why meta-gradient clipping works in stabilizing the convergence of MAML in practice.
            3) Finally, we provide convergence rates for our method.
            
            
            § PRELIMINARIES
            
            
             §.§ Vanilla MAML
            
            
            We assume we have a set of training tasks {𝒯_i }_i=1^M drawn from an unknown distribution of tasks P(𝒯), such that for each task 𝒯_i one can associate a training _i and test _i dataset—or equivalently a training f̂_i and test f_i objective. Then, the vanilla MAML objective is that of solving the following optimization problem:
            
                ^⋆ := _∈Θ  
                    F() := 1/M∑_i=1^M [F_i():=f_i ( _i() = ( f̂_i,, ))] ,
            
            
            where ( f̂_i,, ) is an optimization algorithm that takes as input the objective f̂_i (i.e., dataset and loss), the initialization  and other hyperparameters denoted by  (.e.g., learning rate, and the number of steps), then outputs an updated task-specific parameter _i() that is hopefully a better "approximate" solution for the individual task objective f̂_i.
            
            For example, ( f̂_i,, ·) may correspond to
            one or multiple steps of gradient descent on f̂_i initialized at . For
            example, if we use one step of gradient descent with a learning rate α, then we have:
            
                _i() ≡( f̂_i,, :={α}) =  - α∇_f̂_i().
            
            To solve (<ref>) with gradient-based methods, we require a way to differentiate through . In the case of multiple steps like (<ref>), this corresponds to backpropagating through the dynamics of gradient descent. This backpropagation through gradient-based optimization algorithms naturally involves higher order derivatives and the need to save the whole trajectory to compute the meta-gradient (i.e., the gradient of F), which is a big drawback to vanilla MAML.
            
            Another (potential) drawback of MAML defined in (<ref>) is that it depends on the choice of the optimization algorithm  (since we need its specific trajectory). 
            
            
            
             §.§ First-order MAML and Reptile
            
            One option considered in the literature to address the computational and memory overheads encountered when differentiating through gradient-based optimization algorithms is to devise first-order meta-gradient approximations <cit.>. Two such approaches stand out: FO-MAML and Reptile.
            
            FO-MAML simply ignores the Jacobian dd leading to the following approximation:
            
                _FO-MAML = 1/M∑_i=1^M ∇ f_i(_i())
            
            
            The Reptile approximation is less straightforward, but the crux of it is using an average gradient over the inner optimization algorithm's trajectory. 
            
                _Reptile = 1/M∑_i=1^M  - _i()Kα
            
            where in (<ref>), K is the number of steps of  and α is the learning rate.
            
            These two approximations avoid the prohibitive computational and memory costs associated with vanilla MAML. However, both approximations introduce bias to the true meta-gradient that is irreducible, at least in the case of FOMAML <cit.> (the bias of Reptile is not clear in general).
            
            
            
             §.§ B-MAML : MAML as a fully Bi-Level Optimization Problem
            
            Ignoring the computational overhead of MAML, the memory overhead is naturally a result of the dependence of the MAML objective in (<ref>) on the choice of the inner optimization algorithm  and thus on the trajectory of ; then if one can break this dependence on , one would avoid this memory overhead; one idea to accomplish the latter is to make the MAML objective depend on the inner optimization problem rather than the specific optimization algorithm used to solve such an optimization problem. This will amount to framing MAML as the following purely bi-level optimization problem :
            
                ^⋆ := _∈Θ F() := 1/M∑_i=1^M [F_i():=f_i ( ^⋆_i() )],(outer-level)
            
            where for i∈{1,⋯,M} we define (recall that f and f̂ denote validation and training objectives respectively):
            
                ^⋆_i() := _∈Θf̂_i() + λ/2 - ^2 (inner-level)
            
            Where λ is a real hyperparameter that plays the role of the inverse of the learning rate α that MAML had, it helps control the strength of the meta-parameter or prior () relative to new data. We note that this hyperparameter can be a vector or a matrix, but we keep it as a scalar for simplicity. 
            
            We also note that the formulation (<ref>) is not new and was introduced, for example, in <cit.>.
            
            To use gradient-based methods to solve (<ref>), we need to compute the gradient ∇ F. Using the implicit function theorem and assuming that λ + ∇^2 f̂_i is invertible, it is easy to show that
            
                ∇ F_i() = (  + 1/λ∇^2 f_i(_i^⋆()))^-1∇ f_i(^⋆_i())
            
            What is noteworthy about (<ref>) is that the meta-gradient ∇ F_i() only depends on ^⋆_i() which can be estimated using any optimization algorithm irrespective of the trajectory said-algorithm will take.
            
            A downside of (<ref>) is that it involves computing the Hessian and inverting it. To reduce this burden, one can equivalently treat ∇ F_i() as a solution to the following linear system (with the unknown ∈^d):
            
                (  + 1/λ∇^2 f_i(_i^⋆()))  = ∇ f_i(^⋆_i()),
            
            which only needs access to Hessian-Vector products instead of the full Hessian and can be approximately solved with the conjugate gradient algorithm, for example, which is exactly the idea of <cit.>.
            
            In this work, we propose a different strategy that consists of writing the meta-gradient as the gradient of the solution of a perturbed optimization problem with respect to its perturbation parameter. This means we can approximate the meta-gradient using the solution of two optimization problems.
            
            
            
            
            § FIRST-ORDER B-MAML
            
            
            We consider the B-MAML objective defined in (<ref>), (<ref>); our main idea relies on perturbing the inner optimization problem (<ref>). For a perturbation parameter ν∈, and each training task 𝒯_i, we introduce the following perturbed inner optimization problem, which interpolates between validation and training objectives:
            
                ^⋆_i,ν() := _∈Θ ν f_i() + f̂_i() + λ/2 - ^2.
            
            We assume that there is a neighbourhood 𝒱_0 of 0, such that ^⋆_i,ν() is well-defined for any ν∈𝒱_0 and ∈Θ.
            Then we can show the following result:
            
                For any training task 𝒯_i, if ∇ F_i() exists, then ν↦_i,ν^⋆() is differentiable at ν=0 and 
                ∇ F_i() = -λd_i,ν^⋆()/dν|_ν=0 .
            Sketch of the proof. We use the fact that _i,ν^⋆() is a stationary point of ↦ν f_i() + f̂_i() + λ/2 - ^2 this will give us a quantity that is null for all ν∈𝒱_0, then we differentiate with respect to ν and ν=0.
            
            Proposition <ref> writes the meta-gradient ∇ F_i() as the derivative of another function that is a solution to the perturbed optimization problem <ref>, thus presenting us with a way we can approximate the meta-gradient using the finite difference method <cit.>. We consider mainly two approximations: the forward and symmetric approximations.
            
            
                ^For_i,ν() = -λ(_i,ν^⋆() - _i,0^⋆()/ν)(forward approximation)
            
                ^Sym_i,ν() = -λ(_i,ν^⋆() - _i,-ν^⋆()/2ν)(symmetric approximation)
            
            
            We note that more involved approximations (that need solving more than two optimization problems) can be engineered, but we limit ourselves, in this work, to (<ref>) and  (<ref>).
            
            Assuming that ν↦_i,ν^⋆() is regular enough near ν=0 (for example, three times differentiable on 𝒱_0 and its third derivative is bounded), then we should expect that 
            
                ∇ F_i() - ^For_i,ν() = (λν)  and  ∇ F_i() - ^Sym_i,ν() = (λν^2)
            
            
            We will provide conditions under which we get the first identity in Equation <ref> in Section<ref> and support the second experimentally in Section <ref>. 
            
            In practice, we can't realistically solve the optimization problem (<ref>) and have access to the true values of _i,ν^⋆(); instead, we will solve the problem (<ref>) approximatively using any algorithm  of our choice and assume that for a given precision δ, we can get an approximate solution _i,ν() of (<ref>) such that 
            
                _i,ν() - _i,ν^⋆()≤δ .
            
            We use g_i,ν^method for method∈{For, Sym}, to denote the estimator resulting from the use of the approximate solutions; this will introduce an additional bias (w/t ∇ F_i) to our estimators in (<ref>), (<ref>); it is easy to show that this bias should be bounded by 2λδν in the worst case. Notice that this bias term increases with small values of ν, which suggests a sweet spot for ν when including the bias terms in (<ref>).
            
            
            The overall bias is then
            
                ∇ F_i() - g^For_i,ν() = (λν +  λδν)  and  ∇ F_i() - g^Sym_i,ν() = (λν^2 +  λδν) ,
            
            minimizing for ν we get that for ν^For∼√(δ) and ν^Sys∼δ^1/3 we get:
            
                ∇ F_i() - g^For_i,ν() = (λ√(δ))  and  ∇ F_i() - g^Sym_i,ν() = (λδ^2/3) ,
            
            
            We summarize this in Algorithm <ref>.
            
            
            
            In line 10 of Algorithm <ref>, we can use any optimization algorithm to update the meta-parameters , but our theoretical analysis in Section <ref> will only consider the Gradient Descent (GD) and Clipped Gradient (ClippedGD) algorithms (or Normalized GD which is equivalent). We will show that the B-MAML objective (<ref>) has a smoothness parameter that grows with the norm of its gradient; under this type of smoothness, it is known that ClippedGD is well-suited <cit.>, Adam <cit.> is also well-suited since it estimates the curvature and uses it to normalize the gradient. We also show that under stronger assumptions, the B-MAML objective is smooth in the classical sense (meaning its gradient is Lipschitz), and in this case, GD can be used but can have a worse complexity.     
            
            Now that we have presented our main algorithm, it is time to discuss its theoretical guarantees under common assumptions used in the Bi-Level optimization literature.
            
            
            
            
            
            
            § THEORETICAL ANALYSIS
            
            In this Section, we provide theoretical guarantees of Algorithm <ref> using the forward approximation in equation (<ref>). We start by stating the assumptions that we make on the training tasks {_i}_i=1^M, then discuss the smoothness properties of the B-MAML objective defined in (<ref>) resulting from such assumptions. Finally, we discuss the convergence rate when using Gradient Descent (GD) or Clipped Gradient Descent as the meta-optimizer.
            
            
             §.§ Assumptions
            
            
            We will make use of the following assumptions 
            [training sets are well-behaved]
            For all training tasks _i, the training objective f̂_i is twice differentiable, L̂_1-smooth and has L̂_2-Lipschitz Hessian.
            [test sets are well-behaved]
            For all training tasks _i, the test objective f_i is differentiable,  L_0-Lipschitz, and has L_1-smooth Hessian.
            
            
            We will also consider the following stronger assumption on the training objectives of our tasks
            [Strong convexity]
            
            There exists μ≥ 0 such that for all training tasks _i, the inner training objective f̂_i + λ/2·^2 is μ-strongly convex.
            
            
            It is worth noting that for Assumption <ref> to hold, the functions f̂_i do not have to be strongly convex as well; in fact, we only need to choose the regularization parameter λ big enough; to be specific, under Assumption <ref>, f̂_i is L̂_1 smooth, which means that taking λ > l̂_1 will ensure Assumption <ref> holds with μ = λ - L̂_1. 
            We can also show that the perturbed problem (<ref>) will have a unique solution as long as ν∈𝒱_0=(-μ/L_1,μ/L_1).
            
            
            
            
            Finally, we will need an additional assumption on the relationship between the individual tasks {_i} and their average used in the definition of B-MAML (<ref>).
            [Bounded variance between given tasks]
            There exists ζ≥ 0, such that for all ∈Θ, we have:
            
                1/M∑_i=1^M∇ F_i()- ∇ F()^2≤ζ^2.
            
            Note that in Assumption <ref>, the quantity ζ^2 can be interpreted as the variance resulting from task sampling.
            
            
            
             §.§ Properties of B-MAML
            
            
            We will first study the bias of the forward approximation in (<ref>) compared to the true meta-gradient. We show the following proposition:
            [Bias of the forward approximation]
            Under Assumptions <ref> and <ref>, for λ≥ 2 l̂_1, for any training task _i we have:
            
                ∇ F_i() - ^For_i,ν() = (L_0/λ(L_1 + L̂_2L_0/λ) ν).
            
            
            From Proposition <ref>, the following corollary ensues:
            [Bias of FO-B-MAML<ref>]
            Under Assumptions <ref> and <ref>, for λ≥ 2 L̂_1, for a training precision δ defined as in (<ref>), choosing ν =  √(λ^2δ/L_0(L_1λ + L̂_2L_0)), then for any training task _i we have:
                
                ∇ F_i() - g^For_i,ν() = (√( L_0(L_1/λ + L̂_2L_0/λ^2)δ)).
            Discussion. As a reference, the bias of using the expression of the meta-gradient in (<ref>) while replacing _i^⋆ with an approximate solution up to precision δ leads to a bias of (δ). If, as in iMAML<cit.>, one solves the linear system in (<ref>) up to a precision δ^', then this leads to a bias of the order (δ+δ^').
            Our bias is a (√(δ)), which is worse (for small values of δ); this is to be expected since we don't use any second-order information, unlike the other methods. We note that using more advanced (and costly) finite difference approximations of the gradient in Proposition <ref> should close this gap.
            
            We will now discuss the smoothness of the B-MAML objective (<ref>). Proposition <ref> shows that this smoothness can grow with the norm of the gradient; functions satisfying such an assumption have been studied, for example, in <cit.> for classic optimization as opposed to meta-learning.
            
            [Generalized Smoothness of individual meta-objectives]
            Under Assumptions <ref> and <ref>, for λ≥ 2 l̂_1, for any training task _i we have for any ,^'∈Θ:
            
                ∇ F_i() - ∇ F_i(^' )≤min( (),(^')) - ^',
            
            where () = L_1 + L̂_2/λ∇ F_i().
            
            Combining Proposition <ref> and Assumption <ref>, we get:
            [generalized smoothness of B-MAML]
            Under Assumptions <ref>, <ref> and <ref>, for λ≥ 2 L̂_1, we have for any ,^'∈Θ:
            
                ∇ F() - ∇ F(^' )≤min((),(^')) - ^',
            
            where () = _0 + _1∇ F(),_0=L_14 + L̂_2/4λζ and _1 = L̂_2/2λ.
            
            If we additionally use strong convexity ( Assumption <ref>), then we can prove that the meta-gradient ∇ F() is bounded; this will make the B-MAML objective smooth in the classical sense.
            
            [Classical smoothness]
            Under Assumptions <ref>, <ref>, <ref> and <ref>, for λ≥ 2 L̂_1, we have for any ∈Θ: ∇ F()≤λ L_0/μ:= G .
            
            Hence, for any ,^'∈Θ we have 
            
                ∇ F() - ∇ F(^' )≤ - ^',
            
            where := _0 + G _1, for _0,_1 defined in Corollary <ref>.
            
            It is worth noting that the smoothness constant  shown in Corollary <ref> might be much larger than _0 and _1 as μ might be small.
            
            
             §.§ Convergence
            
            Now we have all the ingredients to discuss the convergence rate of Algorithm <ref>. For simplicity, we will assume that we can sample all training tasks and leave the case where this is not possible (i.e., the number of tasks M is big) to the Appendix.
            
            Given a gradient (estimate) , We consider three algorithms to update the meta-gradient:
            
            GD. Which updates the parameter in the following way:
            ← - η  .
            ClippedGD. Which updates the parameter in the following way:
            ← - ηmin(1,c/) .
            NormalizedGD. Which updates the parameter in the following way:
            ← - η/β +   .
            
            We note that ClippedGD and NormalizedGD are equivalent up to a change of the learning rate η as shown in <cit.>.
            
            Throughout this section, we denote by _0 the initialization and assume that the objective F in (<ref>) is lower bounded by F^⋆ > -∞, and denote Δ = F(_0) - F^⋆.
            [Convergence of FO-B-MAML <ref> using NormalizedGD]
            Under the generalized smoothness shown in Corollary <ref>  and its assumptions, Algorithm <ref>, using NormalizedGD with η=1/_1 and β=_0/_1, finds a meta-parameter  satisfying ∇ F()≤ε + (√(δ)) in at most (_0 Δ/ε^2+ _1^2Δ/_0) outer steps.
            [Convergence of FO-B-MAML using GD]
            Under the smoothness assumptions as in Corollary <ref>, Algorithm <ref>, using GD with η=1/_0 + G _1 (G is defined in Corollary <ref>), finds a meta-parameter  satisfying ∇ F()≤ε + (√(δ)) in at most (_0 Δ/ε^2+ G _1Δ/ε^2) outer steps.
            
            
            Theorems <ref> and <ref>  show that NormalizedGD has a better dependence on L_1 than GD. We conclude that judging from those upper bounds, it is (theoretically) better to use NormalizedGD than GD, even when strong convexity (Assumption <ref>) is satisfied.
            
            The quantity (√(δ)) in both theorems is the bias of FO-B-MAML using the forward approximation <ref>. To ensure convergence to an ε-stationary point (i.e.  such that ∇ F()≤ε) it suffices to take δ∼ε^2.
            Overall Complexity. The total number of gradient calls needed by Algorithm <ref> is simply : M ×Outer-steps(ε) ×Inner-steps(δ). For example, when Assumptions <ref> to <ref> are satisfied, using Nesterov's accelerated gradient method as the inner optimization problem, we have
            
                Inner-steps(δ) = (√(κ̂)log(1/δ)),
            
            where κ̂=L̂_1/μ is the condition number f̂_i.  hides logarithmic terms.
            If we use NomalizedGD as the outer optimizer, then the total number of gradient calls is:
            
                (M√(κ̂)log(1/δ)(_0 Δ/ε^2+ _1^2Δ/_0)) .
            
            
            We compare our method to other methods in the literature in Table <ref>.
            
            Comparison to iMAML. iMAML uses Hessian vector products to approximately solve the linear system in (<ref>), thus needing 2Mem(∇ f_i) of memory which is the same as ours. Also, hessian-vector products have about five times the cost needed to compute the gradient of neural networks <cit.>. 
            
            
            
            
            § EXPERIMENTS
            
            
            We compare our Algorithm <ref>to other methods such as iMAML<cit.>, MAML <cit.>, Reptile and FO-MAML <cit.>, in terms of the quality of the meta-gradient approximation and convergence. We consider a synthetic linear regression problem (details are in Appendix <ref>) that has the advantage of having a simple closed-form expression of the meta-gradient; we use gradient descent as the inner optimizer for all algorithms. Figure <ref> shows the quality of the meta-gradient approximation and evolution of the loss for different algorithms. We see that FO-B-MAML meta-gradient approximation benefits continuously from the increased number of inner steps (equivalent to a small δ), which is not the case for the other first-order methods like FO-MAML and Reptile. FO-B-MAML also compares favorably to iMAML, which uses the more expensive Hessian-vector products. As noted before, iMAML uses a number cg of Hessian-vector products (about five times more expensive than a gradient) on top of the inner iterations; thus, subtracting 4*cg from the inner steps should make the curves of FO-B-MAML and iMAML much closer. The same conclusions can be said about the loss curves where FO-B-MAML outperforms other first-order methods and is competitive with second-order methods: MAML and iMAML (cg=10), which is natural as they use more information. We note that FO-B-MAML outperforms iMAML with a small number of conjugate gradient steps cg∈{2,5}.
            
            
            
            § GENERAL DISCUSSION
            Extension. In this work, we stayed limited to the very simple and specific form in (<ref>),(<ref>) (a specific type of regularization and hyperparameters). We note that our approach is more general and can very easily be extended to a more general form and can be used to meta-learn the hyperparameters as well.
            
            For example, we can assume the following general inner problem
            
                _i^⋆(:={,_d,λ})=_[g(,) :=f̂_i(_d,) + λℛeg(;)] ,
            
            where _d can denote other shared parameters like a common decoder. To get the perturbed problem, we simply add the term ν f() to the function g. Then we can prove that: 
                ∇ F_i() = d ∂_ g(^⋆_i,ν(),)/dν|_ν=0
            
            and use finite differences to approximate the derivative in (<ref>).
            Limitations. One of the main limitations of our work is that by using finite differences, we need to solve the inner problem for each task at least twice. At the same time, this comes with the benefit of avoiding the use of any second-order information (and parallelization), it is still an important (open) question whether we can devise new approximations that avoid this slight memory overhead.
            
            One possible solution to avoid the use of the finite difference method is to use automatic differentiation to compute the derivative of ^⋆_ν with respect to ν since ν is just a real number, which means this should still be cheaper than MAML; however, prima facie, this should incur the same memory burden as MAML. We leave this exploration for future work. 
            
            
            
            
            § CONCLUSION
            
            We proposed a new first-order variant of MAML based on its bi-level optimization formulation. We equipped our method with a convergence theory that shows that it has an advantage over previously known first-order methods and is comparable to second-order methods, although it does not use any second-order information. We experimentally showed that our method can approximate the true meta-gradient to a high precision. We also show how to generalize our method to encoder-decoder networks and learn hyperparameters.
            
            abbrvnat
            
            § MISSING PROOFS
            
            
             §.§ Proof of Proposition <ref>
            
            The fact that ν↦_i,ν^⋆() is differentiable at ν = 0 will be proven later.
            
            We have that 
                _i,ν^⋆()∈ Argmin_ν f_i() + f_i() + λ/2 - ^2
            
            
            This means 
                ν∇ f_i(_i,ν^⋆()) + ∇f_i(_i,ν^⋆()) + λ (_i,ν^⋆() - ) =
            
            Taking the derivative of the above equation with respect to ν gives 
                ∇ f_i(_i,ν^⋆()) + ν∇^2f_i(_i,ν^⋆())d_i,ν^⋆()/dν+ ∇^2 f_i(_i,ν^⋆())d_i,ν^⋆()/dν + λd_i,ν^⋆()/dν =
            
            
            Which yields the following expression 
            
            
                d_i,ν^⋆()/dν = - (ν∇^2f_i(_i,ν^⋆())+ ∇^2 f_i(_i,ν^⋆()) + λ)^-1∇ f_i(_i,ν^⋆())
            
            
            We set ν=0 and get:
            
                d_i,ν^⋆()/dν|_ν=0 = - (∇^2 f_i(_i^⋆()) + λ)^-1∇ f_i(_i^⋆()) = -1/λ∇ F_i()
            
            
             §.§ Proof of Proposition <ref>
            
            
            Using Equation (<ref>), we have:
            
            
                _i,ν^⋆() =  - 1/λ( ν∇ f_i(_i,ν^⋆()) + ∇f_i(_i,ν^⋆()) )
            
            
            Thus 
            
                λ_i,0^⋆() - _i,ν^⋆()ν = ∇ f_i(_i,ν^⋆()) + ∇f_i(_i,ν^⋆()) - ∇f_i(_i,0^⋆())ν  .
            
            
            The form of the meta-gradient in Equation <ref> implies that:
            
                ∇ F_i() = ∇ f_i(_i,0^⋆()) - 1/λ∇^2f_i(_i,0^⋆())∇ F_i().
            (<ref>)–(<ref>) gives :
            
            
                ∇ F_i() - _i,ν^For   = ∇ f_i(_i,0^⋆()) - ∇ f_i(_i,ν^⋆())_(I)
                   + ∇f_i(_i,ν^⋆()) - ∇f_i(_i,0^⋆())ν - 1/λ∇^2f_i(_i,0^⋆())∇ F_i()_(II).
            
            
            Let's define _ν = ∇ F_i() - _i,ν^For the bias of the forward approximation.
            The norm of the first term (I) can be easily bounded using the smoothness of f_i by:
            
                (I)≤ L_1 _i,ν^⋆() - _i,0^⋆() .
            
            
            The second term (II) can be simplified using Cauchy's theorem which guarantees the existence of  such that 
            
                ∇f_i(_i,ν^⋆()) - ∇f_i(_i,0^⋆())ν = ∇^2f_i(_i,0^⋆())[_i,ν^⋆() - _i,0^⋆()ν] + 12ν∇^3f_i(_i,0^⋆())[_i,ν^⋆() - _i,0^⋆()]^2,
            
            
            Thus, using Assumptions <ref> and <ref>, we get:
            
                (II)≤L_1λ_ν + L_2/2ν_i,ν^⋆() - _i,0^⋆()^2.
            
            
            Overall, 
            
                _ν≤ L_1 _i,ν^⋆() - _i,0^⋆() + L_1λ_ν + L_2/2ν_i,ν^⋆() - _i,0^⋆()^2  ,
            
            Which implies :
            
            
                (1 - L_1λ)_ν≤_i,ν^⋆() - _i,0^⋆()( L_1 +  L_2/2ν_i,ν^⋆() - _i,0^⋆()).
            
            
            All that is left is to bound the term _i,ν^⋆() - _i,0^⋆().
            
            If we go back to (<ref>), then we can write:
            
                _i,ν^⋆() - _i,0^⋆()   = 1/λ( ∇f_i(_i,0^⋆()) - ∇f_i(_i,ν^⋆()) + ν∇ f_i(_i,ν^⋆()))
                   ≤L_1/λ_i,ν^⋆() - _i,0^⋆() + ν L_0/λ.
            
            Thus:
            
                (1 - L_1/λ) _i,ν^⋆() - _i,0^⋆()≤ν L_0/λ.
            
            
            For simplicity we assume, λ≥ 2 L_1 which gives:
            
                _i,ν^⋆() - _i,0^⋆()≤2ν L_0/λ  .
            
            
            Plugging the result in Eq (<ref>) and using λ≥ 2 L_1 gives:
            
            
                _ν≤L_0/λ( L_1 +  L_0 L_2/λ)ν .
            
            
            The overall bias resulting from using approximations of _i,ν^⋆() instead of their exact values is bounded by:
            
                L_0/λ( L_1 +  L_0 L_2/λ)ν + 2δ/ν,
            
            which is minimized for ν = √(2λ^2δL_0(L_1λ + L_0 L_2)), using this value of ν in the overall bias (<ref>), gives the result of Corrolary <ref>.
            
            
            
             §.§ Proof of Proposition <ref>
            
            
            Let ,^'∈Θ. Using Eq (<ref>), we have:
            
            
                ∇ F_i()    = ∇ f_i(_i,0^⋆()) - 1/λ∇^2f_i(_i,0^⋆())∇ F_i()
                ∇ F_i(^')    = ∇ f_i(_i,0^⋆(^')) - 1/λ∇^2f_i(_i,0^⋆(^'))∇ F_i(^')
            
                ∇ F_i() - ∇ F_i(^')    =  ∇ f_i(_i,0^⋆()) - ∇ f_i(_i,0^⋆(^')) 
                   + 1/λ( ∇^2f_i(_i,0^⋆(^'))∇ F_i(^') - ∇^2f_i(_i,0^⋆())∇ F_i())
                   =  ∇ f_i(_i,0^⋆()) - ∇ f_i(_i,0^⋆(^')) 
                   + 1/λ(∇^2f_i(_i,0^⋆(^')) - ∇^2f_i(_i,0^⋆()))∇ F_i(^') 
                   - 1/λ∇^2f_i(_i,0^⋆())(∇ F_i() - ∇ F_i(^'))
            
            Thus: 
            
                ∇ F_i() - ∇ F_i(^')   ≤ L_1 _i,0^⋆() - _i,0^⋆(^') + L_2/λ_i,0^⋆() - _i,0^⋆(^')∇ F_i(^')
                   +L_1/λ∇ F_i() - ∇ F_i(^')
            
            
            which implies:
            
                (1 - L_1/λ) ∇ F_i() - ∇ F_i(^')≤(L_1  + L_2/λ∇ F_i(^')) _i,0^⋆() - _i,0^⋆(^')
            
            
            Let's define, () := L_1/4  + L_2/4λ∇ F_i(). Exchanging  and ^', and assuming λ≥ 2 L_1, we get:
            
                ∇ F_i() - ∇ F_i(^')≤min ((),(^')) _i,0^⋆() - _i,0^⋆(^')/2
            
            
            To finish the proof, we need to bound the quantity: _i,0^⋆() - _i,0^⋆(^').
            
            We have
            
                _i,0^⋆() - _i,0^⋆(^')   =  - 1/λ∇f_i(_i,0^⋆()) - (^' - 1/λ∇f_i(_i,0^⋆(^')))
                   =  - ^' - 1/λ(∇f_i(_i,0^⋆()) - ∇f_i(_i,0^⋆(^')))
                   ≤ - ^' + L_1/λ_i,0^⋆() - _i,0^⋆(^')
            
            
            Again, choosing λ≥ 2 L_1, we get:
            
            
                _i,0^⋆() - _i,0^⋆(^')≤ 2  - ^'.
            
            
            Plugging the last inequality in Eq (<ref>), we get:
            
                ∇ F_i() - ∇ F_i(^')≤min ((),(^'))  - ^',
             which finishes the proof.
            
            
            
             §.§ Convergence of NormalizedGD and ClippedGD
            
            
            Consider a differentiable function F satisfying the following property for all ,^'∈Θ:
            
                ∇ F() - ∇ F(^')≤min ((),(^'))  - ^',
            
            and for any function .
            
            Then we have:
            
            
                F(^')    = F() + ∇ F()^⊤ (^' - ) + ∫_0^1[∇ F( + t(^' - )) - ∇ F()]^⊤(^' - )dt
            
            
            Thus 
            
                |F(^') - F() - ∇ F()^⊤ (^' - )|   ≤ |∫_0^1[∇ F( + t(^' - )) - ∇ F()]^⊤(^' - )dt|
                   ≤∫_0^1() t ^' - ^2 dt
                    = ()2^' - ^2.
            
            
            In particular,
            
                F(^')≤  F() + ∇ F()^⊤ (^' - ) + ()2^' - ^2
            
            
            Let's consider a general GD update: ^' =  - η∇ F(), where η might depend on . For this update, we have
            
                F(^')   ≤  F() - η∇ F()^2 + ()η^22∇ F()^2
                   = F() - η (1 - ()η2) ∇ F()^2
            
            
            It is easy to see that η = 1/() minimizes the right-hand side of the above inequality, which leads to:
            
                F() - F(^') ≥∇ F()^2/2 ()
            
            
            One important observation here is that the optimal step size is the inverse of the generalized smoothness, thus if the smoothness depends on the norm of the gradient or other quantities, the optimal step size depends on them too.
            
            Let's now discuss the special case where () = _0 + _1 ∇ F(.
            
            In this case, we have:
            
            
                F(^t) - F(^t+1) ≥∇ F(^t)^2/2 (_0 + _1 ∇ F(^t).
            
            
            For a given precision ε, the goal is to bound the number of steps t necessary to reach ∇ F(^t≤ε.
            
            Before reaching the goal above, we naturally have two regimes, a first one for which ∇ F(^t≥_0 / _1 and another one where ε≤∇ F(^t≤_0 / _1.
            
            If we are in the first regime, we have 
                F(^t) - F(^t+1) ≥(_0 / _1)^2/4_0 =  _0/4_1^2.
            
            
            Whereas if we were in the second regime, then we would have:
            
            
                F(^t) - F(^t+1) ≥ε^2/4_0 .
            
            
            All in all, as long as ∇ F(^t≥ε, we have
            
            
                F(^t) - F(^t+1) ≥min(ε^2/4_0,_0/4_1^2). .
            
            
            Let K be the number of steps necessary to reach the first index t such that ∇ F(^t≤ε. Assuming that the function F is lower bounded and denoting Δ = F(^0) - inf F, then 
            
            
                Δ≥ K min(ε^2/4_0,_0/4_1^2).
            
            
            Thus K ≤Δ/min(ε^2/4_0,_0/4_1^2)≤4_0Δ/ε^2 + 4_1^2Δ/_0.
            
            
            
            § DETAILS OF THE EXPERIMENTS
            
             we can equivalently write a quadratic objective that represents the task loss as:
            
                f_i() = f_i() = 1/2^⊤_i  + ^⊤_i,
            
            In this case, it is easy to show that:
            
                ^⋆_i,ν() = ((1+ν)_i + λ)^-1 (λ - (1+ν)_i)
            
            
            and
            
                ^⋆_i() = ^⋆_i,0() = (_i + λ)^-1 (λ - _i)
            
            
            The meta-gradient of task i has the expression:
            
                ∇ F_i()    = λ (_i + λ)^-1∇_ℒ_i(^⋆_i())
                   = λ (_i + λ)^-1(_i(_i + λ)^-1 (λ - _i) + _i)
            
            
            And it is not difficult to verify that indeed ∇ F_i() = -λd^⋆_i()/dν|_ν = 0.
            
            Because we have the exact expression of the meta-gradient, we can compute it exactly and compare the relative precision of different approximation methods. This is what we did in Figure <ref>. ]
