Global Convergence of MAML and Theory-Inspired Neural Architecture Search for Few-Shot Learning

Model-agnostic meta-learning (MAML) and its variants have become popular approaches for few-shot learning. However, due to the non-convexity of deep neural nets (DNNs) and the bi-level formulation of MAML, the theoretical properties of MAML with DNNs remain largely unknown. In this paper, we first prove that MAML with over-parameterized DNNs is guaranteed to converge to global optima at a linear rate. Our convergence analysis indicates that MAML with over-parameterized DNNs is equivalent to kernel regression with a novel class of kernels, which we name as Meta Neural Tangent Kernels (MetaNTK). Then, we propose MetaNTK-NAS, a new training-free neural architecture search (NAS) method for few-shot learning that uses MetaNTK to rank and select architectures. Empirically, we compare our MetaNTK-NAS with previous NAS methods on two popular few-shot learning benchmarks, miniImageNet, and tieredImageNet. We show that the performance of MetaNTK-NAS is comparable or better than the state-of-the-art NAS method designed for few-shot learning while enjoying more than 100x speedup. We believe the efficiency of MetaNTK-NAS makes itself more practical for many real-world tasks.


Introduction
Meta-learning, or learning-to-learn (LTL) [59], has received much attention due to its applicability in few-shot image classification [23,69], meta reinforcement learning [18,23,62], and other domains such as natural language processing [8,78] and computational biology [43]. The primary motivation for meta-learning is to fast learn a new task from a small amount of data, with prior experience on similar but different tasks. There are a few meta learning approaches designed for few shot image classification, such as metric-based [57,63], model-based [45,56], optimizerbased [39,52]. Model-agnostic meta-learning (MAML) is a * equal contribution popular gradient-based meta-learning approach, due to its simplicity and good performance in many meta-learning tasks [18,19]. MAML formulates a bi-level optimization problem, where the inner-level objective represents the adaption to a given task, and the outer-level objective is the meta-training loss. There are many variants of MAML, [20,21,31,46,51], and they are almost always applied together with deep neural networks (DNNs) in practice.
Even though MAML with DNNs is empirically successful, this approach still lacks a thorough theoretical understanding. For example, the most common practice is to use gradient descent approach (e.g., SGD or Adam [34]) to train MAML with DNNs, and the optimization can usually obtain almost zero training loss and 100% training accuracy (i.e., global convergence) with suitable hyper-parameters [3,19]. However, prior theoretical works could not account for the global convergence of MAML trained with gradient descent on non-linear neural nets of more than two layers. Hence, a crucial question that remains unknown for MAML optimization is: Can MAML with DNNs converge to global minima?
This question motivates us to analyze the optimization properties of MAML with DNNs, and we provide a positive answer with rigorous theoretical analysis. Briefly, for over-parameterized DNNs, we analyze the optimization trajectory of MAML with square loss and prove that the training loss is guaranteed to converge to zero at a linear rate. Additionally, in this convergence analysis, we find the DNN trained by MAML can be described by a kernel regression, with a novel class of kernels that we name as Meta Neural Tangent Kernels (MetaNTK).
One may wonder whether our theory has any practical implications. Intuitively, our theory reveals that MetaNTK is closely related to the performance of MAML. To demonstrate the practical value of our theory, we provide a concrete use case of MetaNTK: MetaNTK can help us efficiently find neural net architecture for few-shot learning.
Most meta-learning algorithms adopt standard network structures such as ConvNets [36], ResNets [22] and Wide ResNets [79] for few-shot image classification, the most popular task to benchmark meta-learning. However, these network structures were developed on supervised learning benchmarks such as CIFAR [35], and ImageNet [12], and recently, it has been shown that these popular structures actually overfit to the supervised learning task on these datasets [54]. This indicates that the popular network structures may not be optimal for tasks other than supervised learning, such as few-shot learning. Thus, one may naturally consider neural architecture search (NAS) [15,42,81] to automatically search for neural net architectures that are suitable for few-shot learning. To this end, prior works [16,32,40] designed NAS methods specific for few-shot learning, but they require substantial computational cost (e.g., the search cost of [32] and [16] on mini-ImageNet is 100 and 7 GPU days, respectively; the training of [40] takes 150 GPU days on miniImageNet), which makes them impractical for many real-world tasks and not environmentalfriendly [13,74]. Hence, a natural question is: Can we accelerate NAS for few-shot learning to have much lower or even negligible search cost (compared to training cost)?
We provide an efficient solution to this quest, MetaNTK-NAS, which is inspired by the MetaNTK we derive in our global convergence analysis of MAML. Briefly, we use the condition number of MetaNAK as an indicator for the trainability of networks under MAML. Since MetaNTK is directly computed at initialization, no training is needed in the search stage, leading to a surprisingly small search cost (e.g., less than 0.07 GPU day on mini-ImageNet).
Our main contributions are summarized below: • Global Convergence and Induced Kernels of MAML 1 : We prove that with over-parameterized DNNs (i.e., DNNs with a large number of neurons in each layer), MAML is guaranteed to converge to global optima with zero training loss at a linear rate. The key to our proof is to develop bounds on the gradient of the MAML objective, and then analyze the optimization trajectory of DNN parameters trained under MAML. Furthermore, we show that in the over-parameterization regime, the output of MAML-trained networks becomes equivalent to the output of a special kernel regression with a new class of kernels, Meta Neural Tangent Kernels (MetaNTK).
• Theory-Inspired Efficient NAS for Few-Shot Learning: We propose MetaNTK-NAS, a new NAS method for few-shot learning that takes advantage of MetaNTK. Briefly, it uses the condition number of the MetaNTK of each network as an indicator for its trainability under meta-learning. Empirically, our MetaNTK-NAS is comparable or better than MetaNAS [16], the state-of-theart NAS method for few-shot learning, on both miniIm-ageNet and tieredImageNet, while consuming 100x less cost in the search process.

Related Works
Meta-Learning Optimization. The MAML family (i.e., MAML [19] and its variants) is a popular approach for meta-learning. Several recent works theoretically analyze MAML or its variants in the case of convex objectives [5,7,20,24,31,75]. However, neural nets are non-convex, so these works do not account for common practices of MAML with neural nets. On the other hand, [17,28,51,80] consider the non-convex setting, but they only provide convergence to stationary points. Since stationary points can have high training/test error, the convergence to them is not very satisfactory. In particular, [67] proves the global convergence of MAML for a special class of two-layer networks that has frozen last layers with binary weight values. The unrealistic setting of [67] makes its results much weaker than our work, where our analysis is compatible with any depth and has no restriction on layer weight values. Notably, the MAML family shares similarities with multi-task learning from an optimization perspective [66].
Neural Tangent Kernels. Recently, there is a line of works studying the optimization of neural networks in the setting of supervised learning, e.g., [2,14,26,30,47], and many of them are restricted to two-layer networks. Notably,[26] proves that gradient flow on infinitely wide neural nets of any depth is guaranteed to converge to global optima, while its training dynamics can be described by kernel regression with neural tangent kernels (NTK). Further, [37] relaxes some assumptions of [26], and proves that gradient descent on finitely wide neural nets of any depth also enjoys global convergence as long as the width is large enough and the learning rate is sufficiently low. Notice that these works are tailored for supervised learning, thus it is unknown if global convergence is also guaranteed in other problems using neural networks. In this work, we leverage the tools of NTK from [26,37] to analyze MAML in the few-shot learning setting, and our analysis can be easily generalized to other variants of MAML such as [9,50,51].
Neural Architecture Search. Neural Architecture Search (NAS) is proposed to automate neural architecture discovery to replace cumbersome manual designs for various deep learning tasks. Early works successfully utilize reinforcement learning [6,81] and evolutionary algorithm [53] to find high-performance architectures. However, most of these methods are computationally expensive. To enable efficient architecture search, DARTS [42] proposed continuous relaxation of the architecture representation to allow search via gradient descent. Unfortunately, DARTS is hard to optimize and may suffer from performance degradation due to its weight-sharing strategy [68,77]. To further accelerate architecture search, [44] proposed trainingfree NAS to evaluate randomly initialized architectures, thus fully eliminating neural network training during the search. Some following training-free methods propose to search with NTK [11,72], linear regions [11] and pruningrelated criterion [1]. On the other hand, there are a few works applying NAS to few-shot learning using some metalearning algorithms.
[32] apply progressive neural architecture search to few-shot learning and [16,40] adopt DARTSvariants. But these approaches are very costly (e.g., [32,40] take more than 100 GPU days and [16] takes over 1 GPU week), thus it remains unexplored how to efficiently apply NAS to few-shot learning.

Preliminaries
Few-Shot Learning Consider a few-shot learning problem with a set of training tasks that contains N supervised- where (X i , Y i ) represents n query samples (i.e. test samples of T i ) with corresponding labels, while (X i , Y i ) represents m support samples (i.e. training samples of T i ) with labels. Then, we denote are training tasks for metalearners to train on (i.e., for meta-training). In the evaluation stage, an arbitrary test task T = (X, Y, X , Y ) is picked, and the labeled support samples (X , Y ) are given to the trained meta-learner as input, then the meta-learner is asked to predict the labels of the query samples X from T . Notice that this few-shot learning problem above can also be called a n-shot k-way learning problem.
Neural Net Setup Consider a neural network f θ with L hidden layers, where parameters θ ∈ R D . For i ∈ [L], we use l i to denote the width of the i-th hidden layer. Without loss of generality, we consider all hidden layers have the same width 2 , i.e., l 1 = l 2 = · · · = l L = l. We consider the parameters θ are Gaussian initialized 3 , with details shown in Appendix A.
MAML The algorithm of MAML is shown in Algorithm 1. For simplicity, it shows MAML with one inner-loop update step, while our theory is compatible with arbitrary steps of inner-loop update (e.g., Line 5 of Algorithm 1 can be modified to have multiple gradient descent steps). For convenience, we define a meta-output function F as the output of the model f with adapted parameters. For MAML with one inner-loop step, the meta-output on arbitrary task 2 This same-width assumption is not a necessary condition. One can also define l = min {l i } L i=1 instead and all theoretical results in this paper still hold true. 3 Kaiming initialization [22]is also a kind of Gaussian initialization. Evaluate the loss of f θ on support samples of Ti: Compute adapted parameters θ i with gradient descent: Evaluate the loss of f θ i on query samples of Ti: end for 8: Update parameters with gradient descent: ) x∈X is the concatenation of model outputs on all samples in X.
In this paper, we consider the square loss function (ŷ, y) = 1 2 ŷ − y 2 2 for convenience. Then the MAML training loss is is the concatenation of meta-outputs.
Second-Order Gradient (Hessian) in MAML It is well known that gradient descent on the MAML objective (2) induces Hessian terms. For example, for MAML with one inner-loop step such as (1), the gradient of objective (2) is where ∇ 2 θ (f θ (X ), Y ) ∈ R D×D is a Hessian term. Modern neural nets typically have millions of parameters, e.g., D > 10 7 in  that is commonly used in recent few-shot learning works [38,60]. Thus the Hessian terms usually have huge computation and memory cost.

Theoretical Results
Notation. For notational convenience, we denote the Jacobian of the meta-output on training data as J(θ) = ∇ θ F θ (X , X , Y ), and define a kernel function, which we name as Meta Neural Tangent Kernel function (MetaNTK). As the width l approaches infinity, for Gaussian randomly initialized parameters θ 0 , the kernel function Φ θ0 (·, * ) becomes a deterministic function independent of θ 0 (proved by Lemma 3 in Appendix B), denoted as For convenience, we denote F t (·) F θt (·), f t (·) f θt (·) andΦ t (·, * ) Φ θt (·, * ). For any diagonalizable matrix M , we use σ min (M ) and σ max (M ) to denote its least and largest eigenvalues.

Global Convergence of MAML
Suppose the neural network is sufficiently overparameterized, i.e., the width of hidden layers, l, is large enough. Then, we prove that gradient descent on the MAML objective (2) is guaranteed to converge to global optima with zero training loss at a linear rate. The detailed setup, assumptions, and proof can be found in Appendix B. We provide a simplified theorem below.
Theorem 1 (Global Convergence). Define Φ = lim l→∞ 1 l J(θ 0 )J(θ 0 ) T and η 0 = 2 σmax(Φ)+σmin(Φ) . For arbitrarily small δ > 0, and there exist R > 0, l * ∈ N, and λ 0 > 0, such that: for width l ≥ l * , running gradient descent with learning rates η < η0 l and λ < λ0 l over random initialization, the following upper bound on the training loss holds true with probability at least 1 − δ: Main Proof Ideas Here, we depict the big picture of our global convergence proof for MAML with DNNs. To prove the global convergence of MAML with DNNs, we first obtain Lemma 1 (shown in Appendix B), which indicates that the Jacobian of the meta-output, J, changes locally in a small region under perturbations on initial network parameters. Then, we analyze the training dynamics of MAML and show that the parameter movement during training is confined in a small region. Hence, the Jacobian is stable across training, indicating the loss landscape is almost quadratic in the local neighborhood of initialization. Importantly, we find that for sufficiently large width, there definitely exists a global minimum with zero training loss inside the neighborhood of any parameter initialization θ 0 . As a result, the almost quadratic loss landscape guarantees that gradient descent with a sufficiently small learning rate will reach this global minimum in the neighborhood at a linear rate.
Challenges Even though the big picture of our global convergence proof for MAML may look intuitive and simple, there exist several severe challenges in the analysis that do not appear in the supervised learning setting. Here we give one example of the challenges we deal with in the analysis: MAML is a bi-level optimization problem, and each (outer-loop) gradient descent step on its training objective (2) consists of (multiple) inner-loop gradient descent steps. Hence, the Jacobian (i.e., the gradient of the meta-output) consists of Hessian (i.e., second-order gradient) terms that do not exist in supervised learning models, and these Hessian terms appear in the form of matrix exponentials. In order to prove the local stability of the Jacobian (i.e., Lemma 1), we utilize non-trivial theoretical tools on matrix exponentials [29, 61] that can tackle this challenge.

Equivalence between MAML and Kernels
Analytical Expression of Meta-Output. In the setting of Theorem 1, the training dynamics of the MAML can be described by a differential equation where we denoteΦ 0 ≡Φ θ0 ((X , X , Y ), (X , X , Y )) and F t ≡ F θt for convenience. Notice that (7) is a first-order ODE. The solution of this ODE gives rise to the analytical expression of F t on arbitrary task T = (X, Y, X , Y ), whereΦ 0 (·) ≡Φ θ0 (·, (X , X , Y )) and T η Φ0 (t) = Φ −1 0 I − e −ηΦ0t are shorthand notations. Here, we provide a formal definition of NTK [26,37], which will be used shortly.
Definition 1 (NTK). For any neural net function f : R k → R with randomly initialized parameters θ 0 , its neural tangent kernel function is defined asΘ 0 (·, * ) ≡Θ θ0 (·, * ) := ∇ θ0 f θ0 (·)∇ θ0 f θ0 ( * ) , and it converges to a deterministic kernel as the width l approaches infinity [26,37], Below, we provide an analytical expression of Meta Neural Tangent Kernel (MetaNTK) for MAML in the infinite width limit, indicating that the kernel function Φ defined in (5) can be equivalently viewed as a composite kernel function built upon NTK function Θ(·, * ). The derivation of this expression can be found in Lemma 3 in Appendix B.
Definition 2 (MetaNTK in the Infinite Width Limit). As the width l approaches infinity, MetaNTK can be expressed as Φ ≡ Φ((X , X ), (X , X )) ∈ R knN ×knN , which is a block matrix that consists of N × N blocks of size kn × kn. For i, j ∈ [N ], its (i, j)-th block is where φ : The following theorem shows that as the width of neural nets approaches infinity, MAML becomes equivalent to a special kernel regression with the MetaNTK of Definition 2. The proof is provided in Appendix D.
Theorem 2 (MAML as Kernel Regression). Suppose learning rates η and λ are infinitesimal. As the network width l approaches infinity, with high probability over random initialization of the neural net, the MAML output, (8), converges to a special kernel regression, where G is a function defined below.
Remarks. The kernel Φ is whatΦ 0 converges to as the network width approaches infinity. However,Φ 0 ≡ Φ 0 ((X , X , Y ), (X , X , Y )) depends on Y and Y , while Φ ≡ Φ((X , X ), (X , X )) does not, since the terms in Φ depending on Y or Y all vanish as the width approaches infinity. Although (12) is a sum of two kernel regression terms, it can still be viewed as a single special kernel regression relying on MetaNTK Φ. Notably, Φ can be seen as a composite kernel built upon the base kernel function Θ.

MetaNTK-NAS
Recently, there has been a series of training-free NAS works that reduce the search cost of NAS by directly searching over untrained candidate structures [11,41,44,73] (The higher ∆Ct,o j , the more likely we will prune oj) (The lower ∆Rt,o j , the more likely we will prune oj) key of these works is to measure certain properties or metrics of untrained networks that are correlated with the final training/test accuracy. Among them, TE-NAS [11] utilizes two theory-motivated metrics of untrained networks to achieve training-free NAS: (i) the condition number of the neural tangent kernel (NTK), which can be seen as an indicator for the trainability of the network under supervised learning; (ii) the number of linear regions in the input space, which implies the expressivity (i.e., representation power) of the network. Empirical studies of [11] confirm that these two metrics of untrained networks are correlated with the test accuracy of trained networks with the same structures.
Since few-shot learning is quite different from supervised learning, metrics specific to supervised learning may not be suitable for few-shot learning. For example, NTK is derived in the supervised learning setting, thus the use of condition number of NTK in TE-NAS [11] might be ineffective in few-shot learning. A natural candidate for fewshot learning is the MetaNTK we derive in Theorem 2, which can be viewed as the counterpart of NTK in metalearning, thus it is a natural idea to replace NTK with MetaNTK in TE-NAS to accommodate the few-shot learning task, which is the core of our proposed MetaNTK-NAS.
Briefly speaking, the main idea of our MetaNTK-NAS is to compute an importance score for each untrained can- didate structure by the condition number of MetaNTK and the number of linear regions in the input space, then search for a structure that maximizes this score. Specifically, for each candidate structure N with parameters θ 0 randomly initialized by Kaiming Initialization [22], we sample a batch of training tasks are n query samples and m support samples, respectively. Then, we compute the MetaNTK of the network based on the analytical expression derived in Eqs. (10) and (11). Notice that Eq. (11) demonstrates the MetaNTK Φ is a composite kernel built upon the NTK kernel function in the infinite width limit. We assume this holds approximately true for finitely wide networks, and use the formula (11) to build MetaNTK Φ θ0 from NTK kernel functionΘ θ0 . This approach has a computational benefit: if we compute MetaNTK following the definition in (4), that will involve second-order gradients; however, building MetaNTK from NTK following (11) could get rid of this burden sinceΘ θ0 is computed purely from first-order gradients. Also,Φ θ0 is positive definite 4 , thus its eigenvalues are all positive, and we can define its condition number to be We compute another metric following Definition 1 of [11], The condition number C N indicates the trainability 5 of the network structure (the lower, the better) under metalearning, and R N stands for the representation power of the structure (the higher, the better). Our Algorithm 1 is designed to minimize C N and maximize R N over candidate structures in the search space, following the algorithm design of TE-NAS [11]. An illustration of Algorithm 1 is provided in Fig. 1. 4 Since NTK is positive definite [26] and we build MetaNTK from NTK in a way that preserves the positive definiteness. 5 The connection between the condition number of NTK and trainability is discussed in Sec. 3.1.1 of [11] 6. Experiments

Experiment Setup
We conduct experiments on two popular few-shot image classification datasets, mini-ImageNet and tiered-ImageNet, which both are subsets of ImageNet [12]. And our experiments consist of three stages: search, train and evaluate. Here we give an overview of the datasets.
• mini-ImageNet Implementation Details The neural network we use is obtained by stacking 5 or 8 searched cells together. Cells located at the 1/3 and 2/3 of the total depth of the network 6 are reduction cells, where we decrease the spatial resolution and double the number of channels 7 . We set the initial number of channels to 48 8 . To search for the candidate cells, we start with a supernetwork N 0 composed of all possible edges and operations. We follow TE-NAS [11] to prune one operator on each edge by its importance per round. The importance of each operator is measured by the change of condition number of MetaNTK C N and the number of linear regions R N before and after being pruned. We repeat the process until the supernetwork N k becomes a singlepath network. We summarize our algorithm in Algorithm 1.
To evaluate the architecture searched by MetaNTK-NAS, we train the network on the same dataset where the search is conducted. For the training, we keep the same number of cells and the initial number of channels used in the search stage. As for the training recipe, we use RFS [60] (without their additional knowledge distillation trick), an FSL method in the fashion of pre- Hardware Most of our experiments were run on NVIDIA V100s, and the rest were run on NVIDIA RTX 3090s. Each experiment is run on a single GPU at a time. The search cost of MetaNTK-NAS is benchmarked on V100s.

Experiment Results
Empirical Results Each experiment of MetaNTK-NAS and MetaNAS(retrained) is repeated over at least 3 runs of different random seeds. We evaluate each trained model on 1000 test tasks randomly sampled from the test set, and report the mean and standard deviation of the test accuracy.
Performance Comparison In Table 1, we compare MetaNTK-NAS with multiple meta-learning algorithms on miniImageNet and tieredImageNet under 5-way few-shot classification setting. Among these algorithms, MetaOpt-Net is the state-of-the-art gradient-based meta-learning algorithm, and RFS is an efficient few-shot learning algorithm, while AutoMeta, T-NAS++, and MetaNAS are existing NAS algorithms specifically designed for few-shot learning. Compared to MetaOptNet and RFS, which use (a) Normal cell (5 cells, miniImageNet).
(c) Normal cell (5 cells Table 2. Ablation study on mini-ImageNet. The row "Linear Region" stands for NAS with only the number of linear regions. The row "Random Cell" evaluates stacks of randomly sampled candidate cells from the search space. ResNet-12 as backbone architecture, our method outperforms them with a much fewer number of parameters (2.5x∼6x fewer). Besides, our MetaNTK-NAS achieves comparable or better performance than MetaNAS, the stateof-the-art NAS algorithm for few-shot learning across various settings on the two datasets (cf. the last 4 rows of Tab. 1). Examples of searched cells are also shown in Fig. 2. Efficiency Comparison While achieving competitive performance, our method enjoys 100x faster search speed (1.54 GPU hours search cost compared to 168 GPU hours search cost of MetaNAS on miniImageNet for 5-cells structures). Since MetaNAS cells are obtained by training supernetwork in the small-scale regime of 100k parameters on miniImageNet, we believe that comparing our search cost of 5-cells setup on miniImageNet to theirs is fair. We also believe MetaNTK-NAS is likely to have an even larger improvement in search speed compared to MetaNAS on tieredImageNet 10 or larger datasets. Therefore, we can conclude that MetaNTK-NAS is comparable to or better than the state-of-the-art of NAS methods for few-shot learning with 100x faster search speed.

Ablation Experiments
In this section, we conduct ablation studies to analyze the effects of different ingredients used in MetaNTK-NAS. We compare the following setups with different combinations of components: (a) we conduct a search with TE-NAS [11], which searches with NTK and number of linear regions 11 ; (b) we conduct a search using only the number of linear regions (no NTK or meta-NTK is used); (c) we conduct a 10 The experiments of the original MetaNAS paper [16] is limited to miniImageNet and Omniglot (a much smaller dataset). 11 We use the same number of training samples to compute MetaNTK and NTK for a fair comparison. random search, where we randomly sample candidate cells from the search space.
Tab. 2 shows the results of our ablation study on mini-ImageNet. The improvement of MetaNTK-NAS over the rest methods indicates the usefulness of the MetaNTK condition number in NAS for few-shot learning. Notice that the NTK condition number seems to have adverse effects on the performance. It indicates that NTK, which is derived in supervised learning, does not fit few-shot learning well.

Conclusion
In this paper, we first focus on the optimization properties of model-agnostic meta-learning (MAML) equipped with deep neural networks (DNNs), and prove the global convergence of MAML with over-parameterized deep neural nets. Based on the convergence analysis, we prove that in the infinite width limit of DNNs, MAML converges to a kernel regression with a new class of kernels, which we name as Meta Neural Tangent Kernel (MetaNTK). Inspired by recent works that apply Neural Tangent Kernel (NTK) to NAS for supervised learning [11,72], we propose MetaNTK-NAS, a new NAS method for few-shot learning based on our derived MetaNTK. Empirically, we compare MetaNTK-NAS with prior works, and observe that the performance of MetaNTK-NAS is comparable or better than the state-of-the-art NAS methods for few-shot learning on miniImageNet and tieredImageNet, while enjoying 100x less search cost.

Overview of the Appendix
The appendix is divided into the following sections, • Sec. A: Describes the neural network setup and parameterization.
• Sec. B: Presents theoretical results and proof regarding the global convergence of gradient-based meta-learning.
• Sec. C: Derives the expression of MAML output.
• Sec. D: Derives the equivalence between MAML and kernel regressions.
• Sec. E: Presents more details of experiments in Sec. 6.

A. Neural Network Setup
In this paper, we consider a fully-connected feed-forward network with L hidden layers. Each hidden layer has width l i , for i = 1, ..., L. The readout layer (i.e. output layer) has width l L+1 = k. At each layer i, for arbitrary input x ∈ R d , we denote the pre-activation and post-activation functions by h i (x), z i (x) ∈ R li . The relations between layers in this network are where W i+1 ∈ R li×li+1 and b i+1 ∈ R li+1 are the weight and bias of the layer, ω l µν and b l ν are trainable variables drawn i.i.d. from zero-mean Gaussian distributions at initialization (i.e., σ 2 ω li and σ 2 b are variances for weight and bias, and σ is a point-wise activation function.

B. Proof of Global Convergence for Gradient-Based Meta-Learning with Deep Neural Networks
In this section, we will prove the global convergence for gradient-based meta-learning with over-parameterized neural nets. To prove the global convergence theorem, we introduce several key lemmas first, i.e., Lemma 1, 2, 3. Specifically, the subsections of this section are formulated as follows. Notice that in this section, we consider the standard parameterization scheme of neural networks shown in (16). The global convergence theorem, Theorem 1, depends on several assumptions and lemmas. The assumptions are listed below. After that, we present the lemmas and the global convergence theorem, with proofs in Appendix B.1,B.3,B.4 and B.5. For Corollary 3.1, we append its proof to Appendix C.
Assumption 1 (Bounded Input Norm). ∀X ∈ X , for any sample x ∈ X, x 2 ≤ 1. Similarly, ∀X ∈ X , for any sample x ∈ X , x 2 ≤ 1. (This is equivalent to a input normalization operation, which is common in data preprocessing.) Assumption 2 (Non-Degeneracy). The meta-training set (X , Y) and the meta-test set (X , Y ) are both contained in some compact set. Also, X and X are both non-degenerate, i.e. ∀X, X ∈ X , X = X, and ∀X , X ∈ X , X = X .
Assumption 4 (Full-Rank). The kernel Φ defined in Lemma 3 is full-rank.
These assumptions are common, and one can find similar counterparts of them in the literature for supervised learning [4,37]. In particular, notice that Assumption 3 is just for simplicity purpose without loss generality. In fact, one can directly set l = min i∈[L] l i as the minimum width across hidden layers, and all theoretical results in this paper still hold true [37].
As defined in the main text, θ is used to represent the neural net parameters. For convenience, we define some short-hand notations: and where we use the 2 loss function (ŷ, y) = 1 2 ŷ − y 2 2 in the definition of training loss L(θ t ) in (23), and theΦ t in (24) is based on the definition 12 ofΦ θ (·, ) in Sec. 4.1.
Below, Lemma 1 proves the Jacobian J is locally Lipschitz, Lemma 2 proves the training loss at initialization is bounded, and Lemma 3 provesΦ 0 converges in probability to a deterministic kernel matrix with bounded positive eigenvalues. Finally, with these lemmas, we can prove the global convergence of MAML in Theorem 3.
Lemma 2 (Bounded Initial Loss). For arbitrarily small δ 0 > 0, there are constants R 0 > 0 and l * > 0 such that as long as the width l > l * , with probability at least (1 − δ 0 ) over random initialization, which is also equivalent to Proof. See Appendix B.3.
Note the update rule of gradient descent on θ t with learning rate η can be expressed as The following theorem proves the global convergence of MAML under the update rule of gradient descent.
In the results of Theorem 3 above, (29) considers the optimization trajectory of network parameters, and show the parameters move locally during training. (30) indicates the kernel matrixΦ t changes slowly. Finally, (32) demonstrates that the training loss of MAML decays exponentially to zero as the training time evolves, indicating convergence to global optima at a linear rate.

B.1. Helper Lemmas
Lemma 4. As the width l → ∞, for any vector a ∈ R m×1 that a F ≤ C with some constant C > 0, we have where θ is randomly intialized parameters.
Proof. Notice thatΘ with gradient as where we apply a dot product in the first two dimensions of 3-tensors and matrices to obtain matrices. Then, it is obvious that our goal is to bound the Frobenius Norm of Below, we prove that as the width l → ∞, the first and second terms of (36) both have vanishing Frobenius norms, which finally leads to the proof of (33).
• First Term of (36). Obviously, reshaping ∇ 2 θ f θ (x) ∈ R 1×D×D as a R D×D matrix does not change the Frobenius norm Proof of Lemma 5.
Overview. In this proof, we consider the expression and we prove the terms of (45), (46) and (47) all have vanishing Frobenius norm. Thus, (44) also has vanishing Frobenius norm in the infinite width limit, which is exactly the statement of (42). This indicates that (43) also has a vanishing Frobenius norm, sinceΘ θ (X, X ) can be seen as a stack of n copies ofΘ θ (x, X ), where n is a finite constant.
Step I. Each factor of (44) has bounded Frobenius norm.
[10] shows that largest eigenvalues ofΘ θ are of O(L), and we knowΘ θ is positive definite [4,26], thus it is obvious the eigenvalues of I − e −λΘ θ τ fall in the set {z | 0 < z < 1}. Therefore, certainly we have In conclusion, we have shown Step II. Bound (45). Without loss of generality, let us consider the neural net output dimension k = 1 in this proof, i.e., f θ : R d → R. (Note: with k > 1, the only difference is that ∇ θ f (X ) ∈ R mk×D , which has no impact on the proof). Then, we havê with gradient as where we apply a dot product in the first two dimensions of 3-tensors and matrices to obtain matrices. Based on (48), we know that Then, applying (33), we have Step III. Bound (46) and (47) • Bound (46): Then, we consider ∇ θ F θ (X, X , Y ), the gradient of F θ (X, X , Y ) in (58), By Lemma 5, we know the last term of (59) has a vanishing Frobenius norm as the width increases to infinity. Thus, for any ε > 0 and 0 < δ < 1, there exists l * > 0 s.t. for width l > l * , with probability at least 1 − δ, the last term of (59) is of O(ε), i.e., Since O(ε) is of a negligible order, we do not carry it in the remaining proof steps for simplicity, and it does not affect the correctness of the derivations (since the bounds of this Lemma are probabilistic). Now, let us consider the SVD decomposition on 1 where U ∈ R km×km , V ∈ R D×km are orthonormal matrices while Σ ∈ R km×km is a diagonal matrix. Note that we take km ≤ D here since the width is sufficiently wide. Then With these results of SVD, (60) becomes where H θ ≡ H θ (X , X ) = 1 l ∇ θ f θ (X ) ∇ θ f θ (X ) ∈ R D×D , and the step (62) can be easily obtained by a Taylor expansion similar to (61).
Note that H θ is a product of ∇ θ f θ (X ) and its transpose, hence it is positive semi-definite, and so does e −λHτ . By eigen-decomposition on H, we can easily see that the eigenvalues of e −λHτ are all in the range [0, 1) for arbitrary τ > 0. Therefore, it is easy to get that for arbitrary τ > 0, By Lemma 1 of [37], we know that there exists a K 0 > 0 such that for any X and θ, Combining (63) and (64), we have which is equivalent to Now, let us study the other term of interest, To bound J(θ) − J(θ) F , let us consider It is obvious that e −λH θ τ op , e −λHθτ op ≤ 1. Also, by the relation between the operator norm and the Frobenius norm, we have Besides, Lemma 1 of [37] indicates that there exists a K 1 > 0 such that for any X and θ,θ ∈ B(θ 0 , Cl −1/2 ), Therefore, (72) gives and then (70) is bounded as As for (71), notice that · op ≤ · F and (64) give us Then, to bound e −λH θ τ − e −λHθτ op in (71), let us bound the following first Then, with the results above and a perturbation bound 13 on matrix exponentials from [29], we have where we used the facts H θ op = Θ θ op ≥ O(1) [10,71] and (76) and (78), we can bound (71) as Finally, with (75) and (79), we can bound (67) as Finally, combining these bounds on (70) and (71), we know that Taking K = max{K 0 , K 3 } completes the proof.
[26] proves that for sufficiently large width,Θ 0 is positive definite and converges to Θ, the Neural Tangent Kernel, a full-rank kernel matrix with bounded positive eigenvalues. Let σ min (Θ) and σ max (Θ) denote the least and largest eigenvalue of Θ, respectively. Then, it is obvious that for a sufficiently over-parameterized neural network, the operator norm of Θ(X, X )Θ −1 (I − e −λΘτ ) can be bounded based on σ min (Θ) and σ max (Θ). Besides, [4,37] demonstrate that the neural net output at initialization, f θ0 (·), is a zero-mean Gaussian with small-scale covaraince. Combining these results and (82), we know there exists R(R 1 , N, σ min (Θ), σ max (Θ)) such that By taking an supremum over R(R 1 , N, σ min , σ max ) for each training task in and for R 0 = √ N R 2 , define δ 0 as some appropriate scaling of δ 1 , then the following holds true with probability (1 − δ 0 ) over random initialization,
Hence, for any i, j ∈ [N ], as the width l approaches infinity, [Φ 0 ] ij converges in probability to a deterministic matrix lim l→∞ [Φ 0 ] ij , as shown by (91). Thus, the whole block matrixΦ 0 converges in probability to a deterministic matrix in the infinite width limit. Denote Φ = lim l→∞Φ0 , then we know Φ is a deterministic matrix with each block expressed as (91).
, it is a symmetric square matrix. Hence all eigenvalues ofΦ 0 are greater or equal to 0, which also holds true for Φ. In addition, because of Assumption 4, Φ is positive definite, indicating σ min (Φ) > 0. On the other hand, from [4], we know diagonal entries and eigenvalues of Θ(·, ) are positive real numbers upper bounded by O(L), as a direct result, it is easy to verify that the diagonal entries of the matrix Φ are also upper bounded, indicating σ max (Φ) < ∞. Hence, we have 0 < σ min (Φ) < σ max (Φ) < ∞.
Extension. It is easy to extend (91), the expression for Φ ≡ lim l→∞Φ0 ((X , X , Y ), (X , X , Y ), to more general cases. Specifically, we can express Φ(·, ) analytically for arbitrary inputs. To achieve this, let us define a kernel function, Then, it is obvious that for i, j ∈ [N ], the (i, j)-th block of Φ can be expressed as [Φ] ij = φ((X i , X i ), (X j , X j )).

B.5. Proof of Theorem 3
Proof of Theorem 3. Based on these lemmas presented above, we can prove Theorem 3.
Lemma 2 indicates that there exist R 0 and l * such that for any width l ≥ l * , the following holds true over random initialization with probability at least (1 − δ 0 /10), Consider C = 3KR0 σ in Lemma 1.
First, we start with proving (29) and (32) by induction. Select l > l * such that (93) and (25) hold with probability at least which finishes the proof (32). Finally, we prove (30) by where we used (29) and Lemma 1.

C. Analytical Expression of MAML Output
In this section, we will present Corollary 3.1. Briefly speaking, with the help of Theorem 3, we first show the training dynamics of MAML with over-parameterized DNNs can be described by a differential equation, which is analytically solvable. By solving this differential equation, we obtain the expression for MAML output on any training or test task.
Remarks. This corollary implies for a sufficiently over-parameterized neural network, the training of MAML is determined by the parameter initialization, θ 0 . Given access to θ 0 , we can compute the functionsΦ 0 and F 0 , and then the trained MAML output can be obtained by simple calculations, without the need for running gradient descent on θ 0 . This nice property enables us to perform a deeper analysis on MAML with DNNs.
Proof. For the optimization of MAML, the gradient descent on θ t with learning rate η can be expressed as Since the learning rate η is sufficiently small, the discrete-time gradient descent above can be re-written in the form of continuous-time gradient descent (i.e., gradient flow), Then, the training dynamics of the meta-output F t (·) ≡ F θt (·) can be described by the following differential equation, whereΦ t =Φ t ((X , X , Y ), (X , X , Y )) = ∇ θt F t (X , X , Y )∇ θt F t (X , X , Y ) . On the other hand, Theorem 3 gives the following bound in (30), indicatingΦ t stays almost constant during training for sufficiently over-parameterized neural networks (i.e., large enough width l). Therefore, similar to [37], we can replaceΦ t byΦ 0 in (98), and get which is an ordinary differential equation (ODE) for the meta-output F t (X , X , Y ) w.r.t. the training time t. This ODE is analytically solvable with a unique solution. Solving it, we obtain the meta-output on training tasks at any training time t as, The solution can be easily extended to any test task T = (X, Y, X , Y ), and the meta-output on the test task at any training time is whereΦ 0 (·) ≡Φ θ0 (·, (X , X , Y )) and T η Φ0 (t) =Φ −1 0 I − e −ηΦ0t are shorthand notations.

D. Gradient-Based Meta-Learning as Kernel Regression
In this section, we first make an assumption on the scale of parameter initialization, then we restate Theorem 2. After that, we provide the proof for Theorem 2.
[37] shows the output of a neural network randomly initialized following (16) is a zero-mean Gaussian with covariance determined by σ w and σ b , the variances corresponding to the initialization of weights and biases. Hence, small values of σ w and σ b can make the outputs of randomly initialized neural networks approximately zero. We adopt the following assumption from [4] to simplify the expression of the kernel regression in Theorem 2.
Assumption 5 (Small Scale of Parameter Initialization). The scale of parameter initialization is sufficiently small, i.e., σ w , σ b in (16) are small enough, so that f 0 (·) 0.
Note the goal of this assumption is to make the output of the randomly initialized neural network negligible. The assumption is quite common and mild, since, in general, the outputs of randomly initialized neural networks are of small scare compared with the outputs of trained networks [37].
where K is the neural tangent kernel function corresponds to neural networks with frozen hidden layers (i.e., only the last linear layer is optimized by gradient descent). The appearance of K directly results from the special inner-loop update rule of ANIL (i.e., only updates the last linear layer in the inner loop).

E. More Details on Experiments
Training Data Augmentation Following previous few-shot learning works [38,60], in the training stage, we adopt data augmentation operations, including random cropping, color jittering, and random horizontal flip.
Training Batch Size For all 5-cells experiments, a batch size of 64 is used. For 8-cells experiments, we set the batch size to 40 for miniImageNet and 56 for tieredImageNet to accommodate the GPU memory of a single GPU card.