Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper presents some new theoretical insights into a two-layer (linear or non-linear) network based meta-learning framework for dimension reduction and few-shot linear regression. In the considered problem setting, the hidden layer for feature extraction is assumed to be shared across the training and test tasks, and the output layer is optimized in a task-specific way with quadratic loss. For well-specified low-dimensional linear representation learning models, statistical analysis shows that when the tasks are sufficiently divergent, the excess risk of the target task estimator has a near-optimal rate of convergence, up to a near-optimal statistical error of meta-training. The corresponding results for well-specified high-dimensional linear representation and neural networks have also been derived under additional regularization conditions.

Strong points:

-S1. Theoretical understanding of meta-learning for feature extraction and few-shot linear regression is an interesting and timely topic in representation learning.

-S2. The excess risk bounds look correct and can reasonable justify the benefit of multi-task feature extraction in terms of sample efficiency. 

-S3. The paper is well organized and neatly presented  

Weak points:

-W1. The entire analysis was made under a fundamental assumption that each training task should be globally minimized. From the perspective of optimization, such an assumption is fairly unrealistic in the sense that the linear/non-linear representation learning in the meta-training phase is non-convex and highly non-trivial for optimization. It is thus debatable whether excess risk, which is usually studied in convex learning theory,  should be used as a measurement of generalization performance for the considered representation learning problem. 

-W2. In Section 4, it is not very clear how to handle the identifiability issue in model (6), namely, $\hat B$ and $\hat W$ can be properly re-scaled and rotated without changing their product. The same concern can be raised for the underlying true model of data generalization in Equation (4) with linear feature map. The excess risk bounds in Theorem 4.1 and Theorem 5.1 seem to be invariant to such a scaling issue. However, the Assumptions 4.3 and 4.4 are clearly sensitive the scale of model. Is there any way to justify this kind of gap between assumption and result?

-W3. Assumption 4.3 essentially requires that $T\ge k$ because otherwise the smallest singular value will be zero. What will happen if $T<k$? I encourage the authors to provide some discussions/clarifications on this point. 



review_title: Reasonable theoretical results under unrealistic conditions

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper aims at justifying the success of few shot learning methods that work based on finding a shared representation among a number of tasks. A serious theoretical challenge is that, even if we assume such a representation exists (and belongs to a predefined class of functions with controlled capacity), we would still need to assume something that connects the source tasks with the target task. Previous work has considered "i.i.d. tasks", however, the obtained bounds were not natural in the sense that we don't have the usual decrease in the error as we increase the size of the training set of the source tasks. Under a different set of assumptions, the authors show that, in a sense, one can "fully" exploit the training data from the source tasks. 

Multiple settings are considered, including linear least squares with a low dimensional shared representation, generalization to non-linear representation, high-dimensional (low norm) representation, and neural networks. The obtained results are interesting, and some intuitions are provided about the assumptions and the results. These discussions are sometimes short/dense, making it hard for the reader to follow the details. This is perhaps due to the page-limit.

Perhaps a basic intuition for the first result (linear case with a low dimensional shared representation) is that if the source tasks are somewhat "uniform" in the low dimensional representation and the number of tasks is large enough, then in a sense they will "cover" the low dimensional space, and the learned representation will be in a sense accurate in all directions; so if the target tasks is also selected somewhat uniformly, then the learned representation will work well. Is this correct? In any case, I suggest that the authors add more of these intuitions to the paper, especially for the other problems including the neural net and the high-dimensional linear representation.

It will be interesting to do some experiments on a real world data set and see the extent to which the assumptions are realistic. It will help to see the actual value of the upper bounds on a synthetic data set that adheres the assumptions. 


  
review_title: A solid theory paper on few-shot learning

final_score: rating: 7: Good paper, accept
review_content: ## Summary 

The paper describes excess risk bounds for ERM in the few-shot learning setting where one has access to $n_1$ samples from each of the $T$ source tasks and $n_2$ samples from the target class. Under the assumption that there exists a ground-truth representation map, shared across all tasks, and a ground-truth task-specific linear map, that maps from the representation space to output space, the authors derive bounds that make use of all $n_1T$ data samples from the source tasks to bound the excess risk of the ERM.  

The bounds that are derived are for the following three settings: 1) low dimensional linear representation, 2) general linear map with $\ell$-2 norm-based capacity control for the representation, and 3) linear map with a Relu non-linearity based representation. The key innovation is the structure imparted onto the input distribution of the source and target tasks where the assumption is that the input distribution of *all* the tasks covers the target task. The assumptions get progressively stricter for each of the three cases where for the low dimensional linear case, the assumption is that covariance of the target tsk is dominated by the covariance of all the source tasks, for the high dimensional case, the mean covariance is shared across tasks and finally for the neural network cases where the tasks share the same input distribution. These assumptions allow the improvement of the bound in Maurer et al. 2016. 


## Strengths: 

1. Overall the paper is well written and motivated. The implication of the results are well discussed and makes for a good read. 
2. Under the assumptions on input distribution, results are an improvement over the iid task case and provides theoretical motivation for few-shot learning. 
3. Generalizes the Excess risk bound for the ERM in [1] for the low dimensional linear and the high dimensional linear setting. Extends the result to the ERM of 2 layer Relu network. 

## Weaknesses

1. The bound is valid when one has access to oracle ERM. This is not the case for most non-convex optimization. Especially in the case of the neural network extension.
2. As pointed out by the authors, many results are very similar to concurrent work of [1]
3. The paper lacks discussion with some prior work  [2] where the authors obtained results for task averaged excess risk. The result in this work is not for new task but since the authors make strong assumptions on input data distribution and task model the result seems like a natural extension of the results in [1].

## Discussion and concerns

Both Theorem 5.1 and 6.1 make the coherence assumption on the target task model. I understand that it allows us to get a bound in terms of $\| \Theta^*\|$ but the implications of this assumption is not well discussed in the paper. This looks like assumption 4.3 for Theorem 4.1. Any understanding of how the results would change if we don’t make the assumption 4.3 and the coherence assumptions?


__EDIT: Added references__
[1] Nilesh Tripuraneni, Chi Jin, and Michael I Jordan. Provable meta-learning of linear representations. arXiv preprint arXiv:2002.11684, 2020
[2] Pontil, M., & Maurer, A. (2013, June). Excess risk bounds for multitask learning with trace norm regularization. In Conference on Learning Theory (pp. 55-76).
review_title: Theoretical justification for the usefulness of having more source data in few shot learning

final_score: rating: 6: Marginally above acceptance threshold
review_content: #######################################################################

Summary:
This paper studies the benefit of few-shot learning for sample complexity, when all the tasks (both source and target task) share the same underline representation. Under some assumptions on the data and tasks, this paper improves the previous result based on the iid task assumption and shows that they can utilize all source data. The considered models include linear model (both low dimensional and high dimensional representation) and two-layer neural network.

#######################################################################

Pros:
- Understanding when and why few-shot learning is useful is an important and interesting problem. This work provides some insights into this problem and proves that in some setting few-shot learning is indeed helpful for the sample complexity.
- By introducing some new assumptions on data and tasks which is different from previous the iid assumption on the tasks, the paper shows that one can use all source data.
- Several models are considered in the paper, including linear model and two-layer neural network model. 
- The results are mainly focused on the statistical analysis, that is the property of minimizer. The algorithms to achieve such minimizer are also discussed, though for neural net, it may need exponential width.
- The paper is easy to follow and clearly discusses the meaning of assumptions.

##################################################################

Cons/Questions:
- I was wondering if author(s) could discuss [1] in the related work, which seems to focus on the similar problem.
- In Section 4 (low dimensional linear representation), a deterministic target risk is discussed in Remark 4.1. That is, the risk for any fixed target task instead of the average of all target task. I was wondering if such result could also hold in the setting of later sections, i.e., high-dimensional linear representation and two-layer neural network.

[1] On the theory of transfer learning: The importance of task diversity. arXiv preprint arXiv:2006.11650

####################################################################

Minor:
- In Theorem 4.1, \kappa is defined, but does not seem to be used in the theorem statement.

#####################################################################

Thanks for the  response from authors! I will keep my score.

review_title: Review

Meta-review: The paper considers the problem of learning a new task with few examples by using related tasks which can exploit shared representations for which more data is available. The paper proves a number of interesting (primarily theoretical) results.
Decision: Accept (Poster)