Unraveling Model-Agnostic Meta-Learning via The Adaptation Learning Rate
Authors: Yingtian Zou
Fusheng Liu
Qianxiao Li
Venue: ICLR 2022 Poster (2022)
Keywords: Meta-Learning
Learning rate
Optimization

Abstract: Model-Agnostic Meta-Learning (MAML) aims to find initial weights that allow fast adaptation to new tasks. The adaptation (inner loop) learning rate in MAML plays a central role in enabling such fast adaptation. However, how to choose this value in practice and how this choice affects the adaptation error remains less explored. In this paper, we study the effect of the adaptation learning rate in meta-learning with mixed linear regression. First, we present a principled way to estimate optimal adaptation learning rates that minimize the population risk of MAML. Second, we interpret the underlying dependence between the optimal adaptation learning rate and the input data. Finally, we prove that compared with empirical risk minimization (ERM), MAML produces an initialization with a smaller average distance to the task optima, consistent with previous practical findings. These results are corroborated with numerical experiments.

Published as a conference paper at ICLR 2022
UNRAVELING MODEL-AAGNOTIC META-LEARNING VIA THE ADAPTATION LEARNING RATE
Yingtian Zou, Fusheng Liu, Qianxiao Li National University of Singapore, Singapore (yingtian, fusheng) @u nus edu, qianxiaoθnus edu.
ABSTRACT
Model-Agnostic Meta-Learning (MAML) aims to find initial weights that allow fast adaptation to new tasks. The adaptation (inner loop) learning rate in MAML plays a central role in enabling such fast adaptation. However, how to choose this value in practice and how this choice affects the adaptation error remains less explored. In this paper, we study the effect of the adaptation learning rate in meta-lcarning with mixed linear regression. First, we present a principled way to estimate optimal adaptation learning rates that minimize the population risk of MAML. Second, we interpret the underlying dependence between the optimal adaptation learning rate and the input data. Finally, we prove that compared with empirical risk minimization (ERM), MAML produces an initialization with a smaller average distance to the task optima, consistent with previous practical findings. These results are corroborated with numerical experiments.
INTRODUCTION
Meta-learning or learning to learn provides a paradigm where a machine learning model aims to find general solution that be quickly adapted learning has been widely applied to challenging tasks such as few-shot learning (Vinyals et al., 2016; Snell al., 2017; Rusu al., 2018), continual learning (Finn al., 2019; Javed & White, 2019), and neural architecture search (Zhang et al., 2019; Lian et al., 2019). One promising approach in meta-learning is Model-Agnostic Meta-Learning (MAML) (Finn et al., 2017), which consists of two loops of optimization. In the outer loop, MAML aims to Iearn a good meta- neeta-niitilliztiinn that can be quickly adapted new task in the inner loop with limited adaptation (parameter optimization) steps. The double loops optimization serve as "learning- model adapt new tasks faster than direct Empirical Risk Minimization (ERM) algorithms (Finn et al., 2017; Raghu et al., 2020). Recent works (Nichol et al., 2018; Fallah et al., 2020; Collins et al., 2020; Raghu et al., 2020) attribute the fast adaptability to the phenomenon that the learned meta- mnta-initialization lies in the vicinity of all task solutions. However, the theoretical justification of this empirical statement, and more generally how fast adaptability of MAML depends on the inner loop optimization remains unclear. As key component of MAMI., the adaptation (inner loop) learning rate (hereafter called () is shown empirically to plays a crucial role in determining the performance of the learned meta-initialization (Rajeswaran ERM and MAML, in the sense that the latter reduces to the former when a = O. However, from theoretical viewpoint, the dependence of MAML performance on the choice of remains unclear, and furthermore, there lacks precise practical guideline on how to pick a near- optimol value.
tasks. Due to its fast adaptability, meta-
coanmiingtt--dddae to-adapt" process, thus enabling the trained
al., 2019). In particular, the value of bridges
In this paper, we address these issues by answering the following two questions: (1) How to choose the optimal that minimizes population risk of MAML? (2)What is the effect of a fast adaptability of MAML? To this end, we consider the mixed linear regression problem with random feature models. For the first question, we derive the optimal a which minimizes the population risk of MAML in the limit of an infinite number of tasks. This can then be used to estimate an effective a prior to training. Moreover, we analyze the underlying statistical dependency between the optimal a and the input data, e.g. relation to the moments of data distribution. This in turn allows the heuristic application of results beyond linear models, and demonstrate this with experiments. To answer the second question, we compare MAML with an ERM algorithm (without inner loop optimization) in order to reflect the effect of a in optimization. As stated in many works, like Nichol et al. (2018), that

---

Published as a conference paper at ICLR 2022
meta-initializatiinn learned by MAML in parameter space is close to all training tasks thus contributes to fast adaptability. We conduct an experiment and observe that MAML with not too large a yields shorter mean distance to task optima than ERM. To justify this empirical finding, we define metric measuring the expected geometric distance between the learned meta-inittalization and task optima. We prove that in our setting, the MAMI. solution indeed possess smaller value of this metric compared with that of ERM for small a, providing theoretical evidence for the observed phenomena. Our contributions can be summarized follows:
We provide principled way to select the optimal adaptation learning rate a' for MAML which minimizes population risk (Theorem & Proposition 1). We also interpret the underlying statistical dependence of a to input data (Corollary 1) with two examples.
We validate the observation that MAML learns a good veta-initiallzzation in the vicinity of the task optima, which reveals the connection between the adaptation learning rate a and the fast adaptability optimization. (Theorem 2)
We also extend our result about the choice of a² to more practical regime, including deep learning. All of our theoretical results are well corroborated with experimental results.
PROBLEM FORMULATION
We study the MAML algorithm under the mixed linear regression setting. Suppose we have task T that is sampled from the distribution D(T). Each task T corresponds to a linear relationship
æT,1
yr = 1b (B(XT)ar Xxr
Xr E Rxxd, ((Xx) E Rxdd ar E Rdd.
TT,K
(2.1)
where Xx Kxd= is the input data of task T which has K vector samples { (.. FT,K) TTs Rd= i.i.d sampled from D(x) !. For each input data, have a mapping & : RRd Rdd transform each point of XT from input data space Rd to a d-dimensional feature space 12d where we denote the transformation of all data in task T' by ((X))
[ő(XT,1), ..., ((XT, as the feature of that task. Then, we assume optimal solution ar IR for task T is i.i sampled from D(a). The corresponding label E R can be obtained from (2.1).
Our target is to learn a model minimize the risk of different tasks across D(T). Note that each task T' is determined by a feature-solution pair (2(X)), ar). Therefore, we can formulate this multi-task problem with parameter space Rd and loss function as
min ETwD(T) [L (w; T)] Rdd
min weRs
[e (w; (X)). a)]
(2.2)
To solve this problem, ERM and MAML algorithms yield different iterations. Specifically, ERM uses all data from all tasks to directly minimize the square error loss f, such that population risk of ERM is
(w, K) == a~ ( K
E
((X - 4()a
(2.3)
As counterpart, MAMI. first adapts with adaptation learning rate each task using its training set a subset of task data the inner loop. Then, in the outer loop, MAML minimizes the evaluation loss for each adapted task-specific solution using validation set. For simplicity, since data is i.i.d sampled from the same distribution, we first consider the setting where all data in each task is used as training set and validation set in our main results. We present later the extension of these results to the case with a different train validation split. (Please refer to Appendix H.
Thus, the general population risk of one-step MAML is defined by
Cm(w, a, K) = D X~D(a) K
1
w a (w: ((X) ((X))))
(2.4)
Inner Loop
For simplicity, we denote this sampling and stacking multiple examples matrix process as X D(x)
2

---

Published as a conference paper at ICLR 2022
In practice, use the empirical objective function surrogate objective function. We first sample N tasks with task optima (a1, a.y from ( and then sample data for each task. Then, the empirical risk of MAML can be specified as L.
Lm Sw, a, = NK Σ
((X))a
(2.5)
where w = w (X;) (x( (x)) (KKK)aa)KK](()) adapted parameters of task after inner loop. Correspondingly, we apply ERM algorithm to the same problem by removing inner loop (setting a = 0). thus the empirical risk of ERM is denoted as (w, N. K). In addition, we follow the original MAMI. (Finn et al., 2017) to use the same a for training and testing.
Notation We denote optimal adaptation learning rate a², Global minima of empirical risk of MAML and ERM (when they are unique) are denoted by wm. W,. We write {1.... N as [N] and use ||-Il denote the Euclidean norm. We use subscripts to index the matrices/vectors corresponding to task instances, and bracketed subscripts to index the entries of matrices. Other notations are summarized in Appendix Table 1.
Assumption (Normalization). For simplicity, we consider centered parameter space such that Eg-D(a) [a] = 0 and Var(a] = =
Assumption 2 (Bounded features). With probability 1, the covariance matrix of input features (X) (X) is positive definite and has uniformly bounded eigenvalues from above by Xs >> O and below by X1 >
MAIN RESULTS
In this section, we analyze MAML through the adaptation learning rate a. Our derived insights are summarized into three theoretical results: (1) The estimation of an optimal adaptation learning rate a* which minimizes MAML population risk; (2) The statistical meaning of a* terms of the data distribution, and (3) The geometric interpretation of the effect of a fast adaptability of MAML compared to ERM.
3.1 ON THE OPTIMAL ADAPTATION LEARNING RATE ax
We focus on the underparameterizzed case (K d). Given the empirical objective functions P,, L. defined in (2.5), we can derive the global minima by the first-order optimality condition. We obtain the global minimum of ERM w. and minimum of MAML wm in the following closed-forms,
w, = w, (1)())), a:hee())) =
Σ SE[N]
((,) (xx))
Σ
((X,)T((X,))
jEIM
(3.1)
(m) = Wm wm ({C:(a). a()
Σ Ca(a) iE[M]
Σ JE[M]
C,(a) (((a)),(()aa))
where ((x,))+(X)][( ((x])===)((((a 9 (TxT,(XXXxxx))))) C,((a) Rxdd can be viewed as the adapted feature of task Observe that wm (a) (and thus the MAML algorithm) depends on a. MAML reduces to ERM. For large a, instabilities may occur, thus there may exist an optimum, a that minimizes the MAML population risk. The later intuition worthwhile to be proved, from which we do not have principled way to guide the choice of optimal hyperparameter a' for MAML so far. To this end, we focus on the generalization error by taking the population risk on the global minimum of empirical risk. In particular, the average sense, where the average population risk is
consider the population risk of the MAML optimizer in
(3.2) whose minimizer denote (N, K). In this way, eliminate randomness of the global minimum w., learned from sampled tasks. The following theorem gives precise value o (N, K) in the limit N
E. (a, N. K) EE L. (Wm, a, K)
3

---

Published as a conference paper at ICLR 2022
Theorem 1. Under assumptions 1 & we have as N 0o, a (N, + afsm(()) where
K tr|EEx 21r ( (X) ([
(()))
amam (K)
(3.3)
(X) E Rxd Ç K the sample size per task and N the number of tasks.
The proof is found in Appendix B. In this theorem, give the nearly optimum o which is an alternative form for true optimal a, namely a', to minimize the MAML generalization error. As dictated in (3.3), the desired o² is determined by the feature covariance matrix in expectation.
Remark. The precise derivation of the case where N is finite is complicated, thus we derive the limiting case here as an estimator of true a*. Our estimation a the unique minimum. We will show later that this allows to compute near optimal values efficiently in praclice, each of which is close to the optimal o² (N, K) in corresponding problem.
Remark. The estimator (3.3) can be generalized to different scenarios. For overparameterized models, we obtain a similar result for the minimum norm solution if the number of tasks N is limited (NK & d). Further, we show a computationally efficient estimator (H.15) in Appendix H.2. For deep learning, we can compute range of effective values based on Oiinn We also give the numerical form when the training data different from the test data each task. These are presented in Appendix H.4 and H.l respectively.
In the above we considered the average population risk (3.2). This simplifies the calculations of finding the a'. Below, we justify this simplification by showing that in the limit of large number of tasks, the average population risk is a good estimate of the true population risk.
Proposition (Informal). Assume u = CCaa))T((aa)) C(a)a is sub- -ab-gaussian random variable with sub- gaussian norm |,m]| L, assumption & 2 hold, then with probability at least 1 8 that
L S
(
de de K) N2
2 E(a,K) N
2 log
Lm mm(W (wm; at, K) Lm N, N,
max K
log
(3.4)
8
where e(a, K) - O(1/cco + a)²). Here co O a constant and d is the feature size.
The proof is found in Appendix C. Proposition complements Theorem by guaranteeing that the gap between the average population risk and population risk with same argument a will disappear along with N goes infinity. Large makes the bound tighter while small makes E(a, K) converge to a positive constant; thus (3.4) provides a non-vacuous bound with regard to a. Hence, is justified to make an estimation of a using the average case. By Theorem 1 and Proposition 1, give an explicit form to estimate a for MAMI. where this estimation Qiim is not too far from the true a' of specific case. Later experiments show our estimation ossm is close true a" in both underparameterized and overparameterized models (see Section 5. This is meaningful for selecting an a" minimizing MAML risk, instead of randomly choosing it. Previous work (Bernacchia, 2021) explores on this by giving range of a" may exist for the linear model. Instead, we show fine result that we provide a certain value estimator of a". (Details refer Appendix H.5)
Relation to data distribution. After estimating the value of a through Theorem interested in the statistical interpretation of a*. In particular, we aim to summarize the dependence of estimation of a' on the distribution of the inputs and tasks. This in turn allows to devise strategies for choosing near optimal a for MAML beyond the simple settings considered here.
now
Corollary 1. With a feature mapping Rdd= -> Rdd for each data & E Rdd,, the aiem in Theorem will sarisfy the following inequality
d
2do (dlo) ((x))) S ajin S 20" o (xx))
(3.5)
where o² (2(((z)),... (x k)) is variance of the feature.
See proof in Appendix D. According to Corollary 1, we see that a is bounded by the statistics of the input data. These bounds are governed by the standard derivation terms. More specifically, our estimator (3.3) holds an inverse relationship higher order moment of data distribution while its
4

---

Published as a conference paper at ICLR 2022
5.5-
Mean distance
5.0-
4.5-
Wi2)
4.0-
3.5-
3.0-
2.5
0.000
0.001
0.002
0.003
0,004
W(3)
(a) Visualization of solutions and trajectory
(b) Mcan solution distances
Figure I: (a) Visualization of trajectory of MAML solution (a). Orange dots task optima {a, |Nj] of sampled tasks, where location a, is decided by its entries. Red dots highlighted in red circle are newly coming tasks. Green cross is wr, (a = 0) while the purple trajectory is generated as increasing. Red star Wmm wm (afim)) (b) Average euclidean distances of Wm (a) and {a: Jiv] display corresponding points left figure. Black arrow is the tangent line. Best viewed in colors.
bounds (3.5) have an inverse relationship data variance. As consequence, the dim for different problems mainly depend on the standard derivations. For example, ofim and thus a* will shrink to zero as the variance of data increases and vice versa. In other words, small a is tailored to those tasks with large data variance when the model size is fixed. To illustrate the insight more clearly, we present two examples regression with polynomial basis functions (Example 1) and the case where (X) is random matrix with prescribed distribution (see Appendix E). In this following example, we narrow the range and get the exact relationship where the expression of a rather than its bounds depend on data variance and model size d. In later experiments, also validate this relationship on various models with different basis functions.
Example (Polynomial basis function). Assume we have K i.i.d samples Ti, JK NNO o²) for each task. Consider polynomial basis function & R + Rd, where ó(z) = (1,..,, xd-1). value of fiim has an inverse relationship to o² and dimension d (Proof is in Appendix E).
Then
3.2 GEOMETRIC INTERPRETATION OF MAML ADAPTATION
In another direction, we aim to investigate geometric properties of the meta-initialization learned by MAML as a varies. In previous experimental investigations, it is suggested that MAML learns the near meta-initialization to all tasks Nichol al. (2018) trade-offs easy and hard tasks Fallah et al. (2020). We can also observe the new phenomena in toy experiments. As shown in the Figure 1 (a), we sampled 500 tasks in R² parameter space. Specifically,
i.idd sample and stack data as X; E K D(x) and task optima a, ~ D(a), a E IR2 (scattered orange dots) for each task i. Green
shows the location of MAML solution w. (a:) with a 0, namely ERM solution w,- Since D(x), D(a) are some symmetric zero-mean distributions, the optimal solution is expected at the origin. When several new training tasks (with higher penalties) have been added as shown in the red circle area, then new w, will be closer to new tasks. Along a increasing, w., (a) generates trajectory shown as the purple curve. The dynamies of global minimum w,,(ox will start from green cross and move away from the red circle until reach an optimum location of point (red star wn (aism) )) which minimizes the total distances to red and orange dots (Other cases shown Appendix H.4).
It indicates that the effect of (inner loop optimization) is to help MAML minimize total distances to all training task optima. Unlike ERM learning biased solution dense tasks area, MAMI. converges to distance-aware solution that tries to minimize the distances within one-step adaptation at stepsize a. The afm is the optimum adaptation stepsize to learn the optimum location point, or nearest point, to all tasks. Figure I (b) displays the mean distance for each point in purple trajectory to all tasks. As we can see, the distance decreases at beginning as a increases until reach the minimum.
To theoretically prove the insight in Figure 1, characterize it by measuring the average post- adaptation distance between the mnta-initialization (global minimum) learned by a specific algorithm and task optima in task distribution.
5

---

Published as a conference paper at ICLR 2022
Definition (Average Distance under Fast Adaptation). Given task distribution D(T), meta- inirialization w'x learned by algorithm A, optimum ar of task T, the average distance under t-step (t 2 0) fast adaptation is defined by
F((w2) ==
E T~D(T)
I aTI?, W'AT - w - Vvel(w'
(3.6)
j=1
where w'x A.T is the adapted parameter of task T with t steps, nj is the step size, is the loss function.
Fr evaluates the distance between adapted parameters and true task optimum for given meta- initialization at any adaptation step t. If t is small, Fr describes the fast adaptation error in solution distance of the meta-initialization learned by an algorithm. Hence, we can measure the fast adaptability of MAML with F.Wwm). Observe that for small a, Wm can be linearized as
Wm (a) = w, - aV w.m (0) + O(a2)
(3.7)
In this regime, the effect of MAML dictated by the a gradient V. (. which can be visualized as the tangent of the purple curve at the green cross in Figure 1(b). By comparing Fr of the meta- initializations wr, Wm, learned by ERM and MAML, we are able to find the connection between and the fast adaptability in meta- meta-learning, at least in the small alpha regime. For simplicity, we assume that the input data features are uncorrelated, thus the covariance matrix is diagonal.
Theorem 2. Let Wma (a), wy be the meta- meta-initialinn initializaatinns learned from Ti,..., Tv by MAML and ERM.
With Fi(.), under Assumption I & for any a E 0, K 112 +1 D2 - X//22 of step we have
at number
A7(4X) x7)
27 K
2
4ad
Er, T D(T) [F((w,) (F FF((
As
(3.8)
NK
where ni is the step size in Definition 1, č >>> 0 is constant.
See proof in Appendix G. This theorem prove insight at small that MAML has smaller average solution distance than ERM. As it illustrated in Theorem 2, at any step t 2 0, Fe (a)) < F((,,)) holds if a is smaller than some constant. This means adapting to different tasks with MAML meta- initialization leads to shorter average solution distance than ERM's at any number of adaptation steps. But the gap will disappear along number of steps t increasing to infinity, which is sensible. Note that even / = 0, this inequality still holds true. Therefore the veta-initializztion of MAML wm. has shorter expected distance to new task than ERM w, before adaptation. Theorem 2 has revealed the connection between a and fast adaptability. Even with small a, MAML learns more adaptive solution than ERM which is closer to the new tasks in expectation enabling quick approximation. It benefits from learning closer meta-initialle innta-iniiiaaizationn for all tasks average. Thus plays role in learning a distance-aware solution. This result is consistent with our observation in the Figure 1.
Compared to ERM algorithms, the fast adaptability of MAML stems from the leamed meta- initialization determined by the adaptation learning rate a. When facing a multi-task problem, traditional ERM algorithms bias its learned initialization minimize the averaged risk. However, this strategy fails to take the further adaptation into account, and thus learns a solution far from unknown task optima. On the contrary. MAML learns distant-aware meta-initializztion and converges the vicinity of all task optima with limited adaptation budget (Nichol et al.. 2018: Rajeswaran et al., 2019), or tends to favor "hard tasks" (Fallah et al., 2020; Collins al., 2020). Hence, before adap- tation, ERM may have lower population risk than MAML. However, after adaptation, the situation will reverse since MAML can adapt to most unknown task optima closer (see Figure 5())). This benefit is also illustrated by (Zhou et al., 2020) that the shorter solution distance leads to better meta-initializztion for fast adaptation. We note that "task hardness" may not always be easy to define, especially for non-linear cases (Collins et al., 2020). Here, we instead focus directly analyzing the geometric distance (Theorem 2), which has substantiated the aforementioned findings in optimization behavior from different angles.
4 RELATED WORK
Meta learning learns a general solution based on previous experience which can be quickly adapted to unknown tasks (Finn et al., 2017; Li et al., 2017; Snell et al., 2017; Vinyals al., 2016; Nichol

---

Published as a conference paper at ICLR 2022
35
60-
K-23,
K- 15,N-50
25
K=7,N=112
50
K- N5
15
30
10
20
(xx10-)
(x10-1
(a) NTK (Uniform initialization)
(b) NTK (Normal initialization)
Figure 2: Loss of overparameterized quadratic regression with regard to a. Triangles in the dash-dot line is the mean loss across whole tasks. The error bar denotes 95% confidence interval on different tasks. Red stars are estimations a'on
al.. 2018: Grant et al., 2018; Harrison et al., 2018; Rusu et al., 2018; Rajeswaran et al., 2019; Finn & Levine, 2018; Rajeswaran et al., 2019; Finn et al., 2018; Yin et al., 2020). One promising approach meta-learning is Model-Agnostic Meta-Leariing (MAML) (Finn et al., 2017) which learns a meta iettainnitilizzaiinn such that the model can adapt to new task via only few steps gradient descent. Understanding the fast adaptability of meta-learning algorithm, especially on MAML, is now important question. As a variant of MAML,, (Nichol et al., 201 8) attribute fast adaptation to the shorter solution distance, and devises a first-order approximation algorithm based on this intuition. Other first-order methods (Denevi al., 2019; Zhou et al., 2019) try achieve adaptation by adding a regularized term to get a distance- aware solution. (Raghu et al., 2020) shows that even performing inner loop optimization on part of the parameters still leads to fast adaptation. A shared empirical finding of these results is that MAML produces initial weights that are closer to the population optimum of individual tasks average, and it is argued that this partly contributes its fast adaptibility. Here, we present a rigorous result that confirms the distance reduction property of MAML, at least in the considered setting, lending theoretical backing these empirical observations.
On the theoretical front, analyses of meta-learning mainly focus on generalization error bounds and convergence rates (Amit & Meir, 2018: Denevi al., 2019; Finn et al., 2019; Balcan et al., 2019; Khodak et al., 2019; Zhou et al., 2019; Fallah et al., 2020; Ji et al., 2020b; Zhou et al., 2020; Ji et al., 2020a). For example, Fallah et (2020) studies MAML by recasting as SGD on modified loss function and bound the convergence rate using the batch size and smoothness of the loss function. et al. (2020b) extend this result to the multi-step version of MAML. Other works (Charles & Konečný, 2020; Wang et al., 2021; Gao & Sener, 2020; Collins et al., 2020) investigate the MAML optimization landscape and the trade-off phenomena in terms of task difficulty: e.g. MAML tend to find meta- cetta-nniiaalizations that are closer difficult tasks. However, the effect of inner loop learning rate a on the MAML dynamics and learned solution are not explored in these works.
Of particular relevance is the work of Bernacchia (2021), which derives, under ideal setting of Gaussian inputs and regression coefficients, a range of a values that can help guide its choice. In this paper, adopt more general setting, where we do not assume specific input distributions. We derive a precise optimal value of a (instead of a range), which can be estimated from input data. Furthermore, show using experiments that the optimal values may not be negative (c.f. Bernacchia (2021)) in the standard meta-learning setting, where the same a is used for training and testing.
EXPERIMENTS
5.1 ESTIMATION OF a"
We verify our theorem through Neural Tangent Kernel (NTK) (Jacot al., 2018) and deep learning on the Omniglot dataset (Lake et al., 2011). ). In the former setting, we followed the problem setup in (Bernacchia, 2021) to perform quadratic regression. Different from their model size of 60, used a two-layer Neural Tangent Kernel (NTK) (Jacot et al., 2018) with sufficiently wide hidden layers (size 10, 000). Then, estimate a by the neural tangent feature obtain oe = 1/(2NN55)
7

---

Published as a conference paper at ICLR 2022
Default
25
Ours
2.0
1.5
Default
0.2
Ours
(a) Omniglot 20w Is Test Loss
(b) Omniglot 20w Test Accuracy
Figure 3: Test loss and accuracy Omniglot 20-way 1-shot classification. The blue and orange line represent the test loss (left) and test accuracy (right) of original configuration in ANIL (Raghu al., 2020) paper and our online estimation. The shadows are the standard deviation of multiple experiments with different seeds.
0.375
N(O, a)
N(O, a)
0.350
0.00020
U1-112a/2, v12
Ul v12a(2)
0.325
Exp(1/o)
0.00019
0.250
0,00005
0.225
6.200
o of ((x)
0 of D(x)
(a) Gaussian Basis function
(b) NTK with Uniform Initialization
Figure 4: Value of af along the data variance, o². Different curves are different data distributions. (a)The feature of Gaussian basis function. These curves can be perfectly fitted by an inverse proportional function. (b) The feature of uniformly initialized NTK model.
(ō is the variance of NTK feature, whose derivation is found in Appendix H.2). Shown vertical dotted line ending with the red star in Figure 2, we can see our estimation is nearly optimal. To reduce fortuity, choose arbitrary values of N, K to compute the estimation ojam- Furthermore, also test our estimation on uniform initialization with other groups of hyper- parameters and obtained similar results. Then, for deep learning classification, we use online estimation to compute a" for ANIL Raghu et al. (2020) on the Omniglot dataset Lake et al. (2011). ). To keep training stable, we normalize the features before the last layer and compute the corresponding a Then, we compare our estimation scheme with the default selection method where the model and training learning rates are the same. Test loss accuracy are reported with mean and variance Figure 3. Both training schemes achieve similar results after x 10 iterations. We only plot the first 1.5 x 10 iters (20 iters per scale) to see the differences clearly. As shown, our estimation a converges faster than that in the default configuration. Other experimental parameters and additional results, including non-central distributions and deep regression experiments, are found in Appendix H.4. Overall, these experiments suggest that our estimation derived in the idealized linear setting guide practical hyper-parameter selection.
5.2 RELATION OF DATA VARIANCE AND OPTIMAL &
In this section, we verified our theoretical results agom and its relation to data variance. As drawn the Figure 4, value of an and data variance have inverse relationship. We first verified
8

---

Published as a conference paper at ICLR 2022
-0.0005
0.0010
-2
0.0015
0.0020
U(-S, 5)
-3
U(-5. 5)
N(0, 2)
N(0, 2]
0.0025
Exp(1)
Exp(1)
0.0030
10
20
30
40
50
0
10
20
30
40
50
(a) Adaptation Loss Gap
(b) Fast Adaptation Distance Gap
Figure 5: With different data distributions, Z; ~ U(-5. 5). 2), Exp(1) (curves in different colors) (a) the loss difference between MAML and ERM with t steps adaptation on each task E, E. (2mm) (ww)) ( E (Wm) is the t-step adaptation loss on task from the MAML learned initialization w.n) and (b) Average solution distance gap of MAML and ERM after t-step adaptation, F((m)) F((,))
this with Gaussian basis function (())(s) exp( (X(s) 125)² /20 Then, we conducted experiments on three different data distributions: normal distribution NO0, uniform distribution U(-vT2o /2, / 12o// /2) and exponential distribution Exp(1/o). From in (a), we can see the smooth curves perfectly fitted with some inverse proportional function e.g. y 0.35/o². Next, used NTK as the basis function to verify our result in overparameterized regime. We used two layers MLP with width= 10, 240 and uniform initialization to compute the neural tangent feature. As we can see from Figure 4(b), the diagram also shows the tendency that aiim decreases as a increasing, As consequence, variance, as a part of the statistical property of data, will influence a*.
5.3 FAST ADAPTATION
To understand the effect of on Fe, set 10
+ to train MAML such that its global minimum wm is inched from ERM w,- Then, we tracked their adaptation losses and adaptation errors with growing adaptation steps, shown in the Figure 5. Adaptation loss for task is defined by (ww) = [[x((,)))_______) Ad)pt( i, t, y:1l where Adapt(w, i, 1)) is t-step adaptation parameter with learning rate 1) le 5. The adaptation loss difference between MAML and ERM is described as 2.000 (wm) (w,). From Figure 5 (a) we can see, the loss of MAML marginally higher than ERM before adapting. But the difference dramatically decreases to negative values, which illustrates that MAMI. has better performance than ERM with only few steps adaptation. Similar results appear on various data distributions: uniform distribution l/( (4(55, 5), normal distribution (0, 2) and exponential distribution Erp(1). makes sense because wp, Wm are the minimizers of non-adaptation loss and one-step adaptation loss, respectively. Then adaptation errors in distance Fi( (m)) ) - F(,,)) along adaptation step t. In Figure 5(b) we can see, Fi of MAML is always smaller than ERM's, including
plot the difference of
Since F, measures distances of adapted solution and task optimum solution, this result has substantiated our Theorem 2. Furthermore, also demonstrate that the effect of a, even is small, is acting the guide to find distance-aware meta-initialization for target tasks which possesses faster adaptability compared to ERM.
6 CONCLUSION
In this paper, we investigated MAMI through the lens of adaptation learning rate a. We gave a prineipled way to estimate an optimal adaptation learning rate a' minimizing MAML population risk. We also try to interpret the role of statistically and geometrically. Further investigation has revealed the underlying data statistics that a depends on. This statistical dependency also motivates us to explore other effect of a, such as the optimization behavior in a geometric context. By studying role of on optimization, we confirmed theoretically that MAMI obtains solutions with shorter average distance to individual task optima than ERM an empirical observation that was suggested to contributes to MAML's 's fast adaptability. We believe these results are instructive in contributing to the theoretical understanding of meta- leaa-nn and its algorithm design.

---

Published as a conference paper at ICLR 2022
7 ACKNOWLEDGEMENT
This research/project is supported by the National Research Foundation, Singapore under its Al Singapore Programme (AISG Award No: AISG-GGC-201-001-222 conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore. Q. Li is supported by the National Research Foundation, Singapore, under the NRF fellowship NNRF-NRFF13--22--0000))
Any opinions, findings and
REFERENCES
Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended pac-bayes theory. In ICML, 2018
Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for wradient-based meta-learning. In International Conference on Machine Learning, pp. 423.433. PMLR, 2019.
Alberto Bernacchia. Meta-learning with negative learning rates. In International Conference on Learning Representations, 2021.
Andrea Braides. A handbook of gonnaa-cnvvergenee. In Handbook of Differential Equations: stationary partial differential equations, volume 3, pp. 101-213. Elsevier, 2006.
Zachary Charles and Jakub Konečný. On the outsized importance of learning rates in local update methods. arXiv preprint 2000000007.00878, 2020.
Liam Collins, Aryan Mokhtari, and Sanjay Shakkottai. Why does maml outperform erm? an optimization perspective. arXiv preprint arXiv:2010. 14672, 2020.
Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to to-le stochas- tic gradient descent with biased regularization. In International Conference on Machine Learning, pp. 1566-1575. PMLR, 2019.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. On the convergence theory of gradient- based modeel-agnostic learnne algorithms. In International Conference Artificial Intelligence and Statistics, pp. 1082-1092. PMLR, 2020.
Chelsea Finn and Sergey Levine. Meta-learning and universality: Deep representations and gradi- ent descent approximate any learning algorithm. In International Conference Learning Representations, 2018
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proceedings of the 34th International Conference Machine Learning- -oouuee 70, pp. 126-1135. JMLR. org, 2017.
Chelsea Finn, Kelvin Xu, and Sergey Levine. Probabilistic model-agnostic meta-learning. In Advances in Neural Information Processing Systems, pp. 9516-9527, 2018.
Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-learning In International Conference on Machine Learning, pp. 1920-1930, PMLR, 2019.
Katelyn Gao and Ozan Sener. Modeling and optimization trade-off in meta-learning. Advances in Neural Information Processing Systems, 33, 2020.
Erin Grant, Chelsea Finn, Sergey Levine, Trevor Darrell, and Thomas Griffiths. Recasting gradient- based meta-learning as hierarchical bayes. arXiv preprint arXiv: 1801. 1801008930, 2018.
James Harrison, Apoorva Sharma, and Marco Pavone. Meta-learning priors for efficient online
bayesian regression. arXiv preprini
2018.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and
generalization in neural networks. In Advances Neural Information Processing Systems, 2018.
Khurram Javed and Martha White. Meta-learning representations for continual learning. arXiv
preprint arXiv: 1905. /2588 2019.
10

---

Published as a conference paper at ICLR 2022
Kaiyi Ji, Jason D Lee. Yingbin Liang, and H Vincent Poor. Convergence of meta-learning with task-specific adaptation over partial parameters. In Advances in Neural Information Processing Systems, 2020a.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Multi-step andeliagi meta-learning: Convergence and improved algorithms. arXiv preprint arXiv:2002.07836, 2020b.
Mikhail Khodak, Maria-Florina F Balcan, and Ameet S Talwalkar. Adaptive gradient- meta- learning methods. In Advances in Neural Information Processing Systems, pp. 5915-5926, 2019.
Brenden Lake, Ruslan Salakhutdinov, Jason Gross, and Joshua Tenenbaum. One shot learning of simple visual concepts. In Proceedings of the annual meeting of the cognitive science sociely, volume 33, 2011.
Zhenguo Li, Fengwei Zhou, Fei Chen, and Hang Li. Meta-sgd: Learning to learn quickly for few-shot 2017.
learning. arXiv preprint arXiv:
Dongze Lian, Yin Zheng, Yintao Xu, Yanxiong Lu, Leyu Lin, Peilin Zhao, Junzhou Huang, and Shenghua Gao. Towards fast adaptation of neural architectures with meta learning. In International Conference Learning Representations, 2019.
Albert W Marshall, Ingram Olkin, and Barry C Arood. Inequalities: theory of majorization and its applications, volume 143. Springer, 1979.
Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. arXiv preprint arXiv:1803.022 02999, 2018.
Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning or feature reuse? towards understanding the effectiveness of maml. In International Conference Learning Representations, 2020.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. In Advances in Neural Information Processing Systems, pp. 1 113-124, 2019.
Mark Rudelson and Roman Vershynin. Hanson-wrigh wright incquality and sub-gaussian concentration. Electronic Communications Probability, 18:1-9, 2013.
Andrei A Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu, Simon Osin- dero, and Raia Hadsell. Meta-learning with latent embedding optimization. arXiv preprint 18Xiv:1807.00 07,06600 2018.
Rajesh Sharma, Madhu Gupta, and Girish Kapoor. Some better bounds on the variance with applications. J. Math. Inequal, 4(3):355-366 2010.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In Advances in Neural Information Processing Systems, 2017.
Oriol Vinyals, Charles Blundell, Tim Lillicrap, Koray Kavukcuoglu, and Daan Wierstra. Matching networks for one shot learning. In Advances in Neural Information Processing Systems, 2016.
Xiang Wang, Shuai Yuan, Chenwei Wu, and Rong Ge. Guarantees for tuning the step size using learning-to-leet approach. In International Conference on Machine Learning, pp. 10981-10990. PMLR, 2021.
Mingzhang Yin, George Tucker, Mingyuan Zhou, Sergey Levine, and Chelsea Finn. Meta-learning without memorization. In International Conference on Learning Representations, 2020.
Chris Zhang, Mengye Ren, and Raquel Urtasun. Graph hypernetworks for neural architecture search. In International Conference on Learning Representations, 2019.
Pan Zhou, Xiaotong Yuan, Huan Xu, Shuicheng Yan, and Jiashi Feng. Efficient meta learning via minibatch proximal update. In Advances in Neural Information Processing Systems, 2019.
Pan Zhou, Yingtian Zou, Xiao- Tong Yuan, Jiashi Feng, Caiming Xiong, and Steven C. H. Hoi. Task similarity aware meta learning: Theory-inspired improvement on maml. In 4th Workshop on Meta-Learning at NeurlPS, 2020.
11

---

Published as a conference paper at ICLR 2022
A DEFINITIONS, NOTATIONS AND LEMMAS
Notation We denote optimal adaptation learning rate a", Global minima of empirical risk of MAML and ERM (when they are unique) are denoted by Wm. Wy, We write {I,... N as [N] and use -|- to denote the Euclidean norm. We use subscripts to index the matrices/vectors corresponding to task instances, and bracketed subscripts to index the entries matrices. For function f depends on b, omit other variables by (....)) when discuss with
Table I: High-frequency notation table.
Symbols
Definition
Symbols
Definition
Adaptation learning rate
K, kis l22
All/train/val/ sample size task
a' fimm Cest X1, As
Optimal adaptation learning rate Estimation (limit) of a Min/max of eigenvalues
Lm Lr
Population risk of MAML/ERM Empirical risk of MAML/ERM Average population risk
Lms Ly
Lm
a;
Task optimum of task i
N
Number of training tasks
Feature dimension
Wm Wt
Global minimum of MAML/ERM
Definition 2 (Gamma Convergence). Let Pn : X - R for each n E N. We say that (FN)EN r
-onverges to F X I, and write I limm- Fn = F or Fn - F,
For every a E X and every (In)neN such that In + in X
F(x) S lim Fn (xn)
n
for every E X, there exists some (In)ne such that In x in X and
F(x) 2 limsup Fn (In)
Definition 3 (Lower Semicontinuous Envelope). Given F : - R, the lower semicontinuous envelope (or relaxation) of F is the "greatest Ise function bounded above by F":
plsc (b) == sup(G(() | G: G x is Ise and G S F on X}
inf inf F (Ix) (In)nEx X and In + x
n
Lemma (Remark 2.2. (Braides, 2006)). If uniform converge to F, then F., Ig plae where Flac Lower Semicontinuous Envelope of F.
Lemma 2 (T-Convergence. (Braides, 2006)). Let X be topological space. Let {Fr} be equi- coercive family of functions and let F, -converges to F in X, then
lim dn where d, = infaex and d = infaex F(x). That is, the minima converges F,
The minimizers of F,, converge to a minimizer of F.
Proposition 2. If both A and B are positive semidefinite, the inequality is true:
tr(AB) S tr()..
(A.1)
and if A is n-by-n symmetric PSD, we have
(T(A)) tr(A)2
(A.2)
12

---

Published as a conference paper at ICLR 2022
Proof. Let tr().. For PSD matrix A, we have A al. Then
tr(AB) tr AB < tr(B (al) = tr(A) tr(A)tr(B))
(A.3)
For second inequality,
apply spectral decomposition as A QQQ-1.100 So have
tr(A) = tr(QDQ-1) tr(DQQ=*)= = E\=
where (A E [1, is the eigenvalues of matrix A. Then by Cauchy-Schwart inequality we can get
tr(Aa)²
X
Σ x
=ntr(A²)
Hhright-Wright Lemma 3 (Hanson- Wright inequality, (Rudelson & Vershynin, 2013)). Let X = (X1,..., ;.....,,)))) R be a random vector with independent components X; which satisfy EX; = and [Xeel1ps S L. Ler A be an n X n matrix. Then, for every 2 0.
A L )
t
P P A - EX AX
t S 2 exp -emin
where [lEl|, = sup p p 1/2 [E) X 12) 1/p is sub- sub-gaussian norm, ||A|| = max |Ax||2/|a>|1 is operator norm and ||A|| k. |a.
13)/2 is Hilbert-Schmidt (or Frobenius) norm.
Definition 4 (Fast Adaptation Error). Given the task distribution D(T), meta--nitializatiinn w", the optimal solution of task is W/, then t-step fast adaptation error is defined by
Fi(w", ((T)) T~D(T)
E
|w/ w
(A.4)
where w/ -
- 1 ve ((w))) is the adapted parameter of task T with t steps.
Lemma 4 (Ruhe's trace inequality, (Marshall et al., 1979)). A, B are positive semidefinite Hermitian matrices with eigenvalues,
01 2 ... 2an an 2 0, bi 2 ... 2 bn 2 0
respectively, then
a tr(AB)) S
a;b;
Proposition 3. For any positive random variable x D(x), we have following inequality holds true
(BenD(z)(23)) - (E) (() 00
(A.5)
Proof. With the fact that
(En-D(e((2))) - BenD(a) (e)
- -( oplc) dz) (f ('p(()) - -(1aaple)) d²p(x) dz)
2
(A.6)
where x > 0 and p(x) > O.
Let = (xр(z)) 0 and g = (x"p(x))*
2 > 0, with Cauchy-Schward Inequality,
( fg dx
2
s {fA 1 dx ( )z)
(2 dx
(A.7)
we have that
(/r
V V2p(z)) vpp(z\/='pll x3)(()))))))))))))())) de) = =(1 fg dx
2
(BanD(a) (x))))
(Vap(=)) dr / (Vizp(z)
2
(A.8)
dr
R
EEz (I) (x))
E
13

---

Published as a conference paper at ICLR 2022
B PROOF OF THEOREM
Proof Sketch We list our proof steps follows
1. Get global minima of ERM and MAML by first order optimality condition.
2. Let average MAML population risk Ln as the target in order to eliminate the randomness (Proposition guarantees the upper bound between Lm and population risk Cm).
3. Approximate this target function f. by another function L which is the limit of E. as number of tasks N +
4. According to positive definiteness, we can get the range of a.
5. With notion of gamma convergence, the minimizer of L. will also converge to the minimizer of Lage
6. Our estimation of o* is in the range of in Step 4.
Notation for this proof: For simplicity, we omit the arguments of the function its symbol has index e.g. 4 (xX))) C C,(a). Then give the full proof on estimation of a².
Proof. Recall that the global minimum closed form for ERM and MAML are
(r(NKK) -w, (1,( (ep(X)),aheeIv))) aiSseNN))
Σ
Σ 2 2
(B.1)
Wm (a, N, K) Win ((Ch(a),a:heIN))
C.
Σ CJ
Cjas
where C. 2
20 2. 2, C2 Rxd
Since Wm depends on random variables 01,... ON. The average population risk of MAML, defined in (3.2), where
Cm N, K)- = Ew.,, Lm (Wm, a, K) = E am a, K)
(B.2)
of global minimum um (B.1) can be written as Lm (a,, N, K)
Es, E ax DDaaa Fm (Wms K)
E
E D
E
[C(()( a]l2
K N
N
E
E
C(a)
Σ
cJ C,J
K aaaa)) X~D(a))
(B.3)
N
Let A2
C
Σ
CTC E Raxd, The (B.3) can be rewritten
(m, N, K)
1
E (a D(a) X~D(e))
E
C(a) Σ Njag
a
K
N
1
E
E
Σ Aaai
C(a)
Enya
K (a ~ D(a) XwD((r))
(B.4)
NV
T
-
C((a
Asas
-
Σ
Aja;
C(a)
C(aaja
j=1
1=1
+a CaTC(a)TC(aja
14

---

Published as a conference paper at ICLR 2022
Under Assumption and is independent to X, then we have Em (a. N, N) K X~D(a) (a.HiinDia
1
Σ Ima
C(a)TC(a)
E
j=1
da (C(a)
(B.5)
o² X-D(a))
(AJ ((A))((())C( + (C(a) (c(a) (((a))((()))
E
Let (a) be an approximation function of 2. (a, K).
d² X>D((a)
Lape (a)
E
tr(C(aTTC(a))
0 E
(1-
2a
*(x) x(x)Tx(X) xxx) x(x) o(x)) K
T
(1- 2a ((x) T ((x)
=
tr
K
X~D(a)
K
(B.6)
Then the approximation error will be
K
La, N, N,K)
- (a)
N
Σ tr (ATC())
E X~D(a))
(B.7)
N
N CcTCC
N
E X~D(an)
Σ j=l
Ir
C.C,,
((a)T((a)
Σ c.C,
where
4a
4a
C. C,
2. Φb
{b) 12)²
+
+ (0) 2,)3
(B.8)
K
K2
With Assumption 2, there exists constants 0 < < where
ci S
(B.9)
With Proposition 2 hold, Vi E [N] we have
4a
4a²
tr C:)
+
Φ 2.13
K2
4a
4a²
Lr ( Φ.)
Ir
)2 + Ir
R2 (0. T;)3
4a
40²
S sup
||
inf
tr((@]
T 2.)21 +
sup
(B.
ME[M]
K
iE[N]
K
4a
4a
=02
inf
tr( Φ.). +
K
+E(N]
K2
4a
2
c
of
Kd K²
15

---

Published as a conference paper at ICLR 2022
Then by applying multiple times of Proposition 2 we have
E
Cj Σ
c(a)
Σd cfC,
(-D(
1==1
N
E X>D((a)
Σ
tr
CJC,
Σ
Σ
C.Co
C(a)
j=l
P=1
N
$ X~D((a)
E
Σ
tr
[[]]
tr tr
tr (r((())
(B.11)
j=l
-17
N
E X-D(aa)
Σ
tr C;)
(C(a)TC(a))
j=l
i=1
2
4a
4a
E Ci
SN 02
K² 0
tr
Kd
X~D(m))
i=1
Next, we need upper bound the last inverse term. With Assumption 2 we know that all eigenvalues of (XX) (XX)) D(x) bounded by [Ar, As]. Let Cau(a) Em= C₁ then with probability the max/min eigenvalues of Cau(a) will have following constraints,
{
Aman (a)) Amoz (Cau(a))
N(A, 4a K 4o2 S (As 4a + 4a 1a223/K²
(B.12)
Since the (a) is positive matrix, need have the constrain Amin (Cau (a)) 0, which means
K(A VAg X4) 1
K(A + VAg - x1)
E
0,
(B.13)
2X
21}
There exists positive definite matrix (a N)I where
Cau(a) ž Amin Amin (Cau)I
(B.14)
and the following inequality easy to get
tr(Cau(a)) 2 tT tr(mmmn (Cau) tr(Caila)) S <tr(Amin (Cau)
(B.15)
So the last inverse term will be
N
]T=
-12
tr X~D(wx)
E
Σ
CTTO
1 N(Ar / + 40223/R3
0
1
(B.16)
No
i=1
Apply these inequalities to (B.7), we can get the upper bound
N (a
4a ka
c 40²
(a,
Lapr (a)
<
1
(B.17)
K
N2(Ai- - 40x2 40228
N
K(Aद -20 -
K(A++V Xf
When a E
0,
the limit will go to zero,
223
22
lim
sup
(a, N, K. I,apz ( =
(B.18)
N-000
x(a3 1ag x4)
x<a3 1 Af1
ag 0.
223
223
,00
16

---

Published as a conference paper at ICLR 2022
which means Lm (a, N, K) will uniformly converge to (m) for belongs to the interval above. Note that Lm (a. N, K) is continuous function of a. So with Lemma 1, we have
r lim Lm (a, N,
Lmm (a)
(B.19)
So we have estimation true a", denoted as ajm
aum arg min mm (a)
4a (0(x))((x)) -arg min E tr (X)) (()) XxD(X)
4a (X(X)
K2
K
Bx ( [
(B.20)
(a, According to Lemma where a² (N, K) is the minimizer of (a, N, N,K) a' aNNN, K) = arg min C. (a, K)K),
lim a (N, K) = Ojim N
(B.21)
C PROOF OF PROPOSITION 1
Proposition 4 (Formal state of Proposition 1). Assume u = C(a) C(a))C(a)a is sub-gaussian ran-
dom variable with aub-gaussian norm [ llv = supp21 p 1/2 (E) P)) 1/p < L. Then with probability at least 8 that
L? S
de(a, K) N2
E(a, K)
log 2
Lm Cm(um: a, K) (a N. K)
max
log 6'
(C.1)
K
N
0, K(G / 14--13) 151
K(A S
-1f1
if E
U
and
2x
2A7
E(a, K) = (As - 4aA7/K + 4a -4A////44////K 4 2/22//33/
when assumption I & 2 holds. d is the feature size, N is the number of tasks and K is the sample size per task.
Here, we follow the same proof notation Theorem 1.
Proof. By definition, we have
Lm N. = ax D(a)) D(a) C. (w, (a, K),,, a),
(C.2)
Similar to (B.3), let A,
IN CTC.)
CJ we we have,
Lm (Wm, ar K)
E
E
[C(() (a, N, K) a)
K a>D((a) X~D(at)
N
E
C(a) Σ Aja5 - a
K a~D((a) X-D(a))
N
N
E
Σ Aaa;
C(a)
Σ
(C.3)
K X
N
a -aTC(a)TC(a)
Σ A,a;
Σ ,,ai
C(a)aa(a)a
1=1
+a TaTC(a)TTC(a
17

---

Published as a conference paper at ICLR 2022
With Assumption 1, second term and third term of (C.3) will be cancelled. So the L. is
Lm K X-D(a))
1
Σ Aaa,) )
C(a)
Σ Aaa
o
E X>D(a)
cr(((a)TC(a))
(C.4)
As the comparison, (a, N, K) is the averaged function of L.., which is given by
N
Fm 1 K (=D(a))
E Σ Aaa
C(a)T((a)
Σ Aja,
Hn (a.
(C.5)
+ o (C(a)
Let A be the common matrix of cross-term of a, and aj, then for each term in (C.5),
N
N
C[C( = =
Σ C
C(a)
Σ
C
C,C,,
M==
(C.6)
=Ū,AC,
So cancel their second terms, the difference of Lm (W,m a) and L. (a, N, K) will be
Lm Cmm(wn (Wm: a, K)- (a, K)
a (C(a) + XxD((a)
ΣΣ a C.Ačaa
E x(nD(a)
a C.Aūaa (
K [a.)) (xD(
i=1j=1
(C.7)
Σ a C,ACaa ==
ΣΣ ==j=1
a T,AAaa
E K XND((a)
(a
1=
N Auj
N
1
E K X~D(aa)
E
u
Auj
(a: (a:) (=1
where Č,a; = C. Cja; is sub gub-gaussian random variable and with Assumption 1,
Eu, Ea, = 0
(C.8)
Let UiN] = -uui;..;; E Nd, we write the quadratic form into a bilinear form for each product
term u. Auj
A
A
U1
U ANIAUIN (uT ux)
ΣΣ
u T
Au
(C.9)
A
uN
where
Ā = 1v1N @ A,
||||| E R
NaxNa
(C.10)
a N N block matrix and @ Kronecker product. And the relations of A and À are
A NIA AA 2 Σ Als
(C.11)
18

---

Published as a conference paper at ICLR 2022
By applying Hanson- Wright inequality have
Pr (1 (Wm: a, K) - Lm (a, N. > Pr
U ANN SOUTT-AUiNN 21)
K
(C.12)
82
2 exp
-emin
LAIIA|I
Further with Cauchy Inequality, we can get the following equation
N
N C(a)
|||
Σ
o
Ox
(C.13)
N
Σ
Cr
<
According to Theorem 1, all eigenvalues of second term falls - 4o2////KKKK////// 4aA2/ K + 2 K / and of order I/N for first term.
(As 4a K 22
/3 K2)
||||| -
(C.14)
N2 4a K 40 K2)2
Let Let K) (As 4a27/K 4a //, 4023/K K + 4a /
| NAI K)a
(C.15)
N
Next, we can bound ||A|| us by ||||]. It's obvious that ||A]|s I (rank(A)]| So ||A]] can be upper bounded by
Taaaa) 7 [[(((a]T(aa]
N Σ
Ca(a) Ca(ai)
|| S rank(A)]|A|II S rank(A)
(C.16)
rank( rank(AA) K)
dea de? K)
<
N
N4
Thus, the ||Al)s will no more than
|| S <a) N2
(C.17)
In summary, we can get the bound
Pr (| a, K) - C... (a, N.) >) s 2exp
-omin
I.N LAds"(a, K)' L2e K)
12N2
(C.18)
Finally, we rewrite the inequality by eliminating I, we have at least 1 6,
1
{ [ee(a, K)
2 8(a, K)
log 2
Lm(Wre a,, K) L. (a,, N, K) S max {V
log
(C.19)
N2
N
D PROOF OF COROLLARY
Proof. Recall our estimation of at is given by.
K xx (xx)
aim = arg min Lap (a)
(D.1)
Str[Ex[((X)) (X)
19

---

Published as a conference paper at ICLR 2022
For each task, we have K samples with d dimensional features (X) RR Since ( T ((X) is positive definite matrix, by applying spectral decomposition, we have
tr Ex (((D(()T((()))))) ((x))² =Bx (x)))
=Ex tr((UExU [(UUEX("(UXXUT)) [UEXUT]]
(D.2)
= Ex 1
where U is an orthogonal matrix and Σx is the a diagonal matrix filled by eigenvalues Ai.... Aa of the covariance matrix of the feature. It's easy prove in Principle Component Analysis (PCA) that tr Exxx is the variance of features where
o² (6(
1 K
Ex ( 10) ($(() nt)
K
Σ (d(x;) - -11² Σ A
(D.3)
K
K
B(Ex)
K
where o(x,) E IRd is each row of (XX) and μ is zero.
With Jensen's 's inequality, we have
[[x]( S ttr s [[r](E (021)
(D.4)
Thus, write the inequalities
K[tr Ex (2x)]²
Kdftr (Ex)]²
x (3x)]3 2d tr E.
2ft Ex (Ex
(D.5)
K
Kd
2d Ex (Ex)
2tr Ex (Ex)
therehy
d
S ajim S
(D.6)
E EXAMPLES
Example (Normal, Polynomial feature) Assume we have K i.i.d samples I1. 2K and a is random vector from zero-mean distribution. Consider polynomial basis function Φ: R Rdd where d(y) (I, yd
(
(XX)
:
(E.1)
((TK)
A-1
Since we have
[x db (X) 26 (X))1
(E.2)
21r[Ex 2 (X) (X))31
So that
2 Σ x 2(1-1)+4
trEx((((X)) (()))(XX)xxx)11 EE,, >
+ +...+
+
Σ
x
(i-1)+
- 1)+d
2
F
(E.3)
j=1 m=1
K
16 2 2 22) 2) (K 1)K Σ Σ
122 22 (0
1=1
20

---

Published as a conference paper at ICLR 2022
Similarly, the denominator is
T [
(
d d
d
k
\Σ
k Σ
Σ
Σ 1=1
2
+
1=1
L7
B
2/+1-3
2
+d-- 3
2//
Σ
24t1/2
1=1
dk²
(E.4)
=E,
/+1 ++d 2 x
Σ
x
+
dk
dK(K-1)
[KTE] (1itttmttttt1-1-1 +3K(K 1)) 22:22211--11 m1
/=1
+(K 3k 2K (K (a
If K = 1, 1, + 0 the optimal ajim will be
j=1 Σ d
m== E B2,221+m-- 21
apm
2 ΣS=1 -i=1
Dd 0== E3 22
2d
IC 1,1) 20 d 1, 2
2i=0
(E.5)
2 3d
92 [\[[(())
Ed'- g1 1)0 (0
1)!!
2 - (dd (2j 11)!!
02
where C(n, k)
is the binomial coefficient and (d, C(i+ -C)
d+ 1,1).
k:
K - 00, σ +
(K - 1)K2 Σ 2j=1
E [2 2)
Oiimm
D5 j=1 E1=1 Ed=
3 3K² 2 2K E3 (x(++m+1-3)
Σ/= Σm= 2 + 21]
j=1 Σl= Σ - 33 [3 O(1)
(E.6)
1=0 Φ1 (d, B3
2d-2
((1)
==0
Σ 91 (d. 1)!!
1 0z
0(1) o
3d/21 sa(d, 1)!lrs
We show the coefficients of each moment in the Figure 6. As we see, denominator becomes dominant since the coefficient of every moment, number of terms and order of moment are all larger (higher) than numerator.
So in this case, the a/m has an inverse relationship with o².
Example 2 (Random Matrices) Assume all elements Y. in feature matrix are independent. Then let Y be random matrix we have
21

---

Published as a conference paper at ICLR 2022
800
91 92
1750
91
1500
g3
600
1000
400
750
200
500
250
0
0
50
100
150
200
250
300
20
40
60
80
120
140
index i, (d=50)
index (d=50)
Figure 6: Example of d = 50 with coefficients of each moment given by 91 (d, (2d a), (d(
E Yi
Σ
Yn
((X)x((X) =
(E.7)
zi=1 VidVn
Σ Vid
For the numerator in (D.1),
K
(2 YuiY's
K
tr [
-By ΣΣ s=1
Σ
Yusi
1=1
(E.8)
=dKB[t + (dK(K 1) + d(d - 1)K 1
+ d - 1|)K( 1)K(K-1)B-1) (M)
Here, the row m column entry of (0(X) ((x))² is
d
K
($(X) mm)
Σ
YinYa Yie
Σ
YenYis
(E.9)
==1
The diagonal entry of (Ø(X) 3 ((X))
at row m will given by
K
K Σ
(x( 2 (mm) Σ
Yim Yis
Σ
YunYrs
YimYio
(E.10)
j=1
Similarly, the denominator is
tr tr [xx (x))*1
K
K
K
= =Bygyie(k),jel
Σ w=
Y im Vis
VinKee
Σ 5=1
Yym Knm Vyo
= K + Kdddd - 1) (E
+ E²1 (1
+ by + - - 1)d(d 1)
EY
1E
(E.1I)
+ b, + K(K - 1)d(d 1)
1)
B
+ 6, + K(K - 1)d(d (CCKK-DD(--DDD00<"""00>----1-001
+ 02 + (K33 - -KK 1))E -M + E (x1)
22

---

Published as a conference paper at ICLR 2022
where b1 = K(K 1)dEEY" (K3-3K" + 22 (KKdEB1 (
K 1. the optimal aism will
dE Y
E1 Y
(E.
Yo
2E
K - oo and d + oc,
K (dd((K (1
Oeimm
(K3 3K² + 2K)
+
0(1)
(E.13)
dR3 dR3 + d(d ( ( + E3[y
E - 3 "",-- 0
E G (1)
Both examples related to the high order moments of data distributions. In polynomial feature example, we focus on the gaussian distributed data and its inverse relationship to data variance. As for any random matrix, it depends on the fourth moment over sixth moment.
F PROPOSITION FOR THEOREM 2
Proposition 5. 7,, a E [-e, e) global minimum of MAMI. wm((a)) is given by following equation
Wm (a) =w, +a Σ (x2,) T ((X,))
Σ (o(,)) ((x,))
( (w, ag))
(E.1)
V w (E)
(ax E)
2!
where w, is ERM global minimum.
Proof. As for the MAMI,, the global minimum is,
N Σ C.C,
N
Wm (a) =
Σ
(F2)
with C((a)= 4; 24 2 4, Ca(a) E kxd
Let Wa = Ein C. (a)C; and v. denote En C.J.A then
N
2a
2a
V.W.
=V a
tb T
43
4
4
4
K
K
t=1
(F3)
8a
[ T
)
2
K2
Similarly, we have
N Σ
8a
V Vo =
( Φ2) 2a;
+
(
a
(F.4)
K
K²
23

---

Published as a conference paper at ICLR 2022
For first-order derivative, have the following form,
Va Wm (0) -Wo'last Vavale a=
VaWall=zie (0))
N
N
4
Σ $
Σ
(
13 Paj aj + Σ
( 1b)) 2 (0)
K
K
1=1
(F.5)
N
Σ
4 Dj
Σ
4
2b
(wm (0) - aa)
K
1=1
Recall that
N
N
Wm (0) W.
T
(F.6
So for small a, we have the Taylor expansion at zero that
V w (E)
Wm (a) Wm (0) + Wa (0) +
(a - E)
2!
N
-1
N
w +a
Σ
(Xx)) ((Xi)
Σ
(Txxx))(((Xx)))
(wa - ag)
-ai)
(F.7
K
V2
th (5)
+
(a- =E
2!
G PROOF OF THEOREM
Proof Sketch We list our proof steps as follows
1. Based Definition our target is to illustrate that fast adaptation distance gap between Wm and w,, is always negative which means MAML has smaller distance to all the tasks at any adaptation steps in expectation.
2. We first get the linearized expression of w. by Proposition 5.
3. Compute fast adaptation distance gap A Ty, task distribution D(T) and take expectations with respect to all random variables.
(wx, across same
4. With lemma of trace inequalities and assumptions, we can get the upper bound for the dominant term of A, refer to (G.30).
5. Bound the reminder terms, can get the range of
Notation for this proof Follow the Theorem 1, we omit the arguments of the function if its symbol has index c.g. 4r ((Xr). Covariance matrix 4 = GT and inverse of sum covariance matrix V (ZiE(N) $ 2.) -1 for short.
Proof. For each task T sampled from distribution D(T), gradient descent iteration yields
w w/ 17 Vlr()
21 x.
(DTWT +Tar)
K
21 d DT
20
w/. +
db PTaT
(G.1)
K
K
2m sb T DT
1+1
1+1
27
2n
5-1
w
Σ
(
oT
2o
K
K
j=1
24

---

Published as a conference paper at ICLR 2022
where w is the initialization. Let GT
O Pr, the adapted error will be
2
| arll
27 (1-
GT
w
+
21
1
2n GT K
)
Grar ar
(G.2)
K
K
j=1
For simplicity, let
QT= =
QT
2n K
GT
ST
Σ
2T
1
2n
GT K
J-1
GTaT aT
K
j=1
then with Definition 1, we can get t-step fast adaptation enror for MAML.
F((w))
E T>D(T)
1 + Sr
(G.3)
and the ERM fast adaptation error is
F((w)))
10/ Srll
(G.4)
T~D(T)
Note that the sum geometric series in ST
j-1
27
2n K
ST =
GT
Grat aaar-ar aT =
GT - aT = Qtar (G.5)
K
K
Now, let's focus on the error gap of MAML and ERM, denoted as A, then we have
A
E T D(T
F((w) F(((e)))
O6 (w., + +w²) + 2ST, OJ (w - w/)) )
(G.6)
E TN.
For small a, we get its linear expansion in Proposition 5
V2 w wn (E)
wh (a)) : + a V. 20
(0)+
(a -E)
0
2!
-1
(G.7)
t + a EG,
Σ
4
G2
(w a,)
+ Rr
K
where R₁ = [00 V. u (E)
(a =) is the reminder term. So it would be
E
Q+ (2w a wh (0) + R1) 2Sr, VQ'
(G.8)
wi and TTD(TT
Let V EN G3)
and the first derivative V wo (0) is split into
a V w (0) V
Σ
4 K
v
Σ 4
(G.9)
thus inner product will be four product terms and reminder term which is
{
N
))
N Egjas
A
8c
E
E DID(
Qiv
Gi
w. OiV
K
(a.
Ez 1)
N
N
Gaa 1)
+ ST. Q.V
ST. Q+V
+
RS + Ri
(G.10)
25

---

Published as a conference paper at ICLR 2022
where the remainder terms
R2 a² Va Vown (0), (0), V Va (0)), Ri a² Rı, vo (0)
(G.11)
Now, let's look at the expectation. Recall that task T is defined by random variables (+(x)) ar). With simultancously diagonalizable assumption, all feature covariance matrix in tasks can be factor- ized to
((X))) -
(G.12)
where U is the basis of features, Ex is the only random variable of Gr. So the data of each task depends on eigenvalue diagonal matrix Σr. So taking expectation T means the two independent expectation (D))D(()) Bay=D(a). Similarly, w in previous section is expressed by
w
G.
Σ
Gja
(G.13)
Ey..... Tr (w")
(a:) B(c,)) (w,) (ar) my Errani (w)))
For each product term in (G.10), we list four main terms as following. First term is
Q.V
Σ
G3ud
Tr.... Tw.DT((T
E
QNV
Σ Gjai
4ax
Q V Σ C.V
Σ EGaa
(G.14)
((a)) (Gch
K
N
E (G.)
tr
Σ GVVQQVV
Σ
VG,
Similarly, we can get the second term
N
EE
Ooree @+V V
G:aj
E
E (G.)in)
O Σ G3aj
(a.
(G.15)
N
E [G.
tr
Σ
G.VQ+
For third and fourth terms, Eap=D(a) is marginal expectation of ET-D(T)) thus
N Sr. V.V C9
E (wD(T)
= E
E a)~D(a) wi (G.(G.
-harr,
ar Q.V Σ G.
(G.16)
Similarly, the fourth term is
ST. "
G3a
(G.17)
((a) T~D(T)
26

---

Published as a conference paper at ICLR 2022
So overall, the care about above four terms function of a, N, tt,.... denoted as 6, (a N) (e N) =A
R2
Ri
N
8
E
Σ
Eg
VG.
K
[G.]
N
80
E K (G.)(N)
tr
Σ GGVOT
N
N
8a
E K [G:],]
tr
Σ G.VQR
Σg
VG, Σ
(G.18)
1
N ((
&a
E K (G:],N
tr
Σ G.VQ
VG; G.
8ax
E
Σ VQLQIV
VG -G
G?
K
(G.]M)
By simultaneously diagonalizable assumption, we have Nh
N
- (122071)
8, = 80
E (r.))M)
tr
vor
K
i=1
N
N DEEDSNN33 - EuUTUT )
N
8a
E tr
VototV
K
(G.19)
where EN =
(EMELN Ex
is a PD matrix and Qf = - (21/ K) is exponential decay
term w.r.t 17. With probability 1, A. E, 1
(N - 3
(G.20)
Note that VQ$Q4V - (Q+V)T V symmetric positive definite matrix where
VQLOVV V =UÊNUT QUUÊNUT
-UENUT (UUT (UUT-2 -
-2 -MUETUT) UÊNUT
-UÊNUTU (1---
[-
21 Er
K UTUENUT
(G.21)
-UΣN
1
21 Dr
21
ΣNUT
Note that m-th diagonal entry of E(E.JiM
N Σ
UEPEN EJU - ΣN UI!UT) is
(EX2)2
EXEA3
(EXP)2
EXEA3 -EXE> |&m 11
(C-)
(m)
C(m)=
<
(G.22)
NEÀ
NEA
NEA
where (C-S) is according to Cauchy-Schwarl inequality for integrals in Proposition
So the above matrix is a negative definite matrix. Now, let can derive following trace inequality for NSD and PSD.
Proposition 6. I is n-by-n negative definite matrix and B is a n-by-n PSD matrix, we have tr(AB) S Amin (B)rr(A)
(G.23)
27

---

Published as a conference paper at ICLR 2022
Proof. By Ruhe's trace inequality (Lemma 4), we have tr(AB) E, (n Eigen-
values of A are negative where (A( < 0, Vi E [n]. So we have tr(AB) I Amin (B) >, (A) Amin (A)
So with Proposition 6, we have
N N ΣΣ
N
6,(a, -
So E
Amin (V) tr
-
-EUSPUT
(G.24)
K
(EAN
with (G.20) and (G.21)
Amin (VQ+Q+V)- Amin
ΣN 1
21 K
Ex
21
ΣN EN
1
1
20122
21
(G.25)
N
K
For the second part, we have
N N
N ΣΣ Σ
N
N Σ
-1
Ir
Σ
SUDUT
= Ir
Σx
Σ
j
k
N
N
N
N
tr
Σ Σx
Σ Σ
Σ 3
h
N Σ
N Σ Σ
N
N Σ
N
S-min
2i
tr
23
k
N
N
N
N >Σ k
N
1
Σ
Σk
tr
ΣΣ E
NoN
k
(G.26)
Overall, with probability 1, we have
5e N) S N3
Sad
2nd
26
I tr (E.i
ΣΣ
N
N
N Σ k
N
3 S4
(G.27)
K
Specifically,
N
N
N Σ
N
E [E:)
tr
&
tr
NE
NE(E*)
(N2 N)B
(N² - N)EEE>EEE E()
(G.28)
c=
(N² N)
B Pio
[E(S>) B{E)
1=1
With Proposition 3 we know that any eigenvalue x = E(1 > 0 obeys the statistical condition E?[22] - E[}]] Thus there exists constant è > 0 such that
E tr (E/hv)
Σ
Σ
M
<-dd(N2- N)
(G.29)
Finally, we have
(((,,))-((1121))
217
21
Sad
1
N))
Xx
(G.30)
K
KX3
N
NZ
28

---

Published as a conference paper at ICLR 2022
Now, let's bound the remainder terms R1, R2 where
E GJ m.: a;) )
R1
E ( D(a) T~D(T)
E Q2
(G.31)
Ri is the remainder term in Taylor expansion (G.7). With Integral Mean Value Theorem
Va w (E)
a² V (5")
R1
(a - E)
(G.32)
2!
2
We have the locally Lipschitz property for C function wm (a),, in small region with small a such that
a² V w (0)
R1
(G.33)
Then have
N
-1
N
V 2
(0)
Σ
Gk
Σ
a - C. + VG
K
8
Σ
N
Gk
-1
ΣD
N
N
G. - G.G (n az)
K
N
N
N
8
Σ
Gh
Gu - - + (G,Gaa, - 10303aj)
K
N
N
N
8
Σ
Gk
Σ
(G
G az))
K2
(G.34)
Recall (F.6) the : = EEN N T.
[ N T. b.ar) while BaIN)D(()) w. a; =0. The R2 in
above equation is
4
R2
E T~D(TT
tr
-
K3
3
U EY Of
E
tr
K3 T-D(TT
(G.35)
4
tr T~D(TT
I
Ir
R3
i=1 j=1
2d
21 K
N
N3
A
sup iJj[[N]
E tr 2.
-
And the eigenvalues of Eg are bounded in DAs Az) where
E Ir
M
-
ir 3NEE" + +NN - N))((
E,,,,
(G.36)
S d 33 + +(N2 - -N) - 199]
< (4 - -19
29

---

Published as a conference paper at ICLR 2022
In summary,
4o 4a
-99)
(1 1
27
21
R S
As
(G.37)
NK
K
Similar to R let's bound the R2 in (G.10),
N
N
R₂ =
E D(a ITD(T)
E
Σ
G2
(n -aa)
Q.V
2 K
G3 (w
a1)
K
16a
N
N
E
tr
Σ G.V
$ tr
Σ
tr
Σ
Q7
(G.38)
K2 TND(T)
TwD(T)
i==1
i=1
16
2m As
21
X2NK2
Thus the final constraint of a will be
27
40x 3 d (41g
19)
2 X
8ad2
(
1
)
A3
0
K
NK3
X2NK2
KX
N
N²
27
Ao
21
a (414 12)
4ax
- f -2
0
(G.39)
K
K
X²K
1
N2
a²
2 (4A g
4ax1
2e
1
+
1
0
K2
X²K
N
where ratio factor f == [11 21/ K xxx) /
- -2n/ K KX,,) We have the extreme points of a
41
+
+ 4
(4A8
2 x
(1-
x
Ra
a(N) =
(G.40)
(119 X2)
K²
For K E z+ 2 1, small a, [ 0 and large / we have
A= [(1 2n/ K KAa)/ / 2n/
(G.41)
So finally, the needs to satisfy
2 + K / + -
a(N) S a(2)
(G.42)
X2 X0)
H EXPERIMENTS
H.1 PRACTICAL FORM OF THEOREM
For practical use, we show a numerical form to estimate a for the case where number of tasks is finite and training data u E l is different from validation data E R The corresponding feature matrices are & ((u) and (t).. Let's derive corollary of Theorem for realistic meta-learning setting.
Corollary 2. If training feature (u)) E glixd is different from validation feature (t)) E & xd for every task, then
En ( (())
aijm (k1) = 2r ((u) ((u)((((t) (()))))))(())(TT)))))))) Tuu)
(H.1)
Proof. Similar proof of Theorem have
N Σ [((a)))((aa)
-1
N Ca(a) (((O)))
Wm ((x,, a; OalEMM, N, k1, a2) =
Σ
(H.2)
30

---

Published as a conference paper at ICLR 2022
where Ci(a) (I
& ( TT(u,)) Reaxd
The corresponding average population risk will be
Lm 1 N2, av..a.... Cm (Wm: at ki, k2)
((a) (Wm (f actiel) N. b)) a)l
(H.3)
E
a. N w>
Then we can define similar approximation function L (a) as (B.6) where
L aape (ax) - BeeDD(a) ir [(aa)
(H.4)
And with same bound for [[:(,)))l: ((,))] (2), have
lim Lm (k1, h2, N. Lap (a)
(H.5)
-0000
With Gamma convergence lemma, can get the final estimation ajem in (H.1).
In experiments, we use the following numerical form
hn Di tr ((t))) (t.))
Ofiim
(H.6)
2Σ (( 2(u,))
evaluate our estimation.
H.2 OVERPARAMETERIIEE SETTING
Let's consider overparameterized setting. Thus, we have feature for each task (K < d), v ((,,), E R Correspondingly, empirical objective of ERM given by
(w) NK
V.w y:ll-
Assume meta-initialization the mean of all task optima that mean (a1, aN). Then concate- nate all task features we have
Vi(1)
Valt
yall E NKxd
(H.7)
V N(KK
So MAML objective is given by
I Vanw' yaul
NK [[Ca(a)) - a
(H.8)
NK
where w' -Iw 2a/(NN))aat (V v (2a/NK)V a.)). The minimum norm solution is
TT a)) is adapted parameters and Cau(a) Van (1
W.n (-.., N, K, Ca (aal(a)Cat(aa))) Cau (a)a
(H.9)
Note that, in overparameterized setting, Theorem will not perfectly give the precise form for a*. But the technique can be easily extend to large d setting where
(a, N, K) = =Ea a (C - a]
Ea,,,, [w] C(a) C C(a)w,, + +a C(a))C(a)aa
(H.10)
Ex tr(Cau(a) C.gram ((a T.grm
Caram Cau(a))
+ Ez tr(C((a) C((a)]
31

---

Published as a conference paper at ICLR 2022
where Can (Can(a)Can(a))))
By Proposition 2, the Lm (a, K) will be upper bounded where
Lm (a, N, K) = tr Catt ((a) ((a))aa))(( E, (rC((a)
Ca (a + ((C(() =mm Cau(a)) Care
(H.11)
S tr(Cau(a) Call Cau(a)) (rCCa)) + E. tr(C(a)) C(a))
Cau
=2 tr(C(a))
Hence, minimizing the upper bound also tells us how to select a². In another word, we are seeking an estimation gest nearly minimize the upper bound.
Best = arg min E. tr(C(a)
(H.12)
a
and the C(a) C(a) is covariance matrix where
4a C(a) =
V
112
4a
(
1/3 (v)
(H.13)
NK
K2
We can derive that
NKE E. tr(v 4/3
Cest
(H.14)
Since d is large, its computational cost is high. Here assume second moment of all elements of T v are σ2, which means 7 is the variance of all elements of features, Finally we have
Cest 2N K
(H.15)
Let's take the Neural Tangent Kernel (NTK) (Jacot et al., 2018) for example, f(w énit xx) + "ns xx)
f(w, x²)
(w w iiit).
(H.16)
Then have neural tangent feature
v w V flo Xi) (w initt
(H.17)
1 = fn X,)
Next, stack all the features V all compute the variance e.g. recall V Vtu.std(). After that, we can compute the estimation Deat using (H.15).
H.3 EXPERIMENTAL SETUP
Estimation of ax* underparameterizedd model We set hyperparameters dimension d = 20, number of training/validation samples task K = 50, number of tasks N = 5000. Each x: is i.i.d sampled from a distribution u(- 5) while each a i.i.d sampled from high dimension Gaussian distribution (O,,, 3/). Then computing the Ordinary Least Square (OLS) solution with different a, can show the training loss landscape in terms of a. The true a (N) arg min, min L(a, 5000, 50, w) is the minimizer of the training loss. Our estimation a%m described in Theorem is evaluated by comparing the error to true a*.
Estimation of a", overparameterized model We perform the nonlinear regression on different models. The first is quadratic regression using neural tangent feature (see H.2). All hyperparameters are set to be same as (Bernacchia, 2021) where
2 W N Wo: p 1111
b b~ b~~(00,0)) (0,40) y x x/x,w,b> N ((x w + b)2,o²)
But to guarantee the overparameterizzaton,, dimension will be 30, 001. Then we perform quadratic function regression with ranging a value to see the test loss. After that, evaluate the how accurate estimation using (H.15) is by
set hidden size with 10, 000, which means the total
32

---

Published as a conference paper at ICLR 2022
comparing to optimum of test loss. Second experiment is sine function regression using 3-layer MLPs activated with ReLU. The data and labels are generated from a stochastic function
y = a sin(2 + b), a, ~ (1(0, x), x ~ ((-5,,5) 5)
To get a good representation, we pre-train the model with ERM loss and then freeze the first two layers the feature extractor. Then we use the output from second layer as the random feature to train last layer on 1, 000 training tasks. At the same time, iim can be computed from the features of 000 training tasks. Then last layer trained with differnet a will be evaluated on 10, 000 test tasks.
Fast adaptation distance We run experiments with random matrices. For each task, the data are ii.d drawn for the prescribed distributions which represent three common types, Uniform 41-5, 5, 5). Gaussian N (N 2) and Exponential Exp(1). Specifically, each entry in random matrix X E RR (K 50, d = 20) is sampled variable from distribution (i)) ~ D(z). The feature X. First we sample 5000 training tasks to compute the closed-form meta-initializations for ERM and MAML with small (10 4). Then we perform t-step adaptation on 5000 test tasks and compare the fitting losses and the Average Distance under Fast Adaptation Fel (w F(W,)) The learning rate 1) fast adaptation evaluation 10-5
map is an identity map 4 (X)
Estimation of a", deep learning In our experiments, we valid our estimation of a' on sine regression and few-shot classification.
For deep regression, we follow the (Finn et al., 2017) to perform sine regression with 3-layer MLP whose hidden size is 40. Then each task an instance in stochastic function y = a (i + b), b ~~ (0, T) while the training set is 10 i.d sampled data pair from the corresponding sine function and test set is consists of another sampled 256 points. During test, we sample 10, 000 tasks to evaluate the learned model.
For deep classification, we follow the Omniglot experiments in (Raghu et al., 2020). Here, we adopt the online estimation scheme to compute the a for the adaptation learning rate of last layer. To this end, we apply a 1/ x Nway Nshot x o²) where o² is mean of covariance of the normalized feature F F, F (Fi/I/Fill.... FN / [lN')...))) Then Obuffer in the buffer is online updated using fhuffer + 0.90 + 0.1a".
H.4 ADDITIONAL RESULT
H.4.1 OFTIMIZATION BEIIAVIOR
We add more illustrative experiments visualizing the trajectory of global minima of MAML. We consider normally distributed task optima with centralized data and uncentralized data. As shown in the MAML minimum still try to balance the distances to different task optima. But the situation is more complex uncentralized data (second row). However, a always minimize the geometric distance beginning where the shape of mean distance function appears be convex. This has confirmed our Theorem 2 where small always lead to a shorter mean distance to different task optima than ERM algorithm.
H.4.2 ESTIMATION OF a" ON BASIS FUNCTION FEATURE
Firstly, we used the random matrix for task as the feature matrix, D E Kxd All elements of &; i.i.d sampled from ()). Secondly, created the random features using Gaussian basis function. Gaussian basis function & (X)) = exp(- (X(s)) - 21,)² /2a?)
) is a function whose value depends only on the distance between the input and some fixed point. Thirdly, we used polynomial feature (i.) (co. c, d-1) which is based Taylor series. With N tasks, compute the one-step adaptation loss. Optimal learning rate minimizing the loss is denoted by a (NV). The error gap between true optimum and estimation |a (N) - amml with three random features are shown in Figure (a). (b)& & (c) respectively. To reduce random errors, there was an average of 10 sampling trials, shown the solid lines. The shadow
represents standard deviation. As the number of tasks N increasing, the estimation error will shrink down to zero and its uncertainty reduces as well. So our estimation is reliable and accurate when number of tasks becomes large.
33

---

Published as a conference paper at ICLR 2022
Mcan distance
W12
30
0.00000. www.000025...o 00500 00750. 200.0.000.0000010010 155.01330.0177
W111
Mean distance
32
Wo3
20-
28
26-
-6
24-
-8
0.000
0.005
0,010
0.015
0.020
WI21
Figure 7: Additional results for optimization behavior with normally distributed task optima. Left column: Visualization of trajectory of MAML solution. Orange dots are task optima {ahnN] of sampled tasks, where location of a; decided by its entries. Red dot highlighted in circle is new coming task. Green cross is Wy, (a = 0) while the purple trajectory is generated as a increasing, Red star is wm (fism> ...). Right column: Average euclidean distance of Wm (a. and {a} [N] and corresponding points in left figure. First centralized data (0, 2), (0, Second row: uncentralized data x ~ 7(0, 5), (0, 3/). Best viewed in colors.
0.025
0.6
0.020
0.20
0.5
0.015
0.15
0.4
(44)
0.010
0.2
0.05
0.1
0.000
0.00
0.0
21
2'
2
20
2
2'
2
2
2
2
2"
2
2
Number tasks
Number of tasks
Number tasks
(a)
(b)
(c)
Figure 8: Estimation error la" (N) ajm along task number N increasing (K is fixed). The blue line in the shadow is mean of the error. The shadow area is the standard deviation of the errors. (a) Random matrices (b) Gaussian basis function (c) Polynomial basis function.
We use Gaussian basis function as the random feature and conduct the experiments on different types of distribution to evaluate our estimation quality. Then, with zero mean 24 N as the stereotype of central symmetric distribution. In experiments, we set 15, N 3000 and the parameters in Gaussian function depends on the range of data. As shown in the Figure 9, the estimation aj is close to true optimum, a* in four different cases: (a) data is sampled from a central uniform distribution 2/( (((-,,5), task optima are sampled from central normal distribution (0, 32 I); (b) data is sampled from non-central normal distribution (0 22), task optima are sampled from a central normal distribution (0, 3²1): (c) data is sampled from central uniform distribution 2/(-5, 5), task optima are sampled from non-central normal distribution (5,5 I): (d) data is sampled from a non-central Chi-Sqaure distribution x7).. task optima sampled from imbalanced Zipf distribution P(x
uniform/normal distribution
k) 2(o where ((s) is the
34

---

Published as a conference paper at ICLR 2022
0.001
0.005
0.01
0.05
0.08
0.1
0.15
0.2
0.3
0.4
0.5
Pre MSE
829
822
822
827
829
827
825
821
826
825
826
Post MSE
829
820
817
807
800
797
805
820
861
955
989
Table 2: Test loss of one-step sinusoid regression with neural network feature. First row is the discrete test values of second row is the Mean Square Error( (MSE) loss before adaptation and third row is the loss after adaptation. All loss values are digits after the decimal point
Riemann Zeta function. Note that results in (c) and (d) are beyond our Assumption 1, So our theorem can be extended to more general scenarios.
40
30
30
Loss
10-
alpha
alpna
(a) x U( 5, 5) a (0, 9Z)
(b) x ~ (3,, 4), a (0, 9I)
175
150
75
50
-0.4
-02
0.
02
0.6
0.8
-04 -0.
0.0
02
0.4
0.6
0.8
1.0
alpha
alpha
(c) ~ U1( (,, 5), 15,
(d) ~ x² (7), Zipf(2f)
Figure 9: Evaluate estimation aim on different types of distributions. (a) Central data distribution and central task optima distribution. (b) Non-central data distribution and central task optima distribution. (c) Central data distribution and Non-central task optima distribution. (d) Non-symmetric non-central distributions for data and task optima.
H.4.3 ESTIMATION OF a" ON NEURAL NETWORK FEATURE
We used neural network based feature verify our theorem in underparameterizee (original model size in Finn et al. (2017)) and overparameterized setting (NK < d). In former setting, we used 3-layer Multilayer Perceptron (MLP) activated with ReLU for sine functions family regression where each task is regress an instance in stochastic function ERM to train and freeze the first layers (as feature extractor) and then only fine-tune last layer with MAML. Compute ammm through features of sampled training tasks got a 10319. As shown in Table. 2, the optimal a lowest MSE after adapting 0.1 which is nearest discrete value in table to Olim"
sin(x + b), a, b (/00, T). We used
H.4.4 HEURISTIC ESTIMATION RANGE FOR DEEP LEARNING
To make it practical for deep learning, we give the heuristic estimation range where a" it might be based theorem. Previously, show (3.3) for underparameterrized model (K d) and (H.15) for overparameterized model (NK & d). Besides, the trace term for covariance matrix underparameterizeed setting can be simplied by K where z2 is the covariance of the feature (second moment). So here, the heuristic estimation by merging these two settings, where it derived as
ajim =
(H.18)
2 K, d)
35

---

Published as a conference paper at ICLR 2022
where N, K are number of training task and its training sample size, d is model size. Next, show a simple way to estimate the range of o². In general, each element of feature with probability will fall into the [0, 1]. Then, given ñ observations, have (Popoviciu' 's inequality covariance (Sharma et al., 2010))
< 0 S
(H.19)
2ñ
Proof. Assume with probability 1, each element of ((X) has z E [m, M).
Define function terms of random variable x: by
f(t) = E [ t)
(H.20)
Computing the derivative f', and solving the minimum
(t) -B|aa] + 2t = f(E[=))
min f(t) ER
(H.21)
So we have the covariance has following upper bound
M +
8² === S
(H.22)
where
M + m
E
m 2
= E2 [[(x - m) + (2c M))
(M m)2
(H.23)
2
4
Thus for .M 1, have
(1 - 0)2
0² 5
(H.24)
4
4
for an independent sample of ñ observations from a bounded probability distribution, the von Szokefalvi Nagy inequality shows that
(M m)²
1
à²
(H.25)
2n
2n
Here, we conduct following deep regression experiments to evaluate our heuristic estimation. We plot the estimated range of a* given by our bounds the red area between the two star-lines in Figure 10. Then we perform quadratic regression with 2-layer neural network follow the hyperparameter in (Bernacchia, 2021). From Figure 10(a), our estimated range includes suboptimal points. Follow the setting of (Finn et al., 2017) (All hyperparameters are same), we 3-layer NN with hidden size to sine regression tasks. As shown in the Figure 10(b), our estimated range includes the optimal and other good a.
see, the optimal for this task is positive and
H.5 RELATION TO NEGATIVE LEARNING RATE
As we mentioned before, (Bernacchia, 2021) show negative learning rate minimizing the test loss of MAML. In this section, compare their results with ours. Specifically, we follow the setting of underparameterized experiment (Bernacchia, 2021) where the defined hyperparameters are set to be same, n4 = n, 25,n, n, 10, = 40, p 30, 0.2,v 0.2. Parameters sampled from following distributions
2 Wo:
w W~N N
-1p
1p
x x~ N (0,1)
We conduct experiments on numerical fitting loss on meta- learning instead of the closed-forms Gtest in theorems (Bernacchia, 2021)². As result on special case where a, = 0.2 is fixed. However, this strategy highly depends on the selection of a, that may not achieve the minimum of meta-learning loss.
see from the Figure 11, (Bernacchia, 2021) only give the
TTst losses computed standard meta-leamiig regression
36

---

Published as a conference paper at ICLR 2022
4.50
range
3.0
2.5
Test Loss
3.75
1.5
3.50
1.0
3.25
range
Losses
0.0
-10-2
-10-
-10
10T4
10
10"2
10-
a
(a) Quadratic Regression 2-layer NN
(b) Sine Regression 3-layer NN
Figure 10: Heuristic estimation of a" range of deep learning. (a) Quadratic regression on 2-layer
neural network. (b) Sine regression on 3-layer neural network.
d1
fix
0.0440
0.0438
-0.4
-0.2
0.0
0.2
0.1
0.0430
-0.4
-0.
0.0
62
0.4
Ours vs. fixed ar
Same (Ours)
Fixed = 0.2
positive
0.10
negative
-0.4 -0.2
0.2
0.4
Figure 11: Comparison of our estimation and (Bernacchia, 2021) on underparameterized mixed linear regression. X -aaxis is the discrete values of ae and Y-axis the test loss of MAML. First row, test loss with respect to while the left one shows same for meta-training and meta- veta-testing and right one is fixed a₁ = 0.2 strategy. Second row, comparison of test loss of different strategies and the suggested range of minimizers given by their paper (pink and green diamonds) and our estimation (red diamond). Best viewed in color.
In addition, we run deep learning experiments to demonstrate that optimal learning rate a is positive. All hyperparameters and generating process are set be same the non-linear regression experiments in (Bernacchia, 2021), l). Furthermore, we train the 2-layer neural network to regress quadratic functions with 5 adaptation steps and evaluate models on same 10 folds with each fold consists of 1000 test tasks. The results (with error bar) are shown in the Figure 12. As we can see, the optimal learning rate for both strategies are positive.
37

---

Published as a conference paper at ICLR 2022
4.4
4.4
T Loss
Test Loss
4.0
4.0
3.8
3.8
3.4
3.4
3.2
3.2
3.0
-0.01
0.00
0.01 0.02 α
0.03 0.04
0.05
-0.01 0.00
0.01 0.02 0.03 0.04
0.05
a
Figure 12: Test losses with reference adaptation learning rate in meta-training of deep quadratic regression in (Beraacchia, 2021). X-axis is the discrete values of a and Y-axis the test loss of MAML.. Left: test loss with fixed o; 0.01 and varying o,- Right: test loss with same oz and ar,
38


Reviews:
[{"review_id": "t7VfsXlLc7b", "reviewer": "Reviewer_9gLM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n\nThe questions investigated by the paper are interesting and are well-positioned in relation to prior work. The contributions appear to develop on closely related studies such as Bernacchia et al, ICLR 2021. Supporting the theoretical results with empirical studies also provides some intuition and further insights.\n\n ## Weaknesses\n\nI am not familiar enough with the methods and related work to gauge the significance of the theoretical results. However, a couple points on clarity that came up when reading:\n\n- For clarity, the estimator of optimal LR in Eq 145 could be included in the main paper, since this is used in the experimental sections.\n- Fig 5 was a little hard to understand as a standalone -- could thetwo differences in loss/solution distance be defined in the caption or in the figure itself to help with this?\n", "summary_of_the_paper": "This paper considers the popular MAML algorithm, and provide more theoretical understanding of (1) the optimal inner loop learning rate and (2) how the MAML initialization compares to that learned by empirical risk minimization. They consider the mixed linear regression setting when analyzing these questions.\n\nFirstly, to estimate the optimal inner loop learning rate (adaptation rate), the authors pose this as a problem of minimizing MAML's population risk, and develop an estimator for this optimal learning rate. \n\nThey then aim to understand how the initialization learned by MAML compares to that from empirical risk minimization (ERM), finding that on average that MAML's initialization is closer to the optimal per-task initializations than the one learned by ERM.\n\nThe two main theoretical results (optimal adaptation and comparing the meta-initialization of MAML to that of ERM) are validated in synthetic experiments with different data generating distributions.", "summary_of_the_review": "Overall this work is well-motivated and appears to provide new insight about the inner loop adaptation of MAML and the significance of the meta-initialization learned by MAML, so I would consider recommending acceptance. However, as stated, I am not familiar with related theoretical works so have selected my confidence score in accordance with that. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "t-8hneLXcxe", "reviewer": "Reviewer_6tyw", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[Pros]\n\n1. This paper is well written with numerous theoretical findings supported by derivations in the appendix.\n\n2. Their method of how to properly set the inner-learning rate and their implication can benefit the meta-learning community.\n\n\n[Cons]\n\n1. As far as I understand, the derivation is based on the assumption that the adaptation only takes place at the last linear layer. This is clearly different from original MAML where adaptation takes place at all the layers. Also, as far as I understand, the analysis is only valid for regression problems, so I wonder how to make use of the findings to help classification problems.\n\n2. Similarly, the experimental results are done only under the synthetic environment, which limits the practical impact of this paper. Can you extend the experiment to more realistic scenario such as miniImageNet few-shot classification?\n\n3. In my opinion, the intuition behind their theoretical findings is a little bit straightforward, although understanding the phenomena is very important. For example, it is seems easy to imagine how nonzero inner-learning rate can help the shared initialization to stay robust against different task sampling. Of course it is always good to formalize such an intuition, but I just wonder how significant the importance is.\n\n[Simple questions (minor)]\n\n1. From reading the paper, I understood that how alpha=0 (ERM) can fail in Figure 1, but I do not understand why too large alpha fails as well, in terms of staying robust against the biased task sampling (the red circle). Can you provide an intuition in relation to the derivation?", "summary_of_the_paper": "This paper explores a question of how to theoretically derive a form of optimal MAML inner-learning rate and how to interpret its meaning. In order to do this, the authors assumes that the given problem is linear regression with some possibly nonlinear feature transformations. Then they derive the form of optimal MAML inner-learning rate (alpha). Further, they demonstrate that MAML with proper inner-learning rate stabilizes the meta-learning of the shared initialization, such that the shared initialization can generally minimize the distance from all the given task predictors, whereas the baseline ERM is sensitive to the density of the task distribution. The experimental results also demonstrate their derivation and intuition.", "summary_of_the_review": "The submission formalizes the MAML inner-learning rate theoretically, and it can benefit meta-learning community to some extent. However, I'm not fully convinced if the finding is practically important, or something new (in terms of intuition) as well.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "i76LrZbuHwA", "reviewer": "Reviewer_pMe3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper provides new insights into the theory of MAML. I have two main concerns/questions, which are listed below:\n\n- First, the authors assume in equation (4) that the datasets used for updating the model and validating it are the same. This is an unusual assumption to me: if you know the true label to update the model, then validating the model on it might not make sense. I appreciate it if the authors explain how much the analysis depends on this assumption and whether it can be relaxed or not.\n\n- Theorem 2 on ERM vs. MAML seems very similar to what (Collins et al., 2020) studied in their paper. I appreciate it if the authors explain how their results differ from the results of that paper. \n\n", "summary_of_the_paper": "This paper studies the MAML problem. In particular, authors consider mixed linear regression problem and provide two sets of results:\n- First, they characterize the optimal learning rate for test time, i.e., the stepsize that is used for updating the model at test time, when the number of tasks goes to infinity. More formally, they show that the optimal learning rate depends on the distribution of the feature vector. \n- Second, the authors characterize the gain obtained from MAML in comparison with ERM. The obtained bound matches with basic intuitions. For instance, it increases with the test time learning rate up to some $\\bar{\\alpha}$ and also decreases as the number of deputation steps increases. ", "summary_of_the_review": "Overall, I find the paper's attempt to shed light on the theory of MAML interesting. I have two main concerns on the test set/validation set separation and comparison with another result in the literature. I am open to raising my score based on the authors' responses.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8DdMMoZy1Dd", "reviewer": "Reviewer_iGwz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n- The paper was largely well-written.\n- The theoretical results were validated by simulations (albeit toy), even when the assumptions were slightly violated.\n\nWeaknesses\n- Missing loosely related works in meta-learning as hierarchical Bayes [A] and Bayesian linear regression with learned priors [B].\n- The large gap between the setting studied in the paper and meta-learning in practice limits my confidence in how impactful this work will be. Even works that limit adaptation to be optimizing a linear model (e.g. Raghu et al. (2020)) atttribute the success of meta-learning to representation learning; this work does not consider representation learning.\n\nQuestions\n- Can we not think of MAML in this mixed linear regression setting as learning the mean of a Gaussian prior over $w$, and the choice of $\\alpha$ as implicitly specifying the variance of the prior?\n- Why is ERM a valid algorithm to consider for mixed linear regression? How can a single $w$ possibly fit multiple tasks, e.g. consider two tasks with the same $\\Phi(X)$ but different $a$? Why not consider task-specific ERM, in which a different $w$ is fit to each task?\n- Is there any way the estimator for $\\alpha^*$ can be leveraged in a typical meta-learning experiment? E.g. with ANIL, using online estimation of the representation statistics?\n- Given the emphasis in modern empirical deep learning on activation normalization, is the derived relationship between regressor variance and $\\alpha$ practically significant? \n\nReferences\n- [A] Grant et al., Recasting gradient-based meta-learning as hierarchical Bayes, 2018, https://arxiv.org/pdf/1801.08930.pdf.\n- [B] Harrison et al., Meta-Learning Priors for Efficient Online Bayesian Regression, 2018, https://arxiv.org/abs/1807.08912", "summary_of_the_paper": "This work analyzes the model-agnostic meta-learning (MAML) algorithm in the linear regression setting. It first derives an estimator for the optimal inner-loop learning rate for one inner-loop update. The authors analyze the statistical properties of the optimal inner-loop learning rate in order to try to obtain insights applicable to settings that go beyond restrictive assumptions in the theoretical analysis, finding an inverse relationship between the estimator and regressor variance. As a second contribution, the authors analyze the geometric properties of MAML and characterize the distance between adapted parameters and true task optima, giving an expression for the deviation of this distance in expectation between MAML and empirical risk minimization (ERM). The authors validate their optimal learning rate estimator with simulations across a variety of feature mappings, and also corroborate the estimator's inverse relationship with the regressor variance.", "summary_of_the_review": "The theoretical contributions of this work are somewhat interesting but are also of dubious practical relevance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "1Iqo-9ejf_q", "reviewer": "Reviewer_ui6t", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points: \nThe paper is well structured, experiments make sense and well coordinated with the hypothesis \n\nFor the part that is hard to prove the hypothesis strictly in mathematic method, the paper put much effort to design meaningful experiments to illustrate and ‘prove’ those points \n\nThough coro1 is weak (since the reverse relation with variance of features rather than data points themselves is intractable), the authors tried to reveal it by several concrete examples (i.e. example1) and experiments. \n\nThe first result offered a method to get a better initialized value for alpha, which is valuable both in theoretical way and in practical use.\n\nWeak points \n\nSome of the results are not surprising and inspiring, lack of novelty.\n\nThe first result offered a method to get a better initialized value for alpha, which is valuable both in theoretical way and in practical use. But the latter two, i.e. the interpretation of alpha are not inspiring enough. Intuitively, alpha has relation with data(or say task) distribution. And the geometric interpretation is another way to formulate the goal of MAML. \n\n", "summary_of_the_paper": "The paper put effort to understand the adaptation learning rate alpha. It gave a principled way to estimate the optimum alpha* minimizing MAML population risk. It showed the relation between alpha* and data distribution (variance of features). It also showed that alpha in MAML, compared to ERM, helped to minimize the total distance to all the tasks’ optima.\n\n", "summary_of_the_review": "I don't think those results well pass the bar of ICLR conference. According to the above, I would suggest a weak reject (barely below the bar). PS: I am not sure if result one (find the better alpha) could be applied in practical tasks. My confidence is mostly on the theoretical part of the paper", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: After carefully reading all reviews and rebuttal, I actually think the paper provides sufficient new insight in understanding MAML that is worth being accepted. I want to thank the authors for actively engaging with the reviewers, and providing sufficient changes to the paper in order to clarify and improve its contributions. 

Theoretical results tend to be harder to judge, as they often need to happen under assumptions that make them tractable. Nevertheless they provide intuitions and understanding of the underlying principle that end up having an impact even in more realistic scenarios where these assumptions might not hold. I think this is such a scenario, and I think better understanding the relationship between ERM and approaches as meta-learning is important for the field moving forward.
Decision: Accept (Poster)