Provable Generalization of Overparameterized Meta-learning Trained with SGD
Authors: Yu Huang
Yingbin Liang
Longbo Huang
Venue: NeurIPS 2022 Accept (2022)
Keywords: MAML
generalization theory
excess risk
mixed linear regression

Abstract: Despite the empirical success of deep meta-learning, theoretical understanding of overparameterized meta-learning is still limited. This paper studies the generalization of a widely used meta-learning approach, Model-Agnostic Meta-Learning (MAML), which aims to find a good initialization for fast adaptation to new tasks. Under a mixed linear regression model, we analyze the generalization properties of MAML trained with SGD in the overparameterized regime. We provide both upper and lower bounds for the excess risk of MAML, which captures how SGD dynamics affect these generalization bounds. With such sharp characterizations, we further explore how various learning parameters impact the generalization capability of  overparameterized MAML, including explicitly identifying typical data and task distributions that can achieve diminishing generalization error with overparameterization, and characterizing the impact of adaptation learning rate on both excess risk and the early stopping time. Our theoretical findings are further validated by experiments. 

Provable Generalization of Overparameterized Meta-learning Trained with SGD
Yu Huang
Yingbin Liang Department of ECE The Ohio State University liang. 8890osu. edu
IIIS Tsinghua University
y- y-muang20@mails
wtr.allls..tssuuteeeeeeee tsinghua. edu.
Longbo Huang* III
Tsinghua University
Longbohuang@t:singuua. edu. cn
Abstract
Despite the superior empirical success of deep meta-lcarning, theoretical under- standing of overparameterized meta-learning is still limited. This paper studies the generalization of a widely used meta-lcarning approach, Model-Agnostic Meta- Learning (MAML), which aims find good initialization for fast adaptation to new tasks. Under mixed linear regression model, we analyze the general- ization properties of MAML trained with SGD in the overparameterrized regime. We provide both upper and lower bounds for the excess risk of MAML, which captures how SGD dynamics affect these generalization bounds. With such sharp characterizations, we further explore how various learning parameters impact the generalization capability overparameterized MAMI., including explicitly identi- fying typical data and task distributions that can achieve diminishing generalization error with overparameterization and characterizing the impact of adaptation learn- ing rate both excess risk and the early stopping time. Our theoretical findings are further validated by experiments.
Introduction
Meta-lcarning [22] is learning paradigm which aims to design algorithms that are capable of gaining knowledge from many previous tasks and then using improve the performance future tasks efficiently. It has exhibited great power in various machine learning applications spanning over few-shot image classification [31, 32], reinforcement learning [21] and intelligent medicine [20].
One prominent type of meta-learning approaches is an optimization-base Meta-Learning (MAML) [16], which achieves impressive results in different tasks [30, 4, 2]. The idea of MAML to learn a good initialization w", such that for new task we can adapt quickly to good task parameter starting from w MAML takes bi-level implementation: the inner-level initializes at the meta parameter and takes task-specific updates using a few steps of gradient descent (GD), and the outer-level optimizes the meta parameter across all tasks.
method, Model-Agnostic
With the superior empirical success, theoretical justifications have been provided for MAML and its variants over the past few years from both optimization [18, 38, 14, 25] and generalization perspectives [1, 11, 15, 9]. However, most existing analyses did not take overparameterizztion into
"Corresponding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

consideration, which we deem as crucial to demystify the remarkable generalization ability of deep meta-learning [41, 22]. More recently. [36] studied the MAML with overparameterized deep neural nets and derived a complexity- bound to quantify the difference between the empirical and population loss functions at their optimal solutions. However, complexity-bas generalization bounds tend to be weak in the high dimensional, especially in the overparameterizel regime. Recent works [6, 43J developed more precise bounds for overparameterized setting under a mixed linear regression model, and identified the effect of adaptation learning rate on the generalization. Yet, they considered only the simple isotropic covariance for data and tasks, and did not explicitly capture how the generalization performance of MAML depends on the data and task distributions. Therefore, the following important problem still remains largely open:
Can overparameterized MAML generalize well to new task, under general data and task distributions?
In this work, we utilize the mixed linear regression, which is widely adopted in theoretical studies for meta-learning [27. 6, 12, 3], as a proxy to address the above question. In particular, we assume that each task 5 is noisy linear regression and the associated weight vector is sampled from common distribution. Under this model, we consider one-step MAML meta-trained with stochastic gradient descent (SGD), where we minimize the loss evaluated at single GD step further ahead for each task. Such settings correspond to real-world implementations of MAML [17, 28, 22] and are extensively considered in theoretical analysis [14, 8, 15]. The focus of this work is the overparameterized regime, i.e., the data dimension d is far larger than the meta-training iterations T (d >> T).
1.1 Our Contributions
Our goal is to characterize the generalization behaviours of the MAML output in the overparameter- ized regime, and to explore how different problem parameters, such as data and task distributions, the adaptation learning rate 3", affect the test error. The main contributions are highlighted below.
Our first contribution is a sharp characterization (both upper and lower bounds) of the excess risk of MAML trained by SGD. The results are presented in general manner, which depend on a new notion of effective meta weight, data spectrum, task covariance matrix, and other hyperparameters such as training and test learning rates. In particular, the effective meta weight captures an essential property of MAML, where the inner-loop gradient updates have distinctive effects on different dimensions of data eigenspace, i.e., the importance of "leading" space will be magnified whereas the "tail" space will be suppressed.
We investigate the influence of data and task distributions the excess risk of MAML. For log-decay data spectrum, our upper and lower bounds establish a sharp phase transition of the generalization. Namely, the excess risk vanishes for large T (where benign fitting occurs) if the data spectrum decay rate is faster than the task diversity rate, and non-vanishing risk occurs otherwise. In contrast, for polynomial or exponential data spectrum decays, excess risk always vanishes for large T irrespective of the task diversity spectrum.
We showcase the important role the adaptation learning rate 5"r plays in the excess risk and the early stopping time of MAML. We provably identify a novel tradeoff between the different impacts of 3 on the "leading" and "tail" data spectrum spaces as the main reason behind the phenomena that the excess risk will first increase then decrease as 1 changes from negative to positive values under general data settings. This complements the explanation based only on the "leading" data spectrum space given in [6] for the isotropic case. We further theoretically illustrate that 3rr plays a similar role in determining the early stopping time, i.e., the iteration at which MAML achieves steady generalization error.
Notations. We will use bold lowercase and capital letters for vectors and matrices respectively. N (0, denotes the Gaussian distribution with mean 0 and variance x², We use f(z) S g(x) to denote the case f(x) < cg(x)) for some constant e 0. We use the standard big-O notation and its variants: ((-), where T is the problem parameter that becomes large. Occasionally, we use the symbol (-)) to hide polylog(T') factors. 1(.) denotes the indicator function. Let - max (z, 0}.

---

2 Related Work
Optimization theory for MAML-type approaches Theoretical guarantee of MAML was initially provided in [17] by proving a universal approximation property under certain conditions. One line of theoretical works have focused on the optimization perspective. [14] established the convergence guarantee of one-step MAML for general nonconvex functions, and [25] extended such results to the multi-step setting. [18] analyzed the regret bound for online MAML. [38, 36] studied the global optimality of MAML with sufficiently wide deep neural nets (DNN). Recently, [10] studied MAML from a representation point of view, and showed that MAML can provably recover the ground-truth
subspace.
Statistical theory for MAML-type approaches. One line of theoretical analyses lie in the statistical aspect. [15] studied the generalization of MAML on recurring and unseen tasks. Information theory-type generalization bounds for MAML were developed in [26, 9]. [8] characterized the gap of generalization eπтоr between MAML and Bayes MAML. [36] provided the statistical error bound for MAML with overparameterized DNN. Our work falls into this category, where the overparameterization has been rarely considered in previous works. Note that [36] only derived the generalization bound from the complexity based perspective to study the difference between the empirical and population losses for the obtained optimization solutions. Such complexity bound is typically related to the data dimension [29] and may yield vacuous bound in the high dimensional regime. However, our work show that the generalization error of MAML can be small even the data dimension is sufficiently large.
Overparamterized meta-learning. [13, 34] studied overparameterized meta-learning from a repre- sentation learning perspective. The most relevant papers our work are [43, 6], where they derived the population risk in overparameterized settings to show the effect of the adaptation learning rate for MAML. Our analysis differs from these works from two essential perspectives: i). we analyze the excess risk of MAML based on the optimization trajectory of SGD in non-asymptotic regime, highlighting the dependence of iterations T, while they directly solved the MAML objective asymp- totically; ii). [43, 6] mainly focused on the simple isotropic case for data and task covariance, while we explicitly explore the role of data and task distributions under general settings.
Overparameterized linear model. There has been several recent progress in theoretical under- standing of overparameterized linear model under different scenarios, where the main goal is to provide non-asymptotic generalization guarantees, such as studies of linear regression [5]. ridge regression [35], constant-stepsize SGD [42], decaying-stepsize SGD [39], GD [40], Gaussian Mixture models [37]. This paper aims to derive the non-asymptotic excess risk bound for MAML under mixed linear model, which can be independent of data dimension d and still converge as the iteration T enlarges.
3 Preliminary
3.1 Meta Learning Formulation
In this work, we consider standard meta-learning setting [15], where number of tasks share some similarities, and the learner aims to find a good model prior by leveraging task similarities, so that the leamner can quickly find desirable model for new task by adapting from such an initial prior.
Learning proper initialization. Suppose we are given collection of tasks {TeTT= sam- pled from some distribution T. For each task Tt, we observe N samples D, A (X,, = i.idd Po. (x))))(xx), where di is the model parameter for the 1-th
(i.) E Rd task. The collection of (De)T= is denoted as D. Suppose that D, is randomly split into training and validation sets, denoted respectively as Din & (Xin y!!) and Dout & (XQ"", y correspondingly containing 1h and nt samples (i.e., N M2 + n22). We let w RR denote the initialization variable. Each task Ti applies an inner algorithm A with such an initial and obtains an output A(w; D. Thus, the adaptation performance of w for task T can be measured by the mean squared loss over the validation set given by E(A(w:; ; = 20n En ((xP)) A(w; Dir)) - =
JE[NN
2 The goal of meta-learning is to find an optimal initialization W Rd by minimizing the following empirical
3

---

meta- teta-training loss:
T
min 2(A, W) where [(A,w; WA,,; - I (((ww D. WER
-
(I)
In the testing process, suppose new task sampled from 7 is given, which is associated with the dataset Z consisting of points with the task. We apply the learned initial 3 as well as the inner algorithm A on Z to produce task predictor. Then the test performance can be evaluated via the following population loss:
[(A,w) = TB
[e (A(w; 2) (x, v))l
(2)
Inner Loop with one-step GD. Our focus this paper is the popular meta-learning algorithm MAML [16], where inner stage takes few steps of GD update initialized from We consider one step for simplicity, which is commonly adopted in the previous studies [6, 10, 19]. Formally, for any
E IRd, and any dataset (X, with samples, the inner loop algorithm for MAML with learning
rate /3 is given by
== w NVw (w: (X, (X, = (I - _ X) X
Alw; (X,))) :=
(3)
We allow the learning rate differ at the meta- trainin and testing stages, denoted as 8 and f respectively. Moreover, in subsequent analysis, we will include the dependence on the learning rate to the inner loop algorithm and loss functions as A(w, B3 (X,))) [(A, w, 9; D) and ((,,w,))
Outer Loop with SGD. We adopt SGD to iteratively update the meta initialization variable based on the empirical meta-training loss eq. (1), which how MAML is implemented in practice [17]. Specifically, the constant stepsize SGD with iterative averaging [15, 12, 11], and the algorithm summarized in Algorithm 1. Note that at each iteration, we use one task for updating the meta parameter, which can be easily generalized to the case with mini-batch tasks for each iteration.
Algorithm MAML with SGD
Input: Stepsize 0, meta learning rate f Initialization:
for 1 to do
Receive task 7. with data D,
Randomly divided into training and validation set: Din = (X Dout (Xqut youl)
Update Wi+1 Wi (VA((W 8hh end for
return W.
$ ETO W.
Meta Excess Risk of SGD. Let wn denote the optimal solution the population meta-test error eq. (2). We define the following excess risk for the output wy of SGD:
R(Wr, (*)) A E [C(A,,r - L(A, .
(4)
which identifies the difference between adapting from the SGD output Wy and from the optimal initialization w". Assuming that each task contains fixed constant number of samples, the total number of samples over all tasks is OTT). Hence, the overparameterized regime can be identified as > T, which is the focus this paper, and is in contrast the well studied underparameterizze setting with finite dimension d (d < T). The goal of this work is to characterize the impact of SGD dynamics, demonstrating how the iteration T affects the excess risk, which has not been considered in the previous overparameterized MAMI. analysis [6, 43].
3.2 Task and Data Distributions
To gain more explicit knowledge of MAML, specify the task and data distributions in this section.

---

Mixed Linear Regression. We consider a canonical case in which the tasks are linear regressions. This setting has been commonly adopted recently in [6, 3, 27]. Given task T, its model parameter is determined by 0 E IR. and the output response is generated as follows:
y = 00x x + 2,
Px P2
(5)
where is the input feature, which follows the same distribution Px across different tasks, and is the i..d. Gaussian noise sampled from (0,, a²). ). The task signal 0 has the mean 0* and the covariance Eg _ E[eeT] Denote the distribution of as Pe. We do not make any additional assumptions on Pe. whereas recent studies MAML [6, 43] assume it to be Gaussian and isotropic.
Data distribution. For the data distribution Px, we first introduce some mild regularity conditions:
1. x E Rd is mean zero with covariance operator E = E[xx T]
2. The spectral decomposition of Σ is VAVT Eiso \vaey with decreasing eigenvalues Aa 0, and suppose Σ Ei>o A 20. 3. Σ 1x Tx -ussusGaunia
To analyze the stochastic approximation method SGD, we take the following standard fourth moment condition [42, 24,7 7].
Assumption (Fourth moment condition). There exist positive constants c1, bi >> O, such that for any positive semidefinite (PSD) matrix A, it holds that
by aar(EA)) + EAE = Ex-P, [xx Axx = tr(EA)E
For the Gaussian distribution, suffices to take ei 3,
3.3 Connection Meta Least Square Problem.
After instantiating study the task and data distributions in the last section, note that VE(A(w, 3"; D;r); Di is linear with respect to w. Hence, we can reformulate the problem eq. (1) as least square (LS) problem with transformed meta inputs and output responses.
Proposition 1 (Meta LS Problem). Under the mixed linear regression model, the expectation of the meta-tran eeta-training loss eq. (1) taken over task and data distributions can be rewritten as:
E
C( B":
; D) = -L(A (.A.w,15)) 130) ) = EB.T
1 | --1²
(6)
The meta data given by
B
1
X out
I
gor
x
th x!1)
VT2
oul
I
X
x
0
gr 2 out
X our T z
n1
n1
where i E Ra xd
2 E R , oow E Roaxd and zuu
R denote the inputs and noise for
training and validation. Furthermore,wer we huve
B0" + with meta noise EEG
B = 0.
(8)
Therefore, the meta-training objective is equivalent to searching for a w, which close to the task mean 0". Moreover, with the specified data and task model, the optimal solution for meta-test loss eq. (2) can be directly calculated [19], and we obtain w = [[(] = 0*. Hence, the meta excess risk eq. (4) is identical to the standard excess risk [5] for the linear model eq. (8), i.c.
R(Wr, )² = 1 [BoT - > |BO - >1 but with more complicated input and output data expressions. The following analysis will focus on this transformed linear model.
Furthermore, we can calculate the statistical properties of the reformed input B, and obtain the meta-covariance:
B B = -I
3"
+
F
3
n1
5

---

where F E[xx' T Σxx
Let X
E Raxd denote the collection of i..d. samples from Px, and
denote
8² B X XXXXX 2 x) = (1- + -F =²).
Ha. = B[[[
We can then write BB B] H Regarding the form of B and Ha,, we need some further conditions the higher order moments of the data distribution.
T
Assumption 2 (Commutity). F [xxx' Σxx
commutes with the data covariance E.
Assumption holds for Gaussian data. Such commutity of Σ has also been considered in [42].
Assumption 3 (Higher order moment condition). Given [3] < 1 and E. there exists constant C(3, Σ) 0. for large
X1
for any unit vector E Rd we have:
_ _x X < < <(B,E))
Bill
(9)
n
In Assumption 3, the analytical form of CB3, Σ) can be derived if Σ x is Gaussian. Moreover, if Further technical discussions are presented in Appendix.
0, then we obtain C(3, Σ)
Main Results
In this section, we present our analyses on generalization properties MAML optimized by average SGD and derive insights on the effect of various parameters. Specifically, our results consist of three parts. First, we characterize the meta excess risk of MAML trained with SGD. Then, we establish the generalization error bound for various types of data and task distributions, to reveal which kind of overparameterizatioo regarding data and task is essential for diminishing meta excess risk. Finally, we explore how the adaptation learning rate 3or affects the excess risk and the training dynamics.
4.1 Performance Bounds
Before starting our results, we first introduce relevant notations and concepts. We define the following rates of interest (See Remark for further discussions)
c(3, = c1 + 8| 1 /C
Ejo 6A tr("")
f(3, Eg) = c(3, tr (E + 40 o /C3, tr()) o 93,n,, E, Eg) : 0² + b, tr HnH,,, 1 lggobi tr /r(E))/n.
Moreover, for a positive semi-definite matrix H, s.t. H and E can be diagonalized simultaneously, let 14: (H) denote its corresponding eigenvalues for v., i.e. (.(())v (Recall v; is the i-th eigenvector of Σ)
We next introduce the following new notion the effective meta weight, which will serve as an important quantity for capturing the generalization of MAML.
Definition 1 (Effective Meta Weights). For 1,8T 1,10 < 1/>1, given step size a and iteration T, define
Ui (H,, (T (H,,H,))))) E, (Ta? )/4, (Hm,
M (H,, (Ho),8*)
(10)
14 (H (
We call ( (00,,a)) (Hn),go) and (H,, )4 (H),,r)) the meta ratio (See Remark 2).
We omit the arguments of the effective meta weight E, for simplicity in the following analysis.
Our first results characterize matching upper and lower bounds on the meta excess risk of MAML in terms of the effective meta weight.
Theorem 1 (Upper Bound). Let wl; (wo 0" v.). 1f 13 < 1/>1, is large ensuring that He (H (H > O, Vi and a < 1/ (o(3", ()(r))) then the meta excess risk R(W., ) is bounded above as follows
R(WT, ,8t)
Bias Var

---

where
2
W
Bias
3
T²T
14 9")
Var
2
Σ
(1- ac(3"r Σ) Ertr( (E))
1 (H 1,022 at Taju(H,, (H,,, + (H oo)))
x x(( 12,,0 a, Do, Σ) 20(8", Σ)
Awof)
V/2
Remark The primary error source of the upper bound are two folds. The bias term corresponds to the error if we directly implement GD updates towards the meta objective eq. (6). The variance error composed the disturbance of meta noise (the V1 term), and the randomness of SGD itself (the V2 term). Regardless of data or task distributions, for proper stepsize a, we can easily derive that the bias term is ( and the 222 term also O which dominated by V1 term (1((1). Hence, to achieve the vanishing risk, need to understand the roles of E, and f(-)
Remark 2 (Effective Meta Weights). By Definition 1, separate the data eigenspace into "leading" (2 oT and "tail" (< a spectrum spaces with different meta weights. The meta ratios indicate the impact of one-step gradient update. For large n,, f4: (Hn, ~ (1 3A,)² A; and hence a larger 3 in training will increase the weight for "leading" space and decrease the weight for "tail" space, while larger 8 always decreases the weight.
Remark 3 (Role of f(-)). f(-) in variance term consists of various sources of meta noise &, including inner gradient updates (3), task diversity (Eg) and noise from regression tasks (ar). As mentioned in Remark 1, understanding f(.) is critical in our analysis. Yet, due to the multiple randomness origins, techniques for classic linear regression [42, 24] cannot directly applied here. Our analysis overcomes such non-trivial challenges. 5(-) in Theorem 2 plays similar role to s(-).
Therefore, Theorem implies that overparametterizaioo is crucial for diminishing risk under the following conditions:
For f()): tr(EE,) and tr(=²) is small compared to T;
For E5; the dimension of "leading" space is o(T), and the summation of meta ratio over "tail" space o( +
We next provide a lower bound on the meta excess risk, which matches the upper bound in order.
Theorem (Lower Bound), Following the similar notations in Theorem Then
2T R(WT, 8*)
1
Σ
E
1
Σ
14
112
D (r(
x 000 g(8",
9
n1, E, Ea)= +
1000 Σ
Mi(H
. )2 at
1 (H sn) a Nwol.
Taja (Hny,
Our lower bound can also be decomposed into bias and variance terms as the upper bound. The bias term well matches the upper bound up absolute constants. The variance term differs from the upper bound only by n. where ny is the batch size of each task, and is treated as a constant (i.e., does not scale with 7) [23, 33] in practice. Hence, in the overparameterized regime where d > T and T tends be sufficiently large, the variance term also matches that in the upper bound w.r.t. T.
4.2 The Effects of Task Diversity
From Theorem and Theorem 2, we observe that the task diversity Ee f-) and g(-) plays a crucial role in the performance guarantees for MAML. In this section, explore several types of data distributions to further characterize the effects of the task diversity.
We take the single task setting as comparison with meta-learning, where the task diversity diminishes (tentatively say Eg -> 0), i.e., each task parameter = 0² such case, is unnecessary to do one-step gradient in the inner loop and set f 0, which is equivalent to directly running
7

---

SGD. Formally, the single task setting can be described as outputting wi with iterative SGD that minimizes L(AA, 0; D) with meta linear model 7
(X 0" 20
Theorem 1 implies that the data spectrum should decay fast, which leads small dimension of "leading" space and small meta ratio summation over "tail" space. Let us first consider a relatively slow decaying case: A = kー log P(k + 1) for some > 1. Applying Theorem I, we immediately derive the theoretical guarantees for single task:
Lemma 1 (Single Task). If |f < x and if the spectrum of E satisfies N = k- -looo P(k + 1), then R(w (r)) O log"
At the test stage, if set S then the meta excess risk for the single task setting, i.e., R(w 0). is exactly the excess risk in classical linear regression [42]. Lemma can be regarded as generalized version of Corollary 2.3 [42], where they provide the upper bound for R(wss"" 0), while we allow a one-step fine-tuning for testing.
Lemma suggests that the log-decay sufficient assure that R(w 0) is diminishing when d > T. However, in meta-learning with multi-tasks the task diversity captured by the task spectral distribution can highly affect the meta excess risk. In the following, our Theorem and Theorem (i.e., upper and lower bounds) establish sharp phase transition of the generalization for MAML for the same data spectrum considered in Lemma 1, which is in contrast to the single task setting (see Lemma 1), where log oeg-decay data spectrum always yields vanishing excess risk.
Proposition 2 (MAML, log- Decay Data Spectrum), Given 1 1 < X under the same data distribution as Lemma and the spectrum of Eg, denoted as V4, satisfies vix log' (k + 1) for some > O, then
(1lgg r- 2pt1 (P) RiwT, 8*) = -00 log" #11)+(T) (T)
2 2p 2p
Proposition 2 implies that under log-decay data spectrum parameterized by p. the meta excess risk of MAML experiences phase transition determined by the spectrum parameter Since large implies large eigenvalues and high variations for task vectors, we adopt measure the diversity of task distributions, and call r as the task diversity in the sequel. While slower task diversity rate r < 2p guarantees vanishing excess risk, faster task diversity rate 2 2p- - necessarily results in vanisinig excess risk. Proposition 2 and Lemma together indicate that while log-decay data spectrum always yields benign fitting (vanishing risk) the single task setting, can yield non-vanishing risk in meta learning due to fast task diversity rate.
We further validate our thcoretical results in Proposition by experiments. We consider the case 2. As shown in Figure la, when r < 2p 1, the test error quickly converges to the Bayes error When 2p- 1, Figure 1b illustrates that MAML already converges on the training samples, but the test error (which is further zoomed in Figure Ic) levels off and does not vanish, showing MAML generalizes poorly when 2p-
6930
Boyes
Bayes
1.3
Teai
Train
Risk
049)
Dayes
Test
1.2
6490
110
1.4
250
300
2.0
250
300
30
100
Iteration
Dteration T
Iteratoon
(a) 84 0.25 log 1.5 (1+1)
(b) v: = 0.25 0.25llog (1 11
(c) v; = 0.25 log (1 1)
Figure 1: The effects of task diversity. 500, = 300, A
(log(++)) 3"h 0.02, f 0.2.
Furthermore, we show that the above phase transition that occurs for log-decay data distributions no longer exists for data distributions with faster decaying spectrum.

---

Proposition 3 (MAML, Fast-Decar Data Spectrum). Under the same task distribution as in Proposi- tion 2, i.e. the spectrum of Σg, denoted vi, satisfies uy log' (k: 1) O1) (0(1)for for some > 0, and the data distribution satisfies:
1. Ae= = 9 for some 1, R(WT" 3t0) = = T
and R(WT, 0
T
2. A ek R( , = +++) and R(WT, 0(+)
4.3 On the Role of Adaptation Learning Rate
The analysis in [6] suggests a surprising observation that negative learning rate (i.e., when S takes a negative value) optimizes the generalization for MAML under mixed linear regression models. Their results indicate that the testing risk initially increases and then decreases as 8 varies from negative positive values around zero for Gaussian isotropic input data and tasks. Our following proposition supports such trend, but with a novel tradeoff in SGD dynamics as new reason for the trend, under more general data distributions. Denote w/ the average SGD solution of MAML after T iterations that uses 3 as the inner loop learning rate.
Proposition 4. Let Tlog P(T)) and d = T log"(T)) where p. q >> 0. Suppose Px is Gaussian and the spectrum of Σ satisfies
[188,
kS8
A
1/(dd s)) 8);
8+ ++1sks d.
Suppose the spectral parameter of Eg is O()), and let the step size a 20( tn)) large ni, 18"7,1884 +,, we have
Then for
R(wT T (8)) 50 (T) (1- B"r1) + O (Tog((T)) AnAA)) + +
(1I)
The first two terms in the bound of eq. (11) correspond to the impact of effective meta weights E, on the "leading" and "tail" spaces, respectively, as we discuss in Remark 2. Clearly, the learning rate 8 plays a tradeoff role in these two terms, particularly when is close to q. This explains the fact that the test error first increases and then decreases as 5" varies from negative positive values trend of the
around zero. Such a tradeoff also serves as the reason for the firs-increase-then-deeee test error under more general data distributions as we demonstrate in Figure 2. This complements the reason suggested in [6], which captures only the quadratic form where there exists only the "leading" space without "tail" space.
AA) of f for isotropic Σ,
8.0
Rivk
8:7
6:56
035
035
ger
-035
4.50
-25
g
308
155
ger
(a) A; 10g
(b) X 3log(s+1)
(c) A
Figure R(w ( as function of 8hh d 200. T 100. Eg 0.8" I, g 0.2.
Based on the above results, incorporating with our dynamics analysis, we surprisingly find that 8 not only affects the final risk, but also plays pivot role towards the early iteration that the testing error tends to be steady. To formally study such a property, we define the stopping time as follows.
Definition (Stopping time). Given , for any e > 0, the corresponding stopping time l (3 (89) is defined as: (,th 8tth mint s.t. R(w,"" 10t) <

---

In the sequel, we may omit the arguments in t. for simplicity. We consider the similar data distribution in Proposition 4 but parameterized by K, i.e., = K log-"(K) and d = K log" (K), where p, / > 0. Then we can derive the following characterization for t..
Corollary 1. If the assumptions Proposition 4 hold and p = 9. Further, let Eo I,' and | < X1 Then for (B" ,89) E (s, K}, we have:
L.
Ee
L
Le(1 -10--""aal Aa> Stc
exp
(1
3 11
S exp (E
U1
+ U²(1 - 3" >m))) $1
(12)
(1 - 30r
where L1, Le Ug U. > 0 are factors for "leading" and "tail" spaces that are independent of K
Equation (12) suggests that the early stopping time t. is also controlled by the tradcoff role that S plays in the "leading" (U₁, L2) and "tail" spaces (U,, L,), which takes similar form as the bound in Proposition Therefore, the trend for t, in terms of 5 will exhibit similar behaviours as the final excess risk, and hence the optimal 3 for the final excess risk will lead to an earliest stopping time. We plot the training and test errors for different 5"rh in Figure 3, under the same data distributions as Figure 2a to validate our theoretical findings. As shown in Figure 3a, 8 does not make much difference in the training stage (the process converges for all 3" when T is larger than 100), However, in Figure 3b at test stage, 3rth significantly affects the iteration when the test error starts to become relatively flat. Such an early stopping time first increases then decreases as 3r varies from -0.5 to 0.7, which resembles the change of final excess risk in Figure 2a.
30
42
20
Soy
105
Beration T
Herdioon
(a) Training Risk
(b) Test Error
Figure 3: Training and test curves for different 3r. d = 500, A ilog (1+1)
Eo
0.82 d
3, = =0.2.
Conclusions
In this work, we give the theoretical treatment towards the generalization property of MAML based on their optimization trajectory in non-asymptotic and overparameterized regime. We provide both upper and lower bounds on the excess risk of MAML trained with average SGD. Furthermore, we explore which type of data and task distributions are crucial for diminishing error with overparameterization. and discover the influence of adaption learning rate both on the generalization error and the dynamics, which brings novel insights towards the distinct effects of MAML's one-step gradient updates on "leading" and "tail" parts of data eigenspace.
Acknowledgments and Disclosure of Funding
The work of Yu Huang and Longbo Huang supported part by the Technology and Innovation Major Project of the Ministry of Science and Technology of China under Grant 2020AAA01084000 and AUZ0AAA010SAN Precision Medicine Foundation 10001020109 09. The work of Y. Liang was supported in part by the U.S. National Science Foundation under the grant 2134111
the Tsinghua University Initiative Scientific Research Program, and Tsinghua
2 Such terms have been suppressed for clarity. Details are presented in the appendix.
10

---

References
[1] Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended pac-bayes theory. In International Conference Machine Learning, pages 204-214. PMLR, 2018.
[2] Antreas Antoniou, Harrison Edwards, and Amos Storkey. How to train your maml. arXiv preprint arXiv: 1810.095020 2018.
[3] Yu Bai, Minshuo Chen, Pan Zhou, Tuo Zhao, Jason Lec, Sham Kakade, Huan Wang, and Caiming Xiong. How important is the train-validation split in meta-learning? In International Conference on Machine Learning, pages 543-553, PMLR, 2021.
[4] Yujia Bao, Menghua Wu, Shiyu Chang, and Regina Barzilay. Few-shot text classification with distributional signatures. arXiv preprint arXiv: l9X8v:/908,00 11990000099 2019.
[5] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30033-30777 2020.
[6] Alberto Bernacchia. Meta-learning with negative learning rates. In ICLR, 2021.
[7] Raphaël Berthier, Francis Bach, and Pierre Gaillard. Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model. Advances in Neural Information Processing Systems, 33:2576-2586, 2020.
[8] Lisha Chen and Tianyi Chen. Is bayesian model-agnostic meta learning better than model- agnostic meta learning, provably? In International Conference on Artificial Intelligence and Statistics, pages 1733-1774. PMLR, 2022.
[9] Qi Chen, Changjian Shui, and Mario Marchand. Generalization bounds for meta-learning: An information-theoreti analysis. Advances in Neural Information Processing Systems, 34, 2021.
[10] Liam Collins, Aryan Mokhtari, Sewoong Oh, and Sanjay Shakkottai. Maml and anil provably learn representations. arXiv preprint arXiv:2202.033: 03222333..333, 2022.
[11] Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-lenn stochastic gradient descent with biased regularization. In International Conference on Machine Learning, pages 1566-1575. PMLR, 2019.
[12] Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Learning to learn
around a common mean. Advances in Neural Information Processing Systems, 31, 2018.
[13] Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:2002.00 09434, 2020.
[14] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. On the convergence theory of gradient- based model-agnostic meta-learning algorithms. In International Conference on Artificial Intelligence and Statistics, pages 1082-1092. PMLR, 2020.
[15] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Generalization of model-agnostic meta- learning algorithms: Recurring and unseen tasks. Advances in Neural Information Processing Systems, 34, 2021.
[16] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. In International conference machine learning, pages 1126-1135. 1135. PMLR, 2017.
[17] Chelsea Finn and Sergey Levine. Meta-learning and universality: Deep representations and gradient descent can approximate any learning algorithm. arXiv preprint 111.1:17 2017.
[18) Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-learning. In International Conference Machine Learning, pages 1920-1930. PMLR, 2019.
11

---

[19] Katelyn Gao and Ozan Sener. Modeling and optimization trade-off in meta-learning. Advances in Neural Information Processing Systems, 33:11154-11163 2020.
[20] Jiatao Gu, Yong Wang, Yun Chen, Kyunghyun Cho, and Victor OK Li. Meta-learning for low-resource neural machine translation. arXiv preprint arXiv:/808,00 08437, 2018.
[21] Abhishek Gupta, Russell Mendonca, YuXuan Liu, Pieter Abbeel, and Sergey Levine. Meta- reinforcement learning of structured exploration strategies. Advances in neural information processing systems, 31, 2018.
[22] Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey. Meta-learning in neural networks: A survey. arXiv preprint arXiv:2004. 05439, 2020.
[23] Prateck Jain, Sham Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Paral- lelizing stochastic gradient descent for least squares regression: mini-batching averaging, and model misspecification. Journal of Machine Learning Research, 18, 2018.
[24] Prateek Jain, Sham M Kakade, Rahul Kidambi, Praneeth Netrapalli, Venkata Krishna Pillutla, and Aaron Sidford. A markov chain theory approach to characterizing the minimax optimality of stochastic gradient descent (for least squares). arXiv preprint 1rXiv:1710.09430, 2017.
[25] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Multi-step model-agnostic meta-Icarning: Conver- gence and improved algorithms. 2020.
[26] Sharu Theresa Jose and Osvaldo Simeone. Information-theorrtic generalization bounds for meta-learning and applications. Entropy, 23(1):126, 2021.
[27] Weihao Kong, Raghav Somani, Zhao Song, Sham Kakade, and Sewoong Oh. Meta-learning for mixed linear regression. In International Conference on Machine Learning, pages 5394-5404, PMLR, 2020.
[28] Zhenguo Li, Fengwei Zhou, Fei Chen, and Hang Li. Meta-sgd: Learning to learn quickly for few-shot learning, arXiv preprint arXiv:1707.0966 2017.
[29] Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of over-parametrization in generalization of neural networks. arXiv preprint arXiv: 12076, 2018
[30] Abiola Obamuyide and Andreas Vlachos. Model-agnostic meta-learning for relation classifica- tion with limited supervision. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5873 5879, 2019.
[31] Mengye Ren, Eleni Triantafillou, Sachin Ravi, Jake Snell, Kevin Swersky, Joshua B Tenen- baum, Hugo Larochelle, and Richard S Zemel. Meta-leamnin for semi-supervised few-shot classification. arXiv preprint 18X3v:800300061 2018.
[32] Andrei A Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu, Simon Osindero, and Raia Hadsell. Meta-learning with latent embedding optimization. arXiv preprini 18X 2018.
[33] Shai Shalev-Shwart and Tong Zhang. Accelerated mini-batch stochastic dual coordinate ascent. Advances in Neural Information Processing Systems, 26, 2013.
[34] Yue Sun, Adhyyan Narang, Ibrahim Gulluk, Samet Oymak, and Maryam Fazel. Towards sample-efficient overparameterized meta-learning Advances in Neural Information Processing Systems, 34, 2021.
[35] Alexander Tsigler and Peter I. Bartlett. Benign overfitting in ridge regression. arXiv preprint arXiv:2009. 14286, 2020.
[36] Haoxiang Wang, Ruoyu Sun, and Bo Li. Global convergence and induced kernels of gradient- based meta-learning with neural nets. arXiv preprint 200.::20000..64006 2020.
12

---

[37] Ke Wang and Christos Thrampoulidis. Benign overfitting in binary classification of gaussian mixtures. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4030-4034. IEEE, 2021.
[38] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. On the global optimality of model- agnostic meta-learning. In International conference on machine learning, pages 9837-9846. PMLR, 2020.
[39] Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham M Kakade. Last iterate risk bounds of sgd with decaying stepsize for overparameterized linear regression. arXiv preprint arXiv:2 10.00//1 98, 2021.
[40] Jing Xu, Jiaye Teng, and Andrew Chi-Chih Yao. Relaxing the feature covariance assumption: Time-variant bounds for benign overfitting linear regression. arXiv preprint 2rXxv22002.00054, 2022.
[41] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
[42] Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Benign overfitting of constant-stepsize sgd for linear regression. In Conference Learning Theory, pages 4633-4635. PMLR, 2021.
[43] Yingtian Zou, Fusheng Liu, and Qianxiao Li. Unraveling model-agnostic meta-leariin via the adaptation learning rate. In International Conference on Learning Representations, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethies review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
13

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "zHxwY6_3hCJ", "reviewer": "Reviewer_9gwj", "summary": "This paper investigated the provable generalization performance of overparameterized MAML. In particular, the authors focus on the mixed linear regression model and a one-step meta-training process with stochastic gradient descent (SGD). Theoretically, they give both upper and lower bounds on the excess risk of meta-learning trained with SGD. Furthermore, they explore the affect of task/data distributions and adaptation learning rate.\n\nOverall, this paper provides some theoretical evidences to understand the effects of MAML trained with SGD. The main concern to me is the novelty and significance of the theoretical results. Due to the fact that most of the results have been known, I think this paper is interesting but not so surprising.", "questions": "I hope the authors can clarify some of my concerns. But if I am wrong, please correct me.", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1.  This paper is clearly written and easy to follow.\n2.  The proofs of the main results are complete.\n3.  MAML is a popular meta-learning method and theoretical analysis on it is also important to the ML community.\n\n**Weaknesses**\n1. The main concern to me is the novelty of this paper. The analysis of generalization performance of MAML based on SGD has been investigated by Chen et al., 2020 and Fallah et al., 2021, who also give generalization bounds for MAML which show the convergency rate of $\\mathcal{O}(\\frac{1}{T})$ and $\\mathcal{O}(\\frac{1}{Tn})$, respectively. Besides, their results are more general than this work because the previous work do not relay on a specific case of mixed linear regression. I think the author should compare and discuss in details with the previous results on MAML trained with SGD. In terms of MAML for linear regression, Collins et al., 2020 have analyzed that the performance of MAML can outperform ERM, which is a much stronger result to me.\n\n2. Another concern to me is the definition of task diversity rate $r$ in the analysis of the affect of task diversity. I can not found its formal definition in the main pages. I wonder how it can measure or represent the diversity the task distribution. \n\n3. For the significance of this paper, I noticed that most of the results are intuitive or have been proven in the literature. I think a good theory paper should give new insights for people or can guide some practical algorithms for improvement.\n\n4. Can the results be generalized to other machine learning methods beyond the linear regression, such as neural networks?\n\nChen et al., A Closer Look at the Training Strategy for Modern Meta-Learning, NeurIPS 2020  \nFallah et al., Generalization of Model-Agnostic Meta-Learning Algorithms: Recurring and Unseen Tasks, NeurIPS 2021  \nCollins et al., Why Does MAML Outperform ERM? An Optimization Perspective, ArXiv 2020   ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "yROT8V-84Vo", "reviewer": "Reviewer_T2R8", "summary": "The paper introduces a generalization bound of MAML in more complex linear regression tasks in the over-parametrized regime. Their main theoretical results upper and lower bounds the excess risk while linking it to input data as well as task distribution, outer loop length and inner loop learning rate. Theoretical results are supported by experiments. ", "questions": "See above. \n\n1. How exactly does the theory generalise to the meta-batch setting. \n2. I might have missed this but why do you have to use the iterative averaging instead of using the final w_T?\n3. Can you comment on how to extend the theory for longer inner loops.  \n", "limitations": "The authors do not explicitly discuss the limitations of their work, although I agree that this is not needed here.  ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written, relaxes common assumptions and therefore generalizes existing bounds. I am not familiar with the theoretical literature in meta-learning but I found the paper very nice to study, although I did not validate the correctness of the theoretical results thoroughly. The math in the paper is quite dense but I think the authors do a nice job presenting the results. Overall, I think the paper is of value to the (meta-learning) community at NeurIPS and I propose acceptance. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "vdFYgs_PIc", "reviewer": "Reviewer_uDLS", "summary": "The authors study the overparameterization behavior in the Model-Agnostic Meta-Learning (MAML) framework. They find lower and upper bounds of the risk of MAML trained with SGD. They show that for a large number of meta-training iterations the excess risk vanishes. They also show the effects of early stopping and adaptation learning rate on excess risk.", "questions": "None", "limitations": "There are no limitations with regards to negative societal impacts.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is very well written and organized. Following it was straightforward.\n2. The authors use some settings which correspond to real world applications (L46)\n3. The authors derive explicit formulas for bias and variance which bound the excess risk above. Additionally, they derive a lower bound on the excess risk. \n4. The leading and tail spectrum space analysis is very interesting and well developed.\n\nWeaknesses:\n1. Focusing on mixed linear regression is the right move to do when studying these theoretical properties. However, there is a drawback: people don’t really use linear regression for meta learning in practice. The authors are thus not doing anything wrong but this work is weak in practicality. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept