Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work provides UDA bounds based on the information-theoretic tools. Accordingly, new UDA methods are proposed with empirical evidence. 
strength_and_weaknesses: Strength:

1. The theoretical analysis in Section 5 is interesting and novel to me.

2. Applying SGLD to UDA, though itself is not initially developed in this paper, is novel to me.


Weakness:

1. As the authors claimed, the KL term upper bounds some other measures (e.g., Wasserstein distance), which indicates that the bound is looser and therefore less informative. 

2. In the literature, algorithm-dependent bounds have already been developed. For example, in [1], the expected target loss is upper bounded in terms of the performance gap, which depends on the learning algorithm. Unfortunately, the authors did not provide an in-depth analysis of or comparison with existing works along this line, which is related to this paper. 

3. Page 5: squared loss does not satisfy the triangle inequality. In fact, it satisfies the \emph{approximate triangle inequalities} [2].

4. The entire theoretical analysis in Section 4 is incremental – it is more like a rephrasing of existing conclusions using the information-theoretic language, which does not provide any new insight. For example, it is hard to understand what is the difference between $\lambda^*$ in Theorem and $\lambda$ in [3].

5. More detailed description is needed to understand the intuition behind $I(W;Z|X_j’)$ or $I(X_j’;Z|W)$.

6. The authors noted that the bound in Theorem 5.3 only depends on $n$. From my aspect, it indicates that the bound cannot verify the benefits of target data, but just SGLD itself. In other words, there is a gap between Theorem 5.1 and Theorem 5.3.

7. The empirical results are not convincing. The authors should evaluate the method on more practical benchmark data sets (e.g., Office-Home, VisDA, DomainNet…). In addition, compared with a recent baseline (KL), the improvement is not significant.


[1] Wang, B., Mendez, J., Cai, M. and Eaton, E., 2019. Transfer learning via minimizing the performance gap between domains. Advances in Neural Information Processing Systems, 32.

[2] Crammer, K., Kearns, M., & Wortman, J. (2008). Learning from Multiple Sources. Journal of Machine Learning Research, 9(8).

[3] Ben-David, S., Blitzer, J., Crammer, K., Kulesza, A., Pereira, F., & Vaughan, J. W. (2010). A theory of learning from different domains. Machine learning, 79(1), 151-175.


Questions:

1. On page 5, is the random variable T’ above Eq. 4 sampled from the source or target? 

2. Remark 5.1, why the mutual information will vanish as $n, m \rightarrow \infty$ (as it is already defined over the expectation)?

3. Theorem 5.1, the average over $m$ and $n$ seem unnecessary since RHS is already defined over the expectation.

4. The mathematical definition of $I^{T_j’}(W;Y_i|T_i)$ is not clear to me.

5. Theorem 5.3 is strange to me -- does it mean a small T will give a better generalization performance?





clarity,_quality,_novelty_and_reproducibility: Some details and intuitions need more clarification. 
summary_of_the_review: While this paper provides some new insights into UDA, I don't think it is ready to publish in a top-tier conference (e.g., ICLR) given the weaknesses mentioned. However, it could be a good paper if the authors can carefully address the issues.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work proposed the information-theoretic generalization error analysis of UDA. Especially the authors provided two approaches, PP generalization error and expected EP generalization error, which are based on the change-of-measure inequalities. Then the authors discussed these bounds about existing algorithms, especially margin alignment. Finally, based on the theoretical analysis, the authors proposed two algorithms: gradient regularization based on mutual information and controlling label information based on the entropy decomposition. The numerical experiments support the usefulness of these algorithms.
strength_and_weaknesses: # Strength
-  The authors discuss how the obtained bound relates to existing algorithms in detail. The authors discussed how the KL divergence obtained by the change-of-measure inequality relates to margin alignment methods in Theorem 4.2 and Sec 5.3.
- The second generalization error bound (expected EP generalization error) in Theorem 5.1 seems novel and leads to the useful algorithm in Theorem 5.3.
- The obtained algorithm is solid based on Theorem 5.3 and seems easy to implement and improve existing methods, as shown in Table 1.

# Questions and Weakness
- According to the Appendix, the authors used cross-entropy loss, but I am not sure the cross-entropy loss satisfies Assumption 2 of subgaussianity since the cross-entropy loss is unbounded.
- In the algorithm, when taking the gradient of the gradient penalty, does the Hessian appears in the update rule? Or did the authors use detach function in pytorch so that the Hessian would not appear?
- The method of controlling label information requires additional memory and computation since it requires the subnetwork to generate $\tilde{W}$.
- I would like to know the exact definition of $P_{W,Z'|X'_j=x'_j}$. Does this mean $Z'=(Y',X')$ is the test data in the target domain, and $X'_j=x_j'$ is the training data of unlabelled data in the target domain ?
- I would like to know the performance of CL+GP, where both the controlling label information and gradient penalty is applied. Does this lead to better performance? Or does the use of two techniques regularize the information too much and is harmful to UDA?
clarity,_quality,_novelty_and_reproducibility: Paper is well written and not difficult to follow. The present generalization error bound, especially Theorem 5.1 and obtained algorithms seems novel. 

summary_of_the_review: This paper presents the novel information-theoretic generalization error bound in UDA, which significantly generalizes the existing analysis and algorithms.
Also, the authors showed that the gradient penalty is useful in UDA by connecting it to the obtained MI in the generalization error bound. I think the results obtained in this paper are worth publication.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper use an information-theoretic framework to analyze the generalization ability of hypotheses and
learning algorithm of unsupervised domain adapation problem.
strength_and_weaknesses: Strength:
1、The authors rigorously prove some generalization error bound. One of the bounds is associated only
with the learning algorithm, which is very different from other work.
2、The author designs a new algorithm on the UDA problem based on their theory and achieves good
results compare to other methods in the otatedMNIST and Digits datasets.
3、The author has relaxed the previous strong assumptions[1], so that the conclusions drawn are closer to
the real situation. And the author add gradient penalty based on this, which can be applied to any existing
UDA algorithm
[1] A. Tuan Nguyen, Toan Tran, Yarin Gal, Philip Torr, and Atilim Gunes Baydin. KL guided domain
adaptation. In International Conference on Learning Representations, 2022. URL https:
//openreview.net/forum?id=0JzqUlIVVDd.

weakness：

1、The experiments are limited. Experiments on some popular datasets ( Office-Home, Office-31) have not been reported in the paper. The authors do not state how the results of the experiments match the theory analyzed clearly. 

2、I don't understand how the first inequality sign of Equation (14) is derived from Lemma 1. How to use the independence condition between the algorithms  and unseen target data.

3、Compare to other UDA paper, this paper lack visual instructions such as t-SNE.

4、The paper lacks ablation experiments with gradient penalties to demonstrate the effectiveness of this design.
clarity,_quality,_novelty_and_reproducibility: The paper is well written and the code is provided.  

summary_of_the_review: This paper give some bounds of UDA problem. The authors propose generalization error bounds relevant only to the learning algorithm, which is very different from previous work. In addition, the authors analyze previous work and relax its strong assumptions. And based on this, a controlling label information algorithm is proposed. However, there are some details of the proof that are not clearly written. Besides, there is a lack of explanation of experimental results and theoretical analysis.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the problem of *unsupervised domain adaptation* (UDA): described as a supervised learning problem where the source and target domain distributions are different and the learning algorithm has access to labelled source and unlabeled target data.

The paper considers the *empirical-to-population* (EP) generalization error in this setting, which is defined as 
$$\textnormal{Err}(w) = R_{\mu'}(w) - R_s(w),$$

where $R_{\mu'}$ is the population risk in the target domain distribution $\mu'$ and $R_s$ is the empirical risk in the source domain with a dataset $s = \lbrace z_i\rbrace_{i=1}^n$ sampled i.i.d. from the source distribution $\mu$. 

Traditionally, in the domain adaptation literature, the studied error is the *population-to-population* (PP) generalization error
$$\widetilde{\textnormal{Err}}(w) = R_{\mu'}(w) - R_\mu(w),$$

since one may decompose the EP generalization error $\textnormal{Err}$ into the PP error and the classical generalization error, for which there is a large literature in its characterization, namely
$$
    \textnormal{Err}(w) = \widetilde{\textnormal{Err}}(w) + \big[R_\mu(w) - R_s(w) \big].
$$

The paper employs known techniques from the classical generalization community to bound differences of expectations of the same function to develop bounds of both the EP error and the PP error. These bounds are both tighter and more insightful than previous bounds: e.g., the bounds in Section 5 can make use of the unlabeled data. This way, also taking from the classical generalization community, they find bounds on the stochastic gradient Langevin dynamics algorithm (SGLD).

Then, they use the insights obtained from the derived bounds to develop regularization strategies that result in better EP generalization error in their experiments.
strength_and_weaknesses: **Strengths**

* The paper combines nicely the known techniques to bound the classical generalization error in the UDA setting. Typically these are only used to bound the PP error and not the EP error.

* The resulting bounds are often tighter than those in the literature and some of them provide new insights into the UDA problem.

* The resulting regularization strategies obtain better results than the known schemes to improve domain adaptation.

**Weaknesses**

* Although the classical generalization error papers introducing the techniques used to bound the difference of expectations are quickly cited in the related work section, it is not clear in the main text where and how these techniques are used or how they inspired the bounds in the main text. 

    * Section 4.1. is strongly powered by Lemma A.1. which is basically Lemma 1 in *[Xu and Raginsky 2017]* letting $\mathcal{X} \times \mathcal{Y} = \Theta$, $P_{X,Y} = Q$, and $P_{X} \otimes P_{Y} = P$.
    * Section 4.2. (Theorem 4.4., Corollary 4.3, and the discussion around them) is based on *[Rodríguez-Gálvez et al. 2021]*.
    * Section 5.1. is first based on the disintegration ideas from *[Negrea et al. 2019]* and then on the decompositions of *[Rodríguez-Gálvez et al. 2021]*.
    * Section 5.2. is based on the information-theoretic analyses of SGLD and noisy SGD *[Pensia et al. 2018, Bu et al. 2019, Negrea et al. 2019, Haghifam et al. 2020, Rodríguez-Gálvez et al. 2021b, Neu et al. 2021, Wang and Mao 2022]*. 
    * Also in Section 5.2., it is stated that gradient penalty is strongly theoretically justified for standard supervised learning based on Theorem 5.3. Similar observations can be made from the results on standard generalization error from both the information-theoretic *[Negrea et al. 2019, Haghifam et al. 2020, Rodríguez-Gálvez et al. 2021b, Neu et al. 2021, Wang and Mao 2022]* and ODE analysis *[Smith et al. 2021]* communities.

* The discussion around the lower bound on the target domain population risk of Corollary 4.1. is confusing (at least to me). The result says that $R_\mu(w) - \sqrt{2R^2 D_{\textnormal{KL}}(\mu' \lVert \mu)} \leq R_{\mu'}(w)$. The discussion refers to this as a fundamental difficulty in UDA learning, since using the same predictor $f_w$ the population risk in in the target domain cannot be lower than that of the source domain minus a constant depending on the domain difference. However, I understand this as a potential advantage: one can design algorithms that attain lower population risk in the target domain than in the source domain when the domains are sufficiently different. 

* The discussion in Section 5.3. can be strengthened. The authors note that the expected cross-entropy loss for each $Z_i$ can be decomposed as (6) $$\mathbb{E}[\ell(f_W(T_i),Y_i)] = H(Y_i|T_i) + \mathbb{E}[D_{\textnormal{KL}}(P_{Y_i|T_i,W} \lVert Q_{Y_i|T_i,W})] - I(W;Y_i|T_i).$$ 
Then they proceed to say that minimizing the expected cross entropy may not adequately reduce $H(Y_i|T_i)$ but increase $I(W;Y_i|T_i)$. However, note that $I(W;Y_i|T_i) = H(Y_i|T_i) - H(Y_i|T_i,W)$, and therefore (6) can be simplified to $$\mathbb{E}[\ell(f_W(T_i),Y_i)] = H(Y_i|T_i,W) + \mathbb{E}[D_{\textnormal{KL}}(P_{Y_i|T_i,W} \lVert Q_{Y_i|T_i,W})],$$
suggesting that minimizing the expected-cross entropy will minimize $H(Y_i|T_i,W)$. Since conditioning reduces the entropy $H(Y_i|T_i,W) \leq H(Y_i|T_i)$, so minimizing $H(Y_i|T_i,W)$ does not need to minimize $H(Y_i|T_i)$, effectively having an effect of maintaining a large conditional mutual information $I(W;Y_i|T_i)$.

* The proof of Theorem 4.2. seems to need the extra assumption of having symmetric losses, i.e., losses such that $\ell(x,y) = \ell(y,x)$ for all $x,y$. 

(*Sorry for the slight change in notation in the following two bullet points, the OpenReview render is not happy with subscripts in the expectation symbols $\mathbb{E}$*.)

* Theorem 4.3. and its proof seem a little confusing to me. In *[Germain et al. 2020]* the domain disagreement is defined as $$\textnormal{dis}(P_X,P_{X'}) = \big| E_{W,W'} \big[E_{X'}[\ell(f_W(X'),f_{W'}(X')] - E_{X}[\ell(f_W(X),f_{W'}(X)] \big] \big|,$$ 
however in the text it is written as $$\textnormal{dis}(P_X,P_{X'}) = \big| E_{W,W',X'}[\ell(f_W(X'),f_{W'}(X')] - E_{W,W',X}[\ell(f_W(X),f_{W'}(X)] \big|,$$ 
which is confusing since usually there is a relationship between $W$ and $X$, as the parameters of the model's function depend on the data. Hence, it appears like if in the proof of Theorem 4.3. there is a flaw regarding the conditioning. Let's focus on the first array of three inequalities and on the first term on the right-hand-side. Essentially, the proof states that $$\sup_{W, W' \in \mathcal{W}^2} E_{X'}[t \ell(f_W(X'),f_{W'}(X')] \leq E_{W,W'} \big[E_{X'}[t \ell(f_W(X'),f_{W'}(X')] \big] \leq E_{W,W',X'} [t \ell(f_W(X'),f_{W'}(X')],$$ 
and if $W$ and $X$ are related this is not true. 

    * This may be easily fixed by making sure that the independence of $W,W'$ and $X$ and $X'$ is clear in the definition from *[Germain et al. 2020]*.

* In Theorem B.1. it is stated that without loss of generality one may assume that $\alpha \leq \mathbb{E}[e^{g(\hat{Z})}] \leq \mathbb{E}[e^{g(Z)}]$, where $\hat{Z} \sim \hat{\mu}$ and $Z \sim \mu$, for some constant $\alpha > 0$ and any $g$. I can understand the fist inequality concerning $\alpha$, but I do not see why the moment generating function of $g(Z)$ dominates that of $g(\hat{Z})$ in general.

* In Theorem B.2., after solving for Theorem 11.2.1. in *[Cover and Thomas, 2006]* one gets the standard dependence on the probability $\frac{1}{n} \log(1/\delta)$, not $\frac{1}{n \log \delta}$.


**References**

*[Cover and Thomas, 2006]* Elements of information theory. \
*[Xu and Raginsky, 2017]* Information-theoretic analysis of generalization capability of learning algorithms.\
*[Pensia et al. 2018]* Generalization error bounds for noisy, iterative algorithms. \
*[Bu et al. 2019]* Tightening mutual information based bounds on generalization error. \
*[Negrea et al. 2019]* Information-theoretic generalization bounds for SGLD via data-dependent estimates. \
*[Germain et al. 2020]* PAC-Bayes and domain adaptation. \
*[Haghifam et al. 2020]* Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. \
*[Rodríguez-Gálvez et al. 2021b]* On random subset generalization error bounds
and the stochastic gradient Langevin dynamics algorithm. \
*[Smith et al. 2021]* On the origin of implicit regularization in stochastic gradient descent. \
*[Rodríguez-Gálvez et al. 2021]* Tighter expected generalization error bounds via Wasserstein distance. \
*[Neu et al. 2021]* Information-theoretic generalization bounds for stochastic gradient descent. \
*[Wang and Mao, 2022]* On the generalization of models trained with SGD: information-theoretic bounds and implications.  
clarity,_quality,_novelty_and_reproducibility: * **Clarity**: The paper is clear and well-written.

* **Quality**: The quality of the paper is good. As mentioned in the review, the resulting bounds are tighter and some of them reveal interesting insights. Also, the regularization scheme empirically performs better than previous schemes in the literature.

* **Novelty**: While the techniques are not novel and have been employed previously (see weaknesses), their use in the UDA is novel as far as I know. Nonetheless, the resulting bounds and insights are indeed new, as well as the regularization technique.

* **Reproducibility**: \
    *Theory*: I reproduced all the proofs except for the questions that I placed the authors in the weaknesses. 
    
    *Experiments*: There is code provided to reproduce the experiments.  I hope this code is then uploaded to some easily accessible repository and with an easy link in the main text.
summary_of_the_review: This paper finds upper bounds on the empirical-to-population (EP) and population-to-population (PP) generalization error in unsupervised domain adaptation (UDA). 

To do so, the paper employs various techniques used to bound the classical generalization error. Using these techniques the resulting bounds are tighter than other bounds in the literature and some provide interesting insights on what is necessary/important to succeed in UDA. 

Finally, the paper uses such insights to develop regularization strategies that result in better domain adaptation than previous schemes.

The paper is a good contribution to the community and therefore I lean towards acceptance. Nonetheless, there are some issues to improve (see Weaknesses) such as proper crediting to the inspiring work on bounding the classical generalization error, from which most of the bounding techniques are taken; the discussion around Corollary 4.1. and (6); the assumptions needed for 4.2.; the point raised about Theorem 4.3.; and some statements in Theorems B.1. and B.2. I believe all of them are small and doable during the rebuttal phase.
 

**Minor comments and nitpicks that did not impact the score of the review**

* In the third paragraph of the introduction you use the terms PP and EP without explaining them. It would be good to write what they mean.
* In the 4th line of the Preliminary, 'hypothesis space of ~~interesting~~ interest,'
* In page 3, line 5, 'an algorithm $\mathcal{A}$ that takes'
* In Assumption 3: is $\beta$-Lipschitz ~~continues~~ continuous.
* Also in Assumption 3. Lipschitz continuity is defined with respect to a metric $d$. So I recommend to say that $\ell(f_w(X),Y)$ is $\beta$-Lipschitz continuous in $\mathcal{Z}$ with respect to a metric $d$ on $\mathcal{Z}$ for any $w \in \mathcal{W}$.
* You say that (3) is remarkable. What is remarkable about such a result? It seems reasonable and in line to the previous literature. 
* In page 5, could you add a reference (or some references) after the claim that "A common method is to assign pseudo labels to target data based on a learned source classifier". 
* In Theorem 4.5 and its proof, the Lipschitz constant should always be $\beta$, sometimes you also write $L$.
* There is a change in notation for probabilities in the second to last paragraph in page 8. The one starting with "Notice that...".
* In the proof of Theorem 4.2 one can go from (8) to the equation after (9) directly using the triangle inequality.
* Could you provide the exact equation or theorem for the classic VC-dimenstion generalization bound in the proof of Theorem B.1.
* In the last line of page 18: 'might exist a ~~more optimal~~ faster convergence rate'.
* One can go directly from the third to the last equality in Section C.7. using the classical definition of conditional mutual information $I(X;Y|Z) = H(Y|Z) - H(Y|X,Z)$.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper presents work on the upper bounds of UDA problem, in particular the generalization error bounds relevant only to the learning algorithm and also provides techniques for improving generalization with experimental validation.

Strengths 
All the reviewers agreed on manuscript novelty, specifically the application of Stochastic Gradient Langevin Dynamics (SGLD) to Unsupervised Domain Adaptation (UDA). It was observed that the work demonstrated tighter upper bounds for two notions of generalization errors compared to previous work. Their work also provides new insights into algorithm designs for the UDA problem. 

Weakness: 
A reviewer mentioned that the bound is loss and theoretical analysis is kind of incremental given the existing results. The cross-entropy loss, which is used in the paper, might not satisfy the assumption of subgaussianity. It is not well addressed in the rebuttal.  Perhaps some work might have been done to demonstrate subgaussianity since it is explicitly mentioned in the paper.  Another weakness is that the technique is not new which also pointed by reviewers. It seems that the practical insight provided by the theoretical results is only about restricting the gradient norm, which has nothing to do with UDA itself. All these concerns are not well addressed in the rebuttal. 


justification_for_why_not_higher_score: 1) A reviewer mentioned that the bound is loss and theoretical analysis is kind of incremental given the existing results. 2) The cross-entropy loss, which is used in the paper, might not satisfy the assumption of subgaussianity. 3) It seems that the practical insight provided by the theoretical results is only about restricting the gradient norm, which has nothing to do with UDA itself. 4) The empirical results are not quite convincingIt is not well addressed in the rebuttal. It is not well addressed in the rebuttal. 

justification_for_why_not_lower_score: All the reviewers agreed on manuscript novelty, specifically the application of Stochastic Gradient Langevin Dynamics (SGLD) to Unsupervised Domain Adaptation (UDA).
Decision: Accept: poster