Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces a new error bound for the target domain motivated from Tikhonov-regularized inverse problem. This adoption gives an optimal selection scheme for the error bound of target domain based on distance-regularized domain adaptation, which is a theoretical principle for most domain adaptation methods. The proposed method is evaluated on the three benchmarks on domain adaptation.
main_review: My concerns are solved by the author. I'm keeping my rating 7 and increasing my confidence from 3 to 4.

==========================================================================================

### Originality

The introduced formulation gives an alternative optimal target error bound for unsupervised domain adaptation. Inspired by the Tikhonov-regularized inverse problem, the authors explore similarities between two problems and leads to solutions for the domain adaptation.

### Quality

I'm not familiar with the Tikhonov-regularized inverse problem, the other parts of the paper seem to be good and written in a good manner. But, work on the limitation of the domain adaptation is missing. I will discuss it in the limitation section below.

### Clarity

The paper is well-structured and easy to follow. Section 2 to 4 gives clever structure to understand the statement. 

### Significance

The work introduces a novel scheme to select the optimal regularization parameter for target-error bound for domain adaptation, while there exist many works on domain adaptation giving good practices. The experiment is relatively weak, but it is of acceptable quality. My concern as a practitioner for domain adaptation is this work does not talk about the regularization weight of domain adversarial network (DANN), which is epoch-based scheduling value not a fixed value. I will discuss in the limitation section.
limitations_and_societal_impact: ### related works

Could discuss the your method with the work [R1]? In line 99~102, it seems that covariate shift problem assumption is adopted the other papers. case. Could you refer to papers that take this as an assumption for the method? As I know it is not the case for most of the works. The work [R1] indicates covariate shift is the main problem of domain adaptation solver that relies on minimizing the distance between source and target domains. 

### DANN and regularization scheduling

It is common to use domain adaptation parameter $\lambda$ is initialized at $0$ and gradually increased to 1 using the scheduling policy.
$\lambda_p = \frac{2}{1 + exp ( -\gamma \cdot p )} -1$

[R1] On Learning Invariant Representation for Domain Adaptation, ICML 19
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes the  balancing principle to tackle hyper-parameter selection in unsupervised domain adaptation without requiring target labelled data. By viewing the target error bound as the combination of "  learning errors"  and the distance between source and target domains, the paper designs an algorithm that balances both terms to estimate the regularization parameter.  Generalization guarantee  of the corresponding selected  model is provided. Empirical  evaluations on a simulation dataset and two classical domain adaptation datasets highlight the performances achieved by the proposed method over existing approaches.
main_review: - Overall, the paper is well written. In particular, the rationale behind the proposed method is justified. Empirical evaluations support these intuitions and show how they contribute Unsupervised Domain  adaptation (UDA).
- Specifically, the paper tackles the challenging task of model selection in UDA without having access to labelled data from target domain. As such, the addressed problem is of interest for practitioners. To achieve the hyper-parameter  selection in UDA, the paper adapts to DA the balancing principle, a framework used in ill-posed inverse problems.
- The main pursued idea is to estimate the regularization parameter such that the domain-gap distance is balanced with the learning errors occurring in the target error upper-bound. As not all terms in the learning errors are computable, a surrogate is used to attain the balancing. It  consists in computing the cross-errors over $f_i, f_j, j=1,  \cdots, i-1$ on target data and in ensuring that  the cross-errors are lower than a specified bound depending solely on the domain distance. As a model $f_i$ is related to a hyper-parameter $\alpha_i$  (the $\alpha_i$s  are set increasingly), the best hyper-parameter is the maximal of such $\alpha_i$s. Interestingly the procedure is agnostic to the  theoretical target error bound. As a concept  of proof, the paper investigates the use of two existing target error bounds to illustrate the benefit of the approach. Finally the rationale behind the proposed approach is supported by a generalization guarantee.
- The paper  claims that the proposed method, BPDA, may account for label shift (lines  99-102). However  this assertion is not investigated in the experimental evaluations  or supported by a theoretical  analysis. Note that in UDA,  there exists target bound that  handles the label shift (see [a]). Is this kind of bound more suitable to BPDA to deal with generalized shift? 
- The considered target error in Equation (4) is  based on the 0-1 loss that offers the nice triangle inequality property (used to establish Theorem 1). However,  in practice when training the pursued model $f$  one rather relies on surrogate function of the 0-1 loss. How this fact impacts the consistency of estimated hyper-parameter? In the same vein does the  margin loss, used in the the target bound (6), satisfy the properties stated lines 66-68?
-  $D(\alpha)$ is assumed  to  be non-increasing. In  practice when training the UDA model in a deep learning setting,  the assumption may not hold true. Is this  detrimental for the proposed UDA model selection?
- The paper should discuss the tightness of the bound (15).
- In the empirical evaluations on the Transformed Moons, it might be interesting to compute and plot $E(\alpha)$, $D(\alpha)$ to  illustrate the ability of  BPDA to retrieve the correct  regime of the  hyper-parameter.
-  Reported results in Table 2  suggest that BPDA is  effective over existing approaches. However, Table 3 related to the more challenging multi-class classification tends  to mitigate that  effectiveness. In  fact,  Table 3 does not show the significance of BPDA as its standard deviations are higher than for the competitors. At best, BPDA is on par with those methods. Can the authors elaborate more  on this? Notice that instead of comparing the methods using the average of the averaged classification errors, the ranking of the methods will be  more significant.
- The performances of BPDA (as for the competitors)  tend to  vary according to the  used domain distance. Is a setting more suitable for BPDA that can be recommended to practitioners? 
- Minor comments
* To  ease readability,  I would suggest  to expand earlier in the paper the terms $E(\alpha)$ and DA(\alpha)$ related to UDA.
* Line 127: the upper bound on the sampling error should read $\eta_{t, \mathcal{G}, \delta}$
* Lines 146-147:  it is  not clear why the second term in $\lambda_{\mathcal{H}}$ expression does not depend on $\phi$, the representation mapping
* Equation (7): the representation mapping function $\phi$ is  missing in  the expression of $\hat{d}$.
* To  help the reader, I would propose to specify the terms $A(\alpha)$ and  $S(\alpha)$ (at least in the supplementary material) when presenting the balancing principle for regularized inverse problems.
* Line 210: note that $\phi$ is not a scalar-valued function. 

[a] Domain Adaptation with Conditional Distribution Matching and Generalized Label Shift, Remi Tachet des Combes, Han Zhao, Yu-Xiang Wang, Geoffrey J. Gordon. Neurips 2020

After feedback
--------------------
I thank the authors for providing detailed responses to the raised points. I highly appreciate their endeavour to clarify most concerns, especially the thighness of the target bound,  the practical instanciation of the bound or the discussion on the potential limitations of the approach when dealing with label shift. The sole weakness I may point out (ans this was mentioned in the paper)  is that the approach seems not overcome existing methods on more challenging DA datasets. Nevertheless the proposed method is theoretically grounded which is a good point to be mentioned. I increase my score to 6. 
limitations_and_societal_impact: The paper  adequately metions the broader impact of the tackled unsupervised domain adaptation . Especially the issue related  to the fact existing bias (including societal bias) in source domain data may be lifted to the target domain after adaptation is discussed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the problem of choosing a justified regularization parameter for unsupervised domain adaptation.
The authors make a link between ill-posed inverse problems and approaches based on a weighted combination of the source error and a distance between source and target feature representations.
They propose a framework based on balancing approximations and sampling errors to obtain a target error bound that takes into account a balance between learning errors domain distance.
This leads to develop a founded rule for the choice of the regularization parameter which can be applied with source and target distributions with disjoint supports. 
A bound on the target risk is provided. 
An experimental evaluation of the approach is provided using the Moons toy dataset and the Amazon reviews and DomainNet–2019 benchmark.
main_review: Originality
---------------
This paper studies the tuning of a particular hyperparameter in the context of unsupervised domain adaptation. An important strong point is the procedure is founded theoretically which is not often the case of existing methods.

Quality
-----------
The proposed method is justified theoretically and argumented.

The experimental evaluation is sound but limited in some points: other baselines and a study on how far the assumptions are verified could be added.
 
I would have also appreciated a thorough discussion on the target risk bounds that can be obtained from Thm1 for different divergence measures, both from theoretical and practical sides. One can wonder if the bound will not be large in some cases to match the required constraints?


Clarity
---------
The paper is clear and easy to read. The contribution is well presented.


Significance
-----------------
The problem studied is of importance in the context of domain adaptation problems. 
The method has the advantage to be simple which makes it rather accessible in practice while being justified in practice.
This is the first (or at least among the first) for which the theoretical justification helds for  distributions without disjoint support.
The results are rathe good.

However the method is specialized for only one hyperparameter while many domain adaptation algorithms optimized losses with multiple objective and hyperparameters. So the contribution has a strong limitation from this point.
Another one is probably the computation cost that requires quadratic pairwise computation on the parameter range.
About the theoretical guarantee, one the one hand this is strong point to have such a guarantee, but the bound can be loose at some point. In representation spaces where the two distributions are close, the bounds seems to be infinite, which is not what one would expect here.
Experimental evaluation can be improved in some points




Comments
---------------------

-In order to assess the quality of the result, I would be interested in having more discussions about the bound provided in Thm 1. 
It could be interesting to try to instantiate the bound in theory and in practice to make it more concrete and maybe to better compare it to other bounds.

One thing that puzzles me is that when considering a representation space $\phi$ such that the source and target distribution are naturally close, then the divergence will be naturally small and thus D(0), which makes the bound very loose and possibly infinite if the two distributions are the same.
Maybe refining the bound with restrictions on $\phi$ could be a direction for trying to have a better consistency.

-About the assumptions (paragraph started line 174): The authors have justified that they can be reasonable in theory, but I wonder what happens in practice. It could be interesting to check in the experiments to which the assumptions are verified and if the worst results can be identified as results obtained when the assumptions are not (fully) satisfied.

-In the results, and in particular in those related in the supplementary material, it seems that the proposed method has on average a higher variance than other methods. Can the authors provide some explanations for explaining this behavior. Is it a consequence of a generalization bound not that tight?
While the method is simple, it may then be more difficult to use it in practice?

-I am wondering if the authors could discuss more the computational cost of the method that requires to compute pairwise comparisons between candidate hypothesis/models. This seems costly and one can wonder if the benefits worth the computational time cost. In particular when a user is looking for a precise tuning, the cost is prohibitive and this is confirmed in the reported experiments in supplementary material (DANN on the MiniDomainNet benchmark)
Maybe can we imagine some stochastic methods to accelerate the computation of the criterion?

-About distribution with disjoint supports, the result is good but in the experimental setup other baselines adapted to disjoint supports could be considered, (e.g. the TrCV method below).

Other (heuristic) validation methods that can be discussed in the related work and used as other baselines in the experiments based a notion of "reverse validation":   
 *Erheng Zhong, Wei Fan, Qiang Yang, Olivier Verscheure, Jiangtao Ren: Cross Validation Framework to Choose amongst Models and Datasets for Transfer Learning. ECML/PKDD 2010   
 *Lorenzo Bruzzone, Mattia Marconcini: Domain Adaptation Problems: A DASVM Classification Technique and a Circular Validation Strategy. IEEE Trans. Pattern Anal. Mach. Intell. 32(5): 770-787 (2010)   

Another direction can also be to consider heterogeneous domain adaptation, but here specific domain distances must be considered, as well as benchmarks dedicated to these tasks.

-In the experiments, I did not understand well how the baseline TB corresponding to the best target error is computed?
It is the best target error found among the $\alpha$ values selected or is it a bound obtained when learning for labeled target data?
In both cases, this is clearly a lower bound for the error.
In the first case, one can notice from the results in Appendix, that sometimes the method is close to this bound and sometimes not. In the second situation does this mean the assumption that D(\alpha) is non-increasing is false in practice.
In the second case, it is strange to be sometimes very close to the TB results.
Can the authors precise this point.

-In terms of writing, I agree that the inverse problem setting should be cited and discussed, but I think that the discussion on it can be reduced since at the end the two problems considered are rather different.
   
-A minor remark, but line.109, the notation $\phi(x)=\phi(x')$  is maybe badly chosen


-------   
After Rebuttal
-------   
The authors did a strong work to answer the points mentioned in the review. I appreciated the answers. I increase my score to 6.
limitations_and_societal_impact: The work is methodological and fundamental, so there is no direct negative societal impact.
The authors propose a broader impact discussion at the end of the paper.

However, in my opinion, the paper did not discuss properly the limitations of the work. The authors mention that this is discussed in Section 4.2 but as far as I can see, the only point is mentioning that the bound may not be tight and optimality cannot be guaranteed, but no precise limitations are discussed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors study the hyperparameter selection problem in the context of unsupervised domain adaptation.
While hyperparameter selection is not trivial at all due to the absence of the labeled data in the target domain, the authors employ the balancing principle to draw a connection between unsupervised domain adaptation and ill-posed inverse problems.
The proposed method is based on balancing the discrepancy term and the error term, and the joint minimizer is chosen as a good hyperparameter.
Notably, this method does not require any assumptions such as covariate shift and support matching as supposed in the existing researches.
main_review: I think the problem studied in this paper is pretty interesting.
Hyperparameter selection is one of the central obstacles when unsupervised domain adaptation (UDA) is applied in real-world scenarios.
While this problem itself has been actively studied as a matter of course, the proposed approach sheds new light on the estimation methodology to deal with "inaccessible" in the common domain adaptation bounds---the joint error minimizer.
This obstacle was mitigated by the balancing principle estimate (Definition 2), and in particular, by means of Lemma 1.
In my opinion, this is a pretty interesting theoretical result in the UDA context.

I'm overall positive about this paper, but let me put a few remarks that could help the authors to improve the paper.

**Clarity issue**:
I would like to see the following points improved.
- The definitions of the discrepancy and error terms $D(\alpha), E(\alpha)$ is ambiguous as of Section 2, which may lead to some potential misunderstanding. For example, "... cannot be estimated similarly to the learning errors $E(\alpha)$" (l.187), but I thought the error term only depends on the source domain, which turned out to be false at l.203 and I understood that $E(\alpha)$ contains the joint error $\lambda_\mathcal{G}$ as well.
- Why do we put the balancing condition as in Eq. (11), not $D(\alpha^*) = E(\alpha^*)$ as in the case of inverse problems?
- (l.136) "Using Eq. (3), the source error can be further upper bounded by the empirical source error": This is not clear because Eq. (3) is a concentration bound for the target domain. Do you assume the similar bound for the source domain, too?

**About the domain adaptation bound**:
In Eq. (4), the common domain adaptation is shown.
As far as I understand (please let me know if the following is wrong), the DA bound based on $\mathcal{G}$-divergence is not correct, although it is presented in [7].
Indeed, the proof of Theorem 1 in [7] upper bounds $\mathcal{H}\Delta\mathcal{H}$-divergence by $\mathcal{H}$-divergence, which does not hold in general.
To make it precise, we need to bound by $\mathcal{G}\Delta\mathcal{G}$-divergence as done in Theorem 2 in [27].

----
A few minor comments.
- (l.127) "the sampling error by $\eta_{t,\mathcal{G},\delta}$" instead of "the sampling error by $\eta_{z,\mathcal{G},\delta}$"?
- (Eq.(6)) the argument in $\varepsilon_S^{(\rho)}$ should be $g_h \circ \phi$?
- (l.232) The numbering of Lemma is not aligned between the main text and the supplementary material. Could you align or mention it at least?
limitations_and_societal_impact: The authors have adequately mentioned potential social impacts in the concluding section.
review_title: null

Meta-review: The submission proposes the balancing principle to tackle hyper-parameter selection in unsupervised domain adaptation, with an error bound for the target domain.  The reviewers were unanimous that the paper was above the acceptance threshold for NeurIPS.  In the post rebuttal discussion, it was pointed out that the method is supported by theoretical analysis, and although it is not likely that this current paper will be the final word on model selection for domain adaptation, that it provides a concrete step forward in a topic that has a lack of theoretical analysis.  As such, it is of interest to the NeurIPS community and may foster additional research and analysis on the topic.
Decision: Accept (Poster)