Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies overparametrized representation learning in meta-learning, i.e. representation dimensionality (R) is larger than number of samples ($n_2$) per task. It does so in the setting of linear representations, but goes beyond existing analyses that typically assume that the covariance of task regressors to be low rank and restrict representation dimensionality to be small. The paper characterizes the optimal representation for every dimensionality R (in an asymptotic regime), observes a double descent phenomenon w.r.t. R in the performance of the representation on test tasks, also concludes that the optimal dimensionality can be overparametrized in many cases. It then analyzes the sample complexity of learning such a representation with finite train tasks samples, and finds that choosing R adaptively with number of samples can strike a balance between bias and variance of the representation. An important phenomenon of alignment of feature covariance and task covariance is introduced and its effect on sample complexity and optimal dimensionality is studied. Experiments on simulated data verify some of findings and the presence of the alignment is observed on some real datasets (MNIST, CIFAR).
main_review: Originality:

This paper meaningfully extends the linear representation learning by studying the role and need for high dimensionality of representations when the features and tasks are not exactly low rank, unlike recent analyses that make such a low rank assumption. It makes good use of previously employed asymptotic analysis for regularized linear regression. I found the discussion and comparison to previous work adequate. A relevant work is [1] that also analyzes high dimensional representations for (overparametrized) meta-learning, but relies on gradient dynamics to automatically uncover the underlying subspace structure.

Quality:

The results seem believable from a skim over the proofs. I didn't verify all the details, especially for the closed form expression in Theorem 1. Technical claims are supported by proofs in the appendix and with simulation experiments in some places.

Clarity:

I found the paper mostly clearly written and easy to follow. I found the discussion before Theorem 2 a bit clunky (line 260-276), since $s_F$ and $s_T$ are only defined in Table 2. I would encourage the authors to rework this part a bit.

Significance:

The paper analyzes more general and realistic settings than those analyzed in previous work on meta-learning linear representations and explores the benefit of covariance alignment in sample complexity. The main contribution is theoretical and it does not necessarily provide any practical algorithmic suggestions. It needs to make simplifying assumptions in some cases, like asymptotic analysis, eigenspace alignment and linear representations, but these do not significantly dilute the conceptual contribution in my opinion.


Additional comments:

- L84: Is DoF degree of freedom? not defined anywhere

- L194: p=R?

- L242,243: Something seems off in the alignment metrics. canonical-identity alignment is equal to 1/d in the way it is defined currently



---------------------------------------------------------------------------------------------------------------------
**Post rebuttal**: I thank the authors for their many responses to reviewer concerns. After reading everything and the reviewer discussions, I am inclined to retain my recommendation of accept (7). I think providing some more details and highlighting the conclusions from Fig 1(a) and 1(b) even later in the paper will help. One of the major concerns raised by other reviewers (which I agree with) is the clarity of the paper. More specifically, Theorem 1 can afford to be written much more clearly, especially the part about how the limit of $n\_2\rightarrow\infty$ is taken. The author response provides a lot of clarification in this regard, but I think it can be improved even further, e.g. the statement "the joint empirical distribution $\frac{1}{R} \sum_{i=1}^{R} \delta_{\Lambda_{R_i}, \tilde{\Sigma}^R_{T_i}}$ converges to a fixed distribution" seems very important but is inadequately discussed. Many readers of this paper will not be familiar with the kind of asymptotic results and analyses presented in this paper, so it will help to clearly explain how the limits are taken, why an asymptotic analysis is needed, and what the results mean for the practical case of finite $d,n\_2,R$. Also, some of the empirical verifications with CIFAR-10 and MNIST and a good suggestion made by another reviewer in the discussions was to extend this analysis to more few-shot learning based datasets. Personally I think that these changes are not too drastic to change my opinions about the paper.


[1] N. Saunshi, Y. Zhang, M. Khodak, S. Arora. ICML 2020. A Sample Complexity Separation between Non-Convex and Convex
Meta-Learning.
limitations_and_societal_impact: Limitations of the work are discussed in Section 6.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper presents an analysis of the role of representation width when learning a shared feature extractor across multiple tasks. The authors argue that wider representations improve transfer, even when only a small number of labelled examples are accessible to fine-tune the last linear layer of a neural network. Their theoretical analysis focuses on linear regression with a linear feature extractor, with most experiments also on this setting.
main_review: Strengths:

The message of the paper is interesting and relevant to the few-shot learning community. In particular, a thorough study of width in meta-learning is novel and welcome. 

Weaknesses:

- Simplified analytical setting: the authors only consider linear regression with a shared, linear feature extractor. Although linear regression has been used in prior work, some more recent theoretical works have shifted towards the more general convex (and sometimes non-convex) setting. See for example [1, 2]. Since linear regression induces a quadratic optimization problem, I am concerned that the proposed approach won't be easily extended to those settings.
- Lack of real-world validation: On top of the simplified analytical setting, theoretical insights are never validated on real-world datasets. Hence, I wonder if those insights carry over to real-world applications. Taking classification tasks as an example, it is well-known that nearest-neighbor classifiers (like ProtoNet) tend to work better with lower-dimensional representations, while SVMs work best with larger representations.
- As a minor remark, I think this paper would benefit from a reference to R2D2 [3] who obtain excellent classification results with a deep feature extractor and ridge regression classifier (but don't say anything about representation width). Their method could also be used to address the lack of real-world validation.

References:

[1] "A Theoretical Analysis of the Number of Shots in Few-Shot Learning", Cao et al., ICLR 2020.

[2] "On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms", Fallah et al., AISTATS 2020.

[3] "Meta-learning with differentiable closed-form solvers", Bertinetto et al., ICLR 2019.
limitations_and_societal_impact: 1 paragraph on limitations, none on societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the role of overparameterization in meta representation learning.

Meta-learning studies how to learn from previous tasks to adapt quickly to new ones, while overparameterization studies the settings where the number of training points is smaller than the number of features. Recent works studied the generalization properties of meta-learning a linear representation but did not focus on the overparameterized setting, where the number of training samples per task is lower than the dimension of the meta-learned representation.

This work presents asymptotic results on the expected risk in the overparameterized regime. Furthermore they propose an algorithm to learn a linear representation together with sample complexity bounds. They also provide some empirical results validating their analysis.

main_review: I anticipate that I am not very familiar with theoretical results in meta representation learning and overparameterization. I apologize if I misunderstood crucial parts of the work and in that case I am willing to increase the score after the discussion.

1. I found the paper hard to read. Some crucial symbols are introduced without definition or are inconsistent. Theorems and algorithms are poorly explained. Contributions and most of the experiments are also unclear. 

2. I do not think Theorem 1 (crucial part of the work) is meaningful. It is also not explained well. Usually an upper bound on the risk is provided and then limits are taken. Theorem 1 seems to skip the first part. Furthermore, with fixed $\kappa = \frac{R}{n_{2}}$ . if you take the limit for $n_2 \to \infty$ in 3.4  also $R \to \infty$  and the left hand side of (3.4) is 0 if the risk is bounded. Also it seems that the matrices will have infinite rows and columns in the limit.

3. The authors do not mention [A, B] which also provide learning guarantees with meta-learning of a linear representation.

#### **Final Score**
4. I am giving this paper a 4. I think the problem that the authors are tackling is potentially interesting. Overparameterization probably plays a big role also in meta-learning. However I think the quality of the work is far from being sufficient for acceptance.

#### **Additional comments**

5. Close to line 37: how is training on cifar 10 in Figure 1(a) done? only the last layer is trained or all the weights are fine-tuned? I would write this here.

6. line 62: I think saying that the linear representation mapping throws away features is wrong. It just weighs them.

7. I found the contributions section quite heavy in terms of loosely defined notation and references to future sections.

8. Line 244-247 are not clear

9. Line 52: I think the term “underparametrized” is used in the wrong way here. The model the related work studies has input dimension higher than feature dimension $d < R$ while $R$ could still be (and often is) higher than the number of samples per task $n_2$, which would make it overparameterized in the sense meant by the authors.

10. Observation 2 is not proved anywhere (not even in the supplementary).

#### **Update**
After the discussing with authors and reviewers I better understand the purpose of Theorem 1. However I am still unsure on the significance of the presented results and I still think the paper lacks clarity. I increased my score from 4 to 5.

#### **References**

[A] G. Denevi, C. Ciliberto, D. Stamos, and M. Pontil. Incremental learning-to-learn with statistical guarantees. In Proc. 34th Conference on Uncertainty in Artificial Intelligence (UAI), 2018.

[B] G. Denevi, D. Stamos, C. Ciliberto, and M. Pontil. Online-within-online meta-learning. In Advances in Neural Information Processing Systems, pages 13089–13099, 2019.

limitations_and_societal_impact: The authors discuss limitations in the conclusion section. I can not tell if the list is exaustive.

The work does not have potential negative societal impact since it is mostly theoretical.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the representation learning for multi-task linear regression problem in the setting with arbitrary feature covariance, arbitrary task covariance, and arbitrary representation dimension. In this setting, it aims to address two questions: (1) given a set of $T$ linear regression tasks with $N$ total samples, what is the optimal representation $\Lambda \in \mathbb{R}^{d\times R}$ for a downstream few-shot linear regression task? and (2) what is the sample complexity for finding this representation? To address these questions, the authors find a closed-form solution for the optimal representation when the fine-tuning phase involves an eigen-weighting procedure, which they argue introduces an inductive bias that enables few-shot success. They show that the key to estimating this optimal representation is estimating the "canonical task covariance", which they show necessitates a number of samples growing with the effective ranks (traces) of the task and feature covariances, rather than the ambient dimension $d$. The authors also provide an overall risk bound that shows it is preferable to have smaller $R$ for smaller $N$.

main_review: Strengths:

1. The introduction is mostly clear and does a great job of motivating the linear setting.

2. To the best of my knowledge, arbitrary task covariance had not yet been considered for linear multi-task representation learning, so the dependence of the excess risk on the canonical task covariance is a new result.

3. Showing that the sample complexity grows with the effective ranks of the covariance matrices rather than the ambient dimension is a nice result.

4. The analysis is rigorous and certainly non-trivial. The proofs are correct as far as I could tell.

5. Understanding over-parameterization in representation learning is a highly relevant problem.

Weaknesses/Questions:

1. After the introduction I found this paper very difficult to understand, which leaves me with numerous questions about its contributions (see below). The writing can be significantly improved, both in terms of fixing typos and more importantly, giving more simple and clear explanations of the results. I found the interpretations of Theorems 1 and 3 especially lacking, since they involve highly non-intuitive expressions yet very little explanation was given of them.

2. Regarding Theorem 1 and eigen-weighting: what is the point of the eigen-weighting? How do the results compare to the case in which standard linear regression is executed in the few-shot phase instead? Do any insights from eigen-weighting generalize beyond linear models? I get that eigen-weighting is itself an inductive bias, but I am not sure how this inductive bias helps... right now it seems to only complicate the problem, making the optimal representation (in Theorem 1) non-intuitive and only computable in closed form under that restrictive assumptions that $n_2 \rightarrow \infty$ and the feature and task covariances are simultaneously diagonalizable.

3. Regarding Theorem 2 and surrounding text: $s_F$ (and $s_T$) should be defined outside of the Theorem 2 so that it is clear what they are when you refer to them multiple times outside of the theorem. There should also be some accompanying intuition for this definition. It is also not clear why the relationships between $r_F$ and $s_F$, and $r_T$ and $s_T$ hold in Table 2.  Further, you have introduced $\iota$ in Example 1, but it does not appear in the bound which does not make sense. 

4. Regarding Theorem 3: how does $\theta_{-}$ scale, and how can $\Lambda_{\theta_{-}}(R)$ be computed (do you compute the representation using the constraint that its minimum singular value is lower bounded by $\theta_{-}$, or is $\theta_{-}$ evaluated after the fact)? It is not clear that "representation learning error increases with $R$" from the result. Also, the risk becomes negative when $R > n_2$, is there a missing assumption?

5. I am doubtful of the novelty of many of the contributions of this paper compared to [1], which also provides bounds for the linear representation learning + few-shot learning problem in the over-parameterized setting with arbitrary feature covariance, and obtain a bound that depends on effective rank, not dimension (see Theorem 6). The authors do not mention this result in the current work.

6. It is repeatedly stated that [2] gives a sample complexity of $dr^2$, but this is only true under the assumption that the minimum singular value of the task covariance matrix is $O(1/r)$. If it is $O(1)$, then [2] achieves $dr$. The authors need to mention this in the update and do a fair comparison with clear assumptions on the task covariance matrix.

Overall: This paper is promising, but at this point I have too many questions and concerns to recommend acceptance.

[1] Du et al. Few-Shot Learning via Learning the Representation, Provably. 2020.
[2] Tripuraneni et al. Provable Meta-Learning of Linear Representations. 2020.

----------------------

Post-rebuttal: I thank the authors for their thorough response. They have helped me to better understand the results of the paper, and also resolved my concerns about comparisons with [1] and [2]. I believe this is an important result, but the clarity of the paper can be significantly improved in order for the result to be fully appreciated. I have raised my score to a 6.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This paper studies overparameterization for meta-learning in the setting of linear-regression tasks. It answers the questions about the optimal linear representation of features for a new downstream task and the number of samples needed to build this representation. The reviewers are quite diverse at the beginning and raised a number of questions, with one of the main criticisms being on the clarity of Theorem 1. The authors have done a good job at replying the reviews, and the reviewers also have done a good job at discussing the rebuttal. Finally, the originally negative reviewers are able to converge to the borderline and the positive reviewers maintained their scores. I propose acceptance of this paper due to the important contribution of demonstrating overparameterization to meta learning. However, I highly recommend the authors to take the comments from the reviewers and revise the paper carefully for its final version. It would make the paper even stronger if the revision can somehow address the following question raised in the discussion: it is expected the paper can provide either stronger empirical verifications (MNIST and CIFAR100 in the appendix are non-standard in FSL) or for theory beyond linear regression case.
Decision: Accept (Poster)