Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies representation learning in a setting where the source tasks and the target task use different prediction function spaces beyond linear functions, and asks the following question: how many source tasks are required to achieve *diversity* (an important quantity related to the generalization ability from source tasks to the target task)?

The paper first shows that diversity over the source tasks' prediction function space implies diversity over the target task's prediction function space. As a result, even when the target task uses multi-layer neural networks as prediction functions, generalization is still guaranteed as long as the source tasks use linear prediction functions. However, when the source tasks use nonlinear prediction functions, there exist some fundamental limits for generalization: the paper proves some hardness results, including a novel lower bound on the number of required source tasks in terms of the eluder dimension. The paper further provides an upper bound in terms of the generalized rank. Furthermore, the paper gives some theoretical results indicating that simpler tasks generalize better. Such insights are validated by numerical experiments.
main_review: The paper is well-written. The considered problem is not only theoretically interesting but also practically relevant. I checked some key parts of the proofs, and believe that the claimed results are correct. The connection between representation learning and the eluder dimension is particular interesting --- to my knowledge, the eluder dimension is mainly studied in the bandit and RL literature, with much more upper bounds proved than lower bounds. The connection between representation learning and the eluder dimension discovered in this paper is novel and may lead to deeper understanding of related fields. I also like the fact that many theoretical results in this paper are complemented by numerical experiments (though not in exactly the same setups).
limitations_and_societal_impact: When the source tasks use nonlinear prediction functions, the paper provides an upper bound stated in terms of the generalized rank. Is it possible to provide an upper bound based on the eluder dimension or a lower bound based on the generalized rank? If not, then pointing out the main obstacles may be helpful. Also, understanding the roles, differences and interpretations of the two complexity measures (or some other potentially useful complexity measures) seem like an important future direction.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies a transferred representation learning problem. In the considered setting, there are a set of source tasks and a target task. Each task consists of representation learning and prediction. The assumption is that all tasks share the same best representation function. The core question is: if we run ERM over source tasks, is the learned representation a good representation for the target task, and what is the generalization error for the target task? The authors quantify the performance through the Gaussian complexity of the function classes, and a quantity called "diversity", which relates the generalization error between the source tasks and the target task. Then the authors discusses several special cases, including "source tasks are more complex than the target tasks", "source tasks are simply learning representation", "source tasks are representation followed by non-linear functions". The main message is the simpler the source tasks are, the better chance transfer representation learning will succeed. 
main_review: This paper provides an interesting and clean viewpoint to quantify the performance of transfer representation learning.  The arguments in the paper look convincing and intuitive, while still providing new insight. The experimental results are also largely aligned with the theory. For the non-linear source task part, the lower bound using eluder dimension or the upper bound using generalized rank seem very pessimistic to me, because they are usually large beyond linear functions. The lower bound proof is also in a worst-case sense and may not reflect the reality. It would be good if the authors can provide discussions on this, and comment on whether those bounds can be improved using other complexity measures or considering more benign cases. 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies theory of representation learning. It differs from existing papers by considering scenarios when (a) the source and the target function class are different, and (b) non-linear prediction functions are used. There are three main results. The first result provides an upper bound for the generalization error of the target task if the source tasks are diverse. The second result shows the hardness of being diverse if the source tasks use nonlinear prediction functions, by relating diversity and eluder dimension. And the third result connects diversity and generalized rank.
main_review: Significance: The paper studies two meaningful extensions of representation learning theory as outlined in the summary. Both extensions are inspired by common practice in deep representation learning. And therefore studying these extensions is a necessary and important step to breach the gap between theory and practice. 

Originality: Across all the results presented in the paper, the most novel and exciting result is the link between diversity and eluder dimension (the second result on hardness). As noted by the author, this paper is the first to discover such a connection. The remaining results in the paper are built upon existing works, with little novelty in both the results and the proof techniques. The lack of a literature review makes it hard for readers to distinguish the contributions of the paper and various known results in the field.

Technical correctness:
-	To the best of my knowledge, I have checked the proof and finds no glaring issues with the technical theorems and lemmas in the paper. Therefore, I would like to focus the discussion of this section to understand more about the proof techniques and the implications of the theoretical results for practitioners.
-	Proof technique: Firstly, from what I understand, Theorem 1 is almost a direct result of the diversity assumption (Definition 1). As noted by the authors, the improvement of Theorem 1 as compared to standard generalization bound in supervised learning (e.g., in [2]) is in the third term. However, this improvement is achieved by fixing a representation \hat{h} and apply Theorem 6 (built upon [2]) over the predictor function space. Secondly, the hardness result for the general function class in Theorem 5 is, again, almost a direct result of the eluder dimension definition when t is less than the eluder dimension. Thirdly, the upper bound with the generalized rank result is a direct application of an existing Lemma in [1] (as noted by the author). To this end, I think that the three results are not so significant in terms of proof technique.
-	Implication for practitioners: Although these settings studied in the paper are inspired by common practice, the paper does not discuss (and I find it hard to interpret) the implications of these results. For example, many of the results in the paper rely on the assumption that the source tasks are diverse. And Proposition 2 is the only result that tells us how to achieve diversity through the notion of generalized rank. However, as noted by the authors, even upper bounding the generalized rank is hard. In the end, the paper does not discuss a concrete method to achieve diversity in the source task. For this reason, I find it challenging to use the theory presented in this paper as guidance for empirical practice.

Experiments: In terms of empirical studies, I appreciate the various experiments exploring the behavior of representation learning. One major gap between the developed theory and practice is that empirically, we cannot find the minimizers, but instead arbitrary local minimizers via gradient-based methods. Therefore, I understand that mismatch between theory and practice is unavoidable. I find the introduction of a single source task with multiple outputs and its connection to multiple source tasks a bit arbitrary and unnecessary. Other than that, I am satisfied with the empirical results.

Clarity: The main paper is clear and well-written. I can follow and understand the ideas most of the time. Notations are consistent and correct. However, there is no section dedicated to discussing related works. The lack of such discussion makes it very hard to distinguish the contributions of the papers and known results. I understand that it could be due to page limits that the authors decide to remove the related work section and just refer to existing work throughout the development of the paper. However, I would appreciate it if the paper discusses existing work, as well as connects the presented results to existing results in the literature in the supplementary material.

Minor comments:
-	While the paper mentions that Theorem 6 is achieved by applying the standard bounded difference inequality from [2], and provides no proof. To me, even after glancing through [2], I could not quite understand how to get Theorem 6. I would appreciate it if the paper elaborate more or include a short proof of Theorem 6.
-	In Theorem 4, should the left infimum be taken over \mathcal{F}^{\otimes T}?
-	In Theorem 4, where does h^\ast show up?
-	In Theorem 5, the notion of dual-class of function space is not defined.
-	In definition 3, should the \mathcal{R} be just R? Also, the identity rank notation is not consistent: id-rk and id-rank.
-	On line 287, should the K_{so}=1 only and not 2, 3, since K_{so}=2, 3 give negative results.

[1] On the Theory of Transfer Learning: The Importance of Task Diversity.

[2] Rademacher and Gaussian Complexities: Risk Bounds and Structural Results.

======== After rebuttal ========

Thank you for the response. I am willing to increase my score from 6 to 7. As discussed, please include a related work section in the future version of the paper.
limitations_and_societal_impact: See the section above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the importance of diversity in representation learning. The novelty over previous work is that this work studies the case where the prediction classes for the source and target can be different and nonlinear.

This paper first shows that diversity over the source prediction class $F_{so}$ implies diversity over the target prediction class $F_{ta}$, both of which could be nonlinear, as long as $F_{ta}$ is more complex than $F_{so}$. On the other hand, if $F_{so} \not\subset F_{ta}$, then 0-bias diversity cannot hold. When diversity does hold, error bounds on the target task are derived in terms of the diversity constants.

The second contribution of the paper is a negative result for nonlinear $F_{so}$: the number of tasks required to achieve $(\nu, 0)$-diversity is lower bounded by $\Omega(2^d)$ for 1-layer NN, or by the eluder dimension for the general case which is known to grow exponentially.

Finally, the theoretical results are verifies empirically on synthetic data. Different than the multi-task setup for theory, the experiments are on a single task with multiple outputs. The results show that diversity can still be achieved in this setting, with the representation learning performance improving with the diversity as desired.
main_review: **Significance and novelty of the contribution**: This paper generalizes the analysis of diversity to the case when the source and target prediction classes are nonlinear and nonidentical. This is an important problem to study, though the technical novelty is somewhat limited.

**Question**:
* The exponential lower bounds implied by Theorem 4 & 5 seem to be based on the assumption of $\mu = 0$. This seems to fit the  diversity definition on page 1, not the $(\nu, \mu)$-diversity in Def 1 where $\mu$ can be non-zero, which would mean the exponential lower bound no longer applies.
* For empirically verify the effect of diversity (Fig 1(c)), the value of $p$ seems too small to extract a confidence conclusion; moreover, the transfer performance is worse than the baseline in 3 out of 4 choices of $p$. Could you provide results with larger scale dataset (e.g. higher values of $p$ and more data points) please?

**Clarify of writing**: the paper is reasonably structured overall, though some parts would benefit from some rephrasing.
  - Typo: bottom of page 1, the diversity condition: $f_{ta}^*$ is not in the definition.
  - The paragraph after line 26: "at least $d$ source tasks": please add references.
  - Appendix B doesn't read well; e.g. line 400 (appendix) says "Now using Assumption 1", but the equation that follows doesn't use it.
  - Typo: the assumption on weight norms right above line 165.
  - Line 206: please provide references.
  - Thm 5: please provide a definition of the dual class.
  - Line 214 says that Thm 5 is consistent with Theorem 9, which is not mentioned in the main text. Perhaps change this to "consistent with Theorem 4".
  - Line 220: this should be $(T, \mu)$-diverse; $\nu$ is defined differently in Tripuraneni et. al. than in this work. Moreover, the result in Tripuraneni et. al. has some quantifiers on $\mathcal{F}$; please make this clear.
  - Typo: Proposition 2: "$w(f_1), ..., w(f_{d_i})$ span $\mathbb{R}^{d_i}$".

====== 
Post-rebuttal update: I thank the authors for their responses and have raised my score.
limitations_and_societal_impact: The authors discussed potential future direction of taking into consideration the optimization algorithm, and potential social impact of causing unfairness if the tasks were unfairly chosen for under-represented groups.
review_title: null

Meta-review: The reviewers agreed that this paper studies a practically relevant problem (transfer/representation learning) and provides novel upper and lower bounds on transfer learning performance, as well as experimental results to complement the theoretical guarantees. While many of the technical tools (e.g., eluder dimension) will be familiar within research on contextual bandits and reinforcement learning, their use in this context is novel, and is likely to find broader use. The results here also suggest a number of interesting new follow-up directions. The paper is also well-written.
Decision: Accept (Spotlight)