Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.

Overall, 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.
strengths_and_weaknesses: **Strengths**
1.  This paper is clearly written and easy to follow.
2.  The proofs of the main results are complete.
3.  MAML is a popular meta-learning method and theoretical analysis on it is also important to the ML community.

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

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

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

4. Can the results be generalized to other machine learning methods beyond the linear regression, such as neural networks?

Chen et al., A Closer Look at the Training Strategy for Modern Meta-Learning, NeurIPS 2020  
Fallah et al., Generalization of Model-Agnostic Meta-Learning Algorithms: Recurring and Unseen Tasks, NeurIPS 2021  
Collins et al., Why Does MAML Outperform ERM? An Optimization Perspective, ArXiv 2020   
questions: I hope the authors can clarify some of my concerns. But if I am wrong, please correct me.
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:

1. The paper is very well written and organized. Following it was straightforward.
2. The authors use some settings which correspond to real world applications (L46)
3. 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. 
4. The leading and tail spectrum space analysis is very interesting and well developed.

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

questions: None
limitations: There are no limitations with regards to negative societal impacts.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
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. 

questions: See above. 

1. How exactly does the theory generalise to the meta-batch setting. 
2. I might have missed this but why do you have to use the iterative averaging instead of using the final w_T?
3. Can you comment on how to extend the theory for longer inner loops.  

limitations: The authors do not explicitly discuss the limitations of their work, although I agree that this is not needed here.
review_title: null

Meta-review: metareview: This paper explores the generalization of SGD, as used in a MAML-style algorithm for meta learning in an overparametrized setting. The generative model considered is  "mixed linear regression", in which tasks follows a linear + Gaussian noise data model (a different direction per task, with minimal assumptions on the distributions for the directions --- precisely, the mean and covariance of the distribution). Overparametrization means d >> T, where d is the dimension of the vector of parameters, T is the number of tasks. The main conceptual takeaway is that there is a "phase transition" effect depending on what the step size is, and whether the risk decays as $T \to \infty$ --- depending (in a fairly complicated way) on various quantities, perhaps most interestingly a notion of "task diversity" (captured through the covariance of the direction for the tasks). The proof techniques largely follow [Zou et al '21] which considers overparametrization for SGD in just the case of linear regression --- which involves a bias/variance decomposition and a series of concentration bounds to bound each respectively. Since data coming from different tasks has a different SVD, this makes the proofs non-trivial to extend.


confidence: Certain
Decision: Accept