Generalization of Model-Agnostic Meta-Learning Algorithms: Recurring and Unseen Tasks
Authors: Alireza Fallah
Aryan Mokhtari
Asuman E. Ozdaglar
Venue: NeurIPS 2021 Poster (2021)
Keywords: meta-learning theory
generalization bounds
algorithmic stability
convex optimization

Abstract: In this paper, we study the generalization properties of Model-Agnostic Meta-Learning (MAML) algorithms for supervised learning problems. We focus on the setting in which we train the MAML model over $m$ tasks, each with $n$ data points, and characterize its generalization error from two points of view: First, we assume the new task at test time is one of the training tasks, and we show that, for strongly convex objective functions, the expected excess population loss is bounded by $\mathcal{O}(1/mn)$. Second, we consider the MAML algorithm's generalization to an unseen task and show that the resulting generalization error depends on the total variation distance between the underlying distributions of the new task and the tasks observed during the training process. Our proof techniques rely on the connections between algorithmic stability and generalization bounds of algorithms. In particular, we propose a new definition of stability for meta-learning algorithms, which allows us to capture the role of both the number of tasks $m$ and number of samples per task $n$ on the generalization error of MAML. 

Generalization of Model-Agnostic Meta-Learning Algorithms: Recurring and Unseen Tasks
Alireza Fallah
Aryan Mokhtari ECE Department The University of Texas Austin mokhtari @austin. wtw.an.ttee...mmmmmmm.m edu
EECS Department
Massachusetts Institute Technology afallah@mit. edu
Asuman Ozdaglar
EECS Department
Massachusetts Institute of Technology asuman@mit, edu
Abstract
In this paper, we study the generalization properties of Model-Agnostic Meta- Learning (MAML) algorithms for supervised learning problems. We focus the setting in which we train the MAML model over m tasks, each with n data points, and characterize its generalization error from two points of view: First, we assume the new task at test time is one of the training tasks, and we show that, for strongly convex objective functions, the expected excess population loss bounded by O(1/mn). Second, we consider the MAML algorithm's generalization an unseen task and show that the resulting generalization error depends on the total variation distance between the underlying distributions of the new task and the tasks observed during the training process. Our proof techniques rely on the connections between algorithmic stability and generalization bounds of algorithms. In partieular, we propose a new definition of stability for meta-learning algorithms, which allows us to capture the role of both the number of tasks and number of samples per task n on the generalization error of MAML.
Introduction
In several machine learning problems, it is of interest design algorithms that can be adjusted based on previous experiences and tasks to perform better on a new task. In particular, meta- learning algorithms achieve such a goal through various approaches, including finding a proper meta-initializztion for the new task [1-3]. updating the model architecture [4-6], or learning the parameters of optimization algorithms [7,
popular meta-learning framework that has shown promise in practice Model-Agnostic Meta- Learning (MAML), which first introduced in [1]. MAML algorithm uses available training data on number of tasks to come up with a meta-initialization that performs well after slightly time with respect the task. In other words, unlike standard supervised learning, in which we aim to find a model that generalize well to a new task without any adaptation step, in MAML goal is find initial model for learning new task when we have access to limited labeled data for that task to run one (or few) step(s) of stochastic gradient descent (SGD).
updated
As shown in Fig. in MAML training phase. Once the model is trained (wii.) a new task is revealed at test time for which we have access to K labeled samples drawn from D We use these labeled samples of the task to
given tasks with corresponding datasets (S,) in the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

update the trained model by running step of SGD leading to new model for the test task (W We finally evaluate the performance of the updated model over the test task, denoted by Crest ( (w (eww))
MAML and its variants have been extensively studied over the past few years from both empiri- cal and theoretical point of view [2. 9-16]. In particular, [13] provided convergence guarantees for MAML algorithm under the assumption that access to fresh samples any round of the training stage possible, and [15] extended this results to the case that multiple gradient steps can be performed at test time. However, one shortcoming of such analysis is that, at training stage, we often do not have access to fresh samples at every iteration. Instead, we have access to a large set of realized samples and we typically do multiple passes over the data points during the training stage.
Training stage
S1 P1
Sm Pm
Hence, it is essential come up with a novel analysis that addresses this issue by characterizing the training error and generalization error of MAML separately. In this paper, we accomplish this goal and showcase the role of different problem parameters in the generalization error of MAML. Specifically, we assume that we are given m supervised learning tasks, with (possibly different) underlying distri- butions P1....Pmi Pmm, where for each task we have access to n samples As we measure the performance of model by its loss after one step of SGD adaptation with K sam- ples, the problem that one can solve in the training phase is minimizing the average loss, over all given m tasks and their n samples, after one step of SGD with K samples. This empirical loss can be considered as surrogate for the desired expected loss (with respect to tasks data) over all m tasks. Here, we focus the case that MAML is used to solve this empirical minimization problem, and our goal is to quantify the test error of MAML output. To tackle this problem, we first briefly revisit the results from the optimization literature bound the training error of MAML, assuming that the loss functions strongly convex. We next turn to the main focus of our paper which is the generalization properties of MAML. More specifically, we address the following questions:
Wirzin
Test stage
Diest Piest
V L.C.virmn Doea))
Liest ( (WSew)
Whew
Figure 1: MAML framework
one of the m given tasks recurs uniformly at random at test time, then how well (in expectation) would the trained model perform after adaptation with SGD over the fresh samples of that task? In other words, having training error minimized, what would be the generalization error and our guarantee on test error? Here, show that for strongly convex objective functions, we could achieve a generalization error that decays at (11 /mn). Our analysis builds on the connections between algorithmic stability and generalization of the output of algorithms. While this relation is well-understood in classic statistical learning [17, 18], here we propose a novel stability definition for meta-learning algorithms which allows us restore such connection for our setting.
Assuming that the task at test time is NOT one of the m tasks at training, how would the model perform on that task after the adapiation step? We answer this question by focusing on the case that the revealed task at the test time is a new unseen task with underlying data distribution Pm+1. and formally characterizing the generalization error of MAML in this case. We show that when the task at test time is new, the generalization error also depends on the total variation distance between Pm++1 and p1,.... Pm-
Related work: Recently, there has been significant progress in studying theoretical aspects of meta-learning, in particular, MAML. Authors in [19] proposed iMAML which updates the model using an approximation of one step of proximal point method and studied its convergence. In [20], authors introduced the task-robust MAML by considering minimax formulation rather than minimization. Several papers have also studied MAML through more general frameworks such as bilevel optimization [21], stochastic compositional optimization [22], and conditional stochastic
MMore precisely, in analysis take 2n samples per each task to simplify derivations.

---

optimization [23]. Also, several works have studied the extension of meta- meta-learning theory to online
learning [24, 31, federated learning [25]. and reinforcement learning [26, 27].
The most relevant paper to our work is [28] that studies generalization of meta-leaming algorithms using stability techniques and shows (11 /m) bound for nonconvex loss functions, Here
focus on strongly convex objective functions and present an analysis that differs from this work in two fundamental aspects. First, we present different notion of stability that allows us to capture the number of data points per task in our bound. In particular, our stability notion measures sensitivity of the algorithm to perturbations that involve changing K data points which is the data unit involved in the adaptation step of the MAML algorithm. This enables us to obtain much tighter bound ((1/mn) (compared (11/m) /m) achieved in [28] for strongly convex functions), highlighting the dependence on the number of the data samples available for each task. Second, we also consider the generalization of MAML for the case that the task at test time not one of the available tasks during the training stage.
The generalization of MAML has also been studied in [29] from an empirical point of view. In particular, they show that the generalization of MAML to new tasks is correlated with the coherence between their adaptation trajectories in parameter space. This is aligned with the connection of generalization and closeness of underlying distributions that we observe in our results.
2 Problem formulation
In this paper, we consider the supervised learning setting, where each data point is denoted by (xx y) E Z with X' being the input (feature vector) and y ) being its corresponding label. We use the loss function 1: Rd x 2 + R+ to evaluate the performance of a model parameterized by w E W. where W is a convex and closed subset of R.. In other words, for a data point (z, v) E Z, the loss f(w, z) denotes the error of model w in predicting the label y given input
We consider access to m tasks denoted by TI...., Tm where the data corresponding to each task T; is generated from a distinct distribution p;- The population loss corresponding to task Ti for model w defined as (w) == [
[f(w, =)].
We further use the notation L(w; D) to denote the empirical loss corresponding to dataset D, which is 1 defined as the average loss of w over the samples of dataset D, i..., L(w; D) := [D] Σ.ED f(w, 2), where [D] is the size of dataset D. In general, and throughout the paper, use the hat notation to distinguish empirical losses from population losses.
Our goal is to find w E W that performs well on average² over all tasks, after it is updated with respect to the new task and by using one step of stochastic gradient descent (SGD) with a batch of size K. To formally introduce this problem we first define the function (,(w) which captures the performance of model w over task Tr once it updated by a single step of SGD,
F((w)= = Ppp [Cs (w 1 aV-[aV D(at)) )} = Epg Ezupi
[((w
a Σ Ve(w, ('), VVe(,,))) K D'ED
x (1)
where DI is a batch with K different samples, drawn from the probability distribution p;. Note that the outer expectation is taken with respect to the choice of elements of Diest while the inner one is taken with respect to the data of task i.
As our goal is to find model that performs well after one step of adaptation over all m tasks, we minimize the average expected loss over all given tasks, which can be written as
1 m Σ F((w).
min F(w) wEW
As the underlying distribution of tasks often unknown in most applications, we often unable to directly solve the problem in (2). On the other hand, for each task, we often have access to data points that drawn according their data distributions. Therefore, instead of solving (2), we solve its sample average surrogate problem in which each F; is approximated by its empirical loss.
Our analysis can be extended the case that the distribution over tasks is not uniform.
3

---

To formally define the empirical loss for each task, suppose for each task Tj we have access to training set S; where its elements are drawn independently according to the probability distribution p:. We further divide the set S; into two disjoint sets of size defined as S.r and S i.e., S == {Sr", S and ||; || = n. Here, we use the elements of the S." to estimate the inner gradient V VL(w, Dist) and use the samples in the set Sque estimate the outer function (,(-). Specifically, we define the sample average of F; using data sets S.n" and Stat as
(,w
E
P (w- a aVL(w, )
(3)
n K
Σ
Σ
Σ RES.
w Σ EED
Ve(w, (((,z2),,
71
This expression shows that we use all n elements of S.tt to approximate the expectation required for the computation of Li, and we approximate the expectation with respect the test set by averaging over all subsets of S.Dh that have K elements. Given this expression, the sample average approximation (empirical loss) of Problem (1) is given by
m 771 Σ (,(,SS))
arg min F(w,S) wEW
(4)
where S = (S.) 1 is defined the concatenation of all tasks data sets.
Having the dataset S, a (possibly randomized) optimization algorithm A with output A(S) can be used to find an approximate solution to the problem in (4). The error of this solution with respect to the MAML empirical loss, i.e., F(A(S),
minw S.,,S), is called training error. In this paper, we are mainly interested to bound the test error which is the error of A(S) with respect to the population loss, i.e., F(A(S)) miny F. The test error is also sometimes called excess (population) loss. Note that the expected test error can be decomposed into three terms:
EA,S F(A(S)) -min F] W
(test error)
EAS
+ EA.S S)) min F(,, Es W
min F(.,5) W
min F. W
generalization
training emoor
20
can be verified that the expectation of the third term (over A and S) is non-positive since Es [miny S)] miny Es, and [s) F. Hence, bound the expected test error, we should bound the expectation of training and generalization errors.
The Model-Agnostic Meta-Learning (MAML) method proposed in [1] is designed to solve the empirical minimization problem defined in (4). The steps of MAML are outlined in Algorithm 1. MAML solves Problem (4) by using SGD update for the average loss function f (w, S). To better highlight this point, note that the gradient of V F(w, ju, S) can be written as the i-th term corresponding to task T, given by
E VF: S;), where
Vi S.)
Σ
(1a - ua-ov>Llw,pp x VL (w
(5)
D.
I K
which involves the second-order information of the loss function. Therefore, to compute mini-batch approximation for the above gradient, we consider the batches DJn S!h with size K and De C Spet with à elements. Replacing the above sums with their batch approximations leads to the following stochastic gradient approximation
(w: D D. L.. (w aV D))), D.T)).
which is indeed an unbiased estimator of the gradient Vir( S.) in (5). If each task we perform the update of SGD with g, and then compute their average would be similar to running SGD for

---

Algorithm 1: MAML [1]
Input:
The set of datasets S {S. with S; = {S "; test time batch size K; # of tasks summoned at each round r; # of iterations T. Choose arbitrary initial point w e W:
for I 0 to T 1 do
Choose r tasks uniformly at random (out of m tasks) and store their indices in B;; for all T; with E B, do
Sample batch D. of K different elements from S.nh with replacement;
Sample batch D. of size b from S.ae and with replacement:
w++1 w² Br aVv-VViL )) VL ww a L(w', ".""), D.
w
end for
w++1 := rw (, DiEi w w end for
1 Return: TT and TT == T+1 Ei= w
the average loss Vi S). This exactly how MAML is implemented in practice as outlined in Algorithm 1. In this paper, we consider a constrained problem, and as result, we also need an extra projection step in the last step to ensure the fcasibility of iterates. Finally, the output of MAML could be the last iterate w" or the time-average of all iterates wf : 7+I Ei w'.
As stated earlier, the convergence properties of MAML-type methods from an optimization point of view have been studied recently under different set of assumptions. In this paper, as we characterize the sum training error and generalization error, we briefly discuss the optimization error of MAMI. when it is used to solve the empirical problem in (4). However, the main focus of this paper is on studying the generalization error of MAML with respect to new samples and new tasks. Specifically, we aim to address the following questions: (i) How well does the solution of (4) generalize to the main problem interest in (2)? This could be seen as the generalization error of the MAML algorithm new samples for recurring tasks. (ii) How well does the solution of (4) generalize to samples from new unseen tasks? To be more precise, how would the obtained model preform if the new task is not one of the m tasks Ti..... Tm observed at training, and it is rather a new, unseen task Tm+1 with an unknown underlying distribution Pm++1 1 In the upcoming sections, we answer these questions on the generalization properties of MAML in detail and characterize the role of number of tasks m, number of samples per task n, and number of labeled samples revealed at test time K.
Theoretical results
In this section, we formally characterize the excess population loss (test error) of the MAML solution, when we measure the performance of a model after one step of SGD adaptation. In particular, we first discuss the training error of MAML in detail. Then, establish generalization error bound for the case that the solution of MAMI. is evaluated over new samples of recurring task. Finally, we state the generalization error of MAML once its solution is applied new unseen task. Before stating our results, we mention our required assumptions.
Assumption 1. For any z E Z. the function E(.,,) is twice continuously differentiable. Furthermore, we assume it satisfies the following properties for any w, u E Rd.
(i) For any z E Z, the function {(.,2) is u-strongly convex, i.e., [[V[(w, 2) - Vê(u, 2)1l 2 wlwl w|l:
(ii) The gradient norm is uniformly bounded by G over W, i.e., [V(ww,)) - G;
(ii) The loss is L-smooth over Rd, i.e., [[V[(w: w. z) Vl(u, =| < L|| w - ull:
(iv) Hessian is p-Lipschitz continuous over Rdd i.e.. V - v 2)]l S p|| u//.
We also require the following assumption on the tasks distribution. This assumption implies that, with probability one, a set of finite samples generated from a distribution p; are all different.
5

---

Assumption& 2. We assume 2 is Polish space (i.e., complete, separable, and metric) and Fz is the Borel o-algebra over 2. Moreover, for any i, Pe is non-atomic probability distribution over F2), ie., pi(2) = 0 for every 2 E 2.
3.1 Training error
While the main focus of this paper on studying the population error of MAML algorithm, we first study its training error which is required to provide characterization of the excess loss of MAML. To do so, we first state the following result from [24] and [13] on the strong convexity and smoothness of f(w aV (w, D), 2) for any batch D and any 2 2.
Lemma 1 ([13) & [24]). If Assumption 1 holds, then for an arbitrary batch D and Z, and with S
the function E(w aVL(w, D), is 4L + 20pG smooth over W. Furthermore, f(w - [(w, 2), is -stronngly convex, if a S min 2T 8pG
1 L'
1 R
An immediate consequence of this Lemma is that the MAML empirical loss F defined in (4) is also 4/8-strongly convex and 4L + 2apG smooth over W. In addition, it can be shown that the norm of gi (w; D. , D. defined in (6), which is the unbiased gradient estimate used in MAML, is uniformly bounded above; for more details check Lemma 5 in Appendix A. Having these properties of the MAML empirical loss established, we next state the following proposition on the training error of MAML. This result is obtained by slightly modifying the well-known results the conver- gence of SGD in [30-32] in order to take into account the stepsize constraints that are imposed by generalization analysis. For completeness, the proof of this result is provided in Appendix B.
). If Asssupption I holds, then for MAML with Br min(3, p(t+1)) ) for 3 S 8/ p. and for any set S, the last iterate w satisfies
Proposition 1. Consider ((,, S) defined (4) with a S min Z 8pc
E F( 8) F(wg, s)] 20
G2 TT))
L (pa
paG
G
+
(7)
122
T
VT)
and the time-average of iterates n" satisfies
(log(T +
E | S) - fw's 5) s O(1)
3p
nT
where w/g == arg min wew S), and the expectations are taken over the randonness of algorithm.
In the above expressions, the notation O(1) only hides absolute constants. It worth noting that the term / in (7) vanishes, w's be a minimizer of the unconstrained problem, i.c., F S) = 0.
3.2 Generalization error
We derive our generalization bounds for MAML by establishing its algorithmic stability properties. The stability approach has been used widely to characterize the generalization properties for optimiza- tion algorithms such as stochastic gradient descent [18] or differentially private methods [33]. These arguments are based on showing the uniform stability of algorithms [17] which we restate it here.
Definition 1 ([17)) Consider the problem of minimizing the empirical function L(w, H. for some dataset H. A randomized algorithm A with output wH given dataset H is called uniffrrmyy stable if the following condition holds: Take the dataset H which is the same as H. except at one data points. Then, we have sup EA | 2) f(w R]]] S 7, where the expectation is taken over the randomness of
The above definition captures the stability of an algorithm. Specifically, it states that Algorithm A is y staable, if the resulting loss of its outputs, when is run using to two different datasets that only differ in one data point, are at most 7 away from each other. Note that the above definition holds if the difference between the losses evaluated at any point is bounded by 7. The main importance of this definition is its connection with generalization error. In particular, it can be shown that if an algorithm 7-uniformly stable and "symmetric", then its generalization error bounded above by 7; see, c.g., [17]. Next, we formally state the definition of symmetric algorithm.

---

Definition 2. An algorithm A: 2 + RR is called symmetric, for any S C 2", the distribution of its output, i.e., A(S), does not depend on the ordering of elements of S. i.e. if we take S' as permulation of S, the distribution of A(S) and A(S") would be similar.
Note that Definition I is useful for the case where measure the performance of model by its loss function over a sample, i.e., [(w, 2). However, in this paper we measure the performance of a model by looking its loss after one step of SGD which involves K data points, as defined in (6). Therefore, we cannot directly use Definition 1 for characterizing the generalization error of MAML. In fact, in what follows, we first propose a modified version of the uniform stability definition, which is compatible with our setting, and then show how such stability could lead to generalization bounds for MAML-type algorithms.
Definition 3. Consider the problem in (4). A randomized algorithm A with output wis given dataset called (r, K) yuniformly stable if the following condition holds for any i E (1.... .m.: Take the dataset S which is the same as S, except that 8tn and Sqm differ from S and S.t in at most K and one data points, respectively. Then, for any E 2 and any K distinct points {z1:-., [ak,,,,,)))) in Z,
EA Ealle
[le (ws- - -VVLLss (2)1s 12.) e {"ss aV (2g)) S S7
where the expectation is taken over the randomness of A.
A few remarks about the above definition follow. First, one might wonder, why it is needed to change K points of the set S." while we change only one point of the set St Note that, going from (1) to (3), the expectation Epi= [.] is replaced by the sum over all (x) possible batches Dit of size K from STh In other words, for the empirical sum in (3), each batch Dtdh can be seen as a data unit. That said, and similar to Definition to characterize the stability, we need change one data unit which is one batch of size K. That is why we change K data points of S.n in the definition of (7, K) unniforlyy stability. On the other hand, we replace L.(.) Ez-p. [e[., 2)] in (1) with sum over points of Spar in (3), and thus, for this one, each data unit is just a single data point. So, similar to Definition 1, we just change one data point for the set S.u.
Second, it is worth comparing this definition with the other definition given for stability of meta- learning algorithms in [28]. In that paper, the definition of stability is based modifying the whole dataset S, rather than what we do here which is changing just K + points. While taking such a definition makes the analysis relatively simpler. it prohibits of generalization error on n, and hence the resulting upper bound for generalization error would be larger. We will come back to this point later when we derive the stability of MAML with respect to Definition 3 and compare it with the one obtained in [28].
from characterizing the dependence
As we discussed, the main reason that we are interested in the uniform stability of an algorithm is its connection with generalization error. In the next theorem, we formalize this connection for MAML formulation and show that if an Algorithm A is (r, K) -u-unffrrlly stable and symmetric, then its output generalization error is bounded above by y.. The proof of this result is available in Appendix C.
Theorem 1. Consider the population and empirical losses defined in (2) and (4), respectively. If Assumption 2 holds and A is a (possibly randomized) symmetric and (7,, K) K-)uniffrmly stable algorithm with output ws W, then EAS [F(s)) - F( S7.
This result shows that if we prove symmetric algorithm is (7, (7,K))uma -uniformly stable as defined in Definition 3, then we can bound its output model generalization error by 7. Hence, to characterize the generalization error of the model trained by MAML algorithm, we only need to capture the uniform stability parameter of MAML. Before stating this result, it is worth noting that while we limit our focus to MAML in this paper, Definition 3 and Theorem 1 could provide framework for studying the generalization properties of broader class of gradient-based meta- learning algorithms such as Reptile [34], First-order MAML [1], and Hessian-Free MAML [13].
Theorem 2. If Assumption I holds, then MAML (Algorithm 1) with both last iterate and average P. } and B, S 1 is (7, -unniformly stable, where iterate outputs and with S min I 8pG
= (1)
G (1+aLK)
maj
According to the above discussion, the result of Theorem 2 guarantees that the generalization error of MAML solution decays by factor of O(K/mn), where m is the number of tasks in the training set
7

---

and n is the number of available samples per task. The classic lower bound for SGD over strongly convex functions translates O(1/mn) lower bound in our setting, Hence, our bound is tight in the small K regime, which is generally the case in few-shot learning problems. However, one shortcoming of this result is that is not tight in the large K regime. In Appendix E we show how we could improve this result for the large K regime. However, throughout the paper, we keep our discussion limited to the small K regime.
Remark 1. If instead of using our uniform stability definition (i.e., Definition 3), one uses the stability definition given in [28], the resulted stability constant " would be proportional to (1/m) rather than (1/mn). In fact, our proposed cniform-stabbllig definition empowers us obtain a better bound and indicates the role of number of samples per task n in the generalization error.
Remark 2. The algorithmic stability technique is mainly limited to the convex setting, since, in the nonconvex case, need to keep learning rate very small to obtain meaningful generalization results which makes it impractical (Check Appendix G for further discussions on this matter). In fact, the main reason that we assume is strongly convex and S (2(μ) is to ensure that the mela-objective convex, as, in general, relaxing any of these two could lead to a nonconvex meta- veta-objectivv function. However, these two assumptions together make the objective function strongly convex, which is not necessarily needed in our analysis. In fact, if we assume that & and the meta- peeta-funttion are convex (but not necessarily strongly convex), could still use Definition 3 to derive similar generalization bounds.
Putting Proposition and Theorem 2 together, obtain the following result on the excess population loss MAMI algorithm. We only report the result for the averaged iterates here, but one can obtain the result for the last iterate similarly by using Proposition 1.
Proposition 2. Consider the function F defined in (2) with S min EL BeG ). If Assump- tions 1 and 2 hold, then the average of iterates generated by MAML (Algorithm 1) with B. min( 2apt m(t+T)) after T iterations satisfies
G (T) + L/P
1+
EAS F(w"")min
min S 011) W
+
T
mn
where the expectation is taken over the sampling of S and the randomness of MAML algorithm.
As an immediate application, the following corollary characterizes MAML test error.
MAML Corollary 1. Under the premise of Proposition 2, .AML algorithm after T = Ó(mL//p) iterations
returns TT such that EAs [F(w") minw F] S O (G a/LK) /LK)/(mnf())
3.3 Generalization an unseen task
As we discussed in Section 2, another generalization measure is how the model trained with respect to the empirical problem in (4) performs on a new and unseen task Tm+1 with corresponding distribution Pm+11 To state our result for this case, we first need to introduce the following distance notion between probability distributions.
Definition 4. For two distributions P and Q, defined over the sample space Ω and a-field F, the total variation distance is defined as I|P - Q1 == sup ((AA) - Q(A)).
It is well-known that the total variation distance admits the following characterization
P PP-QQlrv = sup f:05/51
Ex-p[[(=) (x)))
(8)
Also, we require the following boundedness assumption for our result. Assumption 3. For any E 2, the function {(., is M -boudeed over W.
Considering these assumptions, we are ready to state our result for the case when the task at test time new task and is not observed during training.
Theorem 3. Consider the population losses defined in (1) and (2). Suppose Assumptions 1, and 3 hold. Then, for any w W, we have
F (m) F(w)l S D(pm+1 mm)
(9)
8

---

where
4aG²
m Pm+1 PillTV + (M 2aG
1 m
((p=+1 (p)) ((Pm+1:(p:)::))
PelITV (10)
m
While the proof is provided in detail in Appendix F, here we discuss sketch of it to highlight the main technical contributions. To simplify the notation here, let assume m 1, meaning that pi is the distribution used for training and P2 is the distribution corresponding to the new task. Note that we aim bound [2( Fi Fi Recalling the definition of population loss (2), we need bound the following expression (we drop the absolute value due to symmetry)
(x3 Papp (w aVi(w, {z}b)), 2²)] (xt s (1w aV ((w, {z)b),, =');
(11)
[X] B ((=))) K+1 [X], with Notice that this difference can be cast as E ((=))
X == w (-- a V [(w, ( As result, naive approach would be using Lipschitz and boundedness properties of (Assumptions and 3) along with (8) to obtain a bound depending on
[|r - p2 + ((K) P2 |rv. However, this bound is not tight as it grows with K.
To address this issue, exploit coupling technique. Note that the expression in (11) does not depend on the joint distribution of 2!} and 2f. and instead, only depends on the marginal distribution of 2 and 23. That said, for each j. we assume that z} and 2 are sampled from a distribution on Z x Z such that z} P1, 2] P2, and u(2) * 23) llp1 Pallrv. Such coupling exists and called maximal coupling of P1 and pa [35]. Using this idea, as we show in Appendix F, we can eliminate the dependence
K, and available labeled samples at test time denoted by K.
result, the upper bound in (9) is independent of number of
Remark Note that the terms 1 E Ilpm=1 PillTv and lpm++1 m E Pallry in D(pm+1, (p.)a)) come from the fact that we consider uniform distribution over tasks in the empirical problem (4). In particular, if we instead consider the empirical problem arg min Ex qi
m.
F3 FFF((w,, Si), for some non-negative weights qi with Σ 9: D(pmt1, (Pr (=1) on the right hand side of (9) would change to
then
m -E Eapillry + 12aG2
m
(M + 22G
Σ qe gillpmt Pellrv.
This result shows that by changing the training problem we can achieve a lower generalization error for MAML. if we have some information about the distribution pm+1 training time. For instance, if we know Pm+1 will be much closer to P1 compared to p2, making the weight of larger than P2 would decrease the generalization error of MAMI.
Corollary 2. Recall the population loss Fm41 defined in (2) and D(pm+1 (p defined in Theorem 3. Let A be an algorithm for solving the empirical problem (4) which achieves e excess risk, i.e., E (A((F()()) mill F S If Assumptions 1, 2 and 3 hold, then algorithm A finds a model ws which achieves + D(pm+1, mm excess loss with respect to Fmtti
min Fm+1 5 ++222(pmm (p:)m
This corollary and Proposition together imply that the MAML algorithm's 's test error with respect to the new task Tm+1 is ((1 wer + D(pm+ 1. {p, Im ))) As result, if the new task's distribution Pm++1 is sufficiently close to the other tasks' distributions, MAML will have a low test error on the new unseen task. On the other hand, if pm++1 is far from p1:... : Pm in TV distance, then test error of the model trained (T;h) over Tm+ could be potentially large. In Appendix F.2 we show how this result can be extended to the case that the task test time is generated from distribution over both
recurring tasks mm and the unseen task Tm+1-
4 Conclusion and future work
In this work, we studied the generalization of MAMI. algorithm in two key cases: a) when the test time task is recurring task from the ones observed during the training stage, b) when it is

---

new and unseen one. For the first one, and under strong convexity assumption, we showed that the generalization error improves as the number of tasks or the number of samples per task increases. For the second case, we showed that when the distance between the unseen task's s distribution and the distributions of training tasks is sufficiently small, the MAMI output generalizes well to the new task revealed at test time.
While we focused on the convex case in this paper, deriving generalization bounds when the meta- function is nonconvex is a natural future direction to explore. However, this could be challenging since the generalization of gradient methods not well understood the nonconvex setting even for the classic supervised learning problem.
5
Acknowledgment
Alireza Fallah acknowledges support from the Apple Scholars in AI/ML PhD fellowship and the Math Works Engineering Fellowship. This research is sponsored by the United States Air Force Research Laboratory and the United States Air Force Artificial Intelligence Accelerator and was accomplished under Cooperative Agreement Number FA8750-19-22 19000-199---00000 The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the United States Air Force or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. This research of Aryan Mokhtari is supported in part by NSF Grant 2007668, ARO Grant 1911NF110022 the Machine Learning Laboratory at UT Austin, and the NSF AI Institute for Foundations of Machine Learning.
References
[1] C. Finn, P. Abbeel, and S. Levine, "Model-agnostic meta-learning for fast adaptation of deep networks," in Proceedings of the 34th International Conference on Machine Learning, (Sydney, Australia), 06-11 Aug 2017.
[2] A. Nichol, J. Achiam, and J. Schulman, "On first-order meta-learning algorithms," arXiv preprint 1833:v:88000990 2018
[3] M. Khodak, M.-F. F. Balcan, and A. S. Talwalkar, "Adaptive gradient- based meta-learning methods," in Advances in Neural Information Processing Systems, pp. 5915-5926, 2019.
[4] B. Baker, O. Gupta, N. Naik, and R. Raskar, "Designing neural network architectures using reinforcement learning," " in International Conference on Learning Representations, 2017.
[5] B. Zoph and Q. V. Le, "Neural architecture search with reinforcement learning," in International Conference Learning Representations, 2017.
[6] B. Zoph, V. Vasudevan, J. Shiens, and Q. V. Le, "Learning transferable architectures for scalable image recognition," in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8697-8710, 2018.
[7] S. Ravi and H. Larochelle, "Optimization as model for few-shot learning," " in International Conference on Learning Representations, 2017.
[8] M. Andrychowicz, M. Denil, S. Gómez, M. W. Hoffman, D. Pfau, T. Schaul, B. Shillingford, and N. de Freitas, "Learning to learn by gradient descent by gradient descent," " in Advances in Neural Information Processing Systems 29, pp. 3981-3989 Curran Associates, Inc., 2016.
[9] A. Antoniou, H. Edwards, and A. Storkey, "How to train your MAML," in International Conference on Learning Representationss 2019.
[10] Z. Li, F. Zhou, Chen, and Li, "Meta-SGI: Learning to learn quickly for few-shot learning." " arXiv preprint arXiv:/707. 777.00985, 2017.
[11] E. Grant, C. Finn, S. Levine, T. Darrell, and T. Griffiths, "Recasting gradient-based based meta- learning as hierarchical bayes," in International Conference on Learning Representations, 2018.
10

---

[12] H. S. Behl, A. G. Baydin, and P. H. S. Torr, "Alpha MAML: adaptive model-agnostee meta- learning." " 2019.
[13] A. Fallah, A. Mokhtari, and A. Ozdaglar, "On the convergence theory of gradient- -baed model- agnostic meta-leaming algorithms," in International Conference on Artificial Intelligence and Statistics, pp. 0082-1092, 2020.
[14] R. Xu, L. Chen, and A. Karbasi, "Meta learning in the continuous time limit," arXiv preprint arXiv:2006. 10921, 2020.
[15] K. Ji, J. Yang, and Y. Liang. "Multi-step model-agnostic meta-learning: Convergence and improved algorithms," arXiv preprint urXiv:2002.07836 2020.
[16] I.. Wang, Q. Cai, Z. Yang, and 7. Wang, "On the global optimality of model-agnostic meta- learning," in International Conference on Machine Learning, pp. 9837-9846, PMLR, 2020.
[17] O. Bousquet and A. Elisseeff. "Stability and generalization," Journal of machine learning research, vol. 2, no. Mar. pp. 499-526, 2002.
[18] M. Hardt, B. Recht, and Y. Singer, "Train faster, generalize better: Stability of stochastic gradient descent," in International Conference on Machine Learning, pp. 1225-1234, PMLR, 2016.
[19] A. Rajeswaran, C. Finn, S. M. Kakade, and S. Levine, "Meta-learning with implicit gradients," in Advances in Neural Information Processing Systems (H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bol BicheBBuc, E. Fox, and R. Garnett, eds.), vol. 32, pp. 113-124, Curran Associates, Inc., 2019.
[20] L. Collins, A. Mokhtari, and S. Shakkottai, "Task-robust model-agnostic meta-learning," Ad- vances in Neural Information Processing Systems, vol. 33, 2020.
[21] V. Likhosherstov, X. Song, K. Choromanski, Davis, and A. Weller, "Ufo-blo: Unbiased first-order bilevel optimization," arXiv preprint arXiv:2006.0366) 2020.
[22] T. Chen, Y. Sun, and W. Yin, "Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization," arXiv preprint arXiv:2008. /0847, 2020.
[23] Y. Hu, S. Zhang, X. Chen, and N. He, "Biased stochastic gradient descent for conditional stochastic optimization." ArXiv, vol. abs/2002.10099., 2020.
[24] C. Finn, A. Rajeswaran, S. Kakade, and S. Levine, "Online meta-learning," in Proceedings of the 36th International Conference on Machine Learning, vol. 97 of Proceedings of Machine Learning Research, (Long Beach, California, USA), pp. 1920-1930, PMLR, 09-15 Jun 2019.
[25] A. Fallah, A. Mokhtari, and A. Ozdaglar, "Personalized federated learning with theoretical guar- antees: A model-agnostic meta-learning approach," Advances in Neural Information Processing Systems, vol. 33, 2020.
[26] H. Liu, R. Socher, and C. Xiong, "Taming maml: Efficient unbiased reii-reiinorcemment learning," in International Conference on Machine Learning, pp. 4061-4071, PMLR, 2019.
[27] A. Fallah, K. Georgiev, A. Mokhtari, and Ozdaglar, "Provably convergent policy gradient methods for 2020.
meta-reinforcemen learning," arXiv preprint arXiv:2002.05/35,
[28] J. Chen, X.-M. Wu, Y. Yi, Q. Li, L.-M. Zhan, and F.-l Chung, "A closer look at the training strategy for modern meta-learning," Advances in Neural Information Processing Systems, vol. 33, 2020.
[29] S. Guiroy, V. Verma, and C. Pal, "Towards understanding generalization in gradient-based meta-learning," arXiv preprint a90i:: 072877 2019.
[30] A. Rakhlin, O. Shamir, and K. Sridharan, "Making gradient descent optimal for strongly convex stochastic optimization," arXiv preprint arXiv:1109.5644 2011.
11

---

[31] E. Hazan, A. Agarwal, and S. Kale, "Logarithmic regret algorithms for online convex optimiza- tion," Machine Learning, vol. 69, no. 2-3, pp. 169-192, 2007.
[32] A. Nemirovski, A. Juditsky, Lam, and A. Shapiro, "Robust stochastic approximation approach to stochastic programming," SIAM Journal on Optimization, vol. 19, no. 4, pp. 1574-1609, 2009.
[33] R. Bassily, V. Feldman, K. Talwar, and A. Guha Thakurta, "Private stochastic convex opti- mization with optimal rates," Advances in Neural Information Processing Systems, vol. 32, pp. 11282-1 291, 2019.
[34] A. Nichol, J. Achiam, and J. Schulman, "On first-order meta-learning algorithms," arXiv preprint arXiv: 1803: 0299,, 2018.
[35] Den Hollander, "Probability theory: The coupling method," Lecture notes available online (http://websites. math. leidenuniv.
ectures. pdf), 2012.
[36] Y. Nesterov, Introductory Lectures Convex Optimization: A Basic Course, vol. 87. Springer, 2004.
12


Reviews:
[{"review_id": "sNwlQvdX8LL", "reviewer": "Reviewer_CKWF", "summary": "In this paper, the authors provide a generalization and uniform-stability-type analysis for MAML training. In specific, the authors first present a generalization error bound (based on the uniform stability bound) of $O(1/mn)$ for strongly convex objective functions when the new task at the test time belong to one of the training tasks. Then, for a more interesting setting where the new task does not belong to the training tasks, the authors provide a generalization bound consisting of a total variation distance between the data distributions of this unseen task and the training tasks. One toy experiment is provided in the supplementary materials to verify the impact of the sizes $m,n$ on the generalization performance. ", "questions": "", "limitations": "", "rating": 6, "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": "In this paper, the authors provide a generalization and uniform-stability-type analysis for MAML training. In specific, the authors first present a generalization error bound (based on the uniform stability bound) of $O(1/mn)$ for strongly convex objective functions when the new task at the test time belong to one of the training tasks. Then, for a more interesting setting where the new task does not belong to the training tasks, the authors provide a generalization bound consisting of a total variation distance between the data distributions of this unseen task and the training tasks. One toy experiment is provided in the supplementary materials to verify the impact of the sizes $m,n$ on the generalization performance. My detailed comments are given as below.\n\nPros:\n1.\tThis paper is well written and easy to follow. I find that the notations, definitions, assumptions and related works in this paper are clear and the explanation for the main results are clear and reasonable. \n2.\tStudying the generalization for MAML type of algorithms is very important, and this paper takes a good try to provide generalization error and stability bounds for MAML under various settings. \n3.\tThis paper shows that the sample number for the intra-task training is also important and can be used to further reduce the generalization error. \n\nCons:\n1.\tMy first concern is the tightness of the upper bound. It is true that the dependence on $mn$ (i.e., the total number of training sample) is optimal for the strongly convex objective function (in fact, this is a  standard result in statistical learning where the optimal dependence of the excess risk on the sample size M is $O(M)$). However, it is not clear whether other parameters (even some constants) are still optimal for the authors’ upper bounds, e.g., the authors do not prove the optimality of the test sample size $K$. In addition, it seems to me that the results in this paper are not surprising (even though the derivations can be different due to the MAML structure), i.e., the bounds decrease with the total number $mn$ of the training samples (as we always see in standard supervised learning). I will be more excited if the derived upper bounds can involve some special components caused by the composite structure of MAML or the upper bounds capture some interplay between the training and the test procedures of the meta training process of MAML. In Chen et al., 2020 (as pointed out by the authors), they provide interesting findings on how the support/query split used in the meta learning (including MAML) affects the generalization (as well as the theoretical generalization bounds). However, I do not see much new things for MAML in the generalization bounds in this paper. \n2.\tMy another concern is that the empirical verification is not sufficient. First, the curves in the experiments contain  large variations, and I suggest the authors can run more seeds and do an average to make the results convincing. Second, the authors only verify the impact of sample sizes $m,n$ on the generalization performance. Since the sample size $K$ of the test data is also important, I suggest an experiment to test its impact on the generalization. Third, the authors provide a generalization bound for an unseen task, which increases with the total variation distance between tasks’ distributions. Therefore, it would be better if the authors can provide experiments to verify whether such a total variation distance metric really captures the generalization error. If so, this will be a good contribution because it may provide guidelines for how to improve the generalization of meta-learning based on the task selection.  Fourth, since the supervised classification is an important application for meta-learning, it would be better if an experiment can be done for it.\n3.\tThe  training error characterization mainly follows from  exiting works e.g., Fallah et al., 2020, and the stability analysis is somewhat based on Bousquet & Elisseeff, 2020. Can the authors clarify here what is challenging when extending to the MAML training? \n\nIn summary, I think this paper takes a good step to study the generalization of MAML, and it involves some novel characterizations, e.g., eliminating the dependence on $K$ for the total variation distance characterization via the maximum coupling in Hollander, 2012. Although the derivations in this paper may contain new treatments, I do not find the results interesting or exciting and the experiments are not sufficient to verify the generalization of MAML in broader applications. To attract more people form this meta-learning area,  I feel these bounds are not sufficient and more efforts should be taken, e.g., to show that such total variation bound has a tight impact on the generalization of MAML. Therefore, I tend to weakly reject this paper, but I am open to increase my score based on the authors’ feedback and other reviewers’ comments.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "nQkcY8z5bc9", "reviewer": "Reviewer_UMVa", "summary": "The paper provides a generalization analysis of MAML. Based on a new definition of stability of meta-learning, it characterizes the generalization error on seen and unseen tasks.\n", "questions": "", "limitations": "", "rating": 6, "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": "Please address the following concerns:\n- The results in Theorem 2 and Corollary 2 both show that the generalization error increases for a larger K (the number of shots). This conflicts with the experiment results in MAML or other meta-learning papers. So I have a major concern about whether the bound is vacuous. Moreover, it would be better to empirically verify the effect of K. \n- The theoretic results of Theorem 2, i.e., the generalization error of seen tasks, are not empirically studied. It would also better to provide some simple experiments to verify it.\n- The equation in line 569 seems not so straightforward. The loss of the i-th task is not only affected by the replacement of K data points in $S_i^n$, but also affected by the replacement of data points in $S_j^n (j \\neq i)$. So I wonder whether expectations of $w_S$ and $w_\\tilde{S}$ are the same.\n\n****************************************************After Rebuttal**********************************************\n- While I am satisfied with the response to the assumption of strong convexity and smoothness, I am still not convinced by the response to my major concern regarding $K$. \n     - When $K$ is small which is usually the case in meta-learning, this bound is as loose as SGD. In this case, why do we need meta-learning?\n     - Only when $K$ is as large as possible (Appendix E), the error decreases as $K$ increases. In fact, according to the bound, if the total number of samples across all tasks is $1M$, $K$ has to be even as large as $\\sim10,000$, which is rarely practical in meta-learning.\n\nIf the latest discussion by the authors can be included, I tend to increase the score to \"weakly accept\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The assumption of strong convexity and smoothness is very strong and does not hold for most neural networks. The authors have not fully addressed such limitation.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "UG9mF0WKqst", "reviewer": "Reviewer_acnS", "summary": "This paper analyzes the generalization bound of MAML-type algorithms from two aspects: (1) when the test task is a sample from the training tasks and (2) when the test task is unseen during training stage. A generalization bound on strongly convex case is given in case (1) showing the generalization error is deceasing at a rate of $O(1/mn)$. On the other hand, a bound under the total variation assumption is given in case (2), showing the bound depends on the average total variation between all the training tasks and the unseen task. The paper focuses on theory and thus no experiments are included.", "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": "Overall I think this is a good paper, because it provides the generalization bound in terms of data points in the homogeneous case, and a total variation based analysis in the heterogeneous case. I didn't check all the proof line by line, but the key results make sense to me and are, to my best knowledge, new in the literature.\n\nRegarding the technical parts, I have two concerns:\n\n1. The authors state in line 292 Remark 2 that in the analysis of recurring tasks case, strong convexity is assumed because \"The algorithmic stability technique is mainly limited to the convex setting.\" This seems a little off to me, because algorithmic stability has been studied in several previous works. For instance, Section 3.5 of (Hardt et al., 2016; https://arxiv.org/pdf/1509.01240.pdf), (London, 2017; https://arxiv.org/pdf/1709.06617.pdf), (Zhang et al., 2020; https://arxiv.org/pdf/2002.11875.pdf), etc. It seems the divergence comes from a different notion of stability proposed in the paper, which captures the number of data points per task. But I don't see how such definition would prevent the analysis on non-convex problems. Could you elaborate why the non-convexity assumption is challenging based on the stability notion in your case? Maybe an example would help.\n\n2. A minor concern: In many previous works analyzing MAML-type algorithms, a bilevel structure is established (which is closer to how we do meta-learning in reality). For instance (Ji et al., 2020;https://arxiv.org/pdf/2006.09486.pdf) analyzes the convergence, etc. I wonder how the results in this paper would adapt/be applicable to the bilevel case? In bilevel programming, the stability analysis is not new(https://arxiv.org/pdf/2106.04188.pdf), do you see any challenge there?\n\n**Updates**\nI've read the author response and I think the authors adequately answered my question regarding difficulty in relaxing the results to the non-convex case. I encourage the authors to include the discussion into the paper so as to make it clear.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No limitation or potential negative societal impact is shown.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "MwSwYK3Aekn", "reviewer": "Reviewer_aLZn", "summary": "This paper studies the generalization properties of MAML in the strongly convex setting. It's assumed that there are $m$ training tasks, each with $n$ samples, and the inner loop adaptation is one step of SGD using $K$ samples. It's proved that if the new task is a uniformly random task from one of the $m$ training tasks, MAML incurs a generalization error of $O(\\frac{K}{mn})$; if the new task is an unseen task, the error depends on the TV distance between the new task distribution and all the training task distributions as well as their average. The analysis is based on a modified version of algorithmic stability tailored to the MAML setup.", "questions": "", "limitations": "", "rating": 4, "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": "Originality: The contribution of this paper is new. The paper obtains an $O(1/mn)$ bound in the strongly convex setting, while the previous result in [25] is $O(1/m)$ (though [25] covers non-convex losses). The proof technique is based on algorithmic stability but also needs nontrivial modification.\n\nQuality: The paper is technically sound. The results are clearly stated and discussed.\n\nClarity: The paper is clearly written and well organized.\n\nSignificance:\n- I think the most interesting result is the $O(1/mn)$ error bound for \"in-task generalization\", i.e., generalizing to a random training task. The previous bound for MAML is only $O(1/n)$ in [25]. To obtain the $O(1/mn)$ bound, a new type of stability (Definition 3) is required, which is non-trivial.\n- However, I believe the result of generalization to an unseen task (Theorem 3) is very loose and does not capture the actual interesting aspects of meta-learning. Essentially, for this bound to be small it requires the new task distribution to be very close in TV distance to all the training tasks as well as their average. However, this is almost never the case. For example, suppose that all the tasks are drawn i.i.d. from a meta-distribution over tasks (which is usually true in a lot of few-shot learning benchmarks). Then $p_1, p_2, \\ldots, p_{m+1}$ could all be very different from each other, but we can still expect MAML to generalize well to $p_{m+1}$, since it's a task drawn from the same meta-distribution. The bound provided in the current paper dramatically fails to capture this.\n- The strong convexity is certainly very restrictive, and it's noted that the technique used in the paper cannot generalize beyond the convex case. That said, this is understandable and acceptable as a first step for theoretical purpose. \n\nOther questions:\n- The paper only considers 1-step SGD adaptation in the inner loop. Is there any hope to generalize the result to multiple steps?\n- It seems that a somewhat non-standard data splitting procedure is used, i.e. first splitting the data into $S_i^{in}$ and $S_i^{out}$ each with size $n$, and then the samples used for inner and outer loops are sampled from these two subsets. How important is this in the theoretical analysis and is it unavoidable?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As noted in the main review, I believe the generalization result to an unseen task is very loose and can be misleading. A discussion of this is needed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "MBNrNQDAzCC", "reviewer": "Reviewer_xQuq", "summary": "The paper analyzes the generalization error of MAML in 2 scenarios that are different in the new tasks at test time which are (i) the training tasks and (ii) unseen tasks, under the assumptions that the loss function is (strongly) convex and the number of steps of SGD in the adaptation step of MAML is 1. In the former case, this work proposes a new notion of stability that is capable of capturing the dependence on the number of data points per task in the bound. In the latter case, this work formulates a generalization error bound based on the total variation distance between the distribution of the new task and those of the training task.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "(originality & significance) I think that the paper presents an improved result over the existing work and other new theoretical results. In particular, it proposes a new notion of stability to construct a generalization error bound that depends on the number of data points per task, which allows a tighter bound compared with an existing work. It also proposes a new approach of using the total variation distance to analyze the generalization bound when the task at test time does not come from the training tasks.\n\n(quality):  The main weaknesses of the analysis is in the assumption of the convex loss function because MAML is often used to learn a deep neural network whose loss is non-convex. Therefore, the implications of such analysis to the real applications of MAML remain unknown. However, I acknowledge that the paper justifies this weakness in Remark 2. Another limitation is about the restriction of the number of SGD steps in the adaptation of MAML. The paper could be improved by mentioning the implications (or challenges) when the number of SGD steps in the adaptation of MAML is larger than 1.\n\nThe paper is generally well-structured and well-written. There are only very few minor typos: \n* Assumption 1(ii): “unbounded”.\n* Line 196: “from [1]” should be from [24] if I’m not wrong.\n* Line 218: “deferentially private” should be “differentially private”.\n* Lines 286 and 287: “k” should be “K”.\n* Title of section 3.3: “Task” is capitalized.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "43xpv0lQlE", "reviewer": "Reviewer_xD4r", "summary": "The authors present generalization bounds for MAML when test tasks are the same as the ones seen during training (recurring tasks) or when they are different but sampled from the same distribution (unseen tasks). The main takeaways are a. for recurring tasks, the excess population loss is bounded by O(1/mn) with m the number of tasks and n the number of data points, and b. generalization to unseen tasks depends on the distance (total variation) between train and test task distributions.", "questions": "", "limitations": "", "rating": 7, "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 results of the paper are novel and of interest to the multi-task/meta-learning community. In particular, the generalization result for recurring tasks (Th. 1 & 2) refines multi-tasks bounds for MAML when data is limited. This is important since limited data is often the main motivation for these types of meta-learning methods. While the approach to get those bounds builds on the stability of SGD, the proposed stability definition is tailored to MAML and lends itself to further study and extensions. The second result (Th. 3) directly targets transfer to new tasks, formalizing one of the main intuitions behind MAML: the closer the train and test tasks, the most effective the transfer. To the best of my knowledge, this is the first work directly assessing generalization for MAML when train and test task sets are disjoint.\n\nIt helps that the paper is clearly written and introduces all necessary background to MAML. For each theorem, assumptions are clearly stated and the results are discussed from both a theoretical and practical perspective. Although a bit dense, I enjoyed reading this paper.\n\nThe main limitation of the paper is convexity of the meta-learning loss — but similar publications also considered this setting. Specifically, I would like to see the assumptions on the fast-adaptation learning rate (alpha) relaxed, since they are rarely met in practice.\n\nFinally, I wished the related work section were a bit more expansive. For example, issues of generalization were also considered in [1], and [2] discussed issues related to the number of samples per tasks. How does the present work differ?\n\nReferences:\n\n[1] \"Global Convergence and Generalization Bound of Gradient-Based Meta-Learning with Deep Neural Nets\", Wang et al., ArXiv 2020.\n\n[2] \"How to distribute data across tasks for meta-learning?\", Cioba et al., ArXiv 2021.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are clearly stated, societal impact is not mentioned.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This learning-theory paper used stability approach to study the generalization properties of Model-Agnostic Meta-Learning (MAML).  The rate of $O(1/mn)$ for strongly convex objective in the homogeneous setting is the first-ever known result for meta learning and greatly improves the existing results.  For the heterogeneous setting, the generalization was proved using the total variation distance between the data distributions of this unseen task and the training tasks.  As far as I can see from reading through the proof techniques, it is indeed solid and non-trivial. 

There are various concerns about strong-convexity and smoothness assumption for stability analysis which were well responded and explained in the rebuttal.  It should be included as a discussion on the limitation of stability analysis in the final version.  I would also particularly encourage the authors to include discussions on other concerns raised by the reviewers such as the generalization bound related to K and the appropriateness of using the TV metric for deriving generalization on unseen tasks for meta learning etc. 
Decision: Accept (Poster)