Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: **Summary**: 
This paper analyses the statistical and computational properties of one particular type of meta-representation learning approaches, which alternatively optimises a shared feature extractor that produces linear representations, and solves inner task-specific linear models taking in the shared linear representations. Under the canonical settings when the feature extractor is linear, they show that the meta-representation learning algorithm can achieve near optimal error rate.

**Contributions**:
- This paper analyses one family of widely adopted meta-representation learning algorithms they call AltMinGD, and prove a near optimal error rate, following the proof strategy for matrix sensing (which is still significantly different from the linear meta-representation learning problem).
- This paper introduces a new variation of AltMinGD-S, motivated by their analysis. The new algorithm selects a subset of well-behaved tasks at each iteration, and requires a much smaller number of samples per task to estimate representation.
- This paper also analyses a variation called AltMin (in appendix) where the outer loop feature extractor is optimised exactly, and proves slightly improved guarantees.


main_review: **Originality**: 
Although there are previous theoretical studies trying to analyse the statistical and computational properties of meta-representation learning algorithms, they often focus on algorithms that have little resemblance to those used in practice, or provide a highly suboptimal error rate. This paper focuses on one particular type of algorithm called AltMinGD, which is successful and popular among previous work. They show that in the canonical setting when the learned shared representation is linear, their analysis of this algorithm would give a near-optimal error rate.

Even though the proving strategy is inspired by those from matrix sensing. The two problems are significantly different, and this paper proves all necessary concentration bounds.

They also introduce a new variation called AltMinGD-S that would require much fewer samples per task and analyse this new algorithm.

**Quality**:
This work has clear motivation and I think they are tackling an important problem with practical implications. However, I am not familiar with related work and the theoretical work on meta-representation learning, I am afraid I cannot comment more on the quality of their analysis. 

I would like to only highlight one of my concerns below. I would appreciate it if the authors could give an explanation: If I understand correctly, many previous work on meta-representation learning such as MetaOptNet, ANIL, etc, actually backpropagate through the inner loop minimisation when updating their feature extractors. However, in this paper, (if I am not mistaken), the algorithms *alternatively* optimise the feature extractor and solve the inner loop optimisation for each task. When computing the gradient w.r.t the feature extractor parameters $U$, do you consider the fact that the optimal inner parameter $V^{\ast}$ is actually dependent on $U$ , and compute gradients accordingly? If yes, I have no further concerns. If not, could the authors discuss whether this difference might lead to different conclusions in their analysis?

**Clarity**:
The motivation and assumption of this work are clear and well presented. The theoretical analysis part is intense if the reader did not read background references, but I think the authors have already put effort into making it clear.

**Significance**:
I believe this paper is tackling an important problem of meta-representation learning that is of practical relevance. The conclusions and proof strategy presented in this work can also be useful for future work.

limitations_and_societal_impact: **Limitations**:
This paper is under a simplified setting where the shared representation is linear, and all tasks are considered when updating the feature extractor (non-stochastic optimisation). But I think the conclusions are still useful, and these are sensible simplifications as a first work to analyse this algorithm.

**Societal Impact**:
This is a theoretical work and I have no concerns over its negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper provides sample complexity and error bounds for “alternating gradient descent minimization” (AltMinGD), an algorithm used for meta-learning. It shows that AltMinGD applied to linear regression is superior to competitors such as Empirical Risk Minimization (ERM) and Method of Moments (MoM). Furthermore, they show that the bounds are tight and basically cannot be improved upon.

main_review: Even if results apply to linear representations only, I find this work very compelling and useful.
In the last couple of years, increasing evidence shows that linear meta-representation learning is a very useful and tractable framework to understand meta-learning, and to gain some intuition about the phenomena observed in more complicated (non-linear) contexts.  
The paper is well written and I think it can be published in its current form.

I only have a couple of clarification questions:
1) By assumption the matrix U is orthogonal. My understanding is that AltMinGD enforces orthogonality of U by a QR decomposition at the end of training. This step is not even mentioned in the text and it seems very brute force. How important is the assumption of orthogonal U? Why doesn’t the QR last step ruin the representation obtained during training?
2) What is the intuition behind the superior performance of AltMinGD with respect to ERM and MoM?

Other comments:

- A number of papers about meta-learning and linear regression have been published recently that the authors have not considered: https://arxiv.org/abs/2102.00940, https://arxiv.org/abs/2010.05843, https://arxiv.org/abs/2010.12916, https://arxiv.org/abs/2010.14672
- In line 124 (Assumption 2), the condition number k is introduced but not used.
- Line 171. How is the number 4 selected as maximum condition number for the Hessian?

limitations_and_societal_impact: No societal impact
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper analyses linear meta-representation learning, deriving formally statistical guarantees for widely adopted and empirically successful alternating minimisation algorithms (AltMinGD). With the gained insight, the authors propose a new variant of AltMinGD, named AltMinGD-S, which introduces a task selection mechanism at each alternating iteration to improve efficiency with respect to number of samples per task in high number of tasks scenarios.
main_review: The paper provides valuable theoretical insights and statistical bounds on representation meta-learning. The analysis is thorough and well explained, reaching simple and insightful conclusions. The new proposed method of AltMinGD-S is maybe of incremental novelty, but it is well motivated and rooted in the new insights, although I have some doubts on its practical efficacy (see comments). The experiments are not very comprehensive and not very well explained.

Specific comments:

1) It is unclear from the text in several locations whether AltMinGD is an existing algorithm that is analysed to get statistical bounds, or is a new algorithm proposed in this paper. I think it is the former. If so, some sentences and labels might need to be rephrased to avoid saying "our method" or similar when referring to it, e.g. line 285.

2) The organisation of the paper could be improved to make the above distinction clearer and improve the clarity of the paper in general. As far as I understand, sections 2 and 3 are essentially background, with the exception of subsection 3.1, which introduces the idea of  AltMinGD-S. I think a more organic structure should follow how the contributions are presented in the introduction: i) background on AltMinGD and similar, ii) statistical analysis of AltMinGD (firt half of section 4) and then iii) introduce idea of AltMinGD-S based on these insights (subsection 3.1 + second half of section 4). In the current form, I struggled to understand what is statistical guarantees on existing methods and what is novel method.

3) is the new variant AltMinGD-S named AltMin in the abstract and experiments? I am finding it very confusing to track the experimental proofs of the claims in the experiments.

4)  If I understood well the high level idea of AltMinGD-S, it only selects the tasks that it finds having low error at a particular iteration, leaving out the high error tasks which risk to "throw it off". In this way, is not a bias introduced  in the learning? The model is encouraged to learn some tasks very well and just ignore those that it can not do so well. Maybe the experiments disprove this, but I could not find much evidence in them (as pointed out in point 3).
limitations_and_societal_impact: No unstated limitation or societal impact concern.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper analyses the problem of **linear** meta-representation learning, and more particularly the *alternating minimization and gradient descent* algorithm (AltMinGD) that has become empirically popular for meta-learning methods. The authors prove statistical guarantees for this algorithm.   
They also propose an alternate version, AltMinGD-S, which achieves better per-task sample complexity, but is less tractable in practice because it is based on a task subset selection which relies on the linearity of the representations.
Then, they show with experiments than the AltMin algorithms achieve smaller errors than the Method of Moments and similar error than the Burer-Monteiro ERM, while being easier to tune. They also study the number of iterations required, and show that the AltMin algorithms (AltMin, AltMinGD, AltMin-S) are the fastest ones.
main_review: __**Originality:**__  This paper presents a novel and broad statistical analysis in terms of error and sample complexity of AltMin algorithms. [12] also analyzed the statistical guarantees of AltMinGD in the linear case, but only in the noiseless setting and in the view of federated learning. The authors clearly clarify the differences with [12].

__**Quality:**__  The work presented here is considerable, there is a lot of additional results in the appendix, particularly for the AltMin algorithm. The authors state in the paper that the BM-GD algorithm is hard to tune, but the plots provided in the paper do not help in supporting this. The plots in appendix G are important to see the variability of the results of the BM-GD algorithm. The authors discussed the limitations of their work and compared the different bounds on the sample complexity for the algorithms considered.

__**Clarity:**__  I found the paper dense to read, the writing could improve in clarity.  
I think there is an error when referring to related work, the notations and the definition of the AltMin algorithm is associated to [41], but this paper does not use the same notations, and it never refers to AltMin. I assume the authors wanted to refer to [24]. 
The numbering and the formulation of the theorems is not the same between the main paper and the appendix. I think the theorem 1 in the paper corresponds to theorem 9 in the appendix and same for the proof, but it is hard to confirm because the formulations and the quantities involved in the two theorems are different. It seems like the theorem are repeated multiple times (with different formulations), which messes up the numbering and makes it difficult to find for the proof corresponding to each theorem.

__**Significance:**__ I found the paper interesting as it provides a strong analysis of the AltMin algorithms, though it is restricted to the linear case. These algorithms are widely used in practice for meta-learning methods. Researchers could leverage this work for a non-linear analysis of AltMin or put into practice the insights from these results.
limitations_and_societal_impact: The work presented here is very theoretical. To study the possible negative impacts of this kind of work is to study the negative impacts of the whole field.
review_title: null

Meta-review: All reviewers agree that this is a solid contribution to NeurIPS: it tackles a relevant problem in the context of meta-learning and does so by proposing a novel and interesting strategy inspired by the matrix sensing literature. The authors provide a thorough theoretical investigation of the setting considered, which yields insights also on previous work on the topic of linear meta-representation learning. There are a few issues with clarity that authors have addressed during the discussion period and that will need to be taken care of in the final version of the paper. In particular, including material from the Appendix (e.g. plots concerning the behavior of Burer-Monteiro gradient descent) and adding further insight regarding the distinction between AltMin and AltMinGD-S (also explaining why this was not tested in the experiments). 
Decision: Accept (Poster)