Fundamental Limits of Transfer Learning in Binary Classifications
Authors: Mohammadreza Mousavi Kalan
Salman Avestimehr
Mahdi Soltanolkotabi
Venue: ICLR 2022 Submitted (2022)

Abstract: A critical performance barrier in modern machine learning is scarcity of labeled data required for training state of the art massive models, especially in quickly emerging problems with lack of extensive data sets or scenarios where data collection and labeling is expensive/time consuming. Transfer learning is gaining traction as a promising technique to alleviate this barrier by utilizing the data of a related but different \emph{source} task to compensate for the lack of data in a \emph{target} task where there are few labeled training data. While there has been many recent algorithmic advances in this domain, a fundamental understanding of when and how much one can transfer knowledge from a related domain to reduce the amount of labeled training data is far from understood. We provide a precise answer to this question for binary classification problems by deriving a novel lower bound on the generalization error that can be achieved by \emph{any} transfer learning algorithm (regardless of its computational complexity) as a function of the amount of source and target samples. Our lower bound depends on a natural notion of distance that can be easily computed on real world data sets. Other key features of our lower bound are that it does not depend on the source/target data distributions and requires minimal assumptions that enables it application to a broad range of problems. We also consider a more general setting where there are more than one source domains for knowledge transfer to the target task and develop new bounds on generalization error in this setting. We also corroborate our theoretical findings on real image classification and action recognition data sets. These experiments demonstrate that our natural notion of distance is indicative of the difficulty of knowledge transfer between different pairs of source/target tasks, allowing us to investigate the effect of different sources on the target generalization error. Furthermore, to evaluate the sharpness of our bounds we compare our developed lower bounds with upper-bounds achieved by transfer learning base-lines that utilize weighted empirical risk minimization on the combination of source(s) and target data sets.

Under review as a conference paper at ICLR 2022
FUNDAMENTAL LIMITS OF TRANSFER LEARNING IN BINARY CLASSIFICATIONS
Anonymous authors Paper under double-blind review
ABSTRACT
A critical performance barrier in modern machine learning is scarcity of labeled data required for training state of the art massive models, especially in quickly emerging problems with lack of extensive data sets or scenarios where data col- lection and labeling is expensive/time consuming. Transfer learning is gaining traction as a promising technique to alleviate this barrier by utilizing the data a related but different source task to compensate for the lack of data in targel task where there are few labeled training data. While there has been many recent algorithmic advances in this domain, fundamental understanding of when and how much one can transfer knowledge from a related domain to reduce the amount of labeled training data is far from understood. We provide precise answer this question for binary classification problems by deriving a novel lower bound the generalization error that can be achieved by any transfer learning algorithm (regardless of its computational complexity) as function of the amount of source and target samples. Our lower bound depends on natural notion of distance that can be easily computed on real world data sets, Other key features of our lower bound are that it applies any arbitrary source/target data distributions and requires minimal assumptions that enables it application to broad range of problems. We also consider a more general setting where there are more than one source domains for knowledge transfer to the target task and develop new bounds on generalization error in this setting. We also corroborate our theoretical findings real image classification and action recognition data sets. These experiments demonstrate that our natural notion of distance is indicative of the difficulty of knowledge transfer between different pairs of source/target tasks, allowing us investigate the effect of different sources on the target generalization error. Further- more, to evaluate the sharpness of our bounds we compare developed lower bounds with upper-bounde achieved by transfer learning base-lines that utilize weighted empirical risk minimization on the combination of source(s) and target data sets.
INTRODUCTION
Modern machine learning models such as deep neural networks have enjoyed wide success in many domains Krizhevsky al. (2012). The success such deep models critically relies on an enormous amount of data required for training these massive models. For instance, GPT3 which is the state of the model for natural language process has 175 billion parameters and requires data set of size 45 terabytes for training. However, in new or emerging application domains it is often extremely difficult or costly gather such large labeled training data.
A promising approach to this problem has been via transfer learning which aims at leveraging abundant available labeled data from related source task to reduce the amount of labeled data required for the target task Pan & Yang (2009); Weiss et al. (2016). From practical perspective transfer learning has been rather successful empirically. In particular, state of the art transfer learning approaches based on pretrained models and fine tuning has led to significant improvements on various benchmark datasets. Despite this empirical success however there is a huge gap between theory and practice in transfer learning and the fundamental limits and benefits of transfer learning understood. Key challenging questions include: What is an appropriate notion of similarity between different tasks and how be quantitatively defined and computed on real data? What is the best
not well

---

Under review as a conference paper at ICLR 2022
achievable accuracy of any transfer learning algorithm with only limited number of source and target samples? How does this accuracy depend on the number of samples and the similarity between the source and target tasks?
While the answer to these challenging questions are still not fully understood. they have indeed attracted lot of interesting theoretical work in this area Galanti et al. (2016). We will discuss this literature in thorough detail in Section 2. In this paper, we take a step towards answering the aforementioned key questions enabling a better understanding of the fundamental limits of transfer learning. We focus on binary classífications where the goal is to learn a classifier from a hypothesis class with finite VC-dimension. This covers most contemporary classification models including the training deep neural networks for binary classification. In this setting, we first define a natural notion of similarity between source and target tasks via the performance of the best source hypothesis on the target task. Then equipped with this notion of similarity, we derive statistical minimax lower bound on the target generalization error in terms of the number of labeled data from source and target tasks as well as the VC dimension of the hypothesis class and the similarity between source and target tasks. Furthermore, we extend this result to the case where there are multiple sources with different similarity to the target. Our results demonstrate that sources with high similarity to the target are more effective at reducing the target generalization error. Towards bridging the in transfer learning we also demonstrate the utility of our theoretical result in concrete applications. Indeed, a key feature of our result is that our lower bounds can be easily and efficiently computed on real data sets and apply broad class of practical settings.
gap
In summary our key contributions are as follows:
We develop novel statistical minimax lower bound on the generalization error that can be achieved by any transfer learning algorithm as a function of the amount of source and target samples and natural notion of similarity between source and target tasks.
A key features of our lower bound (including our notion of similarity) is that it can be easily computed on real world data sets. Furthermore, our lower bound holds for any source/target distribution and applies with minimal assumptions to wide variety of contemporary learning models including deep neural networks.
We investigate the sharpness of our lower bounds and demonstrate their utility via experi- ments on action recognition and image classification.
2
PRIOR WORKS
A closely related literature to transfer learning is domain adaptation where there is no or very few labeled target data and the goal is to adapt the hypothesis learned on the source domain to achieve a low target generalization error Chen et al. (2019); Blitzer et al. (2007); Azizzadenesheli et al. (2018); Long et al. (2016); Shen et al. (2018). Most of this literature assume that source and target share a common labeling rule but there is shift in the marginal distributions. There many upper bounds for the target generalization error in this setting this setting. For instance, Ben-Davin et al. (2007; 2010) gives upper bound for the target generalization error in terms of source generalization error and a divergence measure between the domains that can be estimated by finitely many unlabeled data from the source and target. In another work Mansour et al. (2009) introduces a new discrepancy distance and generalizes the results of Ben-David et al. (2007) for wide family of loss functions using Rademacher complexity. Similar this setting, but for multiple source domain adaption scheme, Mansour et al. (2021) proposes a family of algorithms based on the idea of model selection under the assumption that target distribution is close some convex combination of sources. A more recent work Lei et al. (2021) studies linear regression under shift distribution including covariate shift (i.e. conditional distributions of source and target are the same) as well as model shift (i.e. only distributions of the features of the source and target are the same) and develops algorithms achieving near optimal minimax risk in this setting.
In addition to upper bounds, there are also few results which provide lower bounds for target generalization error. David et al. (2010) provides impossibility results under the assumption of covariate shift and small discrepancy of unlabeled distributions. Mousavi Kalan et al. (2020) studies transfer learning with one hidden layer neural networks for regression problems. This result defines a notion of similarity between the source and target tasks based on a distance between the ground truth
2

---

Under review as a conference paper at ICLR 2022
parameters of the source and target networks. Using this distance this paper develops statistical minimax lower bound for the target generalization error in terms of the number of source and target samples as well the defined similarity of the source and target under the distribution shift with the assumption that the features are generated by Gaussian distributions. Compared to Mousavi Kalan et al. (2020) our result has quite few unique advantages: (1) We do not assume that the source and target data are generated according to a planted (teacher) network and our results now even hold in the agnostic setting. (2) Mousavi Kalan al. (2020) applies to regression problems but this result covers c classification (3) Mousavi Kalan et al. (2020) only considered one- me-hidden layer neural networks for predicting the labels of extracted features. In this result we can handle arbitrary deep neural networks. (4) Our notion of similarity between the source and target distributions can be much more easily estimated by using only a few target data without the need for estimating the ground truth target parameters which requires lots of labeled target data.
More closely related to this work Hanneke & Kpotufe (2019) derives a minimax lower bound for target generalization error in binary classification under the assumption of relaxed version of covariate shift and small transfer exponent parameter which is defined to measure the discrepancy of the source and target distributions. Our work differs from this previous work except for assuming the VC dimension of the model is finite we do not make any further assumptions. This makes our results applicable in much broader set of classifications or decision making problems. Furthermore, our lower bound can be evaluated on real data sets and serve as a guideline to practitioners helping them decide when utilizing additional knowledge from a source domain is useful for given target task.
Most of the literature in transfer learning try to provide sufficiency and necessity results by deriving upper and lower bounds for target generalization error in a relatively general setting. However, these papers often require a variety of assumptions to find the optimal classifier in target domain in closed form. For instance, Karbalayghareh et al. (2019; 2018) defines joint prior distribution of source and target domains using a Wishart distribution which relate the source and target tasks and then makes it possible to study and understand the transferability between domains. Furthermore, in this setting, the authors develop a closed form optimal Bayesian transfer learning and demonstrate its advantage over a classifier obtained by only target data. Related to this setting but for regressions, Karbalayghareh et al. (2018) obtains the optimal Bayesian transfer learning under setting of joint Gaussian feature/label distribution. In contrast with the above in our paper we do not make any assumptions about the distribution of the data.
PROBLEM FORMULATION
We consider a transfer learning problem where there are some labeled training data from a source task and a target task with the goal of inferring a hypothesis function with small generalization error in the target task. More specifically, we assume have ns and nt source and target labeled data where each training data consists of an input/feature as well as an output/label. We denote the source and training data by (ass, ys) ~ P and (æTT 3/) ~ Q, respectively, where ys, yr E {0, 1} and P, Q are the joint feature-label distributions of source and target data. Additionally, we assume that source and target features/inputs share same domain, Øy ØT E X. and H C c2 denotes a fixed hypothesis class with dx VC-dimension.
In transfer learning the goal is to find a hypothesis from H that minimizing the target excess risk defined below based on combination of source and target data.
Definition (Excess risk) For a hypothesis function h E H and source and target label-feature data generated according to distributions IP and Q ((xs.ys) ~ P and (xr,yr) ~ Q). we define the source and target excess risks as follows
(h) Q(h(aT) + yTl Q Qhe (xT) 4 yr]
and
(h) = (P(h()s) * usl - [hg (as) # ys] where hi = arg minKeR ([h(=)) # yTl and hig arg min (((()))) # ys)
Next, we need to define an appropriate notion of distance between the source and target. In the literature of domain adaptation, where the conditional expectation remains unchanged and there is
3

---

Under review as a conference paper at ICLR 2022
only shift in input distributions, it is common to define the distance as the enror of performance of the best source hypothesis in the target task. We also define the distance between source and target as the target excess risk of the best source hypothesis.
Definition 2 (Transfer distance) We define the transfer distance between source and a target with distributions and Q as follows
p(P, Q) = Q (1 (TT) # ur) - (aT) # yrl
(3.1)
Since we aim to derive minimax lower bound for transfer learning in binary classifications, we consider the class of pairs of distributions whose transfer distance is within fixed number A. As will elaborate further in Remark 7 below this notion of distance can be easily estimated/computed in practice.
4
MAIN RESULTS
In this section we characterize the fundamental limits of transfer learning in binary classifications by deriving a minimax lower bound via information anformation-theoretie arguments.
Theorem Consider transfer learning problem where there ng and ny number of source as well as target data and the hypothesis class H. has VC dimension dy obeying dæ 2 10. Furthermore, suppose that h = SS S2) is an estimated hypothesis for the target task using source and targer data in which Sp and So denote i..dd feature-label data pairs {ar yy' (il and ((r))) VT ))==
(8) (5)
generated according to the source and target distributions P and Q. Fix a transfer distance A < 0.99.
Then for any there exists (IP, Q2) with p(P,, Q) S A and universal constant such that
3 3-2
Prob Sp.52
(x) c. c.cc(ns du A)
8
where
c(ns, dH,
V
+
ns
dh
de
This also implies that
inf sup E h ((F.))S So,Se
(T((i)] c- e(us, no, dit, A).
(4.1)
The bound above characterizes the fundamental limits of transfer learning by providing a lower bound on the excess risk of any algorithm (regardless of computational tractability) as function of the number of source and target training data, the similarity/distanee between the source and target tasks and the dimension of the hypothesis class used.
Remark
The assumption A < 0.99 in the statement of Theorem 1 is just made for simplifying the analysis and the upper bound of 0.99 can be replaced by any constant in the interval (0, 1).
Remark 2
Remark One can show that the numerical constant in equation 4.1 obeys c 3-2v2
Remark 4 (Connection PAC learning) We note that the well-known agnostic PAC learning result
for single task gives lower bound of c- / Váz where is the number of samples of the task. Theorem recovers this result when there is not any source task, namely n, = 0, and the transfer learning problem reduces to learning a task without any prior knowledge from the source.
Remark (Identical source and target) When the source and target tasks are identical, then the transfer learning problem reduces learning a single task with ns + vr training data. Theorem also leads to the same conclusion in this special case as when the source and target data are identical
and thus c = V nstor which states that the lower bound is proportional to reciprocal of combination of source and target samples expected.
du
4

---

Under review as a conference paper at ICLR 2022
Remark 6 (Sharpness in special case) We note that the above lower bound is known be tight in special cases. For instance when there is a small amount of source data and A is rather large. the lower bound reduces to V du which known to be tight based on known agnostic PAC learning bounds.
nt
Remark 7 (How to apply Theorem I in practical settings.) In this remark we explain how Theorem can be applied when using contemporary machine learning models involving artificial neural networks. In this case, the hypothesis class corresponds to all neural networks with fixed architecture but different parameters. It is known that the class of neural networks with a fixed architecture has finite VC dimension and Harvey et al. (2017) gives upper and lower bounds for VC dimension of neural networks with ReLU activation functions. Thus, to apply Theorem I, one only needs to have an estimate of the transfer distance per Definition 2. We note that the transfer distance 3.1 consists of two terms: To estimate the first term, we note that hig can be easily estimated due to the abundance of source data in most applications. Also with an estimate of hig in hand one can estimate Q + yr] rather accurately using a simple empirical average with a few target test data as well-knows concentration of bounded functions imply that this empirical average is well concentrated around (xr) * yr). Up on first glance it seems that estimating the second term which corresponds to the lowest possible error in the target domain among the hypothesis class, requires large amount of labeled target data which is not available in practical problem. However, in an overparametrized setting, it is typical to assume that there exists a network which achieves very small target generalization error so can ignore the second term in most practical problems. Finally we note that as stated earlier the lower bound on the target excess risk gives an estimate of what generalization performance Furthermore, by comparing the estimated transfer distance of different pairs of tasks, we can find the pairs that are more suitable for transfer learning. This knowledge can in lurn significantly reduce the required number of target samples to achieve a certain accuracy.
can expect with certain number of source and target samples.
Next, we extend our result to a multiple source transfer learning setup where instead of only one source task there are several source tasks available and the goal is to transfer knowledge from multiple sources to a given target task to achieve a small target generalization error.
Theorem Suppose that there are uss T8S2:" ... ngx number of samples from N source tasks as well as or number of samples from target task and the hypothesis class H has VC dimension du obeying du 2 max (N + 9, N/2). Furthermore, suppose that h = ; Sp....., Spx Sq) is estimated hypothesis for the targel task using N sources and target data where Sv, and Sig denote i.i.d. data UTT
((r)) S, (s,)) )= and ((al)) (8) (5) y generated according to souce and target distributions Py and
(i) (6) ns;
Q j 1,... N. Fix transfer distances (Ai} where O S Aj 1. Then for any h there exists
(PL, ..., M, Q) with p(IP, j: Q)) < Aj and universal constant such that
3 3-2 >
Prob
Er(h)= E(ns, ... nsw: NT, dz, A ..... AN)
Sp. y St Se
where
e(ns,,... nSy TT, dre, Ai.... AN)
V du
nT
+ dx dxtnng D1
199
dx tx An
This in turn implies that
inf sup
E St. PN Sq (ET( 2 c. c... nT, dui MI.,,,A))
(4.2)
Si,, h
J=I....
Remark Similar to the previous theorem, Theorem 2 provides a minimax lower bound for target excess risk with the key distinction that now it applies in the setting where there are multiple source with different transfer distances to the target. This theorem characterizes the exces risk achievable by any algorithm function of these transfer distances well the number of samples from the different sources and the target data. Theorem 2 indicates that the more sources we have, the better performance can achieve in the target domain. However, this performance gain maybe marginal
5

---

Under review as a conference paper at ICLR 2022
for source tasks that have large transfer distance the target where there very few training data. In these cases of course it may be more computationally efficient to discard these sources given the marginal improvement in the generalization performance suggested by this theorem.
Remark 9 (Identical sources) if all the source tasks are identical, then there are effec- nsw number of source samples and by Theorem 1 the lower bound Theorem 2 also gives the same order wise lower bound as
tively ns,
would be
dN
VN.
+ ax tamy
dxs +any
nS Remark 10 (Infinitely many source samples) When A; > 0 and ns, + cc, the fraction dusnss A saturates at Iz which shows that when the source and target have positive distance, the source can never compensate for the target samples.
Remark 11 In the lower bound, the product terms Amss appear which indicate that source with large transfer distance can sometimes be as useful as a source with small transfer distance when there is large amount of training data available from that source.
5 EXPERIMENTAL RESULTS
In this section we evaluate our theoretical results on real data sets for action recognition and image classification tasks. By estimating the parameters appearing Theorem for different pairs of tasks, we first plot the lower bounds and then by running weighted empirical risk minimization investigate the sharpness of the bounds. We also investigate the effectiveness of different source tasks with different transfer distances on the target generalization error.
5.1 ACTION RECOGNITION
Experimental setup. We first perform experiments on the UCF101 action recognition data set. We pick CricketBowling and TableTennis videos from UCF101 the target task well three different pairs of classes as the source tasks: 1- CricketBowling and BaseballPitch, Cricketshot and Archery, 3- BaskethallDunk and Basketball. We pass the videos through i3d network pretrained on kinetics400 Carreira & Zisserman (2017) with the fully connected top classifier removed and extract the corresponding features of dimension 2048 from the videos. We then work with the extracted features instead of the raw videos.
Training. We train a one hidden layer neural network with 15 number of hidden units and ReLU activation functions for each pair of data sets. Table consists of test accuracy on CricketBowling vs. TableTennis, when using the network trained each source task. We use these accuracies for deriving the corresponding lower bounds. Furthermore, we run weighted empirical risk minimization as simple transfer learning approach to find some upper bounds on the target generalization error. Given n, and пи number of source and target samples, for estimating the corresponding one hidden layer neural network parameters we minimize the following weighted empirical risk
1-X
Σ
Cos(WWRReL((Wi/ (0) (8
A
Cost Cos((WRRdLU(Waa") (" (5.1)
min W.
TTT
TLS
where the function Cost denotes the logistic regression cost and (0,0.2,0.400.6, 1}. We then pick the lambda which minimizes the target test error.
Results. First we calculate the transfer distance by Definition 2 for each source/target pairs using Table 1. To this end, we assume that best target generalization error is zero and using the Table I we obtain the transfer distance for each pair which demonstrated in Table 2. As can be observed by Table 2, the pair of Sourcel and Target has the lowest transfer distance among other pairs since both of the source and target tasks share a same class which is CricketBowling, Furthermore, Table determines which pairs are more suitable for transferring the source knowledge the target.

---

Under review as a conference paper at ICLR 2022
Task
Test accuracy of Target us- ing the source network
Target: CricketBowling vs. TebieTennis
Source1: CricketBowling vs. Baseball Pitch
0.946
Source2: Cricketshot vs. Archery
0.61
Source3: BasketballDunk vs. Basketball
0.52
Table
pair of tasks
P(Source, Target)
(Sourcel, Target)
0.053
(Source2, Target) 0.39
(Source3, Target) 0.48
Table 2: Transfer distance of pairs of source and target on UCF101 action recognition.
x10
Target Generalization Error
Target Generalization Error
0.5
Sourcel-Targer Source2 Target
Lower Bound1
9.5
Source3-11 Targee
0.4
Source2- Target
Sourcee Tareee--Tarae Targes
Bound3
0.3
0.2
8.5
0.1
20
40
60
20
40
60
Number of Target Samples
Number of Target Samples
(a) Theoretical lower bounds
(b) Lower bounds and upper bounds
Figure 1: (a) depicts our lower bounds for three pairs of source and target tasks on action classification. (b) depicts the lower bounds along with the upper bounds obtained via weighted empirical risk minimization.
Next, we draw the lower bound curves for each pair in Fig 1a. To this end, we need to find the VC dimension of the hypothesis class which consists of neural networks with the architecture of 2048 15 * with ReLU activation functions. Theorem in Harvey et al. (2017) gives a lower bound for VC dimension of neural networks with ReLU activation functions by 640 and L are the number of parameters and layers, respectively. Then in Figure 1b we plot the lower bounds along with the upper bounds obtained via Formula 5.1 for three different pairs of source and target as well using only target samples. We obtained these upper bounds by running Formula 5.1 five times and then averaging the results. Fig 1b shows that when the distance of source from target is small it would be more effective in achieving small target generalization error. We would like to mention that all of these plots we choose the same number of source samples for each pair.
1 W L logz
where W
Figure 2 shows the average X, the weight appearing in Formula 5.1, when the number of target samples is 100 to 150. It shows that in the pair Sourcel and Target the average demonstrate the usefulness of the source in the target task. Furthermore, the small value of À in the pair 3ource3 and Target suggests that when the transfer distance is high, source samples are no longer usefull.
high which
5.2 IMAGE CLASSIHICATION
Experimental setup. In this section we focus image classification tasks and utilize Theorem to recognize appropriate pairs of tasks that are suitable for transfer learning. We choose some classes of the DomainNet data set Peng al. (2019) as source and target tasks. We pick Clock and Ambulance from DomainNet Clipart for the target task and three different pairs of classes as the source tasks: 1- Clock and Ambulance, 2- Cricketshot and Table'Tennis, 3- Table and FrontCraw. Here
7

---

Under review as a conference paper at ICLR 2022
Average X
0.4
Pairl
DuPaiz2
Ln Pair3
Figure 2: Average weighted empirical risk minimization for three different pairs of source and target tasks for action recognition.
Task
Test Accuracy of Target
using the source network
Target: Clock vs. Ambulance (Clipart)
Sourcel: Clock Ambulance (Sketch)
0.916
Source2: Clock vs. Crow (Sketch)
0.697
Source3: Crow vs. Basket (Sketch)
0.65
Table
Target: Generalization Error
0.012
Target Generalizetion Error
0.5
Sourcel-Tanget Souree2-Tanger Source3-Target
Bound1
Lower Bound2
0.4
Lower Bound3
Sourcei-
0.011
Sourre--Tap
0.3
Target
0.2
0.01
0.009
40
20
40
Number Target Samples
Number of Target Samples
Thenretical lower bounds
Lower bounds and upper bounds
Figure (a) depicts our lower bounds for three pairs source and target tasks on image classification. (b) depicts the lower bounds along with the upper bounds obtained via weighted empirical risk minimization.
pair of tasks
p(Source, Target)
(Sourcel, Target) 0.083
(Source2, Target) 0.3
(Source3, Target) 0.35
Table Transfer distance of pairs of source and target on DomainNet image classifications).
use ResNet50 network pretrained on Imagenet for extracting features of dimension 2048 and in the sequel we work with the extracted features rather than the raw image data.
Training. We train a one hidden layer neural network with 15 number of hidden units and ReLU activation functions for each pairs of the tasks. Table 3 includes the test accuracy on the target task when using the networks trained different sources, which is necessary for estimating/caleulatin the transfer distance as demonstrated in Table 4. Similar to the subsection 5.1, we also run weighted empirical risk minimization for finding upper bounds for the pairs of the source and target tasks.
Results. Similar to the previous section on action recognition, using Table we can obtain the identify suitable pairs of source and target tasks
transfer distances and based this distance
8

---

Under review as a conference paper at ICLR 2022
0.4
Average X
0.2
Pairl
DaPaiz2
Ln Pair3
Figure 4: Average weighted empirical risk minimization for three different pairs of source and target tasks for image classification.
for transfer learning. In the pairl Source and target tasks share the same objects which are Clock and Ambulance which results in low transfer distance. In pair2, still one of the objects which is Clock is the same in the source and target and we can see that the transfer distance for pair2 is lower than that for pair3. Then we plot the lower bounds in Fig 3a and weighted empirical risk minimization in Fig 3b. One can see that sources that are closer to the target according to our notion of distance are more effective achieving small target generalization error.
corresponding upper bounds obtained by
CricketBowling is common both in the source and Targetl. This suggests that these tasks similar to each other and the estimated transfer distance conforms with this intuition. Furthermore, CricketBowling and Cricketshot intuitively similar to another and this is also reflected in the lower transfer distance between source and Target2.
In Fig 4 we plot the average A, the weight appearing in Formula 5.1 when the number of target samples varies from 150 to 200. demonstrates that when a source is close to the target the weight of source risk in weighted empirical risk becomes high which shows the effectiveness of source samples in achieving small target generalization error.
6 PROOF OUTLINE
The main idea of proof is based on the following proposition proved in Tsybakov (2009)
Proposition 1 [Theorem 2.5 of Tyybakov (2009)) Assume that M 2 and the function d(.,) :) semi-distance. Also suppose that {Pe, Ja,e0 is family of distributions indexed over parameter space, O, and contains elements Oo, 01,-.. ..., 0M such that:
(i) d(O,, 0,) 2s 0, V <sjkssi
(ii) P3 < Po.
fj = 1, I,... M,, and
1 M
DRo(P))P)) S a loggMM
M
1=1
with 0 < 1/8 and P, Po,, j ...,, M and Dia denotes the KL-divergence. Then
VM
2 log M
inf sup Po (dd(0,) > 8) 1 VM
(1
-2o
â oee
Based on Proposition construct family of pairs of distributions, namely source and target distributions, whose transfer distances satisfy the A-constraint. To do so we pick some points from the domain X shattered by the hypothesis class and define appropriate distributions points. Furthermore, this family of distributions are indexed in the space [-1,1]d which can be metric space using Hamming distance. In order to satisfy the condition (i) in Proposition the indexes have to be well separated which can be achieved using the well-known Gilbert- Varshamov's bound. Finally we show that estimating a parameter with small hamming distance equivalent to estimating an appropriate hypothesis with small excess risk error.
this set of

---

Under review as a conference paper at ICLR 2022
REFERENCES
Kamyar Azizzadenesheli, Anqi Liu, Fanny Yang, and Animashree Anandkumar. Regularized learning for domain adaptation under label shifts. In International Conference on Learning Representations 2018.
Shai John Blitzer, Koby Crammer, Fernando Percira, et al. Analysis of representations for domain adaptation. Advances in neural information processing systems, 19:137, 2007.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79(1):151-175, 2010.
John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman. Learning bounds for domain adaptation. In NIPS, 2007.
Joao Carreira and Andrew Zisserman. Quo vadis, action recognition? new model and the kinetics dataset. In proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6299-6308, 2017.
Xinyang Chen, Sinan Wang. Mingsheng Long, and Jianmin Wang. Transferability vs. discriminability: Batch spectral penalization for adversarial domain adaptation. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research. PMLR, 2019.
Shai Ben David, Tyler Lu, Teresa Luu, and Dávid Pál. Impossibility theorems for domain adaptation. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 129-136. JMLR Workshop and Conference Proceedings, 2010.
Tomer Galanti, Lior Wolf, and Tamir Hazan. theoretical framework for deep transfer learning. Information and Inference: A Journal of the IMA, 5(2): 159- 2016.
Steve Hanneke and Samory Kpotufe. On the value of target data in transfer learning. In NeurlPS, 2019.
Nick Harvey, Christopher Liaw, and Abbas Mchrabian. Nearly-tight ve-dimension bounds for piecewise linear neural networks. Conference on learning theory, pp. 1064-1068. PMIR, 2017.
Alireza Karbalayghareh, Xiaoning Qian, and Edward R Dougherty. Optimal bayesian transfer regression. IEEE Signal Processing Letters, 25(1 1659, 2018.
Alireza Karbalayghareh, Xiaoning Qian, and Edward Russell Dougherty. Optimal bayesian transfer learning for count data. JEEE/ACM Iransactions on computational biology and bioinformatics, 2019.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances in neural information processing systems, 15: 2012.
Qi Lei, Wei Hu, and Jason Lee. Near-optimal linear regression under distribution shift. In Interna- tional Conference on Machine Learning, pp. 6164-6174. PMLR, 2021.
Mingsheng Long, Han Zhu, Jianmin Wang, and Michael Jordan. Unsupervised domain adaptation with residual transfer networks. Advances in Neural Information Processing Systems, 2016.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In 22nd Conference on Learning Theory, COLT 2009, 2009.
Yishay Mansour, Mehryar Mohri, Jae Ro, Ananda Theertha Suresh, and Ke Wu. A theory of multiple- source adaptation with limited target labeled data. In International Conference on Artificial Intelligence and Statistics, pp. 2332-2340. PMLR, 2021.
Seyed Mohammadreza Mousavi Kalan, Zalan Fabian, Salman Avestimehr, and Mahdi Soltanolkotabi. Minimax lower bounds for transfer learning with linear and one-hidden layer neural networks. In Advances in Neural Information Processing Systems, 2020.
10

---

Under review as a conference paper at ICLR 2022
Sinno Jialin Pan and Qiang Yang. A survey transfer learning. IEEE Transactions on knowledge and data engineering, 22110):1345 1359, 2009.
Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 1406-1415, 2019.
Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu. Wasserstein distance guided representation learning for domain adaptation. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Alexandre B Tsybakov. Introduction to Nonparametric Estimation. Springer series in statistics. Springer, Dordrecht, 2009. doi: 10.1007/b13794.
Karl Weiss, Taghi M Khoshgoftaar, and DingDing Wang. A survey of transfer learning. Journal of Big data, 3(1):1-40, 2016.
7 APPENDIX
7.1 PROOF OF THEOREM
We also use the following famous result in information theory known as Gilbert-Varhsamen Varhsamov's bound for packing argument.
Proposition 2 (Lemma 2.9 of Tsybakov (2009)) Ler d 2 8. Then there exists subset {w(() w w( of of (-1, 1, such that w( (1.1....,1] 1),
d
dist( (i)t(w((, (K)) 2 8
SO < k k M and M 2 24/8
where dist(w, w') Ex k= [wNN + w/)) is the Hamming distance between binary sequences = (w' w'y).
w = -W.,.... wa) and w
We will also use the following lemma proved in Hanneke & Kpotufe (2019). We would like to mention that some ideas of the proof are similar to those in Hanneke & Kpotufe (2019). However, as discussed section the problem setting of Hanneke & Kpotufe (2019) different from that of this work which results in constructing different set of distributions.
Lemma Let < 1/2 and [-,,1]. Then
DEa Ber Ber(112+ (z/2) o), B1eBBerr1////1 (=/2) (z/2).c) .)) S ca e for some independent of
Now in place provide the proof of Theorem 1. Let d = du - 2 and pick --1, .... Td from shattered by H.
Next, construct family of pairs of distributions (IP Qw)) indexed by E 1) where 1)d is the parameter space playing the role of in Proposition 1. For the following, fix e C c(ng, nT, dæ, A) < 1/2 for some constant e₁ to be determined later in proof and c(ns, nr, du A) is defined in Theorem 1.
Distribution Qui Que is composed of marginal and conditional distribution, namely Que We define the marginaldistributions as follows:
Q% x Q ylz
Q. [ x=1) A
Q" (x xo) 0.99 A
Q" ( a.)) = 100d
for i = 1...d
For the conditional distributions:
Qy = 1|x = x-1) = Q (y = 1/ = xo) = 1
(y 1|0 = x.) = 1/2 + (wi)e for = 1..., d
11

---

Under review as a conference paper at ICLR 2022
Distribution Pw: Pw is composed of marginal and conditional distribution, namely Pw Pyla u/a= We define the marginal distributions as follows:
( = x--1) = P P (a: = za) = 1/2(1 d n
2 27;) + nsA
for i 1,.,,d
For the conditional distributions:
Piy yl (1 = 1/2 8 xー =0
Pau (y 1 0 F7) =
p. y/2 (y = 1 = x.) = 1/2 + (w:)e for i= 1,..,d
Verifying p(P Qw:) < A: Bayes classifier of the domain generated by Pue is as follows:
(2o) = 1
(ag)) if my otherwise lg( for i == 1,,.,d
Similarly for the domain generated by Qu, we have
h7 h (2x)
h (m:) if = 1 otherwise (7;)); = 0 for i i= 1,.,,d
So hig and by disagree only on __ which implies that
p(Pw. (w): Q1h5(=T) vrl - (xT) * yrl = A
Since we want to derive a lower bound for the minimax risk stated in Theorem 1, among the hypotheses that they agree æ; for 1,... d the hypothesis that outputs æ-1 and æu results in smaller target error. Hence, H onto 1) with the constraint that h(x_1) h(xv) for all h E H. Furthermor, for any w, w/ E f,, 1)dd we have
restrict ourselves H which is the projection of
Er(hw')) dist(w, w') 100d
e, ha E F
when the target domain is generated by Qu.
Reduction to a packing: By using Proposition 2, we can get a subset E of 11, whose cardinality M 2 24/8 and for any w, wo belonging to Σ we have dist(w, w') 2 d/8. Furthermore, for any w, w' Σ have
(x(wwr))
100d 800
On the other hand, there is bijective map between {-1, 1] and elements of H. and any classifier h: {xx} + {0, 13 with h((x1)) h(xx)) = be reduced w E {-1, 13dd So we can choose E as the set of indices in Proposition with Hamming distance as the semi-metric and the expression
Pw (dist(w, w) > d/8) translates into Pa (ha) > c..).
KL divergence bound (part (ii) of Propasition 1): Define P = Pas X Q For any w, w' E Σ
we have
Daa(PulPuo) = ns (P. + Diil (ewr)
= nn. EDI(FP p/le pWw() + nr
ED (Q.) (22))
Qa
= ns
Dei (Pw...
bla, m + nT
100d Dur (Q)) (
d nsA
d
< ng
C0E2
nT 100 c
d nsA
< c.e dd
if < then coc < and apply Proposition
12

---

Under review as a conference paper at ICLR 2022
7.2 PROOF OF THEOREM 2
Proof of Theorem is similar to that of Theorem 1. However, we construct different target and source probability distributions.
Let d = du - N - and pick T-M, :..... Lo, L1, ... Td from shattered by H. Then we construct family of distributions (PP)) ..... p(,) Qw)) indexed by E {-1,1]4. Let
C <(ns)).... R nr, dzp A Ai.... AN) ) for some constant 6₁ < 1 to be determined later in proof. Furthermore, without loss of generality assume that A 2 A 2 2 AN 0.
Distribution Qw: Qu is composed of marginal and conditional distribution, namely Qw
QW x Qu y/a
We define the marginal distributions as follows:
Q x-1) A; A+t1 for i 1,..., N and Q x--) AA
Q (x zn) = 0.99 A
Q x .x) 100d
for i 1,.,d
For the conditional distributions:
2yja (y 1/x x x-1) for L...,
Oy (y 1 a 0o) =
yl (y = 1/x = x.) = 1/2 + (w;)e for i == 1,...d
Distribution p(U. pp(() is composed of marginal and conditional distribution, namely P!
(f)
vlu Iow (1) We define the marginal distributions as follows:
1
d for j 1, 1,..,NN
p (x: x--)
+
d d+ D;
1 (1)
(x vo)
N + (1
d + nss A
1
pa x x4y) d + ngg A
for j = 1,..,
For the conditional distributions:
ylan (y |ac ar_,) if j222, otherwise (y (y 1/ xx_)) for j 1 1,... N
blw (y 1 r00 =
P (y = 1/x = x.i) = 1122 (wy)e for j = 1,.,d
Verifying p(PP)) Qw) < A;
Bayes classifier of the domain generated by p(,) as follows:
hg, (x- = 0 j 2 i, otherwise his, (x- = 1 for j = I,..., N
h5. (xo)
hs. (xy) = 1 wy L, otherwise h3 (x,) for j I,... d
Similarly for the domain generated by Que have
hx 1 for 1,,,N N (x)a)) =
hx;))
if Wj otherwise h7(0,)) = 0 for 1..., d
So his and hy disagree ii..... x- which implics that
p(P(() Qw) Qth (TT) + yrl ((7((() yr Ai
13

---

Under review as a conference paper at ICLR 2022
With the same argument used in the proof of Theorem we restrict ourselves to H which is the projection of H. with the constraint that h(x-N) ... h1 ((za) 1 for all h e H.
The rest of the proof is exactly the same except the part regarding the KL divergence bound.
KL divergence bound: Define Pa (1
x x PC p
Q
=
ss
Das (P()))pp
DRi (2ll
j=1
N
E Dar (P
( ppp (
nr +
DRI L
p
Qa
1=1
d
Σ ss Σ
Dao(P w/a.
(' ylas
1 + nr
1
Dai (22g),,, (ggee)
d + ng, dgg As
100d
j=l
d d ns, A
Σ nss
CuE² nr- 100 cuc²
for small enough 6j we can apply Proposition
7.3 ADDITIONAL EXPERIMENTAL RESULTS
In section 5 we fix number of source samples and vary the number of target samples. Here in order to investigate the effect of source samples on the target generalization error, we fix the number of target samples nT and vary the number of source samples. Fig depicts the theoretical lower bounds along with the upper bounds obtained by empirical risk minimization for image classifications. We use the same source/target pairs as used section 5.2. Fig 5 demonstrates that Sourcel more helpful in reducing the target generalization eтrоr because it has low distance from the target. Furthermore, shows that increasing the number of source samples is useful up a point and beyond that point the error saturates and does not decrease further as discussed in Remark 10.
Target Generalization Error
0.3
0.2
mww Wom
0.1
Bound1 Bound2
Lower Bound5
Sourcel- -Target
Sourea2-Target
Source3-Tarrett
20
40
60
80
100
Number of Source Samples
Figure 5: Depicts the lower bounds along with the upper bounds obtained via weighted empirical risk minimization. In this setting the number target samples is fixed at nz 3
14


Reviews:
[{"review_id": "lo-rdnFas7N", "reviewer": "Reviewer_WXNa", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "[Since it is an emergency review, I checked the proof sketch. The detailed derivations are not examined.]\n\nPros:\n- This paper proposed a novel min-max learning bound under the proper transfer distance $\\rho(P, Q)<1$. The conclusion is interesting and insightful.\n- The proof is technically sound and recovers the conventional PAC-learning.\n\nCons:\n- The proof seems straightly adopting the information-theoretical lower bound technique, where the key component (transfer distance) is generally **not** adopted in practice.\n- The lower bound in multi-source is quite trivially extended. \n- The concerns on empirical validation.\n\n--------------------------------------------------------------------------------\nDetailed Reviews:\n\n- About the proof and significance.\n\nThe high-level proof idea is directly inspired by the conventional information-theoretical lower bound. The key difference lies in the introduction of transfer distance: the prediction risk gap (between the optimal source and target predictor) in the target domain. Although it is an interesting notion, as far as I know, almost no modern (in deep learning regime) transfer learning approach has indeed adopted this concept. \n\nBesides, I have concerns about the paper scope. Since the papers in ICLR should generally involve the theory/practice w.r.t. the representation learning. The main contribution seems to have no direct relation to representation learning...\n\n- About the multi-source scenarios\n\nThe multi-source scenario is just a trivial extension of the single source (by considering the $P_i-Q$ pairs). This can be fundamentally problematic (eq 4.2). In the multi-source scenarios, the $\\Delta$ is not necessarily small. There can exist some poor sources, which is quite natural. However, the proof just simply assumes the small transfer distance, which is unreasonable. Thus the learnability is related to the proposed multi-source algorithm. The author is encouraged to check papers [1,2] for a better understanding. Paper [1,2] also involves the lower bound in the multi-source setting.\n\n- About the experiments. The whole experiment is unclear\n\n  1.  it is unclear how the lower bound is indeed justified in the experiments.\n  2. The transfer risk is generally un-estimable since it is related to the ground-truth distribution. If we use observed samples to estimate, this can be quite problematic since the gap between the expected and observed terms is not proven.\n  3. The same problem is shown in Fig 1(2), Fig 4.  Why weighted erm? What is the motivation for introducing weighted ERM? Multiple papers have adopted the weighted ERM with a clear upper bound. I could not understand the whole rationale in this setting. \n\n- Other comments\n\n   The transfer distance can be negative with a highly noisy target and clean source distribution. The author is encouraged to provide a discussion.\n\nReference: [1] A theory of multiple-source adaptation with limited target labeled data. Aistats 2021\n[2] On the Sample Complexity of Adversarial Multi-Source PAC Learning. ICML 2020\n\n\n\n\n\n\n\n\n\n", "summary_of_the_paper": "[Disclosure: This is an emergency review. ]\n\nThis paper demonstrates the min-max lower bound of transfer learning. (More precisely, transfer learning under the same binary label space $Y=(-1,+1)$). Eq (4.1) points out the key theoretical results. Then the bound is extended into the multi-source scenarios. The empirical validations are provided.\n\n======Update after rolling discussion\n\nI would like to appreciate the author for their detailed responses. I have read the whole reviews and responses. I decided to maintain my current rating, due to the concerns on theoretical and empirical significance.   ", "summary_of_the_review": "This paper provided a lower bound in the binary domain adaptation classification problem, the conclusion is interesting and technically sound. However, this reviewer has concerns of significance and empirical validations. Based on this, I currently recommend a weakly negative score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "cXsEhlM-C96", "reviewer": "Reviewer_9V1Q", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 deals with a very interesting problem that is of fundamental importance: understanding the usefulness of transfer learning and its limitations given the relatedness between source and target domains.\nBased on binary classification problems, the authors derive a lower bound for the generalization error that can be possibly achieved by any transfer learning algorithm as a function of source/target sample size.\n\nAnalysis based on real datasets for tasks like action recognition and image classification demonstrates how the derived bounds can be used to obtain interesting insights regarding transfer learning in practical scenarios.\nFurthermore, following their theoretical derivations, the authors make a large number of remarks, which provide interesting and useful insights regarding transfer learning and enrich the discussions.\n\nAs the full knowledge of the source and target data distributions are not required in the analysis and as only minimal assumptions need to be made, the lower bound and the analysis presented in the paper may be relatively easily applicable to various transfer learning problems in a practical setting.\n\n\nMAJOR CONCERNS\n\nHowever, it is important to note that there exist relevant studies on binary classification in the context of transfer learning, where fundamental limits and efficacy of transfer learning have been discussed in depth.\n\nExamples of such studies include:\n\n1. Karbalayghareh, Alireza, Xiaoning Qian, and Edward R. Dougherty. \"Optimal Bayesian transfer learning.\" IEEE Transactions on Signal Processing 66.14 (2018): 3724-3739.\n\n2. Karbalayghareh, Alireza, Xiaoning Qian, and Edward R. Dougherty. \"Optimal Bayesian transfer regression.\" IEEE Signal Processing Letters 25.11 (2018): 1655-1659.\n\n3. Karbalayghareh, Alireza, Xiaoning Qian, and Edward Russell Dougherty. \"Optimal bayesian transfer learning for count data.\" IEEE/ACM transactions on computational biology and bioinformatics (2019).\n\nFor example, in paper (1) shown above, its authors investigated the problem of optimal classification using both source domain and target domain data.\nUncertainty regarding the feature-label distributions was considered in the study, where a Bayesian scheme was used to derive the optimal Bayesian classifier that guarantees the best-expected classification performance.\nThis work investigated the effect of relatedness between domains as well as the complexity of the classification problem at hand to examine the benefits and limitations of transfer learning.\n\nWhile the authors present a brief review of some prior work relevant to this current paper, it is narrowly focused on a few papers, failing to present the main contributions of the current study in light of relevant advances in the field, including the papers shown above.\nConsidering that there exists prior work that addresses (at least to some extent) questions such as \"what is the best achievable accuracy via transfer learning for binary classification\" and \"how does this accuracy depend on the source/target domain sample size and the similarity between the domains\", review of the relevant literature and presenting the proposed error bound and the analysis results in a proper context would be critically important.\n\nAnother concern about the current paper is that the experimental results based on the real datasets are somewhat limited to clearly demonstrate the benefits of the novel lower bound derived in the paper as well as the insights/remarks presented therein.\nAdditional examples would strengthen the work, and the authors may want to consider synthetic examples as well where the underlying feature-label distributions are known (with potential uncertainties).\nFor example, since the classification error of the optimal Bayesian transfer learning (OBTL) classifier can be estimated, it would be very interesting to consider such an example to test the tightness of the bound presented in this paper.\n\n\nMINOR COMMENTS:\n\nThe current manuscript includes a large number of typos and grammatical errors.\nPlease carefully proofread the manuscript and correct the errors.\n\nThe authors may also want to show the error bounds as a function of source sample size - for different levels of relatedness/similarities between the source/target domains/tasks.\nCurrently, only the bounds as a function of target sample size are shown.\n \n\n", "summary_of_the_paper": "In this paper, the authors aim to answer some of the fundamental questions regarding transfer learning.\nEspecially, the authors consider the problem of binary classification, for which they derive a novel lower bound on the generalization error achievable by any transfer learning algorithm as a function of source sample size and target sample size.\nThe presented results may improve our understanding of the utility and the limitations of transfer learning based on the relatedness between the source and target domains under consideration.\nThe authors show that the proposed method can be practically used in real applications, as it does not require full knowledge of the source and target domain distributions and makes minimal assumptions.\nThis paper considers real datasets for action recognition and image classification tasks for demonstration, based on which they also evaluate the sharpness of the derived bounds.\n\n", "summary_of_the_review": "This paper investigates an interesting and important problem: namely, the fundamental limits of transfer learning in the context of binary classification.\nThe authors derive a novel lower bound on the generalization error, based on which they present useful insights regarding the efficacy and limitations of transfer learning, especially as a function of source/target sample size and the relatedness between the domains/tasks.\nAs the presented results only make minimal assumptions and do not require full knowledge of the source/target domain data distributions, the results in this current work may be relatively easily applied to various real-world transfer learning problems (for binary classification). \nHowever, the current study overlooked closely relevant prior works on optimal transfer learning for classification (and other tasks), where relevant discussions on the efficacy and limitations of transfer learning have been made.\nFurthermore, additional experimental results (e.g. based on synthetic examples) would be needed to clearly demonstrate the usefulness/accuracy of the derived lower bound and to further validate the insights presented in the paper.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Oz5iJRU1EW9", "reviewer": "Reviewer_TfQT", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strong points:\n\n1. The paper is generally well organized. It is easy to understand the purpose and contribution of this paper.\n2. The literature review is clear. The relation to prior work is explained in detail.\n\nWeak points\n\n1. (P4) The lower bound in (4.1) is not sharp. Consider a general case of transfer learning problem for bounds, i.e., $n_S>>n_T>>0$. In this case, the second term in the denominator is canceled, and the bound is reduced to $\\sqrt{\\frac{1}{n_T/d_H+1}}$. This means that a large size of source data cannot improve the bound, i.e., this lower bound is very loose for a transfer learning problem.\n\n2. The theoretical contribution is not significant enough. The derivation of a lower bound based on VC dimension setup is not a novel idea. \n3. (P3)(3.1） The distribution assumption that $\\rho(P,Q)$ is smaller than a fixed number $\\Delta$, is very strong. In addition, the lower bound in (4.1) depends on this $\\Delta$. Therefore, the claim in the abstract, \"the lower bound does not depend on the source/target data distributions\" does not hold.\n4. Experiments are running the datasets with a size of about 100. This is too small to confirm a theoretical bound. Generally speaking, the order data size needs to be large enough to avoid the effect of constant in the bound.\n\nSuggestions:\n1. Run the experiments on datasets with large sizes such as 100K to check the bounds.\n2. Theoretical prove the lower bound is sharp, which would be a significant theoretical contribution.\n\n", "summary_of_the_paper": "This paper provides a lower bound on the generalization error for binary classification problems. This bound can be achieved by any transfer learning algorithm (regardless of its computational complexity) as a function of the amount of source and target samples. In addition, this lower bound and can be generalized to the multi-source case.", "summary_of_the_review": "The initial recommendation of the paper. is \"reject, not good enough.\"", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KW4J_yMXMo1", "reviewer": "Reviewer_dGvD", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "It gives new bounds with minimal assumptions, but\n1.\tIt is better to give more comparison between the new bound and the existing ones.\n2.\tIt is only for binary classes, but in real transfer learning, it is usually multi-class learning problems.\n3.     In experiments, it only shows that the bound is affected by the number of source and target training data, the similarity between source and target tasks. Moreover, how to find if the bound is tight or not?\n\n", "summary_of_the_paper": "This paper derives a novel lower bound on the generalization error of transfer learning as a function of the amount of source and target samples. It does not depend on the source/target data distributions and requires minimal assumptions. It also derive a bound for multi-source domains. ", "summary_of_the_review": "Based on the above review, the paper is slightly above the acceptance bound.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6NRqUF7IFqE", "reviewer": "Reviewer_pmYF", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Transfer learning is a natural, well-studied approach to dealing with scenarios with limited data. The authors make two main contributions in this work: a new distance measure (called “transfer distance”) between learning problems, and a clean generalization lower bound for when transfer learning can be helpful. The empirical experiments give a convincing argument that transfer distance is a relevant quantity in practice, and deserves further study. Overall, the paper is very well written and should be of interest to a general learning audience.\n\nOn the other hand, the work is not without weaknesses. The main focus of the paper is on proving a lower bound, but there is no indication of whether the new transfer term in the bound is tight. While some empirical experiments are done using ERM transfer methods, the results do not seem particularly convincing in this aspect. Second, the authors make a major point of emphasizing that transfer distance is easy to estimate (see Remark 7). This is actually false, at least in the worst-case. Having a good estimate $h$ of $h^*_S$ over $S$ is not sufficient to estimate $Q[h_S^*(x_T) \\neq y_T]$, because the marginal weight where $h$ and $h^*_S$ differ could shift dramatically between the source and target distributions. This needs to be clarified, and to recover the result it would be nice to see conditions on S and T where it remains true.\n\n\nMinor comments for the authors:\n\n1. Citations for empirical success in first paragraph?\n\n2. typos: is differs, resullts, \n\n3. Covariate shift is never defined. \n\n4. On page 3 it is stated that domain adaptation requires the conditional to stay the same—should this say covariate shift?", "summary_of_the_paper": "This work studies lower bounds on transfer learning in distribution-free classification, a technique for leveraging related source data S for some target classification problem T. This is a useful idea in practice since common ML algorithms such as deep learning require massive amounts of labeled data, which can often be prohibitively expensive. If we can leverage data from an existing problem and transfer the knowledge, we can get around this issue. The authors in this work provide a lower bound on the generalization error of transfer learning dependent on a natural measure of distance between the source problem S and target problem T (in particular, this is given by the error of the best hypothesis on S evaluated on T). They then provide empirical evidence that their distance measure captures the difficulty of transfer learning in practice, and that it can be estimated using available source and target data.", "summary_of_the_review": "Overall, I recommend weak acceptance of this work: the authors introduce a natural notion of distance and give a clean lower bound, but the evidence of tightness is weak and the discussion of estimating transfer distance needs to be corrected.\n\nEDIT: I have read the authors' response and my review remains largely unchanged. I believe with the addition of either a theoretical upper bound or more convincing empirical verification would lead to a very strong paper, but I can only recommend weak acceptance of its current incarnation. It could also be helpful to include experiments on estimating transfer distance in reasonable settings, since the assumption that $Q[h^*_S(x_T) \\neq \\hat{h}(x_T)]$ is small does potentially limit applicability to scenarios without any major shifts in the underlying distributional weights.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper shows minimax lower bounds on transfer learning for binary classification, in terms of a notion of transfer distance, defined in this paper. Experimental results try to show the validity of the proved minimax lower bounds. 

All reviewers acknowledge that the lower bounds are worthy contributions; however, none of the reviewers felt strong enough to champion this work, due to that:
- the theoretical sharpness of the lower bounds are not discussed in detail (Reviewers TfQT, pmYF, and dGvD). Remark 6 only discusses the regime of a small amount of source data and a large transfer distance, which is fairly limited.
- it is unclear to what extent the experiments validates the theory (Reviewer WXNa). Note that for a minimax lower bound, for any algorithm, there is some corresponding "worst-case" datasets such that the algorithm does not do well; it is unclear if the datasets considered here are worst-case at all. 
- the lower bound techniques are fairly standard.
- the comparisons between the lower bounds in this work and prior lower bounds (e.g. those in [1,2]) need to be discussed more thoroughly.

We encourage the authors to take into account the reviewers' feedback and revise the paper. 

[1] Hanneke and Kpotufe. On the value of target data in transfer learning. NeurIPS 2019.
[2] ​​Mansour, Mohri, Ro, Suresh, and Wu. A theory of multiple source adaptation with limited target labeled data. AISTATS 2021.
Decision: Reject