Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: [Disclosure: This is an emergency review. ]

This 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.

======Update after rolling discussion

I 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.   
main_review: [Since it is an emergency review, I checked the proof sketch. The detailed derivations are not examined.]

Pros:
- This paper proposed a novel min-max learning bound under the proper transfer distance $\rho(P, Q)<1$. The conclusion is interesting and insightful.
- The proof is technically sound and recovers the conventional PAC-learning.

Cons:
- The proof seems straightly adopting the information-theoretical lower bound technique, where the key component (transfer distance) is generally **not** adopted in practice.
- The lower bound in multi-source is quite trivially extended. 
- The concerns on empirical validation.

--------------------------------------------------------------------------------
Detailed Reviews:

- About the proof and significance.

The 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. 

Besides, 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...

- About the multi-source scenarios

The 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.

- About the experiments. The whole experiment is unclear

  1.  it is unclear how the lower bound is indeed justified in the experiments.
  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.
  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. 

- Other comments

   The transfer distance can be negative with a highly noisy target and clean source distribution. The author is encouraged to provide a discussion.

Reference: [1] A theory of multiple-source adaptation with limited target labeled data. Aistats 2021
[2] On the Sample Complexity of Adversarial Multi-Source PAC Learning. ICML 2020










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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors aim to answer some of the fundamental questions regarding transfer learning.
Especially, 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.
The 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.
The 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.
This 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.


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.
Based 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.

Analysis 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.
Furthermore, 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.

As 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.


MAJOR CONCERNS

However, 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.

Examples of such studies include:

1. Karbalayghareh, Alireza, Xiaoning Qian, and Edward R. Dougherty. "Optimal Bayesian transfer learning." IEEE Transactions on Signal Processing 66.14 (2018): 3724-3739.

2. Karbalayghareh, Alireza, Xiaoning Qian, and Edward R. Dougherty. "Optimal Bayesian transfer regression." IEEE Signal Processing Letters 25.11 (2018): 1655-1659.

3. Karbalayghareh, Alireza, Xiaoning Qian, and Edward Russell Dougherty. "Optimal bayesian transfer learning for count data." IEEE/ACM transactions on computational biology and bioinformatics (2019).

For example, in paper (1) shown above, its authors investigated the problem of optimal classification using both source domain and target domain data.
Uncertainty 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.
This 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.

While 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.
Considering 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.

Another 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.
Additional 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).
For 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.


MINOR COMMENTS:

The current manuscript includes a large number of typos and grammatical errors.
Please carefully proofread the manuscript and correct the errors.

The 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.
Currently, only the bounds as a function of target sample size are shown.
 


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.
The 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.
As 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). 
However, 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.
Furthermore, 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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
main_review: Strong points:

1. The paper is generally well organized. It is easy to understand the purpose and contribution of this paper.
2. The literature review is clear. The relation to prior work is explained in detail.

Weak points

1. (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.

2. The theoretical contribution is not significant enough. The derivation of a lower bound based on VC dimension setup is not a novel idea. 
3. (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.
4. 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.

Suggestions:
1. Run the experiments on datasets with large sizes such as 100K to check the bounds.
2. Theoretical prove the lower bound is sharp, which would be a significant theoretical contribution.


summary_of_the_review: The initial recommendation of the paper. is "reject, not good enough."
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

On 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.


Minor comments for the authors:

1. Citations for empirical success in first paragraph?

2. typos: is differs, resullts, 

3. Covariate shift is never defined. 

4. On page 3 it is stated that domain adaptation requires the conditional to stay the same—should this say covariate shift?
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.

EDIT: 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
main_review: It gives new bounds with minimal assumptions, but
1.	It is better to give more comparison between the new bound and the existing ones.
2.	It is only for binary classes, but in real transfer learning, it is usually multi-class learning problems.
3.     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?


summary_of_the_review: Based on the above review, the paper is slightly above the acceptance bound.
review_title: null

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