Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

Regarding the technical parts, I have two concerns:

1. 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.

2. 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?

**Updates**
I'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.
limitations_and_societal_impact: No limitation or potential negative societal impact is shown.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

main_review: Please address the following concerns:
- 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. 
- 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.
- 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.

****************************************************After Rebuttal**********************************************
- 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$. 
     - 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?
     - 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.

If the latest discussion by the authors can be included, I tend to increase the score to "weakly accept".
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.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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.

Pros:
1.	This 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. 
2.	Studying 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. 
3.	This paper shows that the sample number for the intra-task training is also important and can be used to further reduce the generalization error. 

Cons:
1.	My 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. 
2.	My 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.
3.	The  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? 

In 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.  
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

It 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.

The 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.

Finally, 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?

References:

[1] "Global Convergence and Generalization Bound of Gradient-Based Meta-Learning with Deep Neural Nets", Wang et al., ArXiv 2020.

[2] "How to distribute data across tasks for meta-learning?", Cioba et al., ArXiv 2021.
limitations_and_societal_impact: Limitations are clearly stated, societal impact is not mentioned.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

(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.

The paper is generally well-structured and well-written. There are only very few minor typos: 
* Assumption 1(ii): “unbounded”.
* Line 196: “from [1]” should be from [24] if I’m not wrong.
* Line 218: “deferentially private” should be “differentially private”.
* Lines 286 and 287: “k” should be “K”.
* Title of section 3.3: “Task” is capitalized.

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.
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.

Quality: The paper is technically sound. The results are clearly stated and discussed.

Clarity: The paper is clearly written and well organized.

Significance:
- 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.
- 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.
- 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. 

Other questions:
- The paper only considers 1-step SGD adaptation in the inner loop. Is there any hope to generalize the result to multiple steps?
- 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?
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_title: null

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)