Representation Learning Beyond Linear Prediction Functions
Authors: Ziping Xu
Ambuj Tewari
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Representation Learning
Few Shot Learning
Multitask Learning

Abstract: Recent papers on the theory of representation learning has shown the importance of a quantity called diversity when generalizing from a set of source tasks to a target task. Most of these papers assume that the function mapping shared representations to predictions is linear, for both source and target tasks. In practice, researchers in deep learning use different numbers of extra layers following the pretrained model based on the difficulty of the new task. This motivates us to ask whether diversity can be achieved when source tasks and the target task use different prediction function spaces beyond linear functions. We show that diversity holds even if the target task uses a neural network with multiple layers, as long as source tasks use linear functions. If source tasks use nonlinear prediction functions, we provide a negative result by showing that depth-1 neural networks with ReLu activation function need exponentially many source tasks to achieve diversity. For a general function class, we find that eluder dimension gives a lower bound on the number of tasks required for diversity. Our theoretical results imply that simpler tasks generalize better. Though our theoretical results are shown for the global minimizer of empirical risks, their qualitative predictions still hold true for gradient-based optimization algorithms as verified by our simulations on deep neural networks.

Representation Learning Beyond Linear Prediction Functions
Ziping Xu Department of Statistics University of Michigan zi zipingxuGumich edu
Ambuj Tewari Department of Statistics University of Michigan tewaria@um's ch. edu
Abstract
Recent papers on the theory of representation learning has shown the importance of a quantity called diversity when generalizing from a set source tasks to a target task. Most of these papers assume that the function mapping shared representations to predictions linear, for both source and target tasks. In practice, researchers deep learning use different numbers of extra layers following the pretrained model based on the difficulty of the new task. This motivates us to ask whether diversity can be achieved when source tasks and the target task use different prediction function spaces beyond linear functions. We show that diversity holds even if the target task uses neural network with multiple layers, long source tasks linear functions. If source tasks use nonlinear prediction functions, we provide negative result by showing that depth-1 neural networks with ReLu activation function need exponentially many source tasks to achieve diversity. For a general function class, find that eluder dimension gives lower bound the number of tasks required for diversity. Our theoretical results imply that simpler tasks generalize better. Though our theoretical results are shown for the global minimizer of empirical risks, their qualitative predictions still hold true for gradient-bass optimization algorithms as verified by our simulations on deep neural networks.
1 Introduction
It has become common practice (Tan et al. 2018) to use pre-trained network as the representation for a new task with small sample size in various areas including computer vision (Marmanis et al. 2015), speech recognition (Dahl et al.] 2011 Jaitly al. 2012 Howard and Ruder] (2018) and machine translation (Weng et al.] 2020). Most representation learning is based on the assumption that the source tasks and the target task share the same low-dimensional representation.
In this paper, following the work of Triiuraneni et al. (2020), we assume that each task, indexed by t, generates observations noisily from the mean function Jž o ht, where ht is the true representation shared by all the tasks and ft is called the prediction function. We assume h² E H. the representation function space and ft Fi,, the prediction function space. (Tripuraneni et al. (2020) proposed target tasks
diversity condition which guarantees that the learned representation will generalize with any prediction function. Assume we have T source tasks labeled by 1...., T and Fi = Fr = Frn- We denote the target task by and let (x h) E the excess error of ʃ, T for task l. The diversity condition can be stated as follows: there exists some v > O, such that for any fe Fea and any h E H.
1 E
inf Fee F.F. Excess & for larget task
Eta(fea;))
< v
inf
FF ....,T 1=1
Excess eroo given for
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The diversity condition relates the excess error for source tasks and the target task with respect to any fixed representation h. smaller indicates a better transfer from source tasks the target task. Generally, we say 7 source tasks achieve diversity over Fta when v is finite and relatively small.
The number of source tasks plays important role here. To this, assume Fso Fia F is discrete function space and each function can be arbitrarily different. In this case, we will need the target task to be the same as least one source task, which in turn requires T [F] and |.].. So far, it has only been understood that when both source tasks and target task use linear prediction functions, takes at least source tasks be diverse, where d is the number of dimension of the linear mappings. This paper answers the following two open questions with focus on the deep neural network (DNN) models:
How does representation learning work when F + Fto?
How many source tasks do we need to achieve diversity with nonlinear prediction functions?
There are strong practical motivations to answer the above two questions. In practice, researchers use representation learning despite the difference in difficulty levels of source and target tasks. We use a more complex function class for substantially harder target task, which means F.o * Fiu- This can be reflected as extra layers when a deep neural network model used as prediction functions. On the other hand, the source task and target task may have different objectives. Representation pretrained on a classification problem, say ImageNet, may applied to object detection or instance segmentation problems. For instance, Oquab al. (2014) trained DNN on ImageNet and kept all the layers as the representation except for the last linear mapping, while two fully connected layers used for the target task on object detection.
Another motivation for our work is the mismatch between recently developed theories in repre- sentation learning and the common practice in empirical studies. Recent papers on the theory of representation learning all require multiple sources tasks achieve diversity so as to generalize to any target task in F (Maurer et al., 2016: Du et al., 2020 Tripuraneni et al. 2020). However, most pretrained networks are only trained on a single task, for example, the ImageNet pretrained network. To this end, we will show that single multi-class classification problem can be diverse.
Lastly, while is common to simply use linear mapping as the source prediction function, there is no clear theoretical analysis showing whether or not diversity can be achieved with nonlinear prediction function spaces.
Main contributions. We summarize the main contributions made by this paper.
1. We show that diversity over F.o implies diversity over Feas when both F.o and Fio DNNs and Fra has more layers. More generally, the same statement holds when Fra is more complicated than F.o. in the way that Fia Fla (F@m) for some positive integer m and function class F'a.
2. Turning our attention to the analysis of diversity for non-linear prediction function spaces, we show that for depth-1 1 NN, it requires 1(24)) many source tasks to establish diversity with d being the representation dimension. For general F... we provide lower bound on the number of source tasks required to achieve diversity using the eluder dimension (Russo) and Van Roy 2013) and provide a upper bound using the generalized rank (Li et al. 2021).
3. We show that, from the perspective of achieving diversity, single source task with multiple outputs can be equivalent to multiple source tasks. While our theories are built on empirical risk minimization, our simulations DNNs for nulti-variate regression problem show that the qualitative predictions our theory makes still hold when stochastic gradient descent is used for optimization.
2 Preliminaries
We first introduce the mathematical setup of the problem studied in this paper along with the two-phase learning method that will focus on.
I is the 2' times Cartesian product of F.
2

---

Problem setup. Let X' denote the input space. We assume the same ipput distribution Px for all tasks, as covariate shift is not the focus of this work. our representation learning setting, there exists a generic feature representation function h* E EH: X + 2 that is shared across different tasks, where 2 is the feature space and H the representation function space. Since we only consider the different prediction functions, each task, indexed by t, is defined by its prediction function fi J+ 2 + Dt C [0, 1], where Ft is the prediction function space of task t and ) is the corresponding output space, The observations Y, f? ht (X) + are generated noisily with mean X.
function ft o h", where ~ Px and is zero-mean noise that is independent
Our representation is learned on souree tasks f: = (fi...... ..f.....fe. f E Fi x x... x Fr for some positive integer T. We assume that all the prediction function spaces F. Fo are the same over the source tasks. We denote the target task by fta E Fia Z + 3, c [0. 1], where Fia is the target prediction function space. Unlike the previous papers (Du et al., 2020; Tripuraneni et al. 2020) Maurer et al.) 2016), which all assume that the same prediction function space is used for all tasks, we generally allow for the possibility that F. + Fta-
Learning algorithm. We consider the same two-phase learning method as in Tripuraneni et al. (2020). In the first phase (the training phase), n (MI,...., WT) samples from each task are available to learn a good representation. In the second phase (the test phase), we are presented samples from the target task learn its prediction function using the pretrained representation learned in the training phase.
We denote a dataset of size from task ft by ST { 3 We use empirical risk minimiza- tion (ERM) for both phase. In the training phase, minimize average risks over {S ) 12-1
Ti Lo (Inss))))))
R(f,h h f2o)
Σ.
where 100 y x + R is the loss function for the source tasks and f = (fi...., fr) E F The estimates are given by (feo, bo h) argming,.. R(f,h fto). In the second phase, we obtain the dataset (Ira,i, Ita,i).
1is from the target task and our predictor fra is given by
arg min R(f, fta) = FEF
Than Σ half o h(xra,)), Mro.s),
for some loss function 4a on the target task. We also use R(.. for the expectation of the above empirical risks. We denote the generalization eиrоr of certain estimates f, h by E(f, h R(f h minyeFFWeE R(f', , h'' I). where JF can be either FST or Fta depending on the tasks. Our so
goal is to bound the generalization error of the target task.
For simplicity, our results are presented under square loss functions. However, we show that our results
can generalize to different loss functions in Appendix G We also assume ni RT Ro for some positive integer .0
2.1 Model complexity
As this paper considers general function classes, our results will be presented in terms of the complexity measures of classes of functions. We follow the previous literature (Maurer al. 2016) Tripuraneni et al., (020)) which uses Gaussian complexity. Note that we do not use the more common Rademacher complexity as the proofs require a decomposition theorem that only holds for Gaussian complexity.
For generic vector-valued function class containing functions q: Rd IR" and N data points, XN = (æ),..., xN )² the empirical Gaussian complexity is defined as
( Eg
sup Q
Σ of ((x;))
Ji N. i.i.d
N
Note that the standard definition has 1/N factor instead of 1/VN. We use the variant so that @ does scale with N in most of the consider and only reflects the complexity of the class.

---

The corresponding population Gaussian complexity is defined as (x(() Exx [ox(e)] where the expectation is taken over the distribution of XN.
2.2 Diversity
Source tasks have to be diverse enough, guarantee that the representation learned from source tasks can be generalized to any target task in Fta- To measure when transfer can happen, we introduce the following two definitions, namely that of transferabiliity and diversity.
Definition 1. For some v, ft > O, we say the source tasks fi...., fI Fo are (v, traansfebaeeel to task fta if
sup se E(S, fia) NEW inf JEFR" Eff, fāo) +u/v Sv.
Furthermore, we say they are (v, p..p--iiveess over Fia if above ratio is bounded for any true target prediction functions fta E Fras i.e.
inf E(J, Sto)
sup sup fi. E. NEW inf
FEFS E(f, f20) 1/1V S..
When it clear from the context, we denote E(S, Sia) and E(S,h (%0 by & h) and ( h). respectively. We will call the transfer component and μt, the bias introduced by transfer. The definition of transferable links the generalization error between source tasks and the target task shown in Theorem [ The proof can be found in Appendix [A]
Theorem 1. If source lasks fi.... Si are (U, over Fras then for any Sia E Feas we have
2TT n... (Fra
9l((2/0)
Eralftas h) S vE (for h)
+
Vita
2nt
The first term in Theorem can be upper bounded using the standard excess error bound of Gaussian complexity. The benefit of representation learning is due the decrease in the third term from Gn.,, (F H//v/tt without representation learning to B... (Fra e h)/ / in our case. For the problem with complicated representations, the former term can be extremely larger than the later one.
In the rest of the paper, we discuss when can bound (v,, nt), for nonlinear and nonidentical Fso and Fra.
Negative transfer when source tasks are more complex
Before introducing the cases that allow transfer, first look at case where transfer is impossible.
Let the source task use a linear mapping following the shared representation and the target task directly learns the representation. In other words, fta is identical mapping and known to the learner. We further consider F.. = {= w w E RP} and H = (x + Hx: H E Rpxd]. The interesting case is when p < d. Let the optimal representation be H and the true prediction function for each source task be w..... w In the best scenario, we assume that there is no noise in the source tasks and each source task collects as many samples as possible, such that will have an accurate estimation on each w H E Rexd which we denote by W...
However, the hypothesis class given the information from source tasks are
{H Roxd Ew E R2, TT H W. for all 1...., T).
As H* is the above class, any QH" * for some rotation matrix Q E RPX is also in the class. In other words, non-reducible enror of learnt representation is maxq |||- QH* in the worst case.
More generally, we give a condition for negative transfer. Consider single source task f Let Hi = arg min minjeF,, (f) and Hi arg min min h).. In fact, if one hopes to get representation learning benefit with zero bias (μr = 0), we need all H to satisfy inf feF., Eto (J, h) = 0. i.e. any representation that is optimal in the source task is optimal in the target task as well. Equivalently, we will need Hi, C Hi. As shown in Proposition D the definition of transferable captures the case well.

---

Proposition 1. If there exists h' E His such that h' & Hig then min Eta h") 0. Furthermore, there no 5o, such that 8so is (v, 0) transffrabee to fta.
Proof. The first statement is by definition. Plugging g' into the Definition! we will have v 00
The negative transfer happens when the optimal representation for source tasks may not be optimal for the target task. As the case in our linear example, this is result of more complex Foo- which allows more llexibility reduce errors. This inspires to consider the opposite case where Fi is more complex than Feo.
4 Source task as representation
Before discussing more general settings, we first consider a single source task, which we refer to as so, Assume that the source task itself representation the target task. Equivalently, the source task has known prediction function (x) This is commonly-used framework when we decompose a complex task into several simple tasks and use the output of simple tasks as the input of higher-level task.
widely-used transfer learning method, called offset learning, which assumes (ta(2) = fio (x) wfa(x) (z) for some offset function wia falls within the framework considered here. The offset method enjoys its benefits when Wta has low complexity and can learnt with few samples. is worth mentioning that our setting covers a more general setting in Du et al. (201)). which assumes fia (x) Gff=, ((ff.(()) wT, (z)) for some known transformation function and unknown wi..
We show that a simple Lipschitz condition on Fia gives us bounded transfer-component. Assumption (Lipschitz assumption). Any fia E Fia is L-Lipschitz with respect to L2 distance.
Theorem 2. If Assumption holds, task f2n is (L, trtrrsrffeee to task fia and we have with a high probability.
Ene Fra -68 + Tss
(H)
Bnye (Fra a ch)
VTta
Theorem bounds the generalization error of two terms. The first term that scales with 1/ T only depends on the complexity of H. Though the second term scales with //yTta is casy to see that é nca (Fre to h) ② km. (Fea) < Br. (Fra H) with the dataset (h(r Pre.
4.1 General case
Previously, assume that single source task is representation of the target task. Now consider a more general case: there exist functions in the source prediction space that can be used representations of the target task. Formally. consider Fi. Fi (Fie for some and some turget-speciffe function space FV mm + Vta- Note that Fia is strictly larger than F.o. when 1 and the identical mapping the above property.
Fi In practice, ResNet (Tai al. 2017) satisfies
Assumption 2. Assume any fla F.a -'-Lipschitz with respect to L2 distance.
Theorem 3. If Assumption holls and the source tasks are (v. pi-diverse over its own space Fso. then have
B Bnn (Fea oh)
(B8T. (FOT
( o H.)
Ero (frash)= L'm
+ 11
VT
Vnza
is shown in Tripuraneni et al. (020) that G2 n. (FOS H) can be bounded by ((8To.. (H) VT& (Fso)). Thus, the first term scales with Grn... (H) /Tn.o + Gn... / /nso Again the common part shared by all the tasks decreases with / Nsos while the task task-specific part scales with 2n or /nta-
5

---

4.2 Applications to deep neural networks
Theorem has a broad range of applications. In the rest of the section, we discuss its application to deep neural networks, where the source tasks are transferred to a target task with deeper network.
We first introduce the setting for deep neural network prediction function. We consider the regression problem with '. = -aa-- = R and the representation space 2 C IRP. A depth- K vector-valued neural network is denoted by
f(x) = a (Wr (a (...a wx))))),
where each WE is parametric matrix of layer k and a is the activation function. For simplicity, we let Wx E RRexp for k 1.... .... The class of all depth-K neural network is denoted by Mr. We denote the linear class by L = for + a² x + B vo E RP, ||al122 S M(a) } for some M(a) > 0. We also assume
max W bo. [Waellll| - (K). where || ol and || ll2 are the infinity norm and spectral norm. We assume any E 2, 12110000 S Dz.
Deeper network for the target task. We now consider the source task with prediction function of a depth-KK K neural network followed by a linear mapping and target task with depth- neural network. We let Kta K Then we have
Fra = Lo MK.. K,, MK,, and F - L MK...
Using the fact that M1 = (V)),, we can write Fia as L MK 1 oo (F&P). Thus, we apply Theorem 3a and the standard Gaussian complexity bound for DNN models, which gives us Corollary [
Corollary 1. Let Fso be depth-K, Kso neural network and Fra be depth- Kta neural network. If source tasks are (v, 0) diverree over Foos we have
Eia h)
@TTo (H) VTn
D2vK2o Vn
DzvKta M(a)ll Keo k= M(K)
δ (a) K=1 M(1)
(1)
Vita
Note that the terms that scales with /// and //a have similar coefficients M (T M(k). which do not depends on the complexity of H. The term that depends on BI... (H) scales with 1/ 1/vTri ns as we expected.
5 Diversity of non-linear function classes
While Corollary [ considers the nonlinear DNN prediction function space under a diversity condition, is not clearly understood how diversity be achieved for nonlinear spaces. In this section, first discuss a specific non-linear prediction function space and show a fundamental barrier to achieving diversity. Then extend result general function classes connecting eluder dimension and diversity. We end the section with positive results for achieving diversity under a generalized rank condition.
We consider a subset of depth-1 neural networks with ReLu activation function: F = {x + [(x, w) - (1 e/2)]+ || < 1, ||/||| 1} for some 0. Our lower bound construction is inspired by the similar construction in Theorem 5.1 of Dong et al. 2021).
Theorem 4. Ler T = (fi...., fr be any set of depth-1 neural networks with ReLu activation in F. For any 0, if < 2d(om(1/e))1, there exists some representation h², E H, some distribution Px and a target function fin E F. such that
inf (folf,h') 0, while inf fEFOT
Eta()h)) -2/322
JEF
Theorem implies that we need at least 2(2d log(1/<)) source tasks to achieve diversity. Otherwise, we can always find set source tasks and a target task such that the generalization error in source tasks are minimized to O while that in target task is e² /32.. Though ReI.u gives more intuitive result, we do show that similar lower bounds can be shown for other popular activation functions, for example, sigmoid function (see Appendix E.

---

5.1 Lower bound using eluder dimension
We extend our result by considering general function space FF and build an interesting connection between diversity and eluder dimension (Russo and Van Roy 2013). We believe we are the first to notice a connection between eluder dimension and transfer learning.
Eluder dimension has been used to measure the sample complexity in the Reinforcement Learning problem. It considers the minimum number of impus, such that any two functions evaluated similarly at these inputs will also be similar at any other input. However, diversity considers the minimum number of functions such that any Iwo representations with similar outputs for these functions will also have similar output for any other functions, Thus, there is a kind of duality between eluder dimension and diversity.
We first formally define eluder dimension. Let F be a function space with support X' and let > O. Definition ((FFe) d)dependencc and eluder dimension (Osband and Roy (2014)). We say that X is (F, ( -dependent on {II, (II,...,IIN, In C X' iff
VI,EE, Σ (as)
Se -
]n) iff it does not satisfy the definition of dependence. The eluder dimension dimm(FFe) is the length of the longest possible sequence of elements in X such that for some e' 2 e every element is (F, "...''-indeeeeeen of its predecessors.
We say E X' is (F,, -e)--ddddeeedde of (xI,...,
We slightly change the definition and let dim'g g (F, E) be the shortest sequence such that any x E X' is
(F, deeendnettt on the sequence.
Although ( S dimg(F, e), it can be shown that in many regular cases, say linear case and generalized linear case, dimg@(Fe é) is only larger then dim (F,e) e) up constant.
Definition 3 (Dual class). For any F X' ~ V, we call F F y its dual class iff. F {gx-
gx( = (xx), Vo X}.
Theorem 5. For any function class F x R. and some 0, let F be the dual class of F. Let dg = dim Then for any sequence of tasks fi...., fo S dg - 1, there exists a task fet1 F such that for some data distribution Px and two representations h, h²,
inf fn Ex Exlf/ (h(X)) - (x+2 2 1/2.
inf f. St Ei=1 Ex Exl ff fx(h(
Theorem formally describes the connections between eluder dimension and diversity. To interpret the theorem, first discuss what are good source tasks. Any T source tasks that are diverse could transfer well to a target task the parameter P could be bounded by some fixed value that is not increasing with T' For instance, in the linear case, finite function class, in the worst case, P will increase with T before T reaches [F]. Theorem states that if the eluder dimension of the dual space is at least dg, then scales with T until T reaches dg. as if the function space F is discrete with dg elements.
(d)) matter how large T is. While for
Note that this result is consistent with what is shown in Theorem 9 as eluder dimension of the class discussed above is lower bounded by 2(24) as well [Li al. 2021
5.2 Upper bound using approximate generalized rank
Though we showed that diversity is hard to achieve in some nonlinear function class, we point out that diversity can be easy achieve if we restrict the target prediction function such that they can be realized by linear combinations of some known basis. Triiprrneni et al. (2020) has shown that any source tasks fi,..., fr E FF are (L/T', -i-diverse over the space { E F : e conv(fi..... fr) such that sup, [[((2) f(>)) S μ', where conv(f1...., is the convex hull of (Si,... Jr.. This can be characterized by a complexity measure, called generalized rank. Generalized rank is the smallest dimension required to embed the input space such that all hypotheses in function class can be realizable as halfspaces. Generalized rank has close connections to eluder dimension. As shown in Li al. 2021). cluder dimension can be upper bounded by generalized rank.
7

---

Definition 4 (Approximate generalized rank with identity activation). Let (R( = {a E Rd ||>|| I R}. The p-approximate id-rk(F, R) of a function class F X + R scale R. is the smallest dimension d for which there exists mappings Φb : X + (a(1) and w F + Ba(R) such that for all (x. f) E X F: If(z) (w((f),
p.
Proposition 2. For any F with ju-aproximmaee id-rk(F, R) I d; for some R R> 0, there exists no more than d, functions, Si....,Jdd. such that ((((),... w (fa,) span Idd., Then ,I...., Sd. are (di. diveere over F.
Proposition 2 a direct application of Lemma in Tripuraneni et al. (2020) Upper bounding id-rank is hard for general function class. However, this notation can be useful for those function spaces with a known set of basis functions. For example, any function space JF that is square-integrable has a Fourier basis. Though the basis is an infinite set, we can choose truncation level d such that the truncation errors of all functions are less than j.. Then the hypothesis space FF has y-aaproximmte id-rank less than d.
6 Experiments
In this section, we use simulated environments to evaluate the actual performance of representation learning on DNNs trained with gradient-based optimization methods. We also test the impact of various hyperparameters. Our results indicate that even though our theory is shown hold for ERM estimators, their qualitative theoretical predictions still hold when Adam is applied and the global minima might not be found. Before we introduce our experimental setups, we discuss a difference between our theories and experiments: our experiments use a single regression task with multiple outputs as the source task, while our analyses are built on multiple source tasks.
6.1 Diversity of problems with multiple outputs
Though we have been discussing achieving diversity from multiple source tasks, we may only have access to single source task in many real applications, for example, ImageNet, which is also the case our simulations. In fact, we can show that diversity can be achieved by a single multiclass classification or multivariate regression source task. The diversity for the single multi- variate regression problem with L2 loss is trivial as the loss function is decomposable. For multi- class classification problems or regression problems with other loss functions, we will need some assumptions on boundedness and continuous. We refer the readers to Appendix H for details.
6.2 Experiments setup
Our four experiments are designed for the following goals. The first two experiments (Figure D a and b) target on the actual dependence Nlso Rht, K and K., in Equation (I) that upper bounds the errors of DNN prediction functions. Though the importance of diversity has been emphasized by various theories, no one has empirically shown its benefits over random tasks selection, which we explore in our third experiment (Figure [ c). Our fourth experiment (Figure I d) verifies the theoretical negative results of nonlinearity of source prediction functions showed in Theorem and
Though the hyper- parameters vary in different experiments, our main setting can be summarized below. We consider DNN models of different layers for both source and target tasks. The first K layers are the shared representation. The source task is multi-variate regression problem with output dimension p and K2 layers following the representation. The target task is single-output regression problem with Ktn layers following the representation. We used the same number of units for all the layers, which we denote by nu,, A representation first trained on the source task using Nao random samples and is fixed for the target task, trained on new random samples. In contrast, the baseline method trains the target task directly on the same nia samples without the pretrained network. We use Adam with default parameters for all the training. We use MSE (Mean Square Error) to evaluate the performance under different settings.
6.3 Results
Figure I summaries our four experiments, with all the Y axes representing the average MSE's of 100 independent runs with error bar showing the standard deviation. The X axis varies depending
8

---

on the goal of each experiment. In subfigure (a), we test the effects of the numbers of observations for both source and target tasks, while setting other hyperparameters by default values. The X axis represents Toso and the colors represents Vit In subfigure (b), we test the effects of the number of shared representation layers K. To have comparable MSE's, we keep the sum + Kta
and run K == 1, .,..... 5 reflected in the X axis, while keeping K.. = 1. In subfigure (c), we test the effects of diversity. The larger we have, the more diverse the source task is. We keep the actual number of observations aao p 4000 for fair comparison. Lastly, in subfigure (d), test whether diversity hard to achieve when the source prediction function is nonlinear. The X axis is the number of layers in source prediction function K The nonlinearity increases with Ko- We run K = 1, 3 and add an activation function right before the output such that the function is nonlinear even if g =
2.30
Square
Target
100
0003
0.00
350
1003
3003
Namber
Effects of sample sizes
(b) Effects of K
3.65
2.50
0.002
Sopare
0003
1930
Ouquo Birmeskors
Number Lopees Source Fredicion
(c) Effects of diversity
(d) Effects Keo
Figure 1: (a) Effects of the numbers of observations for both source (ngo) and target tasks (nuz). (b) Effects of the number of shared representation layers K. (c) Effects of diversity determined by the output dimensions p. We keep the actual number of observations n2 p 4000. (d) Effects of nonlinearity of the source prediction function. Higher K indicates higher nonlinearity.
In Figure I (a), MSE's decrease with larger numbers of observations in both source and target tasks, while there is no significant difference between n. 1000 and 10000. The baseline method without representation learning performs worst and it performs almost the same when nua reaches 1000. In (b), there are positive benefits for all different numbers of the shared layers and the MSE is the lowest shared layers. As shown in Figure [ (c), the MSE's s and their variances are decreasing when the numbers of outputs increase, i.e., higher diversity. Figure (d) shows that there is significant difference between baseline and K = 1, 2,3. When K = 2,3 there a negative effects.
Discussion
In this paper, we studied representation learning beyond linear prediction functions. We showed that the learned representation can generalize to tasks with multi-layer neural networks as prediction functions long the source tasks use linear prediction functions. We show the hardness of being diverse when the source tasks are using nonlinear prediction functions by giving lower bound on the number of source tasks in terms of eluder dimension. We further give an upper bound depending on the generalized rank.
Focusing on future work, we need better tools to understand the recently proposed complexity measure generalized rank. Our analyses rely on the ERM, while practice as well as in our simulations, gradient-based optimization algorithms are used. Further analyses the benefits of representation learning that align with practice on the choice of optimization method should be studied. Our analyses assume arbitrary source tasks selection, while, in real applications, may have limited data from

---

groups that are ander-represented. which may lead to potential unfaimess. Algorithm that calibrates this potential unfairness should be studied.
Another direction of future work is to propose reasonable assumptions for guarantée of generaliza- tion even when the source prediction functions nonlinear. Possibly the interesting functions within a subset of the target prediction functiin class, which makes generalization easier.
In this work, consider provided and fixed source tasks. In practice, many empirical methods Graves et al. 2017) are proposed to adaptively select unknown source tasks. An interesting direction to ask whether adaptively task selection could achieve the optimal level of diversity and to design algorithms for that purpose.
Funding Disclosure & Acknowledgements
This work directly supported by NSF grant IIS- 100-2007555.
10

---

References
Bartlett, P. L. and Mendelson, S. (2002). Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):443-482.
Dahl, G. E., Yu, D., Deng, L., and Acero, A. (2011). Context-dependent pre-trate pre-trained deep neural networks for large-vocabulary speech recognition. IEEE Transactions on audio, speech, and language processing, 20(1) (2)--40-42.
Dong, K., Yang, J., and Ma, T. (2021). Provable model-based nonlinear bandit and reinforcement learning: Shelve optimism, embrace virtual curvature. arXiv preprint arXiv:2102.04/66
Dragomir, S. S. and Gluscevic, V. (2000). Some inequalities for the Kullback-Leibler and x²- distances in information theory and applications. RGMIA research report collection, 3(2):199-210.
Du. S. S.. Hu, W. Kakade, S. M., Lee, J. D., and Lei, Q. (2020). Few-shot learning via learning the representation, provably. In International Conference on Learning Representations.
Du, S. S., Koushik, J., Singh, A., and P6czos, B. (2017). Hypothesis transfer learning via transforma- tion functions. In Advances Neural Information Processing Systems, pages 574-584.
Fazlyab, M., Robey, A., Hassani, H., Morari, M., and Pappas, (2019). Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 32: 12211447-..48.
Golowich, N., Rakhlin, A., and Shamir, O. (2018). Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299. PMLR.
Graves, A., Bellemare, M. G., Menick, J., Munos, R., and Kavukcuoglu, K. (2017). Automated curriculum learning for neural networks. International Conference on Machine Learning, pages 1311-1320 PMLR.
Howard, and Ruder, S. (2018). Universal language model fine-tuning for text classification. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 328-339.
Jaitly, N., Nguyen, P., Senior, A., and Vanhoucke, V. (2012). Application of pretrained deep neural networks to large vocabulary speech recognition. In Proceedings of Interspeech.
Jin, C., Netrapalli, P., Ge, R., Kakade, S. M., and Jordan, M. I. (2021). On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. Journal of the ACM (JACM), 68(2):1-29.
Li, G., Kamath, P., Foster, D. and Srebro, N. (2021), Eluder dimension and generalized rank. arXiv preprint arXiv:2104.06970.
Marmanis, D., Datcu, M., Esch, T., and Stilla, U. (2015). Deep learning earth observation clas- sification using Imagenet pretrained networks. IEEE Geoscience and Remote Sensing Letters, 13(1):105-109
Maurer, A., Pontil, M., and Romera-Paredes, B. (2016). The benefit of multitask representation learning. The Journal of Machine Learning Research, 17(1):2853-288)
Oquab, M., Bottou, L., Laptev, I., and Sivie, J. (2014). Learning and transferring mid-level image representations using convolutional neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1717-1724.
Osband, and Roy, B. V. (2014). Model-based reinforcement learning and the eluder dimension. In Advances in Neural Information Processing Systems, pages 1466-1474.
Russo, D. and Van Roy. B. (2013). Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, pages 2256-2266
Scaman, K. and Virmaux, A. (2018). Lipschitz regularity of deep neural networks: Analysis and efficient estimation. arXiv preprint 1rX.v:1805.10965.

---

Shwale-S S. and Ben-David, S. (2014). Understanding machine learning: From theory to algorithms. Cambridge university press.
Tai, Y., Yang. J., and Liu, X. (2017). Image super-resolution via deep recursive residual network. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 3147-3155.
Tan, C., Sun, F., Kong, T., Zhang, W. Yang. C., and Liu, C. (2018). A survey on deep transfer learning. In International conference on artificial neural networks, pages 270-279.
Tripuraneni, N., Jordan, M., and Jin, C. (2020). On the theory of transfer learning: The importance of task diversity. Advances in Neural Information Processing Systems, 33.
Weng. R., Yu. H., Huang, S., Cheng, S., and Luo, W. (2020). Acquiring knowledge from pre- trained model neural machine translation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2266-9273.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The limitations are discussed in Section 7
(C) Did you discuss any potential negative societal impacts of your work? [Yes] The potential societal impacts are discussed in Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] The proofs are all included in the Supplementary materials.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material as a URL)? [Yes] The code is in the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] The training details are in the supplemental material.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] Reported in Figure 1.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] In the supplementary materials.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] We did not use any assets.
(b) Did you mention the license of the assets?
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l roe're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] We did not conduct any research with human subjects.
12

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "WSHQipJV-Rd", "reviewer": "Reviewer_5xzU", "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.\n\nThis 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.\n\nThe 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.\n\nFinally, 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n**Question**:\n* 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.\n* 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?\n\n**Clarify of writing**: the paper is reasonably structured overall, though some parts would benefit from some rephrasing.\n  - Typo: bottom of page 1, the diversity condition: $f_{ta}^*$ is not in the definition.\n  - The paragraph after line 26: \"at least $d$ source tasks\": please add references.\n  - 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.\n  - Typo: the assumption on weight norms right above line 165.\n  - Line 206: please provide references.\n  - Thm 5: please provide a definition of the dual class.\n  - 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\".\n  - 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.\n  - Typo: Proposition 2: \"$w(f_1), ..., w(f_{d_i})$ span $\\mathbb{R}^{d_i}$\".\n\n====== \nPost-rebuttal update: I thank the authors for their responses and have raised my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "RzxtbObEAeH", "reviewer": "Reviewer_WX82", "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)?\n\nThe 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "The paper has potential consequences on fairness, which have been clearly acknowledged in Section 7 of the paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "JSIuXddEMSa", "reviewer": "Reviewer_RHzy", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nOriginality: 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.\n\nTechnical correctness:\n-\tTo 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.\n-\tProof 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.\n-\tImplication 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.\n\nExperiments: 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.\n\nClarity: 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.\n\nMinor comments:\n-\tWhile 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.\n-\tIn Theorem 4, should the left infimum be taken over \\mathcal{F}^{\\otimes T}?\n-\tIn Theorem 4, where does h^\\ast show up?\n-\tIn Theorem 5, the notion of dual-class of function space is not defined.\n-\tIn definition 3, should the \\mathcal{R} be just R? Also, the identity rank notation is not consistent: id-rk and id-rank.\n-\tOn line 287, should the K_{so}=1 only and not 2, 3, since K_{so}=2, 3 give negative results.\n\n[1] On the Theory of Transfer Learning: The Importance of Task Diversity.\n\n[2] Rademacher and Gaussian Complexities: Risk Bounds and Structural Results.\n\n======== After rebuttal ========\n\nThank 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the section above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "A66J7yV_Wh", "reviewer": "Reviewer_ts9h", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

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)