Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper provides a theoretical analysis of meta-learning by proposing a generalization bound and an upper bound of the optimization error. For comparison, this paper studies three settings, the meta-learning setting under which the representation layers' parameters and the task specific layers' parameters are optimized in the inner loop around a learned initialization, a 'frozenrepresentation' setting under which the representation layers' parameters are never updated during the inner loop and the only learning target task setting. 
main_review: The theoretical analysis is novel and interesting. The performance bound of learnability is solid including both the upper bound of the generalization gap and the upper bound of the optimization error. For the implications of the theoretical analysis, the results show that the 'frozen representation' setting fails under weaker assumptions.
limitations_and_societal_impact: The notations are a little hard to follow. It will be better to simplify and clarify the notations.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work presents a theoretical framework to study MAML-like algorithms, where the representations are not identical but similar to some degree. The theoretical investigation was done in the linear and non-linear settings, with an application to two-layer NNs. Risk bounds were obtained in both cases. 
main_review: Overall this is a good theory paper, and mostly well-written.
limitations_and_societal_impact: Pros:
1. This paper provides a theoretical framework for MAML-like algorithms. The theory considers both linear and nonlinear settings and risk bounds were obtained.
2. The frozen-type algorithm is shown to perform badly under the model assumed in this paper.

Cons:
1. The non-linear case is less well-studied.  Assumption 4.1 puts a bound B on l(0,y). This assumption seems restrictive and is even not satisfied by the simple linear regression model when y=x^T beta+eps with x and eps being Gaussian. Is it possible to relax it to be a high probability bound?
2. Any assumptions on the distribution of x and y|x for the nonlinear setting?  
3. In Theorem 4.1, are there any convergence guarantees of the PGD? For example, an upper bound on the number of iterations? 
4. The RHS of Theorem 5.1 should depend on delta, but it's missing.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors provide a statistical understanding of the benefit of fine-tuning in meta-learning (e.g., MAML does not fix the inner representation but tries to fine-tune parameters for all tasks) over the current wisely-used approaches with shared embedding model (i.e., “frozen representation” as called in this paper). In specific, the authors focus on the setting where the ground-truth representation parameters are not the same for all tasks, i.e., no common representation exists for all tasks, and provide the excess risk bounds for the proposed fine-tuning scheme in the linear setting, nonlinear setting and two-layer neural networks. One interesting thing here is that they show that given infinite many source samples, there exists a task distribution such that the frozen representation scheme will have a risk lower bounded by \sigma^2d/n_T, whereas the fine-tuning scheme has an upper bound of  \sigma^2d/n_T, and hence exhibit a fundamental separation between these two types of schemes (of course in this setting, fine-tuning is better).

main_review: In this paper, the authors provide a statistical understanding of the benefit of fine-tuning in meta-learning (e.g., MAML does not fix the inner representation but tries to fine-tune parameters for all tasks) over the current wisely-used approaches with shared embedding model (i.e., “frozen representation” as called in this paper). In specific, the authors focus on the setting where the ground-truth representation parameters are not the same for all tasks, i.e., no common representation exists for all tasks, and provide the excess risk bounds for the proposed fine-tuning scheme in the linear setting, nonlinear setting and two-layer neural networks. One interesting thing here is that they show that given infinite many source samples, there exists a task distribution such that the frozen representation scheme will have a risk lower bounded by \sigma^2d/n_T, whereas the fine-tuning scheme has an upper bound of  \sigma^2d/n_T, and hence exhibit a fundamental separation between these two types of schemes (of course in this setting, fine-tuning is better). My detailed comments are given as follows.

Pros:
1.	This paper provides interesting results on showing that the commonly-used frozen representation schemes may suffer from a performance loss (in terms of generalization) when the assumed common representation does not hold, whereas the fine-tuning approaches allow the differences among such representations (up to some small gaps). Although this is intuitive, this paper provides a rigorous analysis for such a phenomenon. 
2.	The results for nonlinear and neural networks seem to be nontrivial and the empirical results support the theories. 

Cons:
1.	This paper is mathematically intense and not very easy to follow. For example, it is not clear to me (at least from the context) why the authors use A_{B_0}=[B_0 B_0] in (5) rather than B_0 as in [4]? Is this because such a parameterization fascinates the analysis? I wish the authors may have an explanation here. In addition, I do not find the definition of krs(ns,T) in Section 3.3, which seems to be an important quantity as it will diminish with the sample size ns. I believe a more detailed explanation and discussion on this quantity will help the reading. 
2.	In line 187, the first two terms are of norm O(1/\beta) and the third coupling term is of norm O(1/\beta^2) based on the definition of C_\beta. I guess the authors may miss a \beta factor in the definition of \theta. Should  it be \theta = \beta(A_{B_0}w+\Delta w_0+\Delta w) ?   

Overall, I think this paper contains interesting results on the separation between fine-tuning and frozen representation. I wish the authors can address my concerns in the response. 

limitations_and_societal_impact: Yes
review_title: null

Meta-review: The paper studies the statistical aspects of meta-learning, building on the recent work of Tripuraneni et al., and Du et al. The main advancement is to consider fine-tuning on both the source and target tasks, rather than a fixed representation that is adequate for all tasks. Statistically this provides much more flexibility, and as the authors show, it can provably outperform the fixed-representation approaches in some settings. It also more closely matches what is done in practice. 

The results in the paper are fairly interesting although the paper is quite dense. In particular, I appreciated how the optimization aspects are incorporated into the analysis, to capture how fine-tuning leads to a non-convex optimization problem. This enables an apples-to-apples comparison with the fixed-representation approach. The main weakness raised by the reviewers was that the paper is quite hard to read. I agree to some extent, but still I think the paper should be accepted. 
Decision: Accept (Poster)